And the winner is... KECCAK !

Wed 24 October 2012 by chrys

On November 2006, NIST (National Institute of Standards and Technology) announced a public competition for developing a new cryptographic hash algorithm which would become SHA-3. The submission dead-line was October 2008. NIST received 64 submissions and announced 51 valid candidates for the first round in December 2008 and 14 (including French candidates ECHO and Shabal) for the second round in July 2009. On December 2010, they announced the 5 final round candidates which were BLAKE, Grostl, JH, KECCAK and Skein. Finally, this month (October 2, 2012), NIST announced that the winner of the SHA-3 Cryptographic Hash Algorithm Competition is KECCAK.

KECCAK sponge function family

KECCAK is a hash function family based on the sponge construction and so its building block is a permutation, composed of several iterations. This article is an introductory description of the KECCAK hash function which was submitted to the competition and a brief summary of its security analysis. However, for facilitating the reading, before presenting KECCAK we will present a brief description of the sponge construction.

Sponge function construction

A sponge construction builds a function F by using a fixed length permutation f and a padding. This function F is called a sponge function and takes a variable length input (an element of Z*2) and returns a binary string of any requested length. The permutation f operates on a fixed number b of bits which is called the width and is the state on which the function operates. Actually, the state size is the sum of the two main parameters r and c, which are called bitrate and capacity respectively. The whole procedure of a sponge function construction can be viewed in figure 1 and is described below.

Sponge

The first step of the procedure of the sponge function construction is to pad the message M and to divide it into blocs of r bits. Afterwards, the construction proceeds in two phases: the absorbingphase and the squezzing phase. In the absorbing phase, all r bit input message blocks are xored with the first r bits of the state, interleaved with the application of the f function. When all blocks have been processed, the absorbing phase finishes and the squeezing phase begins. Next, in the second phase the first r bits of the state are generated as output blocks, interleaved with applications of the function f . The second phase is finished after the wanted length of output digest has been produced.

KECCAK for SHA-3 proposal

For the SHA-3 proposal the full KECCAK-f [1600] state is composed of 1600 bits, organized in 64 slices of 5 × 5 bits. The position of a bit in a slice can be given either by its x and y value or by its bit number. The z coordinate gives the number of the slice, 0 ≤ z ≤ 63.

For generating the desired output, each version of the KECCAK hash family needs a different bitrate value r and a different capacity value c. More precisely, for an output of 224 bits we have r = 1152 and c = 448, for 256 bits we have r = 1088 and c = 512, for 384 bits we have r = 832 and c = 768 and finally for 512 bits we have r = 576 and c = 1024.

KECCAK-f [1600] is an iterated permutation, consisting of a sequence of n_{r} rounds R. The state size determines the number of rounds and it has been updated to 24 (originally it was 18) for the second round of the competition. Every round function is divided into 5 steps: R = ι ◦ χ ◦ π ◦ ρ ◦ θ.

  • The ι step does an addition of the round constants and is aimed at disrupting symmetry.
  • The function χ is the only nonlinear mapping in KECCAK. Without it, the KECCAK round function would be linear. It applies a 5 × 5 S-box on one row.
  • The permutation π permutes the bits in a slice.
  • The ρ permutation translates a bit in z direction.
  • The permutation θ is a linear map which XORs every bit of a column with the XOR of two other columns.

Attacks

There are two types of attacks on KECCAK hash function. The first one concerns weaknesses in the KECCAK’s internal permutation. The most interesting result in this category is the zero-sum distinguisher first proposed by J.-P. Aumasson et al. (2009) and then extended by C. Boura et al. (2010, 2011). However, the complexities of the attacks are very high (for 24 rounds of KECCAK thecomplexity is 21590 ).

The second type of attacks includes all pre-image and collision attacks. Among them, there is a second pre-image attack proposed by D. J. Bernstein which breaks 8 rounds of KECCAK. However, the attack’s complexity is marginally lower than the exhaustive search. Also, it includes a collision and a near-collision attack on 2 and 3 rounds respectively of KECCAK (complexity 233 and 2 55 respectively) by M. Plasencia et al. (Indocrypt 2011). Finally, I. Dinur et al. presented at FSE 2012 a collision attacks on 4 rounds KECCAK.

Performances

As we can see in here http://bench.cr.yp.to/results-sha3.html, KECCAK is not considered very fast in software. For example, if we compare KECCAK 512 and SHA512 we can see that KECCAK is much slower than SHA-2. However, KECCAK has very good results when implemented in hardware and this is one of the reasons that KECCAK was chosen by NIST.

Conclusion

KECCAK certainly differs from all functions of the MD family (MD5, SHA-1, SHA-2) as it uses a sponge function construction. This fact can be considered neither as an advantage nor a disadvantage.Sponge functions are a new construction that will now, thanks to the nomination of KECCAK as SHA-3, attract more attention from cryptographers. Certainly this is a minus as this construction is not very well analysed yet. However, it is a positive fact that SHA-3 has not the same structure as SHA-2. That means that a new attack could not threaten both algorithms at the same time. Moreover, as SHA-2 is still very solid and is not going to be replaced by KECCAK soon, there is no need to have two functions with similar construction.