Rainbow table attacks are one of the most elegant and historically devastating attacks on password databases. Understanding how they work — and why modern password hashing completely defeats them — is fundamental to understanding why password storage practices matter so much.
The problem: cracking unsalted hashes
When websites store password hashes (instead of plaintext passwords), an attacker who steals the database can try to reverse those hashes. The brute-force approach is obvious: hash every possible password and compare.
But brute-force has a fundamental problem: it's too slow for long passwords and it must be redone for every database. Is there a way to do the work once and reuse it for any database? Yes — that's exactly what rainbow tables do.
What is a rainbow table?
A rainbow table is a precomputed lookup table that maps hash values back to their original passwords. Instead of computing hashes on the fly for each guess, an attacker looks up a stolen hash in the table and instantly finds the password.
The concept was proposed by Philippe Oechslin in 2003, building on earlier time-memory tradeoff work by Martin Hellman.
The time-memory tradeoff
Cracking a hash involves a tradeoff:
Brute force
Compute hashes on demand. Uses minimal memory but requires enormous computation time per crack.
Lookup tables
Precompute and store every hash→password mapping. Instant lookup, but requires impractical amounts of storage (petabytes).
Rainbow tables ← the tradeoff
Use chains of alternating hash and reduction functions to compress the lookup table. Manageable size, fast lookup. The sweet spot.
How rainbow chains work
A rainbow table is built from chains. Each chain starts with a password, applies the hash function, then applies a reduction function (which converts a hash back to a valid password-like string — not the original password, just some password), then hashes again, reduces again, and so on, for thousands of steps.
Chain example (simplified):
password → H → 5e884898da28... → R → xkqmvp
xkqmvp → H → 2e9d58d0e5b7... → R → ztanxl
ztanxl → H → ... → R → ...
Only the start (password) and end (last value) of each chain are stored.
To crack a hash, you apply the reduction function and hash repeatedly until you recognize the endpoint in your stored table. Then you regenerate the chain from the stored start point to find the position where your target hash appears — and read off the password that produced it.
The scale of real rainbow tables
Rainbow tables for MD5 and SHA-1 are freely downloadable online. Any password database still using unsalted MD5 or SHA-1 should be considered completely compromised.
Real-world damage: the LinkedIn breach (2012)
In 2012, LinkedIn suffered a breach exposing 6.5 million SHA-1 password hashes (unsalted). Within days of the hashes being posted online, over 90% had been cracked using rainbow tables and GPU-accelerated brute force. A follow-up investigation in 2016 revealed the full breach affected 117 million accounts.
LinkedIn's error: using unsalted SHA-1 (a fast, cryptographic hash) instead of a slow, salted password hashing function like bcrypt.
How salting completely defeats rainbow tables
A salt is a unique random string added to each password before hashing. When a site uses salting:
Without salt:
hash("password") = 5e884898da28047...
With unique salts:
hash("password" + "xK7qm2") = a1b2c3d4e5f6...
hash("password" + "pL9nR3") = f9e8d7c6b5a4...
Same password — completely different hashes
A rainbow table would need to be built separately for every possible salt value. With a 128-bit random salt, there are 2128 possible salts. Building a rainbow table for each one is computationally impossible. Salting reduces the attacker to brute-force, which they must run fresh against each individual hash.
Modern password hashing functions like bcrypt, Argon2, and scrypt include automatic salting as a core feature. You cannot opt out.
Frequently asked questions
Are rainbow tables still a threat today?
Against properly salted password hashes (bcrypt, Argon2), rainbow tables are completely ineffective. They remain a threat only against legacy systems still using unsalted MD5 or SHA-1 for passwords. Unfortunately, such systems still exist. If a site ever emails you your actual password (rather than a reset link), they're probably storing it in plaintext or with weak hashing.
What's the difference between a rainbow table and a hash dictionary?
A hash dictionary is a simple table: password → hash. It requires enormous storage to cover a large password space. A rainbow table uses chains of alternating hash and reduction functions to dramatically compress the same information, trading some lookup time for storage efficiency. Both are defeated by salting.
Can rainbow tables be built for bcrypt?
In theory, yes — but they're completely impractical. bcrypt's adjustable cost factor means each hash takes ~100ms+ to compute. Building a meaningful rainbow table for bcrypt with cost 12 would require astronomical amounts of computation and time. This is exactly why bcrypt's slowness is a feature, not a bug.