The Keccak sponge function family

Guido Bertoni1, Joan Daemen1,2, Michaël Peeters1 and Gilles Van Assche1

1STMicroelectronics
2Radboud University

Pages

Documents

Notes

Software and other files

Figures

The figures above are available under the Creative Commons Attribution license. In short, they can be freely used, provided that attribution is properly done in the figure caption, either by linking to this webpage or by citing the article where the particular figure first appeared.

Links

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. 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 in [1].)

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 ∈ {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×5 lanes, each of length w ∈ {1, 2, 4, 8, 16, 32, 64} (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

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

Keccak-f[b](A) {
  forall i in 0…nr-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],   forall x in 0…4
  D[x] = C[x-1] xor rot(C[x+1],1),                              forall x in 0…4
  A[x,y] = A[x,y] xor D[x],                           forall (x,y) in (0…4,0…4)

  ρ and π steps
  B[y,2*x+3*y] = rot(A[x,y], r[x,y]),                 forall (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]), forall (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).

Then, we present the pseudo-code for the Keccak[r,c] sponge function, with parameters capacity c and bitrate r. The description below is restricted to the case of messages that span a whole number of bytes. For messages with a number of bits not dividable by 8, we refer to the specifications [1] for more details. Also, we assume for simplicity that r is a multiple of the lane size; this is the case for the standard FIPS 202 instances.

Keccak[r,c](M, d) {
  Initialization and padding
  S[x,y] = 0,                               forall (x,y) in (0…4,0…4)
  P = M || d || 0x00 || … || 0x00
  P = P xor (0x00 || … || 0x00 || 0x80)

  Absorbing phase
  forall block Pi in P
    S[x,y] = S[x,y] xor Pi[x+5*y],          forall (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],                        forall (x,y) such that x+5*y < r/w
    S = Keccak-f[r+c](S)

  return Z
}

In the pseudo-code above, M is the input message, d is a byte that encodes from 0 to 7 suffix bits (e.g., d=0x01 for the plain Keccak without suffix, or see Table 3 for the FIPS 202 instances), and S denotes the state as an array of lanes. The padded message P is organised as an array of blocks Pi, themselves organized as arrays of lanes. The || operator denotes the usual byte string concatenation.

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 [1].

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 [1].

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
Table 2: the rotation offsets

FIPS 202 instances

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

r c d Output length (bits) Security level (bits)
SHAKE128 1344 256 0x1F unlimited 128
SHAKE256 1088 512 0x1F unlimited 256
SHA3-224 1152 448 0x06 224 112
SHA3-256 1088 512 0x06 256 128
SHA3-384 832 768 0x06 384 192
SHA3-512 576 1024 0x06 512 256
Table 3: the parameters of the standard FIPS 202 instances

References

[1] G. Bertoni, J. Daemen, M. Peeters and G. Van Assche, The Keccak reference, 2011

[FIPS 202] Federal Information Processing Standards publication 202, SHA-3 Standard: Permutation-Based Hash and Extendable-Output Functions, 2015