Tutorial on the rainbow tables
From ChekMate Security Group
Contents |
RainbowCrack tutorial
by Zhu Shuanglei <shuanglei@hotmail.com>
http://www.antsight.com/zsl/rainbowcrack/
RainbowCrack is a general propose implementation of Philippe Oechslin's faster time-memory trade-off technique. In this tutorial, we will guide you through the steps to build a instant windows password cracker. You can always take Philippe Oechslin's paper as a good reference if you want some in depth understanding of the theory.
Some basis of Time-Memory Trade-Off
There are two typical attacks in cryptanalysis of block ciphers: brute force and table precomputation. In brute force, an attacker tries all possible keys to encrypt a known plaintext for which he has the corresponding ciphertext. The idea of table precomputation is to precompute and store encryptions of a chosen plaintext and corresponding keys for all possible keys.
RainbowCrack use the second method. It precompute and store all possible plaintext - hash pairs in files so called "rainbow table". Any time the plaintext of a hash is required, you just look up the precomputed tables and find the plaintext in seconds.
Precompute the rainbow tables with rtgen.exe
Now the time to generate the rainbow tables.
There is an utility called "rtgen.exe" (rainbow table generator) in the distribution. Now open a command prompt, switch to the directory where the rainbowcrack files are extracted, make sure there is 128 MB free disk space in place and execute the command:
rtgen lm alpha 1 7 0 2100 8000000 all
This will begin the generation of first rainbow table. It takes 13.2 hours to complete on a 666 MHz CPU. If you want to generate a rainbow table for md5/sha1 algorithm(used to crack md5/sha1 hashes), you can use the command like this "rtgen md5 alpha 1 7 0 2100 8000000 all" or "rtgen sha1 alpha 1 7 0 2100 8000000 all". Here "alpha" is upper case alpha, you can generate a lower case alpha table like this "rtgen md5 loweralpha 1 7 0 2100 8000000 all".
Leave you computer working ...
You can pause the precomputation any time by pressing Ctrl+C. Next time you run rtgen.exe with the same parameters the program will pick up where the precomputation left off and continue the generation of the rainbow table.
When the generation of first rainbow table is finished. There will be a file named "lm_alpha#1-7_0_2100x8000000_all.rt" (128000000 bytes) in the directory. Don't rename the file because we store some parameters in the file title.
Now the time to generate the remaining rainbow tables, make sure you have enough free disk space (128000000 bytes for each table):
rtgen lm alpha 1 7 1 2100 8000000 all rtgen lm alpha 1 7 2 2100 8000000 all rtgen lm alpha 1 7 3 2100 8000000 all rtgen lm alpha 1 7 4 2100 8000000 all
Replace "lm" with "md5" or "sha1" if you want.
Leave you computer working ...
When the precomputation is complete, make sure the following files are in place:
128,000,000 bytes lm_alpha#1-7_0_2100x8000000_all.rt 128,000,000 bytes lm_alpha#1-7_1_2100x8000000_all.rt 128,000,000 bytes lm_alpha#1-7_2_2100x8000000_all.rt 128,000,000 bytes lm_alpha#1-7_3_2100x8000000_all.rt 128,000,000 bytes lm_alpha#1-7_4_2100x8000000_all.rt
If everything goes well, backup all files (recommended) and proceed to the next section of the tutorial.
Sort rainbow tables with rtsort.exe
To speed up the search of rainbow table, we should sort the rainbow table with "rtsort.exe" in advance.
In fact "rcrack.exe" only accept sorted rainbow tables.
Use these commands:
rtsort lm_alpha#1-7_0_2100x8000000_all.rt rtsort lm_alpha#1-7_1_2100x8000000_all.rt rtsort lm_alpha#1-7_2_2100x8000000_all.rt rtsort lm_alpha#1-7_3_2100x8000000_all.rt rtsort lm_alpha#1-7_4_2100x8000000_all.rt
Each command will take several minutes to complete. The "rtsort.exe" utility will sort the file and write back to the original file.
Notice: If free memory size is smaller than the file size, we can't load the file into memory at a time. In which case extra free disk space as large as the file to be sorted is required to apply an external sort.
If everything goes well, proceed to the next section.
Crack the hash with rcrack.exe and the sorted rainbow tables
Finally you have everything ready. Now the time to play with "rcrack.exe".
Notice the file "random_lm_alpha#1-7.hash" in the distribution. It contain 10 randomly generated lanmanager hashes(charset alpha, length 1-7). We will use this file as a test vector.
Launch the program by issuing the command:
rcrack c:\rainbowcrack\*.rt -l random_lm_alpha#1-7.hash
You should replace "c:\rainbowcrack\" with where you place the sorted rainbow tables. It seems that you will find the plaintext of all 10 lanmanager hashes. Now open the file "random_lm_alpha#1-7.plain" and validate the result of rcrack.exe. If they match, that is ok.
To crack some windows password, the syntax is similar:
pwdump2 > pwfile.txt rcrack c:\rainbowcrack\*.rt -f pwfile.txt
The pwdump2 utility is used to dump the lanmanager hashes of windows system. If your password consists of letters only, rcrack will be able to crack it with the success rate 99.9%.
Have fun!
Create date: 2003/9/9 Revised: 2003/11/21
