Subject: RE: CGA issues

From: "Tuomas Aura" <[email-masked]>
Date: Thu, 20 May 2004 12:12:09 -0700

Iljitsch van Beijnum wrote:
> >> I mean, the chance of getting a SHA-1 with all 0 bits in the lowest
16
> >> bits would be 1 in 65536. But that doesn't automatically mean that
if
> >> you try 65536 times you hit one. Has anyone done the math on this?
> 
> > The median number of iterations is 0.69 * 2^(16*Sec).
> 
> So where is the 99th percentile? Or the 99.99th percentile?

In general, if one wants to find a suitable modifier with probability p,
the number trial required is  n = -ln(1-p) * 2^(16*Sec). For example:
  p=0.5       -->  n = 0.69 * 2^(16^Sec)
  p=0.99      -->  n =  4.6 * 2^(16^Sec) 
  p=0.9999    -->  n =  9.2 * 2^(16^Sec)
  p=0.999999  -->  n = 13.8 * 2^(16^Sec)

Tuomas

--------------------------------------------------------------------
To unsubscribe from this list, send email with "UNSUBSCRIBE" in the
body to <[email-masked]>.
Archive: http://standards.ericsson.net/lists/ietf-send/maillist.html
--------------------------------------------------------------------

---

From: Pekka Nikander <[email-masked]>
Date: Fri, 21 May 2004 17:34:46 +0300

>>>> I mean, the chance of getting a SHA-1 with all 0 bits in
>>>> the lowest 16 bits would be 1 in 65536. But that doesn't
>>>> automatically mean that if you try 65536 times you hit
>>>> one. Has anyone done the math on this?
>>

But that only if you assume that the hash function has the
same properties as a random function, if I understand correctly.
But aren't hash functions "flatter" than random functions?

(Yes, this is an academic question, but I have to admit that
my math is rusty and I'd like to understand this better.)

--Pekka