Re: Suggestion on hashing

From: Philip Oakley <philipoakley@iee.org>
Date: Dec 3, 2011, 15:08 UTC
Message-ID: <68774CC59ECA4F7AB5DA410F34045F32@PhilipOakley>
In-Reply-To: <20111203150842.GA4442@sigill.intra.peff.net>

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:

Show 26 quoted lines

> 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