8 ms·
Maybe we shouldn't skip SHA-3
- tptacek 9y agoIf you're going to pick a hash specifically to avoid length-extension attacks, pick SHA-2 512/256, which isn't vulnerable to length extension attacks. Or, for that matter, pick Blake2, which is a slightly less idiosyncratic choice than SHA-3. Everyone --- including the authors of SHA-3 --- is unhappy with the SHA-3 parameters and resulting performance. SHA-2 512/256 is much faster than SHA-3 and supported by more libraries. The notion that by recommending SHA-2 512/256 you're setting people up to use prefix MAC SHA-2 512 or SHA-2 256 is kind of silly. You could similarly argue that by telling people to use SHA-3, you're risking that they "fall back" to SHA-2. Either way, you're calling for a specific hash. The reality is that some people like SHA-3 because it's interesting and because its primitives can be used for a variety of non-hashing applications. That's true! Nobody is saying SHA-3 shouldn't exist. They're just saying: there's no good reason to use it in a modern application. (If you're not clear on length-extension attacks: they're the reason we use HMAC. HMAC-SHA2 isn't vulnerable to length extension attacks; neither is HMAC-SHA1 or HMAC-MD5 --- both of which, fun fact, can't currently be attacked, despite the weakness of their underlying hash. But if you use SHA-2 512/256, you don't have to use HMAC.)
- JoshTriplett 9y ago> Everyone --- including the authors of SHA-3 --- is unhappy with the SHA-3 parameters and resulting performance. Would another variant of Keccak, not the one that became SHA-3, provide more competitive results? Or does Keccak in general not have compelling properties compared to the alternatives?
- tptacek 9y agoYes, there is one: KangarooTwelve, by the Keccak authors. The problem is, there's just not a lot of reasons to use it. SHA-2 isn't broken; in fact, there are hash cryptographers who think SHA-2 may never be broken.
- espadrine 9y ago> there are hash cryptographers who think SHA-2 may never be broken. It is a dangerous assertion, especially if it makes people build things that aren't future-proof enough to support more than one hash type. Otherwise, KangarooTwelve is faster than SHA-2[0], which may be an incentive. Although it is very late compared to BLAKE2, and as a result, it is present in much fewer libraries. [0]: https://twitter.com/KeccakTeam/status/834789451708628995 https://twitter.com/KeccakTeam/status/834789451708628995
- tptacek 9y agoI don't think we're at any risk of research on hashing stopping.
- dsacco 9y agoThat's not necessarily a dangerous assertion. SHA-2 is theoretically immune to foreseeable improvements in computational power. If you use something like SHA-512, a birthday attack will require searching through approximately more candidates than there are atoms in the observable universe. You can't meaningfully improve this by scaling up inordinate amounts of computing power. If you can't rely on raw computational power to force obsolescence, you need either a major paradigm shift (a la quantum computing) or a clever cryptanalytic attack that bypasses the actual difficulty. Quantum computers do not currently pose a serious threat to SHA-2. Grover's algorithm can offer a quadratic improvement to collision identification, but not an exponential one. That's impressive, but not enough on its own. That leaves the last category, which is a clever cryptanalytic attack. This is possible, especially with novel mathematics. But it's not reliable for predicting risk. So really, the only "future-proofing" we can do for SHA-2 is against vague improvements in the underlying math. In any practical sense of the term, it's not a dangerous assertion to claim SHA-2 may never be broken. As Thomas said, research will certainly continue on cryptographic hash functions regardless; moreover, "improvements in math might happen" is not reliable enough to calibrate forced obsolescence or regular updates to hash standards in the future. Given the foregoing, some researchers choose to act as though SHA-2 will never be broken, because there's no meaningful way to assert that it probably will or to coordinate when or how it will, and because there are so many more productive areas of research to focus on where the current algorithms absolutely will be broken in the future. You can't productively work on future-proofing something any further once the space of coherent threats has been reduced to, "this might happen in the future somehow" without real specifics.
- aseipp 9y agoThe parameters NIST specified are just fairly conservative, for one thing (e.g. NIST, IIRC, oddly requested an increase in the number of rounds during the final stages, one of the things people waxed on about.) Regarding another variant: yes, you can get more compelling results, and the authors of Keccak themselves have also proposed another function based on Keccak called KangarooTwelve[1]. K12 has much better performance and parallelism than SHA-3 does in software. (Of course, if you don't need most of Keccak's general properties, you're probably fine with other hashes anyway.) [1] http://keccak.noekeon.org/KangarooTwelve.pdf http://keccak.noekeon.org/KangarooTwelve.pdf
- nincompope 9y agoAs far as I can tell, the increase from 18 to 24 rounds was not NIST's call, but due to the zero-sum distinguishers found on Keccak-f, which made it no longer "hermetic": http://keccak.noekeon.org/NoteZeroSum.pdf http://keccak.noekeon.org/NoteZeroSum.pdf
- cryptonector 9y agoSHAKE is Keccack with parameters that are comparable to SHA-2's, and so performs better.
- baby 9y agoI think our comments and discussions just add to the general confusion though, this is why I just plainly recommend SHA-3. Now if I would personally work on a project I would think of SHAKE first, and I would seriously consider KangarooTwelve (especially for tree hashing, which makes K12 better than any other hash to hash big files).
- tptacek 9y agoYou keep saying that here, and on Twitter, and people --- not just me --- keep telling you that if you're going to recommend a hash specifically to avoid length extension attacks, 512/256 accomplishes that without requiring the adoption of new hashing code. I really don't understand the argument that people can safely type "SHA-3" but not "SHA-2 512/256". Would it help if we renamed SHA-2 512/256? We could call it SHA2.5: better than SHA-2, not quite SHA-3. Or SHA5: better than both! Renaming SHA-2 512/256 sounds a lot easier than getting new hash code implemented in every library.
- baby 9y agoI addressed that point in the post. Unless you replace all the implementations of SHA-2, the deed is done. People will choose SHA-256 and SHA-512 because that's what they've always known. > without requiring the adoption of new hashing code I should have made myself clearer: I recommend SHA-3 for new projects. I wouldn't recommend people to switch to SHA-3 if they are already using SHA-2.
- tptacek 9y agoThis is a little like saying that if you told someone to use Rijndael they might instead use DES.
- baby 9y agoI really don't agree. Rijndael and DES are different algorithm. SHA-512/256 is a made-up algorithm that you need to be aware of. Again I'm talking about "misuse" here. SHA-2 is vulnerable to misuse even if SHA-512/256 is not.
- JoachimS 9y agoRegarding MD5. I advice people from using MD5 in new designs even if it is for HMAC-MD5. Not because that construct is broken (which it isn't), but because we add yet another dependency on an algorithm we in general consider too weak to use. Do you agreee with that advice?
- baby 9y agoYeah, that's a good argument to move to a stronger hash function for HMAC.
- tptacek 9y agoDefinitely don't use MD5!
- StreamBright 9y agoWhat if the use case is not security sensitive, I just want to implement a distributed hash ring for example?
- bradleyjg 9y agoIf the application isn't security sensitive why not a faster non-cryptographic hash like farmhash?
- takeda 9y agoMaybe because it is less popular, this is first time I hear about it. Probably it's also not as widely available.
- StreamBright 9y agoI agree. There is also siphash that we use.
- dom0 9y agoThese are often not packaged, so less available. Though for some applications you wouldn't want a library anyway. (Also, xxhash)
- kobeya 9y agoHow is SHA-512/256 not vulnerable to length extension attacks? I've implemented the SHA family of hash functions before and the only real difference between the two is block size and truncation of output, but I don't see how that stops length extensions.
- helper 9y agoYou can't add more data once you've truncated.
- nialo 9y agoHave you tried implementing the length extension attacks? Truncating from 512 bits to 256 bits hides 256 bits of the state from the attacker, so in order to use a length extension attack they would need to "guess" those bits.
- dom0 9y agoSHA-512/256 is a variant of SHA-512 where the output is truncated to 256 bits. It does not mean "SHA-512 or SHA-256". Yes, perhaps a different symbol than "/" would be better there.....
- jfindley 9y agoTo be fair, while I do agree with you, sha-2 512/256 is an especially confusingly named hash. A _lot_ of people naturally read it as sha-2 512 or 256, which it is not, but thing/otherthing is a common enough pattern that the confusion is understandable. sha-2 256t or something would be much clearer. As the article notes, changing it now is not trivial, but given the potential for confusion is something that might be worth doing, none the less.
- dom0 9y agoI've seen it written as "SHA-2 512-256", which is a bit less confusing.
- nilved 9y ago> The reality is that you should use SHA-3. I'm making this as a broad recommendation for people who do not know much about cryptography. You can't go wrong with the NIST's standard. https://en.wikipedia.org/wiki/Dual_EC_DRBG https://en.wikipedia.org/wiki/Dual_EC_DRBG
- smitherfield 9y agoIf your claim is that SHA-3 contains an NSA backdoor, that's an extraordinary claim requiring extraordinary evidence.[1] In the case you link to, the NSA was publicly the author and the backdoor was "obvious" nearly from the start. [1] Or else a conspiracy theory. Not that conspiracy theories are never true; I'd be surprised but not shocked if this one were.
- nilved 9y agoNo, my claim is simply that NIST sponsorship is not a good reason to use it.
- smitherfield 9y agoFair enough, although I'd still say it is; hashes that've received the NIST's imprimatur have all been above-average compared to their contemporaries, and none of them appear to have any intentional weaknesses.
- tptacek 9y agoThis is the (very) rare case in which a cite to Dual_EC makes some sense.
- JoachimS 9y agoIt wasn't obvious enough to prevent it from slipping into being not only a NIST standard, but also standards by ANSI and ISO. Quite a lot of people around the world that accepted it.
- smitherfield 9y ago
- johnhenry 9y agoWe can look at technologies from two different points of view -- a engineers or as scientists. As engineers, we look at sha-3 as a practical means to an end -- just a secure hashing algorithm. From that point of view, its un-necessary as we already have sha-2. As scientists, it's an experiment and we're still waiting to see the results. The hypothesis is that its existence will strengthen our existing pool of hashing algorithms. We should note that this is a poor hypothesis; given that we don't see any flaws in our [only?] other algorithm, it's currently impossible to test. However; as with many other important experiments, we are seeing other un-expected results and applications. As an engineer, I acknowledge that it's probably best to skip it in most production applications. But as a scientist, let's not skip if anything cool happens down the line?
- cryptonector 9y agoSo, AGL was speaking specifically about TLS. He wasn't suggesting other protocols / formats not use SHA-3 / SHAKE. But this blog post talks about misuse of hash functions as a reason to switch to SHA-3 as if AGL had not referred only to TLS. That's a strawman. It's NOT useful. EDIT: What's the one downvote for? Just curious!
- deleted 9y ago[deleted]
- tytso 9y agoI think the argument that people could misuse SHA-2 is bogus, because if people are rolling their own crypto, they can get themselves into a lot of trouble, not just with SHA-2(key || data). Indeed, that argument may cause people to assume that it's ok for application programmers to do cryptographic protocol engineering, which would be disastrous. A much more general argument is that most people should be using cryptographic frameworks (e.g., which implement TLS), and Adam Langley's thoughts about whether or not SHA-2 should be skipped should be aimed at people who are creating those cryptographic frameworks. But if we are giving advice to random application programmers, they shouldn't be trying to pick cryptographic algorithms to begin with, and the question of whether you should be using SHA-2(key || data) is the sort of thing where the Zen master would be hitting the student with a cluestick for asking the wrong question to begin with.
- remcob 9y agoIn which use cases is the asymptotic cycles per byte relevant compared to the small case performance? I mostly use hashes as part of signing/verifying small messages, say an 80 byte JWT, a Blockchain transaction, a certificate, an TLS/SSH packet, etc. Besides hashing large files (which I rarely do), I don't see where I would reach asymptotic performance, or even use tree-hashing. SHA3's block size is 200 bytes, KangarooTwelve's is, if I'm not mistaken, 8192? I'm more worried about not even filling the first block :)
- baby 9y ago> I mostly use hashes as part of signing/verifying small messages, say an 80 byte JWT, a Blockchain transaction, a certificate, an TLS/SSH packet, etc. Besides hashing large files (which I rarely do), I don't see where I would reach asymptotic performance, or even use tree-hashing. The number I used is definitely not the best one. But I believe it applies to you as you're not hashing a lot of bytes so you will not see much of a speed difference between hash functions. > SHA3's block size is 200 bytes, KangarooTwelve's is, if I'm not mistaken, 8192? I'm more worried about not even filling the first block :) They have the same block size :o rather 8192 is the threshold before you start using the tree hashing mode. This way if you want to hash small messages you do not get a penalty from using KangarooTwelve! It's all good :)
- super-io 9y agoIn hash function competitions, are the authors of the function allowed to vote for their own entry?
- niftich 9y agoIt's unfortunate that the 'bar' in misuse-resistant crypto isn't always equally high, and different experts (as evidenced from this thread) argue that you get there in different ways. In that regard, I think the author makes a good point: despite the hard-to-implement-in-hardware aspect of GCM, the dangers of nonce reuse have always been well-documented, and it's only recently that that went from being a simple algorithmic contract to bad design worthy of correction. I think the point the OP makes is that a suggestion like "use SHA-3" is a simple, succinct, and not-unacceptable answer to a question like "what cryptographic hash function should I use?", giving a safe albeit conservative, but instantly graspable answer without having to go into additional detail -- other than the obligatory mention to that general-purpose hash functions aren't by themselves appropriate for key derivation ("password hashing"). The alternative view -- that SHA-512/256 (which suffers from its naming), or the longer-but-less-truncated-state SHA-384 is faster, more studied, more widely supported -- is a more nuanced recommendation, but then you have to explain why you don't mean SHA-256 or SHA-512. The innovation of libraries like nacl and libsodium was to the user of crypto from having to be a crypto expert themselves, and once you have to explain which of the SHA-2 hashes specified in FIPS PUB 180-4 you should and shouldn't use, we're not really any better than in the footgun days.