Optimum number of tables for minimizing the space-time needed to crack a hash with a success rate of 99.9% is 4 tables.
"Optimum success rate" doesn't exist this is something you just pick. This depends on how long you want to spend creating rainbow tables and disk space.
"Optimum time for computing" is basically the same as "optimum success rate" as they are directly related. The only thing you can change that only effects one of them is number of tables and perfect vs non-perfect.
* How do you determine the best number of tables?
As you can see from the data for a 99.9% success rate the best space-time for cracking is 4 tables for either perfect or non-perfect rainbow tables. For perfect rainbow tables you might want to do 5 tables as it takes less than half the time to generate 4 tables.
Perfect Rainbow Tables "99.9%"
Code:
| | | 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%"
Code:
| | | 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%
* How do you determine the best indexes?
It appears that if you bit pack all the data the best index is such that there are about 15 to 30 chains per index, but all you do is increase or decrease the index until you find the smallest total table size. You may want to do a smaller index if you want to load the whole index in memory. Having an index smaller than the optimal by one or two bits indexed will only make the total size a few percent bigger.
* How do you determine the best chain length vs chain count?
What ever feels right. One way to measure how good a table is, is to do "key space / (chain length * (chain length + 1) / 2 * number of tables)" this number should be at least 10000. This number is roughly the point where you should do brute forcing if you have that many hashes. Chain count is found by calculating "work factor * key space / chain length."
Please note that rainbow crack's "chain length" is one higher than the "real chain length."
One last thing perfect rainbow tables are faster since they don't need to check for as many false alarms as non-perfect rainbow tables.
Perfect:
Code:
| | | | | | | Brute | Generation
| | | Chain | Pre- | | | Force | Time (at
Chars | Tables | Chains | Length | Perfect | Perfect | Perfect and Indexed (*) | Point | .5MLink/s)
------+--------+--------+--------+---------+----------+-------------------------+-------+-----------
69 | 4 | 4,829M | 20,000 | 288 GiB | 38.9 GiB | 15.95 GiB (25,33+18=51) | 9,444 | 8,943 Days
69 | 5 | 1,696M | 20,000 | 126 GiB | 38.9 GiB | 15.45 GiB (25,31+18=49) | 7,555 | 3,926 Days
69 | 5 | 1,896M | 17,889 | 141 GiB | 43.5 GiB | 17.20 GiB (25,31+18=49) | 9,444 | 3,926 Days
51 | 4 | 1,672M | 7,000 | 100 GiB | 13.5 GiB | 5.16 GiB (24,31+16=47) | 9,339 | 1,084 Days
51 | 5 | 587M | 7,000 | 44 GiB | 13.5 GiB | 5.08 GiB (23,30+17=47) | 7,471 | 476 Days
51 | 5 | 656M | 6,261 | 49 GiB | 15.1 GiB | 5.66 GiB (23,30+17=47) | 9,339 | 475 Days
* (bits indexed,bits per start point+bits per end point=bits per chain)
Non-Perfect:
Code:
| | | Chain | | Brute Force | Generation Time
Chars | Tables | Chains | Length | Size | Point | (at .5MLink/s)
------+--------+--------+--------+----------+-------------+----------------
69 | 4 | 1,039M | 20,000 | 61.9 GiB | 9,444 | 1,924 Days
51 | 4 | 360M | 7,000 | 21.4 GiB | 9,339 | 233 Days
_haxxor_ wrote:
Btw how did you get 10000 ?
"One way to measure how good a table is, is to do "key space / (chain length * (chain length + 1) / 2 * number of tables)" this number should be at least 10000."
I just picked a number that isn't really low. The higher the number the better as long as the size of the tables are manageable. It's basically so that someone doesn't pick a chain length of 100 or 10,000,000. You should also look at the time it takes to generate the end points when cracking a hash and make sure it is not too high. Also a nice little trick for indexing is to make the number of chains just under 2^n (where n is an integer). This way the tables are slightly more space efficient.
- Sc00bz -
viewtopic.php?p=10958#p10958update 19.08.2010
-------------------
1 : 0.8646462849 Max (rainbow table)
2 : 1-(1-0.8646462849)^2 = 0.98167937181 (miss 1 in 54.58)
3 : 1-(1-0.8646462849)^3 = 0.9975202349 (miss 1 in 403.26)
4 : 1-(1-0.8646462849)^4 = 0.99966435458 (miss 1 in 2979.33)
5 : 1-(1-0.8646462849)^5 = 0.9999545691458 (miss 1 in 22011.62)
6 : 1-(1-0.8646462849)^6 = 0.99999385076511 (miss 1 in 162624.34)
7 : 1-(1-0.8646462849)^7 = 0.99999916767821 (miss 1 in 1201486.78)
8 : 1-(1-0.8646462849)^8 = 0.999999887342154 (miss 1 in 8876718.86)
9 : 1-(1-0.8646462849)^9 = 0.999999984751342 (miss 1 in 65582192.15)
10 : 1-(1-0.8646462849)^10 = 0.99999999793603749 (miss 1 in 484528573.5)
...
n : 1-(1-0.8646462849)^n
Sc00bz wrote:
1epi wrote:
Sc00bz, how did you get 0.8646462849 for one table ?
273/(206+3 sqrt(1338)) ? why ?
Pick pretty much any keySpace
Set chainCount = keySpace
I picked a chainLen of 50000 for that, but it doesn't change much as the chain length goes up.
expectedUniqueChains = euc(chainLen)
euc(1) = chainCount
euc(i) = keySpace * (1 - e ^ (-euc(i - 1) / keySpace))
perfectTableSuccessRate = 1 - (1 - uniqueChains / keySpace) ^ chainLen <--- that's about equal for some reason I'm getting a memory allocation error with that character.
10k: 86.4587076220994%
20k: 86.4622770147352%
50k: 86.4646284852614%
100k: 86.4654875417649%
150k: 86.4657912004252%
200k: 86.4659483369251%
500k: 86.4662457462117%
http://cryptohaze.com/forum/viewtopic.php?p=738#p738