Understanding Rainbow Tables

Problem

You want to understand how rainbow tables enable fast password cracking and how to defend against them.

Prerequisites

• Understanding of hash functions
• Knowledge of password storage

Steps

1. 1. Understand the precomputation attack

   A rainbow table is a precomputed table of hash-to-password mappings. An attacker computes hashes for many possible passwords once, storing them in a time-memory trade-off table. To crack a stolen hash, they look it up in the table instead of brute-forcing.

   Input

   stolen hash: 5f4dcc3b...

   Output

   lookup in table → 'password'

2. 2. Understand the role of chains

   Rainbow tables use hash chains to compress the storage. Each chain starts from a password, alternates hashing and reduction functions, and stores only the start and end. This reduces storage at the cost of some recomputation during lookup, trading time for space.

   Input

   chain: pw1 → hash → reduce → pw2 → ...

   Output

   store only start + end

3. 3. Defend with salting

   A per-password random salt makes precomputation useless: the attacker would need a separate rainbow table for each salt, which requires more storage than brute-forcing. This is why all modern password hashing (bcrypt, PBKDF2, scrypt) uses salts. Always use a unique salt per password.

   Input

   hash = H(password + salt)

   Output

   rainbow table defeated

Expected result

Understanding of how rainbow tables work and why salting is essential for password security.

Common errors

Storing unsalted password hashes

Always use a per-password random salt. bcrypt, PBKDF2, and scrypt handle this automatically.

Using a shared salt for all passwords

A shared salt still allows a single rainbow table to crack all passwords. Each password needs its own random salt.

Troubleshooting

• If you discover unsalted hashes in a legacy system, migrate to bcrypt or scrypt immediately.
• Rainbow tables are effective against MD5 and SHA-1; they are less practical against slow KDFs like bcrypt.

Security limits

• Rainbow tables are a real threat for unsalted hashes. Salting is the standard defense.
• This is an educational explanation; no cracking is performed.