Rainbow Tables

A lookup table offering a time-memory tradeoff used in recovering the plaintext password from a hash function. Salt is often employed with hashed passwords to avoid the use of a Rainbow Table attack.

Rainbow tables are constructed by building chains of possible plaintext passwords. Each chain is developed by starting with a randomly selected "guess" of the plaintext password and then successively applying the one-way hash followed by a reduction function. The reduction function takes the results of the hash-function and turns it into another plaintext password guess. The intermediate password guesses are then discarded and the first and last are stored in the rainbow table. This table takes time and memory to build, but must only be built once, after which it can then very quickly recover unknown passwords.

Recovery of plaintext passwords is then done by taking the hash password, applying the reduction function, and looking-up the result in the rainbow table. If no match is found, then the hash and reduction functions are applied again and that result is then looked-up. This is repeated until a match is found. Once a match is found, the chain that resulted in the match is reconstructed to find the previously discarded intermediate value, which is then a plaintext password for the given hash.

How Rainbow Tables work