Re: RFC v3: Another proposed hash function transition plan

From: Jonathan Nieder <jrnieder@gmail.com>
Date: Sep 14, 2017, 18:40 UTC
Message-ID: <20170914184022.GB78683@aiede.mtv.corp.google.com>
In-Reply-To: <alpine.DEB.2.21.1.1709141754240.4132@virtualbox>

Hi,

Johannes Schindelin wrote:

> On Wed, 13 Sep 2017, Jonathan Nieder wrote:

Show 11 quoted lines

>> [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].

Show 13 quoted lines

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

Thanks, Jonathan

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