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.

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.

Rotation offsets

The rotation offsets r[x,y] are given in the table below. The formula can be found in the reference specifications.