Re: SHA1 hash safety

From: Theodore Ts'o <tytso@mit.edu>
Date: Apr 18, 2005, 00:09 UTC
Message-ID: <20050418000946.GA7172@thunk.org>
In-Reply-To: <4261E84D.6040208@dwheeler.com>

On Sun, Apr 17, 2005 at 12:38:37AM -0400, David A. Wheeler wrote:

Show 12 quoted lines

> 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