New King of Security Algorithms Crowned
A five-year hunt for a new cryptographic hash scheme leads to the discovery that the old one was really good
Image: Henrik Jonsson/iStockphoto
A new cryptographic hash algorithm, proclaimed the winner of a five-year competition in October, is literally a solution in search of a problem.
Basically, cryptographic hash algorithms are a way to ensure information security. They are typically used in digital signatures and in establishing connections with secure websites. Data that is run through a hash algorithm produces a shorter string of bits; this string acts as a kind of digest of the data. Any change to the data changes the bit string. The resulting string, therefore, acts as a fingerprint of the data, guaranteeing that no one has tampered with it.
The winning algorithm, called Keccak, was submitted by a team of four researchers from European semiconductor company STMicroelectronics: Guido Bertoni, Joan Daemen, Gilles Van Assche, and Michaël Peeters (who now works at NXP Semiconductors).
Keccak is the culmination of a contest launched in 2007 by the National Institute of Standards and Technology (NIST). At the time, the IT industry was concerned that the current cryptographic standard, called Secure Hash Algorithm-2 (SHA‑2), was on the verge of being cracked. Its predecessors were falling like flies, and the cryptographic community feared that there wouldn’t be enough time to invent a new algorithm before SHA-2 fell as well.
But SHA-2 proved a lot tougher than expected. “The train wreck that we feared never happened,” says Tim Polk, manager of the cryptographic technology group at NIST. “One of the things we learned [in the course of the competition] is that SHA-2 is a really good algorithm.”
As a result, when Keccak (also known as SHA-3) was crowned in mid-October, the news was met with a big “So what?”
But Keccak is an important advance, argues Polk, because it uses an entirely different technique from previous cryptographic algorithms. SHA-2 and its predecessors are based on block-cipher technology. They use a compression function to process fixed-length blocks of data and then generate a digest. Block-cipher technology is “something we understand very well and have been doing for a long time,” says Polk.
In contrast, Keccak uses a “sponge function,” a technique that didn’t even exist when SHA-2 was invented. Rather than processing data in blocks, Keccak applies a permutation process—a rearranging—absorbing all the data and then squeezing out a fingerprint , says Van Assche, senior security engineer at STMicroelectronics.
Because its design is such a departure from those of previous algorithms, Keccak is not susceptible to the same methods of code cracking, says Polk. That makes it an excellent alternative and ensures that if either SHA-2 or Keccak is broken, the other will likely stand strong to take its place.
In addition, Keccak’s design makes it particularly useful in embedded applications, which require small chips that use very little power. According to Polk, a circuit that executes Keccak would use less real estate on a semiconductor than one that performs SHA‑2, while still providing good performance at low cost.
But no one really knows how, whether, or when the new algorithm could be used. Its very existence might open up some new possibilities, says Polk: “Sometimes you find that when you get algorithms with new properties, then you get new innovative applications that maybe people never pursued before.”
Another benefit of the competition was that it proved the strength of SHA-2. Having the cryptographic community hack away at SHA-2 for five years without finding any weaknesses has increased confidence in it. “In cryptography, it’s much easier to say something is broken than it is to say something’s secure,” Polk says. In fact, NIST is recommending that companies stick with SHA-2 rather than adopt the new algorithm. “If people are already using SHA‑2, we strongly encourage them to stay with it,” says Polk. “There is no reason to abandon SHA-2.”
Bob Cromwell, an engineer who runs his own computer consulting business, agrees. Ensuring that organizations are running even SHA-2 is still an issue. This year, for example, the authors of a piece of malware called Flame were able to forge a code-signing certificate in Windows, because Microsoft had not disabled the use of an old hash algorithm, MD5, in parts of its operating system. The attackers were able to generate a false certificate, which opened the way for them to distribute the malware to Windows computers as if it were an update from Microsoft.
“Our biggest problem is not trying to push the leading edge—it’s pulling the lagging tail forward,” says Cromwell.