| Re: SHA-1 and the "birthday paradox" |
|
 |
|
 |
|
 |
|
 |
Group: comp.lang.forth · Group Profile
Author: Alex McDonaldAlex McDonald Date: Jun 6, 2008 14:01
On Jun 6, 5:59 pm, Thomas Pornin bolet.org> wrote:> According to Alex McDonald  rivadpm.com>:
>>>> n=sqrt(-2d*ln(1-p))
>
>> ...specifically that thing you just did. But, poor mathematician that
>> I am, I'm suspicious that it's sqrt(negative).
>
> ln(x) is negative when x < 1. When p is small (which is your situation,
> since you envision p < 0.01), ln(1-p) is approximately equal to -p.
> Which yields the final approximation: n = sqrt(2dp).
>
> Â Â Â Â --Thomas Pornin
Thanks. Simplifies it enormously.
The reason for asking is to try and understand the (admittedly small)
risk of collision when using SHA-1 as a digest, or hash key, for
deduplicating blocks of data. In other words, what is the risk of an
identical SHA-1 digest referring to two distinct blocks rather than a
duplicate?
--
Regards
Alex McDonald
| 
