Re: SHA1 hash safety

[Theodore Ts'o <tytso@mit.edu>]

On Sun, Apr 17, 2005 at 12:38:37AM -0400, David A. Wheeler wrote:
> The probability of an accidental overlap for SHA-1 for two
> different files is absurdly remote; it's just not worth worrying about.
> 
> However, the possibility of an INTENTIONAL overlap is a completely
> different matter.  I think the hash algorithm should change in the
> future; I have a proposal below.
> 
> Someone has ALREADY broken into a server to modify the Linux kernel
> code already, so the idea of an attack on kernel code
> is not an idle fantasy. MD5 is dead, and SHA-1's work factor has
> already been sufficiently broken that people have already been told
> "walk to the exits" (i.e., DO NOT USE SHA-1 for new programs like git).

We're very clearly going to need a FAQ for git.

SHA-1's work factor has been decreased to 2**69 from 2**80 for
generating two messages that have the same hash value, WHERE THE HASH
VALUE AND THE MESSAGES ARE NOT UNDER THE ATTACKER'S CONTROL.  This is
not the same as a pre-image attack, where given a message M1 which
hashes to value H, the attacker can find another message M2 which also
hashes to value H.  In even if the attacker can do this, the result
has to have valid git metadata format, and also be valid C code.

So the the recent result which has weakened (but not broken) SHA-1's
use in digital signatures, and which has resulted in the advice to
"walk not run" for the exits, do not apply to git.

Can we guarantee that there won't be further innovations that may
break SHA-1?  Of course not.  But an attacker who wants to introduced
a trojan into the Linux kernel would have a much easier time doing a
"black bag job" --- i.e., breaking into Linus's house in Portland, and
then inserting a buggered patch into his master source tree.

If you're going to be a professional paranoid, it's best to worry
about the realistic attacks before stressing out over the unrealistic
ones.

						- Ted