# Team Keccak

Guido Bertoni^{3}, Joan Daemen^{1,2}, Michaël Peeters^{1}, Gilles Van Assche^{1} and Ronny Van Keer^{1}

^{1}STMicroelectronics - ^{2}Radboud University - ^{3}Security Pattern

# Keccak specifications summary

Keccak (pronounced [kɛtʃak], like “ketchak”) is a family of sponge functions that has been standardized in the form of SHAKE128 and SHAKE256 extendable output functions and of SHA3-224 to SHA3-512 hash functions in FIPS 202, as well as cSHAKE128, cSHAKE256 and other functions in NIST SP 800-185. The text below is a quick description of Keccak using pseudo-code. In no way should this introductory text be considered as a formal and reference description of Keccak. Instead the goal here is to present Keccak with emphasis on readability and clarity. For a more formal description, the reader is invited to read the reference specifications or the FIPS 202 standard.

As a complement, one can also have a look at some simple implementations focused on readability and clarity, such as:

- Markku-Juhani O. Saarinen's tiny_sha3;
- our own readable and compact implementation in C or in Python.

# Structure of Keccak

Keccak is a family of hash functions that is based on the sponge construction, and hence is a sponge function family. In Keccak, the underlying function is a permutation chosen in a set of seven Keccak-$f$ permutations, denoted Keccak-$f[b]$, where $b \in \{25, 50, 100, 200, 400, 800, 1600\}$ is the width of the permutation. The width of the permutation is also the width of the state in the sponge construction.

The state is organized as an array of $5 \times 5$ lanes, each of length $w \in \{1, 2, 4, 8, 16, 32, 64\}$ and $b=25w$. When implemented on a 64-bit processor, a lane of Keccak-$f[1600]$ can be represented as a 64-bit CPU word.

We obtain the Keccak$[r,c]$ sponge function, with parameters capacity $c$ and bitrate $r$, if we apply the sponge construction to Keccak-$f[r+c]$ and by applying a specific padding to the message input.

# Pseudo-code description of the permutations

We first start with the description of Keccak-$f$ in the pseudo-code below. The number of rounds $n$ depends on the permutation width, and is given by $n = 12+2l$, where $2^l = w$. This gives 24 rounds for Keccak-$f[1600]$.

```
Keccak-f[b](A) {
for i in 0…n-1
A = Round[b](A, RC[i])
return A
}
Round[b](A,RC) {
# θ step
C[x] = A[x,0] xor A[x,1] xor A[x,2] xor A[x,3] xor A[x,4], for x in 0…4
D[x] = C[x-1] xor rot(C[x+1],1), for x in 0…4
A[x,y] = A[x,y] xor D[x], for (x,y) in (0…4,0…4)
# ρ and π steps
B[y,2*x+3*y] = rot(A[x,y], r[x,y]), for (x,y) in (0…4,0…4)
# χ step
A[x,y] = B[x,y] xor ((not B[x+1,y]) and B[x+2,y]), for (x,y) in (0…4,0…4)
# ι step
A[0,0] = A[0,0] xor RC
return A
}
```

In the pseudo-code above, the following conventions are in use. All the operations on the indices are done modulo 5. `A`

denotes the complete permutation state array, and `A[x,y]`

denotes a particular lane in that state. `B[x,y]`

, `C[x]`

, `D[x]`

are intermediate variables. The constants `r[x,y]`

are the rotation offsets (see Table 2), while `RC[i]`

are the round constants (see Table 1). `rot(W,r)`

is the usual bitwise cyclic shift operation, moving bit at position `i`

into position `i+r`

(modulo the lane size).

# Pseudo-code description of the sponge functions

Then, we present the pseudo-code for the Keccak$[r,c]$ sponge function, with parameters capacity $c$ and bitrate $r$. We assume for simplicity that $r$ is a multiple of the lane size, as this is the case for the standard instances.

The description below assumes that the input `M`

is represented as a string of bytes `Mbytes`

followed by a number (possibly zero, at most 7) of trailing bits `Mbits`

. The standard instances typically add a few trailing bits for domain separation. When made of bytes, the input of these functions then becomes `Mbytes`

, while `Mbits`

is solely determined by the instance used, see Table 3.

```
Keccak[r,c](Mbytes || Mbits) {
# Padding
d = 2^|Mbits| + sum for i=0..|Mbits|-1 of 2^i*Mbits[i]
P = Mbytes || d || 0x00 || … || 0x00
P = P xor (0x00 || … || 0x00 || 0x80)
# Initialization
S[x,y] = 0, for (x,y) in (0…4,0…4)
# Absorbing phase
for each block Pi in P
S[x,y] = S[x,y] xor Pi[x+5*y], for (x,y) such that x+5*y < r/w
S = Keccak-f[r+c](S)
# Squeezing phase
Z = empty string
while output is requested
Z = Z || S[x,y], for (x,y) such that x+5*y < r/w
S = Keccak-f[r+c](S)
return Z
}
```

In the pseudo-code above, `d`

is the delimited suffix, which encodes the trailing bits `Mbits`

and its length. The padded message `P`

is organised as an array of blocks `Pi`

, themselves organized as arrays of lanes. The variable `S`

holds the state as an array of lanes. The `||`

operator denotes the usual string concatenation. See also the page on bit and byte conventions for more details.

# Standard instances

The parameters defining the standard instances are given in the table below.

*r*

*c*Output length (bits)Security level (bits)

`Mbits`

`d`

SHAKE1281344
256
unlimited
128
1111
`0x1F`

SHAKE2561088
512
unlimited
256
1111
`0x1F`

SHA3-2241152
448
224
112
01
`0x06`

SHA3-2561088
512
256
128
01
`0x06`

SHA3-384832
768
384
192
01
`0x06`

SHA3-512576
1024
512
256
01
`0x06`

cSHAKE1281344
256
unlimited
128
00
`0x04`

cSHAKE2561088
512
unlimited
256
00
`0x04`

**Table 3: the parameters of the standard FIPS 202 and SP 800-185 instances.**The values of

`Mbits`

and `d`

assume that the input to these functions is made of bytes.
The value of the capacity *c* and of the suffix `Mbits`

jointly provide *domain separation* between the different instances. Because their input to Keccak never collide, domain-seprated instances will give unrelated outputs and act as independent functions.

The *customizable* extendable-output functions cSHAKE128 and cSHAKE256 from SP 800-185 have their own domain separation mechanism. In addition to the main input, these functions accept a *function name* input (defined by NIST) and a *customization string* input (user-defined). When these two additional inputs are both the empty string, cSHAKE128 and cSHAKE256 fall back on their corresponding SHAKE functions. The functions KMAC128, KMACXOF128, TupleHash128, TupleHashXOF128, ParallelHash128, ParallelHashXOF128 are defined on top of cSHAKE128, and similarly for KMAC256, KMACXOF256, TupleHash256, TupleHashXOF256, ParallelHash256, ParallelHashXOF256.

# Appendices

## Round constants

The round constants `RC[i]`

are given in the table below for the maximum lane size 64. For smaller sizes, they are simply truncated. The formula can be found in the reference specifications.

**Table 1: The round constants RC[i]**

## Rotation offsets

The rotation offsets `r[x,y]`

are given in the table below. The formula can be found in the reference specifications.

**Table 2: the rotation offsets**