Birthday attack

[Graham]

On Friday 11 Oct 2002 8:10 am, John R T Brazier wrote:

> Some more details here
> http://www.rsasecurity.com/rsalabs/faq/2-4-6.html

Maybe this will also help (sorry for the long quote):

=46rom http://www.zi0n.info/information/pgp.htm:

What Is a Fingerprint ?

A fingerprint is a large number (MD5 uses 39 decimal digits) which fits
to a message unambiguously. The fingerprint is computed by a
one-way-function from the characters of the message, ensuring that
changing a single bit within the message would produce a totally
different result. In this way even a minimal change of the message could
be detected reliably. Because of the fact the hashfunction is
irreversible there is no way of reconstructing the message from the
fingerprint. It is practically impossible as well to design a new
message (as a forgery) in a way, that it computes the same fingerprint
as the original message, because there are 1038 different hashvalues (or
fingerprints) and the one which is generated with the new message is
inpredictable.

Of course it is possible that some other text will accidentally produce
the same hashvalue because even if the number of different hashvalues is
very large, it is also limited. But such a collision could not be
constructed intentionally because you have to try about 1038 variations
to find one. The one-way-function does not give any clue for an
appropriate choice of the forgery and the possibility to get the same
hashvalue from any two different texts is only:
0.000 000 000 000 000 000 000 000 000 000 000 000 029 percent (1/2128).

The Birthday-Attack on MD5

How many people are required to make the possibility for two of them
having their birthday on the same day reach 50 percent ?
The wrong answer is: 365/2 =3D 182 people.
Actually you only need 23 people which is far less than expected, and
transferred to forging a digital signature, the forger can benefit from
this situation considerably. If she does not intend to forge a certain
document but rather confines herself to submit a document for signing by
the potential victim and she has already found a forged document with
the same MD5-fingerprint, forging someone's digital signature is
possible, using such a "suitable pair of documents" (benign and
malicious document).

The number of pairs of documents she has to check until she will
certainly find one working pair is no longer 2127 (170 141 183 460 469
231 731 687 303 715 884 105 728), "but merely" 264 (18 446 744 073 709
551 616) that is 1019 pairs of documents. Finding a working pair of
documents still is "bloody lotta work", but can not be considered as
impossible (see my argumentation concerning the brute-force-attack on
IDEA-keys).

Proof
With N different documents (benign and malicious all in all) there are
N(N-1)/2 pairs. Given that there are K =3D 2128 different hashvalues the
probability of two different documents sharing the same hashvalue is
1/K. To be on the safe side one must try at least half of N2 pairs of
documents, for if the probability for a collision should be 50 percent,
264 pairs of documents will be sufficient.

(N2 * 1/K) / 2 =3D 0,5
N =3D sqrt(K) =3D 264.
Among those 18 446 744 073 709 551 616 different pairs one will probably
be suitable for forging a digital signature.

RESULT

Using sufficient long keys an attack on cryptographic methods used by
PGP is practically pointless. This "theoretical security" has to be
evaluated with respect to current results of cryptographic research.

--=20

Graham