NewHash alternatives and SHA benchmarks

Hi Folks,

I have become interested in git's NewHash migration and have been investigating alternate hash algorithm support in git. It seems that implementation of NewHash is still a way off, and it is still possible to revise the choice of SHA256 for a better alternative.

Many of you may already be aware of Hash content Length extension attacks [1]. While I am not aware of any git vulnerabilities based on length extension; it seems to me that choosing a hash algorithm that is not vulnerable to this attack could prevent a future exploit based on some future protocol or other bug. git hashes should be final in its usage, so length extension resistance is a good property.

SHA3 is not vulnerable to content length extension because it uses a sponge construction internally, meaning state is diffused away, and the state cannot be reconstructed from a hash value. Truncated SHA2 hashes such as SHA224 and SHA512/256 are also not vulnerable to length extension, however, SHA224 only reduces the probability of extension by 1/2^32 which, while not trivial, is a small reduction.

SHA512/256 or SHA3-256 seems to me to be most attractive for safety against content length extension.

With this in mind, I decided to investigate performance properties of the alternative SHA hash algorithms. Of particular interest to me is SHA3-256 and SHA512/256 (SHA512 truncated to 256-bits) as they are both the same size as SHA256 thus are good NewHash contenders.

I was quite surprised by the benchmark results with SHA512/256 1.5X faster than SHA256. SHA512/256 seems a very good alternative to SHA256:

- SHA256 8 x 32-bit state (256-bits) and 64-byte block, 64 rounds
- SHA512 8 x 64-bit state (512-bits) and 128-byte block, 80 rounds

SHA512/256 has understandable good performance on 64-bits systems due to having only slightly more iterations (80 instead of 64) while processing 128 bytes per block instead of 64. In practice, this means SHA512/256 is about 1.5X faster than SHA256 on 64-bit systems.

SHA3, while competitive, is still significantly slower than SHA512. The AVX512 version of SHA3 is actually faster than SHA256. SHA256 is not the best performing NewHash alternative by a long shot.

SHA Benchmarks on Intel Core i7-7980XE @ 4.6GHz ===============================================

(MiB/sec)\      ext      16     128    1024    4096   65536 1048576
     -----    -----   -----   -----   -----   -----   -----   -----
      sha1     avx2    37.5   239.6   817.0  1097.5  1231.2  1244.8
    sha224     avx2    30.8   170.5   439.3   524.3   560.2   564.4
    sha256     avx2    31.2   171.2   438.7   525.0   560.9   564.8
    sha512     avx2    27.1   167.2   561.5   747.1   835.7   842.8
sha512-224     avx2    26.8   164.7   558.8   747.9   836.5   845.1
sha512-256     avx2    26.6   163.9   557.9   751.4   835.0   843.0
  sha3-224     avx2    38.9   313.8   411.5   474.6   491.1   490.7
  sha3-256     avx2    39.7   317.3   414.5   445.3   464.9   464.3
  sha3-384     avx2    39.8   184.6   338.1   348.4   356.5   358.0
  sha3-512     avx2    40.0   185.0   228.4   245.9   248.0   249.0

(MiB/sec)\      ext      16     128    1024    4096   65536 1048576
     -----    -----   -----   -----   -----   -----   -----   -----
  sha3-224   avx512    24.3   192.6   506.5   674.3   736.8   740.9
  sha3-256   avx512    25.0   198.4   511.5   635.4   698.8   698.8
  sha3-384   avx512    24.8   152.3   429.6   503.9   535.7   540.2
  sha3-512   avx512    24.8   152.4   307.3   361.2   375.6   374.4

Recommendations ===============

After performing multiple benchmarks and thinking about this for several weeks I have come to the conclusion that SHA512/256 is a very good alternative to SHA256, both from the perspective of its length extension resistance, and performance. It seems that NewHash implementation is some way off so it is not too late to change.

- Consider SHA512/256 for NewHash

SHA algorithm patches =====================

I will be sending a patch series which adds SHA Algorithms which are in the sha-algorithms branch of my git tree.

- https://github.com/michaeljclark/git.git
- https://github.com/michaeljclark/git/tree/sha-algorithms/sha

This is a precursor to asking some questions about the proposed implementation of multiple or compat hashs (N-hash or 2-hash?). I am curious about the pack format and directory structure for loose objects. It seems there needs to be a single hash chosen for loose object filenames, and auxilliary hashes will need hash to hash map to go from a compat hash to new hash.

I have been reading the code, and it seems like it is going to be a challenge to change to support more than one hash concurrently. My observation is the content addressable storage layer could do with being a little more abstract, as there seems to be a lot of code that seperately computes hashes by accessing the hash algorithms directly versus going through an abstract content-addressable storage layer, like the VFS in Linux.

In any case, I hope you find this benchmark data useful.

Regards,

Michael

[1] https://en.wikipedia.org/wiki/Length_extension_attack