Print this article

Comment

January 2009

Code monkeys jockey for winning algorithm

The National Institute of Standards and Technology (NIST) is having a contest to see who can write the most impenetrable piece of code.
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.

Technology Review reported the winning code would become a building block of a wide variety of Internet protocols, including those used to safeguard communications between banks and their customers.

NIST organized the competition and plans to release a short-list of the best entries by the time this magazine mails, beginning a four-year process of painstaking analysis to find the overall winner.

All this effort is necessary because the current standard—the Secure Hash Algorithm 2 (SHA-2)—is starting to show more gray hair.

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 has not been tampered with en route.

However, a hash function is only 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. Cryptographers call it “a collision.”

The latter issue is complicated by the fact it is impossible to completely avoid collisions. Therefore, the best algorithm is one that simply makes collisions extremely hard to produce.

“You shouldn’t be able to find them,” said William Burr, manager of the Security Technology Group for NIST. “The computation should be too great.”

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 the actual compromise of SHA-2.

Burr notes 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.

Beyond relieving worries about security, a new algorithm can take advantage of new trends in computing, such as dual-core processors, making it faster.

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, cryptographers the world over will begin analyzing them.