The Padding. We start with a message $M$. The message is read in blocks of $r=1088$ bits, so we want the message to have length that is a multiple of 1088. But first the message is padded to $M||01$. This is for “domain separation.” There are other uses of the Keccak algorithm such as SHAKE (mentioned above), and for these other purposes, $M$ is padded differently, for example with 1111. This initial padding makes it very likely that using $M$ in different situations yields different outputs. Next, “10*1 padding” is used. This means that first a 1 is appended to $M$011 to yield $M||$011 . Then sufficiently many 01 s are appended to make the total length one less than a multiple of 1088. Finally, a 1 is appended. We can now divide the result into blocks of length 1088.

Why are these choices made for the padding? Why not simply append enough 0s s to get the desired length? Suppose that $M_1=1010111$. Then $M_1||10=101011110$. Now append 1079 zeros to get the block to be hashed. If $M_2=1010$ is being used in SHAKE, then $M_2||1111$ is padded with 1080 zeros to yield the same block. This means that the outputs for $M_1$ and $M_2$ are equal. The padding is designed to avoid all such situations.

Absorption and Squeezing. From now on, we assume that the padding has been done and we have $N$ blocks of length $1088$:

The absorption now proceeds as in Figure 11.2 (we describe the function $f$ later).

1. The initial state $S$ is a string of 0s s of length 1600.

2. For $j=0$ to $N-1$, let $S=f(S\oplus (M_j||0^c))$, where $0^c$ denotes a string of 0s of length $c=512$. What this does is XOR the message block $M_j$ with the first $r=1088$ bits of $S$, and then apply the function $f$. This yields an updated state $S$, which is modified during each iteration of the index $j$.

3. Return $S$.

The squeezing now proceeds as in Figure 11.2:

1. Input $S$ and let $Z$ be the empty string.

2. While $\text{Length}(\text{Z})<\text{td}$ (where $d=256$ is the output size)

   1. Let $Z=Z||Trun{c}_r(S)$, where ${\text{Trunc}}_r(\text{S})$ denotes the first $r=1088$ bits of $S$.

   2. $S=f(S)$.

3. Return $Trun{c}_d(Z)$.

The bitstring ${\text{Trunc}}_{256}(Z)$ is the 256-bit hash value SHA-$3(M)$. For the hash value, we need only one squeeze to obtain $Z$. But the algorithm could also be used to produce a much longer pseudorandom bitstring, in which case several squeezes might be needed.

The function $\mathit{f}$. The main component of the algorithm is the function $f$, which we now describe. The input to $f$ is the 1600-bit state of the machine

where each $S[j]$ is a bit. It’s easiest to think of these bits as forming a three-dimensional $5\times 5\times 64$ array $A[x\text{,}y\text{,}z]$ with coordinates $(x\text{,}y\text{,}z)$ satisfying

A “column” consists of the five bits with fixed $x\text{,}z$. A “row” consists of the five bits with fixed $y\text{,}z$. A “lane” consists of the 64 bits with fixed $x\text{,}y$.

When we write “for all $x\text{,}z$” we mean for $0\le x\le 4$ and $0\le z\le 63$, and similarly for other combinations of $x\text{,}y\text{,}z$.

The correspondence between $S$ and $A$ is given by

for all $x\text{,}y\text{,}z$. For example, $A[1\text{,}2\text{,}3]=S[707]$. The ordering of the indices could be described as “lexicographic” order using $y\text{,}x\text{,}z$ (not $x\text{,}y\text{,}z$), since the index of $S$ corresponding to $x_1\text{,}{y}_1\text{,}{z}_1$ is smaller than the index for $x_2\text{,}{y}_2\text{,}{z}_2$ if $y_1{x}_1{z}_1$ precedes $y_2{x}_2{z}_2$ in “alphabetic order.”

The coordinates $x\text{,}y$ are taken to be numbers mod 5, and $z$ is mod 64. For example $A[7\text{,}-1\text{,}86]$ is taken to be $A[2\text{,}4\text{,}22]$, since $7\equiv 2$ mod 5, $-1\equiv 4$ mod 5, and $86\equiv 22$ mod 64.

The computation of $f$ proceeds in several steps. The steps receive the array $A$ as input and they output a modified array $A^{\prime }$ to replace $A$.

The following steps $I$ through $V$ are repeated for $i=0$ to $i=23$:

1. The first step XORs the bits in a column with the parities of two nearby columns.

   1. For all $x\text{,}z$, let

      $C[x\text{,}z]=A[x\text{,}0\text{,}z]\oplus A[x\text{,}1\text{,}z]\oplus A[x\text{,}2\text{,}z]\oplus A[x\text{,}3\text{,}z]\oplus A[x\text{,}4\text{,}z]\text{.}$

      This gives the “parity” of the bitstring formed by the five bits in the $x\text{,}z$ column.

   2. For all $x\text{,}z$, let $D[x\text{,}z]=C[x-1\text{,}z]\oplus C[x+1\text{,}z-1]$.

   3. For all $x\text{,}y\text{,}z$, let $A^{\prime }[x\text{,}y\text{,}z]=A[x\text{,}y\text{,}z]\oplus D[x\text{,}z]$.

2. The second step rotates the 64 bits in each lane by an amount depending on the lane:

   1. For all $z$, let $A^{\prime }[0\text{,}0\text{,}z]=A[0\text{,}0\text{,}z]$.

   2. Let $(x\text{,}y)=(1\text{,}0)$.

   3. For $t=0$ to $23$

      1. For all $z$, let $A^{\prime }[x\text{,}y\text{,}z]=A[x\text{,}y\text{,}z-(t+1)(t+2)/2]$.

      2. Let $(x\text{,}y)=(y\text{,}2x+3y)$

   4. Return $A^{\prime }$.

   For example, consider the bits with coordinates of the form $(1\text{,}0\text{,}z)$. They are handled by the case $t=0$ and we have $A^{\prime }[1\text{,}0\text{,}z]=A[1\text{,}0\text{,}z-1]$, so the bits in this lane are rotated by one position. Then, in Step 3(b), $(x\text{,}y)=(1\text{,}0)$ is changed to $(0\text{,}2)$ for the iteration with $t=1$. We have $A^{\prime }[0\text{,}2\text{,}z]=A[0\text{,}2\text{,}z-3]$, so this lane is rotated by three positions. Then $(x\text{,}y)$ is changed to $(2\text{,}6)$, which is reduced mod 5 to $(2\text{,}1)$, and we pass to $t=2$, which gives a rotation by six (the rotations are by what are known as “triangular numbers”). After $t=23$, all of the lanes have been rotated.

3. The third step rearranges the positions of the lanes:

   1. For all $x\text{,}y\text{,}z$, let $A^{\prime }[x\text{,}y\text{,}z]=A[x+3y\text{,}x\text{,}z]$.

   Again, the coordinate $x+3y$ should be reduced mod 5.

4. The next step is the only nonlinear step in the algorithm. It XORs each bit with an expression formed from two other bits in its row.

   1. For all $x\text{,}y\text{,}z$, let

   2. $A^{\prime }[x\text{,}y\text{,}z]=A[x\text{,}y\text{,}z]\oplus \left(A[x+1\text{,}y\text{,}z]\oplus 1\right)\left(A[x+2\text{,}y\text{,}z]\right)\text{.}$

   3. The multiplication is multiplying two binary bits, hence is the same as the AND operator.

5. Finally, some bits in the $(0\text{,}0)$ lane are modified.

   1. For all $x\text{,}y\text{,}z$, let $A^{\prime }[x\text{,}y\text{,}z]=A[x\text{,}y\text{,}z]$.

   2. Set $RC=0^{24}$.

   3. For $j=0$ to 6, let $RC[2^j-1]=rc(j+7i)$, where $rc$ is an auxiliary function defined below.

   4. For all $z$, let $A^{\prime }[0\text{,}0\text{,}z]=A^{\prime }[0\text{,}0\text{,}z]\oplus RC[z]$.

   5. Return $A^{\prime }$.

After I through V are completed for one value of $i$, the next value of $i$ is used and I through V are repeated for the new $i$, through $i=23$. The final output is the new array $A$, which yields a new bitstring $S$ of length $1600$.

This completes the description of the function $f$, except that we still need to describe the auxiliary function $rc$.

The function $rc$ takes an integer $t$ mod 255 as input and outputs a bit according to the following algorithm:

1. If $t\equiv 0$ mod 255, return 1 . Else

2. $R=$10000000

3. For $k=1$ to $t$ mod 255

   1. Let $R=0||R$

   2. Let $R[0]=R[0]\oplus R[8]$

   3. Let $R[4]=R[4]\oplus R[8]$

   4. Let $R[5]=R[5]\oplus R[8]$

   5. Let $R[6]=R[6]\oplus R[8]$

   6. Let $R={\text{Trunc}}_8(R)$.

4. Return $R[0]$.

The bit that is outputted is $rc(t)$.