Rainbow Tables and Time-Memory Tradeoffs
You'll learn how rainbow tables trade storage space for cracking speed, and why salting defeats them.
What Are Rainbow Tables?
Rainbow tables are precomputed lookup tables that store hash chains, allowing attackers to crack password hashes in seconds rather than hours. Instead of trying millions of password candidates during an attack (time-intensive), rainbow tables do the heavy computation once and store the results (memory-intensive). When you encounter a hash, you simply look it up.
Think of it like preparing a massive phone book that maps every possible phone number to a person's name. Finding someone becomes instant lookup instead of calling every number.
How Time-Memory Tradeoff Works
Traditional brute-force attacks consume time by calculating hashes on-demand. Storing every possible hash would consume massive memory (trillions of entries). Rainbow tables find a middle ground using reduction functions that create chains:
plaintext → hash → reduction → plaintext → hash → ...
Only the starting and ending points of each chain are stored. During cracking, you reconstruct chains on-the-fly to find matches, balancing time and storage efficiently.
Why Salting Defeats Rainbow Tables
A salt is random data added to each password before hashing. Even if two users have the password "password123", their hashes differ:
- User1:
hash("abc123" + "password123") - User2:
hash("xyz789" + "password123")
Rainbow tables become useless because you'd need separate precomputed tables for every possible salt value—billions of tables instead of one. This makes precomputation economically impractical.
Modern systems use per-user random salts stored alongside hashes, forcing attackers back to time-intensive methods like dictionary attacks or brute-force with tools like hashcat or john.
Practical Implications
Rainbow tables still threaten unsalted hash databases (like old MD5 or SHA1 password lists). However, properly salted hashes with algorithms like bcrypt or Argon2 render rainbow tables obsolete.
Key Takeaway: Rainbow tables trade computation time for storage space to crack hashes quickly, but salting each password with random data makes precomputed tables impractical and forces attackers to compute hashes individually.