Re: Migrating away from SHA-1?

From: Jeff King <peff@peff.net>
Date: Apr 15, 2016, 02:13 UTC
Message-ID: <20160415021327.GC22112@sigill.intra.peff.net>
In-Reply-To: <20160414224051.GD16656@thunk.org>

On Thu, Apr 14, 2016 at 06:40:51PM -0400, Theodore Ts'o wrote:

> Also, remember that while we can write programs that look for
> suspicious git objects that have stuff hidden after the null
> terminator (in fact, maybe that would be a good thing to add to git,
> hmmm?)[...]

Detecting the hidden bytes is underway elsewhere on the list. And while I think it's a good idea to do so, I don't think it really introduces a meaningful defense against collision attacks.

You can also hide bytes in arbitrary headers in a git object[1], and they will not be shown by default. Adding the extra bytes at the end is certainly easier if you're micro-optimizing the collision process[2], but I don't think it changes the fundamental equation. It reduces the work you do per-sha1 by a constant factor, but not the number of sha1s you expect to compute.

-Peff

[1] Obviously neither "extra headers" nor "stuff after NUL" applies to
    patches sent by email, where everything short of binary-diffs is
    human-readable. So for the kernel, you're really talking about
    attacking a lieutenant whose repo gets pulled. But there are plenty
    of other projects that "git merge" from strangers.

[2] Somewhere in the list archive is my patch to find partial
    collisions like "git commit --sha1=31337", and I did in fact use
    that micro-optimization. That, along with multi-threading, made it
    feasible to do 6-8 character prefixes, as I recall.