Are NIST's changes to Keccak/SHA-3 problematic?

Question

NIST is working on standardizing SHA-3. They have selected Keccak as the basis for SHA-3, and they plan to make some small changes to it; the result (with NIST's changes) will be standardized as SHA-3.

A blog post from the CDT raises concerns over those changes. Two specific concerns were mentioned:

1. The security level is "reduced": instead of offering 224-bit, 256-bit, 384-bit, and 512-bit versions of the hash (as found in the Keccak submission), the SHA-3 standard will only offer 128-bit and 256-bit versions.

2. Some of the internals of the algorithm have been tweaked by NIST.

My question: Are these criticisms of SHA-3 valid? Are they something to worry about?

(To be clear: in the two points above, I'm just repeating what the blog post said. I'm not trying to claim that those two criticisms are valid -- indeed, whether they are fair criticisms or not is exactly what I want to know.)

NIST gives the rationale for these changes in their presentation at CHES 2013.

I wonder if the first criticism might be a misunderstanding; is it an accurate statement of NIST's plans? (See also Why restricting SHA3 to have only two possible capacities?) The second criticism might be more interesting. Is there any technical merit to the second criticism? Is there any reason to distrust the plans for SHA-3, or to suspect shenanigans? Are these changes to Keccak more likely to make it more secure, or less secure?

Answer 1

I do worry, but not for the resistance of SHA-3; I worry for its acceptance.

Technically, what NIST wants to do is sound. They do want to somehow "break" a traditional rule, which is that a hash function with an output of n bits ought to resist collisions with strength 2^n/2, and preimages (first and second) with strength 2ⁿ. Instead, NIST wants harmonized security levels at 2^n/2. Indeed, 128-bit resistance to preimages are more than enough for most practical purposes. On the NIST mailing-list for the SHA-3 competition, John Daemen himself has recently (this morning) argued that the proposed modification on SHA-3 will not only retain 128-bit protection against preimages, but it will even ensure 128-bit protection against multi-target preimages, i.e. something better than what a "classic" hash function with a 128-bit output would offer.

The upside of "harmonizing" the security levels is that it is done, in the case of Keccak, by lowering the internal "capacity", and this increases performance (software performance is a sore point of Keccak in general, in that it is not really faster than SHA-2).

Acceptance, however, is something else altogether. In many cases (unfortunately, in most cases), decision to use or not use a specific algorithm in a given system will be taken by people with a, let's say, less acute grasp of cryptography than the crowd of cryptographers. Most don't imagine that there is a difference between collisions and preimages. What happens on their heads is not something like "mmh, NIST made a trade-off between academical security and performance, but a sound one, approved by other cryptographers, so that's good". Rather, it goes along the lines of "OMG they changed the algorithm now it's all backdoored !". And they finally decide to use a custom scheme, e.g. a XOR of MD4 with MurmurHash, or anything else equally dumb.

In my experience, systems which use cryptography don't get broken because of a well-informed trade-off between performance. They get broken because a good algorithm was misused, or simply not used, because someone got paranoid and/or creative, and used a custom weak scheme instead.

One of the reasons why AES was widely adopted is that Rijndael was unchanged. NIST did not change the slightest bit in the whole algorithm; they just took it as is, i.e. as it was specified by the non-American inventors and also as it was analysed by all the other non-American cryptographers during the competition.

If NIST wants the widest possible acceptance of SHA-3, then they should keep Keccak unchanged from its "third round" specification. And by "unchanged" I mean "really unchanged". This is not just about the internal "capacity", but also the padding and all the other bits.

Acceptance at all costs is not necessarily a worthy goal; maybe NIST considers that having a technically good and fast (or not too slow) algorithm is more important than catering to the crowd of ill-informed paranoid managers who make dumb technical decisions. But at least it is a question worth asking.

Answer 2

There does appear to be some confusion with point 1.

The confusion probably stems from the fact that Keccak has an output size number and a capacity. Output size has little to no effect on security strength. Capacity is what really determines the security strength. So when the post says NIST will only standardize two security levels it is correct (as far as the presentation goes, which is in no way set in stone, see below) and that the original proposal had more levels than this. I'm betting when many people read this, however, they are confused and thing that there are only two output sizes.

This slide from Kelsey's presentation at CHES2013 says that there will be 4 different output versions (224, 256, 384 and 512) as well as 2 variable length output versions. There are only two capacities though (256 and 512) and therefore 2 security levels.

A few slides later we read "Security level determined by hash funcion internals, not output size". I think this could be very confusing for developers who have always been told in the past that the probability of collision is the output bit length divided by two (due to birthday attack). Instead, now the collision probability will depend on the internals which developers will never interact with. It also raises the question, why have 2 different output lengths (224 and 256) when both offer the same bit strength (128 bit)?

Another point comes a few slides later "Preimage strength = collision strength". This is a big difference from what developers are familiar with. And on the same slide NIST admits "But this is a pretty big change from the submission". So the security strength of SHA3-256 against preimage attacks will be 128-bit instead of 256-bit like we would expect with SHA2-256.

At the moment, we typically assume that a security level of around 80 bits is sufficient for security these days. So the proposed versions should be fine for now. The fact that the preimage security levels are different from what we have been use to in the past is somewhat disconcerting in my opinion as it is technically weaker than the same sized output SHA2 functions. Similarly, the confusion around security levels and output length given what developers are use to today cannot be a good thing. Shoot, it is even causing confusion among NIST folks (see this other presentation).

As for the second point, this slide from the same presentation mentions the padding changes. I'm not all that familiar with this, so I can't really comment on how this affects security.

Update

I think it should be noted that as far as capacity goes, NIST has not decided on anything. I just saw an email on the SHA3 competition mailing list from John Kelsey where he lists the following 3 possibilities of what NIST could do (implying that it isn't decided).

Possibility #1: They all get capacity of 512 bits, and so promise 256 bits of security. Since 256 bits of security is the highest level that NIST is concerned with, this makes some sense, but it still leaves the process concerns since it's not the version that was submitted, and is in fact weaker, if only in a competely theoretical way. (That is, it's weaker if you are concerned with attacks requiring more than 2^{256} work.) It also doesn't work if you somehow believe that n-bit fixed-length hash functions must have an indifferentiability bound of n bits, though I do not see why that requirement particularly makes sense, and if we'd chosen one of the other candidates that couldn't support it, I don't think anyone would be bringing it up now.

Possibility #2: SHA3-224 and SHA3-256 get 512 bit capacity, SHA3-384 and SHA3-512 get 1024 bit capacity. This is no weaker than what was submitted, and preserves preimage resistance and the indifferentiability bound of n bits for n-bit hash functions. But the performance hit on 384 and 512 bit hash sizes is pretty substantial, and there is zero practical security benefit from this.

Possibility #3: SHA3-224 gets 448 bits, SHA3-256 gets 512 bits, and so on to 1024 bits of capacity. This is just #2 with more distinct capacities, but it is precisely what was submitted to SHA3, and it gets somewhat better performance for SHA384.

So, when point 1 says "the SHA-3 standard will only offer 128-bit and 256-bit versions." That is simply not true at the moment as the SHA-3 standard has not been set in stone and changes are still being discussed. Thus we do not know what the standard will offer.

Answer 3

Reading the CHES'13 presentation by John Kelsey does make things clearer.

Basically, the whole thing (with the output lengths and capacities) seems to come down to the fact that NIST wants to standardize two versions of the underlying sponge function, SHAKE256 and SHAKE512, with respective capacities of 256 and 512 bits, and then define the actual SHA3 hash functions as specific applications of those sponge functions with fixed output lengths and parameters.

As far as standardizing the sponge functions goes, I think that's a great idea. There's a lot of things you can do with a sponge function that you can't (as easily) do with a traditional hash function, and having a standardized sponge function will let people do those things with the confidence that they're building on standard and well tested primitives. Ultimately, it could even happen that everyone will just get used to working with the SHAKE256/512 functions directly, and the actual SHA3 functions turn out to be little more than a historical curiosity. Or maybe not, but it could be.

I can even see the point of limiting the standard to just two capacity values, since apparently it simplifies implementation. The problem, though, is the chosen capacity values, and specifically the fact that a sponge function with C-bit capacity only offers C / 2 -bit security against both collision and preimage attacks. Thus, if the maximum sponge capacity is 512 bits, then you're never going to get more than 256 bits of preimage resistance out of it.

Contrast this with, say, SHA-512, which is supposed to offer a full 512 bits of preimage resistance (and 256 bits of collision resistance), and SHA3 suddenly isn't looking so good. Of course, one could argue that 256-bit security is enough for anything, and so there's no point in aiming for anything more. That said, a rather glaring feature of the proposal described by Kelsey is that, under it, each of the SHA3 variants would be strictly weaker against brute force preimage attacks than the SHA2 variant of corresponding length: even SHA-256 offers 256-bit preimage resistance, whereas SHA3-256, as described by Kelsey, would only have 128-bit security.

Ultimately, I think the fundamental philosophical issue here is whether one considers collision or preimage resistance to be the most important security property of a cryptographic hash function. If one is mainly concerned with applications requiring collision resistance (like, say, digital signatures), then Kelsey's proposal makes perfect sense: you can't get more than n/2 bits of collision resistance out of an n-bit hash, so there's no point in ever trying for any more. On the other hand, if you're concerned about preimage resistance (e.g. for password hashing), then having any less than the full n bits of security will seem like a waste of space, not to mention potentially misleading.

Ultimately, what I think NIST should do (not that they have any reason to care about what I think) is:

• If you're going to define SHA3 as a drop-in replacement for SHA2, it should be a drop-in replacement, i.e. it should guarantee the same level of resistance to both collision and preimage attacks.

• Yes, this means you're going to need a 1024-bit sponge for SHA3-512. Deal with it.

• Yes, it also means that SHA3-256 will be a bit slower, since it needs a 512-bit sponge rather than a 256-bit one. You could define variants (say, "SHA3-256/2" and "SHA3-512/2") with a reduced sponge capacity, but honestly, I'm not sure if there's any real need for them. You could just advise users who want to make that optimization to use SHAKE256 and/or SHAKE512 directly instead.

• As for the 224-bit and 384-bit variants, who cares? I know you'll have to define them, since SHA2 has them, but honestly, who uses them anyway? Just tweak and truncate the 256-bit and 512-bit versions like Kelsey suggests, and like SHA2 does it.

Ps. You might notice that I haven't said anything about the internal tweaks here; that's because I don't know anything about them, and probably would not know enough to say anything meaningful about them even if I did. Sorry.