Re: How safe are signed git tags? Only as safe as SHA-1 or somehow safer?

From: Jeff King <peff@peff.net>
Date: Nov 22, 2014, 19:43 UTC
Message-ID: <20141122194313.GB13340@peff.net>
In-Reply-To: <546FC446.50101@whonix.org>

On Fri, Nov 21, 2014 at 11:01:26PM +0000, Patrick Schleizer wrote:

Show 5 quoted lines

> > Yes, it is only as "safe as SHA-1" in the sense that you have GPG-signed
> > only a SHA-1 hash. If somebody can find a collision with a hash you have
> > signed, they can substitute the colliding data for the data you signed.
> [..]
> Sounds pretty sad. Isn't this a security issue that should be fixed?

Sure, for some definition of "should". It's not a problem today. It may be a problem in the future. If we were designing git from scratch today, it would probably make sense to use a different hash, or to somehow parameterize the hash.

But we're not starting from scratch. A change like that needs to consider a transition plan. What happens to the existing history? Do we just rewrite it all using the new hash in all object references? If so, what do we do with non-object references to sha1s (in external systems, or even partial sha1s mentioned in commit message)? What do we do with signed tags which are now invalid? Or do we graft history with the new hashes onto the old, letting the two coexist in the same repository? How do we expand the data structures to handle the extra information needed to specify the hash type?

None of these problems is insurmountable, but it's going to take real work on the development side, and is going to create incompatibilities and headaches on the user side. It's probably something we'll need to deal with in the next 10-15 years, but nobody knows quite when.

If you'd like to start working on it, I'd be happy to review your patches. :) But in the meantime, I don't know that anybody considers it an extremely high priority to work on, versus other fixes and features.

> Rather than discussing how feasible collisions in SHA-1 are... Attacks
> on SHA-1 are only getting worse, no?

Actually, not really. I do not keep up terribly well with the academic literature, but I don't think that attacks have gotten any worse in the last few years. Computers _are_ getting faster, though, so a number like 2^61 (which is what Wikipedia claims as the best widely accepted value for producing a collision) gets more and more feasible as time passes.

Of course, we might find worse attacks (or if you want to put on your tinfoil hat, perhaps certain government organizations already have and are keeping them secret). 2^61 is a best case.

Show 10 quoted lines

> > And of course there is the question of getting the colliding data to the
> > victim. Git does collision checks whenever a remote (e.g., from a "git
> > fetch") gives us data that we already have. So you could poison new
> > cloners with bad data, but you could not convince a repository with the
> > existing "good" half of the collision to fetch the "evil" half.
> 
> Poison git cloners with bad data is exactly my point here. Because
> sometimes I am a cloner of my own code - cloning it on a separate
> machine - then verify it using gpg - but don't check it any further. In
> such cases, I'd prefer if security wouldn't depend on SHA-1.

I agree that cloners are an important category of users to clone. But it also means that a single fetcher can detect tampering quite easily. Think about it this way: let's say the Walker/Schneier estimate is right, and in 2021 it will cost ~$43K to find a collision. You spend the money, find a collision on some binary blob that's in the kernel, convince Linus to accept your "good" version, he signs, and then you hack into kernel.org and replace the blob with your evil version. Now the first time somebody fetches the evil version, their git complains about the collision, kernel.org admins investigate, and the problem is fixed. There's some damage, but ultimately you didn't accomplish much.

Or you could spend that $43K hiring somebody to break into Linus's house and manipulate the local copy of the kernel on his computer that he's going to sign. Or buy a zero-day exploit for his browser that gives you remote code execution on his workstation.

Don't get me wrong. I think moving away from SHA-1 is a good idea, and something we're going to want to do for security reasons eventually. But we're definitely not at the point of "well, all of our signatures are worthless now", and I'm not sure we'll be there sooner than a decade from now.

-Peff