How To: Create Rainbow Tables for Hashing Algorithms Like MD5, SHA1 & NTLM

A rainbow table can be thought of like a dictionary, except instead of words and their definitions, it holds combinations of characters on one side and their hashed form on the other. What is a hash and why would you want to know what random combinations of characters are hashed into?

Passwords on the internet are almost always stored hashed. A hash is a method of cryptography that is very cheap to calculate in one direction but very expensive to calculate in the opposite direction. What that means is that you can take a raw text input, say the string password, and run a hashing algorithm on it such as MD5 to get an output of 5F4DCC3B5AA765D61D8327DEB882CF99.

While MD5 may be being replaced by stronger hashing methods such as bcrypt, it's still commonly used on LAMP stacks across the internet today.

Going back to rainbow tables, we should have an entry saying password on one side and 5F4DCC3B5AA765D61D8327DEB882CF99 on the other. Should we ever come across this hash, we can search our table, find it, and learn what the original string was. However, before we can do that, we must learn how to make a rainbow table.

For this guide, I'll be demonstrating from a base of Kali Linux running in a virtual machine, but the instructions for most Linux distros will be basically the same. I will also include some information for those on the Windows platform.

Step 1: Set Up RainbowCrack

We'll be using RainbowCrack to create and sort our tables. Kali Linux comes with RainbowCrack already installed, but if you don't have it or are running on Windows, you can download it or use aptitude if you are on a Debian-based distro like Mint.

On Windows, once you have downloaded RainbowCrack, create a new folder that you can easily navigate to with Command Prompt and extract everything into it. Then, open the Command Prompt, and navigate to the directory you created. Move on to Step 2, since the next paragraphs are for Kali.

In Kali, once we're sure RainbowCrack is installed, we'll need to create a new folder and navigate into it. This is where our tables will be generated and sorted (see Step 3 and 4 for exceptions). You can use the following commands to set up the folder in your home directory. It's best to use a new and empty directory for the sorting process that comes after the table is generated.

cd ~
mkdir RainbowTables
cd RainbowTables

It's important to keep in mind that rainbow tables take up enormous amounts of storage space, especially when you include a wide character set and a long max length. Make sure you have room for hundreds of gigabytes at the very least. Having at least half a terabyte free is better. If you don't have this space available, you can still follow along using smaller character sets, shorter max lengths, and shorter chain lengths.

Step 2: View the Parameters

Once we're in the directory we created, we can run rtgen to make sure everything is installed correctly. This will also return some convenient help, with some example usages of rtgen and the naming of parameters.

rtgen

RainbowCrack 1.7
Copyright 2017 RainbowCrack Project. All rights reserved.
http://project-rainbowcrack.com/

usage: rtgen hash_algorithm charset plaintext_len_min plaintext_len_max table_index chain_len chain_num part_index
       rtgen hash_algorithm charset plaintext_len_min plaintext_len_max table_index -bench

hash algorithms implemented:
    lm HashLen=8 PlaintextLen=0-7
    ntlm HashLen=16 PlaintextLen=0-15
    md5 HashLen=16 PlaintextLen=0-15
    sha1 HashLen=20 PlaintextLen=0-20
    sha256 HashLen=32 PlaintextLen=0-20

examples:
    rtgen md5 loweralpha 1 7 0 1000 1000 0
    rtgen md5 loweralpha 1 7 0 -bench

As you can see, there are two usages given with one example for each:

rtgen hash_algorithm charset plaintext_len_min plaintext_len_max table_index chain_len chain_num part_index

 rtgen md5 loweralpha 1 7 0 1000 1000 0

rtgen hash_algorithm charset plaintext_len_min plaintext_len_max table_index -bench

 rtgen md5 loweralpha 1 7 0 -bench

Of course, because of the space constraints, the parameters aren't really explained, so I'll do that so it's easier to follow along later.

• hash_algorithm: This is the hash algorithm that we want our rainbow tables to use. You can see a list of available algorithms under hash algorithms implemented in the return text. For our example, we will use MD5, but RainbowCrack is just as capable of making perfect SHA1 and NTLM tables, and I will provide the code for the tables for all three.
• charset: The set of characters used to generate the plain-text strings for the rainbow tables. Numeric is digits 0–9, loweralpha is alphanumeric (all letters and digits 0–9), but only in lowercase. For a full list of charsets that you can use, see "charset.txt" that comes with RainbowCrack.
• plaintext_len_min: The minimum length of plaintext strings. For example, if we choose a numeric charset and a min and max of 1, our table will contain all digits 0–9 and their hashed equivalent.
• plaintext_len_max: The maximum length of plaintext strings. For example, if we choose a min of 1 and a max of 2, we get all digits 0–9 and 00–99 and their hashed equivalents in our table.
• table_index: This parameter selects the reduction function. A reduction function is a math formula that trims the number of combinations by removing combinations that are incredibly unlikely to be used. By doing so, it lowers computational time drastically. But the flip-side is that there is a tiny possibility that any given reduction function will skip the combination we're looking for, so "perfect" tables use multiple runs with different reduction functions to make tables that are "perfect," containing every possible combination.
• chain_len: This controls the length of each table. The larger this number is, the more plaintexts are hashed and stored in the table. This is why the reduction function mentioned above matters — it will reduce possible combinations to the chain length you picked. The flip-side of having a long chain length is generation time. If you want a table that is "perfect" and vast, it can take months.
• chain_num: This is the number of chains to generate. Each chain will be 16 bytes.
• part_index: This is for situations where your hard disk space or computing power is limited, or when your filesystem is unable to address extraordinarily large files. We can change this from the 0 that it should normally be to segment the table file into smaller parts.
• -bench: This is a flag that you can add to do a benchmark on the settings that you have selected. It will not actually create any rainbow tables, it will just determine some numbers that you can use to determine how fast you can generate table entries. Based off of that, you can determine how long table generation will actually take.

Step 3: Generate the Rainbow Tables

Now, let's generate those tables! Note, if you're using Windows instead of Linux, you may have to use rtgen.exe instead of just rtgen in my examples below. Run each of the commands below separately. But be warned, these will take hours to fully generate. You can hit Ctrl-C on your keyboard to quit, and the next time you run the same command, it will resume where it left off.

rtgen md5 loweralpha-numeric 1 7 0 2400 24652134 0
rtgen md5 loweralpha-numeric 1 7 1 2400 24652134 0
rtgen md5 loweralpha-numeric 1 7 2 2400 24652134 0
rtgen md5 loweralpha-numeric 1 7 3 2400 24652134 0
rtgen md5 loweralpha-numeric 1 7 4 2400 24652134 0
rtgen md5 loweralpha-numeric 1 7 5 2400 24652134 0

The commands above generate six different rainbow tables using the loweralpha-numeric charset which contains 36 possible characters. For any plaintext falling into that category, we will have over a 99% chance of having its hashed equivalent in our tables.

rtgen md5 loweralpha-numeric 1 7 0 2400 24652134 0
rainbow table md5_loweralpha-numeric#1-7_0_2400x24652134_0.rt parameters
hash algorithm:         md5
hash length:            16
charset name:           loweralpha-numeric
charset data:           abcdefghijklmnopqrstuvwxyz0123456789
charset data in hex:    61 62 63 64 65 66 67 68 69 6a 6b 6c 6d 6e 6f 70 71 72 73 74 75 76 77 78 79 7a 30 31 32 33 34 35 36 37 38 39
charset length:         36
plaintext length range: 1 - 7
reduce offset:          0x00000000
plaintext total:        80603140212

sequential starting point begin from 0 (0x0000000000000000)
generating...
65536 of 24652134 rainbow chains generated (0 m 21.3 s)
131072 of 24652134 rainbow chains generated (0 m 32.8 s)
196608 of 24652134 rainbow chains generated (0 m 32.2 s)
262144 of 24652134 rainbow chains generated (0 m 32.9 s)
327680 of 24652134 rainbow chains generated (0 m 32.2 s)
393216 of 24652134 rainbow chains generated (0 m 33.0 s)
458752 of 24652134 rainbow chains generated (0 m 33.3 s)
524288 of 24652134 rainbow chains generated (0 m 34.0 s)
589824 of 24652134 rainbow chains generated (0 m 33.3 s)
655360 of 24652134 rainbow chains generated (0 m 33.8 s)
720896 of 24652134 rainbow chains generated (0 m 33.0 s)
786432 of 24652134 rainbow chains generated (0 m 32.3 s)
851968 of 24652134 rainbow chains generated (0 m 34.0 s)
917504 of 24652134 rainbow chains generated (0 m 34.3 s)
983040 of 24652134 rainbow chains generated (0 m 34.4 s)
1048576 of 24652134 rainbow chains generated (0 m 33.7 s)
.....

When each rainbow table is finished, it will be saved as the .rt file that the command generates, putting it into your current directory. So each rainbow table will get its own unique .rt file. Note that on newer versions, rainbow tables may be saved in your /usr/share/rainbowcrack directory instead of your current directory.

If you are trying to create tables for SHA1 or NTLM, or perhaps a different charset and length for MD5, you can reference the tables created by the RainbowCrack team. At the bottom of the page, you can select the algorithm you are looking for to view a list of the commands to run to build your own.

Step 4: Sort the Rainbow Tables

Our rainbow table generation is done, but we can't use them just yet. We need to sort them into one table that we can then efficiently search. Luckily, doing this is easy, we just run:

rtsort .

As long as we are in the directory we generated them in, the rtsort . command will turn all the tables we generated into easy-to-search .rt files. These files will be accessible in the directory we chose, in this case, Rainbow Tables in the home directory. However, in some versions of Rainbow Crack, all .rt files will be saved in the /usr/share/rainbowcrack directory, no matter what directory you're currently in. The command above should still work when in the folder you created in Step 1.

Now you have a near perfect rainbow table at your disposal. We'll discuss what we can do with this table, how to do it, and how to protect yourself from people attempting to use rainbow tables to crack your passwords in another guide coming soon.

• Follow Null Byte on Twitter, Flipboard, and YouTube
• Sign up for Null Byte's weekly newsletter
• Follow WonderHowTo on Facebook, Twitter, Pinterest, and Flipboard