I post this minor statistical correction to bugtraq because many of the readers of this list have frequent occasion to calculate probabilities for security related problems and I have found this rule of thumb to be useful it mental calculations. 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 <whitisat_private> WWW: http://www.dbd.com/~whitis/ --- --- 428-B Moseley Drive; Charlottesville, VA 22903 804-962-4268 --- ---------------------------------------------------------------------------
This archive was generated by hypermail 2b30 : Fri Apr 13 2001 - 13:37:49 PDT