5 ms·

I’m already seeing a lot of discussion both here and over at LWN about which hash algorithm to use. The Git team made the right choice: SHA2-256 is the best ch

I’m already seeing a lot of discussion both here and over at LWN about which hash algorithm to use. The Git team made the right choice: SHA2-256 is the best choice here; it has been around for 19 years and is still secure, in the sense that there are no known attacks against it. Both BLAKE[2/3] and SHA-3 (Keccak) have been around for 12 years and are both secure; just as BLAKE2 and BLAKE3 are faster reduced round variants of BLAKE, Keccak/SHA-3 has the official faster reduced round Kangaroo12 and Marsupilami14 variants. BLAKE is faster when using software to perform the hash; Keccak is faster when using hardware to perform the hash. I prefer the Keccak approach because it gives us more room for improved performance once CPU makers create specialized instructions to run it, while being fast enough in software. And, yes, SHA-3 has the advantage of being the official successor to SHA-2.

jayflux 7y ago
> BLAKE is faster when using software to perform the hash Is BLAKE 3 still faster than sha-256 when using the cpu speciliazed instructions? I think most modern desktop CPUs has built-in instructions for SHA256. I’m guessing when people compare BLAKE 3 to SHA 256 they’re comparing software to software, but this wouldn’t be the case in reality?
- strenholme 7y ago
  I haven’t seen any benchmarks for BLAKE3 vs. the Intel/AMD SHA extensions. My guess is that Intel hardware accelerated SHA-256 will be faster than BLAKE3 running in software for most real world uses. I can tell you this much: It is only with Ice Lake, which was released in the last year, that mainstream Intel chips finally got native hi speed SHA-NI support. Coffee Lake and Comet Lake, which are still the CPUs in a lot of new laptops being sold right now, do not support SHA-NI.
  - wahern 7y ago
    AMD Zen supports SHA extensions across all SKUs. Here are `openssl speed` numbers on an AMD EPYC 3201: type 16 bytes 64 bytes 256 bytes 1024 bytes 8192 bytes 16384 bytes blake2s256 46720.33k 187461.21k 305314.65k 373840.55k 398207.66k 401528.15k blake2b512 38423.44k 155318.81k 422325.08k 592401.75k 674843.31k 681743.70k sha256 84620.44k 279840.47k 723573.76k 1199678.81k 1484693.50k 1510484.65k sha512 33854.38k 135674.20k 275343.70k 444872.36k 545802.92k 554166.95k sha3-256 26146.35k 103860.27k 253944.92k 308119.21k 347477.33k 351906.47k sha3-512 26349.83k 105590.85k 144236.03k 173082.62k 189448.19k 189814.10k It's possible that Blake3 might be faster than accelerated SHA-256 on large inputs, where Blake3 can maximally leverage its SIMD friendliness. OTOH, Blake3 really pushes the envelope in terms of minimal security margin. Performance isn't everything. SHA-3 is so slow because NIST wanted a failsafe. OpenSSL info: OpenSSL 1.1.1c 28 May 2019 built on: Tue Aug 20 11:46:33 2019 UTC options:bn(64,64) rc4(8x,int) des(int) aes(partial) blowfish(ptr) compiler: gcc -fPIC -pthread -m64 -Wa,--noexecstack -Wall -Wa,--noexecstack -g -O2 -fdebug-prefix-map=/build/openssl-D7S1fy/openssl-1.1.1c=. -fstack-protector-strong -Wformat -Werror=format-security -DOPENSSL_USE_NODELETE -DL_ENDIAN -DOPENSSL_PIC -DOPENSSL_CPUID_OBJ -DOPENSSL_IA32_SSE2 -DOPENSSL_BN_ASM_MONT -DOPENSSL_BN_ASM_MONT5 -DOPENSSL_BN_ASM_GF2m -DSHA1_ASM -DSHA256_ASM -DSHA512_ASM -DKECCAK1600_ASM -DRC4_ASM -DMD5_ASM -DAES_ASM -DVPAES_ASM -DBSAES_ASM -DGHASH_ASM -DECP_NISTZ256_ASM -DX25519_ASM -DPOLY1305_ASM -DNDEBUG -Wdate-time -D_FORTIFY_SOURCE=2 NOTE: /proc/cpuinfo shows sha_ni detection, and the apt-get source of this version of OpenSSL confirms SHA extension support in the source code, but I didn't confirm that it was actually being used at runtime.
    - strenholme 7y ago
      Assuming Blake3 will be across the board 43% faster (7 instead of 10 rounds) than 32-bit blake2s256, we would get: Blake3 SHA-256 66743 84620 Tiny 534057 1199679 Medium (1024 bytes) 573611 1510485 Largeish (16384 bytes) This is based on the parent’s numbers with a fudge factor to account for Blake3 being a faster version of blake2s256 (i.e. the 32-bit version of Blake2 which is the only version in Blake3) Of course, this does take in to account that Blake3 has tree hashing and other modes which scale better to multiple cores. (Edit: update figures; I need to scale up Blake2s256 not Blake2b512)
      - oconnor663 7y ago
        The BLAKE3 tree mode also takes advantage of SIMD parallelism on a single core, which ends up being a larger effect than the reduced number of rounds. At 2-4 KiB of input (depending on the implementation) it's 2x faster than BLAKE2s on my laptop. Where AVX2 and AVX-512 are supported, those kick in at 8 KiB and 16 KiB of input respectively, widening the difference further. The red bar chart at https://github.com/BLAKE3-team/BLAKE3 https://github.com/BLAKE3-team/BLAKE3 is a single-threaded measurement on a machine that supports AVX-512.
- ptomato 7y ago
  On my machine with sha extensions, blake3 is about 15% faster (single threaded in both cases) than sha256.
  - abecedarius 7y ago
    Also, Blake3 has some kind of advantage in parallelizability, iirc.
    - ptomato 7y ago
      yeah, blake3 multi-threaded is about 11 times faster for me than sha256 single-threaded.
_verandaguy 7y ago
Honest question: what are the use cases in Git where hash computation speed is a meaningful optimization?
- papreclip 7y ago
  less wasted computation means less global warming
- strenholme 7y ago
  It’s actually not a big deal with Git, which is why SHA2-256 is the right choice.
- SQLite 7y ago
  My experience in developing and maintaining Fossil is that the hashing speed is not a factor, unless you are checking in huge JPEGs or MP3s or something. And even then, the relative performance of the various hash algorithms is not enough to worry about.
  - _verandaguy 7y ago
    Thanks for the insight. My intuition was kind of the same, but on modern hardware computing the digest-style (as opposed to cryptographic, slow-by-design) hash is essentially imperceptible for payloads in the low MBs -- and much above that is a use case for LFS.
- loeg 7y ago
  Rewriting all repos from SHA1 to hash-next?
KMag 7y ago
SHA-256 is probably the right choice, but I don't think it's as obvious as you suggest, given SHA-512/256. SHA-512/256 is a standard peer-reviewed and well-studied way to run SHA-512 with a different initial state and then truncate output to 256 bits. This is heavy bikeshedding, but SHA-512/256 would be a more conservative choice than SHA-256. Under standard assumptions, SHA-256 is no weaker than SHA-512. The structure is extremely similar to SHA-256, but a collision on intermediate state requires a collision on all 512 bits of state instead of 256. On most 64-bit CPUs without dedicated hash instructions, SHA-512/256 is faster for messages longer than a couple of blocks, due to processing blocks twice as large in fewer than twice as many operations. Currently, the latest server and laptop CPUs have SHA-256 hardware acceleration but not SHA-512 acceleration. I'm not sure how many phone CPUs support sha256 but not ARMv8.2-SHA extensions (SHA-512). If it weren't for this difference in hardware acceleration, there would be few reasons to use SHA-256. That being said, the current difference in hardware acceleration support probably makes SHA-256 the right choice here.
- strenholme 7y ago
  SHA-512/256 is a lot newer than SHA2-256 (usually called SHA-256, but I prefer the SHA2 prefix to make it clear that it’s a very different beast than SHA3-256), and its speed on 32-bit CPUs is less than optimal, so I don’t see it as being a more conservative choice. In terms of security, it uses the same 19-year-old unbroken algorithm as SHA2-256. I am aware of the length extension issues, but they are not relevant for Git’s use case. In terms of support, SHA-512/256 has, as you mentioned, less hardware acceleration support, and it’s also not supported in a lot of mainstream programs like GNU Coreutils. I also know that some companies mandate using SHA2-256 whenever a cryptographic hash is needed. Git made the right choice with SHA2-256: It’s the most widely supported secure cryptographic hash out there.

jayflux 7y ago

> BLAKE is faster when using software to perform the hash Is BLAKE 3 still faster than sha-256 when using the cpu speciliazed instructions? I think most modern desktop CPUs has built-in instructions for SHA256. I’m guessing when people compare BLAKE 3 to SHA 256 they’re comparing software to software, but this wouldn’t be the case in reality?

strenholme 7y ago
I haven’t seen any benchmarks for BLAKE3 vs. the Intel/AMD SHA extensions. My guess is that Intel hardware accelerated SHA-256 will be faster than BLAKE3 running in software for most real world uses. I can tell you this much: It is only with Ice Lake, which was released in the last year, that mainstream Intel chips finally got native hi speed SHA-NI support. Coffee Lake and Comet Lake, which are still the CPUs in a lot of new laptops being sold right now, do not support SHA-NI.
- wahern 7y ago
  AMD Zen supports SHA extensions across all SKUs. Here are `openssl speed` numbers on an AMD EPYC 3201: type 16 bytes 64 bytes 256 bytes 1024 bytes 8192 bytes 16384 bytes blake2s256 46720.33k 187461.21k 305314.65k 373840.55k 398207.66k 401528.15k blake2b512 38423.44k 155318.81k 422325.08k 592401.75k 674843.31k 681743.70k sha256 84620.44k 279840.47k 723573.76k 1199678.81k 1484693.50k 1510484.65k sha512 33854.38k 135674.20k 275343.70k 444872.36k 545802.92k 554166.95k sha3-256 26146.35k 103860.27k 253944.92k 308119.21k 347477.33k 351906.47k sha3-512 26349.83k 105590.85k 144236.03k 173082.62k 189448.19k 189814.10k It's possible that Blake3 might be faster than accelerated SHA-256 on large inputs, where Blake3 can maximally leverage its SIMD friendliness. OTOH, Blake3 really pushes the envelope in terms of minimal security margin. Performance isn't everything. SHA-3 is so slow because NIST wanted a failsafe. OpenSSL info: OpenSSL 1.1.1c 28 May 2019 built on: Tue Aug 20 11:46:33 2019 UTC options:bn(64,64) rc4(8x,int) des(int) aes(partial) blowfish(ptr) compiler: gcc -fPIC -pthread -m64 -Wa,--noexecstack -Wall -Wa,--noexecstack -g -O2 -fdebug-prefix-map=/build/openssl-D7S1fy/openssl-1.1.1c=. -fstack-protector-strong -Wformat -Werror=format-security -DOPENSSL_USE_NODELETE -DL_ENDIAN -DOPENSSL_PIC -DOPENSSL_CPUID_OBJ -DOPENSSL_IA32_SSE2 -DOPENSSL_BN_ASM_MONT -DOPENSSL_BN_ASM_MONT5 -DOPENSSL_BN_ASM_GF2m -DSHA1_ASM -DSHA256_ASM -DSHA512_ASM -DKECCAK1600_ASM -DRC4_ASM -DMD5_ASM -DAES_ASM -DVPAES_ASM -DBSAES_ASM -DGHASH_ASM -DECP_NISTZ256_ASM -DX25519_ASM -DPOLY1305_ASM -DNDEBUG -Wdate-time -D_FORTIFY_SOURCE=2 NOTE: /proc/cpuinfo shows sha_ni detection, and the apt-get source of this version of OpenSSL confirms SHA extension support in the source code, but I didn't confirm that it was actually being used at runtime.
  - strenholme 7y ago
    Assuming Blake3 will be across the board 43% faster (7 instead of 10 rounds) than 32-bit blake2s256, we would get: Blake3 SHA-256 66743 84620 Tiny 534057 1199679 Medium (1024 bytes) 573611 1510485 Largeish (16384 bytes) This is based on the parent’s numbers with a fudge factor to account for Blake3 being a faster version of blake2s256 (i.e. the 32-bit version of Blake2 which is the only version in Blake3) Of course, this does take in to account that Blake3 has tree hashing and other modes which scale better to multiple cores. (Edit: update figures; I need to scale up Blake2s256 not Blake2b512)
    - oconnor663 7y ago
      The BLAKE3 tree mode also takes advantage of SIMD parallelism on a single core, which ends up being a larger effect than the reduced number of rounds. At 2-4 KiB of input (depending on the implementation) it's 2x faster than BLAKE2s on my laptop. Where AVX2 and AVX-512 are supported, those kick in at 8 KiB and 16 KiB of input respectively, widening the difference further. The red bar chart at https://github.com/BLAKE3-team/BLAKE3 https://github.com/BLAKE3-team/BLAKE3 is a single-threaded measurement on a machine that supports AVX-512.
ptomato 7y ago
On my machine with sha extensions, blake3 is about 15% faster (single threaded in both cases) than sha256.
- abecedarius 7y ago
  Also, Blake3 has some kind of advantage in parallelizability, iirc.
  - ptomato 7y ago
    yeah, blake3 multi-threaded is about 11 times faster for me than sha256 single-threaded.

_verandaguy 7y ago

Honest question: what are the use cases in Git where hash computation speed is a meaningful optimization?

papreclip 7y ago
less wasted computation means less global warming
strenholme 7y ago
It’s actually not a big deal with Git, which is why SHA2-256 is the right choice.
SQLite 7y ago
My experience in developing and maintaining Fossil is that the hashing speed is not a factor, unless you are checking in huge JPEGs or MP3s or something. And even then, the relative performance of the various hash algorithms is not enough to worry about.
- _verandaguy 7y ago
  Thanks for the insight. My intuition was kind of the same, but on modern hardware computing the digest-style (as opposed to cryptographic, slow-by-design) hash is essentially imperceptible for payloads in the low MBs -- and much above that is a use case for LFS.
loeg 7y ago
Rewriting all repos from SHA1 to hash-next?

KMag 7y ago

SHA-256 is probably the right choice, but I don't think it's as obvious as you suggest, given SHA-512/256. SHA-512/256 is a standard peer-reviewed and well-studied way to run SHA-512 with a different initial state and then truncate output to 256 bits. This is heavy bikeshedding, but SHA-512/256 would be a more conservative choice than SHA-256. Under standard assumptions, SHA-256 is no weaker than SHA-512. The structure is extremely similar to SHA-256, but a collision on intermediate state requires a collision on all 512 bits of state instead of 256. On most 64-bit CPUs without dedicated hash instructions, SHA-512/256 is faster for messages longer than a couple of blocks, due to processing blocks twice as large in fewer than twice as many operations. Currently, the latest server and laptop CPUs have SHA-256 hardware acceleration but not SHA-512 acceleration. I'm not sure how many phone CPUs support sha256 but not ARMv8.2-SHA extensions (SHA-512). If it weren't for this difference in hardware acceleration, there would be few reasons to use SHA-256. That being said, the current difference in hardware acceleration support probably makes SHA-256 the right choice here.

strenholme 7y ago
SHA-512/256 is a lot newer than SHA2-256 (usually called SHA-256, but I prefer the SHA2 prefix to make it clear that it’s a very different beast than SHA3-256), and its speed on 32-bit CPUs is less than optimal, so I don’t see it as being a more conservative choice. In terms of security, it uses the same 19-year-old unbroken algorithm as SHA2-256. I am aware of the length extension issues, but they are not relevant for Git’s use case. In terms of support, SHA-512/256 has, as you mentioned, less hardware acceleration support, and it’s also not supported in a lot of mainstream programs like GNU Coreutils. I also know that some companies mandate using SHA2-256 whenever a cryptographic hash is needed. Git made the right choice with SHA2-256: It’s the most widely supported secure cryptographic hash out there.