It will take a long time to find a new algorithm and get it ready for general use, so NIST decided not to wait until SHA-2 was actually compromised. Burr notes that SHA-1, an older hash algorithm that NIST no longer recommends because of weaknesses uncovered by Wang, “is more damaged than destroyed,” since a great deal of computation is still needed to find a collision. “We decided we had to rethink the whole thing,” Burr adds, “because we were just learning more and more about [how hash functions can be attacked], a lot of it disquieting.”
Beyond relieving worries about security, a new algorithm can take advantage of new trends in computing, such as dual-core processors, making it faster. “Hashes are the workhorse of cryptography,” Schneier says, “so performance is critical.”
NIST has received 64 entries for the competition and is looking for ways to narrow down the list. When NIST publishes the short list of entries at the end of this month, cryptographers the world over will begin analyzing them. This promises to be a lengthy process. “For many of the good submissions, discussions about their security will become more subtle than just talking about broken versus nonbroken,” says Christian Rechberger, a lecturer in cryptography at the Institute for Applied Information Processing and Communications, in Austria, and another competition entrant. “For this discussion, the time until the planned decision in 2012 is definitely needed.”
Brian Gladman, a U.K. cryptographer, says that the list of researchers who have submitted algorithms for the competition is impressive. It includes submissions from luminaries such as MIT computer-science professor Ron Rivest, who has already written several highly influential hash functions, and Joan Daemen, one of the designers of a widely-used encryption standard known as the Advanced Encryption Standard (AES).
Rechberger helps maintain the SHA-3 Zoo, a website that collects entries and related analysis. Ultimately, there could be several finalists that remain unbroken at the end of the competition. At the end, the winner will be chosen based on other considerations, such as its speed. For the coming months, however, analysis of entries will do much to advance the understanding of hash functions. And, more dramatically, cryptographers will begin breaking one another’s algorithms.