[tahoe-dev] on discovering that a hash function wasn't secure after all -- was: Re: "Elk Point" design for mutable, add-only, and immutable files

[David-Sarah Hopwood]

Zooko Wilcox-O'Hearn wrote:
[...]
> This is why I think it is useful to use precise terminology when  
> talking about our evolving understanding of secure hash functions.   
> It is tempting to speak loosely and say that MD5 was "secure" until  
> 2004 and then it became "insecure", but that is making assumptions  
> about who knew what in 2003.  To be more precise, you have to say  
> something like "In 2003 no way to generate collisions in MD5 was  
> known to the public.".
> 
> I know a cryptographer who claims to know an ex-KGB man who claims  
> that he could generate preimages of MD5 in 1994.  Sounds crazy  
> right!?

*Preimages*? That does sound crazy. I don't put much weight on
conspiracy theories about how intelligence agencies are supposedly
way ahead of the public state of the art.

OTOH, MD5 should be considered to have been broken for collision
resistance in 1993, when Den Boer and Bosselaers found pseudo-collisions
in the compression function. I don't understand why so many people
dismiss "theoretical" attacks such as pseudo-collisions as unimportant,
when they clearly show that the design goals have not been met.

At the very latest, it was broken in 1996, when actual collisions in
the compression function were found. Since the Merkle-Damgård
construction's proof of security depends on the compression function
being collision-resistant, from that point on there was no reason to
trust the collision resistance of MD5 as a whole.

-- 
David-Sarah Hopwood  ⚥  http://davidsarah.livejournal.com