Rainbow table

Rainbow tables are a practical example of a space–time tradeoff: they use less computer processing time and more storage than a brute-force attack which calculates a hash on every attempt, but more processing time and less storage than a simple table that stores the hash of every possible password.

Rainbow tables were invented by Philippe Oechslin[1] as an application of an earlier, simpler algorithm by Martin Hellman.

The term refers to the way different reduction functions are used to increase the success rate of the attack.

For his presentation at the Crypto 2003 conference, Oechslin added color to the graphic in order to make the rainbow association more clear.

Given a password hash function H and a finite set of passwords P, the goal is to precompute a data structure that, given any output h of the hash function, can either locate an element p in P such that H(p) = h, or determine that there is no such p in P. The simplest way to do this is compute H(p) for all p in P, but then storing the table requires Θ(|P|n) bits of space, where |P| is the size of the set P and n is the size of an output of H, which is prohibitive for large |P|.

In the example chain above, "aaaaaa" would be the starting point and "kiebgt" would be the endpoint, and none of the other passwords (or the hash values) would be stored.

Now, given a hash value h to invert (find the corresponding password for), compute a chain starting with h by applying R, then H, then R, and so on.

Most serious if at any point two chains collide (produce the same value), they will merge and consequently the table will not cover as many passwords despite having paid the same computational cost to generate.

Other difficulties result from the importance of choosing the correct function for R. Picking R to be the identity is little better than a brute force approach.

In effect R shepherds the results of prior hash calculations back to likely plaintexts but this benefit comes with the drawback that R likely won't produce every possible plaintext in the class the attacker wishes to check denying certainty to the attacker that no passwords came from their chosen class.

These chains are not collision-free (they may overlap briefly) but they will not merge, drastically reducing the overall number of collisions.

The theory of this technique was invented by Philippe Oechslin[3] as a fast form of time/memory tradeoff,[1] which he implemented in the Windows password cracker Ophcrack.

A large salt value prevents precomputation attacks, including rainbow tables, by ensuring that each user's password is hashed uniquely.

For older Unix passwords which used a 12-bit salt this would require 4096 tables, a significant increase in cost for the attacker, but not impractical with terabyte hard drives.

[4] These larger salt values make precomputation attacks against these systems infeasible for almost any length of a password.

This forces both the attacker and legitimate users to perform a brute-force search for the secret salt value.

The secret salt size is chosen so that the brute force search is imperceptible to the legitimate user.

However, tables can be generated that take into account common ways in which users attempt to choose more secure passwords, such as adding a number or special character.

Because of the sizable investment in computing processing, rainbow tables beyond fourteen places in length are not yet common.

So, choosing a password that is longer than fourteen characters may force an attacker to resort to brute-force methods.

Rainbow tables have seen reduced usage as of 2020 as salting is more common and GPU-based brute force attacks have become more practical.