8 ms·

NIST Selects Winner of Secure Hash Algorithm (SHA-3) Competition

168 points by dchest 14y ago

ChuckMcM 14y ago
I found this overview http://keccak.noekeon.org/ http://keccak.noekeon.org/ quite approachable. Especially the pdf linked here : http://keccak.noekeon.org/Keccak-reference-3.0.pdf http://keccak.noekeon.org/Keccak-reference-3.0.pdf
deleted 14y ago
[deleted]
deleted 14y ago
[deleted]
sp332 14y ago
Here's a competing author's take on the final round of this competition: http://news.ycombinator.com/item?id=4564190 http://news.ycombinator.com/item?id=4564190
- tptacek 14y ago
  I don't think I understand Schneier's point here. This is only the second time (AFAIK) that NIST has held a contest like this to standardize a crypto primitive. In the first contest, there was a clear and urgent need to retire DES. In the case of SHA-2, it was clear going in that there wasn't a "speeds and feeds" problem with SHA so much as there was a gathering unease about the basic design of the family of hashes from which SHA-2 is derived: MD4 and MD5 are broken, and SHA-1 isn't looking long for this world. Meanwhile, hash functions are not as well studied as block ciphers and number theoretic crypto, and the pace of development in hash research is increasing. There is value simply in diversifying the gene pool of hash functions.
  - apawloski 14y ago
    I think it was just a case of Schneier being a bit of his usual contrarian self. But is he correct in his assertion that the security of SHA-3 is not going to be much greater than that of SHA-2? (I don't mean that as a leading question.)
    - tptacek 14y ago
      What does "greater" mean? I buy into the idea that the attack that breaks SHA-2 is unlikely to break SHA-3, and vice versa, and that's apparently a key design goal for the standard.
      - B-Con 14y ago
        "greater" here means that we would think that SHA-2 is easier to break than SHA-3. Technically speaking, it's a guess, but I think that the general consensus is that it is more likely that SHA-2 will be broken before SHA-3.
- kbd 14y ago
  Here are his comments about this announcement: http://www.schneier.com/blog/archives/2012/10/keccak_is_sha-3.html http://www.schneier.com/blog/archives/2012/10/keccak_is_sha-...
  - tptacek 14y ago
    Note that Schneier hedges in a very similar matter about AES, suggesting in _Practical Cryptography_ that XSL attacks made him dubious of AES's long-term security --- or at least, that if you're "paranoid about your data", that you should use Serpent instead of AES/Rijndael.
    - pbsd 14y ago
      Does Schneier really recommend Serpent to avoid XSL-type attacks? As far as I remember, XSL also applied to Serpent.
      - tptacek 14y ago
        Not directly, but his specific concern with AES is XSL, and he suggests Serpent for more security-conscious users.
apawloski 14y ago
At some points throughout the competition, the determination criteria used by NIST were somewhat unusual, with the decision committee stating that "We preferred to be conservative about security, and in some cases did not select algorithms with exceptional performance, largely because something about them made us “nervous,” even though we knew of no clear attack against the full algorithm." http://csrc.nist.gov/groups/ST/hash/sha-3/Round3/documents/Email_Announcing_Finalists.pdf http://csrc.nist.gov/groups/ST/hash/sha-3/Round3/documents/E... [PDF]
- zokier 14y ago
  That is actually bit more interesting in the light of Schneier complaining about SHA3 not being significantly better than SHA2.
tptacek 14y ago
Keccak's (pronounced: ketchup) team includes Joan Daemen, who was also on the Rijndael team, giving him a hand in both AES and SHA-3. Keccak's structure is simple and markedly different from that of MD4, MD5, SHA1, and the SHA-2 family, all of which share a common design pattern called Merkle-Damgard (MD). MD-style hashes chunk their inputs into blocks and tag the last block with a length; they then run in a manner similar to a block cipher, where each block is combined with the previous block after the hash function core is applied. The resulting output of these MD-style hashes is literally the internal state of the hash at the last block; you can take most SHA-2 hashes, for instance, and "feed them back" to the SHA function with more data to generate a continued hash. This gives rise to a common crypto protocol flaw called a "length extension attack". Unlike MD, Keccak uses a design called a "sponge function". It's called a "Sponge" because it splits hash into two distinct stages: one in which the hash function "absorbs" data, applying the hash core function to permute an internal state, and another in which the hash is "squeezed" to produce output (which further permutes the state). Somewhat like a cryptographic PRNG, the security of the hash function is delegated to the confidentiality of the internal state, which isn't disclosed by producing the hash. Furthermore, Keccak's Sponge design derives security by only allowing inputs to directly influence a subset of the internal state bits. Like MD hashes, the inputs are chunked into blocks and fed to the hash algorithm. But each block fed to the hash affects only that block's worth of internal state bits; the remainder of the hash's state (called the "capacity bits") are mixed in with the "outer" bits during the application of the hash core. Here's a picture that may tell the story better: http://tinyurl.com/cryptosponge http://tinyurl.com/cryptosponge Notice how the "M" bits of the input hit only the "r" bits of "outer" state in the hash, while the "c" bits of "capacity" are used only during the "f" function.
- xal 14y ago
  This is a brilliant exponentiation. Could you explain in similar terms how quick hashes like MurmurHash and CityHash work?
  - tsewlliw 14y ago
    I imagine not, as those are not crypto hash functions, and thus have very different design goals.
B-Con 14y ago
A little more detail from NIST here: http://www.nist.gov/itl/csd/sha-100212.cfm http://www.nist.gov/itl/csd/sha-100212.cfm
- dchest 14y ago
  It's the same link.
  - B-Con 14y ago
    Yep. Wrong tab. A different submission did not link to this page and I meant to post there.
tveita 14y ago
My impression is that people, in the absence of obvious (to them) differences in security, will choose a cryptographic function based on speed, which is simple to understand and quantify. Going by the eBASH benchmarks, software implementations of Keccak are mostly the same speed as SHA-2, and for some CPUs it's significantly slower. It does have better throughput/area ratio in hardware, but chip manufacturers are not early adapters. With that in mind I can't see any major push for general SHA-3 adoption unless the SHA-2 family is broken. Still, I'm looking forward to the reading the report.
- Zenst 14y ago
  "Keccak, created by Guido Bertoni, Joan Daemen and Gilles Van Assche of STMicroelectronics and Michaël Peeters of NXP Semiconductors" I don't think there will be any issue with regards to some early adopters. Maybe even a concideration with regards to common hardware usage like smartcards at some level. But whilst your right about SHA-2 not being broken and making the rush to SHA-3 moot, it does not stop marketing types getting sales over SHA-2 only complient. In that it will be marketing and drive for sales and standing out that will drive it into market with all things being as they stand. Besides, everybody likes a plan B to fall back upon.
lifeisstillgood 14y ago
Surely, as tptacek's professional life (you know the one here on HN) is dedicated to proving that the security of the encryption algorithm is mostly incidental to the security of the system as a whole, then I would like the next competition to be about producing reference implementations or similar. Sort of like keyczar but down to the point where all browsers simply incorporate the same approved crypto libraries and Apis, securely use areas of memory without file handles anywhere in the background and all the other good stuff that takes us into a 80% done by default world. I am not saying this isn't good stuff, but as someone struggling to implement a user login properly it would be much nicer to have a template to follow. (and he waits for someone to point to the template ...)
- pjscott 14y ago
  A user login, you say? First, find bcrypt or scrypt bindings for your programming language of choice. Here's one for Python, with some very concise example code: http://www.mindrot.org/projects/py-bcrypt/ http://www.mindrot.org/projects/py-bcrypt/ Store the hashed password that bcrypt gives you in a database somewhere. Make sure your login goes over HTTPS. I think that should cover the basics; do you have any specific questions?
  - lifeisstillgood 14y ago
    What about handling single sign on for multiple applications - what do I put in the cookie if anything? If I am encrypting a cookie what scheme? What key rotation? How many failures of a cookie to decrypt is suspicious What about password reclamation - do I keep the answers to their grandmothers maiden name in the same database? What about adding a new email address to the list of ones I will mail a password reset token to - do I force them to prove ownership of the first email address before adding the second ? Or will a SMS to their phone do? I am sure I am missing a hundred items and none of them are to do with bcrypt vs scrypt. Thus is hard stuff and I am avoiding most of it with the magic words "Mozilla persona" but I still don't know how to do sso well. I can do not badly but not well. Edit: I am being a bit snipy and I apologise but I know I am in deep waters and would be happier if NIST were producing reference implementations. Perhaps actually they have - there is kerberos. If you want a key visit room 303 with your passport
gourneau 14y ago
Why is the Bid/Ask spread so high right now for STMs stock? http://finance.yahoo.com/q?d=t&s=STM http://finance.yahoo.com/q?d=t&s=STM

168 points by dchest 14y ago

I found this overview http://keccak.noekeon.org/ http://keccak.noekeon.org/ quite approachable. Especially the pdf linked here : http://keccak.noekeon.org/Keccak-reference-3.0.pdf http://keccak.noekeon.org/Keccak-reference-3.0.pdf

deleted 14y ago

[deleted]

deleted 14y ago

[deleted]

sp332 14y ago

Here's a competing author's take on the final round of this competition: http://news.ycombinator.com/item?id=4564190 http://news.ycombinator.com/item?id=4564190

tptacek 14y ago
I don't think I understand Schneier's point here. This is only the second time (AFAIK) that NIST has held a contest like this to standardize a crypto primitive. In the first contest, there was a clear and urgent need to retire DES. In the case of SHA-2, it was clear going in that there wasn't a "speeds and feeds" problem with SHA so much as there was a gathering unease about the basic design of the family of hashes from which SHA-2 is derived: MD4 and MD5 are broken, and SHA-1 isn't looking long for this world. Meanwhile, hash functions are not as well studied as block ciphers and number theoretic crypto, and the pace of development in hash research is increasing. There is value simply in diversifying the gene pool of hash functions.
- apawloski 14y ago
  I think it was just a case of Schneier being a bit of his usual contrarian self. But is he correct in his assertion that the security of SHA-3 is not going to be much greater than that of SHA-2? (I don't mean that as a leading question.)
  - tptacek 14y ago
    What does "greater" mean? I buy into the idea that the attack that breaks SHA-2 is unlikely to break SHA-3, and vice versa, and that's apparently a key design goal for the standard.
    - B-Con 14y ago
      "greater" here means that we would think that SHA-2 is easier to break than SHA-3. Technically speaking, it's a guess, but I think that the general consensus is that it is more likely that SHA-2 will be broken before SHA-3.
kbd 14y ago
Here are his comments about this announcement: http://www.schneier.com/blog/archives/2012/10/keccak_is_sha-3.html http://www.schneier.com/blog/archives/2012/10/keccak_is_sha-...
- tptacek 14y ago
  Note that Schneier hedges in a very similar matter about AES, suggesting in _Practical Cryptography_ that XSL attacks made him dubious of AES's long-term security --- or at least, that if you're "paranoid about your data", that you should use Serpent instead of AES/Rijndael.
  - pbsd 14y ago
    Does Schneier really recommend Serpent to avoid XSL-type attacks? As far as I remember, XSL also applied to Serpent.
    - tptacek 14y ago
      Not directly, but his specific concern with AES is XSL, and he suggests Serpent for more security-conscious users.

apawloski 14y ago

At some points throughout the competition, the determination criteria used by NIST were somewhat unusual, with the decision committee stating that "We preferred to be conservative about security, and in some cases did not select algorithms with exceptional performance, largely because something about them made us “nervous,” even though we knew of no clear attack against the full algorithm." http://csrc.nist.gov/groups/ST/hash/sha-3/Round3/documents/Email_Announcing_Finalists.pdf http://csrc.nist.gov/groups/ST/hash/sha-3/Round3/documents/E... [PDF]

zokier 14y ago
That is actually bit more interesting in the light of Schneier complaining about SHA3 not being significantly better than SHA2.

tptacek 14y ago

Keccak's (pronounced: ketchup) team includes Joan Daemen, who was also on the Rijndael team, giving him a hand in both AES and SHA-3. Keccak's structure is simple and markedly different from that of MD4, MD5, SHA1, and the SHA-2 family, all of which share a common design pattern called Merkle-Damgard (MD). MD-style hashes chunk their inputs into blocks and tag the last block with a length; they then run in a manner similar to a block cipher, where each block is combined with the previous block after the hash function core is applied. The resulting output of these MD-style hashes is literally the internal state of the hash at the last block; you can take most SHA-2 hashes, for instance, and "feed them back" to the SHA function with more data to generate a continued hash. This gives rise to a common crypto protocol flaw called a "length extension attack". Unlike MD, Keccak uses a design called a "sponge function". It's called a "Sponge" because it splits hash into two distinct stages: one in which the hash function "absorbs" data, applying the hash core function to permute an internal state, and another in which the hash is "squeezed" to produce output (which further permutes the state). Somewhat like a cryptographic PRNG, the security of the hash function is delegated to the confidentiality of the internal state, which isn't disclosed by producing the hash. Furthermore, Keccak's Sponge design derives security by only allowing inputs to directly influence a subset of the internal state bits. Like MD hashes, the inputs are chunked into blocks and fed to the hash algorithm. But each block fed to the hash affects only that block's worth of internal state bits; the remainder of the hash's state (called the "capacity bits") are mixed in with the "outer" bits during the application of the hash core. Here's a picture that may tell the story better: http://tinyurl.com/cryptosponge http://tinyurl.com/cryptosponge Notice how the "M" bits of the input hit only the "r" bits of "outer" state in the hash, while the "c" bits of "capacity" are used only during the "f" function.

xal 14y ago
This is a brilliant exponentiation. Could you explain in similar terms how quick hashes like MurmurHash and CityHash work?
- tsewlliw 14y ago
  I imagine not, as those are not crypto hash functions, and thus have very different design goals.

B-Con 14y ago

A little more detail from NIST here: http://www.nist.gov/itl/csd/sha-100212.cfm http://www.nist.gov/itl/csd/sha-100212.cfm

dchest 14y ago
It's the same link.
- B-Con 14y ago
  Yep. Wrong tab. A different submission did not link to this page and I meant to post there.

tveita 14y ago

My impression is that people, in the absence of obvious (to them) differences in security, will choose a cryptographic function based on speed, which is simple to understand and quantify. Going by the eBASH benchmarks, software implementations of Keccak are mostly the same speed as SHA-2, and for some CPUs it's significantly slower. It does have better throughput/area ratio in hardware, but chip manufacturers are not early adapters. With that in mind I can't see any major push for general SHA-3 adoption unless the SHA-2 family is broken. Still, I'm looking forward to the reading the report.

Zenst 14y ago
"Keccak, created by Guido Bertoni, Joan Daemen and Gilles Van Assche of STMicroelectronics and Michaël Peeters of NXP Semiconductors" I don't think there will be any issue with regards to some early adopters. Maybe even a concideration with regards to common hardware usage like smartcards at some level. But whilst your right about SHA-2 not being broken and making the rush to SHA-3 moot, it does not stop marketing types getting sales over SHA-2 only complient. In that it will be marketing and drive for sales and standing out that will drive it into market with all things being as they stand. Besides, everybody likes a plan B to fall back upon.

lifeisstillgood 14y ago

Surely, as tptacek's professional life (you know the one here on HN) is dedicated to proving that the security of the encryption algorithm is mostly incidental to the security of the system as a whole, then I would like the next competition to be about producing reference implementations or similar. Sort of like keyczar but down to the point where all browsers simply incorporate the same approved crypto libraries and Apis, securely use areas of memory without file handles anywhere in the background and all the other good stuff that takes us into a 80% done by default world. I am not saying this isn't good stuff, but as someone struggling to implement a user login properly it would be much nicer to have a template to follow. (and he waits for someone to point to the template ...)

pjscott 14y ago
A user login, you say? First, find bcrypt or scrypt bindings for your programming language of choice. Here's one for Python, with some very concise example code: http://www.mindrot.org/projects/py-bcrypt/ http://www.mindrot.org/projects/py-bcrypt/ Store the hashed password that bcrypt gives you in a database somewhere. Make sure your login goes over HTTPS. I think that should cover the basics; do you have any specific questions?
- lifeisstillgood 14y ago
  What about handling single sign on for multiple applications - what do I put in the cookie if anything? If I am encrypting a cookie what scheme? What key rotation? How many failures of a cookie to decrypt is suspicious What about password reclamation - do I keep the answers to their grandmothers maiden name in the same database? What about adding a new email address to the list of ones I will mail a password reset token to - do I force them to prove ownership of the first email address before adding the second ? Or will a SMS to their phone do? I am sure I am missing a hundred items and none of them are to do with bcrypt vs scrypt. Thus is hard stuff and I am avoiding most of it with the magic words "Mozilla persona" but I still don't know how to do sso well. I can do not badly but not well. Edit: I am being a bit snipy and I apologise but I know I am in deep waters and would be happier if NIST were producing reference implementations. Perhaps actually they have - there is kerberos. If you want a key visit room 303 with your passport

gourneau 14y ago

Why is the Bid/Ask spread so high right now for STMs stock? http://finance.yahoo.com/q?d=t&s=STM http://finance.yahoo.com/q?d=t&s=STM