What is a rainbow table, and why is it a clever space-time tradeoff?
A precomputed mapping from hashes back to plaintexts — instead of cracking from scratch, you look up the answer.
* Rainbow lookup: walk to a known endpoint, then recompute the chain. *
Naive approach (full lookup table):
- Compute hash for every possible password → store all (password, hash) pairs
- Lookup is instant but storage explodes — impossibly large for 8+ char alphabets
Rainbow tables — the smart trick:
Instead of storing every (password, hash) pair, rainbow tables store only endpoints of hash chains:
- Start with
password₀→ hash → reduce →password₁→ hash → reduce → ... (chain of e.g. 1,000 steps) - Store only
password₀andpassword₁₀₀₀(start and end) - To crack a hash: apply reduction + hash forward, see if you hit a known endpoint
- If yes, recompute that chain to find the matching password
Result: Storage shrinks ~1000× but cracking takes ~1000× more compute per lookup. Sweet spot for password cracking.
Real-world tables:
- Vista free — 461 MB, NTLM, alphanumeric, lengths 1-7
- Vista probabilistic free — adds common patterns (dictionary + numbers)
- Vista probabilistic 60G — 60 GB version with much higher coverage
Reading an example table:
Hash | Hash incl. Salt | PWD
2965 | 6757 | Haus
0084 | 3626 | Maus
3098 | 3675 | Raus
8616 | 1856 | Saus
Without salt → easy lookup 2965 → Haus. With salt → useless without knowing the salt, AND every password got a different salt so you can't even tell which hashes are duplicates.
The defeat: Salting completely nullifies rainbow tables (see earlier card).
Tip: Read Ryan Sheasby's series for an excellent visual explanation: Part 1: Precomputed Hash Chains.
Go deeper:
Rainbow tables (Precomputed hash chains) — the canonical reference for the chain construction and the space-time tradeoff math.- Sheasby: Part 1 — Precomputed Hash Chains — walks through why "rainbow tables" are usually really plain hash chains, with clear diagrams.