Rainbow Tables Not Considered Harmful

Since the LinkedIn password dump was posted online a couple of weeks ago, there's been a lot of discussion about hashing algorithms, salts, and, of course, rainbow tables.  Rainbow tables were described in Phillipe Oechslin's 2003 paper Making a Faster Cryptanalytical Time-Memory Trade-Off and are a type of lookup table for password hashes that only require a fraction of the storage needed for a naive lookup.  You might, for instance, only store 1/2000 hashes. 

Rainbow tables seemed like a pretty big deal at the time.  Rather than an attacker brute-forcing passwords every time he needs to crack some hashes, an attacker can make tables ahead of time so that he will only have to perform a relatively quick lookup operation later.  This is way more efficient than brute force if the attacker is dealing with unsalted password hashes from relatively small sites (thousands of users or less). 

Today, rainbow tables don't seem like such a big deal after all.

The problem is that rainbow tables don't scale.  With rainbow tables, each hash has to be considered individually and a single lookup can take about a minute of processing time.  This is pretty manageable if you're attacking a few thousand hashes, but it's totally unworkable for a large site (millions of passwords).  In some cases, the attacker only needs to attack a few accounts.  When attacking a Windows network for instance, the attacker may start out by attempting to crack only the administrator accounts.  Rainbow tables are still useful here and can be used to attempt to quickly recover a few key passwords before resorting to brute force.

In other cases, as with the LinkedIn hack, there isn't a lot of benefit in cracking a single account password.  Instead, the benefit is in being able to crack large numbers of passwords.  The attacker might use these accounts to get into other more profitable accounts (email, banks, etc) or just sell the accounts and let someone else do that.  Using rainbow tables, it would take more than 11 years to look up all 6.5M LinkedIn passwords.  For mixed-case alphanumeric passwords of 8 characters or less, brute force would take no more than a few days with a GPU-based password cracker.

Rainbow tables also do not work at all against strong password hashing algorithms such as scrypt, bcrypt, or PBKDF2.  Salting makes precomputation and storage impossible because no one on Earth will ever be able to build or store tables for 2¹²⁸different salt values.  I discussed the numbers in my previous post.  It's impossible, not just with current technology but with any technology.  There is not enough matter on Earth to build a storage device for that. 

Password stretching (using a slow password hashing algorithm or iterating a fast one thousands of times) also makes precomputation impractical.  Being able to build rainbow tables for any reasonable character set and length (7-10 characters) depends on being able to compute millions or billions of password hashes per second.  Password stretching can slow this to tens or hundreds of passwords per second which puts the work required beyond the capacity of any individual with only one or a few machines at his disposal.  Creating the tables might still be possible with a distributed computing effort, but looking up a hash in the table could still take a week or more. 

In short, rainbow tables are still useful in narrow circumstances, but they aren't devastating.  They don't work against strong password hashing algorithms and they aren't useful against a large number of users.