Salt Slows Rainbow Tables

TL;DR

Adding a salt to passwords significantly slows down rainbow table attacks. A longer, random salt makes the attack exponentially more difficult and often impractical. The time required increases with both salt length and password complexity.

What are Rainbow Tables?

Rainbow tables are pre-computed tables of hash values used to crack passwords quickly. They work by calculating hashes for common passwords or password patterns in advance. When a system’s password database is compromised, attackers can look up the hashes and find corresponding plain text passwords.

What is Salting?

Salting involves adding a unique, random string (the ‘salt’) to each password before hashing it. This means even if two users have the same password, their stored hashes will be different because of the salt. This makes pre-computed rainbow tables useless.

How Does Salting Slow Down Attacks?

1. Unique Hashes: Each password gets a unique hash due to the salt. An attacker can’t use a single table for all passwords.
2. Increased Computational Cost: The attacker needs to generate rainbow tables for each individual salt used by the system. This is computationally expensive and time-consuming.
3. Exponential Growth: The size of the rainbow table required grows exponentially with the length of the salt. A longer salt means a much, much larger table.

Step-by-Step Explanation

1. Without Salting: If you store only password hashes, an attacker can create a rainbow table and quickly crack many passwords.

   # Example (simplified) - without salt
   password = "password123"
   hash = hashlib.sha256(password.encode()).hexdigest()
   print(hash) # Stored in database

2. With Salting: You store the hash and the salt for each password.

   import hashlib
   import os
   
   salt = os.urandom(16).hex() # Generate a random 16-byte salt
   password = "password123"
   salted_password = salt + password
   hash = hashlib.sha256(salted_password.encode()).hexdigest()
   print("Salt:", salt)
   print("Hash:", hash) # Store both in database

3. Attack with Salting: The attacker needs to try and match the stored hashes against rainbow tables generated for each unique salt.

   # Attacker's perspective (simplified)
   stored_hash = "..."
   stored_salt = "..."
   
   # For each possible password...
     password_guess = "..."
   guessed_salted_password = stored_salt + password_guess
   guessed_hash = hashlib.sha256(guessed_salted_password.encode()).hexdigest()
     if guessed_hash == stored_hash:
       print("Password found!")

Salt Length and Attack Time

• 8-byte salt: Offers some protection, but can be cracked with sufficient resources.
• 16-byte salt (recommended): Provides a strong level of security against rainbow table attacks.
• 32+ byte salt: Makes the attack practically impossible for most attackers.

The time to crack passwords increases exponentially with salt length. For example, doubling the salt length roughly quadruples the amount of computation required.

Other Considerations

• Key Stretching: Use key stretching algorithms (like bcrypt, scrypt, or Argon2) in addition to salting. These algorithms intentionally slow down hashing, making brute-force attacks more difficult.
• Password Complexity Policies: Encourage users to choose strong, unique passwords.
• Regular Updates: Keep your cyber security software and libraries up to date.