Password Cracking – Part 8 – Rainbow Tables

What are Rainbow Tables?
Rainbow tables are lookup tables that contain almost every possible combination of passwords in a given character set. It is simply a completed brute force attack that you can reuse as many times as you wish without having to regenerate all those possible password combinations. This can reduce password cracking time by up to 99%! Of course, to generate a rainbow table it can take longer that it would take to crack one password, but afterwards you will be able to crack others in a few minutes compared to hours. Now that you have a basic idea of what rainbow tables are, let’s look at exactly how they work.
If you recall, I said that rainbow tables store most of the possible hashes in a given character set. This is true, but not in the way you might think. Depending on the character set and length of the password, a rainbow table can get extremely large. Below is an example of tables from the RainbowCrack Project:











If the rainbow stored every hash for every plaintext word in a given character set, it would use more memory then you have or can imagine. Instead, rainbow tables use a time-memory trade off technique, known as chains.
To understand these chains, you must first understand the “reduction function”. As you’ve learned, hash functions map plaintext words to hashes, well, the reduction function maps hashes to plaintexts. You might be thinking, didn’t you say that you couldn’t reverse a hash function and get the plaintext from it? True, the reduction function doesn’t inverse the hash function acquiring the original text. No, instead it gets another plaintext from the hash. For example, if we have a set of plaintexts that are made up of 7 numbers [0-9], using the md5() function a possible hash could be MD5(1234567) -> fcea920f7412b5da7be0cf42b8c93759. In this case the reduction function could be as simple as taking the first seven numbers from the hash to generate a new plaintext. So once the reduction function was applied to the hash, it would result in the new plaintext, “9274125”. And that’s what the reduction function does, generates a new plaintext from a given hash.
These chains that make up rainbow tables are made up many combinations of the one way hash function combined with the reduction function, making a chain. For example, if we were to continue the chain from the first example, it would look like this:
Md5(1234567) -> fcea920f7412b5da7be0cf42b8c93759 ->
Reduction(fcea920f7412b5da7be0cf42b8c93759) -> 9274124 ->
—————————————————————————————–
Md5(9274124) -> ed7db1cf7fc4fbd0169f00c37a0165ab ->
Reduction(ed7db1cf7fc4fbd0169f00c37a0165ab) -> 7174016 ->
—————————————————————————————–
The above chain would keep repeating until you or the rainbow table maker decides to stop it, usually after millions of hashes are created. Now here’s how rainbow tables save memory. Instead of storing every one of these hashes, the rainbow table only stores the first plaintext and the last hash in that chain. Then millions of more chains are created, each representing millions of password hashes. If a table was made up of the above chain, then it would be made up of its first plain and final hash looking something like this: 1234567 -> ed7db1cf7fc4fbd0169f00c37a0165ab.
Once enough tables have been generated (millions), you will want to actually use the final rainbow table to crack a password hash by checking to see if it is inside any of the generated chains. Here is the algorithm:

• Check to see if the hash matches any of the final hashes. If so, break out of the loop
  because you have found the chain that contains its plaintext.
• If the hash doesn’t match any of the final hashes in the tables, use the reduction function on
  it to reduce it into another plaintext, and then hash the new plaintext.
• Go back to step 1.

Now that you know which chain contains the plaintext, you can start with the original plaintext of that chain and start hashing and reducing it until you come to the password hash you are trying to crack and its secret plain text. There you have it! The quickest and simplest explanation of rainbow tables that you will ever find!
When should I use a rainbow table?
If there are rainbow tables available for the type of password hash(es) you have, then use it! Chances are it’ll work. If you have to download the tables, then while that’s going on, trying a dictionary attack won’t hurt.
If the passwords are salted, then you probably will not want to use rainbow tables because you will need to create a new rainbow table for every password. Why? Well, if you recall, when you salt a password, you add a random or unique string to it and then run it through the hashing function. So if the password was “password” and the script attached the user’s username to it, the final password would be MD5(“username”+”password”). Since everyone has a different username, the word “password” will never look the same once hashed.