Inside Keccak-f[1600]

The sponge in The Sponge Construction needs a permutation on 1600 bits that behaves like a random one. This note opens it.

01.The state

The 1600 bits are arranged as a three-dimensional array $A[x][y][z]$ with $x, y \in \{0, 1, 2, 3, 4\}$ and $z \in \{0, \ldots, 63\}$.

The easiest way to hold it is as a $5 \times 5$ grid of 64-bit lanes, giving $5 \times 5 \times 64 = 1600$ bits. On a 64-bit processor each lane is one register.

Three pieces of vocabulary get used below. A lane is the 64 bits at a fixed $(x, y)$. A column is the five bits at fixed $(x, z)$, running through all $y$. A slice is the 25 bits at a fixed $z$.

02.The round

The permutation is 24 rounds, each the same composition of five steps:

$$\text{Round}(A) \;=\; \iota\bigl(\chi(\pi(\rho(\theta(A))))\bigr).$$

Each step exists for a specific reason, and knowing the reason is the way to remember which is which.

03.$\theta$, diffusion

Diffusion means spreading a one-bit change across many output bits. This is the layer that does it.

Compute the parity of each column, meaning the XOR of its five bits:

$$C[x][z] \;=\; \bigoplus_{y=0}^{4} A[x][y][z].$$

Build a correction from two neighbouring columns, one of them shifted by one along $z$:

$$D[x][z] \;=\; C[x-1][z] \;\oplus\; C[x+1][(z-1) \bmod 64],$$

and XOR it into every bit of the corresponding slab:

$$A'[x][y][z] \;=\; A[x][y][z] \oplus D[x][z].$$

Trace what a single flipped input bit does. It flips the parity of one column. That parity feeds $D$ at two positions, and each $D$ value is XORed into five bits. So one input bit affects eleven output bits after one round, and after a handful of rounds it affects essentially all 1600. That is the avalanche property.

04.$\rho$, rotation

Rotate each of the 25 lanes cyclically along $z$ by a lane-specific amount, from a fixed table in the specification. The offsets run from 0 for lane $(0,0)$ up to 62.

In hardware a rotation by a compile-time constant is free. It is wiring, not logic, so this step costs nothing in gates and nothing in delay.

Its purpose is to destroy any leftover alignment along $z$. Without it, $\theta$'s effects would stay confined within slices, and an attacker could try to analyse the permutation one slice at a time.

05.$\pi$, lane permutation

$$A'[y][2x + 3y \bmod 5] \;=\; A[x][y].$$

Every lane is moved to a different position in the grid. No bit inside a lane changes.

Like $\rho$, this is free in hardware, being a fixed rewiring.

The pair $\rho$ then $\pi$ is designed together: every lane ends up in a new place and with a new rotation, so no alignment survives from one round to the next.

06.$\chi$, the only non-linear step

Everything so far is XOR, rotation and parity, all of which are linear over $\mathbb{F}_2$. A permutation built only from linear operations would be catastrophically weak: its output would be a linear function of its input, and linear systems are solvable.

$\chi$ is what breaks that:

$$A'[x][y][z] \;=\; A[x][y][z] \;\oplus\; \bigl(\lnot A[(x+1) \bmod 5][y][z] \;\wedge\; A[(x+2) \bmod 5][y][z]\bigr).$$

Each output bit is one input bit XORed with the AND of two others, one of them inverted. It operates along rows within a slice, and it is the same small function applied 320 times.

The AND is the only non-linear gate in the entire permutation. Everything else in Keccak is XOR and wiring.

Its algebraic degree is 2 per round, and degree compounds through composition, so 24 rounds reach an effective degree far beyond anything a distinguisher can exploit.

That one gate is also why Keccak is cheap in hardware. Non-linearity is usually the expensive part of a cipher, often implemented as substitution tables in memory. Here it is a single AND per bit.

07.$\iota$, symmetry breaking

XOR a round-specific 64-bit constant into lane $(0,0)$:

$$A'[0][0] \;=\; A[0][0] \oplus RC_i .$$

The 24 constants come from a simple linear-feedback shift register.

This step looks trivial and is not optional. Without it every round would be identical, and identical rounds leave the permutation with internal symmetries. A state that is symmetric in the right way would stay symmetric forever, and an attacker could work inside that smaller symmetric subspace. The round constants make each round different from every other and destroy those symmetries.

08.Why this design suits hardware

Look at what the five steps actually require: XOR, AND, NOT, and rotation by constants.

No addition, so no carry chains and no long critical paths. No multiplication. No memory lookups, so no tables and no cache behaviour. No data-dependent anything, so the whole permutation is constant-time by construction rather than by careful implementation.

That last point is worth contrasting with the reduction methods earlier in this chapter, every one of which ended with a conditional subtraction that had to be made branchless deliberately. Keccak has no such hazard anywhere. There is nothing to get wrong.

The final note counts what it costs.