Re: Re: SHA1 hash safety

[David Lang <dlang@digitalinsight.com>]

On Sat, 16 Apr 2005, C. Scott Ananian wrote:

> Date: Sat, 16 Apr 2005 11:36:28 -0400 (EDT)
> From: C. Scott Ananian <cscott@cscott.net>
> To: Petr Baudis <pasky@ucw.cz>
> Cc: omb@bluewin.ch, David Lang <david.lang@digitalinsight.com>,
>     Ingo Molnar <mingo@elte.hu>, git@vger.kernel.org
> Subject: Re: Re: SHA1 hash safety
> 
> On Sat, 16 Apr 2005, Petr Baudis wrote:
>
>>> 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.
>> 
>> http://cryptography.hyperlink.cz/MD5_collisions.html
>
> OK, OK, I spoke too sloppily.  Let me rephrase:
>  It's going to take more than just hearsay to convince me that full
>  128-bit MD5 collisions *IN ARBITRARILY CHOSEN DOCUMENTS* are likely.
>
> I could add, "WITHOUT SPECIAL EFFORT BY AN ATTACKER".

you are missing the point.

I'm not talking about takeing one document (sched.c) and finding a 
replacement that can drop in without being noticed.

what I'm talking about is the chance that somewhere, sometime there will 
be two different documents that end up with the same hash

what git is doing (in very crude sysadminish terms) is to take all the 
files you care about, move them into a new directory where they are named 
by their hash with a symlink that replaces the origional file (and then a 
bunch of stuff to manage multiple versions of those symlinks)

if you are taking every file that you ever care about and loosing all 
refrence to it except by it's hash then when you get a second file that 
has the same hash you loose the contents of one of the two files (race 
condition over which file gets written into the storage directory last)

anywhere else that hashing algorithms are used people realize that there 
will be hash collisions and plan accordingly, however people tend to put 
blinders on when you say SHA1 or MD5 and decide that somehow the same 
thing cannot happen with these types of hashes.

they can, and eventually they will so you need to plan accordingly.

David Lang

-- 
There are two ways of constructing a software design. One way is to make it so simple that there are obviously no deficiencies. And the other way is to make it so complicated that there are no obvious deficiencies.
  -- C.A.R. Hoare