On Fri, 19 Dec 1997, Crispin Cowan wrote:
> changed between guesses. The value is 32 bits. So if you made 4
> billion attacks, you would get it right once with probability
> approaching one, but you are not guaranteed to get it even then.
A minor point but while it might technically approach 1 in the long run,
you aren't dealing with the long run you are dealing with a specific
value. It is a long way from it at 4 billion attacks (or 2^32 attacks).
The value is aproximately 0.63. For all values of n sufficently large (it
gets to down to about .65 at n=10), n independant attempts with a
probability of 1/n yield a overall probability of about 0.63. I
independently discovered this rule of thumb several years ago while
dealing with epidemeological issues.
limit as n approaches infinity of 1-( (1-1/n)^n ) is about 0.63.
Most people tend to think around 1 for such calculations but it
is not the case.
As an aside, anyone who thinks the probability is n*1/n (=1) is wrong.
That is the right answer for the wrong problem (hint, is each guess
independent or not?). This is the correct answer for an exhaustive
search of a stationary target.
Note that the actual calculation for this particular implementation
is slightly more complicated since the canary value does not appear
to change randomly with each function invocation; rather, it appears
that it has a different one of 128 values which, as far as I know,
are never regenerated.
Incidently, the pow() function or printf in glibc seems to take absurd
amounts of CPU time with exponents greater than 1E9.
x= 1 y= 1.000000000
x= 2 y= 0.750000000
x= 3 y= 0.703703704
x= 4 y= 0.683593750
x= 5 y= 0.672320000
x= 6 y= 0.665102023
x= 7 y= 0.660083323
x= 8 y= 0.656391084
x= 9 y= 0.653560584
x= 10 y= 0.651321560
x= 11 y= 0.649506101
x= 12 y= 0.648004372
x= 13 y= 0.646741502
x= 14 y= 0.645664690
x= 15 y= 0.644735634
x= 16 y= 0.643925870
x= 17 y= 0.643213805
x= 18 y= 0.642582763
x= 19 y= 0.642019658
x= 20 y= 0.641514078
x= 30 y= 0.638338487
x= 40 y= 0.636767560
x= 50 y= 0.635830320
x= 60 y= 0.635207689
x= 70 y= 0.634764023
x= 80 y= 0.634431856
x= 90 y= 0.634173848
x= 100 y= 0.633967659
x= 1000 y= 0.632304575
x= 10000 y= 0.632138954
x= 100000 y= 0.632122398
x= 1e+06 y= 0.632120743
x= 1e+07 y= 0.632120577
x= 1e+08 y= 0.632120563
x= 1e+09 y= 0.632120549
Incidently, values for other ratios (between number of tries
and inverse probabilities):
1/4 0.2212
1/2 0..3934
1 0.6321
2 0.8646
4 0.9817
8 0.9997
16 0.99999887
I am not an expert on statistics and I have not tried a symbolic
solution to this problem but I have found the general rule(s) of
thumb to be handy. If anyone cares to derive a proof for this,
by all means send me a copy.
---------------------------------------------------------------------------
--- Mark Whitis <whitis@dbd.com> WWW: http://www.dbd.com/~whitis/ ---
--- 428-B Moseley Drive; Charlottesville, VA 22903 804-962-4268 ---
---------------------------------------------------------------------------