Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I am learning Keccak Hash Algorithm and I am a little bit confused about the Capacity bits parameter. I am trying to understand how we can set the capacity parameters while implementing Keccak in python3.
Example: trying to get a collision in Keccak using Capacity = 0 irrespective of hash size (let's say hash size at least 128 bits).
Here is a trivial second preimage attack with arbitrary prefix and single additional block in the case where the capacity is zero (I'll elide padding). Naturally, this includes the much weaker collision attack.
When the capacity is zero, then in the absorption phase the state $S_t$ evolves as $$S_0=\mathbf 0$$ $$S_{t+1}=f(S_t\oplus P_t)$$ where $S_t$ and $P_t$ are the same length in bits. The output is purely a function of $S_n$ and so if I can create two messages with the same $S_n$ they will have the same hash value.
Given a message $P_0\ldots P_{n-1}$, I can compute $S_0,\ldots,S_n$. Now given a prefix $P'_0\ldots P'_{n-2}$, I can compute the corresponding $S_0,S'_1,\dots,S'_{n-1}$. I now specify $$P'_{n-1}:=P_{n-1}\oplus S_{n-1}\oplus S'_{n-1}$$ so that $$S'_n=f(S'_{n-1}\oplus P'_{n-1})=f(P_{n-1}\oplus S_{n-1})=S_n.$$ I now have two messages with the same $S_n$ value and so the same hash output.
More generally, if I can create a collision on the "capacity bits" of the state, I can then collide the full state with a simple choice of the next plaintext block. The state collision will then lead to a hash collision.
