We noticed you're browsing in private or incognito mode.

To continue reading this article, please exit incognito mode or log in.

Not a subscriber? Subscribe now for unlimited access to online articles.

Intelligent Machines

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.

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.

Keep up with the latest in intelligent machines at EmTech Digital.

The Countdown has begun.
March 25-26, 2019
San Francisco, CA

Register now
More from Intelligent Machines

Artificial intelligence and robots are transforming how we work and live.

Want more award-winning journalism? Subscribe to Print + All Access Digital.
  • Print + All Access Digital {! insider.prices.print_digital !}*

    {! insider.display.menuOptionsLabel !}

    The best of MIT Technology Review in print and online, plus unlimited access to our online archive, an ad-free web experience, discounts to MIT Technology Review events, and The Download delivered to your email in-box each weekday.

    See details+

    12-month subscription

    Unlimited access to all our daily online news and feature stories

    6 bi-monthly issues of print + digital magazine

    10% discount to MIT Technology Review events

    Access to entire PDF magazine archive dating back to 1899

    Ad-free website experience

    The Download: newsletter delivery each weekday to your inbox

    The MIT Technology Review App

You've read of three free articles this month. for unlimited online access. You've read of three free articles this month. for unlimited online access. This is your last free article this month. for unlimited online access. You've read all your free articles this month. for unlimited online access. You've read of three free articles this month. for more, or for unlimited online access. for two more free articles, or for unlimited online access.