Re: SHA1 hash safety

> Date: Sat, 16 Apr 2005 10:58:15 -0400 (EDT)
> From: C. Scott Ananian <cscott@cscott.net>
> To: omb@bluewin.ch
> Cc: David Lang <david.lang@digitalinsight.com>, Ingo Molnar <mingo@elte.hu>,
>     git@vger.kernel.org
> Subject: Re: SHA1 hash safety
> 
> On Sat, 16 Apr 2005, Brian O'Mahoney wrote:
>
>> (1) I _have_ seen real-life collisions with MD5, in the context of
>>    Document management systems containing ~10^6 ms-WORD documents.
>
> Dude!  You could have been *famous*!  Why the aitch-ee-double-hockey-sticks 
> didn't you publish this when you found it?
> Seriously, man.
>
> Even given the known weaknesses in MD5, it would take much more than a 
> million documents to find MD5 collisions.  I can only conclude that the hash 
> was being used incorrectly; most likely truncated (my wild-ass guess would be 
> to 32 bits; a collision is likely with > 50% probability in a million 
> document store for a hash of less than 40 bits).
>
> I know the current state of the art here.  It's going to take more than just 
> hearsay to convince me that full 128-bit MD5 collisions are likely. I believe 
> there are only two or so known to exist so far, and those were found by a 
> research team in China (which, yes, is fairly famous among the cryptographic 
> community now after publishing a paper consisting of little apart from the 
> two collisions themselves).
>
> Please, let's talk about hash collisions responsibly.  I posted earlier about 
> the *actual computed probability* of finding two files with an SHA-1 
> collision before the sun goes supernova.  It's 10^28 to 1 against.
> The recent cryptographic works has shown that there are certain situations 
> where a decent amount of computer work (2^69 operations) can produce two 
> sequences with the same hash, but these sequences are not freely chosen; 
> they've got very specific structure.  This attack does not apply to 
> (effectively) random files sitting in a SCM.
>  http://www.schneier.com/blog/archives/2005/02/sha1_broken.html
>
> That said, Linux's widespread use means that it may not be unimaginable for 
> an attacker to devote this amount of resources to an attack, which would 
> probably involve first committing some specially structured file to the SCM 
> (but would Linus accept it?) and then silently corrupting said file via a 
> SHA1 collision to toggle some bits (which would presumably Do Evil).  Thus 
> hashes other than SHA1 really ought to be considered...
>
> ...but the cryptographic community has not yet come to a conclusion on what 
> the replacement ought to be.  These attacks are so new that we don't really 
> understand what it is about the structure of SHA1 which makes them possible, 
> which makes it hard to determine which other hashes are similarly vulnerable. 
> It will take time.
>
> I believe Linus has already stated on this list that his plan is to 
> eventually provide a tool for bulk migration of an existing SHA1 git 
> repository to a new hash type.   Basically munging through the repository in 
> bulk, replacing all the hashes.  This seems a perfectly adequate strategy at 
> the moment.
> --scott
>
> WASHTUB Panama Minister Moscow explosives KUGOWN hack Marxist LPMEDLEY 
> genetic immediate radar SCRANTON COBRA JANE KGB Shoal Bay atomic Bejing
>                         ( http://cscott.net/ )
>