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

Re: [PATCH] Implement fast hash-collision detection

From
Nguyen Thai Ngoc Duy <pclouds@gmail.com>
Date
Nov 30, 2011, 13:35 UTC
Message-ID
<CACsJy8A6kGmn0h0xdxfTC4krXgc8hzO1fHTdqfk0YnASGN5K0w@mail.gmail.com>
In-Reply-To
<20111129205905.GA1793@sigill.intra.peff.net>
On Wed, Nov 30, 2011 at 3:59 AM, Jeff King <peff@peff.net> wrote:
Show 9 quoted lines
> 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.

What I'm thinking is whether it's possible to decouple two sha-1 roles in git, as object identifier and digest, separately. Each sha-1 identifies an object and an extra set of digests on the "same" object. Object database is extended to store all these new digests and mapping between sha-1 and them. When we need to verify an object, given an sha-1, we rehash that object and check the result digest with the ones linked to the sha-1.

These new digests would be "digest of digests" just like how we use sha-1. In fact this new digest set could be just sha-1. We just don't hash trees/commits/tags as-is when computing these new digests. When a tree object is hashed, for example, a new tree object with new digests will be created for hashing (we keep sha-1 <-> new digest mapping on disk). Think of duplicating an entire DAG with new digests as links instead of sha-1, then we keep digests and drop the DAG.

The day sha-1 is broken, a project can generate new digests from its old good repo and enforce developers to use new digests for verification instead of sha-1. sha-1 is still used by git as identifier after that day.

Computing these digests is expensive, but for local, day-to-day use, we only need sha-1 as identifier (correct me if I'm wrong here), so we can delay compute/store these new digests until we absolutely need them (e.g. push/fetch). There is also an interesting case, assume these digests are strong enough, we could replace sha-1 as identifier in git with a cheaper hash. A new hash must fit in 160-bit space that sha-1 takes and should have good distribution, of course. Projects with a lot of data may like it that way.

-- 
Duy
Previous: Jeff KingNext: Junio C Hamano
Message 8 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.