begood Posted October 14, 2009 Report Posted October 14, 2009 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 : frt2ns9The 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-numericcharSetLen = 36maxPwLen = 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 SuccessTables | Table | Work | Previous | Length) | Pre-work) | Rate---------+-----------+-----------+-----------+--------------+--------------+-----------------1 Tables | N/A | N/A | | | | 86.46462849% Max2 Tables | N/A | N/A | | | | 98.16793718% Max3 Tables | N/A | N/A | | | | 99.75202349% Max4 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 SuccessTables | 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 enter10000 = 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 soperfectSize = non-perfectSize / 3.2443perfectSize = 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.rtmd5_loweralpha-numeric#1-7_1_1800x200997364_oxid#000.rtmd5_loweralpha-numeric#1-7_2_1800x200997364_oxid#000.rtmd5_loweralpha-numeric#1-7_3_1800x200997364_oxid#000.rtmd5_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 / stepSpeedBarsWF CPU hash speed = 100Mhashes/sec (Core2Duo@3Ghz)BarsWF CUDA hash speed = 350Mhashes/sec (nVidia 9600GT, Core2Duo@3Ghz)Examples : mixalpha-numeric-space, 1-8bruteforce speed (CPU) = 100Mhashes/secbruteforce speed (GPU) = 350Mhashes/secstepSpeed (1computer) = 3mil links/sec (3*10^6)stepSpeed (frt.com) = 1bil links/sec (10^9)5 perfect tables, success probability = 99.9%tableWorkFactor = 4.488601. charSetLen = 26+26+10+1 = 632. keySpace = 252158292852480 = 2^47.84http://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/100000000bruteforce time (GPU)= 720452 sec = 8.5 days (1 md5 hash)http://www.wolframalpha.com/input/?i=252158292852480/3500000004. note : bFP = bruteForcePointnp-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 sizep&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.comnp-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 yearsnp-time(GPU) = atm i don't have any benchmarks.np-time(frt) = 65 daysnote : 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/252158292852480np-tshttp://www.wolframalpha.com/input/?i=7969004529*16/1024/1024/1024np-tss http://www.wolframalpha.com/input/?i=7969004529*16/1024/1024/1024*5p-tshttp://www.wolframalpha.com/input/?i=7969004529*16/1024/1024/1024/3.2443p-tsshttp://www.wolframalpha.com/input/?i=7969004529*16/1024/1024/1024/3.2443*5p&i-tshttp://www.wolframalpha.com/input/?i=7969004529*16/1024/1024/1024/3.2443/2p&i-tsshttp://www.wolframalpha.com/input/?i=7969004529*16/1024/1024/1024/3.2443/2*55. 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 GiBhashAlgo_mixalpha-numeric-space#1-8_0_142030x7969004529_oxid#000.rthashAlgo_mixalpha-numeric-space#1-8_4_142030x7969004529_oxid#000.rthashAlgo_mixalpha-numeric-space#1-8_8_142030x7969004529_oxid#000.rthashAlgo_mixalpha-numeric-space#1-8_12_142030x7969004529_oxid#000.rthashAlgo_mixalpha-numeric-space#1-8_16_142030x7969004529_oxid#000.rt65538 < 100430 < 131073 => {0,2,4,6,8}p&i-tss = 130 GiBhashAlgo_mixalpha-numeric-space#1-8_0_100430x11269916492_oxid#000.rthashAlgo_mixalpha-numeric-space#1-8_2_100430x11269916492_oxid#000.rthashAlgo_mixalpha-numeric-space#1-8_4_100430x11269916492_oxid#000.rthashAlgo_mixalpha-numeric-space#1-8_6_100430x11269916492_oxid#000.rthashAlgo_mixalpha-numeric-space#1-8_8_100430x11269916492_oxid#000.rt65538 < 71014 < 131073 => {0,2,4,6,8}p&i-tss = 183 GiBhashAlgo_mixalpha-numeric-space#1-8_0_71014x15938233493_oxid#000.rthashAlgo_mixalpha-numeric-space#1-8_2_71014x15938233493_oxid#000.rthashAlgo_mixalpha-numeric-space#1-8_4_71014x15938233493_oxid#000.rthashAlgo_mixalpha-numeric-space#1-8_6_71014x15938233493_oxid#000.rthashAlgo_mixalpha-numeric-space#1-8_8_71014x15938233493_oxid#000.rtmy 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 1 2 Quote
Fitty Posted October 14, 2009 Report Posted October 14, 2009 Foarte bine facut, super tare Felicitari, begood. Quote
begood Posted October 14, 2009 Author Report Posted October 14, 2009 Foarte bine facut, super tare Felicitari, begood.Il mai completez pe masura ce imi vin idei, am lucrat vreo 5 ore la el. 1 Quote
Guest Praetorian Posted October 14, 2009 Report Posted October 14, 2009 Poate vin si eu cu ala al meu.. am si uitat de el. Adu-mi aminte, ca sa mai continui, si sa ma ajuti si pe mine, pe unde nu mai stiu.Bravo. Quote
begood Posted November 10, 2009 Author Report Posted November 10, 2009 recapitulam, cat mai pe scurt.md5 loweralpha-numeric-space 1-8charSetLen = 37maxPwLen = 8keySpace = 3,610,048,327,640 = 2^41.72keySpace = (charSetLen ^ (maxPwLen + 1) - charSetLen ^ minPwLen) / (charSetLen - 1)link1We set bFpoint to 10000, in order to get chainLen.bFpoint = keySpace / (chainLen * (chainLen + 1) / 2 * numTables)link2chainLen = 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 / keySpacelink3Using 16 bytes/chain => non-perfect tableSize = 20.13 GiBlink4expectedUniqueChains ~= 416,218,776 expectedUniqueChains ~= chainCount / (tableWorkFactor / 2 + 1)link5perfect tableSize ~= 6.20 GiBlink6indexed perfect tableSize ~= 3.10 GiBindexed perfect tableSize ~= 1/2 perfect tableSize non-perfect table set size = 100.65 GiBperfect table set size = 31 GiBindexed perfect table set size = 15.5 GiBmd5_loweralpha-numeric-space#1-8_0_12000x1350338576_oxid#000.rtmd5_loweralpha-numeric-space#1-8_1_12000x1350338576_oxid#000.rtmd5_loweralpha-numeric-space#1-8_2_12000x1350338576_oxid#000.rtmd5_loweralpha-numeric-space#1-8_3_12000x1350338576_oxid#000.rtmd5_loweralpha-numeric-space#1-8_4_12000x1350338576_oxid#000.rttutorial1_v2 created by _haxxor_ for FreeRainbowTables.comFeel free to redistribute it, specifying the source (freerainbowtables.com)Free Rainbow Tables | Forum • View topic - [tutorial] How to create a rainbow table set 1 Quote
M4T3! Posted November 11, 2009 Report Posted November 11, 2009 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. Quote
begood Posted November 11, 2009 Author Report Posted November 11, 2009 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. Quote
