Keccak Capacity bits Parameter

ba flag

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

ru flag

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.

kelalaka avatar
in flag
I'm pretty sure this is HW, asked in two different names
kelalaka avatar
in flag
I sit in a Tesla and translated this thread with Ai:


Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.