What are rainbow tables and how are they used?

Question

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.

Answer 1

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.

Answer 2

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.