| HN Mirror

There are about 252 trillion or 2^48 passwords consisting of 8 symbols drawn from (uppercase/lowercase letters + numbers + space). These are presently available in a downloadable lookup table which uses a compression method called 'rainbow tables' to store this information in just 350 GB, if I am reading these numbers correctly. There are similar lookup tables which include all 32 symbols accessible from the keyboard out to 7 characters, taking up 130 GB on disk. These speedups and compressions are made by large distributed computing projects, and would otherwise be out of the range of normal consumers -- but now that the lookup table has been generated, it can be pretty quickly queried, as I understand it.

Salting a hash is meant to stop precisely these attacks, and these numbers were taken for MD5 in particular from:

    http://tbhost.eu/rt.php?algorithm=2

However this also gives us a bound on what's possible. A large project with 10,000 users trying to brute-force passwords can brute force all 2^48 of these, and store them in a highly compressed fashion, in however long it takes to make these things (months?). In theory, no password with under 48 bits of entropy is truly safe from someone with access to, say, government-scale computation.

What's possible for the rest of us? I can use Node.js to encrypt a typical password using PBKDF2(HMAC-SHA1) like so:

     crypto.pbkdf2('sconesMultiply51', '0SGrf8KIZ', Math.pow(2, 17), 18, logger)

This takes 377 ms on my web server and calls SHA1 something like 2^18 times (twice for HMAC, 2^17 for the PBKDF parameter above), 255ms on my laptop. It's also a wrapper for an OpenSSL routine. So this should be about typical for C routines, and I should be able to do 2^20/s without GPU speedups. (That's 2^36 passwords/day.)

The above password 'sconesMultiply51' only has 40 bits of unpredictableness, so give me about two weeks, '0SGrf8KIZ', and sha1('0SGrf8KIZsconesMultiply51') and I can quite possibly find 'sconesMultiply51' by brute force on a laptop.

GPUs make things faster. This site:

    http://www.insidepro.com/eng/egb.shtml

reports doing sha1($pass.$salt) 80 million times per second on an older GPU (an nVidia GTS250). So they can get 2^26/s. If they're right, then they could hypothetically find 'sconesMultiply51' in under a day, as long as you reconfigured them to start searching words from a 10,000-word dictionary which might optionally be capitalized, rather than individual characters.

What's the absolute upper bound? Well, thankfully, the biggest public supercomputers are actually very well-known and published on top500.org. The absolute top of the line today is this beast:

    http://i.top500.org/system/177232

It does 2^53 floating point operations per second. Assuming a hash is something like 100 or 1000 operations, you'd still have 2^43-2^46 tries per second. That's probably an upper limit on what your typical government can do, as well.

Lessons: (1) you'll be safe for the next 20 years at least if you just get used to

    head -c 9 /dev/urandom | base64 | sed 's/+/_/g;s/\//-/g'

and the 12-character passwords that result. (2) you can give people about 16-20 bits of extra security if you use key stretching techniques, but that's about it.