Re: Re: SHA1 hash safety

On Sat, 16 Apr 2005, Petr Baudis wrote:

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".

But you're right, I was too busy thrashing around with the basic probability cluestick to carefully distinguish MD5 (in which *collisions* can be found fairly easily now by an attacker, although not *preimages*) and SHA1 (which is what git is actually using, and still requires 2^69 hash computations to collide).

And note again that these are not preimage attacks. Even with MD5, an attacker can't arbitrarily change existing code in the Linux kernel by creating a malicious file with the same MD5 hash.

But extreme caution is necessary, because both of these hash mechanisms have been shown to be weak, and algorithms grow weaker with time, not stronger.

I think the only conclusion that can be made is that "one should not rely 
on the hash for security".  And I don't believe that we are.  We should be
careful to continue saying "branch 46f<mumble> *in Linus' tree*" instead 
of just "branch 46f<mumble>" and assuming that that is unique.  The 
security is provided by Linus' control over his repository, not by the 
hash.
   --scott

[The 'MD5 collisions in 15 minutes on a laptop' paper did surprise me. I vaguely remember hearing about this before, but I'd forgotten just how broken MD5 is. It's still a fine *hash* function; just not a terribly good *cryptographically secure* hash function.]

Israel PBSUCCESS $400 million in gold bullion President Nader jihad 
RNC LPMEDLEY agent HTKEEPER Cheney SEQUIN SARANAC Clinton biowarfare
                          ( http://cscott.net/ )