Tuesday, November 18, 2008

An Algorithm with No Secrets

Cryptographers will compete to define a new standard.

By Erica Naone --- from technologyreview.com

Cryptographers from around the world have laid their best work on the line in a contest to find a new algorithm that will become a critical part of future communications across the Internet. The winning code will become a building block of a wide variety of Internet protocols, including those used to safeguard communications between banks and their customers. The National Institute of Standards and Technology (NIST) organized the competition and plans to release a short list of the best entries by the end of this month, beginning a four-year process of painstaking analysis to find the overall winner.

Credit: Technology Review

All this effort is necessary because the current standard--the Secure Hash Algorithm 2 (SHA-2)--is starting to show its age. In 2005, Xiaoyun Wang, a professor at the Center for Advanced Study at Tsinghua University, in China, found weaknesses in several related hashing algorithms. Since then, she and her peers in the field have chipped away at other hashing schemes, making officials worry that SHA-2 will also eventually succumb.

A hash algorithm turns an ordinary message into a "digital fingerprint," which can then be used to keep the original message secret during transit or to guarantee that it hasn't been tampered with en route. But a hash function is only considered secure if there is no practical way to run it backward and find the original message from the fingerprint. Equally important, there should be no trivial way to produce two messages with exactly the same fingerprint. The weaknesses discovered by Wang and others relate to this problem--something cryptographers call "a collision." The latter issue is complicated by the fact that it is impossible to completely avoid collisions. So the best algorithm is one that simply makes collisions extremely hard to produce. "You shouldn't be able to find them," says William Burr, manager of the Security Technology Group for NIST. "The computation should be too great."

But competition entrants face another major challenge. While encryption algorithms rely on keeping a "key" secret from attackers, cryptographic hash functions can have no such secrets. This gives an attacker plenty of avenues for cracking a hash algorithm, says Burr.

"Hash functions are the most widely used and the most poorly understood cryptographic primitives," adds Bruce Schneier, chief security technology officer at BT Counterpane and one of the competition entrants. "It's possible that everything gets broken here, simply because we don't really understand how hash functions work."

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.

http://www.partow.net/programming/hashfunctions/index.html