Re: Hash algorithm analysis

From: Jonathan Nieder <jrnieder@gmail.com>
Date: Jun 11, 2018, 19:29 UTC
Message-ID: <20180611192942.GC20665@aiede.svl.corp.google.com>
In-Reply-To: <20180609224913.GC38834@genre.crustytoothpaste.net>

Hi,

brian m. carlson wrote:

> == Discussion of Candidates
>
> I've implemented and tested the following algorithms, all of which are
> 256-bit (in alphabetical order):

Thanks for this.  Where can I read your code?

[...]

> I also rejected some other candidates.  I couldn't find any reference or
> implementation of SHA256×16, so I didn't implement it.

Reference: https://eprint.iacr.org/2012/476.pdf

If consensus turns toward it being the right hash function to use, then we can pursue finding or writing a good high-quality implementation. But I tend to suspect that the lack of wide implementation availability is a reason to avoid it unless we find SHA-256 to be too slow.

[...]

> * BLAKE2bp, as implemented in libb2, uses OpenMP (and therefore
>   multithreading) by default.  It was no longer possible to run the
>   testsuite with -j3 on my laptop in this configuration.

My understanding is that BLAKE2bp is better able to make use of simd instructions than BLAKE2b. Is there a way to configure libb2 to take advantage of that without multithreading?

E.g. https://github.com/sneves/blake2-avx2 looks promising for that.

[...]

Show 12 quoted lines

> |===
> | Implementation             | 256 B  | 1 KiB  | 8 KiB  | 16 KiB |
> | SHA-1 (OpenSSL)            | 513963 | 685966 | 748993 | 754270 |
> | BLAKE2b (libb2)            | 488123 | 552839 | 576246 | 579292 |
> | SHA-512/256 (OpenSSL)      | 181177 | 349002 | 499113 | 495169 |
> | BLAKE2bp (libb2)           | 139891 | 344786 | 488390 | 522575 |
> | SHA-256 (OpenSSL)          | 264276 | 333560 | 357830 | 355761 |
> | KangarooTwelve             | 239305 | 307300 | 355257 | 364261 |
> | SHAKE128 (OpenSSL)         | 154775 | 253344 | 337811 | 346732 |
> | SHA3-256 (OpenSSL)         | 128597 | 185381 | 198931 | 207365 |
> | BLAKE2bp (libb2; threaded) |  12223 |  49306 | 132833 | 179616 |
> |===

That's a bit surprising, since my impression (e.g. in the SUPERCOP benchmarks you cite) is that there are secure hash functions that allow comparable or even faster performance than SHA-1 with large inputs on a single core. In Git we also care about performance with small inputs, creating a bit of a trade-off.

More on the subject of blake2b vs blake2bp:

- blake2b is faster for small inputs (under 1k, say). If this is
  important then we could set a threshold, e.g. 512 bytes, for
  swtiching to blake2bp.

- blake2b is supported in OpenSSL and likely to get x86-optimized
  versions in the future. blake2bp is not in OpenSSL.

[...]

Show 11 quoted lines

> == Summary
>
> The algorithms with the greatest implementation availability are
> SHA-256, SHA3-256, BLAKE2b, and SHAKE128.
>
> In terms of command-line availability, BLAKE2b, SHA-256, SHA-512/256,
> and SHA3-256 should be available in the near future on a reasonably
> small Debian, Ubuntu, or Fedora install.
>
> As far as security, the most conservative choices appear to be SHA-256,
> SHA-512/256, and SHA3-256.

SHA-256x16 has the same security properties as SHA-256. Picking between those two is a tradeoff between performance and implementation availability.

My understanding is that all the algorithms we're discussing are believed to be approximately equivalent in security. That's a strange thing to say when e.g. K12 uses fewer rounds than SHA3 of the same permutation, but it is my understanding nonetheless. We don't know yet how these hash algorithms will ultimately break.

My understanding of the discussion so far:

Keccak team encourages us[1] to consider a variant like K12 instead of SHA3.

AGL explains[2] that the algorithms considered all seem like reasonable choices and we should decide using factors like implementation ease and performance.

If we choose a Keccak-based function, AGL also[3] encourages using a variant like K12 instead of SHA3.

Dscho strongly prefers[4] SHA-256, because of
- wide implementation availability, including in future hardware
- has been widely analyzed
- is fast

Yves Orton and Linus Torvalds prefer[5] SHA3 over SHA2 because of how it is constructed.

Thanks, Jonathan

[1] https://public-inbox.org/git/91a34c5b-7844-3db2-cf29-411df5bcf886@noekeon.org/ [2] https://public-inbox.org/git/CAL9PXLzhPyE+geUdcLmd=pidT5P8eFEBbSgX_dS88knz2q_LSw@mail.gmail.com/ [3] https://www.imperialviolet.org/2017/05/31/skipsha3.html [4] https://public-inbox.org/git/alpine.DEB.2.21.1.1706151122180.4200@virtualbox/ [5] https://public-inbox.org/git/CA+55aFwUn0KibpDQK2ZrxzXKOk8-aAub2nJZQqKCpq1ddhDcMQ@mail.gmail.com/