Glossary

Rainbow Table

A precomputed lookup table mapping hash digests back to their original plaintext inputs. Rainbow tables allow attackers to crack unsalted password hashes quickly by looking up a hash rather than brute-forcing it. Adding a unique random salt to each password before hashing defeats rainbow table attacks.

A rainbow table is a precomputed data structure that maps hash digests to their original plaintext inputs, enabling an attacker to reverse a password hash in constant time without brute-force computation. The "rainbow" structure uses reduction functions to chain plaintexts and hashes, making the table more space-efficient than a simple hash-to-plaintext map. Rainbow tables render unsalted password databases trivially crackable.

How Rainbow Tables Work

A naive lookup table stores every (plaintext → hash) pair. Rainbow tables are more efficient — they store chains where each link alternates between a hash function and a reduction function:

password → hash → reduction → word → hash → reduction → ...

To crack a hash:

  1. Apply reduction and hash functions repeatedly to find a chain endpoint
  2. Look up the endpoint in the table
  3. Replay the chain from the start to find the original plaintext

This recovers passwords in milliseconds instead of days of brute-force computation.

Why Salting Defeats Rainbow Tables

An unsalted rainbow table covers:

hash("password") → "password"
hash("123456")   → "123456"

With unique per-user salts, the attacker would need a separate table for every possible salt:

hash("xJ9k2mPq" + "password") → can't precompute for arbitrary salts
hash("nZ4r8vKs" + "password") → different result, separate table needed

A 128-bit random salt requires 2^128 different rainbow tables — computationally impossible to precompute.

Rainbow Tables Are Still Relevant

Even with modern bcrypt/Argon2, rainbow tables appear in:

  • Unsalted legacy systems: many old systems stored MD5 or SHA-1 of passwords without salts — rainbow tables crack these instantly
  • MD5/SHA-1 cracking services: websites like CrackStation precomputed tables for common hash functions
  • Password reuse: cracked hashes from old breaches reveal passwords reused on new systems

Protection

  1. Use bcrypt, Argon2, or scrypt — all include automatic per-user salts
  2. Never implement your own salt + hash scheme
  3. If using raw hashing (non-passwords), generate a 128-bit random salt per entry
  4. For passwords that must be hashed with raw functions (legacy), use PBKDF2 with at least 600,000 iterations and a unique salt

Notable Leaked Databases

Major breaches where rainbow tables played a role in cracking passwords:

  • LinkedIn 2012: unsalted SHA-1, 117M hashes cracked rapidly
  • RockYou 2009: plaintext passwords stored (no hashing at all)
  • Adobe 2013: 3DES encryption (not hashing), poor key management

These breaches drove the adoption of bcrypt in the industry.