Rainbow table
A rainbow table is a precomputed data structure for inverting a
hash function — that is, for finding an input that
produces a given hash digest. It is most associated with recovering plaintext
passwords from a stolen database of password hashes. Where brute-forcing a
single hash means re-running the hash function across a huge key space, and a
plain lookup table means storing every (password, hash) pair outright, a
rainbow table sits between the two, trading storage for recomputation through
hash chains.
Hash chains and reduction functions
Storing a (password, hash) pair for every candidate in a large dictionary is
prohibitively expensive in space. A rainbow table instead stores only the
start and end of each chain. Beginning from a plaintext word, the chain
alternates two steps: hashing the current plaintext with the target function,
then applying a reduction function R that maps the resulting hash back into
a candidate plaintext. The reduction function is not an inverse of the hash —
hashing is one-way — but a deterministic mapping into the password space, eg.
interpreting the digest as an integer and taking it modulo the dictionary
size to index a word.
After k rounds of hash-then-reduce, only the first and last plaintext of the
chain are kept. To invert a target hash, the attacker walks the hash forward
through repeated R-then-hash steps, comparing each intermediate value
against the stored chain ends. On a match, the chain is reconstructed from its
stored start until the matching plaintext is recovered.
Origins
The technique is a time-memory trade-off introduced by Martin Hellman in
1980. Hellman’s original scheme used one reduction function for every chain,
which caused chains to merge and produced many false matches. Philippe
Oechslin’s 2003 refinement — the "rainbow" variant — uses a different
reduction function at each position in the chain, R_1, R_2, …, R_k.
This drastically reduces chain collisions and false alarms, and is the form
the term refers to today.
Defenses
Rainbow tables are precomputed for one specific hash function. Two controls render them ineffective for password storage.
A per-record salt changes the effective hash function for every password, so a single precomputed table covers only one salt value. Salting makes precomputation no cheaper than brute-forcing each record individually, which is the whole point.
Key derivation functions such as bcrypt, scrypt, Argon2, and PBKDF2 raise the cost of each guess — deliberately slow and, in the case of the newer designs, memory-hard — so that building or walking a precomputed table becomes infeasible. Combined with unique salts, these make rainbow tables obsolete for any competently stored credential.
They remain relevant against legacy, unsalted, fast hashes — raw MD5 or Windows NTLM hashes — where a single leaked hash file can be inverted with a widely available precomputed table in seconds. See authentication for how these controls fit into a broader credential-protection strategy.
See also
References
- Hellman, M (1980). A cryptanalytic time-memory trade-off. IEEE Transactions on Information Theory, 26(4).
- Oechslin, P (2003). Making a faster cryptalytic time-memory trade-off. Advances in Cryptology — CRYPTO 2003.