# brute force attack on KDF vs KEY

if we believe 256bit keys are secure in AES against any brute force attack, is that possible we use a KDF (convert user's weak entered password in truecrypt into a fixed AES key) with too much round and cycle to make a weak password (with All ASCII printable characters) secure as a true binary 256bit random key ? assume we want KDF proccesing don't take more than a few seconds on general today computers, how to compute relation btw KDF cycles and key's Entropy ? (what's possible length of an KDFed ASCII password which is secure as a 256 bit key ?)

-
You can increase the security level by perhaps 20-40 bits using a slow KDF. So to reach 256 bits, the suer would still need a really strong password. –  CodesInChaos Feb 9 '13 at 15:43
@CodesInChaos - I'm curious to know how you arrived at that estimation of 20-40 bits. Is it reasonable to assume that the slower the KDF (ie, scrypt as opposed to pbkdf2), the more 'bits' of security added? –  hunter Feb 11 '13 at 17:27
@hunter 20 bits fits a million iterations of PBKDF2, and scrypt is a bit costlier due to the high RAM requirement, so I guessed 40. I was too lazy to do any actual math. –  CodesInChaos Feb 11 '13 at 17:46

There are two forms of entropy here at work. First there is "uncertainty" entropy from the user password which is typically very low (on the order of 20 to 40 bits for most passwords out there). And then, there's "computational" entropy, which is artificially obtained by forcing an attacker to do work to calculate keys.

Essentially, if you run your KDF for $k$ iterations, you'll add about $\log_2(k)$ bits of computational entropy.

This doesn't take into account the fact that not all KDF's are equal, it is just an asymptotic observation.

So, yes, theoretically, you can transform a weak password of, say, 20 bits of entropy, into a very strong 256-bit key with roughly 256 bits of entropy, but you'd need $2^{256 - 20} = 2^{236}$ KDF iterations... at this point it may be more beneficial for the attacker to try a different approach. I mean, putting aside the fact that nobody is going to wait around to compute your KDF - the iteration count has to be low enough so that normal users can't feel it but attackers can (say, half a second per KDF invocation).

Also, what do you mean by a "KDFed ASCII password"? In general, the output of a KDF is used directly into a cipher or message authentication code, not as a new password. But, given that there's 96 ASCII printable characters (I think) then each character has a maximum entropy of $\log_2(96) \approx 6.58$ bits.

So to obtain 256 bits of entropy you'll need at least $256 / 6.58 \approx 39$ characters in your password.

-
a "KDFed ASCII password" would be a result of applying a KDF to an ASCII password. $\hspace{1 in}$ –  Ricky Demer Feb 9 '13 at 20:51
I'm not sure that the PRF within the KDF is strong enough to handle that many rounds, but I guess that's not going to be an issue :P –  Maarten Bodewes Feb 14 '13 at 17:29