# What are rainbow tables and how are they used?

Where can I find one? Is there a pot of gold at the end?
How do I protect against them?

From the Area51 proposal

This question was IT Security Question of the Week.
Read the Sep 09, 2011 blog entry for more details or submit your own Question of the Week.

-
+1 for the "pot of gold" –  Nathan Osman Apr 7 '13 at 3:24
There is a very good tutorial that illustrates on how rainbow table works here: techshangrila.blogspot.sg/2015/01/how-rainbow-table-works.html (see the video) –  william007 Jan 13 at 8:40

Rainbow Tables are commonly confused with another, simpler technique that leverages a compute time-storage tradeoff in password recover: hash tables.

Hash tables are constructed by hashing each word in a password dictionary. The password-hash pairs are stored in a table, sorted by hash value. To use a hash table, simple take the hash and perform a binary search in the table to find the original password, if it's present.

Rainbow Tables are more complex. Constructing a rainbow table requires two things: a hashing function and a reduction function. The hashing function for a given set of Rainbow Tables must match the hashed password you want to recover. The reduction function must transform a hash into something usable as a password. A simple reduction function is to Base64 encode the hash, then truncate it to a certain number of characters.

Rainbow tables are constructed of "chains" of a certain length: 100,000 for example. To construct the chain, pick a random seed value. Then apply the hashing and reduction functions to this seed, and its output, and continue iterating 100,000 times. Only the seed and final value are stored. Repeat this process to create as many chains as desired.

To recover a password using Rainbow Tables, the password undergoes the above process for the same length: in this case 100,000 but each link in the chain is retained. Each link in the chain is compared with the final value of each chain. If there is a match, the chain can be reconstructed, keeping both the output of each hashing function and the output of each reduction function. That reconstructed chain will contain the hash of the password in question as well as the password that produced it.

The strengths of a hash table are that recovering a password is lightning fast (binary search) and the person building the hash table can choose what goes into it, such as the top 10,000 passwords. The weakness compared to Rainbow Tables is that hash tables must store every single hash-password pair.

Rainbow Tables have the benefit the person constructing those tables can choose how much storage is required by selecting the number of links in each chain. The more links between the seed and the final value, the more passwords are captured. One weakness is that the person building the chains doesn't choose the passwords they capture so Rainbow Tables can't be optimized for common passwords. Also, password recovery involves computing long chains of hashes, making recovery an expensive operation. The longer the chains, the more passwords are captured in them, but more time is required to find a password inside.

Hash tables are good for common passwords, Rainbow Tables are good for tough passwords. The best approach would be to recover as many passwords as possible using hash tables and/or conventional cracking with a dictionary of the top N passwords. For those that remain, use Rainbow Tables.

-
Oh my goodness, I admit to being shocked - I discuss and explain Rainbow tables all the time, and all this time it seems I have been one of the "commonly confused"! I would totally +1000 times, I really learned something new here (and I thought I knew the answer). Glad I asked the question after all... Thank you! –  AviD Nov 18 '10 at 16:25
Though to be specific (now that you opened my eyes I did some more research :) ), Rainbow Tables are differentiated from Hellman Hash Chains by using several different reduction functions. More complex indeed... but really quite a beautiful idea (Ah! is that why they're called "Rainbow" tables?) –  AviD Nov 18 '10 at 16:28
I agree this is a very good explanation. In my answer I explained it simply and also really explained it wrong by being to simple. The beauty of Rainbow tables are the fact they don't store every hash value. I am going to edit mine but also up voting this as it is definitely a better explanation. –  Mark Davidson Nov 18 '10 at 16:28
Hmm... Though the more I think about it, in real life systems Rainbow Tables are nowhere near as useful as hash tables. As you stated, for common passwords hash tables are much better (since they are order of magnitude faster, and the size requirements for a password dictionary are of course much smaller than the entire possible range of passwords). And who're we kidding? Most passwords fall into that category, it is very rare (and will be for some time) that you need to call in RT. –  AviD Nov 18 '10 at 16:33
the only thing missing is the "how to protect". I'd like to accept your answer if you can add that in. –  AviD Nov 23 '10 at 14:09

There are many good explanations of what rainbow tables are, this one How Rainbow Tables work is particularly good. Also the Wikipedia article has a very good explanation as well. For a bit more indepth reading the definitive paper on the subject is Making a Faster Cryptanalytic Time-Memory Trade-Off.

A simple explanation of Rainbow Tables is that they make use of a time memory trade off technique. Meaning instead of taking a target hash value and a dictionary of words then hashing each word and doing the comparison on the fly (brute force approach using something like John), you instead hash all the values in the dictionary in advance (this may take a very long time depending on dictionary size). But once its done you can compare as many hashes as you want against the pre hashed values in the rainbow tables this is significantly faster than calculating the hashes again.

The explanation I wrote here previously in an effort to be short was misleading, since it did not explain the use of reductions that rainbow tables make use of. For a better explanation till I rewrite this bit see @Crunge answer.

You can either generate the rainbow tables yourself using an application like RainbowCrack or you can download them from sources like The Shmoo Group, Free Rainbow Tables project website, Ophcrack project and many other places depending on what type of hashes you need tables for.

To protect against a Rainbow Table based attack the most effective method of combating it is to ensure that every hash within a system is salted. This makes pre-generated rainbow tables useless and would mean an attacker would have to generate a custom set of tables to use against the targeted hashes, which would only be possible if they knew the salt.

-
Furthermore (consider editing this in), if you use a different salt for every password, recording it unencrypted in the database, then the attacked would need to generate a custom set of tables for each hash, which would defeat the object of the exercise - the whole point of the rainbow table is to brute force the whole password-space and then get all the passwords for one brute-force effort; if you're only getting one password per rainbow table, then you might as well directly brute force the hash. –  Richard Gadsden May 13 '11 at 14:32