Password cracking has a brute economics problem: hashing billions of candidates takes serious compute, and a naive attacker pays that cost again for every stolen database. Around 2003, cryptographer Philippe Oechslin popularized a devastating shortcut - Do the computation once, compress the results cleverly, and crack any password hash of that type forever after with a fast lookup. The technique, called rainbow tables, turned cracking Windows passwords from an overnight job into a coffee-break trick and forced an industry-wide reckoning in how passwords get stored. Then a countermeasure that fits in one sentence killed it almost completely. The story is worth knowing not for nostalgia, but because it's the cleanest lesson in security economics you'll ever get - And because unsalted hashes still surface in breaches today.
The problem rainbow tables solve
When a site stores passwords properly, it doesn't keep them - It keeps hashes, the output of a one-way function. Steal the database and you hold 5f4dcc3b5aa765d61d8327deb882cf99 rather than password. Hashes can't be run backward; the only way through is forward: guess a candidate, hash it, compare. (You can watch the forward direction yourself with an MD5 generator - Instant one way, no way back.) The basics are covered in password hashing: MD5 vs SHA-256 vs bcrypt.
An attacker facing a stolen table of hashes has two classical options:
- Compute on demand. Hash candidates until one matches. Costs heavy compute per attack, but almost no storage.
- Precompute everything. Build a giant lookup table of every possible password and its hash, once. Afterward, any hash cracks in milliseconds - But storing every 8-character password with its hash would demand exabytes. Impossible.
Rainbow tables are the compromise: a time-memory trade-off that stores perhaps one ten-thousandth of the precomputed data in exchange for a modest amount of computation per lookup. Suddenly the impossible table fits on a hard drive.
How the trick works
The mechanism is chains. Take a starting password, hash it, then apply a "reduction function" that maps the hash back into some password-shaped string (not the original - Hashes don't reverse; the reduction just deterministically produces another candidate). Hash that, reduce again, and repeat thousands of times. Then store only the first and last links of the chain and throw the rest away.
Do this for millions of chains and you've implicitly covered trillions of password-hash pairs while storing only millions of endpoints. To crack a target hash, you run it through the same reduce-hash cycle until you hit a stored endpoint, then regenerate that one chain from its start to find which password produced your hash. You pay a burst of computation per lookup - Vastly less than searching the whole space, at a millionth of full-table storage.
(The "rainbow" refines this by using a different reduction function at each chain position - Pictured as colored bands - Which elegantly suppresses the chain collisions that plagued earlier designs.)
The payoff in practice was brutal. Freely downloadable tables covered every alphanumeric Windows LM/NTLM password or unsalted MD5 up to certain lengths; tools looked up hashes in seconds. Crucially, the tables were shareable - One group's month of precomputation became everyone's instant crack, downloadable or queryable on websites.
One sentence that killed it: the salt
A salt is a random value, unique per user, stored alongside the hash and mixed into it: instead of hash(password), the site stores hash(salt + password) plus the salt itself.
That's the whole countermeasure, and it's fatal to precomputation. A rainbow table is built against one exact hash function. Salting effectively gives every user their own hash function - hash("x7Kp2..." + password) - That didn't exist until their account was created. A table built in advance can't include it; a table built after the theft must be built per-user, at which point it's slower than just guessing directly. Precomputation's one asset - Reusability - Is destroyed.
A salt doesn't make a hash harder to crack once - It makes every precomputed shortcut worthless and every attack strictly per-user. One random value per row, and a decade of shared rainbow tables became landfill.
Salts aren't secrets; they sit in the database beside the hash, and that's fine - Their job is uniqueness, not secrecy. The related-but-different pepper (a secret value kept outside the database) and the full seasoning story are covered in salts and peppers.
Rainbow tables vs modern attacks
Salting became standard practice everywhere competent (bcrypt, scrypt, and Argon2 build it in automatically), and meanwhile GPUs got so fast that recomputing candidates on demand stopped being painful. Modern cracking rigs run wordlist-plus-rules attacks - The approach detailed in dictionary attacks - At billions of guesses per second against fast hashes, salt or no salt. The precomputation shortcut simply stopped being the bottleneck-breaker it once was.
| Rainbow table | GPU dictionary/brute force | |
|---|---|---|
| Precomputation | Massive, one-time, shareable | None needed |
| Storage | Gigabytes to terabytes | Wordlists: gigabytes |
| Defeated by salting | Completely | Not at all (just per-user cost) |
| Defeated by slow hashes | Yes (table build becomes infeasible) | Rate cut from billions/sec to thousands/sec |
| Works on modern systems | Rarely - Legacy unsalted hashes only | Yes - The current standard threat |
| Historical peak | ~2003–2012 | 2012–present |
So are rainbow tables dead? Mostly - But "mostly" does real work in that sentence. Breaches still occasionally disgorge unsalted MD5 or SHA-1 tables from legacy systems, ancient forum software, and homegrown code, and for those, precomputed lookup services crack enormous fractions instantly. Windows NTLM hashes - Still unsalted for backward compatibility - Remain a niche where tables and related precomputation stay relevant to penetration testers. The technique is retired from the front lines, not extinct.
What this means for your passwords
You can't choose how a website stores your password - And breach history says plenty still do it badly. The rational response is to be safe under the worst storage you might encounter:
- Assume fast, and occasionally unsalted, hashing. Against that, only entropy saves you. A random 16+ character password from a password generator sits beyond reach of tables, wordlists, and brute force alike - Roughly 105 bits, unattackable even at MD5 speeds.
- Uniqueness caps the blast radius. When some legacy site's unsalted table falls, a unique password means the damage ends there instead of cascading through reuse.
- Watch for the tell. A site that emails you your actual password, or "recovers" it rather than resetting it, is storing it reversibly or worse - Treat that account as pre-breached and never let its password near anything important.
- See the whole battlefield once. Rainbow tables are one exhibit in a larger museum; how hackers crack passwords tours brute force, dictionaries, stuffing, and where each defense fits.
If you build software: never hand-roll storage. Use Argon2 or bcrypt - Salted by design, deliberately slow, and configured so even a total database theft yields hashes that cost attackers dollars per guess rather than nanoseconds. A general-purpose function like the one behind any SHA-256 hash tool is superb for integrity checks and exactly wrong, alone, for passwords: its speed is the vulnerability.
FAQ
Can a rainbow table crack any password?
No - Only passwords within the space the table was built for (say, alphanumerics up to 9 characters, for one specific unsalted hash function). Anything longer, using excluded characters, or salted falls outside the table entirely. That boundary is why long random passwords were safe even at the technique's peak, and why a single salt defeats the whole approach.
Why can't attackers just build rainbow tables that include salts?
Arithmetic. A table covering one hash function is already a massive build; covering every possible salt multiplies that build by the number of salt values - With a 128-bit salt, 2¹²⁸ variants. Building per-user tables after stealing the salts is possible but pointless: a single-target table is slower than simply running a direct dictionary attack against that user.
Are rainbow tables illegal?
Generating or possessing them isn't inherently illegal - They're published research artifacts, and penetration testers use them under authorization. Using them to crack credentials you have no right to access is illegal in most jurisdictions under computer-misuse laws, the same as any unauthorized cracking. The tool is neutral; the target authorization is what matters legally.
How do I know if a site salts my password?
You mostly can't verify it from outside - Storage is invisible to users. Weak proxies: sites that can email you your existing password have already failed; sites publishing security pages that mention bcrypt, scrypt, or Argon2 are doing it right (those algorithms salt automatically). Since you can't audit, defend unilaterally: high-entropy unique passwords are safe under every storage regime.
Do rainbow tables work against bcrypt or Argon2?
No, twice over. Both embed a unique random salt per password, so precomputation can't target them at all. And both are deliberately expensive - Thousands of times slower than MD5 - So even building a hypothetical single-salt table would take geologic time. That combination of salting plus cost is precisely why modern password-hashing standards settled on these designs.