Re: When Will We See Collisions for SHA-1? (An interesting analysis by Bruce Schneier)

[Jeff King <peff@peff.net>]

On Tue, Oct 16, 2012 at 01:58:06PM -0400, Theodore Ts'o wrote:

> I seem to recall that there was at least some discussion at one point
> about adding some extra fields to the commit object in a backwards
> compatible way by adding it after the trailing NUL.  We didn't end up
> doing it, but I could see it being a useful thing nonetheless (for
> example, we could potentially put the backup SHA-2/SHA-3 pointer there).

I don't see much point in it. If we want to add new backup pointers to
commit objects, it is very easy to do so by adding new header fields.

A much bigger problem is the other places we reference sha1s. The
obvious place is trees, which have no room for backup pointers (either
in headers, or with a NUL trick). But it also means that any time you
have a sha1 that you arrive at in some other way than traversal from a
signature, you are vulnerable to attack. E.g., if I record a sha1 in an
external system, today I can be sure that when I fetch the object for
that sha1, it is valid (or I can check that it is valid by hashing it).
With sha1 collisions, I am vulnerable to attack.

> What if we explicitly allow a length plus SHA-2/3 hash of the commit
> plus the fields after the SHA-2/3 hash as an extension?  This would
> allow a secure way of adding an extension, including perhaps adding
> backup SHA-2/3 parent pointers, which is something that would be
> useful to do from a security perspective if we really are worried
> about a catastrophic hash failure.

I'm not sure exactly what you mean. Extended parent pointers make sense,
but I don't see what you mean in your first sentence. It sounds like we
are SHA-2/3 hashing something internal to the object, but that doesn't
help. If the pointers are sha1, then I can always replace the whole
object with a colliding one, even if that object is internally
consistent with respect to sha-2.

> The one reason why we *might* want to use SHA-3, BTW, is that it is a
> radically different design from SHA-1 and SHA-2.  And if there is a
> crypto hash failure which is bad enough that the security of git would
> be affected, there's a chance that the same attack could significantly
> affect SHA-2 as well.  The fact that SHA-3 is fundamentally different
> from a cryptographic design perspective means that an attack that
> impacts SHA-1/SHA-2 will not likely impact SHA-3, and vice versa.

Right. The point of having the SHA-3 contest was that we thought SHA-1's
breakage meant that SHA-2 was going to fall next. But Schneier's
comments before the winners were announced were basically "it turns out
that SHA-2 is not broken like we thought, so there's no reason to ditch
it, and the fact that it is well-studied and well-deployed may mean it's
a good choice".

So I could go either way. This is not a decision we should make today,
though, so we can wait and see which direction the world goes before
picking an algorithm.

-Peff