Understanding Rainbow Tables

My buddy Aamir aka DrChaos.com wrote a interesting post defining what a Rainbow table is, when they are used and why salting passwords makes it hard to use Rainbow tables. The original post can be found HERE.

On the topic of breaking passwords, I often hear security professionals and a few other folks mention Rainbow Tables. I used to think a Rainbow Table was a set of pre-computed (pre-calculated) hashes from passwords…essentially a lookup table where a plaintext’s unencrypted password corresponds to a known hash.

However, this is not a totally accurate definition of a Rainbow Table. In reality, a reverse lookup table allows you create a second table consisting of the password hash of user accounts. Then you use a Rainbow Table consisting of hashes and guessed passwords to compare the two. You can see if the hashed password of compromised user account matches a hashed password in lookup table.In the reverse lookup table (upper left) you can see Sarah and Stephen have the same password. Therefore, they generated the same password hash in the second table (upper right).

This is dangerous because someone who knows Stephen’s password can now know Sarah’s password by simply looking at the hash. Tons of data has been generated on known passwords and their corresponding hash.

The reason lookup tables don’t work well is because they take a very long time to compute. If you want to find a password, you must have the hash computed for it. This can take a very long time, is extremely processor intensive, and it can be prohibitive due to disk space requirements.

A Rainbow Table is a representation of related plaintext password sequences. They are big lists of passwords. However, there are very stringent criteria applied to the creation of them.

Rainbow Tables are a compromise between a lookup table and low memory usage. The magic in Rainbow Tables is a basically a reduction function. A hash function maps plaintext into hashes. A reduction function reduces the hashes to plain texts.

If you are a security professional, you have most likely heard for years that hashes are one-way functions. They cannot be reversed. Don’t worry, this article does not change that rule. A reduction function is not a true inverse function. It does, however, reverse engineer the hash to plaintext.

A good explanation of this can be found at:

http://kestas.kuliukas.com/RainbowTables/

If the set of plaintexts is [0123456789]{6} (we want a rainbow table of all numeric passwords of length 6), and the hashing function is MD5(), a hash of a plaintext might be MD5(“493823”) -> “222f00dc4b7f9131c89cff641d1a8c50”.

In this case the reduction function R() might be as simple as taking the first six numbers from the hash; R(“222f00dc4b7f9131c89cff641d1a8c50”) -> “222004”.

We now have generated another plaintext from the hash of the previous plaintext. This is the purpose of the reduction function.

Constructing a Rainbow Table requires two things: a hashing function and a reduction function. The hashing function for a given set of Rainbow Tables must match the hashed password you want to recover. The reduction function must transform a hash into something that is usable as a password.

A hash is a one-way function, but a reverse hash is also a one-way function. The chains which make up Rainbow Tables are one-way hash and reduction functions starting at a certain plaintext and ending at a certain hash. Here is the process:

1. A chain in a rainbow table starts with an arbitrary plaintext
2. It then hashes it
3. Next it reduces the hash to another plaintext.
4. Then it hashes the new plaintext

The table only stores the starting plaintext and the final hash at which you choose to end. Thus a chain containing millions of hashes can be represented with only a single starting plaintext and a single finishing hash.

When cracking passwords via brute force, lookups or other functions, the attacker obtains a list of encrypted or hashed passwords. A traditional password attack takes encrypted passwords and tries to guess what the plaintext is. A Rainbow Table takes passwords and encrypts all the guesses and compares them against the hash value.

In other words, your computer is still doing the same amount work in cracking the passwords…perhaps even more in some cases. The big advantage is when a Rainbow Table has been created, the results can be stored, indexed, and searched. Therefore, Rainbow Tables are extremely powerful because a lot of the work has previously been done for you.

How do you protect against Rainbow Table attacks?

To make things difficult for hackers, advanced password techniques now salt passwords. Salting a password means adding random data into the password hash algorithm. This prevents having the same hash value, as we see in the third table at bottom of Figure 1.

If random data is used to salt the hash, this makes the same password used by 2 different individuals result in a unique hash. Stephen and Sara, even if they use the same password, will use different random data along within the hashing algorithm, thus generating a unique hash value.

The most effective way is to use large, random salting of every single password. This method is costly in terms of computational power required to support it. It is also difficult to implement correctly (the random factor) and even when you can use this method it is very difficult to verify it was done correctly.

Until next time – protect those passwords!