Standard that is key to virtually all secure online communications is broken.

Andrew Brandt, PC World

Thursday, February 17, 2005

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 has come out during one of the largest conferences about computer security and encryption, the annual RSA Data Security Conference, which runs through Friday in San Francisco.

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