brute force attack on KDF vs KEY

Question

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 ?)

Answer 1

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.