Rainbow Tables: When Salt Makes Them Worth It

TL;DR

Rainbow tables become cost-effective when cracking passwords with a specific salt value is cheaper than brute-forcing. This happens when the table size needed to cover a reasonable percentage of possible salts (e.g., 90%) is smaller than the storage required for a full brute-force attack covering all possibilities. For typical password lengths and salt sizes, this often means rainbow tables are useful starting around 16-bit salts or larger.

Understanding the Problem

Rainbow tables precompute hashes to speed up password cracking. However, they’re vulnerable if passwords use a unique ‘salt’ for each user. A salt is random data added to the password before hashing. If salts are different for every password, you need a separate rainbow table entry for each salt.

Calculating Table Size

The key is figuring out when building and storing tables for multiple salts becomes cheaper than just trying all possible passwords (brute-forcing). Here’s how to approach it:

Step 1: Determine Password Space

First, estimate the total number of possible passwords. This depends on password length and character set.

• Password Length: Let’s assume an average password length of 8 characters.
• Character Set: Assume a mixed-case alphanumeric character set (26 lowercase + 26 uppercase + 10 digits = 62 characters).
• Total Password Space: 62⁸ ≈ 218,340,105,584 possible passwords.

Step 2: Determine Salt Space

The salt space is the number of unique salts used. This depends on how long the salt is and what characters it uses.

• Salt Length: Let’s consider a salt length of 16 bits (2 bytes).
• Salt Character Set: Assume hexadecimal characters (0-9, A-F = 16 characters).
• Total Salt Space: 16² = 256 possible salts.

Step 3: Calculate Rainbow Table Size

To cover a reasonable percentage of the salt space, you need to build tables for multiple salts. A coverage of 90% is often used as a starting point.

• Number of Salts to Cover: 256 * 0.9 = 231 salts
• Table Size per Salt: Rainbow table size depends on the reduction function and chain length, but let’s assume each salt requires a table storing approximately 1 million entries (this is an example; actual values vary significantly).
• Total Rainbow Table Size: 231 salts * 1,000,000 entries/salt = 231,000,000 entries.

Step 4: Calculate Brute-Force Storage

Brute-forcing requires storing information for every possible password.

• Storage per Password: Assume you need to store a hash and potentially some metadata (e.g., salt) for each password attempt, requiring 10 bytes per entry.
• Total Brute-Force Storage: 218,340,105,584 passwords * 10 bytes/password = 2,183,401,055,840 bytes ≈ 2.18 TB

Step 5: Compare Storage Requirements

Compare the rainbow table size (231 million entries) to the brute-force storage (2.18 TB). In this example, the rainbow table is significantly smaller.

When Rainbow Tables Become Practical

1. Small Salt Space: If the salt space is small (e.g., 8 or 16 bits), rainbow tables are likely to be cost-effective.
2. Large Password Space: With a large password space, brute-forcing becomes impractical.
3. Computational Cost: The time it takes to generate the rainbow table needs to be less than the time it would take to brute-force a significant portion of the passwords.

Example Code (Python – Illustrative)

This is a simplified example to demonstrate calculating password space, not actual rainbow table generation.

import math

def calculate_password_space(length, charset_size):
  return charset_size ** length

password_length = 8
charset_size = 62 # Mixed-case alphanumeric
password_space = calculate_password_space(password_length, charset_size)
print(f"Password space: {password_space:,}")

salt_length = 16
salt_charset_size = 16 # Hexadecimal
salt_space = calculate_password_space(salt_length, salt_charset_size)
print(f"Salt space: {salt_space:,}")

Important Considerations

• Hash Algorithm: The strength of the hash algorithm affects brute-force difficulty.
• Reduction Function: The quality of the reduction function in rainbow tables impacts their effectiveness.
• Chain Length: Longer chains increase table size but improve coverage.
• Hardware: GPU cracking significantly speeds up both rainbow table generation and brute-forcing.
• Modern Password Storage: Modern systems use strong key derivation functions (e.g., Argon2, bcrypt) with large salts to make rainbow tables impractical. These are designed to be slow and memory-intensive, defeating precomputation attacks.