How to Perform Cryptanalysis with Rainbow Tables

[Nytro]

How to Perform Cryptanalysis with Rainbow Tables

Author: sToRm

In this tutorial, I'm going to explain how to break (almost) any hash into cleartext using cryptanalysis with rainbow tables.

So first, let's look at a hash, specifically an md5 hash. A standard md5 hash is 32 characters long, composed of alphanumeric (0-9, but only a-f) characters. Another standard hash, but less commonly used is sha1, which is 40 characters long. Basically, the idea behind hashing is that you input a string (your password) and a hash pops out. It is impossible to back-track the hash, i.e. decrypt it (although some weakness have been found in hashing algorithms, there is still no way to reverse the hash), so the only way to crack it is to make a bunch of hashes until we find one that matches.

Common ways of creating lots of hashes (with the intent to find a match to the target hash) are brute-forcing and using a wordlist. Brute-force will come up with every string possible and hash it. If you keep a brute-force on long enough (this can take anywhere from a few hours to a few centuries - not kidding), you will eventually find a match, therefore cracking the hash. This is impractical, as most of us don't have access to university or government supercomputing grids.

The second method of cracking a hash is by using a wordlist. Wordlists use the same principal as brute-forcing, except that they check the hash against a list of commonly-used passwords. Some wordlists are just dictionaries, while others are planned out and target certain genres of words. Wordlists work surprisingly well, mostly because people are dumb and use passwords like "password" or "1234567890".

The third and perhaps most effective method of hash cracking is to use rainbow tables, which I am going to explain to you today. Rainbow tables take the same approach as brute-forcing but are so efficient as to cut down the cracking time to anywhere from a few seconds to a few days. This of course depends on the extension of your rainbow tables. More hashes in your tables means a greater chance of a successful crack, but it trades off for a larger file size and longer cracking time. It's up to you to find the balance.

Okay, enough background information; let's get started with learning how to use rainbow tables. The best program for our task is "rcrack". Rcrack is available at http://www.antsight.com/zsl/rainbowcrack/ as an open source project (Note: rcrack and other bundled programs with it are only executable via the command line). Also, grab some free rainbow tables from http://www.freerainbowtables.com/rainbow_tables/ . You'll find most downloads for the tables themselves in BitTorrent format due to the sheer size (Note: never execute the cracking programs that come "pre-packaged" with table torrents, as most are trojaned. The tables themselves are clean, but always download the programs from their official sites.). The third and final thing you need is a decent character set; these direct rcrack to understanding what types of characters you wish to crack. The absolute best one I've found is by Ramius Kahn, which I've mirrored at http://www.gonullyourself.org/downloads/charset.txt .

Now that you've got your rainbow tables downloaded, rcrack ready, and a decent charset, there's just one final step before you can use these tables. Using the program "rsort" (included in the rcrack package), you must sort each rainbow table (commands available by running the program with no arguments). Doing so is important enough to the efficiency of the cryptanalysis that rcrack will reject any rainbow tables that aren't sorted.

W00t! Now we are ready to crack! Run rcrack with no arguments to learn the commands. Input the hash/es you wish to crack using the appropriate method, and go outside for a few hours. It will tie up your CPU and hard drive (it's pretty resource-intensive), so either do something else, or watch intently at the pretty scrolling text (I'm not kidding, I'm actually apt to do the second sometimes xD). Hopefully, a decrypted hash will pop out at the end, leaving you with a mild case of the lulz.

Rcrack is pretty bitchy sometimes, so if you have any questions or are getting some nasty error, please please please refer to the documentation first (however limited it is), then Google, and then post your questions here. Good luck, and happy hashing!

Written by sToRm

February 15, 2008

[Gonzalez]

Interesant.

-Gonzalez