An Algorithm with No Secrets

Cryptographers will compete to define a new standard.

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."

Story continues below

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."