Re: MD5 and SHA-0 collisions

From: Francois Grieu (fgrieu_at_francenet.fr)
Date: 08/31/04 

Date: Tue, 31 Aug 2004 11:44:07 +0200

"Bill Helem" <gi_j00NOSPAM@hotmail.com> ask:

> What are the operational complexity of these? IIRC for MD5,
> generating a specific collision can be can be done in O(2^128)...
> what are the new numbers?

See
Xiaoyun Wang and Dengguo Feng and Xuejia Lai and Hongbo Yu:
Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD
<http://eprint.iacr.org/2004/199>

In short: minutes for MD5, claimed o(2^40) for SHA-0.

Note that this is to find collision between messages
that differ only by a few bits. If collisions are wanted
between messages with different, arbirary beginning
(a frequent practical case), AFAIK the best attack remains about
o(2^65) for MD5, o(2^81) for SHA-0 and SHA-1.

P.C. van Oorschot and M.J. Wiener:
Parallel Collision Search with Cryptanalytic Applications
Journal of Cryptology, vol. 12, no. 1, 1999
<http://www.scs.carleton.ca/~paulv/papers/JoC97.pdf>
<http://www3.sympatico.ca/wienerfamily/Michael/MichaelPapers/pcs.pdf>

  François Grieu