8 ms·

> SHA-3 did introduce something useful: extendable output functions Much more than that! Keccak (SHA-3) introduced the Sponge construction. This goes _way_ fu

by remcob 9y ago

> SHA-3 did introduce something useful: extendable output functions Much more than that! Keccak (SHA-3) introduced the Sponge construction. This goes _way_ further than extendable output functions: It allows you to build all the symmetric cryptographic primitives from one basic element! This means: hashes, PRNGs, MACs, encryption, AEAD, etc. The only thing you need that looks like crypto code is a single permutation function. This significantly reduces the amount of security critical code to write. If you talk about hardware implementations, the permutation function takes less die space than SHA2, and optimizes all these primitives. The sponge construction and all it's derivatives are proven secure assuming the permutation function is. And assuming SHA3 is secure, the permutation function is too. The alternative, the Merkle–Damgård construction, has a bunch of known problems. It's also used by pretty much every thing else, so it made sense to diversify. Honestly, I'm a bit sad by the reputation SHA-3 is getting. It is an eye-opening elegant design that makes all previous crypto look overly complex.

kobeya 9y ago
Replying here because you said most of the things I was going to say. This article just makes me sad -- Keccak was chosen for SHA-3 specifically because it turned out SHA-2 wasn't as broken as we feared, and although slow Keccak brings to the table cryptographic diversity and the slew of cool things that can be done with a sponge construction that are now possible using standard cryptographic primitives. NIST made clear that by the time of finalist selection, the point of SHA-3 was NOT to replace SHA-2. OP should know better.
- karaziox 9y ago
  But NIST didn't make that clear. The thing they made clear is in fact the exact opposite and the OP mentions it. They called it SHA-3, saying to the world that this was a better SHA-2. If they wanted to make clear that SHA-3 wasn't to replace SHA-2, they should really have named it something else. Now everybody not knowledgeable to the details will sadly assume the 3 is better than the 2.
  - Spooky23 9y ago
    3 doesn't imply better, just n+1. People who aren't sweating the details aren't the intended audience for NIST.
  - baby 9y ago
    It is better.
  - kobeya 9y ago
    They said it explicitly ehen they announced the winner.
- dchest 9y ago
  NIST made clear that by the time of finalist selection, the point of SHA-3 was NOT to replace SHA-2. OP should know better. That's exactly what this post is about. That we shouldn't replace SHA-2 with SHA-3, just what NIST ordered :)
arghwhat 9y ago
A good and simple example of a Keccak benefit is the KMAC, which is a lot simpler than the construct HMAC needed by the Merkle-Damgård family of hashes. But the article is right that newer crypto, or more crypto, is not necessarily a good thing. It is also true that there is no need for people to rush to Keccak - SHA-256 and SHA-512 are not broken. It is mostly an interesting function for development of new cryptographic constructs.
- tptacek 9y ago
  It is simpler, but how meaningful is that in practice? HMAC is universally available in crypto libraries, far more so than SHA-3 is, and since HMAC needs to interoperate (even more so than ciphers do), it's practically never botched in code. I sort of object to the idea that HMAC is complicated, also. It's more complicated than KMAC which barely deserves a name, but any intern can implement HMAC reliably from the diagram on the Wikipedia page. Hash twice, domain-separating each hash with a simple constant. Done. The only implementation flaw stemming from HMAC in real systems is shared by KMAC (variable-time comparison functions).
  - arghwhat 9y ago
    People still occasionally implement HMAC as `H(K||msg)` or `H(msg||K)`, use defective AES modes, use IV's and nonces inappropriately, use ARC4, use MD5, and use SHA-1. Pretty sure a quick Wikipedia read would have stopped Adobe from DES encrypting passwords as well. Simpler means less likely to misunderstand or fuck up, which is a good property to have. I did also point out that it is mostly interesting for development of new constructs. There's very little point in replacing a working, properly implemented HMAC with a KMAC at this point. ... In the future, however, Keccak may be used for more constructs (aead, for example), at which point a shared "core" for all the crypto you use would be an interesting thing to have, reducing the amount of trusted constructs, sharing optimizations (handwritten asm or hw), and so forth. At that point, migrating would be a sensible thing to do.
tptacek 9y ago
None of these are good reasons to build SHA-3 into a design today, which is the point of the post. He's not criticizing SHA-3's design; pretty much everyone thinks it's interesting and valuable. The point is that the resulting standard doesn't have a lot of immediate practical benefit for real systems.
- baby 9y ago
  I don't think that's true. TuppleHash is THE solution for fingerprints. SHAKE is useful for really a lot of different purposes. Imo self made protocols could really benefit from STROBE today as well.
  - npscalar 9y ago
    And all the SHA-3-derived functions in SP 800-185. For instance, ParallelHash is super fast and a NIST standard.
snakeanus 9y ago
> It allows you to build all the symmetric cryptographic primitives from one basic element! This means: hashes, PRNGs, MACs, encryption, AEAD, etc Isn't this true for most cryptographic hash functions? MAC with HMAC or H(key || m), encryption with a CTR-like mode on top of the MAC, etc.
- tptacek 9y ago
  Observe also that Chapoly, which is built on a stream cipher generated from a hash running in counter mode, written by basically one of the pioneers of ciphers-from-hash-constructions, does not use its hash core as its MAC; it's simply faster to use a polynomial MAC.
  - remcob 9y ago
    With a sponge construction the AEAD is a one-pass operation. You feed plaintext in, out comes ciphertext. In the end you crank it one more time and out comes the MAC/tag. This is unlike other constructions, where you need to go over the data twice, with two different crypto algorithms (encryption + mac) that may or may not share a core component.
    - tptacek 9y ago
      OCB does the same thing, without a sponge construction.
    - baby 9y ago
      This is interesting, I've always seen it as bad because you had to decrypt first, and then you could verify the tag. But now I understand that this also allows you to have a one-pass operation.
- remcob 9y ago
  True, the symmetric primitives are sort of interchangeable, but I'd like to see how to build an AEAD using hash functions that doesn't require you process the data twice. I don't think it can be easily done, if at all. It certainly won't do to combine a HMAC with a CTR-mode encryption. Keccak allows for very simple and efficient implementations of all these primitives. > H(key ‖ m) This is insecure for SHA2 (length extension). However, it is secure when done with SHA3. In fact, it's pretty much how you construct a MAC from it, that's how natural it is. HMAC was invented specifically to deal with the shortcomings of SHA2 and predecessors. For reference, it is H(key ⊕ opad, H(key ⊕ ipad, m)), where opad = 0x5C… and ipad = 0x36…. Compare that with the above and you'll see what I mean with simple and efficient.
DennisP 9y ago
Fwiw, Ethereum uses Keccak for pretty much all hashes other than the proof of work (which uses an ASIC-resistant function).
- baby 9y ago
  Looks like Chain does as well: https://chain.com/docs/1.1/protocol/specifications/data#sha3 https://chain.com/docs/1.1/protocol/specifications/data#sha3
agl 9y ago
If I may (hopefully accurately) summarise your argument: the sponge construction means that we could just implement a single permutation in hardware / optimised software and build everything from it, thus saving die area / code size, and complexity. But deciding to skip SHA-3 doesn't preclude any of that. SHA-3 is the hash standard itself, and even the Keccak team appear to be pushing K12 rather than SHA-3. It seems unlikely that a full set of primitives built around the Keccak permutation would choose to use the SHA-3 parameters at this point. Indeed, SHA-3 adoption might inhibit that ecosystem by pushing towards those bad parameters. (I think there's wide agreement that SHA-3 is too conservative.) On the other hand, you might want SHA-3 because you believe that it'll result in hardware implementations of the permutation and you hope that they'll be flexible enough to support what you /really/ want to do with it. I'm not sure that would be the best approach even if your goal was to move to a permutation-based world. Instead I would nail down the whole family as you would like to see them and use small chips to try and push it. K12 is probably a step in the right direction.
- baby 9y ago
  I agree with you. But at the same time I wouldn't toss SHA-3 which is the answer for many applications. If you're agile and you know what you're doing sure. But for people who don't know what they are doing, following the NIST standard is a safe decision. In 20 years maybe we'll get hardware support for keccak-f. In the mean time we can get excited at the idea of most of your crypto primitives (kdf, prng, aead, hash, ...) being built on top of a single, simple, short and well audited implementation of keccak-f.
  - stouset 9y ago
    SHA-3 is currently a reasonable choice for effectively zero real world use-cases. SHA-2 has many advantages over it, and I can't think of a single disadvantage. SHA-3 has practical value as a moderately well-analyzed cipher in the event of rapid catastrophic cryptanalysis of SHA-2, but barring that kind of event its real value is in the general theoretical advancement of sponge constructions.
    - 9y ago
baby 9y ago
I'll add that Keccak brought the duplex construction as well! Root to keyak, ketje and Strobe!
__manuels__ 9y ago
Another advantage is that SHA-3 just uses AND, XOR, ROT, NOT, but not SHR (logical shift right) which allows for much easier formal analysis of the algorithm!
- baby 9y ago
  That's not true: https://github.com/gvanas/KeccakCodePackage/blob/master/Standalone/CompactFIPS202/Keccak-readable-and-compact.c#L183 https://github.com/gvanas/KeccakCodePackage/blob/master/Stan...
  - koenigdavidmj 9y ago
    Which is ROT(ate), one of the listed options, even though you have to express it with shifts when writing C.
    - baby 9y ago
      I'm not sure I understand what you two mean. 1) How does not having SHR makes it easier to audit? 2) how are sha-3 implementations actually using SHR not making the parent's comment moot?
      - an27 9y ago
        GP disputed SHR is used in the snippet you highlighted.
      - remcob 9y ago
        A rotate operation is invertible, a logic shift by itself is not. Another fun one is x ^= x >> n with n some strictly positive constant, this is also invertible. It's used a lot in the murmurhash family of non-cryptograhic hash functions.
        oh_sigh 9y ago
        Why does invertibility matter? AND and OR are not invertible, but they are used?

by remcob 9y ago

kobeya 9y ago

Replying here because you said most of the things I was going to say. This article just makes me sad -- Keccak was chosen for SHA-3 specifically because it turned out SHA-2 wasn't as broken as we feared, and although slow Keccak brings to the table cryptographic diversity and the slew of cool things that can be done with a sponge construction that are now possible using standard cryptographic primitives. NIST made clear that by the time of finalist selection, the point of SHA-3 was NOT to replace SHA-2. OP should know better.

karaziox 9y ago
But NIST didn't make that clear. The thing they made clear is in fact the exact opposite and the OP mentions it. They called it SHA-3, saying to the world that this was a better SHA-2. If they wanted to make clear that SHA-3 wasn't to replace SHA-2, they should really have named it something else. Now everybody not knowledgeable to the details will sadly assume the 3 is better than the 2.
- Spooky23 9y ago
  3 doesn't imply better, just n+1. People who aren't sweating the details aren't the intended audience for NIST.
- baby 9y ago
  It is better.
- kobeya 9y ago
  They said it explicitly ehen they announced the winner.
dchest 9y ago
NIST made clear that by the time of finalist selection, the point of SHA-3 was NOT to replace SHA-2. OP should know better. That's exactly what this post is about. That we shouldn't replace SHA-2 with SHA-3, just what NIST ordered :)

arghwhat 9y ago

A good and simple example of a Keccak benefit is the KMAC, which is a lot simpler than the construct HMAC needed by the Merkle-Damgård family of hashes. But the article is right that newer crypto, or more crypto, is not necessarily a good thing. It is also true that there is no need for people to rush to Keccak - SHA-256 and SHA-512 are not broken. It is mostly an interesting function for development of new cryptographic constructs.

tptacek 9y ago
It is simpler, but how meaningful is that in practice? HMAC is universally available in crypto libraries, far more so than SHA-3 is, and since HMAC needs to interoperate (even more so than ciphers do), it's practically never botched in code. I sort of object to the idea that HMAC is complicated, also. It's more complicated than KMAC which barely deserves a name, but any intern can implement HMAC reliably from the diagram on the Wikipedia page. Hash twice, domain-separating each hash with a simple constant. Done. The only implementation flaw stemming from HMAC in real systems is shared by KMAC (variable-time comparison functions).
- arghwhat 9y ago
  People still occasionally implement HMAC as `H(K||msg)` or `H(msg||K)`, use defective AES modes, use IV's and nonces inappropriately, use ARC4, use MD5, and use SHA-1. Pretty sure a quick Wikipedia read would have stopped Adobe from DES encrypting passwords as well. Simpler means less likely to misunderstand or fuck up, which is a good property to have. I did also point out that it is mostly interesting for development of new constructs. There's very little point in replacing a working, properly implemented HMAC with a KMAC at this point. ... In the future, however, Keccak may be used for more constructs (aead, for example), at which point a shared "core" for all the crypto you use would be an interesting thing to have, reducing the amount of trusted constructs, sharing optimizations (handwritten asm or hw), and so forth. At that point, migrating would be a sensible thing to do.

tptacek 9y ago

None of these are good reasons to build SHA-3 into a design today, which is the point of the post. He's not criticizing SHA-3's design; pretty much everyone thinks it's interesting and valuable. The point is that the resulting standard doesn't have a lot of immediate practical benefit for real systems.

baby 9y ago
I don't think that's true. TuppleHash is THE solution for fingerprints. SHAKE is useful for really a lot of different purposes. Imo self made protocols could really benefit from STROBE today as well.
- npscalar 9y ago
  And all the SHA-3-derived functions in SP 800-185. For instance, ParallelHash is super fast and a NIST standard.

snakeanus 9y ago

> It allows you to build all the symmetric cryptographic primitives from one basic element! This means: hashes, PRNGs, MACs, encryption, AEAD, etc Isn't this true for most cryptographic hash functions? MAC with HMAC or H(key || m), encryption with a CTR-like mode on top of the MAC, etc.

tptacek 9y ago
Observe also that Chapoly, which is built on a stream cipher generated from a hash running in counter mode, written by basically one of the pioneers of ciphers-from-hash-constructions, does not use its hash core as its MAC; it's simply faster to use a polynomial MAC.
- remcob 9y ago
  With a sponge construction the AEAD is a one-pass operation. You feed plaintext in, out comes ciphertext. In the end you crank it one more time and out comes the MAC/tag. This is unlike other constructions, where you need to go over the data twice, with two different crypto algorithms (encryption + mac) that may or may not share a core component.
  - tptacek 9y ago
    OCB does the same thing, without a sponge construction.
  - baby 9y ago
    This is interesting, I've always seen it as bad because you had to decrypt first, and then you could verify the tag. But now I understand that this also allows you to have a one-pass operation.
remcob 9y ago
True, the symmetric primitives are sort of interchangeable, but I'd like to see how to build an AEAD using hash functions that doesn't require you process the data twice. I don't think it can be easily done, if at all. It certainly won't do to combine a HMAC with a CTR-mode encryption. Keccak allows for very simple and efficient implementations of all these primitives. > H(key ‖ m) This is insecure for SHA2 (length extension). However, it is secure when done with SHA3. In fact, it's pretty much how you construct a MAC from it, that's how natural it is. HMAC was invented specifically to deal with the shortcomings of SHA2 and predecessors. For reference, it is H(key ⊕ opad, H(key ⊕ ipad, m)), where opad = 0x5C… and ipad = 0x36…. Compare that with the above and you'll see what I mean with simple and efficient.

DennisP 9y ago

Fwiw, Ethereum uses Keccak for pretty much all hashes other than the proof of work (which uses an ASIC-resistant function).

baby 9y ago
Looks like Chain does as well: https://chain.com/docs/1.1/protocol/specifications/data#sha3 https://chain.com/docs/1.1/protocol/specifications/data#sha3

agl 9y ago

If I may (hopefully accurately) summarise your argument: the sponge construction means that we could just implement a single permutation in hardware / optimised software and build everything from it, thus saving die area / code size, and complexity. But deciding to skip SHA-3 doesn't preclude any of that. SHA-3 is the hash standard itself, and even the Keccak team appear to be pushing K12 rather than SHA-3. It seems unlikely that a full set of primitives built around the Keccak permutation would choose to use the SHA-3 parameters at this point. Indeed, SHA-3 adoption might inhibit that ecosystem by pushing towards those bad parameters. (I think there's wide agreement that SHA-3 is too conservative.) On the other hand, you might want SHA-3 because you believe that it'll result in hardware implementations of the permutation and you hope that they'll be flexible enough to support what you /really/ want to do with it. I'm not sure that would be the best approach even if your goal was to move to a permutation-based world. Instead I would nail down the whole family as you would like to see them and use small chips to try and push it. K12 is probably a step in the right direction.

baby 9y ago
I agree with you. But at the same time I wouldn't toss SHA-3 which is the answer for many applications. If you're agile and you know what you're doing sure. But for people who don't know what they are doing, following the NIST standard is a safe decision. In 20 years maybe we'll get hardware support for keccak-f. In the mean time we can get excited at the idea of most of your crypto primitives (kdf, prng, aead, hash, ...) being built on top of a single, simple, short and well audited implementation of keccak-f.
- stouset 9y ago
  SHA-3 is currently a reasonable choice for effectively zero real world use-cases. SHA-2 has many advantages over it, and I can't think of a single disadvantage. SHA-3 has practical value as a moderately well-analyzed cipher in the event of rapid catastrophic cryptanalysis of SHA-2, but barring that kind of event its real value is in the general theoretical advancement of sponge constructions.
  - 9y ago

baby 9y ago

I'll add that Keccak brought the duplex construction as well! Root to keyak, ketje and Strobe!

__manuels__ 9y ago

Another advantage is that SHA-3 just uses AND, XOR, ROT, NOT, but not SHR (logical shift right) which allows for much easier formal analysis of the algorithm!

baby 9y ago
That's not true: https://github.com/gvanas/KeccakCodePackage/blob/master/Standalone/CompactFIPS202/Keccak-readable-and-compact.c#L183 https://github.com/gvanas/KeccakCodePackage/blob/master/Stan...
- koenigdavidmj 9y ago
  Which is ROT(ate), one of the listed options, even though you have to express it with shifts when writing C.
  - baby 9y ago
    I'm not sure I understand what you two mean. 1) How does not having SHR makes it easier to audit? 2) how are sha-3 implementations actually using SHR not making the parent's comment moot?
    - an27 9y ago
      GP disputed SHR is used in the snippet you highlighted.
    - remcob 9y ago
      A rotate operation is invertible, a logic shift by itself is not. Another fun one is x ^= x >> n with n some strictly positive constant, this is also invertible. It's used a lot in the murmurhash family of non-cryptograhic hash functions.
      - oh_sigh 9y ago
        Why does invertibility matter? AND and OR are not invertible, but they are used?