Jump to content
begood

[tutorial] How to create a rainbow table set

By begood, in Tutoriale in engleza

Recommended Posts

begood Newbie

begood

Posted
Posted

ro : In sfarsit m-am hotarat sa scriu un tutorial cuprinzator care sa descrie metoda de a genera tabele rainbow perfecte, de calitate ridicata (viteza sporita, rata de succes mare).

en : I finally decided to create a comprehensive tutorial in witch I describe the method on how to generate perfect rainbow tables of high quality (high speed & high success rate)

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%"

         |           |           | Less      | Smaller Than | Smaller Than |
         |           |           | Total     | Previous     | Previous     |
         | Work Per  | Total     | Work Than | (Const Chain | (Const Total | Total Success
Tables   | Table     | Work      | Previous  | Length)      | Pre-work)    | Rate
---------+-----------+-----------+-----------+--------------+--------------+-----------------
1 Tables |       N/A |       N/A |           |              |              | 86.46462849% Max
2 Tables |       N/A |       N/A |           |              |              | 98.16793718% Max
3 Tables |       N/A |       N/A |           |              |              | 99.75202349% Max
4 Tables | 12.78300x | 51.13200x |           |              |              | 99.90100293%
5 Tables |  4.48860x | 22.44300x |    56.11% |      0.0001% |      -11.80% | 99.90100191%
6 Tables |  2.72220x | 16.33320x |    27.22% |      0.0007% |       -9.54% | 99.90099547%
7 Tables |  1.95350x | 13.67450x |    16.28% |     -0.0006% |       -8.01% | 99.90099836%
8 Tables |  1.52334x | 12.18672x |    10.88% |     -0.0006% |       -6.91% | 99.90100114%

Non-Perfect Rainbow Tables "99.9%"

         |           |           | Less      | Smaller Than | Smaller Than |
         |           |           | Total     | Previous     | Previous     |
         | Work Per  | Total     | Work Than | (Const Chain | (Const Total | Total Success
Tables   | Table     | Work      | Previous  | Length)      | Pre-work)    | Rate
---------+-----------+-----------+-----------+--------------+--------------+-----------------
1 Table  | 61.52000x | 61.52000x |           |              |              | 99.90100449%
2 Tables |  9.27400x | 18.54800x |    69.85% |     69.8505% |       57.36% | 99.90099964%
3 Tables |  4.33500x | 13.00500x |    29.88% |     29.8846% |       14.13% | 99.90100885%
4 Tables |  2.74900x | 10.99600x |    15.45% |     15.4479% |        2.37% | 99.90106579%
5 Tables |  1.99450x |  9.97250x |     9.31% |      9.3079% |       -1.40% | 99.90100455%
6 Tables |  1.55950x |  9.35700x |     6.17% |      6.1720% |       -2.78% | 99.90099853%
7 Tables |  1.27810x |  8.94670x |     4.38% |      4.3850% |       -3.28% | 99.90099297%
8 Tables |  1.08180x |  8.65440x |     3.27% |      3.2671% |       -3.41% | 99.90101465%

Also, Sc00bz had a brilliant idea : to calculate the bruteForcePoint. This number is nothing else but how many times a rainbow table is more "efficient" than a bruteforcer. For a "good" rainbow table set, he said that the bruteForcePoint should be between 1,000 and 10,000, the higher, the faster the rainbow table, the better. chainLen shrinks and chainCount grows when bruteForcePoint grows. This means that the table size grows with bFP.

bruteForcePoint = keySpace / (chainLen * (chainLen + 1) / 2 * numTables), numTables = 5 so we can calculate chainLen .

chainLen = (sqrt(bruteForcePoint) * sqrt(numTables) * sqrt(8 * keySpace + bruteForcePoint * numTables) - bruteForcePoint * numTables) / (2 * bruteForcePoint * numTables)

I know, it's a ugly formula, but we have a friend : Wolfram|Alpha. We only need to enter

10000 = 80603140212 / (x * (x + 1) / 2 * 5), we are interested in the positive solution : x~~1795.09, where x is chainLen . And we can aproximate it to 1800.

chainLen = 1800.

The next step is to calculate chainCount. It's easy :

chainCount = tableWorkFactor * keySpace / chainLen . We know tableWorkFactor = 4.48860, keySpace = 80603140212, chainLen = 1800.

chainCount = 200997364.

16bytes/chain => Table size = 3215957824 Bytes ~= 3GiB. 5 tables => 15 GiB, don't forget, we create non-perfect tables !

Actually they are :

perfectSize = non-perfectSize / ((tableWorkFactor / 2) + 1), tableWorkFactor = 4.48860 so

perfectSize = non-perfectSize / 3.2443

perfectSize = 991264008 bytes = 945 MiB.

After indexing, the table size will be ~half the perfect size.

Perfected&indexed table set size ~= 2.3 GiB.

In the end we have the following configuration :

loweralpha-numeric, 1-7, chainLen = 1800, chainCount = 200997364.

Running WinRTGen (oxid.it) on my (slow and old) computer (intel Celeron D @ 3Ghz) I get 3.8 Mhashes/sec, stepSpeed = 820,500 links/sec.

Table precomputation time : 5 days, total precomputation time : 25 days, max cryptanalysis time : 10 sec.

The config will be : 

md5_loweralpha-numeric#1-7_0_1800x200997364_oxid#000.rt
md5_loweralpha-numeric#1-7_1_1800x200997364_oxid#000.rt
md5_loweralpha-numeric#1-7_2_1800x200997364_oxid#000.rt
md5_loweralpha-numeric#1-7_3_1800x200997364_oxid#000.rt
md5_loweralpha-numeric#1-7_4_1800x200997364_oxid#000.rt

-------------------------------------------------------

I also have some specifications.

If chainLen is between 2 and 65,537 we use table index like in the above configuration {0,1,2,3,4}

but if chainLen is higher than 65,537, table index needs to be weird.

Chain Length Range    | Table Indexes
----------------------+--------------------------
        2 -    65,537 | 0,   1,   2,   3,   4 ...
   65,538 -   131,073 | 0,   2,   4,   6,   8 ...
  131,074 -   262,145 | 0,   4,   8,  12,  16 ...
  262,146 -   524,289 | 0,   8,  16,  24,  32 ...
  524,290 - 1,048,577 | 0,  16,  32,  48,  64 ...
1,048,578 - 2,097,153 | 0,  32,  64,  96, 128 ...
2,097,154 - 4,194,305 | 0,  64, 128, 192, 256 ...
4,194,306 - 8,388,609 | 0, 128, 256, 384, 512 ...

Sc00bz sugested that the chainCount should be higher than 200.

The speed of a quad core computer is 3 milion links/sec (3*10^6, that's ~3.5 times faster than mine :)) )

The current [14.10.2009] speed of the Freerainbowtables.com project is 1 - 1.6 bil links/sec (10^9).

tableGenerationTime = keySpace * tableWorkFactor / stepSpeed = chainCount * chainLen / stepSpeed

BarsWF CPU hash speed = 100Mhashes/sec (Core2Duo@3Ghz)

BarsWF CUDA hash speed = 350Mhashes/sec (nVidia 9600GT, Core2Duo@3Ghz)

Examples :

mixalpha-numeric-space, 1-8

bruteforce speed (CPU) = 100Mhashes/sec

bruteforce speed (GPU) = 350Mhashes/sec

stepSpeed (1computer) = 3mil links/sec (3*10^6)

stepSpeed (frt.com) = 1bil links/sec (10^9)

5 perfect tables, success probability = 99.9%

tableWorkFactor = 4.48860

1.

charSetLen = 26+26+10+1 = 63

2.

keySpace = 252158292852480 = 2^47.84

http://www.wolframalpha.com/input/?i=log_2((63*(63^8-1)/(63-1)))

3.

bruteforce time (CPU)= 2521582 sec = 700 h = 30 days (1 MD5 hash)

http://www.wolframalpha.com/input/?i=252158292852480/100000000

bruteforce time (GPU)= 720452 sec = 8.5 days (1 md5 hash)

http://www.wolframalpha.com/input/?i=252158292852480/350000000

4. note :

bFP = bruteForcePoint

np-ts = non-perfect table size (GiB)

np-tss = non-perfect table set size (GiB)

p-ts = perfect table size (GiB)

p-tss = perfect table set size (GiB)

p&i-ts = indexed perfect table size

p&i-tss = indexed perfect set size (GiB)

np-time(CPU) = non-perfect table set generation time on one computer (md5 algo on WinRTGen)

np-time(frt) = non-perfect table set generation time on FreeRainbowTables.com

np-time(GPU) = non-perfect table set generation time on one GPU


   bFP  |    chainLen    |   chainCount    |  np-ts  |  np-tss |  p-ts  | p-tss | p&i-ts | p&i-tss 
--------+----------------+-----------------+---------+---------+--------+-------+--------+----------
   5000 |         142030 |      7969004529 |     119 |     594 |     37 |   184 |     19 |      92 
  10000 |         100430 |     11269916492 |     168 |     840 |     52 |   259 |     26 |     130 
  20000 |          71014 |     15938233493 |     238 |    1187 |     74 |   366 |     37 |     183

np-time(CPU) = 60 years

np-time(GPU) = atm i don't have any benchmarks.

np-time(frt) = 65 days

note : the generation time is about the same for all configurations because keySpace and stepSpeed are constants.

chainLen 

http://www.wolframalpha.com/input/?i=5000=252158292852480/(x*(x+1)/2*5)

chainCount 

http://www.wolframalpha.com/input/?i=4.48860=142030*x/252158292852480

np-ts

http://www.wolframalpha.com/input/?i=7969004529*16/1024/1024/1024

np-tss 

http://www.wolframalpha.com/input/?i=7969004529*16/1024/1024/1024*5

p-ts

http://www.wolframalpha.com/input/?i=7969004529*16/1024/1024/1024/3.2443

p-tss

http://www.wolframalpha.com/input/?i=7969004529*16/1024/1024/1024/3.2443*5

p&i-ts

http://www.wolframalpha.com/input/?i=7969004529*16/1024/1024/1024/3.2443/2

p&i-tss

http://www.wolframalpha.com/input/?i=7969004529*16/1024/1024/1024/3.2443/2*5

5.

Because chainLen is between 131,074 and 262,145 we will have the following index for each table {0,4,8,12,16}

The final configurations :

131074 < 142030 < 262145 => {0,4,8,12,16}

p&i-tss = 92 GiB


hashAlgo_mixalpha-numeric-space#1-8_0_142030x7969004529_oxid#000.rt
hashAlgo_mixalpha-numeric-space#1-8_4_142030x7969004529_oxid#000.rt
hashAlgo_mixalpha-numeric-space#1-8_8_142030x7969004529_oxid#000.rt
hashAlgo_mixalpha-numeric-space#1-8_12_142030x7969004529_oxid#000.rt
hashAlgo_mixalpha-numeric-space#1-8_16_142030x7969004529_oxid#000.rt

65538 < 100430 < 131073 => {0,2,4,6,8}

p&i-tss = 130 GiB


hashAlgo_mixalpha-numeric-space#1-8_0_100430x11269916492_oxid#000.rt
hashAlgo_mixalpha-numeric-space#1-8_2_100430x11269916492_oxid#000.rt
hashAlgo_mixalpha-numeric-space#1-8_4_100430x11269916492_oxid#000.rt
hashAlgo_mixalpha-numeric-space#1-8_6_100430x11269916492_oxid#000.rt
hashAlgo_mixalpha-numeric-space#1-8_8_100430x11269916492_oxid#000.rt

65538 < 71014 < 131073 => {0,2,4,6,8}

p&i-tss = 183 GiB


hashAlgo_mixalpha-numeric-space#1-8_0_71014x15938233493_oxid#000.rt
hashAlgo_mixalpha-numeric-space#1-8_2_71014x15938233493_oxid#000.rt
hashAlgo_mixalpha-numeric-space#1-8_4_71014x15938233493_oxid#000.rt
hashAlgo_mixalpha-numeric-space#1-8_6_71014x15938233493_oxid#000.rt
hashAlgo_mixalpha-numeric-space#1-8_8_71014x15938233493_oxid#000.rt

my first tutorial for FreeRainbowTables.com

_haxxor_

Download it, share it.

source : Free Rainbow Tables | Forum • View topic - [tutorial] How to create a rainbow table set

  • Upvote 1
  • Downvote 2
Link to comment
Share on other sites
begood Newbie

begood

Posted
  • Author
Posted

recapitulam, cat mai pe scurt.

md5 loweralpha-numeric-space 1-8

charSetLen = 37

maxPwLen = 8

keySpace = 3,610,048,327,640 = 2^41.72

keySpace = (charSetLen ^ (maxPwLen + 1) - charSetLen ^ minPwLen) / (charSetLen - 1)

link1

We set bFpoint to 10000, in order to get chainLen.

bFpoint = keySpace / (chainLen * (chainLen + 1) / 2 * numTables)

link2

chainLen = 12,017. We will aprox it to 12,000.

I'm going to create a perfect rainbow table set, perfectTableSuccessRate = 99.9%, 5 perfect tables.

So, according to Sc00bz, tableWorkFactor = 4.48860.

We now can calculate

chainCount = 1,350,338,576.

tableWorkFactor = chainLen * chainCount / keySpace

link3

Using 16 bytes/chain =>

non-perfect tableSize = 20.13 GiB

link4

expectedUniqueChains ~= 416,218,776

expectedUniqueChains ~= chainCount / (tableWorkFactor / 2 + 1)

link5

perfect tableSize ~= 6.20 GiB

link6

indexed perfect tableSize ~= 3.10 GiB

indexed perfect tableSize ~= 1/2 perfect tableSize

non-perfect table set size = 100.65 GiB

perfect table set size = 31 GiB

indexed perfect table set size = 15.5 GiB


md5_loweralpha-numeric-space#1-8_0_12000x1350338576_oxid#000.rt
md5_loweralpha-numeric-space#1-8_1_12000x1350338576_oxid#000.rt
md5_loweralpha-numeric-space#1-8_2_12000x1350338576_oxid#000.rt
md5_loweralpha-numeric-space#1-8_3_12000x1350338576_oxid#000.rt
md5_loweralpha-numeric-space#1-8_4_12000x1350338576_oxid#000.rt

tutorial1_v2 created by _haxxor_ for FreeRainbowTables.com

Feel free to redistribute it, specifying the source (freerainbowtables.com)

Free Rainbow Tables | Forum • View topic - [tutorial] How to create a rainbow table set

  • Upvote 1
Link to comment
Share on other sites
M4T3! Enthusiast

M4T3!

Posted
Posted

Nu sunt rautacios, dar te ai chinuit asa mult ca ai scris in engleza...sau poate si deasta.Scrie in romana sa priceapa toti, eu inteleg, am facut engleza 10 ani, fac si la facultate, dar de ce engleza? Mai da i in pula mea, ca si la facultate cumpar carti scrise de profesori universitari si ce sa vezi? sunt in engleza si mai gasesc cate un termen care nu l inteleg si care strica tot ca nu mai pricep nimic.

Repet, e doar un sfat, nu o lua personal si nici un nume de rau.:)

Link to comment
Share on other sites
begood Newbie

begood

Posted
  • Author
Posted

Suna ciudat sa il scriu in romana + termenii folositi sunt toti explicati in engleza, ar trebui sa ma pun sa explic fiecare termen, ceea ce e foarte mult de lucru.

Oricum, unul care nu stie engleza nu prea are ce intelege, deoarece totul legat de tabele rainbow e in engleza, documentatie etc.

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
Go to topic listing
×
×
  • Create New...