Re: RFC v3: Another proposed hash function transition plan

[Jonathan Nieder <jrnieder@gmail.com>]

Hi,

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

> 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