Rainbow tables for password cracking

An announcement about a new site offering free 'rainbow tables' on the bugtraq mailing list sparked our interest; what are these tables and what can they be used for? It turns out that rainbow tables are the result of pre-computing various one-way hash functions to facilitate decrypting them. In effect, the right set of tables makes a one-way hash function reversible for certain inputs and the inputs of interest are passwords.

Many applications use one-way hash functions (such as MD5 or SHA1) to store passwords because they hide the password value from prying eyes, but it is easy to compare hashed passwords when a user logs in. This relies on the fact that it is difficult to reverse the hash function and produce the original password, but the application can just apply the hash function to the password presented and compare the output to the stored hash. Operating systems, database management systems, web and other applications often use this method to store their users' passwords.

For those that might want to crack a password, a straightforward, but very time consuming method would be to brute force it. Generate the hashed values for each string in the password search space and compare it to the hashed value of interest; when they match, the password is cracked. If one needed to crack passwords regularly, it might make sense to store the password to hash mappings so that it would just take a lookup to find any previously cracked password. The storage requirements of that kind of table, for any plausible set of potential passwords (say 1-8 alphanumeric characters) are huge. Rainbow tables are a way to reduce the storage requirements substantially while still preserving much of the speed benefits of using a lookup table.

To create a rainbow table, you must first come up with a reduction function that takes a hash as input and maps it to a password in the search space. You then start with a password and repeatedly hash and reduce it several thousand times creating a chain of passwords. You discard all but the first and last password and store that pair. To reverse a particular hash value, you reduce the hash value and look for that password as the end of one of the chains. If you do not find it, then you hash and reduce again. Once you find a matching end of the chain, you use the first password to recreate the chain and the cracked password is the second to last in the chain.

This ingenious scheme comes from a paper presented at the CRYPTO 2003 conference. The paper is a bit dense if you are unfamiliar with the references cited, so the author has a simplified explanation as well.

Rainbow tables are specific to a particular hash algorithm and password search space and that is where the free rainbow tables site comes in handy. There are currently two tables available there, one for MD5 and one for the older Windows DES-based password algorithm. The MD5 version is 36Gb in size and will crack 99.9% of lowercase alphanumeric passwords that are eight characters or less in length. The site also has links to other sites with tables as well as to the Project RainbowCrack site which has source for various programs to generate and use the tables.

The best defense against rainbow tables is 'salt', which has been a part of UNIX passwords since near the beginning of time (UNIX epoch time anyway). Salt is a random string that is added to the password before hashing it and then stored with the password. Linux MD5 passwords store the salt between two dollar signs in the password field in /etc/shadow. This random string effectively multiplies the number of tables required to do a dictionary lookup by the number of individual salt values available. Even just eight bits of salt (and Linux uses much more than that) would require nine terabytes of rainbow table.

While this technique is not particularly effective at recovering OS passwords (at least on Linux), there are quite a number of web applications that store straight MD5 passwords without any salt (and some, sadly, store plaintext passwords). Other applications may do that as well. If the password hashes become exposed via a SQL injection or other flaw, rainbow tables could be just the ticket to breaking into those systems.