Guido Bertoni^{3}, Joan Daemen^{2}, Seth Hoffert, Michaël Peeters^{1}, Gilles Van Assche^{1} and Ronny Van Keer^{1}
^{1}STMicroelectronics  ^{2}Radboud University  ^{3}Security Pattern
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 SHA3224 to SHA3512 hash functions in FIPS 202, as well as cSHAKE128, cSHAKE256 and other functions in NIST SP 800185. The text below is a quick description of Keccak using pseudocode. 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:
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 64bit processor, a lane of Keccak$f[1600]$ can be represented as a 64bit 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.
We first start with the description of Keccak$f$ in the pseudocode 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]$.
Keccakf[b](A) {
for i in 0…n1
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[x1] 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 pseudocode 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).
Then, we present the pseudocode 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..Mbits1 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 = Keccakf[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 = Keccakf[r+c](S)
return Z
}
In the pseudocode 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.
The parameters defining the standard instances are given in the table below.
r  c  Output length (bits)  Security level (bits)  Mbits 
d 


SHAKE128  1344  256  unlimited  128  1111  0x1F 
SHAKE256  1088  512  unlimited  256  1111  0x1F 
SHA3224  1152  448  224  112  01  0x06 
SHA3256  1088  512  256  128  01  0x06 
SHA3384  832  768  384  192  01  0x06 
SHA3512  576  1024  512  256  01  0x06 
cSHAKE128  1344  256  unlimited  128  00  0x04 
cSHAKE256  1088  512  unlimited  256  00  0x04 
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, domainseprated instances will give unrelated outputs and act as independent functions.
The customizable extendableoutput functions cSHAKE128 and cSHAKE256 from SP 800185 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 (userdefined). 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.
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.
RC[0]  0x0000000000000001  RC[12]  0x000000008000808B 

RC[1]  0x0000000000008082  RC[13]  0x800000000000008B 
RC[2]  0x800000000000808A  RC[14]  0x8000000000008089 
RC[3]  0x8000000080008000  RC[15]  0x8000000000008003 
RC[4]  0x000000000000808B  RC[16]  0x8000000000008002 
RC[5]  0x0000000080000001  RC[17]  0x8000000000000080 
RC[6]  0x8000000080008081  RC[18]  0x000000000000800A 
RC[7]  0x8000000000008009  RC[19]  0x800000008000000A 
RC[8]  0x000000000000008A  RC[20]  0x8000000080008081 
RC[9]  0x0000000000000088  RC[21]  0x8000000000008080 
RC[10]  0x0000000080008009  RC[22]  0x0000000080000001 
RC[11]  0x000000008000000A  RC[23]  0x8000000080008008 
The rotation offsets r[x,y]
are given in the table below. The formula can be found in the reference specifications.
x = 3  x = 4  x = 0  x = 1  x = 2  

y = 2  25  39  3  10  43 
y = 1  55  20  36  44  6 
y = 0  28  27  0  1  62 
y = 4  56  14  18  2  61 
y = 3  21  8  41  45  15 