Re: ?: SHA1, breaking probabilities

From: Falko Spiller (falkoNOSPAM@ostrakon.de)
Date: 01/17/03 

From: "Falko Spiller" <falkoNOSPAM@ostrakon.de>
Date: Fri, 17 Jan 2003 19:42:06 +0100

hello all again,

many thanks for the answers up to now. but i admit, i still look for answers
of the sort my boss expects me to give. something like:

"The probability of two documents of length n that are distinct in at least
m byte have the probability of 10*E-23 to be the same. [1] (well that must
be a formula of course, containing n and m)

[1] Mike Mayers, Unbreakable Digests, Famos IT Journal XY"

can you give a hint?

regards and thanks again, falko

"Jesper Nordenberg" <megagurka@yahoo.com> schrieb im Newsbeitrag
news:9c838fb.0301170028.6902a121@posting.google.com...
> Jean-Luc Cooke <jlcooke@lager.engsoc.carleton.ca> wrote in message
news:<b06oqn$sv1$2@driftwood.ccs.carleton.ca>...
> > Q1) Given M1 and M2, Prob. that SHA1(M1) == SHA1(M2) is 1/2^160
> > But, if you have M[1], M[2], ..., M[2^64]. There is a 0.5 prob. that
there is an i and j such that SHA1(M[i]) = SHA1(M[j]).
> > And there are way of finding that M[i],M[j] pair without consuming
massive amoutns of memory. See Van Oorschot Crypto '94 paper on parrallel
collision searches. (electronic form found on hims home page)
>
> Another related question: has anyone calculated the distribution of
> SHA-1? For example, if we calculate the digests of all messages of
> length 300 bits, will they be about equally mapped to all 2^160
> possible SHA-1 output messages?
>
> /Jesper Nordenberg

Quantcast