Re: SHA1 collisions found

Ian Jackson [off-list ref] writes:

I have been thinking about how to do a transition from SHA1 to another
hash function.

Good.  I think many of us have also been, too, not necessarily just
in the past few days in response to shattered, but over the last 10
years, yet without coming to a consensus design ;-)

I have concluded that:

 * We can should avoid expecting everyone to rewrite all their
   history.

Yes.

 * Unfortunately, because the data formats (particularly, the commit
   header) are not in practice extensible (because of the way existing
   code parses them), it is not useful to try generate new data (new
   commits etc.) containing both new hashes and old hashes: old
   clients will mishandle the new data.

Yes.

 * Therefore the transition needs to be done by giving every object
   two names (old and new hash function).  Objects may refer to each
   other by either name, but must pick one.  The usual shape of

I do not think it is necessrily so.  Existing code may not be able
to read anything new, but you can make the new code understand
object names in both formats, and for a smooth transition, I think
the new code needs to.

For example, a new commit that records a merge of an old and a new
commit whose resulting tree happens to be the same as the tree of
the old commit may begin like so:

    tree 21b97d4c4f968d1335f16292f954dfdbb91353f0
    parent 20769079d22a9f8010232bdf6131918c33a1bf6910232bdf6131918c33a1bf69
    parent 22af6fef9b6538c9e87e147a920be9509acf1ddd

naming the only object whose name was done with new hash with the
new longer hash, while recording the names of the other existing
objects with SHA-1.  We would need to extend the object format for
tag (which would be trivial as the object reference is textual and
similar to a commit) and tree (much harder), of course.

As long as the reader can tell from the format of object names
stored in the "new object format" object from what era is being
referred to in some way [*1*], we can name new objects with only new
hash, I would think.  "new refers only to new" that stratifies
objects into older and newer may make things simpler, but I am not
convinced yet that it would give our users a smooth enough
transition path (but I am open to be educated and pursuaded the
other way).


[Footnote]

*1* In the above toy example, length being 40 vs 64 is used as a
    sign between SHA-1 and the new hash, and careful readers may
    wonder if we should use sha-3,20769079d22... or something like
    that that more explicity identifies what hash is used, so that
    we can pick a hash whose length is 64 when we transition again.

    I personally do not think such a prefix is necessary during the
    first transition; we will likely to adopt a new hash again, and
    at that point that third one can have a prefix to differenciate
    it from the second one.

On Fri, 24 Feb 2017, Junio C Hamano wrote:

*1* In the above toy example, length being 40 vs 64 is used as a
   sign between SHA-1 and the new hash, and careful readers may
   wonder if we should use sha-3,20769079d22... or something like
   that that more explicity identifies what hash is used, so that
   we can pick a hash whose length is 64 when we transition again.

   I personally do not think such a prefix is necessary during the
   first transition; we will likely to adopt a new hash again, and
   at that point that third one can have a prefix to differenciate
   it from the second one.

as the saying goes "in computer science the interesting numbers are 0, 1, and 
many", does it really simplify things much to support 2 hashes vs supporting 
more so that this issue doesn't have to be revisited? (other than selecting new 
hashes over time)

David Lang

On Fri, Feb 24, 2017 at 09:32:13AM -0800, Junio C Hamano wrote:

quoted

 * Therefore the transition needs to be done by giving every object
   two names (old and new hash function).  Objects may refer to each
   other by either name, but must pick one.  The usual shape of

I do not think it is necessrily so.  Existing code may not be able
to read anything new, but you can make the new code understand
object names in both formats, and for a smooth transition, I think
the new code needs to.

For example, a new commit that records a merge of an old and a new
commit whose resulting tree happens to be the same as the tree of
the old commit may begin like so:

    tree 21b97d4c4f968d1335f16292f954dfdbb91353f0
    parent 20769079d22a9f8010232bdf6131918c33a1bf6910232bdf6131918c33a1bf69
    parent 22af6fef9b6538c9e87e147a920be9509acf1ddd

naming the only object whose name was done with new hash with the
new longer hash, while recording the names of the other existing
objects with SHA-1.  We would need to extend the object format for
tag (which would be trivial as the object reference is textual and
similar to a commit) and tree (much harder), of course.

One thing I worry about in a mixed-hash setting is how often the two
will be mixed. That will lead to interoperability complications, but I
also think it creates security hazards (if I can convince you somehow to
refer to my evil colliding file by its sha1, for example, then I can
subvert the strength of the new hash).

So I'd much rather see strong rules like:

  1. Once a repo has flag-day switched over to the new hash format[1],
     new references are _always_ done with the new hash. Even ones that
     point to pre-flag-day objects!

     So you get a "commit-v2" object instead of a "commit", and it has a
     distinct hash identity from its "commit" counterpart. You can point
     to a classic "commit", but you do so by its new-hash.

     The flag-day switch would probably be a repo config flag based on
     repositoryformatversion (so old versions would just punt if they
     see it). Let's call this flag "newhash" for lack of a better term.

  2. Repos that have new-hash set will consider the new hash
     format as primary, and always use it when writing and referring to
     new objects (e.g., in refs). A (purely local) sha1->new mapping can
     be maintained for doing old-style object lookups, or for quick
     equivalence checks (this mapping might need to be bi-directional
     for some use cases; I haven't thought hard enough about it to say
     either way).

  3. For protocol interop, the rules would be something like[2]:

      a. If upload-pack is serving a newhash repo, it advertises
         so in the capabilities.

	 Recent clients know that the rest of the conversation will
	 involve the new hash format. If they're cloning, they set the
	 newhash flag in their local config.  If they're fetching, they
	 probably abort and say "please enable newhash" (because for an
	 existing repo, it probably needs to migrate refs, for example).

	 An old client would fail to send back the newhash capability,
	 and the server would abort the conversation at that point.

	 A new upload-pack serving a non-newhash repo behaves the same
	 as now (use sha1, happily interoperate with existing and new
	 clients).

      b. receive-pack is more or less the mirror image.

         A server for a newhash-flagged repo has a capability for "this
	 is a newhash repo" and advertises newhash refs. An existing
	 client might still try to push, but the server would reject it
	 unless it advertises "newhash" back to the server.

	 A newhash-enabled client on a non-newhash repo would abort more
	 gracefully ("please upgrade your local repo to newhash").

	 For a newhash-enabled server with a non-newhash repo, it would
	 probably not advertise anything (not even "I understand
	 newhash"). Because the process for converting to newhash is not
	 "just push some newhash objects", but an out-of-band flag-day
	 to convert it over.

That's just a sketch I came up with. There are probably holes. And it
definitely leaves a lot of _possible_ interoperability on the table in
favor of the flag-day approach. But I think the flag-day approach is a
lot easier to reason about. Both in the code, and in terms of the
security properties.

-Peff

[1] I was intentionally vague on "new hash format" here. Obviously there
    are various contenders like SHA-256. But I think there's also an
    open question of whether the new format should be a multi-hash
    format. That would ease further transitions. At the same time, we
    really _don't_ want people picking bespoke hashes for their
    repositories. It creates complications in the code, and it destroys
    a bunch of optimizations (like knowing when we are both talking
    about the same object based on the hash).

    So I am torn between "move to SHA-256 (or whatever)" and "move to a
    hash format that encodes the hash-type in the first byte, but refuse
    to allocate more than one hash for now".

[2] If we're having a flag-day event, this _might_ be time to consider
    some of the breaking protocol changes that have been under
    discussion.  I'm really hesitant to complicate this already-tricky
    issue by throwing in the kitchen sink. But if there's going to be a
    flag day where you need to upgrade Git to access certain repos, it
    might be nice if there's only one. I dunno.

Junio C Hamano writes ("Re: SHA1 collisions found"):

Ian Jackson [off-list ref] writes:

quoted

 * Therefore the transition needs to be done by giving every object
   two names (old and new hash function).  Objects may refer to each
   other by either name, but must pick one.  The usual shape of

I do not think it is necessrily so.

Indeed.  And my latest thoughts involve instead having two parallel
systems of old and new objects.

*1* In the above toy example, length being 40 vs 64 is used as a
    sign between SHA-1 and the new hash, and careful readers may
    wonder if we should use sha-3,20769079d22... or something like
    that that more explicity identifies what hash is used, so that
    we can pick a hash whose length is 64 when we transition again.

I have an idea for this.  I think we should prefix new hashes with a
single uppercase letter, probably H.

Uppercase because: case-only-distinguished ref names are already
discouraged because they do not work properly on case-insensitive
filesystems; convention is that ref names are lowercase; so an
uppercase letter probably won't appear at the start of a ref name
component even though almost all existing software will treat it as
legal.  So the result is that the new object names are unlikely to
collide with ref names.

(There is of course no need to store the H as a literal in filenames,
so the case-insensitive filesystem problem does not apply to ref
names.)

We should definitely not introduce new punctuation into object names.
That will cause a great deal of grief for existing software which has
to handle git object names and may thy to store them in
representations which assume that they match \w+.

The idea of using the length is a neat trick, but it cannot support
the dcurrent object name abbreviation approach unworkable.

Ian.

Ian Jackson writes ("Re: SHA1 collisions found"):

The idea of using the length is a neat trick, but it cannot support
the dcurrent object name abbreviation approach unworkable.

Sorry, it's late here and my grammar seems to have disintegrated !

Ian.

On Fri, Feb 24, 2017 at 3:39 PM, Jeff King [off-list ref] wrote:

One thing I worry about in a mixed-hash setting is how often the two
will be mixed.

Honestly, I think that a primary goal for a new hash implementation
absolutely needs to be to minimize mixing.

Not for security issues, but because of combinatorics. You want to
have a model that basically reads old data, but that very aggressively
approaches "new data only" in order to avoid the situation where you
have basically the exact same tree state, just _represented_
differently.

For example, what I would suggest the rules be is something like this:

 - introduce new tag2/commit2/tree2/blob2 object type tags that imply
that they were hashed using the new hash

 - an old type obviously can never contain a pointer to a new type (ie
you can't have a "tree" object that contains a tree2 object or a blob2
object.

 - but also make the rule that a *new* type can never contain a
pointer to an old type, with the *very* specific exception that a
commit2 can have a parent that is of type "commit".

That way everything "converges" towards the new format: the only way
you can stay on the old format is if you only have old-format objects,
and once you have a new-format object all your objects are going to be
new format - except for the history.

Obviously, if somebody stays in old format, you might end up still
getting some object duplication when you continue to merge from him,
but that tree can never merge back without converting to new-format,
so it will be a temporary situation.

So you will end up with duplicate objects, and that's not good (think
of what it does to all our full-tree "diff" optimizations, for example
- you no longer get the "these sub-trees are identical" across a
format change), but realistically you'll have a very limited time of
that kind of duplication.

I'd furthermore suggest that from a UI standpoint, we'd

 - convert to 64-character hex numbers (32-byte hashes)

 - (as mentioned earlier) default to a 40-character abbreviation

 - make the old 40-character SHA1's just show up within the same
address space (so they'd also be encoded as 32-byte hashes, just with
the last 12 bytes zero).

 - you'd see in the "object->type" whether it's a new or old-style hash.

I suspect it shouldn't be too painful to do it that way.

                Linus

On Fri, Feb 24, 2017 at 4:39 PM, Linus Torvalds
[off-list ref] wrote:

 - you'd see in the "object->type" whether it's a new or old-style hash.

Actually, I take that back. I think it might be easier to keep
"object->type" as-is, and it would only show the current OBJ_xyz
fields. Then writing the SHA ends up deciding whether a OBJ_COMMIT
gets written as "commit" or "commit2".

With the reachability rules, you'd never have any ambiguity about which to use.

                Linus

On Fri, 24 Feb 2017, Jeff King wrote:

So I'd much rather see strong rules like:

 1. Once a repo has flag-day switched over to the new hash format[1],
    new references are _always_ done with the new hash. Even ones that
    point to pre-flag-day objects!

how do you define when a repo has "switched over" to the new format in a 
distributed environment?

so you have one person working on a project that switches their version of git 
to the new one that uses the new format.

But other people they interact with still use older versions of git

what happens when you have someone working on two different projects where one 
has switched and the other hasn't?

what if they are forks of each other? (LEDE and OpenWRT, or just linux-kernel 
and linux-kernel-stable)

    So you get a "commit-v2" object instead of a "commit", and it has a
    distinct hash identity from its "commit" counterpart. You can point
    to a classic "commit", but you do so by its new-hash.

    The flag-day switch would probably be a repo config flag based on
    repositoryformatversion (so old versions would just punt if they
    see it). Let's call this flag "newhash" for lack of a better term.

so how do you interact with someone who only expects the old commit instead of 
the commit-v2?

David Lang

On Fri, Feb 24, 2017 at 5:00 PM, David Lang [off-list ref] wrote:

On Fri, 24 Feb 2017, Jeff King wrote:

quoted

So I'd much rather see strong rules like:

 1. Once a repo has flag-day switched over to the new hash format[1],
    new references are _always_ done with the new hash. Even ones that
    point to pre-flag-day objects!

how do you define when a repo has "switched over" to the new format in a
distributed environment?

so you have one person working on a project that switches their version of
git to the new one that uses the new format.

But other people they interact with still use older versions of git

what happens when you have someone working on two different projects where
one has switched and the other hasn't?

you get infected by the "new version requirement"
as soon as you pull? (GPL is cancer, anyone? ;)

If you are using an old version of git that doesn't understand the new version,
you're screwed.

On Fri, Feb 24, 2017 at 05:00:55PM -0800, David Lang wrote:

On Fri, 24 Feb 2017, Jeff King wrote:

quoted

So I'd much rather see strong rules like:

 1. Once a repo has flag-day switched over to the new hash format[1],
    new references are _always_ done with the new hash. Even ones that
    point to pre-flag-day objects!

how do you define when a repo has "switched over" to the new format in a
distributed environment?

You don't. It's a decision for each local repo, but the rules push
everybody towards upgrading (because you forbid them pulling from or
pushing to people who have upgraded).

So in practice, some centralized distribution point switches, and then
it floods out from there.

so you have one person working on a project that switches their version of
git to the new one that uses the new format.

That shouldn't happen when they switch. It should happen when they
decide to move their local clone to the new format. So let's assume they
upgrade _and_ decide to switch.

But other people they interact with still use older versions of git

Those people get forced to upgrade if they want to continue interacting.

what happens when you have someone working on two different projects where
one has switched and the other hasn't?

See above. You only flip the flag on for one of the projects.

what if they are forks of each other? (LEDE and OpenWRT, or just
linux-kernel and linux-kernel-stable)

Once one flips, the other one needs to flip to, or can't interact with
them. I know that's harsh, and is likely to create headaches. But in the
long run, I think once everything has converged the resulting system is
less insane.

For that reason I _wouldn't_ recommend projects like the kernel flip the
flag immediately. Ideally we write the code and the new versions
permeate the community. Then somebody (per-project) decides that it's
time for the community to start switching.

quoted

    The flag-day switch would probably be a repo config flag based on
    repositoryformatversion (so old versions would just punt if they
    see it). Let's call this flag "newhash" for lack of a better term.

so how do you interact with someone who only expects the old commit instead
of the commit-v2?

You ask them to upgrade.

-Peff

On Fri, 24 Feb 2017, Jeff King wrote:

quoted

what if they are forks of each other? (LEDE and OpenWRT, or just
linux-kernel and linux-kernel-stable)

Once one flips, the other one needs to flip to, or can't interact with
them. I know that's harsh, and is likely to create headaches. But in the
long run, I think once everything has converged the resulting system is
less insane.

For that reason I _wouldn't_ recommend projects like the kernel flip the
flag immediately. Ideally we write the code and the new versions
permeate the community. Then somebody (per-project) decides that it's
time for the community to start switching.

can you 'un-flip' the flag? or if you have someone who is a developer flip their 
repo (because they heard that sha1 is unsafe, and they want to be safe), they 
can't contribute to the kernel. We don't want to have them loose all their work, 
so how can they convert their local repo back to somthing that's compatible?

how would submodules work if one module flips and another (or the parent) 
doesn't?

OpenWRT/LEDE have their core repo, and they pull from many other (unrelated) 
projects into that repo (and then have 'feeds', which is sort-of-like-submodules 
to pull in other software that's maintained completely independently)

Microsoft has made lots of money with people being forced to upgrade Word 
because one person got a new version and everyone else needed to upgrade to be 
compatible. There's a LOT of pain during that process. Is that really the best 
way to go?

David Lang

On Fri, Feb 24, 2017 at 05:39:43PM -0800, David Lang wrote:

On Fri, 24 Feb 2017, Jeff King wrote:

quoted

quoted

what if they are forks of each other? (LEDE and OpenWRT, or just
linux-kernel and linux-kernel-stable)

Once one flips, the other one needs to flip to, or can't interact with
them. I know that's harsh, and is likely to create headaches. But in the
long run, I think once everything has converged the resulting system is
less insane.

For that reason I _wouldn't_ recommend projects like the kernel flip the
flag immediately. Ideally we write the code and the new versions
permeate the community. Then somebody (per-project) decides that it's
time for the community to start switching.

can you 'un-flip' the flag? or if you have someone who is a developer flip
their repo (because they heard that sha1 is unsafe, and they want to be
safe), they can't contribute to the kernel. We don't want to have them loose
all their work, so how can they convert their local repo back to somthing
that's compatible?

I don't think it would be too hard to write an un-flipper (it's
basically just rewriting the newhash bit of history using sha1, and
converting your refs back to point at the sha1s).

how would submodules work if one module flips and another (or the parent)
doesn't?

That's a good question. It's possible that another exception should be
carved out for referring to a gitlink via sha1 (we _could_ say "no,
point to a newhash version of the submodule", but I think that creates a
lot of hardship for not much gain).

OpenWRT/LEDE have their core repo, and they pull from many other (unrelated)
projects into that repo (and then have 'feeds', which is
sort-of-like-submodules to pull in other software that's maintained
completely independently)

I think with submodules this should probably still work.  If they are
pulling in with a subtree-ish strategy, then they'd convert the incoming
trees to the newhash format as part of that.

Microsoft has made lots of money with people being forced to upgrade Word
because one person got a new version and everyone else needed to upgrade to
be compatible. There's a LOT of pain during that process. Is that really the
best way to go?

I think there's going to be a lot of pain regardless. Any attempt to
mitigate that pain and work seamlessly across old and new versions of
git is going cause _ongoing_ pain as people quietly rewrite the same
content back and forth with different hashes. The viral-convergence
strategy is painful once (when you're forced to upgrade), but after that
just works.

If you want to work on a dual-hash strategy, be my guest. I can't
promise I'll be able to find horrific corner cases in it, but I
certainly can't even try to do so until there is a concrete proposal. :)

-Peff

On Fri, 24 Feb 2017, Jeff King wrote:

quoted

OpenWRT/LEDE have their core repo, and they pull from many other (unrelated)
projects into that repo (and then have 'feeds', which is
sort-of-like-submodules to pull in other software that's maintained
completely independently)

I think with submodules this should probably still work.  If they are
pulling in with a subtree-ish strategy, then they'd convert the incoming
trees to the newhash format as part of that.

as I understand things, they have two categories of things

1. Feeds, which are completely independent, separate maintainers

2. core, which gets pulled into one repo, I don't know if they use submodules in 
the process. I know that what downstream users see is a single repo.

I understand and agree with the idea of trying to converge rapidly. I'm just 
looking at cases where this may be hard (or where there may be holdouts for 
whatever reason)

David Lang

On Fri, Feb 24, 2017 at 5:21 PM, Jeff King [off-list ref] wrote:

On Fri, Feb 24, 2017 at 05:00:55PM -0800, David Lang wrote:

quoted

On Fri, 24 Feb 2017, Jeff King wrote:

quoted

So I'd much rather see strong rules like:

 1. Once a repo has flag-day switched over to the new hash format[1],
    new references are _always_ done with the new hash. Even ones that
    point to pre-flag-day objects!

how do you define when a repo has "switched over" to the new format in a
distributed environment?

You don't. It's a decision for each local repo, but the rules push
everybody towards upgrading (because you forbid them pulling from or
pushing to people who have upgraded).

So in practice, some centralized distribution point switches, and then
it floods out from there.

This seems like the most reasonable strategy so far. I think that
trying to allow long term co-existence is a huge pain that discourages
switching, when we actually want to encourage everyone to switch
someone has switched.

I don't think it's sane to try and allow simultaneous use of both
hashes, since that creates a lot of headaches and discourages
transition somewhat.

Thanks,
Jake

On Fri, Feb 24, 2017 at 5:39 PM, David Lang [off-list ref] wrote:

On Fri, 24 Feb 2017, Jeff King wrote:

quoted

quoted

what if they are forks of each other? (LEDE and OpenWRT, or just
linux-kernel and linux-kernel-stable)

Once one flips, the other one needs to flip to, or can't interact with
them. I know that's harsh, and is likely to create headaches. But in the
long run, I think once everything has converged the resulting system is
less insane.

For that reason I _wouldn't_ recommend projects like the kernel flip the
flag immediately. Ideally we write the code and the new versions
permeate the community. Then somebody (per-project) decides that it's
time for the community to start switching.

can you 'un-flip' the flag? or if you have someone who is a developer flip
their repo (because they heard that sha1 is unsafe, and they want to be
safe), they can't contribute to the kernel. We don't want to have them loose
all their work, so how can they convert their local repo back to somthing
that's compatible?

I'd think one of the first things we want is a way to flip *and*
unflip by re-writing history ala git-filter-branch style. (So if you
wanted, you could also flip all your old history).

One unrelated thought I had. When an old client sees the new stuff, it
will probably fail in a lot of weird ways. I wonder what we can do so
that if we in the future have to switch to an even newer hash, how can
we make it so that the old versions give a more clean error
experience? Ideally so that it lessens the pain of transition somewhat
in the future if/when it has to happen again?

Thanks,
Jake

Repos should address keeping / 'fixing' broken sha-1 as needed.
They also really need to create new native modes so users can
initialize and use repos with (sha-3 / sha-256 / whatever) going forward.
Backward compatibility with sha-1 or 'fixed sha-1' will be fine. Clients
can 'taste' and 'test' repos for which hash mode to use, or add it to
their configs. Make things flexible, modular, configurable, updateable.
What little point is there in 'fixing / caveating' their use of broken sha-1,
without also doing strong (sha-3 / optionals) in the first place, defaulting
new init's to whichever strong hash looks good, and letting natural
migration to that happen on its own through the default process.
Introducing new hash modes also gives good oppurtunity to incorporate
other generally 'incompatabile with the old' changes to benefit the future.
One might argue against mixed mode, after all, export and import,
as with any other repo migration, is generally possible.  And mixed
mode tends to prolong the actual endeavour to move to something
better in the init itself. Native and new makes you update to follow.
A lot of question / wrong ramble here, but the point should be
consistant... move, natively, even if only for sake of death of old
broken hashes. And attacks only get worse. Thought food is all.

On Fri, Feb 24, 2017 at 09:32:13AM -0800, Junio C Hamano wrote:

Ian Jackson [off-list ref] writes:

quoted

I have been thinking about how to do a transition from SHA1 to another
hash function.

Good.  I think many of us have also been, too, not necessarily just
in the past few days in response to shattered, but over the last 10
years, yet without coming to a consensus design ;-)

quoted

I have concluded that:

 * We can should avoid expecting everyone to rewrite all their
   history.

Yes.

There are security implications for old objects if we mix hashes, but I
suppose people who want better security will just rewrite history
anyway.

As long as the reader can tell from the format of object names
stored in the "new object format" object from what era is being
referred to in some way [*1*], we can name new objects with only new
hash, I would think.  "new refers only to new" that stratifies
objects into older and newer may make things simpler, but I am not
convinced yet that it would give our users a smooth enough
transition path (but I am open to be educated and pursuaded the
other way).

I would simply use multihash[0] for this purpose.  New-style objects
serialize data in multihash format, so it's immediately obvious what
hash we're referring to.  That makes future transitions less
problematic.

[0] https://github.com/multiformats/multihash
-- 
brian m. carlson / brian with sandals: Houston, Texas, US
+1 832 623 2791 | https://www.crustytoothpaste.net/~bmc | My opinion only
OpenPGP: https://keybase.io/bk2204

On Sat, Feb 25, 2017 at 06:50:50PM +0000, brian m. carlson wrote:

quoted

As long as the reader can tell from the format of object names
stored in the "new object format" object from what era is being
referred to in some way [*1*], we can name new objects with only new
hash, I would think.  "new refers only to new" that stratifies
objects into older and newer may make things simpler, but I am not
convinced yet that it would give our users a smooth enough
transition path (but I am open to be educated and pursuaded the
other way).

I would simply use multihash[0] for this purpose.  New-style objects
serialize data in multihash format, so it's immediately obvious what
hash we're referring to.  That makes future transitions less
problematic.

[0] https://github.com/multiformats/multihash

I looked at that earlier, because I think it's a reasonable idea for
future-proofing. The first byte is a "varint", but I couldn't find where
they defined that format.

The closest I could find is:

  https://github.com/multiformats/unsigned-varint

whose README says:

  This unsigned varint (VARiable INTeger) format is for the use in all
  the multiformats.

    - We have not yet decided on a format yet. When we do, this readme
      will be updated.

    - We have time. All multiformats are far from requiring this varint.

which is not exactly confidence inspiring. They also put the length at
the front of the hash. That's probably convenient if you're parsing an
unknown set of hashes, but I'm not sure it's helpful inside Git objects.
And there's an incentive to minimize header data at the front of a hash,
because every byte is one more byte that every single hash will collide
over, and people will have to type when passing hashes to "git show",
etc.

I'd almost rather use something _really_ verbose like

  sha256:1234abcd...

in all of the objects. And then when we get an unadorned hash from the
user, we guess it's sha256 (or whatever), and fallback to treating it as
a sha1.

Using a syntactically-obvious name like that also solves one other
problem: there are sha1 hashes whose first bytes will encode as a "this
is sha256" multihash, creating some ambiguity.

-Peff

On Sat, Feb 25, 2017 at 02:26:56PM -0500, Jeff King wrote:

On Sat, Feb 25, 2017 at 06:50:50PM +0000, brian m. carlson wrote:

quoted

quoted

As long as the reader can tell from the format of object names
stored in the "new object format" object from what era is being
referred to in some way [*1*], we can name new objects with only new
hash, I would think.  "new refers only to new" that stratifies
objects into older and newer may make things simpler, but I am not
convinced yet that it would give our users a smooth enough
transition path (but I am open to be educated and pursuaded the
other way).

I would simply use multihash[0] for this purpose.  New-style objects
serialize data in multihash format, so it's immediately obvious what
hash we're referring to.  That makes future transitions less
problematic.

[0] https://github.com/multiformats/multihash

I looked at that earlier, because I think it's a reasonable idea for
future-proofing. The first byte is a "varint", but I couldn't find where
they defined that format.

The closest I could find is:

  https://github.com/multiformats/unsigned-varint

whose README says:

  This unsigned varint (VARiable INTeger) format is for the use in all
  the multiformats.

    - We have not yet decided on a format yet. When we do, this readme
      will be updated.

    - We have time. All multiformats are far from requiring this varint.

which is not exactly confidence inspiring. They also put the length at
the front of the hash. That's probably convenient if you're parsing an
unknown set of hashes, but I'm not sure it's helpful inside Git objects.
And there's an incentive to minimize header data at the front of a hash,
because every byte is one more byte that every single hash will collide
over, and people will have to type when passing hashes to "git show",
etc.

I'd almost rather use something _really_ verbose like

  sha256:1234abcd...

in all of the objects. And then when we get an unadorned hash from the
user, we guess it's sha256 (or whatever), and fallback to treating it as
a sha1.

Using a syntactically-obvious name like that also solves one other
problem: there are sha1 hashes whose first bytes will encode as a "this
is sha256" multihash, creating some ambiguity.

Indeed, multihash only really is interesting when *all* hashes use it.
And obviously, git can't change the existing sha1s.

Mike

On Sun, Feb 26, 2017 at 07:09:44AM +0900, Mike Hommey wrote:

On Sat, Feb 25, 2017 at 02:26:56PM -0500, Jeff King wrote:

quoted

I looked at that earlier, because I think it's a reasonable idea for
future-proofing. The first byte is a "varint", but I couldn't find where
they defined that format.

The closest I could find is:

  https://github.com/multiformats/unsigned-varint

whose README says:

  This unsigned varint (VARiable INTeger) format is for the use in all
  the multiformats.

    - We have not yet decided on a format yet. When we do, this readme
      will be updated.

    - We have time. All multiformats are far from requiring this varint.

which is not exactly confidence inspiring. They also put the length at
the front of the hash. That's probably convenient if you're parsing an
unknown set of hashes, but I'm not sure it's helpful inside Git objects.
And there's an incentive to minimize header data at the front of a hash,
because every byte is one more byte that every single hash will collide
over, and people will have to type when passing hashes to "git show",
etc.

The multihash spec also says that it's not necessary to implement
varints until we have 127 hashes, and considering that will be in the
far future, I'm quite happy to punt that problem down the road to
someone else[0].

quoted

I'd almost rather use something _really_ verbose like

  sha256:1234abcd...

in all of the objects. And then when we get an unadorned hash from the
user, we guess it's sha256 (or whatever), and fallback to treating it as
a sha1.

Using a syntactically-obvious name like that also solves one other
problem: there are sha1 hashes whose first bytes will encode as a "this
is sha256" multihash, creating some ambiguity.

Indeed, multihash only really is interesting when *all* hashes use it.
And obviously, git can't change the existing sha1s.

Well, that's why I said in new objects.  If we're going to default to a
new hash, we can store it inside the object format, but not actually
expose it to the user.

In other words, if we used SHA-256, a tree object would refer to the SHA-1
empty blob as 1114e69de29bb2d1d6434b8b29ae775ad8c2e48c5391 and the
SHA-256 empty blob as
1220473a0f4c3be8a93681a267e3b1e9a7dcda1185436fe141f7749120a303721813,
but user-visible code would parse them as e69d... and 473a... (or as
sha1:e69d and 473a, or something).

There's very little code which actually parses objects, so it's easy
enough to introduce a few new functions to read and write the prefixed
versions within the objects, and leave the rest to work in the same old
user-visible way (or in the way that you've proposed).

Note also that we need some way to distinguish objects in binary form,
since if we mix hashes, we need to be able to read data directly from
pack files and other locations where we serialize data that way.
Multihash would do that, even if we didn't expose that to the user.

[0] And for the record, I'm a maintenance programmer, and I dislike it
when people punt the problem down the road to someone else, because
that's usually me.
-- 
brian m. carlson / brian with sandals: Houston, Texas, US
+1 832 623 2791 | https://www.crustytoothpaste.net/~bmc | My opinion only
OpenPGP: https://keybase.io/bk2204

On Fri, Feb 24, 2017 at 4:39 PM, Linus Torvalds
[off-list ref] wrote:

Honestly, I think that a primary goal for a new hash implementation
absolutely needs to be to minimize mixing.

Not for security issues, but because of combinatorics. You want to
have a model that basically reads old data, but that very aggressively
approaches "new data only" in order to avoid the situation where you
have basically the exact same tree state, just _represented_
differently.

For example, what I would suggest the rules be is something like this:

Hmm. Having looked at this a fair amount, and in particularly having
looked at the code as part of the hash typesafety patch I did, I am
actually starting to think that it would not be too painful at all to
have a totally different approach, which might be a lot easier to do.

So bear with me, let me try to explain my thinking:

 (a) if we want to be backwards compatible and not force people to
convert their trees on some flag day, we're going to be stuck with
having to have the SHA1 code around and all the existing object
parsing for basically forever

Now, this basically means that the _easy_ solution would be that we
just do the flag day, switch to sha-256, extend everything to 32-byte
hashes, and just have a "git2 fast-import" that makes it easy to
convert stuff.

But it really would be a completely different version of git, with a
new pack-file format and no real compatibility. Such a flag-day
approach would certainly have advantages: it would allow for just
re-architecting some bad choices:

 - make the hashing be something that can be threaded (ie maybe we can
just block it up in 4MB chunks that you can hash in parallel, and make
the git object hash be the hash of hashes)

 - replace zlib with something like zstd

 - get rid of old pack formats etc.

but  on the whole, I still think that the compatibility would be worth
much more than the possible technical advantages of a clean slate
restart.

 (b) the SHA1 hash is actually still quite strong, and the collision
detection code effectively means that we don't really have to worry
about collisions in the immediate future.

In other words, the mitigation of the current attack is actually
really easy technically (modulo perhaps the performance concerns), and
there's still nothing fundamentally wrong with using SHA1 as a content
hash. It's still a great hash.

Now, my initial reaction (since it's been discussed for so long
anyway) was obviously "pick a different hash". That was everybody's
initial reaction, I think.

But I'm starting to think that maybe that initial obvious reaction was wrong.

The thing that makes collision attacks so nasty is that our reaction
to a collision is so deadly.  But that's not necessarily fundamental:
we certainly uses hashes with collisions every day, and they work
fine. And they work fine because the code that uses those hashes is
designed to simply deal gracefully - although very possibly with a
performance degradation - with two different things hashing to the
same bucket.

So what if the solution to "SHA1 has potential collisions" is "any
hash can have collisions in theory, let's just make sure we handle
them gracefully"?

Because I'm looking at our data structures that have hashes in them,
and many of them are actually of the type where I go

  "Hmm..  Replacing the hash entirely is really really painful - but
it wouldn't necessarily be all that nasty to extend the format to have
additional version information".

and the advantage of that approach is that it actually makes the
compatibility part trivial. No more "have to pick a different hash and
two different formats", and more of a "just the same format with
extended information that might not be there for old objects".

So we have a few different types of formats:

 - the purely local data structures: the pack index file, the file
index, our refs etc

   These we could in change completely, and it wouldn't even be all
that painful. The pack index has already gone through versions, and it
doesn't affect anything else.

 - the actual objects.

   These are fairly painful to change, particularly things like the
"tree" object which is probably the worst designed of the lot. Making
it contain a fixed-size binary thing was really a nasty mistake. My
bad.

 - the pack format and the protocol to exchange "I have this" information

   This is *really* painful to change, because it contains not just
the raw object data, but it obviously ends up being the wire format
for remote accesses.

and it turns out that *all* of these formats look like they would be
fairly easy to extend to having extra object version information. Some
of that extra object version information we already have and don't
use, in fact.

Even the tree format, with the annoying fixed-size binary blob. Yes,
it has that fixed size binary blob, but it has it in _addition_ to the
ASCII textual form that would be really easy to just extend upon. We
have that "tree entry type" that we've already made extensions with by
using it for submodules. It would be quite easy to just say that a
tree entry also has a "file version" field, so that you can have
multiple objects that just hash to the same SHA1, and git wouldn't
even *care*.

The transfer protocol is the same: yes, we transfer hashes around, but
it would not be all that hard to extend it to "transfer hash and
object version".

And the difference is that then the "backwards compatibility" part
just means interacting with somebody who didn't know to transfer the
object version. So suddenly being backwards compatible isn't a whole
different object parsing thing, it's just a small extension.

IOW, we could make it so that the SHA1 is just a hash into a list of
objects. Even the pack index format wouldn't need to change - right
now we assume that an index hit gives us the direct pointer into the
pack file, but we *could* just make it mean that it gives us a direct
pointer to the first object in the pack file with that SHA1 hash.
Exactly like you'd normally use a hash table with linear probing.

Linear probing is usually considered a horrible approach to hash
tables,. but it's actually a really useful one for the case where
collisions are very rare.

Anyway, I do have a suggestion for what the "object version" would be,
but I'm not even going to mention it, because I want people to first
think about the _concept_ and not the implementation.

So: What do you think about the concept?

               Linus

On Thu, Mar 02, 2017 at 11:55:45AM -0800, Linus Torvalds wrote:

Anyway, I do have a suggestion for what the "object version" would be,
but I'm not even going to mention it, because I want people to first
think about the _concept_ and not the implementation.

So: What do you think about the concept?

I think it very much depends on what's in the "object version". :)

IMHO, we are best to consider sha1 "broken" and not count on any of its
bytes for cryptographic integrity. I know that's not really the case,
but it just makes reasoning about the whole thing simpler. So at that
point, it's pretty obvious that the "object version" is really just "an
integrity hash".

And that takes us full circle to earlier proposals over the years to do
something like this in the commit header:

  parent ...some sha1...
  parent-sha256 ...some sha256...

and ditto in tag headers, and trees obviously need to be hackily
extended as you described to carry the extra hash. And then internally
we continue to happily use sha1s, except you can check the
sha256-validity of any reference if you feel like it.

This is functionally equivalent to "just start using sha-256, but keep a
mapping of old sha1s to sha-256s to handle old references". The
advantage is that it makes the code part of the transition simpler. The
disadvantage is that you're effectively carrying a piece of that
sha1->sha256 mapping around in _every_ object.

And that means the same bits of mapping data are repeated over and over.
Git's pretty good at de-duplicating on the surface. So yeah, every tree
entry is now 256 bits larger, but deltas mean that we usually only end
up storing each entry a handful of times. But we still pay the price to
walk over the bytes every time we apply a delta, zlib inflate, parse the
tree, etc. The runtime cost of the transition is carried forward
forever, even for repositories that are willing to rewrite history, or
are created after the flag day.

So I dunno. Maybe I am missing something really clever about your
proposal. Reading the rest of the thread, it sounds like you had a
thought that we could get by with a very tiny object version, but the
hash-adding thing nixed that. If I'm still missing the point, please try
to sketch it out a bit more concretely, and I'll come back with my
thinking cap on.

-Peff

On Thu, Mar 2, 2017 at 11:55 AM, Linus Torvalds
[off-list ref] wrote:

So: What do you think about the concept?

               Linus

One of the things I like about working on Git is its pretty
high standard of testing. So we would need to come up with
good methods of testing this, e.g. when
GIT_TEST_WITH_DEGENERATE_HASH is set, we'd use
an intentionally weak hashing function and have tests for
the collisions. These tests would need cover most of the
workflows that are currently performed with Git
(local creation, fetching, pushing). Writing all these
additional tests (which consists of creating colliding
objects/commits and then performing all these tests),
sounds about as much work as actually converting to
a new hash function. (First locally and then at a later
point in time all the networking related things).

I would not want to go that way.

Stefan