What is a reduction function, and why is it the secret ingredient that makes rainbow tables work?
A reduction function maps a hash back to a plaintext-shaped string — not the original password, but some valid candidate in the target keyspace. It's what lets a chain alternate hash → plaintext → hash → plaintext.
Why we need it:
Hash functions are one-way — you can't "un-hash." So how does a rainbow chain go password → hash → password → hash → ...?
Answer: between hashes, you apply a reduction function that converts the hash bits into something that looks like a password. It's not a true inverse — it's just any deterministic function that maps a hash → a string in your password keyspace.
Toy example:
For 4-char lowercase passwords:
Reduce(hash) = take the hash mod 26⁴, interpret as 4 lowercase letters
So hash("apple") = 0x1f3d8a4e... → reduce → "kqzm" (some other 4-char word). Then hash("kqzm") = 0x9b2c... → reduce → "vnxp". And so on.
Why this builds a useful index:
Each chain covers ~thousands of (password, hash) pairs while storing only the start and end. To crack a hash:
- Apply reduce → get candidate plaintext
- Hash it, apply reduce, hash, reduce... up to chain length
- If you hit a known endpoint → recompute that chain from its start
- The plaintext just before your target hash IS the original password
Why "rainbow":
Original Hellman tables used ONE reduction function — collisions caused chains to merge and waste space. Philippe Oechslin's 2003 innovation: use a different reduction function at each step of the chain. Visualized as colored layers → "rainbow" tables. This dramatically reduces chain merges and improves coverage.
Why salting kills this:
Reduction functions are designed for a specific keyspace. A salt extends the input by random bytes, so the "plaintext" the reduction function produces no longer matches what was actually hashed. Every salt → entirely new table needed.
Tip: This is why rainbow tables are tied to a specific (algorithm, charset, length) combo — the reduction function bakes those assumptions in. An NTLM-lowercase-7-char table is useless for SHA-256 or for 8-char passwords.
Deep dive: https://en.wikipedia.org/wiki/Rainbow_table#Precomputed_hash_chains and Ryan Sheasby's series for the visual intuition.
Go deeper:
Sheasby: Part 2 — Probability, Efficiency, and Chain Collisions — why a single reduction function causes chains to merge, and how Oechslin's per-step reduction (the actual "rainbow") fixes it.- Rainbow table — reduction functions (Wikipedia) — formal definition of R mapping hashes back into the keyspace and the R₁…Rₖ sequence.