NIST cryptographic showdown enters round two
NIST has eliminated 37 algorithms that had been submitted in a contest to choose the next cryptographic hash. Now, 14 contenders remain.
The competition to select the new Secure Hash Algorithm standard for government has moved into the second round. The National Institute of Standards and Technology has winnowed the 64 algorithims submitted down to 14 semifinalists.
Of the 64 algorithms submitted in 2008, 51 met minimum criteria for acceptance in the competition. The cryptographic community spent the next year hammering at the candidates, looking for flaws and weaknesses.
“We were pleased by the amount and quality of the cryptanalysis we received on the first round candidates, and more than a little amazed by the ingenuity of some of the attacks,” said Bill Burr, manager of NIST's Security Technology Group, in announcing the initial narrowing of the field in July.
Submitters of algorithms that made it through the first round of competition had until September to tweak the specifications or source code, and the final list of second round contenders was recently announced. The 14 second-round candidates are called BLAKE, BLUE MIDNIGHT WISH, CubeHash, ECHO, Fugue, Grøstl, Hamsi, JH, Keccak, Luffa, Shabal, SHAvite-3, SIMD, and Skein. Candidate algorithms are available online at www.nist.gov/hash-competition.
The selection of five finalists is expected by the end of this year, with adoption of the new standard, which will become SHA-3, expected in 2012.
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 securely confirm 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 eventually replace those algorithms now specified in Federal Information Processing Standard 180-2. The standard now includes SHA-1 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.
Harnessing the collective brainpower of the cryptographic community to identify strengths and weaknesses of possible hash algorithms is the idea behind the competition. This is the third cryptographic competition conducted by NIST to select a standard algorithm. The first, to select the Digital Encryption Standard in the 1970s, drew just two submissions, only one of which was seriously considered. In the 1990s the competition for the DES replacement, the Advanced Encryption Standard, drew about 15 submissions.
Burr said that in making second-round selections, NIST evaluators tried to include only algorithms with a serous chance of becoming SHA-3. Evaluators were more forgiving of the shortcomings of conservative designs with apparently large safety factors than of aggressive designs that were broken in the course of review.
The cryptographic community is invited to review, analyze and — if they can — break the second-round candidates. NIST plans to host the Second SHA-3 Candidate Conference at the University of California - Santa Barbara on Aug. 23-24, at which submitters will be invited to present their algorithms. The selection of five finalists is expected in the fall of 2010.