[cryptography] Current state of brute-forcing random keys?

Solar Designer solar at openwall.com
Thu Jun 9 14:37:56 EDT 2011


Hi,

On Thu, Jun 09, 2011 at 10:14:49AM -0700, Paul Hoffman wrote:
> Greetings again. I am helping someone design a system that will involve giving someone a randomly-generated key that they have to type in order to unlock data that is private but not terribly valuable. Thus, we want to keep the key as short as practical to reduce typing and mis-typing, but long enough to prevent trivial brute-force attacks. The encryption will be AES-128 in CBC mode.
> 
> What is the current state of brute-force attacks on AES-128 blobs? Are there recent results where we can estimate the cost of brute-forcing 64-bit and 80-bit keys?

You need a good/suitable KDF:

http://en.wikipedia.org/wiki/Key_derivation_function

This will buy you an equivalent of maybe 20 bits of entropy (depending
on the settings you choose to use).  The much higher speed of direct
brute-force attacks on AES keys is then irrelevant.

For the KDF, you could consider scrypt (designed to make attacks with
specialized hardware relatively costly) or bcrypt (GPU-unfriendly),
although PBKDF2 using one of the SHA-2 family functions is more common
and easier to get accepted (but is weaker against those
massively-parallel attacks).

For some recent numbers, you may see the scrypt paper:

http://www.tarsnap.com/scrypt/scrypt.pdf

(although these focus on relative dollar costs for specialized hardware,
which might not be the most realistic attack scenario in your case).

In passwdqc, we're currently generating 47-bit random passphrases by
default, which per my estimates is about right given a decent and
reasonably configured KDF, as well as typical usability requirements:

http://www.openwall.com/passwdqc/

Here's what these look like:

$ while :; do pwqgen; done | head
Wall9Motion$allow
Vivid8Walk3Fitful
Want3big8murky
deadly4moor9And
pit+Such_Burma
Calmly7Spate&sad
Copy3Cheer=hebrew
Elect3Them$Wholly
Clear9hazy3Large
eleven6mouth_cup

If you add 1 million iterations of stretching in your KDF, 47 bits
encoded in a passphrase is roughly equivalent to a 67-bit AES key, which
sounds sufficient for something "not terribly valuable" (although
another factor is how long the security of this data must be maintained -
e.g., this same key size might be easy to brute-force in 10-20 years
from now).

...Oh, and maybe you can just reuse the scrypt file encryption program
almost as-is?

I hope this helps.

Alexander



More information about the cryptography mailing list