As the title says, I'm trying to compile all the known formulas related to rainbow tables.
key_space = (charset_length*(charset_length^max_password_length-1)/(charset_length-1))
= charset_length^1 + charset_length^2 + ... + charset_length^max_password_length
work_factor = chain_length * chain_count / key_space
bruteforce_point = key_space / (chain_length * (chain_length + 1) / 2 * number_of_tables)
perfect_size = non-perfect_size / ((work_factor_per_table / 2) + 1)
expected_unique_chains *about* = total_chain_count / (work_factor / 2 + 1)
success_rate_per_non-perfect_table = 1 - (1 - expected_unique_chains / key_space) ^ chain_length
seconds_required_to_generate_a_rt = key_space * work_factor / step_speed
success_rate_perfect_rainbow_table = 1 - (1 - no_of_unique_chains / key_space) ^ chain_length
Quote:
P = success rate of a rainbow table
N = number of possible keys
L = length of chain
Co = number of chains
Cmax = max number of unique chains
C = number of unique chains
P = 1 - (1 - C(1) / N) * (1 - C(2) / N) * ... * (1 - C(L) / N)
C(1) = Co
C(2) = N * (1 - e ^ (-C(1) / N))
C(3) = N * (1 - e ^ (-C(2) / N))
C(4) = N * (1 - e ^ (-C(3) / N))
C(5) = N * (1 - e ^ (-C(4) / N))
C(6) = N * (1 - e ^ (-C(4) / N))
...
C(L) = N * (1 - e ^ (-C(L - 1) / N))
Cmax(1) = N
Cmax(2) = N * (1 - e ^ (-Cmax(1) / N))
Cmax(3) = N * (1 - e ^ (-Cmax(2) / N))
...
Cmax(L) = N * (1 - e ^ (-Cmax(L - 1) / N))
----------
key_space - the total number of possible passwords for a given charset_length and max_password_length.
charset_length - character set length
for example :
a-z(loweralpha) = A-Z(upperalpha) = 26 = card{a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z}
0-9(numeric) = 10
perfect_size -
perfect rainbow table size
non-perfect_size - "
original" rainbow table size
chain -
hash chainssuccess_rate_per_non-perfect_table - Success probability of one rainbow table
average step_speed of a quad core = 3 million links per second (3*10^6 links/sec)
average step_speed of the Free Rainbow Tables Super Computer = 1 bil links/second (10^9 links/sec)
work_factor -
Sc00bz wrote:
work_factor is chosen depending on table accuracy wanted. These work factors are found by guess and check and work for most key spaces and chain lengths (small chain lengths like 100 will be off by a little).
http://www.freerainbowtables.com/phpBB3/viewtopic.php?p=10969&f=2#p1096999.9% success probability :
4 Tables =>work_factor per non-perfect_table = 12.78300
5 Tables =>work_factor per non-perfect_table = 4.48860
5 Tables =>work_factor per perfect_table = 1.9945
bruteforce_point >=10000 ;
bruteforce_point -
Sc00bz wrote:
Sc00bz wrote:
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.
.
