Rainbow Tables: Bookkeeping for Password Crackers

This is a continuation of our tutorial series on reversing hashes. You can find the last post here.

When trying to solve a computational problem, you have two resources. Time and memory (space). Methods like dictionary attacks and brute-forcing are time-based attacks because it takes very long each time you perform it. Rainbow tables, on the other hand, get memory involved in the equation.

Rainbow tables are a bit complicated. They are similar to but different from hash tables, which are just tables of (password, hash) pairs. With a hash table, when you want to reverse a hash, you just look up the corresponding pair in the table. Easy! But not very feasible because of the huge memory requirements, and rainbow tables reduce these memory requirements by using a very smart trick.

But before we try to understand how they work, let's use them.

Join our Discord using this invite link to be a part of the SHACK community.

Using a Precomputed Rainbow Table

There are generous people on the Internet who have already created rainbow tables for most common hashing algorithms. All you need to do is use Google: search "md5 rainbow table" and click on the first (trustworthy) website. At the time of writing, this is https://crackstation.net/.

Put your hash in the box, do the captcha, and it should tell you whether the hash was found in the database or not.

Try to use it with the following hashes:

5f4dcc3b5aa765d61d8327deb882cf99 (md5)
4280788d0f7c7a4cf94a396e12deca5431166b22 (sha1)
9cfd153ede266f6f7cf6f1f95d20edae (md4)

Simple, right?

Generating Custom Rainbow Tables: rainbowcrack

There is a pre-installed tool on Kali called rainbowcrack that allows you to create your own rainbow tables with custom settings. If you're not using Kali, you can download the binaries from here.

There are a number of binaries included in rainbowcrack. The ones we care about are rtgen (to generate rainbow tables) and rcrack (to use them to reverse hashes). Below are the help outputs of each command:

Let's create a simple md5 rainbow table. Enter the following command:

rtgen md5 alpha 4 6 0 2100 8000000 all

Here's the output:

It's gonna take a few minutes. It's creating 8,000,000 "chains" that it will then use to do the lookup when we use the table; more on this later.

Normally the *.rt file should be in the present working directory, but I installed rainbowcrack using apt and apparently that means that the tables are stored in /usr/share/rainbowcrack:

I suspect that this is also why I need to use sudo. Make sure the table is in the same directory you're in and then sort it using rtsort

rtsort .

This is what it looks like (I had some other tables too, the one we generated is the third one in the picture):

Now we can crack some hashes. Let's try the following MD5 hash: 9a7facd67360398c818b4a4df1f15c48. Punch this into your terminal:

rcrack . -h 9a7facd67360398c818b4a4df1f15c48

The -h specifies the hash we're trying to crack; using -l allows us to specify a file of newline-separated hashes. Anyway, here's the output:

There you go! You cracked your first hash... kind of.

There are a couple of problems with rainbowcrack though. First of all, it only supports a few hashing algorithms. If you want to generate rainbow tables with custom hashing algorithms (or just newer ones), you need a different solutions. Secondly, I don't think it's maintained anymore. This might also be why it supports so few hash functions. Thirdly, it's kind of a black box and just using it doesn't teach you how rainbow tables actually work. For any actual attacks that knowledge is far more important than just being able to use a tool.

Next up...

In the next instalment to this series, we will write a program to create our own rainbow tables in C with custom requirements. For this, we will need to actually understand how rainbow tables work and are created; I highly recommend reading the original paper by Philippe Oeschlin before moving on to the next article.

Join our Discord using this invite link to be a part of the SHACK community.