[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

[Zooko Wilcox-O'Hearn]

On Sunday,2009-10-11, at 22:23 , David-Sarah Hopwood wrote:

>> Also pay attention to the "what crypto property do we rely on"  
>> column.  I wouldn't be surprised if SHA-256's collision-resistance  
>> is increasingly called into question in future years.
>
> I agree, but note that you can only create colliding files once you  
> know what attack to use -- unlike preimage attacks where you can  
> target files that were created years ago.

That's a good point, but we can't rely on that too much, because how  
do we know that the first person to discover collisions immediately  
published their results?

Xiaoyun Wang announced how to find collisions in MD5 at the Crypto  
2004 conference, but we don't know for sure that Wang was the first  
person to figure out how to do that.

(As an aside, Wang was a Chinese national working at a Chinese  
university.  Why didn't Chinese military/intelligence keep her  
discovery for themselves?  My assumption is that they never noticed  
until too late.  If they had monopolized that discovery and  
rediscovered Stevens et al. 2009 [1] then they could have had a root  
certificate to the Internet -- something that normally only the USA  
military/intelligence agencies are supposed to have.)

So if someone gives you an immutable file cap built with SHA-256 in  
2010, and then in 2020 a method is published for generating  
collisions in SHA-256, then if you want to be sure that the file is  
not a shape-shifter file you have to cast your mind back to 2010 and  
think to yourself "How sure am I that the generation of this cap  
wasn't performed by someone who knew this trick all along back in  
2010?".  :-)

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!?  But I can't disprove it.  And it sounds a lot less crazy now  
that Wang, Klima et al. have shown how to generate an MD5 collision  
in under a minute on a laptop.

Regards,

Zooko

[1] http://www.win.tue.nl/hashclash/rogue-ca/