Secure hash competition down to the final 5

The National Institute of Standards and Technology has narrowed the field of competitors for a new standard Secure Hash Algorithm to the final five, and their developers now are making final tweaks to their algorithms before entering a year of public analysis.

NIST expects to name the new SHA-3 algorithm in 2012. It will become part of the Federal Information Processing Standards 180-3 list of hash algorithms approved for creating digital signatures and other authentications of government documents.

The competition began in 2008 with submission of 64 algorithms, of which 51 met minimum NIST criteria for acceptance. The cryptographic community spent the next year hammering at the candidates, looking for flaws and weaknesses. Fourteen algorithms advanced to the second round in July 2009. Developers of the second-round winners defended their work at a conference held in August at the University of California, Santa Barbara, and finalists were selected from that pool.

Related stories:

The next Secure Hash Algorithm had better be a good one

NIST is nearly ready to pick the next hash algorithm

“The selection was challenging because we had a strong field of 14 contenders,” Bill Burr, manager for the Cryptographic Technology Group at NIST’s Computer Security Division, wrote in announcing the winners in December. “Security was our greatest concern, and we took this very seriously, but none of these candidates was clearly broken.”

The five finalists were chosen not only because of their security but also for their performance factors, Burr said. “NIST wanted highly secure algorithms that also performed well.”

The finalists are:

• BLAKE, submitted by Jean-Philippe Aumasson (Nagravision SA, Cheseaux, Switzerland), Luca Henzen (ETHZ, Zürich, Switzerland), Willi Meier (FHNW, Windisch, Switzerland) and Raphael C.-W. Phan (Loughborough University, UK).
• Grøstl, submitted by Søren Steffen Thomsen, Martin Schläffer, Christian Rechberger, Florian Mendel, Krystian Matusiewicz, Lars R. Knudsen and Praveen Gauravaram from Technical University of Denmark and TU Graz.
• JH, submitted by Hongjun Wu.
• Keccak, submitted by Guido Bertoni, Joan Daemen and Gilles Van Assche (STMicroelectronics) and Michaël Peeters (NXP Semiconductors).
  
• Skein, submitted by Niels Ferguson, Stefan Lucks, Bruce Schneier, Doug Whiting, Mihir Bellare, Tadayoshi Kohno, Jon Callas and Jesse Walker.

A hashing algorithm is a cryptographic formula for generating a unique, fixed-length numerical digest — or hash — of a message. Because the contents of the message cannot be derived from the hash and because the hash is to a high degree of probability unique for each message, it can be used to confirm with a high degree of assurance that a document has not been altered. It also can be used to effectively sign an electronic document and link the signature to the contents.

SHA-3 will augment and possibly eventually replace those algorithms now specified in FIPS 180-2. The standard now includes the SHA-1 algorithm as well as SHA-224, SHA-256, SHA-384 and SHA-512, collectively known as SHA-2. The standards undergo regular reviews and the decision was made to open a competition for SHA-3 in 2007 after weaknesses had been discovered in the currently approved algorithms.

Despite the weaknesses, the SHA-2 family remains viable and there currently are no plans to retire it, said Shu-jen Chang, a computer specialist in the Cryptographic Technology Group.

“No cryptanalysis result has seriously threatened the security of the SHA-2 family of hash algorithms,” she said. “It will remain a FIPS standard as long as its security is not threatened.

SHA-3 was meant to ‘augment’, not ‘replace,’ unless it’s necessary, of course, the algorithms currently specified in FIPS 180-3.”

The intent of the competition is to select a single algorithm for SHA-3 rather than a family or a group to choose from, Chang said.

“It takes a great deal of effort to deploy a cryptographic algorithm and make it interoperable with the existing infrastructure,” she said. “Another consideration is that hash algorithms may need to be implemented on various resource-restricted platforms; supporting multiple SHA-3 algorithms in addition to SHA-2 is not considered a feasible solution.”

Although none of the 14 algorithms in the second round were broken, the selection committee was conservative in its process and chose to err on the side of security, Burr wrote in announcing the finalists.

“In some cases we did not select algorithms with exceptional performance, largely because something about them made us ‘nervous,’ even though we knew of no clear attack against the full algorithm,” he said.

Although none of the finalists excelled in every dimension of performance, they all achieved at least tolerable performance on mainstream desktop or server systems, Burr said. Some candidates that performed with adequate speed were eliminated because implementation required too much of the potential application space, making them impractical.

NIST also considered diversity in selecting finalists, choosing algorithms that incorporated a number of new design ideas from recent years.

Because the new standard will remain a part of the federal security toolkit for a long time, it has been suggested that the SHA-3 selection process should be slowed down to give time for a more thorough examination of the candidates, but Chang said this is not necessary.

“We did not feel that we had been rushed throughout the competition, and there have been plenty of cryptanalysis and performance results published on the candidates,” she said. “Therefore, unless we are convinced otherwise, we are proceeding according to the published schedule.”