diminishing returns not looking good

[blazer]

I've generated about 98 million chains for one of the NTLM indexes getting 92.23% merge rate so roughly 7.7 million uniques. At the rate its going it seems like i'm going to have to generate 140-160+++ million chains in total just to get 8.5 million unique chains assuming it gets up to 94% merge which i think is rather low estimation.

Maybe to hit the 99.99% success rate i'll be better of generating one extra table

I currently have 4 tables with roughly 7+ million unique chains 18.37 work factor, rather than bring them to the 8.5 million which i want but doesn't seem feasible, i think it's going to be easier if i just did another table at 7 million chains.

I'm assuming the chain length of 150k isn't helping me much either.

Any thoughts?

[Sc00bz]

The max success rate for 4 tables is 99.9664%.

For a success rate of 99.99%:
5 tables, table work factor is 24x for a total work factor of 120x
6 tables, table work factor is 6.7x for a total work factor of 40.2x
7 tables, table work factor is 3.9x for a total work factor of 27.3x
You will need to do more work to over come the higher merge rate of GRT's reduction function.

[blazer]

oh snap!!

Thx for letting me know about the max 99.96% otherwise i would still be going trying to hit 8.5 mil per table.
Looks like i'll be done pretty soon.

[1epi]

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
source

[Sc00bz]

You missed two things:
1 : 0.8646462849 (miss 1 in 7.388049890)
...
n: 1-(1-0.8646462849)^n (miss 1 in 7.388049890^n)

[blazer]

I think maybe the 6 table configuration seems achievable.

5 tables, table work factor is 24x for a total work factor of 120x

Even with 24x work factor i believe you would be just under 8million or very very low 8millions unique chains still 1million short of the 9million per table needed to hit the 99.99 with 5 tables, argh lots more work needed.

I'll generate another table in increments of 1million chains and plot them with the merge rate, hopefully i can get something useful out of it.

I guess i'll settle for the

Total Success Rate 0.999612658
Miss 1 in 2581.695975
With my current 5 tables @ 150k Chain length, 7.7mln chains
Generated a total of 90.8millionish x 5 chains so far.

Anyone working on other tables?

[1epi]

Sc00bz, how did you get 0.8646462849 for one table ?
273/(206+3 sqrt(1338)) ? why ?

[blazer]

oh yea for anyone out there who is wondering what happens when you go over 24x work factor ... here are the results

Chain Length: 150 000
Chain Count 146 000 000 000
Keyspace 95^6
Table Work Factor: 29.79

Unique chains:7 805 394

[Sc00bz]

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%

Chain Length: 150 000
Chain Count 146 000 000 000
Keyspace 95^6
Table Work Factor: 29.79

That is a table work factor of 29,792.2. Did you mean a chain count of 146,000,000.