RainbowCrack

Introduction

RainbowCrack is a general propose implementation of Philippe Oechslin's faster time-memory trade-off technique. Function of this software is to crack hash.

The straightforward way to crack hash is brute force. In brute force approach, all candidate plaintexts and corresponding hashes are computed one by one. The computed hashes are compared with the target hash. If one of them matches, the plaintext is found. Otherwise the process continues until finish searching all candidate plaintexts.

In time-memory tradeoff approach, the task of hash computing is done in advance with the results stored in files called "rainbow table". After that, hashes can be looked up from the rainbow tables whenever needed. The pre-computation process needs several times the effort of full key space brute force. But once the one time pre-computation is complete, the table lookup performance can be hundreds or thousands times faster than brute force.

This document explains the steps to make the RainbowCrack software working for first time user. Most contents in this document are implementation specific, while others are generic to time-memory tradeoff algorithm.

The RainbowCrack software includes three tools that must be used in sequence to make things working.
Step 1: Use rtgen program to generate rainbow tables.
Step 2: Use rtsort program to sort rainbow tables generated by rtgen.
Step 3: Use rcrack program to lookup rainbow tables sorted by rtsort.

The table lookup process in final step is equivalent to the hash cracking process.

The way to use these programs will be explained in this document. All of them are command line programs.

Step 1: Use rtgen program to generate rainbow tables

The rtgen program need several parameters to generate a rainbow table, the syntax of the command line is:

    rtgen hash_algorithm charset plaintext_len_min plaintext_len_max table_index chain_len chain_num part_index

Explanation of these parameters:

parameter	meaning
hash_algorithm	The hash algorithm (lm, ntlm, md5 and so on) used in the rainbow table.
charset	The charset of all plaintexts in the rainbow table. All possible charset are defined in the charset.txt file.
plaintext_len_min plaintext_len_max	These two parameters define the possible length of all plaintexts in the rainbow table. If charset is numeric, plaintext_len_min is 1, and plaintext_len_max is 5. Then the plaintext "12345" is likely included in the table, but "123456" will not be included.
table_index chain_len chain_num part_index	These four parameters are really difficult to explain in simple words. To read and understand Philippe Oechslin's original paper can help to know the exact meaning. The table_index is related to the "reduce function" that is used in rainbow table. The chain_len is the length of each "rainbow chain" in the rainbow table. A "rainbow chain" sized 16 bytes is the smallest unit in a rainbow table. A rainbow table contains lots of rainbow chains. The chain_num is the number of rainbow chains in the rainbow table. The part_index parameter determines how the "start point" in each rainbow chain is generated. It must be a number (or begin with a number) in RainbowCrack 1.3 & 1.4. In RainbowCrack 1.2, this parameter can be any string because random "start point" is used, while 1.3 & 1.4 use the sequential "start point".

The right values of all the parameters depend on what you need, to select good parameters require some understanding of the time-memory tradeoff algorithm.

One ready to work configuration is given below, as an example:

hash_algorithm	lm, ntlm or md5
charset	alpha-numeric = [ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789] or loweralpha-numeric = [abcdefghijklmnopqrstuvwxyz0123456789]
plaintext_len_min	1
plaintext_len_max	7
chain_len	3800
chain_num	33554432
key space	36^1 + 36^2 + 36^3 + 36^4 + 36^5 + 36^6 + 36^7 = 80603140212 key space is the number of possible plaintexts for the charset, plaintext_len_min and plaintext_len_max selected.
table size	3 GB
success rate	0.999 The time-memory tradeoff algorithm is a probabilistic algorithm. Whatever the parameters are selected, there is always probability that the plaintext within the selected charset and plaintext length range is not covered. The success rate is 99.9% with the parameters used in this example.
table generation commands	The actual rtgen commands used to generate the rainbow tables are: rtgen md5 loweralpha-numeric 1 7 0 3800 33554432 0 rtgen md5 loweralpha-numeric 1 7 1 3800 33554432 0 rtgen md5 loweralpha-numeric 1 7 2 3800 33554432 0 rtgen md5 loweralpha-numeric 1 7 3 3800 33554432 0 rtgen md5 loweralpha-numeric 1 7 4 3800 33554432 0 rtgen md5 loweralpha-numeric 1 7 5 3800 33554432 0 If ntlm or lm table is desired, replace "md5" in commands above with "ntlm" or "lm". If alpha-numeric charset is desired, replace "loweralpha-numeric" in commands above with "alpha-numeric". If lm table is to be generated, please CONFIRM the charset is alpha-numeric instead of loweralpha-numeric. The lm algorithm NEVER uses lowercase letters as plaintext.

Now it is time to generate rainbow table.
Change the current directory of your command prompt to RainbowCrack's directory, and execute following command:

rtgen md5 loweralpha-numeric 1 7 0 3800 33554432 0

This command takes about 4 hours to complete on Core2 Duo E7300 processor. It is safe to stop the computation any time by pressing Ctrl+C. Next time if the rtgen program is executed with exactly same command line parameters, it will resume from where the computation is stopped and continue the table generation.

When the command is finished, a file named "md5_loweralpha-numeric#1-7_0_3800x33554432_0.rt" sized 512 MB will be in place. The file name is simply all the command line parameters connected, with the "rt" extension. The rcrack program to be explained later need this piece of information to know parameters of the rainbow table. So don't rename the file.

Remaining tables can be generated in same way with commands:

rtgen md5 loweralpha-numeric 1 7 1 3800 33554432 0 rtgen md5 loweralpha-numeric 1 7 2 3800 33554432 0 rtgen md5 loweralpha-numeric 1 7 3 3800 33554432 0 rtgen md5 loweralpha-numeric 1 7 4 3800 33554432 0 rtgen md5 loweralpha-numeric 1 7 5 3800 33554432 0

Finally, these files are generated:
md5_loweralpha-numeric#1-7_0_3800x33554432_0.rt     512MB
md5_loweralpha-numeric#1-7_1_3800x33554432_0.rt     512MB
md5_loweralpha-numeric#1-7_2_3800x33554432_0.rt     512MB
md5_loweralpha-numeric#1-7_3_3800x33554432_0.rt     512MB
md5_loweralpha-numeric#1-7_4_3800x33554432_0.rt     512MB
md5_loweralpha-numeric#1-7_5_3800x33554432_0.rt     512MB

Now the rainbow table generation process complete.

Step 2: Use rtsort program to sort rainbow tables

The rainbow tables generated by rtgen program need some post processing to make table lookup easier. The rtsort program is used to sort the "end point" of all rainbow chains in a rainbow table.

Use following commands:

rtsort md5_loweralpha-numeric#1-7_0_3800x33554432_0.rt rtsort md5_loweralpha-numeric#1-7_1_3800x33554432_0.rt rtsort md5_loweralpha-numeric#1-7_2_3800x33554432_0.rt rtsort md5_loweralpha-numeric#1-7_3_3800x33554432_0.rt rtsort md5_loweralpha-numeric#1-7_4_3800x33554432_0.rt rtsort md5_loweralpha-numeric#1-7_5_3800x33554432_0.rt

Each command above takes about 1 to 2 minutes to complete. The rtsort program will write the sorted rainbow table to the original file.
Don't interrupt the rtsort program; otherwise the rainbow table being sorted will be damaged.
If the free memory size of your system is smaller than the size of the rainbow table being sorted, temporary hard disk space as large as the rainbow table size will be needed to store intermediate data.

Now the rainbow table sorting process complete.

Step 3: Use rcrack program to lookup rainbow tables

The rcrack program is used to lookup the rainbow tables. It only accepts sorted rainbow tables.

Assume the sorted rainbow tables are placed in c:\rt directory, to crack single hash the command line will be:

rcrack c:\rt\*.rt -h your_hash_comes_here

The first parameter specifies the path to the rainbow tables to lookup. The "*" and "?" character can be used to specify multiple files.

Normally it takes seconds or tens of seconds to finish, if the plaintext is within the selected charset and plaintext length range. Otherwise, it takes much longer time to search all the tables only to find nothing.

To crack multiple hashes, place all the hashes in a text file with each hash in a line. And then specify file name in rcrack command line:

rcrack c:\rt\*.rt -l hash_list_file

If the rainbow tables you generate use lm algorithm, the rcrack program has special support for it with the "-f" command switch. A hash dump file in pwdump format is required as input to rcrack program. The file will looks like this:

    Administrator:500:1c3a2b6d939a1021aad3b435b51404ee:e24106942bf38bcf57a6a4b29016eff6:::
    Guest:501:a296c9e4267e9ba9aad3b435b51404ee:9d978dda95e5185bbeda9b3ae00f84b4:::

The pwdump file is the output of pwdump2, pwdump3 or other utilities. It contains both the lm hash and the ntlm hash.

To crack lm hashes in pwdump file, use following command:

rcrack c:\rt\*.rt -f pwdump_file

The lm hash algorithm converts all lowercase letters in plaintext to uppercase; as a result all the plaintexts cracked via the lm hash never contain lowercase letters, while the actual plaintext may contain lowercase letters. The rcrack program will try to do case correction with the ntlm hashes stored in same file and output the original plaintext.

Defense against rainbow tables

A rainbow table is ineffective against one-way hashes that include salts. For example, consider a password hash that is generated using the following function (where "." is the concatenation operator):
hash = MD5 (password . salt)
Or
hash = MD5 (MD5 (password) . salt)
The salt value is not secret and may be generated at random and stored with the password hash. A large salt value prevents precomputation attacks, including rainbow tables, by ensuring that each user's password is hashed uniquely. This means that two users with the same password will have different password hashes (assuming different salts are used). In order to succeed, an attacker needs to precompute tables for each possible salt value. Even for older Unix passwords, which used a 12-bit salt, this would be improbable. The MD5-crypt and bcrypt methods—used in Linux, BSD Unixes, and Solaris—have salts of 48 and 128 bits, respectively.^[3] These larger salt values make precomputation attacks for almost any length of password infeasible against these systems for the foreseeable future.
Another technique that helps prevent precomputation attacks is key strengthening (also called key stretching). When stretching is used, the salt, password, and a number of intermediate hash values are run through the underlying hash function multiple times to increase the computation time required to hash each password^[4]. For instance, MD5-Crypt uses a 1000 iteration loop that repeatedly feeds the salt, password, and current intermediate hash value back into the underlying MD5 hash function.^[3] The user's password hash is the concatenation of the salt value (which is not secret) and the final hash. The extra time is not noticeable to a user because he only has to wait a fraction of a second each time he logs in. On the other hand, stretching greatly reduces the effectiveness of a brute-force or precomputation attacks because it reduces the number of computations an attacker can perform in a given time frame. This principle is applied in MD5-Crypt and in bcrypt.^[5]
Also, rainbow tables and other precomputation attacks do not work against passwords that contain symbols outside the range presupposed, or that are longer than those precomputed by the attacker. Because of the sizable investment in computing processing, rainbow tables beyond fourteen places in length are not yet common. So, choosing a password that is longer than fourteen characters or that contains non-alphanumeric symbols may force an attacker to resort to brute-force methods.

Nearly all distributions and variations of Unix, Linux, and BSD use hashes with salts, though many applications use just a hash (typically MD5) with no salt. The Windows NT/2000 family uses the LAN Manager and NT LAN Manager hashing method and is also unsalted, which makes it one of the more popularly generated tables.