Rainbow Table Attacks Explained

A rainbow table is a precomputed lookup table that maps hash values back to their original inputs, specifically designed to crack password hashes. Instead of computing hashes during an attack, the attacker looks up the target hash in the table and instantly retrieves the corresponding password.

How rainbow tables work:

A basic approach would store every possible password-hash pair, but this requires enormous storage. Rainbow tables use a time-memory tradeoff invented by Philippe Oechslin in 2003, building on Martin Hellman's earlier work. The table stores chains of alternating hash and reduction operations. Each chain starts with a plaintext, hashes it, applies a reduction function (mapping the hash back to a candidate password), hashes again, and repeats for thousands of steps. Only the start and end of each chain are stored. To crack a hash, the attacker applies reduction and hash operations to see if the result matches any chain endpoint, then regenerates that chain to find the matching plaintext.

Scale and effectiveness:

Rainbow tables for MD5 covering all alphanumeric passwords up to 8 characters fit in roughly 100GB and can crack any matching hash in seconds. Larger tables covering more character sets and longer passwords exist but require terabytes of storage. Online services like CrackStation maintained rainbow tables covering billions of common passwords for multiple hash algorithms.

Why salt defeats rainbow tables:

A salt is a random value prepended or appended to the password before hashing: hash(salt + password). Because the salt is different for each user, an attacker would need a separate rainbow table for every possible salt value. With a 128-bit salt, this means 2^128 separate rainbow tables, which is completely infeasible. This is why salting is a fundamental requirement for password hashing. bcrypt, scrypt, and Argon2 all incorporate salts automatically.

Modern defenses:

Salting alone prevents rainbow tables but not brute-force attacks with fast hash functions. The complete defense stack includes: (1) a slow hash function like bcrypt/Argon2, (2) unique random salt per password, (3) sufficient work factor to make each hash computation expensive, and (4) rate limiting on login attempts. Together, these make password cracking computationally and economically impractical.