[Tutorial] How to create a Rainbow Table Set

_haxxor_ · **Posted:** 14 Oct 2009, 21:15

First of all, if we want to create a rainbow table set, we need to know what type of passwords we want to crack with it.

We have the password : frt2ns9

The characters in the password are loweralpha (f,r,t,n,s) and numeric (2,9).
loweralpha = [abcdefghijklmnopqrstuvwxyz]
numeric = [0123456789]

If we combine the two charsets we will end up with :
loweralpha-numeric = [abcdefghijklmnopqrstuvwxyz0123456789]

Now, the password length is 7. In order to crack this password we will need a rainbow table set with the following properties :
charSet : loweralpha-numeric
charSetLen = 36
maxPwLen = 7 (length of the password)

Now we need to calculate the keySpace of the above configuration.
The ecuation is :
keySpace = charSetLen * (charSetLen^maxPwLen - 1)/(charSetLen - 1))

The keySpace is actually the number of possible password combinations that are loweralpha-numeric and have the length between 1 and maxPwLen.
For example: loweralpha-numeric, 1-7.
{a,b,c,...,z,0,1,2,...,9,aa,ab,...,az,a0,a1,...,a9,ba,bc,...,zz,...,99,aaa,...,bbb,...,ccc,...,zzz,...,999,...aaaaaaa,aaaaaab,aaaaaac,...,zzzzzzz,...,9999999}

There are 26 characters in loweralpha, 10 in numeric.
So there are 26+10=36 possible passwords with length 1, 36^2=1296 passwords with length 2, and so on until maxPwLen = 7 : 36^7=78364164096. If we add these, we end up with the actual keySpace: 36^1+36^2+36^3+...+36^7 = 80603140212 = 2^36.23 .
As you can see, the keySpace could be written also as : charSetLen^1 + charSetLen^2 + charSetLen^3 +...+ charSetLen^maxPwLen.

So the keySpace is 80603140212.

BarsWF's bruteforcer (3.14.by), on Core2Duo E2140@3Ghz, has a speed of 100Mhashes/sec. So to calculate the time to bruteforce the above config we only need to divide keySpace with the hash speed : 80603140212/100000000=806 sec.

This means that in the worst case (password : 9999999) it will take up to ~13 minutes to crack (one MD5 hash).

So far, if we want to create a rt set, we need to keep in mind :
1. The type of passwords to be cracked, the charset, and maximum password length.
2. If the keySpace is small and we have a small amount of hashes to crack, it is more efficient to bruteforce the keySpace. If we have a large list of hashes to crack, and/or the keySpace is larger, it's better to create a set of rainbow tables.

Because rainbow tables have the time over memory trade-off property, and they are based on statistical functions => it's more efficient to generate rt's with the success probability of 99.9%. These tables will crack 999 hashes in 1000 (miss 1 in 1000). The higher the success probability, the higher the table size and generation time.

Sc00bz from FreeRainbowTables.com worked out the math behind the rainbow tables, and we ended up with the following conclusion : the best configuration is 5 perfect tables with the tableWorkFactor = 4.48860x in order to get 99.9% success probability.

Here are the charts Sc00bz created :

Perfect Rainbow Tables "99.9%"

[Tutorial] How to create a Rainbow Table Set

Who is online