This website does readability filtering of other pages. All styles, scripts, forms and ads are stripped. If you want your website excluded or have other feedback, use this form.

Keccak Team

Team Keccak

Guido Bertoni3, Joan Daemen1,2, Michaël Peeters1, Gilles Van Assche1 and Ronny Van Keer1
1STMicroelectronics - 2Radboud University - 3Security 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:

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.

rcOutput length (bits)Security level (bits)Mbitsd 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.

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 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.

x = 3x = 4x = 0x = 1x = 2 y = 225 39 3 10 43 y = 155 20 36 44 6 y = 028 27 0 1 62 y = 456 14 18 2 61 y = 321 8 41 45 15 Table 2: the rotation offsets