Rainbow Table

security cryptography

Definition

Rainbow Table

A rainbow table is a precomputed data structure for reversing cryptographic hash functions via a time-memory trade-off.

It stores only the endpoints of long chains of hash–reduce iterations, allowing an attacker to recover a preimage from a hash value in far less time than a brute-force attack and with far less memory than a full lookup table.

Construction

Chain Generation

A chain starts from a random plaintext $p_0$ and iterates:

$$p_{i+1}=R_{i+1}(h(p_i))$$

where $h$ is the hash function and $R_{i+1}$ is a reduction function that maps a hash output back into the plaintext space. A sequence of distinct reduction functions $R_1,R_2,\dots ,R_t$ is used, one per column.

Only the start point $p_0$ and end point $p_t$ are stored.

Lookup

Given a target hash $h^{\ast }$, the attacker applies each tail reduction $R_t,R_{t-1},\dots$ and checks whether the result matches any stored endpoint. On a match, the corresponding chain is regenerated to locate the preimage.

Properties

Time-Memory Trade-off

For a hash space of size $N$, a rainbow table with $m$ chains of length $t$ uses $O(m)$ memory and $O(t)$ time per lookup, satisfying $m\cdot t^2\approx N$.

Collision Resistance

Distinct reduction functions at each step reduce the likelihood of merges — collisions between chains — compared to single-reduction tables (e.g. Hellman tables).

Comparison

Attack	Search Space	Time	Memory
Dictionary	size of dictionary	fast	low
Brute-force	entire key/password space	slow	low
Rainbow table	precomputed chains	very fast (online phase)	high

Defence

Salting

A unique per-password salt changes the hash input for every user, rendering a single rainbow table useless. The attacker must build a separate table for each salt.

Key Stretching

Cascade hashing increases the cost of both table construction and lookup.