Re: Suggestion on hashing

From: Bill Zaumen <bill.zaumen@gmail.com>
Date: Dec 3, 2011, 01:50 UTC
Message-ID: <1322877021.1729.118.camel@yos>
In-Reply-To: <20111202175444.GB24093@sigill.intra.peff.net>

On Fri, 2011-12-02 at 12:54 -0500, Jeff King wrote:

> On Fri, Dec 02, 2011 at 12:08:39AM -0800, Bill Zaumen wrote:

Show 16 quoted lines

> I think your code is solving the wrong problem (or solving the right
> problem in a half-way manner). The only things that make sense to me
> are:
> 
>   1. Do nothing. SHA-1 is probably not broken yet, even by the NSA, and
>      even if it is, an attack is extremely expensive to mount. This may
>      change in the future, of course, but it will probably stay
>      expensive for a while.
> 
>   2. Decouple the object identifier and digest roles, but insert the
>      digest into newly created objects, so it can be part of the
>      signature chain. I described such a scheme in one of my replies to
>      you. It has some complexities, but has the bonus that we can build
>      directly on older history, preserving its sha1s.
> 
>   3. Replace SHA-1 with a more secure algorithm.

Suppose I make the digest pluggable, something I intended to do eventually anyway? Then you just use the existing SHA-1 as an object identifier and the new digest in a signature chain? What I did was essentially to compute the new digest (using a CRC as the trivial case) whenever an object's SHA-1 hash is computed, plus using the new digest for low-cost collision checks.

Then you have everything needed to experiment with your second option. I got the impression that Nguyen had some interest in that, but could be mistaken.

The use is simple: if you have the SHA-1 hash of an object, you call a function, currently named "has_sha1_file_crc" and it returns true if a CRC is available, writing the hash into the buffer supplied as its second argument. You can do whatever you like with it. If you want a digest of digests, you just traverse a commit's tree, and call has_sha1_file_crc whenever you want to look up a digest. So, the API is actually very simple if you just use the patch to quickly look up the digest associated with a SHA-1 ID - everything else it does happens automatically.