What Are Rainbow Tables?

Hello world. I’m Zanidd and welcome to the Hands On Password Cracking and Security course on Code Red. In this section, we’re discussing rainbow table attacks. Into this lesson, we’re going to take a closer look at rainbow tables. In the last video, I told you to imagine that rainbow tables are a table with two columns, one with hashes and the second with the corresponding plain text. But that was just an oversimplification. They’re more than that. Storing all hashes would take too much storage. Rainbow tables are in fact a compromise between pre-computation and low storage usation. First, it uses what is called a reduction function.

Reduction functions map a plain text value to a certain hash, but they do not reverse the hashing operation. As we saw, this is not possible. Reduction functions are a one-way function like hash functions. They can be as simple as taking the first five numbers from the hash. So, we first hash the plain text with the given algorithm, for example, MD5, and then take the first five numbers from the hash. This generates another plain text from the hash, which is not the original plain text but a completely different one.

These reduction functions are used to build chains. The rainbow tables consist of chains for each plain text. A chain starts with a random plain text, hashes it using the hashing function, then reduces the hash to another plain text, hashes the new plain text, and so on. The table only stores the starting plain text and the final hash you choose to end with. And so a chain containing millions of hashes can be represented with only a single starting plain text and one hash. The final table is a lookup table with one plain text and one hash, but they are not the corresponding hashes for the plain text. So you may ask yourself, how can we use this table? It’s useless.

But it’s not. We can use an algorithm. You first need to look for the hash in the table. If you can’t find it, you reduce the hash into another plain text and hash the new one. Now you try to look it up in the list of hashes. When the hash matches with one in the table, you get the starting plain text from the table, hash, and reduce it until you find the corresponding hash with its plain text. This way you can check every hash stored in the chain backwards from the last column in the chain.

You check whether the hash exists in the last column in any of the chains by reducing and hashing the given hash once and then check it against the chain ends. For the second last column, you reduce and hash twice and check for the chain ends. For the third, you do it three times and so on. This sounds pretty complicated, but, luckily for us, we have a couple of tools at our disposal to create and use the rainbow tables. Let’s start by creating one. Please take a minute to study the arguments to the tool. To create a rainbow table, we can use rtgen from the RainbowCrack suite.

The example commands generate a rainbow table with 1,000 chains consisting of lowercase letter passwords with a length from one to seven. Don’t worry if you’re too overwhelmed by it. We’re going to generate a table in a later lesson in this section. There’s one argument that I left out here, namely, dash bench, which will determine how long it will take to generate the rainbow table. I hope you have some idea how rainbow tables work and how we can build and use them. Don’t worry. There will be an exercise at the end of the section where I’m going to show you, step by step, how to generate and use a rainbow table.

But first, we need to get familiar with the tools and commands to perform such an attack in the next lesson.