0
$\begingroup$

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).

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.