Re: Re: SHA1 hash safety

From: David Lang <dlang@digitalinsight.com>
Date: Apr 16, 2005, 22:56 UTC
Message-ID: <Pine.LNX.4.62.0504161549410.22652@qynat.qvtvafvgr.pbz>
In-Reply-To: <Pine.LNX.4.61.0504161114530.29343@cag.csail.mit.edu>

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

Show 19 quoted lines

> 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