16 ms·

Maybe Skip SHA-3

241 points by kungfudoi 9y ago

JoshTriplett 9y ago
SHA-3 does seem to have relatively little to offer by way of incentives to switch. "Just as good" isn't motivation, and any notions of higher cryptographic strength haven't been extensively discussed. "Easier to implement in hardware" will be more compelling when such hardware exists. I'm curious about the statement that SHA-3 is slow; it links to https://www.imperialviolet.org/2016/05/16/agility.html https://www.imperialviolet.org/2016/05/16/agility.html , which doesn't seem related, and matches the previous link. I wonder if that was supposed to link to somewhere else, like http://bench.cr.yp.to/results-sha3.html http://bench.cr.yp.to/results-sha3.html (as linked from https://www.imperialviolet.org/2012/10/21/nist.html https://www.imperialviolet.org/2012/10/21/nist.html )? From that, SHA-3 certainly doesn't run significantly faster than alternatives (variants of BLAKE do indeed outperform it), but it seems roughly on par with SHA-256/SHA-512. But "on par" doesn't give any incentive to switch. I wonder how much relative attention the SHA-3 winner (Keccak) gets compared to other alternatives, like BLAKE?
- agl 9y ago
  Gah, thank you. I did, indeed, mean to link to bench.cr.yp.to. Fixed. (The BLAKE2 page (https://blake2.net/ https://blake2.net/) has a graph too.)
- dom0 9y ago
  > "Easier to implement in hardware" will be more compelling when such hardware exists. Most things are software; from previous experience we know that it basically takes 10 to 15 years between introduction of a primitive (AES and SHA-2 both standardised around 2000; ISA extensions for mainstream CPUs introduced in 2010-2017). From the software PoV SHA-3 would be a rather large regression in performance with a "maybe it's fast by 2030 if Intel is really nice" attached. BLAKE2 on the other hand is an improvement in performance and offers a function that is more modern overall. (E.g. not length-extensible thus low-overhead keyed hash usage, flexible output sizes, tree hashing built-in)
  - mtgx 9y ago
    Yes, perhaps before they choose the next "faster in hardware" crypto algorithm, they also get a commitment from the major chip makers (Intel, AMD, Qualcomm, MediaTek, etc) that they will implement them within let's say 2 years after the contest is over. Otherwise it's just hope that the chip makers will implement it when the algorithms are chosen, and I'm not sure that's good enough after a carefully orchestrated 5-year process of choosing a next-generation algorithm. If they can't get that commitment, then they should choose whatever is faster in software (granted all the other factors are more or less equal).
- jasode 9y ago
  >I'm curious about the statement that SHA-3 is slow; [...] I wonder how much relative attention the SHA-3 winner (Keccak) gets compared to other alternatives, like BLAKE? Coincidentally, I ran a bunch of hash performance benchmarks last week. These were my findings: test: hash a 500MB block of memory. hardware: Intel Core i7-5820K Haswell-E 6-Core 3.3GHz compiler: MSVC2017 (19.10.25019), 32-bit exe: blake2sp - official reference code[1] 153MB/sec SHA3 - Keccak official reference code[2] 12MB/sec SHA3 - rhash sha3[3] 45MB/sec SHA3 - Crypto++ library v5.6.5[4] 57MB/sec SHA256 - Crypto++ 181MB/sec SHA256 - MS Crypto API[5] 113MB/sec SHA1 - MS Crypto API 338MB/sec MD5 - Crypto++ 345MB/sec CRC32 - Crypto++ 323MB/sec The conclusion is that the fastest SHA3 implementation (Crypto++ lib with its assembly language optimizations) is more than 2x-3x slower than SHA256. I can't speak for SHA3 implemented in FPGA/ASIC but as far as C++ compilation targeting x86, it's slow. I've been meaning to try the Intel Compiler to see if it yields different results but haven't gotten around to it yet. Blake2sp is fast. The official reference code is not quite as fast as Crypto++ implementation of SHA256 but it's faster than Microsoft's Crypto API of SHA256. (There are several variants of BLAKE and I chose blake2sp because that's the algorithm WinRAR uses. I think the specific variant of BLAKE that directly competed with Keccack for NIST standardization is slower.) [1] https://github.com/BLAKE2/BLAKE2 https://github.com/BLAKE2/BLAKE2 [2] http://keccak.noekeon.org/files.html http://keccak.noekeon.org/files.html [3] https://github.com/rhash/RHash/blob/master/librhash/sha3.c https://github.com/rhash/RHash/blob/master/librhash/sha3.c [4] https://www.cryptopp.com/ https://www.cryptopp.com/ [5] https://msdn.microsoft.com/en-us/library/ms867086.aspx https://msdn.microsoft.com/en-us/library/ms867086.aspx
  - briansmith 9y ago
    I guess 32-bit x86 performance is maybe not the best benchmark. I think people aren't optimizing for that ISA to the same extent as they are optimizing for x86-64, 64-bit ARMv8, or 32-bit ARM. If you care about performance and you don't have dedicated SHA-256 instructions then on a 64-bit platform you should evaluate SHA-512 as it is much faster. If you only have 256 bits of storage available then truncate its output to 256 bits. IIRC, it's about 1GB/sec on my Haswell laptop.
- pshc 9y ago
  I recently came to believe (correct me if I'm wrong) that the recommended XOFs SHAKE128 and SHAKE256 are actually nice and fast, but often when people talk about SHA-3 they focus on the slower "drop-in replacements" like SHA3-256 which are quite conservative.
  - baby 9y ago
    Yes SHAKE is faster than SHA-3 because of "better" parameter choices.
- baby 9y ago
  Daemen talked about some figures for KangarooTwelve during RWC 2017: * Intel Core i5-4570 (Haswell) 4.15 c/b for short input and 1.44 c/b for long input * Intel Core i5-6500 (Skylake) 3.72 c/b for short input and 1.22 c/b for long input * Intel Xeon Phi 7250 (Knights Landing) 4.56 c/b for short input and 0.74 c/b for long input https://youtu.be/F_nAGS9L97c?t=2451 https://youtu.be/F_nAGS9L97c?t=2451
- npscalar 9y ago
  This page has an interesting speed graph: http://kangarootwelve.org/ http://kangarootwelve.org/
rihegher 9y ago
in short: "SHA-3 should probably not be used. It offers no compelling advantage over SHA-2 and brings many costs."
hackcasual 9y ago
The SHAKE family of functions (and cryptographic sponges in general) are very cool, but like the article says, SHA-3 is weakened by failing to focus on performance. If SHA-2 is sufficiently secure (which looks more and more the case) then a faster SHA-2 would have been a better way of looking at what was wanted out of SHA-3. Faster primitives means more PBKDF rounds, more usage of hashes to secure underlying data.
- tptacek 9y ago
  If you're concerned about the primitives making up your password hash, you shouldn't be using PBKDF2 to begin with; better to use a purpose-built KDF like scrypt, bcrypt, or argon2.
snakeanus 9y ago
> SHA-3 did introduce something useful To me the most useful part of SHA-3 is that you don't need to use HMAC as it is not vulnerable to length extension attacks. Meaning that it's much faster than SHA-2 when used as a MAC construction.
- gcp 9y ago
  But aren't we trying to get away from MACs into authenticated ciphers?
  - tptacek 9y ago
    An authenticated cipher is usually just a composition of a cipher and a MAC.
    - klodolph 9y ago
      That's historically true, but these days I think GCM is the most common. GCM also has hardware support from the CLMUL instruction set available on Intel processors since 2010 and AMD processors since 2011.
      - tptacek 9y ago
        GCM is just a composition of CTR mode and GMAC.
        klodolph 9y ago
        Well, technically you'd get a different result if you applied GMAC after using CTR mode, because the final stage of the GMAC would get a different length value, but the process would be very similar. From a different perspective, GMAC is just GCM without encryption. It's not like GMAC existed and then it was combined with AES to make AES-GCM, it was designed as authenticated encryption and has the ability to encrypt zero bytes while still authenticating other bytes. So no, GCM is not just GMAC + AES.
deleted 9y ago
[deleted]
aicez 9y ago
The assessment that SHA-3's performance is bad completely disregard the results from hardware benchmarking (FPGAs and ASICs). All the hardware results have shown conclusively that Keccak is multiple times faster than SHA-2. While I can't say that the algorithm is going to be supported in HW, with enough usage it might be the case. Edit: Removed my comment regarding BLAKE as it was incorrect.
- Sunset 9y ago
  Isn't this something you don't want? I'd rather use an algo which is painful to do in bulk.
  - sp332 9y ago
    That's helpful for passwords, but most hash applications aren't for passwords. If you're hashing a large file you don't want something super slow, and you don't need to pad out a tiny password into something hard to guess.
- agl 9y ago
  By selecting primitives designed for hardware (AES and GHASH) rather than primitives that use operations that are commonly applicable (ChaCha20 and Poly1305), we've ended up with extra hardware to support AES and GHASH. But it's not clear that was actually a good idea, or just path dependence. ChaCha20, Poly1305, BLAKE2 benefit from improvements that benefit a wide-range of applications, while SHA-3, AES and GHASH do not. Thus the "cost" of high performance support for the former can be amortised over a much wider base.
  - aicez 9y ago
    I suspect that the extra hardware support is not a major concern. This might be because any company that has a true security concern will eventually need to designated an area on its silicon for cryptographic purposes. This area will be security hardened to protect against any side-channel attacks. Also, sharing HW resource for cryptographic purposes is not possible for any device that needs to pass certain security certification. Edit: Typo and additional comment
simias 9y ago
A rather minor point but: >[The diversity of cryptographic primitives] contributes to code-size, which is a worry again in the mobile age In the "mobile age" we use embedded processors with gigabytes worth of RAM and several times the amount of NAND storage, I don't really think a SHA-3 implementation is going to tip the boat over. The author's other points seem very fair though.
- agl 9y ago
  I can confirm that the code size of BoringSSL is something that we worry about for mobile apps. A 50KB increase (which wouldn't be much for an optimised SHA-3) would raise questions. I admit that when I see the 100MB+ size of apps that I have to download, I do wonder why. But I assume that it would be even worse were people not worrying about this stuff.
  - Dylan16807 9y ago
    > A 50KB increase (which wouldn't be much for an optimised SHA-3) would raise questions. Can you elaborate on that? That's orders of magnitude bigger than a naive implementation, and wouldn't fit in L1 cache either.
- mikeash 9y ago
  That massive storage is often still using a heavily constrained data connection. Apple, for example, won't let you download an app over 100MB over cellular data. You want to really try to keep your app under that limit, otherwise a lot of potential users will abandon the app if they discover it while they're not on WiFi.
  - hdhzy 9y ago
    I wonder why is that, I had a shared plan (3 numbers) that gave about 99 GB each month and Apple wouldn't let me download a 100 MB game through LTE?
    - oconnor663 9y ago
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
richdougherty 9y ago
> As I've mentioned before, diversity of cryptographic primitives is expensive. ... exponential number of combinations ... limited developer resources ... It's a good point that diversity is expensive. There's a counter-argument too: if we all decide to use one thing, but it goes wrong - then we're in serious trouble. If we have multiple approaches, then the damage is lessened if one of them turns out to have problems. In other words, I think it's better to have a variety of approaches to manage risk, even if it does impose costs.
- tptacek 9y ago
  The track record on that design strategy is not good. We've been pursuing designs with cryptographic diversity built in for several decades, and the result has been decades of terrible vulnerabilities --- almost none of which have been mitigated by diversity!
  - baby 9y ago
    Have we had some big crypto failures besides "everyone was using md5" and "everyone was using DES"?
    - tptacek 9y ago
      Yes: for instance, the TLS BEAST vulnerability, which affected all the block ciphers in that version of TLS, because the protocol standardized interchangeable ciphers and a message encryption construction based on CBC as separate components. Ironically, when the RC4 attack refinements were published, for awhile sites were forced to choose between a vulnerable CBC implementation and using the vulnerable RC4 cipher. With the exception of MD5 in X.509 certificates and RC4 in TLS, has there been another cryptographic vulnerability that required the retirement of a cipher? SWEET32 is about as close as you come to that, right? And, obviously, there have been many more problems, even just in TLS, than X.509 MD5 and RC4.
      - baby 9y ago
        Wasn't that more because we had not really thought of aead constructions? I mean we didn't even know we had to mac after encrypting. If we had more stream ciphers at the time we would not have been stuck with beast or rc4. Imo sweet32 was just the weak but well-marketed cherry on the top to get rid of the previous generation. We just had the sha-1 collision.
baby 9y ago
I believe this is a good complememt to agl's post with a focus on K12 instead: https://cryptologie.net/article/393/kangarootwelve/ https://cryptologie.net/article/393/kangarootwelve/
matt_wulfeck 9y ago
Why don't we use hash functions that combine the output of two discrete hashing functions and combine the results? It seems to me it's easy to break sha or md5, but what about breaking two fundemantally different algorithms at the same time? Implementation seems as easy as concatenating the two hex outputs into a single string and comparing the results. I'm curious to what others think of this idea.
- agl 9y ago
  It turned out that breaking the combination is SHA-1 and MD-5 is much easier than people expected: https://www.iacr.org/archive/crypto2004/31520306/multicollisions.pdf https://www.iacr.org/archive/crypto2004/31520306/multicollis...
  - tptacek 9y ago
    Shameless plug (this is one of Sean's, though): http://cryptopals.com/sets/7/challenges/52 http://cryptopals.com/sets/7/challenges/52
- JackC 9y ago
  A couple of criticisms I've seen for this idea, as best I understand them as an amateur: (1) It's hard to use a multihash construct correctly. For example, do you want "hash1(message) + hash2(message)" or "hash1(message + hash2(message))" or "hash1(hash2(message))"? The answer is that it depends which features of a hash function matter for your application, and if you pick the wrong one you will have the worst of all worlds instead of the best of all worlds. (Simple example: "md5(password)+scrypt(password)" is a broken way to store passwords, while "sha3(md5(document))" is a broken way to authenticate documents; vice versa would probably be OK.) (2) If you're paranoid, bytes and CPU cycles are (arguably) better spent on extending your best option instead of tacking on less good ones. Breaks tend to come in the form of "it is now feasible to crack a key with length X" or "find collisions with a hash with Y rounds" or whatever, where X and Y were originally picked to strike a balance of security and performance. So if you were going to spend performance on something nonstandard to guard against mathematical breakthroughs, experts might recommend doubling X and Y instead of throwing in a second less-secure cypher. (Although really they'd tell you just to use the standard thing.)
ktta 9y ago
My suggestion after looking around for the best hash function is SHA-256. Not SHA-512, not SHA-512/256. Not even SHA-224 because it offers no performance benefits. BLAKE2 is a good candidate right now considering speed. But SHA-256 instructions will only get more prevalent which will take care of the speed issue. There have been speed comparisons between SHA-256 and BLAKE2 without SHA instructions[1]. BLAKE2 seems like good option then, with the optimized code. But once SHA extensions use hardware instructions, it gets a 5.7x boost which blows BLAKE2 out of the water.[2] There are instructions for SHA-256 in NEON too although I couldn't find any benchmarks. I'd say it'll definitely be faster than BLAKE2 with HW instructions. Combine that with SHA256 being uber popular everywhere, that'll be one less headache. I also doubt SHA-256 will be over thrown in the near future, atleast until SHA-3 instructions become commonplace, which I anticipate will take about a decade from now. [1]: https://news.ycombinator.com/item?id=14357197 https://news.ycombinator.com/item?id=14357197 [2]: https://github.com/randombit/botan/issues/807#issuecomment-270652403 https://github.com/randombit/botan/issues/807#issuecomment-2... EDIT: Looks like SHA-224 might be the best option, considering it has the same core with a truncated output which will make it immune to length-extension attacks.
- tptacek 9y ago
  The advantage to 224 or 512/256 is that they don't expose the full register state of the hash at output and thus, like Blake2 and SHA-3, aren't vulnerable to length-extension attacks: you can (though it would be idiosyncratic to do so) use a simple prefix MAC with them, rather than HMAC.
  - baby 9y ago
    But people don't know that. That's why it is best to just push people towards sha-3 and have the in-house cryptographer decide when sha-2/blake2/kangarootwelve might be relevant for speed purposes.
    - tptacek 9y ago
      I agree that using prefix MACs with SHA-2 is a bad idea, for that reason, but since everyone uses HMAC already and since there are much faster MACs than KMAC, I don't think there's a clear argument for SHA-3 here. I'm just saying, if you're going to recommend one of the SHA-2's, it should probably be one of the truncated ones.
yuhong 9y ago
The preimage strength debacle is probably worth mentioning
dreamthtwasrome 9y ago
Speed isn't a black-and-white panacea property, cost of brute-forcing (ram, cpu, time and money) and other attacks should also be prioritized for a given use-case (ie argon2, scrypt). Fixating on a single, fast algorithm and making it a near universal monoculture makes it easier for well-funded state and corporate entities to reduce their costs to generate a hash collison or do something else nasty because they only have to invest in one kind of possibly cheaper/simpler ASIC building-block. Having several different, but throughly sensible algorithms who's strengths, weaknesses and limitations are well known is a better approach than saying "everyone use X" a-la NESSIE. Users with Paradox of Choice going on can pick the lunch special, AES.

241 points by kungfudoi 9y ago

SHA-3 does seem to have relatively little to offer by way of incentives to switch. "Just as good" isn't motivation, and any notions of higher cryptographic strength haven't been extensively discussed. "Easier to implement in hardware" will be more compelling when such hardware exists. I'm curious about the statement that SHA-3 is slow; it links to https://www.imperialviolet.org/2016/05/16/agility.html https://www.imperialviolet.org/2016/05/16/agility.html , which doesn't seem related, and matches the previous link. I wonder if that was supposed to link to somewhere else, like http://bench.cr.yp.to/results-sha3.html http://bench.cr.yp.to/results-sha3.html (as linked from https://www.imperialviolet.org/2012/10/21/nist.html https://www.imperialviolet.org/2012/10/21/nist.html )? From that, SHA-3 certainly doesn't run significantly faster than alternatives (variants of BLAKE do indeed outperform it), but it seems roughly on par with SHA-256/SHA-512. But "on par" doesn't give any incentive to switch. I wonder how much relative attention the SHA-3 winner (Keccak) gets compared to other alternatives, like BLAKE?

agl 9y ago
Gah, thank you. I did, indeed, mean to link to bench.cr.yp.to. Fixed. (The BLAKE2 page (https://blake2.net/ https://blake2.net/) has a graph too.)
dom0 9y ago
> "Easier to implement in hardware" will be more compelling when such hardware exists. Most things are software; from previous experience we know that it basically takes 10 to 15 years between introduction of a primitive (AES and SHA-2 both standardised around 2000; ISA extensions for mainstream CPUs introduced in 2010-2017). From the software PoV SHA-3 would be a rather large regression in performance with a "maybe it's fast by 2030 if Intel is really nice" attached. BLAKE2 on the other hand is an improvement in performance and offers a function that is more modern overall. (E.g. not length-extensible thus low-overhead keyed hash usage, flexible output sizes, tree hashing built-in)
- mtgx 9y ago
  Yes, perhaps before they choose the next "faster in hardware" crypto algorithm, they also get a commitment from the major chip makers (Intel, AMD, Qualcomm, MediaTek, etc) that they will implement them within let's say 2 years after the contest is over. Otherwise it's just hope that the chip makers will implement it when the algorithms are chosen, and I'm not sure that's good enough after a carefully orchestrated 5-year process of choosing a next-generation algorithm. If they can't get that commitment, then they should choose whatever is faster in software (granted all the other factors are more or less equal).
jasode 9y ago
>I'm curious about the statement that SHA-3 is slow; [...] I wonder how much relative attention the SHA-3 winner (Keccak) gets compared to other alternatives, like BLAKE? Coincidentally, I ran a bunch of hash performance benchmarks last week. These were my findings: test: hash a 500MB block of memory. hardware: Intel Core i7-5820K Haswell-E 6-Core 3.3GHz compiler: MSVC2017 (19.10.25019), 32-bit exe: blake2sp - official reference code[1] 153MB/sec SHA3 - Keccak official reference code[2] 12MB/sec SHA3 - rhash sha3[3] 45MB/sec SHA3 - Crypto++ library v5.6.5[4] 57MB/sec SHA256 - Crypto++ 181MB/sec SHA256 - MS Crypto API[5] 113MB/sec SHA1 - MS Crypto API 338MB/sec MD5 - Crypto++ 345MB/sec CRC32 - Crypto++ 323MB/sec The conclusion is that the fastest SHA3 implementation (Crypto++ lib with its assembly language optimizations) is more than 2x-3x slower than SHA256. I can't speak for SHA3 implemented in FPGA/ASIC but as far as C++ compilation targeting x86, it's slow. I've been meaning to try the Intel Compiler to see if it yields different results but haven't gotten around to it yet. Blake2sp is fast. The official reference code is not quite as fast as Crypto++ implementation of SHA256 but it's faster than Microsoft's Crypto API of SHA256. (There are several variants of BLAKE and I chose blake2sp because that's the algorithm WinRAR uses. I think the specific variant of BLAKE that directly competed with Keccack for NIST standardization is slower.) [1] https://github.com/BLAKE2/BLAKE2 https://github.com/BLAKE2/BLAKE2 [2] http://keccak.noekeon.org/files.html http://keccak.noekeon.org/files.html [3] https://github.com/rhash/RHash/blob/master/librhash/sha3.c https://github.com/rhash/RHash/blob/master/librhash/sha3.c [4] https://www.cryptopp.com/ https://www.cryptopp.com/ [5] https://msdn.microsoft.com/en-us/library/ms867086.aspx https://msdn.microsoft.com/en-us/library/ms867086.aspx
- briansmith 9y ago
  I guess 32-bit x86 performance is maybe not the best benchmark. I think people aren't optimizing for that ISA to the same extent as they are optimizing for x86-64, 64-bit ARMv8, or 32-bit ARM. If you care about performance and you don't have dedicated SHA-256 instructions then on a 64-bit platform you should evaluate SHA-512 as it is much faster. If you only have 256 bits of storage available then truncate its output to 256 bits. IIRC, it's about 1GB/sec on my Haswell laptop.
pshc 9y ago
I recently came to believe (correct me if I'm wrong) that the recommended XOFs SHAKE128 and SHAKE256 are actually nice and fast, but often when people talk about SHA-3 they focus on the slower "drop-in replacements" like SHA3-256 which are quite conservative.
- baby 9y ago
  Yes SHAKE is faster than SHA-3 because of "better" parameter choices.
baby 9y ago
Daemen talked about some figures for KangarooTwelve during RWC 2017: * Intel Core i5-4570 (Haswell) 4.15 c/b for short input and 1.44 c/b for long input * Intel Core i5-6500 (Skylake) 3.72 c/b for short input and 1.22 c/b for long input * Intel Xeon Phi 7250 (Knights Landing) 4.56 c/b for short input and 0.74 c/b for long input https://youtu.be/F_nAGS9L97c?t=2451 https://youtu.be/F_nAGS9L97c?t=2451
npscalar 9y ago
This page has an interesting speed graph: http://kangarootwelve.org/ http://kangarootwelve.org/

rihegher 9y ago

in short: "SHA-3 should probably not be used. It offers no compelling advantage over SHA-2 and brings many costs."

hackcasual 9y ago

The SHAKE family of functions (and cryptographic sponges in general) are very cool, but like the article says, SHA-3 is weakened by failing to focus on performance. If SHA-2 is sufficiently secure (which looks more and more the case) then a faster SHA-2 would have been a better way of looking at what was wanted out of SHA-3. Faster primitives means more PBKDF rounds, more usage of hashes to secure underlying data.

tptacek 9y ago
If you're concerned about the primitives making up your password hash, you shouldn't be using PBKDF2 to begin with; better to use a purpose-built KDF like scrypt, bcrypt, or argon2.

snakeanus 9y ago

> SHA-3 did introduce something useful To me the most useful part of SHA-3 is that you don't need to use HMAC as it is not vulnerable to length extension attacks. Meaning that it's much faster than SHA-2 when used as a MAC construction.

gcp 9y ago
But aren't we trying to get away from MACs into authenticated ciphers?
- tptacek 9y ago
  An authenticated cipher is usually just a composition of a cipher and a MAC.
  - klodolph 9y ago
    That's historically true, but these days I think GCM is the most common. GCM also has hardware support from the CLMUL instruction set available on Intel processors since 2010 and AMD processors since 2011.
    - tptacek 9y ago
      GCM is just a composition of CTR mode and GMAC.
      - klodolph 9y ago
        Well, technically you'd get a different result if you applied GMAC after using CTR mode, because the final stage of the GMAC would get a different length value, but the process would be very similar. From a different perspective, GMAC is just GCM without encryption. It's not like GMAC existed and then it was combined with AES to make AES-GCM, it was designed as authenticated encryption and has the ability to encrypt zero bytes while still authenticating other bytes. So no, GCM is not just GMAC + AES.

deleted 9y ago

[deleted]

aicez 9y ago

The assessment that SHA-3's performance is bad completely disregard the results from hardware benchmarking (FPGAs and ASICs). All the hardware results have shown conclusively that Keccak is multiple times faster than SHA-2. While I can't say that the algorithm is going to be supported in HW, with enough usage it might be the case. Edit: Removed my comment regarding BLAKE as it was incorrect.

Sunset 9y ago
Isn't this something you don't want? I'd rather use an algo which is painful to do in bulk.
- sp332 9y ago
  That's helpful for passwords, but most hash applications aren't for passwords. If you're hashing a large file you don't want something super slow, and you don't need to pad out a tiny password into something hard to guess.
agl 9y ago
By selecting primitives designed for hardware (AES and GHASH) rather than primitives that use operations that are commonly applicable (ChaCha20 and Poly1305), we've ended up with extra hardware to support AES and GHASH. But it's not clear that was actually a good idea, or just path dependence. ChaCha20, Poly1305, BLAKE2 benefit from improvements that benefit a wide-range of applications, while SHA-3, AES and GHASH do not. Thus the "cost" of high performance support for the former can be amortised over a much wider base.
- aicez 9y ago
  I suspect that the extra hardware support is not a major concern. This might be because any company that has a true security concern will eventually need to designated an area on its silicon for cryptographic purposes. This area will be security hardened to protect against any side-channel attacks. Also, sharing HW resource for cryptographic purposes is not possible for any device that needs to pass certain security certification. Edit: Typo and additional comment

simias 9y ago

A rather minor point but: >[The diversity of cryptographic primitives] contributes to code-size, which is a worry again in the mobile age In the "mobile age" we use embedded processors with gigabytes worth of RAM and several times the amount of NAND storage, I don't really think a SHA-3 implementation is going to tip the boat over. The author's other points seem very fair though.

agl 9y ago
I can confirm that the code size of BoringSSL is something that we worry about for mobile apps. A 50KB increase (which wouldn't be much for an optimised SHA-3) would raise questions. I admit that when I see the 100MB+ size of apps that I have to download, I do wonder why. But I assume that it would be even worse were people not worrying about this stuff.
- Dylan16807 9y ago
  > A 50KB increase (which wouldn't be much for an optimised SHA-3) would raise questions. Can you elaborate on that? That's orders of magnitude bigger than a naive implementation, and wouldn't fit in L1 cache either.
mikeash 9y ago
That massive storage is often still using a heavily constrained data connection. Apple, for example, won't let you download an app over 100MB over cellular data. You want to really try to keep your app under that limit, otherwise a lot of potential users will abandon the app if they discover it while they're not on WiFi.
- hdhzy 9y ago
  I wonder why is that, I had a shared plan (3 numbers) that gave about 99 GB each month and Apple wouldn't let me download a 100 MB game through LTE?
  - oconnor663 9y ago

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

richdougherty 9y ago

> As I've mentioned before, diversity of cryptographic primitives is expensive. ... exponential number of combinations ... limited developer resources ... It's a good point that diversity is expensive. There's a counter-argument too: if we all decide to use one thing, but it goes wrong - then we're in serious trouble. If we have multiple approaches, then the damage is lessened if one of them turns out to have problems. In other words, I think it's better to have a variety of approaches to manage risk, even if it does impose costs.

tptacek 9y ago
The track record on that design strategy is not good. We've been pursuing designs with cryptographic diversity built in for several decades, and the result has been decades of terrible vulnerabilities --- almost none of which have been mitigated by diversity!
- baby 9y ago
  Have we had some big crypto failures besides "everyone was using md5" and "everyone was using DES"?
  - tptacek 9y ago
    Yes: for instance, the TLS BEAST vulnerability, which affected all the block ciphers in that version of TLS, because the protocol standardized interchangeable ciphers and a message encryption construction based on CBC as separate components. Ironically, when the RC4 attack refinements were published, for awhile sites were forced to choose between a vulnerable CBC implementation and using the vulnerable RC4 cipher. With the exception of MD5 in X.509 certificates and RC4 in TLS, has there been another cryptographic vulnerability that required the retirement of a cipher? SWEET32 is about as close as you come to that, right? And, obviously, there have been many more problems, even just in TLS, than X.509 MD5 and RC4.
    - baby 9y ago
      Wasn't that more because we had not really thought of aead constructions? I mean we didn't even know we had to mac after encrypting. If we had more stream ciphers at the time we would not have been stuck with beast or rc4. Imo sweet32 was just the weak but well-marketed cherry on the top to get rid of the previous generation. We just had the sha-1 collision.

baby 9y ago

I believe this is a good complememt to agl's post with a focus on K12 instead: https://cryptologie.net/article/393/kangarootwelve/ https://cryptologie.net/article/393/kangarootwelve/

matt_wulfeck 9y ago

Why don't we use hash functions that combine the output of two discrete hashing functions and combine the results? It seems to me it's easy to break sha or md5, but what about breaking two fundemantally different algorithms at the same time? Implementation seems as easy as concatenating the two hex outputs into a single string and comparing the results. I'm curious to what others think of this idea.

agl 9y ago
It turned out that breaking the combination is SHA-1 and MD-5 is much easier than people expected: https://www.iacr.org/archive/crypto2004/31520306/multicollisions.pdf https://www.iacr.org/archive/crypto2004/31520306/multicollis...
- tptacek 9y ago
  Shameless plug (this is one of Sean's, though): http://cryptopals.com/sets/7/challenges/52 http://cryptopals.com/sets/7/challenges/52
JackC 9y ago
A couple of criticisms I've seen for this idea, as best I understand them as an amateur: (1) It's hard to use a multihash construct correctly. For example, do you want "hash1(message) + hash2(message)" or "hash1(message + hash2(message))" or "hash1(hash2(message))"? The answer is that it depends which features of a hash function matter for your application, and if you pick the wrong one you will have the worst of all worlds instead of the best of all worlds. (Simple example: "md5(password)+scrypt(password)" is a broken way to store passwords, while "sha3(md5(document))" is a broken way to authenticate documents; vice versa would probably be OK.) (2) If you're paranoid, bytes and CPU cycles are (arguably) better spent on extending your best option instead of tacking on less good ones. Breaks tend to come in the form of "it is now feasible to crack a key with length X" or "find collisions with a hash with Y rounds" or whatever, where X and Y were originally picked to strike a balance of security and performance. So if you were going to spend performance on something nonstandard to guard against mathematical breakthroughs, experts might recommend doubling X and Y instead of throwing in a second less-secure cypher. (Although really they'd tell you just to use the standard thing.)

ktta 9y ago

My suggestion after looking around for the best hash function is SHA-256. Not SHA-512, not SHA-512/256. Not even SHA-224 because it offers no performance benefits. BLAKE2 is a good candidate right now considering speed. But SHA-256 instructions will only get more prevalent which will take care of the speed issue. There have been speed comparisons between SHA-256 and BLAKE2 without SHA instructions[1]. BLAKE2 seems like good option then, with the optimized code. But once SHA extensions use hardware instructions, it gets a 5.7x boost which blows BLAKE2 out of the water.[2] There are instructions for SHA-256 in NEON too although I couldn't find any benchmarks. I'd say it'll definitely be faster than BLAKE2 with HW instructions. Combine that with SHA256 being uber popular everywhere, that'll be one less headache. I also doubt SHA-256 will be over thrown in the near future, atleast until SHA-3 instructions become commonplace, which I anticipate will take about a decade from now. [1]: https://news.ycombinator.com/item?id=14357197 https://news.ycombinator.com/item?id=14357197 [2]: https://github.com/randombit/botan/issues/807#issuecomment-270652403 https://github.com/randombit/botan/issues/807#issuecomment-2... EDIT: Looks like SHA-224 might be the best option, considering it has the same core with a truncated output which will make it immune to length-extension attacks.

tptacek 9y ago
The advantage to 224 or 512/256 is that they don't expose the full register state of the hash at output and thus, like Blake2 and SHA-3, aren't vulnerable to length-extension attacks: you can (though it would be idiosyncratic to do so) use a simple prefix MAC with them, rather than HMAC.
- baby 9y ago
  But people don't know that. That's why it is best to just push people towards sha-3 and have the in-house cryptographer decide when sha-2/blake2/kangarootwelve might be relevant for speed purposes.
  - tptacek 9y ago
    I agree that using prefix MACs with SHA-2 is a bad idea, for that reason, but since everyone uses HMAC already and since there are much faster MACs than KMAC, I don't think there's a clear argument for SHA-3 here. I'm just saying, if you're going to recommend one of the SHA-2's, it should probably be one of the truncated ones.

yuhong 9y ago

The preimage strength debacle is probably worth mentioning

dreamthtwasrome 9y ago

Speed isn't a black-and-white panacea property, cost of brute-forcing (ram, cpu, time and money) and other attacks should also be prioritized for a given use-case (ie argon2, scrypt). Fixating on a single, fast algorithm and making it a near universal monoculture makes it easier for well-funded state and corporate entities to reduce their costs to generate a hash collison or do something else nasty because they only have to invest in one kind of possibly cheaper/simpler ASIC building-block. Having several different, but throughly sensible algorithms who's strengths, weaknesses and limitations are well known is a better approach than saying "everyone use X" a-la NESSIE. Users with Paradox of Choice going on can pick the lunch special, AES.