What is a rainbow table and how does it attack stored passwords?
A pre-computed table of password → hash pairs (often hundreds of GB) that lets the attacker reverse a stolen hash to its password almost instantly — turning a hard hash computation into a table lookup.
The basic idea (simplified):
- The attacker pre-computes
H(password)for every "likely" password — common passwords, short alphanumeric strings, dictionary words and variations. - Stored as a giant sorted table mapping hash → password.
- When they steal a DB of hashes, they just look up each hash in the table. If
H(123456)matches, they recover "123456" instantly.
Why "rainbow"? The actual technique (Oechslin 2003) uses chains of hashes with multiple reduction functions (rendered with different colours in diagrams — hence "rainbow"). The chains compress storage dramatically vs a naive lookup table. The pure idea is "pre-computed inversions"; the chain trick makes it tractable.
What rainbow tables defeat:
- ✅ Any unsalted hash storage (MD5, SHA-1, SHA-256 of just
password). - ✅ Any common password up to ~10 characters in length.
What defeats rainbow tables:
- Salt — making the attacker pre-compute a separate table per user is infeasible.
- Slow hashing (Argon2 / bcrypt) — even per-user tables become economically infeasible.
Tip: Free downloadable rainbow tables exist for MD5/SHA-1/NTLM up to ~10 character passwords. Many older Windows password leaks (NTLM unsalted hashes) were cracked entirely via rainbow tables. This is the #1 reason salting is non-negotiable.