# Security of Keccak/SHA3 against birthday attacks

If I understand it correctly the security of $$\operatorname{Keccak}$$ depends on the capacity $$c$$, which means that I get a security level of $$2^{128}$$ for $$c=128$$ (I omitted the value $$r$$ here because I think that it is irrelevant to my question...but correct me if I'm wrong).

But in every publication I found (and even on the $$\operatorname{Keccak}$$ website), it is said that the security does not depend on the output length. I don't understand how the value of $$c$$ is relevant to birthday attacks. For every single hash function, I can just run a birthday attack regardless of the inner construction of the hash function, right? Which means that for a $$\operatorname{Keccak}$$ implementation with $$c=128$$ but an output length of let's say $$64$$ bits, I can find a collision after $$2^{32}$$ steps using the birthday paradox, regardless of the value of $$c$$, right?

Let's even take it one step further. How is Keccak with $$c=128$$ and an output length of 1 bit still secure? For practical applications, it simply just can't be...

• Of course important security properties depend on the output size. Collision resistance is $\min(c/2,n/2)$ and preimage resistance $\min(c/2,n)$ where $n$ is the output size. On the other hand indistinguishably doesn't depend on the output size. Where did you find something that claimed that the output size doesn't matter for collision/preimage resistance? – CodesInChaos Nov 11 '16 at 15:33

Let us correct some of your numbers. The size of the capacity is twice the size of the expected security margin (against a birthday attack). This is the idea of flat sponge clain etc

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_{\mathit{claim}}$$. [source]

Thus if you aim for a security margin of $$128$$ bits, you need to have a capacity of $$256$$ bits.

In this approach, one designs a permutation $$f$$ on $$b=r+c$$ bits and uses it in the sponge construction to build the sponge function $$F$$. In addition, one makes a flat sponge claim on $$F$$ with a claimed capacity equal to the capacity used in the sponge construction, namely $$c_{\mathit{claim}}=c$$. In other words, the claim states that the best attacks on $$F$$ must be generic attacks. Hence, $$c_{\mathit{claim}}=c$$ means that any attack on $$F$$ with expected complexity below $$2^{c/2}$$ implies a structural distinguisher on $$f$$, and the design of the permutation therefore attempts to avoid such distinguishers. Note that the existence of a structural distinguisher for $$f$$ does not necessarily imply an attack or weakness in $$F$$. For example, any distinguisher for $$f$$ that has success probability zero below $$2^{c/2}$$ forms no threat, as the flat sponge claim expresses no security against adversaries that may send more that $$2^{c/2}$$ queries. [source]

TL;DR: the security margin is half the capacity. If you aim for 128 bits, you need a capacity of 256 bits.

That being said, we can move to your misunderstanding. You are right to say that if you take an output length of $$1$$ bit, you won't have the $$64$$ bits security claim... because you are looking for a collision in the output.

When you use $$\operatorname{Keccak}$$, you can retrieve the full size of the bit rate ($$r$$). You can also extend this output and because these outputs are related (as you basically always know the content of the bit rate part). Thus the only part that you don't know is the capacity. If you are able to guess or have a collision on this part, then the output is compromised.

### The capacity is the only part of the state that you don't know.

When you want a collision, you look either to have a collision on the capacity part or on the bitrate part which is usually bigger than the capacity...

Let $$a,b$$ be two inputs and $$c,c_1,c_2$$ the capacity part. You have a collision when : $$f(a) \to [\theta \mathbin\| c_1]\\f(b) \to [\theta \mathbin\| c_2]$$ where $$[\theta \mathbin\| c]$$ is full state and $$\theta$$ is the resulting output (here your output length is important).

The other way to find a collision is to manage to get: $$f(a) \to [\alpha \mathbin\| c]\\f(b) \to [\beta \mathbin\| c]$$ (collision in the capacity), because then you can have (due to the simplified sponge construction): \begin{align} f(a \mathbin\| 0) & \to [\alpha \mathbin\| c] &\Rightarrow&&& f([\alpha \oplus 0 \mathbin\| c]) \to \theta \\ f(b \mathbin\| \beta \oplus \alpha) & \to [\beta \mathbin\| c] &\Rightarrow&&& f([\beta \oplus \beta \oplus \alpha \mathbin\| c] ) = f([\alpha \mathbin\| c]) \to \theta \end{align}

TL;DR 2: as @CodeInChaos said Collision resistance is $$\min(c/2,n/2)$$ and preimage resistance $$\min(c/2,n)$$ where n is the output size.. But most papers search collisions on $$\operatorname{Keccak}[1600]$$ thus why they usually state this more generic security margin ($$2^{\mathit{capacity}/2}$$).

• Thank you very much for your answer. Now it has become more clear for me. – Mr Anderson Nov 21 '16 at 8:53
• I feel like I'm missing something obvious, but why is the preimage resistance $\min(c/2, n)$ rather than $\min(c, n)$? – Jack O'Connor Mar 26 '20 at 20:29