The Keccak sponge function family

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

1STMicroelectronics

2NXP Semiconductors

Pages

Notes

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 hash functions that has been submitted as candidate to NIST's hash algorithm competition (SHA-3). 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 specification [1] or the main document [2].

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,d] sponge function, with parameters capacity c, bitrate r and diversifier d, 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,d] sponge function, with parameters capacity c, bitrate r and diversifier d. 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 SHA-3 candidate parameters in [1].

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

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

References

[1] G. Bertoni, J. Daemen, M. Peeters and G. Van Assche, Keccak specifications, version 2, submission to NIST, 2009

[2] G. Bertoni, J. Daemen, M. Peeters and G. Van Assche, Keccak sponge function family main document, submission to NIST (updated), 2009