Re: SHA1 collisions found

From: Jeff King <peff@peff.net>
Date: Feb 23, 2017, 19:32 UTC
Message-ID: <20170223193210.munuqcjltwbrdy22@sigill.intra.peff.net>
In-Reply-To: <CA+55aFx=0EVfSG2iEKKa78g3hFN_yZ+L_FRm4R749nNAmTGO9w@mail.gmail.com>

On Thu, Feb 23, 2017 at 11:09:32AM -0800, Linus Torvalds wrote:

Show 13 quoted lines

> On Thu, Feb 23, 2017 at 10:46 AM, Jeff King <peff@peff.net> wrote:
> >>
> >> So I agree with you that we need to make git check for the opaque
> >> data. I think I was the one who brought that whole argument up.
> >
> > We do already.
> 
> I'm aware of the fsck checks, but I have to admit I wasn't aware of
> 'transfer.fsckobjects'. I should turn that on myself.
> 
> Or maybe git should just turn it on by default? At least the
> per-object fsck costs should be essentially free compared to the
> network costs when you just apply them to the incoming objects.

Yeah, they're not expensive. We've discussed enabling them by default. The sticking point is that there is old history with minor bugs which triggers some warnings (e.g., malformed committer names), and it would be annoying to start rejecting that unconditionally.

So I think we would need a good review of what is a "warning" versus an "error", and to only reject on errors (right now the NUL thing is a warning, and it should probably upgraded).

Show 9 quoted lines

> And in particular, while the *kernel* doesn't generally have critical
> opaque blobs, other projects do. Things like firmware images etc are
> open to attack, and crazy people put ISO images in repositories etc.
> 
> So I don't think this discussion should focus exclusively on the git metadata.
> 
> It is likely much easier to replace a binary blob than it is to
> replace a commit or tree (or a source file that has to go through a
> compiler). And for many projects, that would be a bad thing.

Yes, I'd agree we need to consider both. And no matter what Git does in its own data formats, blobs will always be a sequence of bytes. Hiding collision-cruft in them isn't up to us, but rather the data format.

The nice thing about a blob collision, though, is that you can only replace the opaque files, not, say, C source code. That doesn't make it a non-issue, but it reduces the scope of an attack.

Replacing a commit or tree wholesale means the attacker has a lot more flexibility. So to whatever degree we can make that harder (like complaining of commits with NULs), the better.

Show 7 quoted lines

> > It's not an identical prefix, but I think collision attacks generally
> > are along the lines of selecting two prefixes followed by garbage, and
> > then mutating the garbage on both sides. That would "work" in this case
> > (modulo the fact that git would complain about the NUL).
> 
> I think this particular attack depended on an actual identical prefix,
> but I didn't go back to the paper and check.

The paper describes the content as:

  SHA-1(P | M1 | M2 | S)

and they replace both "M1" and "M2", with a near-collision for the first, and then the final collision for the second. What's not clear to me is if part of M1 can be chosen, or if it's perturbed fully into random garbage.

Show 9 quoted lines

> But the attacks tend to very much depend on particular input bit
> patterns that have very particular effects on the resulting
> intermediate hash, and those bit patterns are specific to the hash and
> known.
> 
> So a very powerful defense is to just look for those bit patterns in
> the objects, and just warn about them. Those patterns don't tend to
> exist in normal inputs anyway, but particularly if you just warn, it's
> a heads-ups that "ok, something iffy is going on"

Yes, that would be a wonderful hardening to put into Git if we know what those patterns look like. That part isn't clear to me.

> The whole _point_ of an SCM is that it isn't about a one-time event,
> but about continuous history. That also fundamentally means that a
> successful attack needs to work over time, and not be detectable.

Yeah, I'd certainly agree with that. You spend loads of money to generate a collision, there's a reasonably high chance of detection, and then as soon as one person detects it, your investment is lost.

According to the paper, the current cost of the computation for a single collision is ~$670K.

At least for now, an attacker is much better off using that money to break into your house and install a keylogger.

-Peff