Re: [PATCH] Implement fast hash-collision detection

[Jeff King <peff@peff.net>]

On Tue, Nov 29, 2011 at 09:04:06PM +0700, Nguyen Thai Ngoc Duy wrote:

> > You can fix this by including an extra header in the signed part of the
> > tag that says "also, the digest of the commit I point to is X". Then you
> > know you have the same commit that Linus had. But the commit points to a
> > tree by its sha1. So you have to add a similar header in the commit
> > object that says "also, the digest of the tree I point to is X". And
> > ditto for all of the parent pointers, if you want to care about signing
> > history. And then you have the same problem in the tree: each sub-tree
> > and blob is referenced by its sha1.
> >
> Can we just hash all objects in a pack from bottom up, (replacing
> sha-1 in trees/commits/tags with the new digest in memory before
> hashing), then attach the new top digest to tag's content? The sender
> is required by the receiver to send new digests for all objects in the
> pack together with the pack. The receiver can then go through the same
> process to produce the top digest and match it with one saved in tag.

I think that is conflating two different layers of git. The security for
tags happens at the conceptual object db layer: you sign a tag, and that
points to a commit, which points to a tree, and so on. The authenticity
comes from the tag signature, but the integrity of each link in the
chain is verifiable because of the has property. The pack layer, on the
other hand, is just an implementation detail about how those conceptual
objects are stored. More than just your tag will be in a pack, and the
contents of your tag may be spread across several packs (or even loose
objects).

So I don't think it's right to talk about packs at all in the signature
model.

If you wanted to say "make a digest of all of the sub-objects pointed to
by the tag", then yes, that does work (security-wise). But it's
expensive to calculate. Instead, you want to use a "digest of digests"
as much as possible. Which is what git already does, of course; you hash
the tree object, which contains hashes of the blob sha1s. Git's
conceptual model is fine. The only problem is that sha1 is potentially
going to lose its security properties, weakening the links in the chain.
So as much as possible, we want to insert additional links at the exact
same places, but using a stronger algorithm.

Does that make sense?

-Peff