SHA-3

NIST emphasized that the goal of the SHA-3 competition wasn’t to replace the SHA-2 standard but to diversify the range of hash functions available for use. As with AES, it also established the standard through an open process in which the design of each proposal was subject to full public scrutiny. A significant side benefit of the SHA-3 process was that the cryptographic community greatly increased its collective knowledge about how to design hash functions, which, until then, had been a somewhat neglected area of research.

NIST received 64 candidate hash functions, of which 51 were then widely analyzed and reduced to 14 proposals. After further analysis, five finalists were selected and examined in even greater detail. The winning hash function was announced in 2012 as Keccak, designed by European industrial researchers (including Joan Daemen, co-designer of AES). The selection of Keccak was based on a combination of its design elegance, security margins, flexibility, and performance. Notably, it performed particularly well in both software and hardware compared to other entries that only ran well in software. In 2015, SHA-3 was formally published as FIPS 202.

SHA-3 design

Reflecting the diversity of properties and application of hash functions, from the outset, NIST encouraged SHA-3 candidates to offer flexibility in terms of facilitating a range of trade-offs between security and efficiency. Keccak, now SHA-3, achieves this through a general design technique called a sponge construction.

A sponge construction has these two important components:

• Internal state: This is the basic temporary memory register on which the sponge construction operates. Each round of computation of the sponge construction transforms the contents of the internal state. In the original Keccak proposal, this internal state consists of a variable number $s$ of bits. The final SHA-3 proposal fixes $s = 1600$. The internal state is divided into two sections. The capacity consists of $c$ bits, where $c$ is typically double the desired hash function output length $l$. The remainder of the internal state consists of $r = s – c$ bits known as the rate because it defines how many message bits are processed in each round.

• Permutation: This is the heart of the sponge construction and is responsible for each transformation of the internal state. The design of this permutation $f$ defines a specific instantiation of the sponge construction. This is why the design of SHA-3 specifies a carefully engineered function $f$ which permutes 1600 bits each time it is applied. We won’t describe the $f$ used in SHA-3 in any further detail here.

Assume the message $M$ we want to hash has been split into $r$-bit blocks $M_1, M_2, ... , M_n$ (after padding). The computation of the hash $h(M)$ of $M$ is determined as follows and is depicted in the illustration below: