Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
2  
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
add comment

1 Answer

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.

share|improve this answer
    
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 –  owlstead Feb 14 '13 at 17:29
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.