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
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
This ingenious scheme comes from a
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
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
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.
to post comments)