Rainbow Tables ≠ Hash Tables

Do you know the difference?

As rainbow and hash tables are often confused, this article attempts to shed some light on their differences and what it means for a table to be a “rainbow table”.

Goal

First of all, it is good to know that the goal of these tables is the same. Both rainbow and hash tables are used as lookup tables for password hashes.

Typically an attacker will precompute many hashes of some hashing algorithm (such as MD4, SHA1, …) and save them in a table. Later when he obtains a password hash, the equivalent plaintext can simply be looked up using the table. This saves a lot of effort for the attacker, as the table only needs to be generated once.

This approach lays in contrast with a brute force attack where the attacker calculates the hash of a plaintext and checks if it matches the hash in the moment itself.

ℹ️ Note that precomputing/generating tables is only useful if no salt is involved. If every plaintext is first mixed with a salt before hashing, a separate table would need to be created for every possible salt (which grows unfeasibly large). This is why salting a password renders rainbow tables useless and why you should always salt your passwords ;).

Differences

So we now know that the goal of a hash table and rainbow table is the same. Where would they differ then, you might ask. The clue is in how the data inside the tables is stored.

For a normal hash table, the data is typically stored in a key-value format such as H:P, where H is the hash and P is the equivalent plaintext. This is a good approach and offers near instant lookup times.

There is only one problem with storing hashes this way: your data quickly begins to grow astronomically large. Taking NetNTLMv1 hashes with a total space of 2⁵⁶ hashes for example. This would amount to 72,057,594,037,927,936 hashes and plaintext, which would take up about 1,048,576TB (that’s right, terrabyte…). So unless you have endless hard drives laying around, this approach quickly becomes infeasible.

This is where rainbow tables enter. Rainbow tables don’t store all hashes and plaintexts. Instead, they are stored inside a chain where only the first and last items of the chain are saved in the table. To make this clear, take the following example:

As can be seen from the visual above, the chain contains alternating plaintexts (P) and hashes (H), which are linked together. To keep the example small, we chose for a length of 4.

ℹ️ Don’t mind the beautifully drawn visuals here, I think it’s clear why I don’t draw for a living.

Inner workings

Note that only the first plaintext and last hash eventually end up in the rainbow table (marked in red) in our example. The other two items were calculated, but did not end up in the table, and thus do not take up any disk space.

The clever part about rainbow tables is that, even though we only saved the items in red, we can still access the items in between (H1 and P2 in this case). All we need to do is perform some calculations. The tradeoff here is that we can save up on disk space, but our lookup time will be longer, given that the calculations will take up CPU cycles. In computer science we typically call this a Space-time tradeoff.

The calculations that will be performed look like this:

To go from a plaintext (typically a password) to a hash, we simply take the plaintext through a hashing algorithm. The algorithm used will depend on which type of rainbow table we want to generate. If we wanted to generate a table for md5, we would simply perform md5 on the plaintext.

The reduce operation is used to go from a hash to a plaintext. Note that this does not mean that we reverse the hash, as this would be impossible.

ℹ️ If you do succeed in reversing hashes, you will probably be the richest person on this planet. In which case… send me a bitcoin or two will you?

Hashing algorithms are specifically designed to be irreversible. What we actually do is, we take a hash and after taking it through a reduction function, we end up with a new plaintext. How the reduction function works will be left as out-of-scope for this article, as many implementations can exist and the implementation is not that relevant in order to understand how rainbow tables work.

With this information, our chain will end up looking like this:

A complete rainbow table will have many of these chains:

Lookup

Now that we understand the structure of rainbow tables, let’s see how a plaintext lookup works.

Suppose we have the hash FFE0FA… (shortened for brevity) and we want to find the plaintext that produced it. Our rainbow table stores only the endpoints of chains, not every intermediate hash. In this example, pay attention to the first chain from our visual above:

password123 → FFE0FA… → kitkat987 → B9A1D3…

Here’s the step-by-step lookup process:

1. Check endpoints first:

We first compare FFE0FA… against all end hashes (H2) in our table. In this case, FFE0FA… is not an endpoint (H2), so we need to check earlier positions in the chain.

2. Step back in the chain:

Next, we assume FFE0FA… might be an intermediate hash (H1). Since we didn’t store H1 in the table, we need to “walk” the chain forward to see if it leads to a known endpoint.

• Apply the reduction function to FFE0FA…. The reduction function always produces the same plaintext for the same hash, so here it gives us:

R(FFE0FA…) → kitkat987

• Hash this plaintext:

H(kitkat987) → B9A1D3…

• Compare this new hash against all H2 values in the table. In this example, B9A1D3… matches an endpoint, meaning the chain containing FFE0FA… has been found.

3. Recompute the chain from the start:

With the matching endpoint identified, we retrieve the chain’s starting plaintext, password123, and recompute the chain step by step:

password123 → H(password123) → FFE0FA… → R(FFE0FA…) → kitkat987 → H(kitkat987) → B9A1D3…

While recomputing, we check each hash:

• H1 = FFE0FA… → This matches our target hash, so the plaintext we were looking for is **password123**.

If the hash hadn’t matched at H1, we could have applied the reduction function again and repeated the process to check the next chain position. However, with a chain length of 2 hashes, there are only two positions to check (H1 and H2). If neither position matches, the hash isn’t covered by our rainbow table.

In reality, chains will be significantly longer, meaning that a lookup may take many steps of reduction and hashing before ending up with a plaintext.

Note also that production-grade rainbow tables such as those from crackmyha.sh often use dynamic reduction functions that change based on the chain index. This helps minimize chain merging, which occurs when two chains produce the same hash at the same position.

In our example, if two chains generate the same hash at H1, from that point on they will produce identical intermediate hashes and endpoints. Once chains merge, they effectively become a single chain, reducing the overall coverage of the table.

Conclusion

Rainbow tables are a powerful tool for reversing hashes efficiently by trading storage for computation. By precomputing chains of hashes and plaintexts, they allow security researchers and attackers to quickly find original passwords without brute-forcing every possibility.

Shameless plug:

Tired of waiting for hashcat to complete? The Crackmyha.sh hash lookup service will be launching soon. Crackmyha.sh is built on top of quality rainbow tables and removes all the complexity of cracking hashes manually.