Rainbow Tables: Precomputed Password Cracking Explained
Learn how rainbow tables work, their trade-offs between time and memory, when they are effective, and why salting renders them useless.
The Tables That Broke Windows Passwords in Seconds
In the early 2000s, Windows LAN Manager hashes were the standard for storing Windows passwords — and they were catastrophically weak. LM hashes split passwords into two 7-character halves, used no salt, and employed a flawed hash algorithm. Security researchers Philippe Oechslin introduced rainbow tables in 2003, and suddenly any Windows password under 14 characters could be cracked in seconds. A single 2.6 GB table could crack 99.9% of all Windows XP passwords.
Rainbow tables are precomputed tables used for reversing cryptographic hash functions, primarily for cracking password hashes. They represent a time-memory trade-off: they use more memory than simple lookup tables but significantly less time than brute force attacks.
Prerequisites
Before studying rainbow tables, you should understand:
The Time-Memory Trade-Off
Simple Lookup Table
Store hash for every possible password
Storage: 26^8 * 32 bytes = ~20 TB (for 8-char lowercase)
Time: O(1)
Brute Force (No Table)
No precomputation
Storage: 0
Time: 26^8 = 208 billion hash computations
Rainbow Table
Store chains of hashes (compressed representation)
Storage: Significantly less than full table
Time: More than O(1) but much less than brute force
How Rainbow Tables Work
Chain Creation
Rainbow tables use reduction functions (R) and hash functions (H) to create chains:
# Simplified rainbow chain concept
# P = Plaintext password
# H = Hash function
# R = Reduction function (maps hash back to possible password)
Chain: P1 -> H(P1) -> R(H(P1)) -> H(R(H(P1))) -> ...
# Store only: first plaintext, last hash
# Start: password
# Reduce: Create next possible password from hash
# Hash: Hash the new password
# Repeat N times
# Store chain endpoints
Chain Lookup Process
def rainbow_lookup(target_hash, rainbow_table):
# Apply R and H alternately to target hash
# For each chain, check if reduced value matches an endpoint
# If match: regenerate chain from start point
current = target_hash
for i in range(chain_length):
# Reduce hash to possible password
possible = reduce(current)
# Check if possible matches any chain endpoint
if possible in rainbow_table.endpoints:
start = rainbow_table.starts[possible]
# Regenerate chain from start
result = regenerate_chain(start, target_hash)
if result:
return result
# Hash the possible password for next iteration
current = hash(possible)
return None
Why "Rainbow"?
The name comes from using different reduction functions (one per column in the table), creating a "rainbow" of colors when visualized. This approach eliminates chain merges and collisions that would occur with a single reduction function.
Rainbow Table Generators
Using rcracki_mt
# Generate rainbow tables
rtgen hash md5 numeric 1 7 0 21000 33554432 0
# Parameters:
# hash: Hash algorithm
# md5: Hash type
# numeric: Character set
# 1 7: Min/Max password length
# 0: Starting index
# 21000: Chain length
# 33554432: Number of chains
# Sort tables after generation
rtsort *.rt
# Crack hashes
rcracki_mt *.rt -h 482c811da5d5b4bc6d497ffa98491e38
Using RainbowCrack
# Generate tables
rtgen md5 loweralpha-numeric 1 8 0 3800 33554432 0
# Sort
rtsort ./md5_loweralpha-numeric#1-8_0_3800x33554432_0.rt
# Crack
rcrack . *.rt -l hashes.txt
Precomputed Rainbow Tables
Publicly Available Tables
# RainbowCrack Project
# Free rainbow tables for:
# - LM (Windows LAN Manager)
# - NTLM
# - MD5
# - SHA1
# Ophcrack Tables
# Specialized for Windows LM hashes
# XP Free Fast: 99.9% success for XP passwords
# Vista Free: 99.9% success for alphanumeric
Table Sizes and Coverage
| Hash Type | Keyspace | Table Size | Success Rate |
|-----------|----------|------------|--------------|
| LM (1-7 chars) | 69^7 | 2.6 GB | 99.9% |
| NTLM (1-7 alphanum) | 36^7 | 36 GB | 99.9% |
| MD5 (1-7 loweralpha) | 26^7 | 28 GB | 99% |
| MD5 (1-8 alphanum) | 62^8 | Very large | Limited |
Why Salting Defeats Rainbow Tables
The Salt Problem
# Without salt
hash("password123") = same hash every time
# One rainbow table works for ALL users
# With salt
hash("password123" + "random_salt_a") = hash_a
hash("password123" + "random_salt_b") = hash_b
# Each salt requires a NEW rainbow table
Salt Space Explosion
Password: "password"
Without salt: 1 hash value
With 32-bit salt: 2^32 = 4 billion hash values
With 128-bit salt: 2^128 hash values
To crack salted passwords with rainbow tables:
- Need separate table for every possible salt value
- 2^128 tables = computationally infeasible
Modern Relevance
Are Rainbow Tables Still Useful?
Rainbow tables remain effective for:
Where They Fail
Real-World Examples
Ophcrack and Windows XP: Ophcrack's rainbow tables could crack 99.9% of Windows XP passwords in seconds, making LM hashes a critical vulnerability.
WPA2 Rainbow Tables: Precomputed tables for common WPA2 passphrases exist (e.g., RainbowCrack's WPA tables), though each table covers limited keyspace.
Common Mistakes
Using rainbow tables for salted hashes: Rainbow tables waste time on salted hashes. Use dictionary attacks instead.
Wrong table selection: Different character sets and lengths require different tables. Match table to expected password format.
Assuming 100% success: Rainbow tables have a success rate based on coverage. Not all passwords will be found.
Best Practices
Related Tools
Related Articles
Summary
Rainbow tables precompute hash chains to enable fast password cracking with a time-memory trade-off. They are effective for unsalted hashes like LM and NTLM but are completely defeated by modern salting practices. For most modern systems, GPU-based dictionary attacks (Hashcat) are more practical.