Rainbow Tables (Smart Table Recovery ™)

What are rainbow tables?

Rainbow table is a precomputed lookup table, which can be used to recover the password from its hashed representation. The use of a rainbow table is much faster than a simple brute-force attack (essentially, most hard work for cracking the password has been already done when the rainbow table was created)

You may think of the rainbow table as a lookup table which maps hash values to plaintext passwords. However, even for very small plaintext sets it is impossible to store all hashes because of memory requirements. Thus, rainbow tables don't store all hash values, but instead use a compact representation of plaintext password chains (or sequences).

How rainbow tables are computed

Each chain of the rainbow table is computed using a number of reduction functions, which map hashes to plaintext passwords (a reduction function is not an inverse of the original hash function). This is done in the following way: each chain starts with an initial plaintext password, which is passed through the hash function. The resulting hash is then passed through the first reduction function; this produces another plaintext password. This is repeated for a fixed number of iterations. Only the initial plaintext password and the last hash value for each chain are stored in the rainbow table. The length of the chain can vary: increasing the length decreases the table size but slows down the password lookup process. 

The table content does not depend on the password being recovered, but it depends on the set of plaintext passwords. For example, there can be a rainbow table for all alphanumeric passwords of length 8. To be more precise, the set of plaintext passwords defines the reduction functions, which will be used to compute the rainbow table because the reduction functions must be surjective (i.e. for each plaintext passwords there must be a hash value, which produces the given plaintext when passed through the reduction function).

How rainbow tables are used for password recovery

In order to recover the hashed password (which means reversing the hash), the password hash is run through the sequence of reduction functions. The structure of the rainbow table and the reduction functions guarantee that the resulting hash will match the final hash of one of the chains. Since the rainbow tables maps the final hashes of each chain to the initial plaintext password, the initial password is now known. Then the initial password is fed into the sequence of reduction functions until the original hash is found. The plaintext password used at the final iteration (which produced the original hash) is exactly the password, which is being recovered.

Rainbow tables are an improvement over an older technique, which also used chains of plaintext passwords. The improvement they offer is that a different reduction function is used to compute each link of the chain. This heavily reduces the probability of merging chains (since chains will merge only if the hash collision occurs at the same position in two chains), increases the probability to recover the password using a given size table and increases the speed of lookups. This is where rainbow tables got this name -- if each reduction function were colored differently, the sequence of reduction functions would indeed look like a rainbow.

Rainbow tables are specific to the hash function they were created for, so, for example a SHA1 table can be used to crack SHA1 hashes only.

Rainbow tables in our software

Rainbow table recovery method can be used in a number of situations. It is particularly good for recovering Windows NT/2000/XP/2003 passwords. It is also applicable for other tasks, such as recovering a password when its hash (MD5, MD4, SHA1 or any other) is known. Our engineers have improved the algorithm of rainbow tables significantly, making it several times faster. It is implemented in the following LastBit software:

• Windows Password v6.0 for recovering Windows passwords;
• Express Recovery Inhouse Edition for recovering Word and Excel 97-2003 documents.
• PDF Password for quickly decrypting PDF documents protected with a 40-bit password;