Re: Suggestion on hashing

["Philip Oakley" <philipoakley@iee.org>]

Had you seen the recent thread by Junio with the footnote link to the paper 
on reconcilliation by using multiple hashes?
http://article.gmane.org/gmane.linux.kernel/1214517.
"What's the Difference? Efficient Set Reconciliation without Prior
Context" http://cseweb.ucsd.edu/~fuyeda/papers/sigcomm2011.pdfIt looks to 
have a lot of the properties being sought, and links with other git aspects.

Philip

From: "Jeff King" <peff@peff.net>: Saturday, December 03, 2011 3:08 PM
On Fri, Dec 02, 2011 at 05:50:21PM -0800, Bill Zaumen wrote:

> 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:
>
> > 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.

If you make the digest stronger (or pluggable) and include it in the
actual objects themselves, then you have a start on (2).

I'd drop all of the digest-exchange bits from the protocol, as the
actual signatures are the real, trustable verification. I don't think
you can drop the external storage of the digests, which is one of the
ugliest bits. You'll be asking for the digests all the time to create
new commit objects, so you need to have it at hand without rehashing.

And I wouldn't get my hopes up that this will go into git any time soon.
At this point, we're really guessing about how broken SHA-1 will be in
the future, and how much we are going to want to care.

Just my two cents.

-Peff
--
Version: 2012.0.1873 / Virus Database: 2102/4653 - Release Date: 12/02/11