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

Solar Designer solar at openwall.com
Thu Jun 9 15:17:09 EDT 2011


Paul -

On Thu, Jun 09, 2011 at 10:37:56PM +0400, Solar Designer wrote:
> 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).

To support the "sounds sufficient" above, and to provide a more direct
answer to your question, it appears that the distributed.net project to
brute-force a 72-bit RC5 key is currently at only 1.66% of the keyspace,
after over 8 years of running on thousands of volunteers' computers:

http://stats.distributed.net/projects.php?project_id=8
http://www.distributed.net/RC5

Of course, computers' speed is increasing over time (especially with
GPUs), so they're going to do a lot more than 1.66% in another 8 years
(in fact, they're somewhat likely to crack the key sooner than that).

And they were lucky to successfully crack a 64-bit key in just 5 years
in 2002 (IIRC, they hit the correct key after having searched only a
small fraction of the keyspace).

Yet several years on thousands of computers sounds excessive for
something "not terribly valuable", so perhaps 67-bit key equivalent
would be enough for your purpose for a few years to come.  It all
depends on just how valuable the information is, and how long it must
remain "secure", vs. the inconvenience of typing a long passphrase.
Of course, go for an 80-bit key equivalent if you can afford that (more
stretching and an extra random word in a passphrase), or even further.

In this context, I am assuming that testing one RC5 key is roughly
equivalent to one iteration in a key derivation function.

Oh, also other attack vectors matter.  There might be little point in
using an extra-complicated passphrase when there's a bypass.

Alexander



More information about the cryptography mailing list