Does anyone in the field know if there's a SHA-4 competition around the corner, or is SHA-3 good enough? It would be interesting if one of the SHA-4 requirements was Zero Knowledge Proof friendlyness. MiMC and Poseidon are two of the big contenders in that area, and it would be really great to see a full NIST quality onslaught against them.
https://www.schneier.com/blog/archives/2013/10/will_keccak_s...
From your first link:
I misspoke when I wrote that NIST made “internal changes” to the algorithm. That was sloppy of me. The Keccak permutation remains unchanged. What NIST proposed was reducing the hash function’s capacity in the name of performance. One of Keccak’s nice features is that it’s highly tunable.
I do not believe that the NIST changes were suggested by the NSA. Nor do I believe that the changes make the algorithm easier to break by the NSA. I believe NIST made the changes in good faith, and the result is a better security/performance trade-off.
jk I’m sure it’s fine… probably
I still think it's probably fine, but I feel better about insisting on SHA-2+mitigations or blake3 instead now, even if the main problem with SHA-3 is its being deliberately designed to encourage specialized hardware accelleration (cf AES and things like Intel's aes-ni).
(To be clear, the fact that Schneier claims to "believe NIST made the changes in good faith" is weak but nonzero evidence that they did not. I don't see any concrete evidence for a backdoor, although you obviously shouldn't trust me either.)
Do you think he’d disclose it if he did?
Making late (in this case, after the competition was already over) changes to a crytographic primitive - without extensive documentation both of why that's necessary (not just helpful) and why it's not possible (not just you promise it doesn't) for that to weaken security or insert backdoors - is a act of either bad faith or sufficiently gross incompetence that it should be considered de facto bad faith.
Schneier claiming to believe that it's good faith implies that he either doesn't understand or (presumably more likely given his history?) doesn't care about keeping the standardization process secure against corruption by the NSA, which suggests either incompetence or bad faith on Schneier's part as well. (Or, in context, that someone was leaning on him after the earlier criticism.)
This is particularly inexcusable since reducing security parameters on the pretense that "56 bits ought to be enough for anybody" is a known NSA tactic dating back to fucking DES.
The new padding prepends either 01, 11, or 1111 depending on the variant of SHA-3. That way the different variants don't sometimes give the same [partial] hash.
It was weird to toss that in at the last second but there's no room for a backdoor there.
But I've had a soft spot for Schneier since this (pre-Snowden) blog post on Dual_EC_DRBG: https://www.schneier.com/blog/archives/2007/11/the_strange_s....
> NIST's current proposal for SHA-3, namely the one presented by John Kelsey at CHES 2013 in August, is a subset of the Keccak family. More concretely, one can generate the test vectors for that proposal using the Keccak reference code (version 3.0 and later, January 2011). This alone shows that the proposal cannot contain internal changes to the algorithm.
In fact, one actually has done almost exactly that: https://en.wikipedia.org/wiki/Data_Encryption_Standard#NSA's...
Blake3 was designed from the ground up to be highly optimized for vector instructions operating on four vectors, each of 4 32-bit words. If you already have the usual 4x32 vector operations, plus a vector permute (to transform the operations across the diagonal of your 4x4 matrix into operations down columns) and the usual bypass network to reduce latency, I think it would rarely be worth the transistor budget to create dedicated Blake3 (or Blake2s/b) instructions.
In contrast, SHA-3's state is conceptually five vectors each of five 32-bit words, which doesn't map as neatly onto most vector ISAs. As I remember, it has column and row operations rather than column and diagonal operations that parallelize better on vector hardware.
SHA-2 is a Merkle-Damgard construction where the round function is a Davies-Meyer construction where the internal block cipher is a highly unbalanced Feistel cipher. Conceptually, you have a queue of 8 words (32-bit or 64-bit, depending on which variant). Each operation pops the first word from the queue, combines it in a nonlinear way with 6 of the other words, adds one word from the "key schedule" derived from the message, and pushes the result on the back of the queue. The one word that wasn't otherwise used is increased by the sum of the round key and a non-linear function of 3 of the other words. As you might imagine, this doesn't map very well onto general-purpose vector instructions. This cipher is wrapped in a step (Davies-Meyer construction) where you save a copy of the state, encrypt the state using the next block of the message, and then add the saved copy to the encrypted result (making it non-invertible, making meet-in-the middle attacks much more difficult). The key schedule uses a variation on a lagged Fibonacci generator to expand each message block into a larger number of round keys.
This is true, and the BLAKE family inherits this structure from ChaCha, but there's also more to it than that. If you have enough input to fill many blocks, you can run multiple blocks in parallel. In this situation, rather than dividing up the 16 words of a block into four vectors, you put each word in a different vector, and the words of each vector represent the same position in different blocks. (I.e rather than representing columns or rows, the vectors point "out of the page.) There are several benefits to this arrangement:
1. You don't need to do that diagonalization operation anymore.
2. If your CPU supports "instruction-level parallelism" for vector operation, working across the four words/vectors in a row gets to take advantage of that.
3. Best of all, you're no longer limited to 4-word vectors. If you have enough input to fill 8 blocks (AVX2) or 16 blocks (AVX-512), you can use those much larger instruction sets.
This is all easy to take advantage of in a stream cipher like ChaCha, because each block is independent. With a hash function, things are more complicated, because you usually have data dependencies between different blocks. That's why the tree structure of BLAKE3 (or somewhat similarly, KangarooTwelve) is so important for performance. It's not just about multithreading; it also about SIMD. See section 5.3 of the BLAKE3 paper for more on this.
I am shocked how fast it is. Just tried it on several files. It is blazing fast.
brew install b3sum on mac.
Edit: Never mind, grand-uncle comment beat me to it:
For what applications is it not good enough, and how/why do we believe that?
(You could contort yourself into an argument that "SHA2 isn't good enough for protocols where you need a keyed hash without HMAC", but 1) that isn't true given SHA2-384 and 2) there really are no such protocols).
The SHA1 break doesn't threaten SHA2. The two hashes are different in a significant way that breaks the SHA1 attack.
Hmm, I think you might be overstating this a bit. While the SHA1 attack indeed does not break SHA2, the whole reason SHA3 exists at all is that SHA1 and SHA2 are similar enough in their structure that we were worried that the methods used in the SHA1 break could be extended to attack SHA2.
So far the answer seems to be no, but it was a serious concern for a while.
Is it a serious concern among cryptographers outside of NIST?
late edit
I removed the scare quotes around "differential paths" after skimming the first Stevens paper and the Chabaud-Joux paper and confirming they were using "differential" they way I understand the term. :)
Also, I'm more confident that the message schedule is pretty central to the attack, and I guess the whole line of research that led up to it?
Is it a serious concern among cryptographers outside of NIST?
Today? Not really, because we've had years of research showing us that SHA2 still seems to be safe. But when the major breaks of SHA1 were happening? Absolutely. In my "everything you need to know about crypto in 1 hour" talk I explicitly said "use SHA2 but be ready to move to SHA3 if needed because the attacks on SHA1 are scary and we're worried they could generalize to SHA2 as well".
As for your points about anticipated benefits of the SHA2 message schedule: isn't part of the point of SHA2 that it's more ARX-y? Which is basically what makes the Shattered line of attacks not viable?
I think we're in the same place in terms of recommendations! Except: I don't know that "the SHA1 attacks could generalize" is all that valid a concern? Regardless, the "why" of this is super interesting and I don't think anyone has broken it down super clearly (I'm not doing it by myself; I don't have the chops).
I don't know that the NSA has ever published the internal discussions which resulted in SHA2, but I always thought the primary design purpose of SHA2 was to produce larger hashes (and thus avoid the 2^80 birthday attack on SHA1).
Except: I don't know that "the SHA1 attacks could generalize" is all that valid a concern?
It's not, now. It was in 2005/2006. Remember there wasn't just one SHA1 attack; there was a whole series of them. (And I'm guessing the NSA was particularly concerned given that some of the attacks were discovered by Chinese researchers.)
It will also be really nice on amd_64 CPUs for doing large amounts of hashing if they ever get a sha3 instruction.
That said, hashing is rarely your bottleneck so there's not much urgency.
SHA-3 is by far and away the most elegant modern cryptographic hash algorithm.
What would this requirement look like and why would it be important for a hash function?
Given that NIST itself warns PQC algorithm may be unsafe after 2035, this should be considered SHA-4.
Sha is not a digital signature algorithm. That is a different type of crypto primitive.
I thought post-quantum cryptography was supposed to be futureproof? Or am I misunderstanding