Rainbow table

A rainbow table is a lookup table offering a time-memory tradeoff used in recovering the plaintext password from a password hash generated by a hash function, often a cryptographic hash function. A common application is to make attacks against hashed passwords feasible. A salt is often employed with hashed passwords to make this attack more difficult, often infeasible.

Overview

A rainbow table is a compact representation of related plaintext password "sequences" (or "chains"). Each chain starts with an "initial password", which is passed through a hash function. The resulting hash is then fed into a "reduction function", which produces a different plaintext password. The process is then repeated for a fixed number of iterations. The initial and final passwords of the chain comprise a rainbow table entry.

Recovering a password using a rainbow table is a two step process. First, the password hash is run through the above reduce-hash sequence. The structure of the table and its reduction function guarantee that the running password will match a final password of one of the chains. This yields the initial password of the chain. Second, the iteration is repeated starting with this initial password until the original hash is found. The password used at the last iteration "is" the password being recovered.

The table content does not depend on the input of the algorithm. It is created once and then repeatedly used for the lookups unmodified.

Increasing the length of the chain decreases the size of the table. It also increases the time required to iterate over each chain, and this is the time-memory trade-off of the rainbow table. In a simple case of one-item chains, the lookup is very fast, but the table is very big. Once chains get longer, the lookup slows down, but the table size goes down.

Example

We have a hash ("re3xes") and we want to find the password that produced that hash.

1. Starting from the hash ("re3xes"), one computes the last reduction used in the table and checks whether the password appears in the last column of the table (step 1).

2. If the test fails ("rambo" doesn't appear in the table), one computes a chain with the two last reductions (these two reductions are represented at step 2)

   * Note: If this new test fails again, one continues with 3 reductions, 4 reductions, etc. until the password is found. If no chain contains the password, then the attack has failed.

3. If this test is positive (step 3, "linux23" appears at the end of the chain and in the table), the password is retrieved at the beginning of the chain that produces "linux23". Here we find "passwd" at the beginning of the corresponding chain stored in the table.

4. At this point (step 4), one generates a chain and compares at each iteration the hash with the target hash. The test is valid and we find the hash "re3xes" in the chain. The current password ("culture") is the one that produced the whole chain : the attack is successful.

Rainbow tables use a refined algorithm with a different reduction function for each "link" in a chain, so that when there is a hash collision in two or more chains the chains will not merge as long as the collision doesn't occur at the same position in each chain. As well as increasing the probability of a correct crack for a given table size, this use of multiple reduction functions approximately doubles the speed of lookups. See the paper cited below for details.

Rainbow tables are specific to the hash function they were created for e.g., MD5 tables can crack only MD5 hashes. The theory of this technique was first pioneered by Philippe Oechslin [http://lasecwww.epfl.ch/philippe.shtml] as a fast form of time-memory tradeoff [Citation
url = http://lasecwww.epfl.ch/~oechslin/publications/crypto03.pdf
first = Philippe
last = Oechslin
title = Making a Faster Cryptanalytic Time-Memory Trade-Off ] , which he implemented in the Windows password cracker Ophcrack. The more powerful RainbowCrack program was later developed that can generate and use rainbow tables for a variety of character sets and hashing algorithms, including LM hash, MD5, SHA1, etc.

Defense against rainbow tables

A rainbow table is ineffective against one-way hashes that include salts. For example, consider a password hash that is generated using the following function (where "." is the concatenation operator):

hash = MD5 (password . salt)

A large salt value prevents precomputation attacks, including rainbow tables, by ensuring that each user's password is hashed uniquely. This means that two users with the same password will have different password hashes (assuming different salts are used). In order to succeed, an attacker needs to precompute tables for each possible salt value. Even for older Unix passwords, which used a 12-bit salt, this would be improbable. The MD5-crypt and bcrypt methods--used in Linux, BSD Unixes, and Solaris--have salts of 48 and 128 bits, respectively.cite journal
url = http://www.usenix.org/publications/login/2004-06/pdfs/alexander.pdf
title = Password Protection for Modern Operating Systems | journal = ;login: | publisher = USENIX Association
first = Steven | last = Alexander | volume = 29 | number = 3 | year = 2004 | month = June] These larger salt values make precomputation attacks for almost any length of password impossible against these systems for the foreseeable future.

Another technique that helps to prevent precomputation attacks is key strengthening (also called key stretching). When stretching is used, the salt, password, and a number of intermediate hash values are run through the underlying hash function multiple times to increase the computation time required to hash each password [cite book
last = Ferguson
first = Neils
authorlink =
coauthors = Bruce Schneier
title = Practical Cryptography
publisher = John Wiley & Sons
date = 2003
location = Indianapolis
isbn = 0-471-22357-3 ] . For instance, MD5-Crypt uses a 1000 iteration loop that repeatedly feeds the salt, password, and current intermediate hash value back into the underlying MD5 hash function. The user's password hash is the concatenation of the salt value (which is not secret) and the final hash. The extra time is not noticeable to a user because he only has to wait a fraction of a second each time he logs in. On the other hand, stretching greatly reduces the effectiveness of a brute-force or precomputation attacks because it reduces the number of computations an attacker can perform in a given time frame. This principle is applied in MD5-Crypt and in bcrypt.cite journal
url = http://www.usenix.org/events/usenix99/provos/provos.pdf
title = A Future-Adaptable Password Scheme | publisher = USENIX Association | location = Monterey, CA, USA
first = Niels | last = Provos | coauthors = David Mazières | date = 1999-06-06
journal = Proceedings of the FREENIX Track: 1999 USENIX Annual Technical Conference]

Also, rainbow tables and other precomputation attacks do not work against passwords that contain symbols outside the range presupposed, or that are longer than those precomputed, by the attacker. Because of the sizable investment in computing processing, Rainbow tables beyond eight places in length are not yet common. So, choosing a password that is longer than eight characters or that contains non-alphanumeric symbols may force an attacker to resort to brute-force methods.

Certain intensive efforts focused on LM hash, an older hash algorithm used by Microsoft, exist in the public domain.

Common uses

Nearly all distributions and variations of Unix, Linux, and BSD use hashes with salts, though many applications use just a hash (typically MD5) with no salt. The Windows NT/2000 family uses the LAN Manager and NT LAN Manager hashing method and is also unsalted, which makes it one of the more popularly generated tables.

History

Rainbow tables are a refinement of an earlier, simpler, and less efficient algorithm that used the inversion of hashes by looking up precomputed hash chains.

Each table depends on the hash function and the "reduce function" used. The "reduce function" is a surjective ("onto") function which maps a hash to a password using the desired character set and password length. Therefore, a "reduce function" for lowercase alphanumeric passwords of 8 characters length is different from a "reduce function" for case-sensitive alphanumeric passwords of 5–16 characters length.

A chain is a sequence of passwords. A starting password is chosen, and the following is done to get the next one in the chain::"reduce"("hash"(a password)) → next passwordAfter a chain containing a suitable number of passwords is created, the final password in the chain is hashed, and the final hash and the starting password are stored together in the rainbow table.

To reverse a hash, look for it in the table. If it isn't found, the following is done to get another hash to try::"hash"("reduce"(a hash)) → next hashThis is repeated until a hash is finally found in the table.

When a match is found, the original password that started the chain that ended with that hash can then be used to generate all the other passwords, and hence hashes, in the chain. Each of the hashes thus generated will be checked against the original target hash, thus hopefully revealing the correct password.

The end result is a table that contains statistically high chance of revealing a password within a short period of time, generally less than a minute. The success probability of the table depends on the parameters used to generate it. These include the character set used, password length, chain length, and table count.

Success probability is defined as the probability that the plaintext can be found for a given ciphertext. In the case of passwords, the password is the plaintext, and the hash of the password is the ciphertext, so the success probability is the probability that the original password can be recovered from the password hash.

See also

* Pollard's lambda algorithm

Notes

References

* Citation
url = http://lasecwww.epfl.ch/~oechslin/publications/crypto03.pdf
title = Making a Faster Cryptanalytical Time-Memory Trade-Off
first = Philippe | last = Oechslin | journal = Advances in Cryptology: Proceedings of CRYPTO 2003, 23rd Annual International Cryptology Conference
location = Santa Barbara, CA, USA | date = 2003-08-17 | isbn = 3-540-40674-3 | publisher = Springer | series = Lecture Notes in Computer Science
* cite journal
url = https://www.isc2.org/cgi-bin/content.cgi?page=738
title = Password Cracking: Rainbow Tables Explained
first = Philippe| last = Oechslin | journal = (ISC)2 Newsletter | month = Mar-Apr | year = 2005

External links

* [http://www.antsight.com/zsl/rainbowcrack/ Project RainbowCrack] A rainbow table generator
* [http://lasecwww.epfl.ch/~oechslin/projects/ophcrack Ophcrack page by Philippe Oechslin] The original rainbow table research with online demo
* [http://kestas.kuliukas.com/RainbowTables/ How Rainbow Tables work]
* [http://www.freerainbowtables.com/faq/ Rainbow Tables FAQ (Section 4)] In-depth explanation about Rainbow Tables and how they work