Rainbow Table

Rainbow Table is a precomputed lookup table for reversing cryptographic hash functions, used for cracking password hashes. It represents a time-memory trade-off: large storage enables fast lookups instead of computing hashes on demand.

How It Works

// Precomputation phase (done once):
for password in wordlist:
    hash = MD5(password)
    table[hash] = password

// Attack phase (instant lookup):
stolen_hash = "5f4dcc3b5aa765d61d8327deb882cf99"
password = table[stolen_hash]  // Returns "password"

Rainbow Chain Optimization

True rainbow tables use chains with reduction functions to compress storage:

// Chain: password → hash → reduce → password2 → hash2 → ...
// Store only: (first_password, final_hash)
// Lookup: compute chains until match found

Why It Works

Many users choose common passwords
Unsalted hashes are deterministic
Same password = same hash everywhere

Limitations

Only works for unsalted hashes
Limited to included password patterns
Storage intensive for long passwords
Slow algorithms (bcrypt) make tables impractical

Defense: Salting

// Without salt:
hash("password") → same hash for all users

// With salt (unique per user):
hash("password" + "randomsalt123") → unique hash
hash("password" + "differentsalt456") → different hash

// Rainbow table would need entry for every salt combination
// Effectively defeats precomputation

Prevention

Always use unique salts per password
Use slow hash functions (bcrypt, scrypt, Argon2)
Never use MD5, SHA-1, or unsalted SHA-256 for passwords