Re: Migrating away from SHA-1?

[Jeff King <peff@peff.net>]

On Tue, Apr 12, 2016 at 03:38:04PM -0700, H. Peter Anvin wrote:

> For existing repositories we will need to have a migration mechanism. Since
> we can't modify objects without completely invalidating the cryptographic
> properties, what I would suggest is that we leave the existing objects as
> is, with a persistent lookup table from SHA-1 to <new hash>, and have that
> lookup table signed (e.g. GPG) by the person responsible for converting the
> repository.  This freezes the cryptographic status of the existing SHA-1
> objects at the time the conversion happens.  This is a very good reason to
> do this before SHA-1 is actually broken  In contrast. SHA-2 has been
> surprisingly resistant to cryptoanalysis, to the point that SHA-3 was
> motivated by performance and the desire to have a well-tested function based
> on entirely different principles should a generic attack against the common
> structure of MD5/SHA-1/SHA-2 would ever be found.

There are a few threads in the list archive discussing options, if you
search.

A conversion table like you mention seems like a "step 2". I think the
first step is figuring out what the new format looks like, and how
objects refer to each other.

The absolute simplest thing that could work is literally replacing sha1
with a 160-bit truncation of sha-256, telling everybody to convert their
repos, and accepting that existing gpg signatures and external sha1
references are all obsolete. Old versions of git are obsolete, but the
code changes are very minor.

That sucks for a lot of reasons, obviously.

So a slightly nicer thing is to parameterize the algorithm for every
object name reference. So commits look like:

  tree sha256:1234abcd...
  parent sha256:1234abcd...

and so on. Of course trees don't have any space for this; they have a
fixed-length for the hash part of each record, which is basically:

  <mode> <name> NUL <20-byte-sha1>

So we'd probably need a "treev2" object type that gives room for an
algorithm byte (or we'd have to try to shove it into the mode, but since
old versions won't know the new algorithm anyway, I don't think it
solves that much...). Or you can just define for the whole tree object
(either implicit in its type, or in a header) that it always uses
algorithm X.

And then the "new" objects can refer to the older sha1 objects directly
(either via "sha1:1234abcd", or we'd probably define a parameter-less
reference to mean "sha1:"), and that essentially grafts the old history
to the new. You can always walk the old history. And because we're
really talk about collision attacks and not pre-image attacks, it
probably remains fairly trustworthy for chaining (because nobody is
making _new_ objects and referring to them via sha1).

And then if you buy into the collision vs pre-image thing above, there's
not much point in caring about the mapping between sha1 and the new
algorithm. The old ones are set in stone and probably fine. You might
want such a mapping for performance (e.g., so that you can immediately
tell that an old sha-1 tree and a new sha-2 tree have an empty diff,
even though they have different ids), but that's purely a local thing.

So perhaps you were thinking of something in between, or an alternative
plan altogether.  I haven't been able to think of a scheme that is
secure, convenient, and involves less work than the one above.

Transitioning to that would be something like:

  0. Overhaul all of the git code to handle arbitrary-sized object ids.

  1. Decide on the new algorithm and implement it in git.

  2. Recognize parameterized object ids in commits and tags (designing
     format, implementing the reading side).

  3. Recognize parameterized object ids somehow in trees (designing
     format, implementing the reading side).

  4. Teach the object database to index objects by the new algorithm (or
     possibly both algorithms).

  5. Add a protocol extension so that both sides can decide which
     algorithm is being used when they talk about oids.

  6. Add a config option to write references in objects using the new
     algorithm.

  7. After a while, flip the config option on. Hopefully the readers
     from steps 1-5 have percolated to the masses by then, and it's not
     a horrible flag day.

We're basically on step 0 right now. I'm sure I'm missing some
subtleties in there, too.

Things get simpler if you don't fully parameterize (e.g., just assume
everything is moved to the new algorithm, and provide a "legacy" parent
pointer for connecting to sha1 history). But part of this would be
future-proofing for a day when sha-2 fails.

-Peff