Understanding the Rainbow Table Threat

Rainbow tables revolutionized password cracking by trading computation time for storage space. Instead of computing hashes during an attack, rainbow tables contain precomputed hash chains that map hash values back to their plaintext passwords. Before salting became standard, attackers could crack millions of passwords in seconds by simply looking up hash values in these massive tables. The name "rainbow table" comes from the color-coding used in visualization of the reduction functions used in the chain generation.

The effectiveness of rainbow tables stems from password predictability and reuse. Common passwords like "password123" always produce the same hash value when using deterministic algorithms. Once someone computes this hash, they can store it and instantly crack any occurrence. Rainbow tables for MD5 and SHA-1 covering common passwords and patterns are readily available, some exceeding several terabytes but providing near-instantaneous lookup for billions of potential passwords.

import hashlib
import os
import time

def demonstrate_rainbow_table_vulnerability():
    """Show how unsalted hashes enable rainbow table attacks"""
    
    # Simulate a rainbow table (in practice, these are massive)
    rainbow_table = {}
    
    # Pre-compute common passwords
    common_passwords = [
        'password', '123456', 'password123', 'admin', 'letmein',
        'welcome', 'monkey', '1234567890', 'qwerty', 'abc123'
    ]
    
    print("Building mini rainbow table...")
    for pwd in common_passwords:
        md5_hash = hashlib.md5(pwd.encode()).hexdigest()
        sha1_hash = hashlib.sha1(pwd.encode()).hexdigest()
        rainbow_table[md5_hash] = pwd
        rainbow_table[sha1_hash] = pwd
    
    # Simulate stolen unsalted hashes
    stolen_hashes = [
        ('user1', hashlib.md5('password'.encode()).hexdigest(), 'MD5'),
        ('user2', hashlib.sha1('123456'.encode()).hexdigest(), 'SHA1'),
        ('user3', hashlib.md5('admin'.encode()).hexdigest(), 'MD5'),
        ('user4', hashlib.sha1('monkey'.encode()).hexdigest(), 'SHA1'),
    ]
    
    print("\nCracking unsalted hashes using rainbow table:")
    print("-" * 50)
    
    start_time = time.time()
    for username, hash_value, hash_type in stolen_hashes:
        if hash_value in rainbow_table:
            print(f"{username}: {rainbow_table[hash_value]} (found instantly!)")
        else:
            print(f"{username}: Not in rainbow table")
    
    elapsed = time.time() - start_time
    print(f"\nTime to 'crack' {len(stolen_hashes)} passwords: {elapsed:.5f} seconds")
    
    # Demonstrate salt effect
    print("\n\nWith proper salting:")
    print("-" * 50)
    
    salted_users = []
    for i, (username, _, _) in enumerate(stolen_hashes):
        salt = os.urandom(16)
        password = common_passwords[i]
        salted_hash = hashlib.sha256(salt + password.encode()).hexdigest()
        salted_users.append((username, salt, salted_hash))
        print(f"{username}: Salt={salt.hex()[:16]}... Hash={salted_hash[:16]}...")
    
    print("\nEach user has unique hash despite same passwords!")
    print("Rainbow tables are now useless - would need one per salt!")

demonstrate_rainbow_table_vulnerability()

The mathematical elegance of rainbow tables lies in their chain structure. Rather than storing every password-hash pair, they store chains of values created through alternating hashing and reduction functions. This approach reduces storage requirements while maintaining high coverage. However, this optimization becomes worthless when every password has a unique salt, as it would require generating separate rainbow tables for each possible salt value—a computationally infeasible task.