[Security Brief] - P16 - Rainbow Table Attacks

In this blog post, we will break down the mechanics of rainbow tables, understand how attackers use them, and discuss the most effective countermeasures.

1. What is a Rainbow Table Attack?

The Basics of Password Hashing

Before diving into rainbow tables, it's essential to understand password hashing. Hashing is a cryptographic process that takes an input (a password) and produces a fixed-length, unique output called a hash. This process is one-way, meaning it should be computationally infeasible to retrieve the original input from the hash.

For example, consider the MD5 hash function applied to the password "password123":

$$H(\text{"password123"}) = \text{482c811da5d5b4bc6d497ffa98491e38}$$Even a small change in the input produces a completely different hash:

$$H(\text{"password124"}) = \text{462c811da5d5b4bc6d497ffa98491e39}$$

This is known as the avalanche effect, a critical property of secure hashing algorithms.

Key properties of hash functions:

• Deterministic: The same input always produces the same output.

• Pre-image resistance: Given $h$, it should be computationally infeasible to find $x$ such that $H(x) = h$.

• Collision resistance: It should be hard to find two different inputs $x_1 \neq x_2$such that $H(x_1) = H(x_2)$.

• Avalanche effect: A small change in $x$ produces a drastically different hash.

However, hash functions are not inherently secure against precomputed attacks like rainbow tables.

While hashing makes it difficult to recover passwords directly, attackers use precomputed tables to reverse hashes efficiently. This is where rainbow tables come into play.

What is a Rainbow Table?

A rainbow table is a large precomputed set of hash-to-password mappings designed to reverse cryptographic hashes efficiently. Instead of trying every possible password individually (as in a brute-force attack), attackers precompute hashes and store them in a structured way, allowing for faster lookups when attacking a hashed password.

Rainbow tables leverage a time-memory trade-off:

• High initial computational cost: Building a rainbow table requires computing hashes for billions of potential passwords.

• Fast lookup times: Once generated, the table allows for rapid hash reversals without redoing the expensive hash computations.

Essentially, a rainbow table acts as a giant cheat sheet that speeds up password cracking at the cost of massive storage requirements.

2. Traditional Hash Cracking vs. Rainbow Tables

Brute Force and Dictionary Attacks

There are multiple ways an attacker can attempt to crack password hashes:

• Brute Force Attack:

  • Try every possible password.

  • Extremely slow for long, complex passwords.

  • Time complexity: $O(\mathrm{N)}<br>$$O(N)$, where $N$ is the number of possible passwords.

• Dictionary Attack:

  • Use a precompiled list of common passwords.

  • Faster than brute force but still requires hashing each guess.

  • Useful when users choose weak passwords.

How Rainbow Tables Work Differently

Instead of computing hashes every time, rainbow tables store precomputed hash chains in a compressed format. This allows attackers to reverse hashes without recomputing them.

Why is this more efficient?

• Brute force requires recomputing $H(x)$ for each guess.

• Rainbow tables allow direct lookups, avoiding unnecessary computations.

• Time complexity is reduced to approximately $O(k)$, where $k$ is the length of a hash chain (much smaller than $N$).

3. How Rainbow Tables are Built

The Concept of Hash Chains

To fully understand rainbow tables, we need to explore hash chains, which are the foundation of how these tables are built. Instead of storing every possible password and its hash separately, which would require enormous amounts of storage, rainbow tables compress this information using chains. This significantly reduces storage requirements while still allowing attackers to reverse hash functions efficiently.

Step 1: Hashing a Password

Let’s assume a user chooses the password "hello123" and a system applies a hash function $H$ to it. The output is a fixed-length hash:

$$H(\text{"hello123"})=\text{"abc456"}$$

This hash cannot be directly reversed, meaning an attacker cannot simply "undo" the function to get back the original password.

Step 2: Applying a Reduction Function

Since hash functions are one-way, attackers use a reduction function $R$ to map a hash back to a possible password.

$$R(H(x)) = x'$$

A reduction function is not the same as reversing a hash! Instead, it transforms the hash into another possible password.

For example, let's define a very basic (and unrealistic) reduction function:

$$R(\text{"abc456"}) = \text{"grape"}$$

This doesn’t mean that "grape" was the original password. It’s just a different password that we can now use to continue the chain.

Step 3: Building a Hash Chain

Now, the process repeats:

1. Hash the new password:

   $$H(\text{"grape"}) = \text{"def789"}$$

2. Apply the reduction function again:

   $$R(\text{"def789"}) = \text{"melon"}$$

3. Repeat this process for multiple steps:

   $$H(\text{"melon"}) = \text{"ghi012"}$$
   $$R(\text{"ghi012"}) = \text{"kiwi"}$$
   

4. Store only the first password and the final hash:

   • Start: "hello123"

   • End hash: "ghi012"

Why Use Hash Chains Instead of Storing Everything?

If we had to store every possible password and its hash, we would need massive amounts of disk space. Instead, hash chains allow us to store just two values for each chain:

• The first password in the chain

• The final hash after multiple iterations

This drastically reduces storage requirements while still allowing an attacker to efficiently reverse a hash by following the chain backward.

Example of a Hash Chain Table

Instead of storing every row in the table, we only store:

• Start password: "hello123"

• End hash: "ghi012"

The full chain can be reconstructed when needed.

Step 4: How Attackers Use These Chains

Let’s say an attacker gets their hands on a hashed password from a data breach:

$$H(\text{?}) = \text{"ghi012"}$$

They search for "ghi012" in the rainbow table and find that it is the end hash of a stored chain. Now, they know the first password in that chain is "hello123".

To recover the original password, they simply replay the chain from the start password until they generate the target hash. The password that produces "ghi012" is the one they are looking for.

4. How Attackers Use Rainbow Tables

Now that we understand how hash chains and rainbow tables are built, let’s explore how an attacker actually uses them to crack password hashes. The goal of the attacker is to find the original plaintext password from a stored hash as quickly as possible.

Step 1: Obtaining a Hash from a Database Breach

The first step for an attacker is getting access to hashed passwords.

This typically happens in data breaches, where hackers steal databases containing user credentials. These databases do not store plaintext passwords but rather hashed versions of them.

Example:
A database might contain:

The attacker now has these hashes, but they still need to convert them back into passwords.

Step 2: Searching for the Hash in the Rainbow Table

Once an attacker has a hashed password, they check whether this hash appears as an end value in their precomputed rainbow table.

Scenario 1: The Hash is Found in the Table

Let’s say the attacker finds 482c811da5d5b4bc6d497ffa98491e38 (Alice’s password hash) as an end hash in their rainbow table.

Since the hash is already stored in the table, the attacker knows that this hash was the final value of a hash chain that started with "hello123".

However, "hello123" might not be the actual password - it's just the starting password for this particular chain. The real password is somewhere inside the chain.

Step 3: Recomputing the Chain to Find the Exact Password

Since the attacker only knows the start password ("hello123") and the end hash, they now need to replay the chain step by step until they find the exact password that produces Alice's hash.

Using our previous example chain:

The attacker sees that step 3 produces Alice's exact hash. That means Alice’s password is "melon456".

Step 4: Using the Retrieved Password

Now that the attacker has successfully recovered Alice’s password ("melon456"), they can:

• Log into Alice’s account on the compromised website.

• Try the same password on other websites (if Alice reuses her passwords).

• Sell the cracked passwords in underground hacker forums.

If Alice has used this password elsewhere (which many people do), the attacker now has access to multiple accounts.

If the attacker does not find the hash in their table, they have two options:

1. Use a larger rainbow table: The attacker may try a different precomputed table with more passwords.

2. Fall back to brute-force attacks: If no precomputed table contains the hash, they may try traditional brute-force guessing.

5. Defenses Against Rainbow Table Attacks

Salting – The Most Effective Defense

A salt $s$ is a random string added to passwords before hashing:

$$H(x+s)=h$$

Salting ensures that even if two users have the same password, their stored hashes are different, making rainbow tables ineffective.

If a salt space has $S$ unique values, an attacker would need $S$ different rainbow tables.  For a 32-bit salt ($S = 2^{32}$), storage increases by a factor of $2^{32}$, making precomputation infeasible.

Using Slow Hash Functions (bcrypt, Argon2, PBKDF2)

Modern hash functions intentionally slow down the hashing process by applying multiple iterations:

$$H'(x) = H(H(...H(x)...))$$

By increasing computation time, these functions make precomputed attacks significantly harder.

If an algorithm takes $t$ milliseconds per hash, then an attacker's lookup time increases:

$$T_{\text{attack}} = O(k \cdot t)$$

Slowing down hash calculations makes brute-force and rainbow table attacks much harder.

Strong Password Policies

Increasing password length exponentially increases the size of a rainbow table:

$$\text{Search space} = C^L$$

For example:

• A 6-character lowercase password space: $26^6 \approx 3.1 \times 10^8$ (manageable for tables).

• A 12-character alphanumeric password space: $(26+26+10)^{12} \approx 3.8 \times 10^{21}$(infeasible).

Conclusion

Rainbow table attacks are an ingenious combination of precomputation, hashing, and storage strategies. They highlight the importance of salting and using modern, slow hashing algorithms when storing passwords. While rainbow tables were once more common for cracking older hash algorithms like LM (used in older Windows systems) or unsalted MD5, best practices in password storage have made them far less effective in modern setups.

Understanding how rainbow tables work helps security professionals design robust defenses. By using salted, slow-hash algorithms and strong password policies, you can significantly reduce or eliminate the threat posed by rainbow table attacks. In a rapidly evolving cybersecurity landscape, keeping informed about these techniques - and their countermeasures - is vital for securing user data.