Re: RFC v3: Another proposed hash function transition plan

From: Johannes Schindelin <Johannes.Schindelin@gmx.de>
To: Jonathan Nieder <jrnieder@gmail.com>
Cc: demerphq <demerphq@gmail.com>,
	Brandon Williams <bmwill@google.com>,
	Junio C Hamano <gitster@pobox.com>,
	Linus Torvalds <torvalds@linux-foundation.org>,
	Git Mailing List <git@vger.kernel.org>,
	Stefan Beller <sbeller@google.com>,
	jonathantanmy@google.com, Jeff King <peff@peff.net>,
	David Lang <david@lang.hm>,
	"brian m. carlson" <sandals@crustytoothpaste.net>
Subject: Re: RFC v3: Another proposed hash function transition plan
Date: Fri, 15 Sep 2017 00:09:29 +0200 (CEST)
Message-ID: <alpine.DEB.2.21.1.1709150008390.219280@virtualbox> (raw)
In-Reply-To: <20170914184022.GB78683@aiede.mtv.corp.google.com>

Hi Jonathan,

On Thu, 14 Sep 2017, Jonathan Nieder wrote:

> Johannes Schindelin wrote:
> > On Wed, 13 Sep 2017, Jonathan Nieder wrote:
> 
> >> [3] https://www.imperialviolet.org/2017/05/31/skipsha3.html,
> >
> > I had read this short after it was published, and had missed the updates.
> > One link in particular caught my eye:
> >
> > 	https://eprint.iacr.org/2012/476
> >
> > Essentially, the authors demonstrate that using SIMD technology can speed
> > up computation by factor 2 for longer messages (2kB being considered
> > "long" already). It is a little bit unclear to me from a cursory look
> > whether their fast algorithm computes SHA-256, or something similar.
> 
> The latter: that paper is about a variant on SHA-256 called SHA-256x4
> (or SHA-256x16 to take advantage of newer instructions).  It's a
> different hash function.  This is what I was alluding to at [1].

Thanks for the explanation!

> > As the author of that paper is also known to have contributed to OpenSSL,
> > I had a quick look and it would appear that a comment in
> > crypto/sha/asm/sha256-mb-x86_64.pl speaking about "lanes" suggests that
> > OpenSSL uses the ideas from the paper, even if b783858654 (x86_64 assembly
> > pack: add multi-block AES-NI, SHA1 and SHA256., 2013-10-03) does not talk
> > about the paper specifically.
> >
> > The numbers shown in
> > https://github.com/openssl/openssl/blob/master/crypto/sha/asm/keccak1600-x86_64.pl#L28
> > and in
> > https://github.com/openssl/openssl/blob/master/crypto/sha/asm/sha256-mb-x86_64.pl#L17
> >
> > are sufficiently satisfying.
> 
> This one is about actual SHA-256, but computing the hash of multiple
> streams in a single funtion call.  The paper to read is [2].  We could
> probably take advantage of it for e.g. bulk-checkin and index-pack.
> Most other code paths that compute hashes wouldn't be able to benefit
> from it.

Again, thanks for the explanation.

Ciao,
Dscho

> [1] https://public-inbox.org/git/20170616212414.GC133952@aiede.mtv.corp.google.com/
> [2] https://eprint.iacr.org/2012/371
> 