Before we dive into rainbow tables, it is important to know the difference between brute force and rainbow tables. When cracking a hash using brute force, your cracker is actually starting with a... b... c and so on, it then hashes the characters and compare it to the hash that you need to crack. The hash calculations takes time and therefore it makes sense to save the calculations to disk and later on just do a lookup next time you need to crack a hash. However, there is a problem with this approach: the resulting table size.
Given a character-set of 0-9 and a length of 14. Each line is going to use 15 bytes (14 bytes + newline) we would end up with the following amount of data:
10^14 * 15 bytes = ~1364 TB
That is way to large to store on disk. Rainbow tables solved this problem by using some clever math to reduce the size of this table with a reduction function.
Rainbow tables are split into character-sets, lengths and algorithms. freerainbowtables.com have support for LM, MD5, NTLM and MYSQLSHA1.I've listed the MD5 tables they provide below in the format used to denote rainbow tables: algorithm_charset#length
- md5_mixalpha-numeric-space#1-7: 18
- md5_mixalpha-numeric-all-space#1-8_0_200000 (266 GB)
- md5_mixalpha-numeric-all-space#1-8_8_300000 (175 GB)
- md5_mixalpha-numeric-all-space#1-8_16_400000 (133 GB)
- md5_mixalpha-numeric-all-space#1-8_24_422000 (200 GB)
- md5_mixalpha-numeric-all-space#1-8_32_422000 (200 GB)
The reason for this is that each table gives better precision. Table 1-3 give 68.8% precision, table 4-5 give 81.8% precision. All together they have 99.9% precision. They also have different speeds due to the different chain lengths. For more information about this, have a look at this FAQ.
|Cracking in Hashcat using brute force|
Rainbow Table Formats
There are different formats of rainbow tables.Original rainbow tables had their own format (RT), FreeRainbowTables have index rainbow tables (RTI and RTI2), Cryptohaze have his own format (GRT) and RainbowCrack Project uses compact rainbow tables (RTC). The main difference is the way they are calculated and stored.
In this blog post I'm going to use the RTI2 format tables from FreeRainbowTables as they have the most complete tables and support (still in beta) for GPU processing.
In order to compare brute force and wordlists with rainbow tables, we need some hashes to crack. I've made 10 hashes from randomly chosen passwords from the RockYou leak.
Minimum length: 6
Maximum length: 13
I've also created 3 hashes that should theoretically show the power of rainbow tables.
AsD12 !! b2974bde01dccc073d9d186300ebdcc8
Character-set: 0-9a-zA-Z + symbols
Minimum length: 8
Maximum length: 14
In order to crack the hashes in the most efficient way possible using each method, I'm going to use the most optimal configuration for each hash. Examples:
Brute force: character-set: a-z0-9
Wordlist: no rules
Rainbow tables: md5_loweralpha-numeric-space#1-8
Brute force: character-set: 0-9
Wordlist: Do not apply to this password
Rainbow tables: md5_numeric#1-14
This method ensures that the timings of cracking each hash can be relatively compared. All the hash cracking will be done on the GPU. I'm also not going to use any rules with the word lists as the time to crack each password would depend on the rules used. I'm using the IQ Wordlist from here.
|Cracking in rcracki using rainbow tables|
* Not actually cracked. It is worst case time to crack in theory. In short: It would take too long time for me to crack.
The measurements was done using oclHashcat-lite and rcracki_mt on a Geforce GTX 560Ti and hard disk reads of about 89 MB/s on average.
In this analysis I cracked 12 out of 13 hashes by combining the 3 methods. That is a total of 92,3%.
The power of rainbow tables is only visible when trying to crack complex passwords of lengths equal or close to the upper limit of the rainbow table. Using brute force, it would theoretically have taken ~72 days to crack the password "AsD12 !!". However, it only took rainbow tables about 37 minutes. That is a huge speed improvement! however, using rainbow tables on ordinary passwords will result in lower speeds, partly due to the time it takes to read the large rainbow tables from disk.