git/list[1] front-page[2] threads[3] people[4] search[5] about
 

Re: [PATCH] Implement fast hash-collision detection

From
Jeff King <peff@peff.net>
Date
Nov 29, 2011, 20:59 UTC
Message-ID
<20111129205905.GA1793@sigill.intra.peff.net>
In-Reply-To
<CACsJy8DboVU4kSbJSV=8NP08OyLYVgOKsm8tt=koZ0=JcGSE=A@mail.gmail.com>
On Tue, Nov 29, 2011 at 09:04:06PM +0700, Nguyen Thai Ngoc Duy wrote:
Show 15 quoted lines
> > 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
Previous: Nguyen Thai Ngoc DuyNext: Nguyen Thai Ngoc Duy
Message 7 of 20 in “Re: [PATCH] Implement fast hash-collision detection”
  1. Jeff KingNov 29, 2011
  2. Ævar Arnfjörð BjarmasonNov 29, 2011
  3. Jeff KingNov 29, 2011
  4. Nguyen Thai Ngoc DuyNov 29, 2011
  5. Shawn PearceNov 29, 2011
  6. Nguyen Thai Ngoc DuyNov 29, 2011
  7. Jeff KingNov 29, 2011
  8. Nguyen Thai Ngoc DuyNov 30, 2011
  9. Junio C HamanoNov 30, 2011
  10. Nguyen Thai Ngoc DuyDec 1, 2011
  11. Bill ZaumenNov 30, 2011
  12. Bill ZaumenNov 29, 2011
  13. Jeff KingNov 30, 2011
  14. Bill ZaumenDec 1, 2011
  15. Jeff KingDec 1, 2011
  16. Bill ZaumenDec 2, 2011
  17. Jeff KingDec 2, 2011
  18. Shawn PearceNov 29, 2011
  19. Jeff KingNov 29, 2011
  20. Bill ZaumenNov 30, 2011

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.