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 (SHA3). 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 in [1].
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 Keccakf permutations, denoted Keccakf[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 64bit processor, a lane of Keccakf[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 Keccakf[r+c] and by applying a specific padding to the message input.
Pseudocode description
We first start with the description of Keccakf in the pseudocode below. The number of rounds n_{r} depends on the permutation width, and is given by n_{r} = 12+2l, where 2^{l} = w. This gives 24 rounds for Keccakf[1600].
Keccakf[b](A) { forall i in 0…n_{r}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[x1] 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 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. 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 SHA3 candidate parameters in [2].
Keccak[r,c](M) { Initialization and padding S[x,y] = 0, forall (x,y) in (0…4,0…4) P = M  0x01  0x00  …  0x00 P = P xor (0x00  …  0x00  0x80) Absorbing phase forall block P_{i} in P S[x,y] = S[x,y] xor P_{i}[x+5*y], forall (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], forall (x,y) such that x+5*y < r/w S = Keccakf[r+c](S) return Z }
In the pseudocode above, S
denotes the state as an array of lanes. The padded message P
is organised as an array of blocks P_{i}
, 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 
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 
References
[1] G. Bertoni, J. Daemen, M. Peeters and G. Van Assche, The Keccak reference, 2011
[2] G. Bertoni, J. Daemen, M. Peeters and G. Van Assche, The Keccak SHA3 submission, 2011