The birth of a new hashing standard: SHA-3

2/19/2013 12:47 PM EST

A cryptographic hash function converts an arbitrary-length message into a fixed-length digest, and it is a fundamental step in the efficient implementation of electronic messages. Back in 2004, significant attacks on the standard hash functions of that time were getting published everywhere. These attacks almost completely broke MD5, SHA-0 and later on SHA-1. At that time, NIST announced that it would phase out SHA-1 and replace it with the more stable SHA-2. However being algorithmically similar to SHA-1, NIST feared that SHA-2 might itself get broken in the near future, and in Nov 2007 announced a competition to select a new standard for cryptographic hashing, SHA-3.

The competition ended Oct 2012 and out of 64 submissions Keccak was declared the winner. Keccak (pronounced “ketchak”) was designed by a cryptographic group from Belgium and Italy, namely Guido Bertoni, Joan Daemen, Gilles Van Assche of STMicroelectronics and Michaël Peeters of NXP Semiconductors. Joan Daemen is also a co-author of the block cipher Rijndael algorithm which won the AES competition. Later research on the cryptanalysis of hashing algorithms improved the confidence in SHA-2 showing that it can still be safely used. However, NIST still slightly favors Keccak for being an entirely different algorithm. “It seems very unlikely that a single new cryptanalytic attack or approach could threaten both algorithms,” as quoted from the NIST announcement statement.

Figure 1: The Sponge Construction, from http://sponge.noekeon.org/

It appears that NIST will keep the two algorithms as a backup for each other. Keccak uses a new Sponge Construction chaining mode with a fixed permutation function ( f ) as shown in the figure. The idea is to limit the effect of the new input data to only r (rate) bits of the internal state. The rest of the state, of size c (capacity) is not directly affected by the current input. The capacity is used as a design parameter to trade security strength for throughput. The size of the internal state of Keccak is 1600 bits organized as a 5×5×64 array, with the rate and capacity configured according to the desired level of security. The Keccak SHA-3 standard proposes digests of 224, 256, 384 and 512 bits. The permutation function is simple yet effective, resulting in Keccak's remarkable performance in hardware modules (ASICs and FPGAs). The designers augmented Keccak with different modes of operation to extend its use toward authentication, random number generation, and high-performance parallel implementation.

The Center for Embedded Systems for Critical Applications at Virginia Tech has contributed to the selection process by supporting the hardware benchmarking of the candidates. Under a NIST funded project lead by CESCA faculty members Patrick Schaumont and Leyla Nazhand-Ali, we designed an ASIC which included all of the final round algorithms and provided their performance results. We shipped the SHA-3 ASIC to 8 different research groups all over the world for various performance and security evaluations. The project continues with evaluation of the vulnerabilities of the winner algorithm ‘Keccak’ against different types of Implementation attacks.