If the output size of SHAKE128/256 is variable, why is the security fixed at 128/256?

Question

The general idea is that the security strength of a good hash function is equal to half it's output length. The output length of SHAKE128 and SHAKE256 is variable, but their strengths are still said to be 128-bit and 256-bit, respectively. Why is that the case?

Answer 1

The general idea is that the security strength of a good hash function is equal to half it's output length.

The security strengths of a random oracle are indeed functions of its output length and nothing more. For a long time the common wisdom was that hash functions should be designed to target the same security strength as random oracle of the same output size. Or in other words, random oracles are the classic model of what an "ideal" hash function should behave like.

In recent years that common wisdom has been giving way to a view that this security goal is often excessive. For example, an 512-bit random oracle give a 256-bit security against collision attacks, but a whopping 512-bit security level against preimage attacks. SHA-512, for example, is claimed to have that security level.

But there is no practical scenario that requires a 512-bit security level against any attacks. So a hash function that "skimped" and provided 256-bit security against both attacks would be more than adequate. Similar remarks could be made about a 256-bit output hash function that offers 128-bit security against both collisions and preimages; it would be a perfectly reasonable choice for many applications that need 128-bit security.

So Keccak/SHA-3 was designed to fit this newer paradigm that a hash function doesn't need to rise to the same security level as a random oracle. Instead of holding up random oracles as the ideal model of a hash function, it is designed to target the same security level as a random sponge—the same sponge construction that Keccak uses internally, but instantiated with a random fixed-size permutation instead of the concrete one that Keccak does.

The random sponge model is more permissive than the random oracle model, but it's still a principled model that's also more realistic. It's principled because there are security proofs that compare the security of a random sponge to that of a random oracle:

We have proven that a random sponge function is as strong as a random oracle, except for the effects induced by the finite memory. [Source]

And this quote also hints at why it's more realistic. A random sponge processes arbitrary-length messages sequentially, one block at a time, using a constant size buffer, just like practical hash functions do. So a random sponge is vulnerable to attacks that exploit those choices, but these are attacks that practical hash functions cannot escape. Random oracles on the other hand are able to behave in ways that no sequential, constant-space hash function could ever reproduce—but that makes them a standard that we know we cannot reach in practice anyway.

The output length of SHAKE128 and SHAKE256 is variable, but their strengths are still said to be 128-bit and 256-bit, respectively. Why is that the case?

Now with the philosophy out of the way, the concrete answer is that they're sponge functions with capacities of $c = 256$ and $c = 512$ respectively, an a random sponge's security level can never exceed $c/2$. These security levels are adequate in practice as long as you choose a sufficient output length.

Answer 2

The inner functions have been specifically designed to only support 128 bit or 256 bit security: it's half of the capacity of 256 or 512 bits. The underlying functions or structure do not change.

You can see this from the following picture, taken from the Noekeon site about generic sponge constructions (SHA-3 / SHAKE / Keccak is a sponge construction):

the capacity is $c$ on the left hand side.

So the output is generated at the squeezing stage, while the capacity (as input for $f$ stays 256 or 512 bits).

This may not matter as much as you think, 256 bit security is considered enough to protect against analysis with a quantum computer. The security won't decrease even if large output is generated.

More information can be retrieved from the Noekeon site:

When using a random sponge as a security reference, one considers the success of a particular attack. Such a success probability depends not only on the nature of the attack considered but also on the chosen parameters of the random sponge, i.e., its capacity, bitrate and whether it calls a random permutation or a random transformation. The flat sponge claim is a simplification in the sense that we consider only the worst-case success probability, determined by the upper bound on the random oracle differentiating advantage [Bertoni et al., Eurocrypt'08], which depends solely on the capacity of the random sponge. Hence, it flattens the claimed success probabilities of all attacks using a single parameter: the claimed capacity $c_{claim}$.

Later it is mentioned that $c_{claim} = c$.