NIST is nearly ready to pick the next hash algorithm
Agency will choose from among 14 semifinalists
- By William Jackson
- Aug 18, 2010
Developers of the 14 semifinalist algorithms for the new SHA-3 Secure Hash Algorithm standard will have a chance to defend their work next week at the second NIST candidate conference, being held at the University of California, Santa Barbara.
“We’re creating a record” on which to base selection of four to six finalists, expected to be named by the end of the year, said Bill Burr, manager of the Cryptographic Technology Group a the National Institute of Standards and Technology. “All in all we’ve got quite a bit of performance data. At this point we have a surprising amount of data on hardware implementation on all 14 candidates.”
Final selection of a new standard hashing algorithm for government is expected by early 2012, although that date could slip if additional analysis is needed, Burr said.
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.
Sixty-four algorithms were submitted to NIST in 2008, of which 51 were met minimum criteria for acceptance in the competition. The cryptographic community spent the next year hammering at the candidates, looking for flaws and weaknesses and 14 algorithms advanced to the second round in July 2009. The 14 second-round candidates are BLAKE, Blue Midnight Wish, CubeHash, ECHO, Fugue, Grøstl, Hamsi, JH, Keccak, Luffa, Shabal, SHAvite-3, SIMD and Skein. Candidate algorithms are available online, and NIST has published a status report on the first round of the competition.
Next week’s conference will give the entrants a chance to address the results of analysis and testing over the past year. The conference is being held in conjunction with this week’s overlapping CRYPTO 2010 conference and the workshops on Cryptographic Hardware and Embedded Systems, being held by the International Association for Cryptologic Research at Santa Barbara.
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.
With 14 semifinalists to hear from, the conference schedule will be tight, with each presenter having only about 15 minutes to address results of analysis over the past year and present an argument for moving to the final round. After a second year of testing and analysis by the crypto community, a final candidate conference is expected to be held in the winter of 2012.
Even when the field has been narrowed to about five finalists, doing an analysis of cryptographic tools that are expected to remain in the federal toolkit for years to come takes considerable time and effort, Burr said, and there have been calls to slow down the process and extend it beyond the current 2012 end point.
“I’m not inclined to do that, but I’m open to arguments,” Burr said.
The timeline for selection will depend in part on developments in cryptography and in attacks against existing standards, he said. NIST might have some additional breathing space in selecting a new standard algorithm because there has been little progress toward breaking SHA-2.
“There was a lot of fear about how much progress there would be in attacking SHA-2,” Burr said, but hackers to not appear to be focusing on that. “SHA-2 is falling, although more slowly than we thought.”