NIST hash function competition
Encyclopedia
The NIST hash function competition is an open competition held by the US National Institute of Standards and Technology
for a new SHA-3 function to replace the older SHA-1 and SHA-2
, which was formally announced in the Federal Register
on November 2, 2007. "NIST is initiating an effort to develop one or more additional hash algorithms through a public competition, similar to the development process
for the Advanced Encryption Standard
(AES)."
Submissions were due October 31, 2008, with a list of candidates accepted for the first round published December 9, 2008. NIST held a conference in late February 2009 where submitters gave presentations on their algorithms and NIST officials discussed criteria for narrowing down the field of candidates for Round 2. The list of 14 candidates accepted to Round 2 was published on July 24, 2009. Another conference was held August 23-24, 2010 (after CRYPTO 2010) at the University of California, Santa Barbara
, where the second-round candidates were discussed. The announcement of the final round candidates occurred on December 10, 2010 and the proclamation of a winner and publication of the new standard are scheduled to take place in 2012.
NIST selected 51 entries for the Round 1. 14 of them advanced to Round 2, from which 5 finalists were selected.
NIST noted some factors that figured into its selection as it announced the finalists:
NIST has released a report explaining its evaluation algorithm-by-algorithm.
but did not pass to Round Two. They have neither been conceded by the
submitters nor have had substantial cryptographic weaknesses. However, most of
them have some weaknesses in the design components, or performance issues.
National Institute of Standards and Technology
The National Institute of Standards and Technology , known between 1901 and 1988 as the National Bureau of Standards , is a measurement standards laboratory, otherwise known as a National Metrological Institute , which is a non-regulatory agency of the United States Department of Commerce...
for a new SHA-3 function to replace the older SHA-1 and SHA-2
SHA-2
In cryptography, SHA-2 is a set of cryptographic hash functions designed by the National Security Agency and published in 2001 by the NIST as a U.S. Federal Information Processing Standard. SHA stands for Secure Hash Algorithm. SHA-2 includes a significant number of changes from its predecessor,...
, which was formally announced in the Federal Register
Federal Register
The Federal Register , abbreviated FR, or sometimes Fed. Reg.) is the official journal of the federal government of the United States that contains most routine publications and public notices of government agencies...
on November 2, 2007. "NIST is initiating an effort to develop one or more additional hash algorithms through a public competition, similar to the development process
Advanced Encryption Standard process
The Advanced Encryption Standard , the block cipher ratified as a standard by National Institute of Standards and Technology of the United States , was chosen using a process markedly more open and transparent than its predecessor, the aging Data Encryption Standard...
for the Advanced Encryption Standard
Advanced Encryption Standard
Advanced Encryption Standard is a specification for the encryption of electronic data. It has been adopted by the U.S. government and is now used worldwide. It supersedes DES...
(AES)."
Submissions were due October 31, 2008, with a list of candidates accepted for the first round published December 9, 2008. NIST held a conference in late February 2009 where submitters gave presentations on their algorithms and NIST officials discussed criteria for narrowing down the field of candidates for Round 2. The list of 14 candidates accepted to Round 2 was published on July 24, 2009. Another conference was held August 23-24, 2010 (after CRYPTO 2010) at the University of California, Santa Barbara
University of California, Santa Barbara
The University of California, Santa Barbara, commonly known as UCSB or UC Santa Barbara, is a public research university and one of the 10 general campuses of the University of California system. The main campus is located on a site in Goleta, California, from Santa Barbara and northwest of Los...
, where the second-round candidates were discussed. The announcement of the final round candidates occurred on December 10, 2010 and the proclamation of a winner and publication of the new standard are scheduled to take place in 2012.
Entrants
This is an incomplete list of known submissions.NIST selected 51 entries for the Round 1. 14 of them advanced to Round 2, from which 5 finalists were selected.
Finalists
NIST has selected five SHA-3 candidate algorithms to advance to the third (and final) round :- BLAKEBLAKE (hash function)BLAKE is a cryptographic hash function submitted to the NIST hash function competition by Jean-Philippe Aumasson, Luca Henzen, Willi Meier, and Raphael C.-W. Phan. It is based on Dan Bernstein's ChaCha stream cipher, but a permuted copy of the input block, XORed with some round constants, is added...
- GrøstlGrøstlGrøstl is a cryptographic hash function submitted to the NIST hash function competition by Praveen Gauravaram, Lars Knudsen, Krystian Matusiewicz, Florian Mendel, Christian Rechberger, Martin Schläffer, and Søren S. Thomsen. Grøstl was chosen as one of the five finalists of the competition. It uses...
(KnudsenLars KnudsenLars Ramkilde Knudsen is a Danish researcher in cryptography, particularly interested in the design and analysis of block ciphers, hash functions and message authentication codes .-Academic:...
et al.) - JHJH (hash function)JH is a cryptographic hash function submitted to the NIST hash function competition by Hongjun Wu. JH was chosen as one of the five finalists of the competition. JH has a 1024-bit state, and works on 512-bit input blocks...
- KeccakKeccakKeccak is a cryptographic hash function designed by Guido Bertoni, Joan Daemen, Michaël Peeters and Gilles Van Assche. Keccak is one of five finalists in the NIST hash function competition to select a SHA-3 algorithm. The authors claim 12.5 cycles per byte on an Intel Core 2 CPU...
(Keccak team, DaemenJoan DaemenJoan Daemen |Limburg]], Belgium) is a Belgian cryptographer and one of the designers of Rijndael, the Advanced Encryption Standard , together with Vincent Rijmen. He has also designed or co-designed the MMB, Square, SHARK, NOEKEON, 3-Way, and BaseKing block ciphers...
et al.) - SkeinSkein (hash function)Skein is a cryptographic hash function and one out of five finalists in the NIST hash function competition to design what will become the SHA-3 standard, the intended successor of SHA-1 and SHA-2...
(SchneierBruce SchneierBruce Schneier is an American cryptographer, computer security specialist, and writer. He is the author of several books on general security topics, computer security and cryptography, and is the founder and chief technology officer of BT Managed Security Solutions, formerly Counterpane Internet...
et al.)
NIST noted some factors that figured into its selection as it announced the finalists:
- Performance: "A couple of algorithms were wounded or eliminated by very large [hardware gate] area requirement – it seemed that the area they required precluded their use in too much of the potential application space."
- Security: "We preferred to be conservative about security, and in some cases 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."
- Analysis: "NIST eliminated several algorithms because of the extent of their second-round tweaks or because of a relative lack of reported cryptanalysis – either tended to create the suspicion that the design might not yet be fully tested and mature."
- Diversity: The finalists included hashes based on different modes of operation, including the HAIFA and sponge hash constructions, and with different internal structures, including ones based on AES, bitslicing, and alternating XOR with addition.
NIST has released a report explaining its evaluation algorithm-by-algorithm.
Did not pass to Final Round
The following hash function submissions were accepted for Round Two, but did not make it to the final round. As noted in the announcement of the finalists, "none of these candidates was clearly broken".- Blue Midnight Wish
- CubeHashCubeHashCubeHash is a cryptographic hash function submitted to the NIST hash function competition by Daniel J. Bernstein. Message blocks are XORed into the initial bits of a 128-byte state, which goes through an r-round bijective transformation between blocks. The initial NIST proposal required about...
(BernsteinDaniel J. BernsteinDaniel Julius Bernstein is a mathematician, cryptologist, programmer, and professor of mathematics at the University of Illinois at Chicago...
) - ECHO (France TelecomFrance TélécomFrance Telecom S.A. is the main telecommunications company in France, the third-largest in Europe and one of the largest in the world. It currently employs about 180,000 people and has 192.7 million customers worldwide . In 2010 the group had revenue of €45.5 billion...
) - FugueFugue (hash function)Fugue is a cryptographic hash function submitted by IBM to the NIST hash function competition. It was designed by Shai Halevi, William E. Hall, and Charanjit S. Jutla. Fugue takes an arbitrary-length message and compresses it down to a fixed bit-length...
(IBMIBMInternational Business Machines Corporation or IBM is an American multinational technology and consulting corporation headquartered in Armonk, New York, United States. IBM manufactures and sells computer hardware and software, and it offers infrastructure, hosting and consulting services in areas...
) - Hamsi
- Luffa
- Shabal
- SHAvite-3
- SIMDSIMD (hash function)SIMD is a cryptographic hash function based on the Merkle–Damgård construction submitted to the NIST hash function competition by Gaëtan Leurent...
Did not pass to Round Two
The following hash function submissions were accepted for Round Onebut did not pass to Round Two. They have neither been conceded by the
submitters nor have had substantial cryptographic weaknesses. However, most of
them have some weaknesses in the design components, or performance issues.
- ARIRANG (CIST - Korea University)
- CHI
- CRUNCH
- FSBFast Syndrome Based HashIn cryptography, the Fast Syndrome-based hash Functions are a family of cryptographic hash functions introduced in 2003 by Daniel Augot, Matthieu Finiasz, and Nicolas Sendrier....
- LaneLane (hash function)Lane is a cryptographic hash function submitted to the NIST hash function competition; it was designed by Sebastiaan Indesteege with contributions by Elena Andreeva, Christophe De Cannière, Orr Dunkelman, Emilia Käsper, Svetla Nikova, Bart Preneel and Elmar Tischhauser. It re-uses many components...
- Lesamnta
- MD6MD6The MD6 Message-Digest Algorithm is a cryptographic hash function. It uses a Merkle tree-like structure to allow for immense parallel computation of hashes for very long inputs...
(RivestRon RivestRonald Linn Rivest is a cryptographer. He is the Andrew and Erna Viterbi Professor of Computer Science at MIT's Department of Electrical Engineering and Computer Science and a member of MIT's Computer Science and Artificial Intelligence Laboratory...
et al.) - SANDstormSandstormSandstorm can refer to:* Dust storm, a storm caused by strong winds and blowing sand or dust* "Sandstorm" , a trance song by Darude* "Sandstorm" , a song on Cast's debut album, All Change...
(Sandia National LaboratoriesSandia National LaboratoriesThe Sandia National Laboratories, managed and operated by the Sandia Corporation , are two major United States Department of Energy research and development national laboratories....
) - Sarmal
- SWIFFTSWIFFTIn cryptography, SWIFFT is a collection of provably secure hash functions. It is based on the concept of the Fast Fourier Transform . SWIFFT is not the first hash function based on FFT, but it sets itself apart by providing a mathematical proof of its security. It also uses the LLL basis reduction...
X - TIB3
Entrants with substantial weaknesses
The following non-conceded Round One entrants have had substantial cryptographic weaknesses announced.- AURORA (SonySony, commonly referred to as Sony, is a Japanese multinational conglomerate corporation headquartered in Minato, Tokyo, Japan and the world's fifth largest media conglomerate measured by revenues....
and Nagoya UniversityNagoya UniversityNagoya University is one of the most prestigious universities in Japan. It can be seen in the several rankings such as shown below.-General Rankings:...
) - Blender
- Cheetah
- Dynamic SHA
- Dynamic SHA2
- ECOHElliptic curve only hashThe elliptic curve only hash algorithm was submitted as a candidate for SHA-3 in the NIST hash function competition. However, it was rejected in the beginning of the competition since a second pre-image attack was found....
- Edon-R
- EnRUPT
- ESSENCE
- LUX
- MCSSHA-3
- NaSHA
- Sgàil
- Spectral HashSpectral HashSpectral Hash is a cryptographic hash function submitted to the NIST hash function competition by Gokay Saldamlı, Cevahir Demirkıran, Megan Maguire, Carl Minden, Jacob Topper, Alex Troesch, Cody Walker, Çetin Kaya Koç. It uses a Merkle-Damgard construction and employs several mathematical...
- Twister
- Vortex
Conceded entrants
The following Round One entrants have been officially retracted from the competition by their submitters; they are considered broken according to the NIST official Round One Candidates web site. As such, they are withdrawn from the competition.- Abacus
- Boole
- DCH
- Khichidi-1
- MeshHash
- SHAMATA
- StreamHash
- Tangle
- WaMM
- Waterfall
Rejected entrants
Several submissions received by NIST were not accepted as First Round Candidates, following an internal review by NIST. In general, NIST gave no details as to why each was rejected. NIST also has not given a comprehensive list of rejected algorithms; there are known to be 13, but only the following are public.- HASH 2X
- Maraca
- NKS 2D
- Ponic
- ZK-Crypt