News that a nine-year-old encryption method -- one that underlies the protection of virtually all secure online communications -- appears to have been cracked by a team of three Chinese researchers has spurred encryption experts around the world to issue a call to action.
The standard, known as SHA-1, "is used in pretty much every cryptographic protocol out there," says encryption expert Bruce Schneier. "(SHA-1 is) used in SSH, in SSL, in S/MIME, in PGP. It's used in IPSec. VPNs use it. Everybody uses it."
The scope of the problem is enormous. Virtually all application and server software that incorporates SHA-1 into its functions -- including Web browsers, e-mail clients, instant messaging programs, secure shell clients, and file- and disk-encryption software -- will need to be replaced or upgraded.
"We all sort of knew this could happen, but we didn't expect it this bad, this soon," says Schneier, who also blogs about security topics.
It's academic, so far
"This is a critical break in SHA that is just at the edge of feasibility," Schneier says. But even though SHA-1 has been broken by academics, that doesn't mean the government or criminals will be able to spy on your encrypted communications immediately.
For regular computer users, the breaking of SHA-1 has no sudden repercussions. Secure online communications have not been thrown wide open. A tougher standard that hasn't been broken, called SHA-256, already exists. Encryption experts are urging software companies to integrate SHA-256 into applications that currently use SHA-1.
Coincidentally, the news about SHA-1 came out during one of the largest conferences about computer security and encryption, the annual RSA Data Security Conference.
Not a 'run for the exits' situation
"We've all been discussing what we're going to do for some time," says Jon D. Callas, chief technology officer for PGP, a company that makes encryption products for individual and business computer users, as well as high-end mail encryption gateways for enterprises. "The next release of PGP will incorporate SHA-256 into the software," Callas says. "PGP 9 will likely go into beta in a few weeks."
"At PGP, we've been working on this for a long time, but we're a little quicker about this kind of stuff than most people," Callas adds.
"This is not a 'Run for the exits, the place is on fire' kind of situation," Callas says. "It's 'The fire alarm is on, this is not a drill, please move to the exits.'"
Hashing takes a beating
Schneier posted a brief item about SHA-1 on his blog last Tuesday, crediting three Shandong University researchers -- Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu -- with the achievement.
"They are respected cryptographers, their work is phenomenally good. This is not a fly-by-night group, and there's no reason not to believe this (is real)," he says.
He describes SHA-1, invented by the National Security Agency in 1995, as "the most common cryptographic primitive" on the Internet. (Cryptographic primitive is an academic term describing a mathematical formula that cryptographers can use to scramble and unscramble codes.)
In the arcane language of encryption, SHA-1 is known as a one-way hash function. Cryptographers use these tools to calculate a hash value for a secret message. Hash values help guarantee that a secret message has not been tampered with in transit, and they can't be used by spies to reconstruct the message.
"We know less about hashing than anything else in crypto -- and we thought we knew more," Callas says. "It will probably take us another two to five years until we really understand hashing algorithms, and in the meantime there will be more dramatic things that will happen."
Immense computing power used
Breaking encryption takes immense amounts of computing power. The researchers who cracked SHA-1 didn't have banks of supercomputers at their disposal, so instead they used a distributed computing program -- Callas describes it as "basically something like SETI@Home" -- to harness the idle computing power of thousands of PCs around the world to complete the task.
"The best attack anyone has ever done (on current encryption) was the distributed attack on MD5-RC64, which took 300,000 computers -- and it took them five years," Callas says. "(Breaking SHA-1) is 16 times harder than that; it'd take those same 300,000 computers roughly 74 years."
But faster home computers, and the power of distributed computing (which shares portions of a monumental task among many thousands of users), seems to have shortened the time scale. "Cryptographic attacks always get better, sometimes by a factor of two or four, but they never get worse," Schneier says.
In an essay he wrote for last August's Computerworld magazine, Schneier hinted that researchers at the time were perhaps close to breaking SHA-1. The essay urged cryptographers to start work on the next generation of one-way hash functions, before the current generation became so broken as to be unusable.