Jun 292011
 


I have been having way too much fun with rainbow tables as of late, which is unfortunate since I should be spending time on my latest Android application – I Need A Ride, but also fitting considering a recent political event. After Mt. Gox (the largest exchange in the Bitcoin market) got hacked and everyone’s personal information was released from their database, I noticed that everyone’s passwords were encrypted with a salted MD5 hash (FreeBSD). After posting a 1btc bounty to whoever could decrypt my password first, it got me into the basics of encryption. I quickly discovered a community of people who use the BOINC client to distribute CPU power across many machines with the goal of creating large rainbow tables – http://www.freerainbowtables.com/. Their mission “… is to prove the insecurity of using simple hash routines to protect valuable passwords, and force developers to use more secure methods.” Mt. Gox did, in fact, prevent people from using rainbow tables since the hash was salted.

Regardless, I wanted to download a set and see how well it stacked up against another type of decryption which involves using your video card(s).

So I downloaded their largest set which claims to be able to decrypt any md5 encrypted password that is up to 8 characters in length containing numbers, spaces, lower and upper case letters. The size of such a table? A cool 380GB. Let’s see how well it did finding the phrase: To0 1oNG (01e68d3411e5c5a9429850dce73ca50f)

5,200 RPM USB HDD

Using 8 threads for pre-calculation and false alarm checking...
Found 440 rainbowtable files...
 
md5_mixalpha-numeric-space#1-8_0_60000x27443122_distrrtgen[p][i]_109.rti:
reading index... 134724491 bytes read, disk access time: 4.14 s
reading table... 219544976 bytes read, disk access time: 6.70 s
verifying the file... ok
searching for 1 hash...
Pre-calculating hash 1 of 1.                    
 
Checking false alarms for hash 1 of 1.                    
 
cryptanalysis time: 0.26 s
 
md5_mixalpha-numeric-space#1-8_0_60000x67108864_distrrtgen[p][i]_000.rti:
reading index... 329426119 bytes read, disk access time: 9.96 s
reading table... 536870912 bytes read, disk access time: 16.11 s
verifying the file... ok
searching for 1 hash...
Checking false alarms for hash 1 of 1.                    
 
cryptanalysis time: 0.50 s
 
.
.
.
 
md5_mixalpha-numeric-space#1-8_0_60000x67108864_distrrtgen[p][i]_043.rti:
reading index... 329500490 bytes read, disk access time: 10.32 s
reading table... 536870912 bytes read, disk access time: 16.66 s
verifying the file... ok
searching for 1 hash...
Checking false alarms for hash 1 of 1.
 
plaintext of 01e68d3411e5c5a9429850dce73ca50f is To0 1oNG
 
cryptanalysis time: 0.60 s
 
statistics
-------------------------------------------------------
plaintext found:            1 of 1 (100.00%)
total disk access time:     1159.59 s
total cryptanalysis time:   21.87 s
total pre-calculation time: 97.53 s
total chain walk step:      1799910001
total false alarm:          15107
total chain walk step due to false alarm: 331458571
 
result
-------------------------------------------------------
01e68d3411e5c5a9429850dce73ca50f	To0 1oNG hex:546f3020316f4e47

What the heck? That took forever (~21 minutes)! Rainbow tables rely in disk read times instead of CPU power due to the space-time trade-off. Since I stored these tables on a 5200 RPM external USB hard drive, the process took a very long time. As a result, I thought I would try it again by placing them on a 7200 RPM SATA 6gb/s drive:

7,200 RPM SATA 6gb/s HDD

Using 8 threads for pre-calculation and false alarm checking...
Found 440 rainbowtable files...
 
md5_mixalpha-numeric-space#1-8_0_60000x27443122_distrrtgen[p][i]_109.rti:
reading index... 134724491 bytes read, disk access time: 1.14 s
reading table... 219544976 bytes read, disk access time: 1.98 s
verifying the file... ok
searching for 1 hash...
Pre-calculating hash 1 of 1.                    
 
Checking false alarms for hash 1 of 1.                    
 
cryptanalysis time: 0.25 s
 
md5_mixalpha-numeric-space#1-8_0_60000x67108864_distrrtgen[p][i]_000.rti:
reading index... 329426119 bytes read, disk access time: 2.76 s
reading table... 536870912 bytes read, disk access time: 4.51 s
verifying the file... ok
searching for 1 hash...
Checking false alarms for hash 1 of 1.                    
 
cryptanalysis time: 0.48 s
 
.
.
.
 
md5_mixalpha-numeric-space#1-8_0_60000x67108864_distrrtgen[p][i]_043.rti:
reading index... 329500490 bytes read, disk access time: 2.81 s
reading table... 536870912 bytes read, disk access time: 4.51 s
verifying the file... ok
searching for 1 hash...
Checking false alarms for hash 1 of 1.                    
 
plaintext of 01e68d3411e5c5a9429850dce73ca50f is To0 1oNG
 
cryptanalysis time: 0.47 s
 
statistics
-------------------------------------------------------
plaintext found:            1 of 1 (100.00%)
total disk access time:     324.77 s
total cryptanalysis time:   21.85 s
total pre-calculation time: 94.39 s
total chain walk step:      1799910001
total false alarm:          15107
total chain walk step due to false alarm: 331458571
 
result
-------------------------------------------------------
01e68d3411e5c5a9429850dce73ca50f	To0 1oNG	hex:546f3020316f4e47

Way better! That only took ~7 minutes to decrpyt! But let’s take it up one more level by putting the tables on a solid state drive. My SSD is not large enough to hold those tables so I downloaded the numeric set and ran a hash that it would not be able to solve simply to see how fast the SSD could power through the entire set:

SSD (Numeric-only tables)

Using 8 threads for pre-calculation and false alarm checking...
Found 16 rainbowtable files...
 
md5_numeric#1-12_0_10000x50052_distrrtgen[p][i]_3.rti:
reading index... 46618 bytes read, disk access time: 0.00 s
reading table... 400416 bytes read, disk access time: 0.00 s
verifying the file... ok
searching for 1 hash...
Checking false alarms for hash 1 of 1.                    
 
cryptanalysis time: 0.00 s
 
md5_numeric#1-12_0_10000x67108864_distrrtgen[p][i]_0.rti:
reading index... 62150231 bytes read, disk access time: 0.28 s
reading table... 536870912 bytes read, disk access time: 2.41 s
verifying the file... ok
searching for 1 hash...
Checking false alarms for hash 1 of 1.                    
 
cryptanalysis time: 0.53 s
 
.
.
.
 
md5_numeric#1-12_3_10000x67108864_distrrtgen[p][i]_2.rti:
reading index... 60811509 bytes read, disk access time: 0.28 s
reading table... 536870912 bytes read, disk access time: 2.42 s
verifying the file... ok
searching for 1 hash...
Checking false alarms for hash 1 of 1.                    
 
cryptanalysis time: 0.51 s
 
statistics
-------------------------------------------------------
plaintext found:            0 of 1 (0.00%)
total disk access time:     35.01 s
total cryptanalysis time:   6.69 s
total pre-calculation time: 5.63 s
total chain walk step:      99970002
total false alarm:          25539
total chain walk step due to false alarm: 94554526
 
result
-------------------------------------------------------
e54769f43e51a2fb5228a6b69383be7f	<notfound>	hex:<notfound>

Although we cannot directly compare the alpha numeric tables to the much smaller numeric-only tables, we can clearly see that an SSD is the way to go as it has ridiculously fast read times comparatively.

But what about using a GPU to decrypt an MD5 hash? Using an overclocked GTX 260, I downloaded hashcat with CUDA support and ran the exact same test:

Overclocked Nvidia GTX 260

cudaHashcat-lite v0.4 starting...
 
Platform: NVidia compatible platform found
Watchdog: Temperature limit set to 90c
Device #1: GeForce GTX 260, 842MB, 1495Mhz, 27MCU
[s]tatus [p]ause [r]esume [q]uit => s
Status.......: Running
Hash.Type....: MD5
Time.Running.: 1 sec
Time.Left....: 2 mins, 46 secs
Plain.Text...: ***aygb
Plain.Length.: 7
Speed........:  807.4M/s
Progress.....: 849346560/134960504832 (0.63%)
HW.Monitor.#1: 98% GPU, 62c Temp
[s]tatus [p]ause [r]esume [q]uit => s
Status.......: Running
Hash.Type....: MD5
Time.Running.: 4 mins, 23 secs
Time.Left....: 1 hour, 49 mins
Plain.Text...: ***aycwb
Plain.Length.: 8
Speed........:  810.3M/s
Progress.....: 216102076416/5533380698112 (3.91%)
HW.Monitor.#1: 99% GPU, 78c Temp
 
.
.
.
 
Status.......: Exhausted
Hash.Type....: MD5
Time.Running.: 1 hour, 52 mins
Time.Left....: 0 secs
Plain.Text...: ***aaaaa
Plain.Length.: 8
Speed........:  809.4M/s
Progress.....: 5533380698112/5533380698112 (100.00%)
HW.Monitor.#1: 98% GPU, 78c Temp
 
Started: Mon Jun 27 21:33:30 2011
Stopped: Mon Jun 27 23:29:11 2011

Almost 2 hours to decrypt! After doing more tests, I discovered that for shorter alpha-numeric passwords (< 6 characters), the GPU was definitely the way to go. But for longer alpha-numeric passwords (7+), the rainbow tables dominated. However, with the proliferation of improved encryption techniques, rainbow tables are a thing of the past, where people will only be able to crack passwords on the fly using their GPU (or calculating hash-specific rainbow tables for a large release of passwords), and not relying upon pre-calculated generic ones.

In an upcoming post I am going to share a quick php program I wrote that will let everyone use the numeric tables demonstrated above to decrypt a password. Everyone will be able to check it out and use the tables themselves without actually having to download them. If I had a web-server with the available storage, I would post up the alpha-numeric-space tables (as well as many hybrid and other tables as well) for all to use. But until that time, you’re going to have to settle for the numeric ones. Try not to die in from anticipation until this time arrives!