杏吧原创

鈥淟AST year, I walked away saying thank God she didn鈥檛 get a break in SHA-1,鈥� says William Burr. 鈥淲ell, now she has.鈥� Burr, a cryptographer at the National Institute of Standards and Technology in Gaithersburg, Maryland, is talking about Xiaoyun Wang, a Chinese cryptographer with a formidable knack for breaking things. Last year Wang, now at Tsinghua University in Beijing, stunned the cryptographic community by breaking a widely used computer security formula called MD5. This year, to Burr鈥檚 dismay, she went further. Much further.

SHA-1 is pretty much the pinnacle of computer security, an algorithm invented and endorsed by the US National Security Agency (NSA) and used in a huge range of security applications. But not for much longer, it seems. 鈥淭his is a bit like when you see the first water seeping through the dyke,鈥� Burr says. 鈥淲ill it continue to seep slowly or is it the beginning of the crumbling of the whole thing?鈥�

SHA is short for 鈥渟ecure hash algorithm鈥�. Hash algorithms are mathematical procedures that have a seemingly magical, and extremely useful, ability to 鈥渄igest鈥� a file of any length, be it a single character or a 20-page document, to produce a fixed-length string of 1s and 0s. They do this by mixing up bits from the document with other bits chosen at random, and then distilling the resulting string of bits down to a particular length (see Diagram). Although the bit string 鈥� the hash 鈥� is meaningless by itself, it provides a short cut for software that verifies whether documents, digital signatures and passwords contain the information they are meant to.

Hash algorithms, also known as hash functions, are used in almost every aspect of digital security. They secure the passwords that give you access to your office network, your email account and secure websites, and enable digital signatures to be used to authenticate messages and their senders; they are used for time-stamping legal, financial and copyright-sensitive documents, for checking that software has not been tampered with, to authenticate secure websites before credit card numbers are typed in and transmitted, and even to generate random numbers for encryption keys. Meanwhile, cryptographers sprinkle them liberally through their protocols to add extra security at every stage. 鈥淲hen I design a protocol, I use them everywhere,鈥� says Bruce Schneier, a cryptographer and security specialist based in Mountain View, California. 鈥淭hey are like good hygiene.鈥�

There are dozens of hash functions to choose from, but the two that were broken by Wang are the most widely used. MD5, which was devised by Ronald Rivest of the Massachusetts Institute of Technology in 1991, is still used in some older applications. SHA-1 was devised by the NSA in 1995 and is used for the newest and most secure applications.

What makes these two so popular? First, they make it extremely difficult 鈥� cryptographers call it 鈥渃omputationally unfeasible鈥� 鈥� to recreate the starting document from its hash, obviously a desirable feature. The second attraction is more subtle: it is computationally unfeasible for a person to find two documents that produce the same hash.

Because of the relatively short length of the hash 鈥� MD5 produces a 128-bit hash, for instance 鈥� many different documents will produce the same hash value. These documents are said to 鈥渃ollide鈥�. But the hash algorithm makes it practically impossible, given today鈥檚 computing power, for anyone to find a collision 鈥� and thus render a document or signature vulnerable to tampering 鈥� by random guessing or 鈥渂rute force鈥�. For MD5, it would take an average of 2⁶⁴ guesses to find a collision.

SHA-1 hashes are longer 鈥� 160 bits 鈥� and it would take an average of 2⁸⁰ guesses to find two documents that share an SHA-1 hash. That would take millions of years to compute on today鈥檚 most powerful computers. Or that鈥檚 what everybody thought: Wang has just rewritten the numbers.

She did it by examining what happens to strings of bits at different stages of the algorithm. As a document or 鈥渕essage鈥� moves through the mathematical procedures, its bit string is rewritten at each step. If you put two messages that initially differ by just a few bits through the system, and watch how they change at each step, it is possible to get a mathematical 鈥渇eel鈥� for the kind of bit strings that will result in a collision. It鈥檚 not easy, and seems to require a special kind of mind, but Wang, for one, is able to do it.

鈥淪he has an incredible ability to look ahead many steps and instinctively know the best route among myriads of possibilities,鈥� says Andrew Chi-chih Yao of Tsinghua University. Charanjit Jutla, a cryptographer at IBM鈥檚 Watson Research Center in Yorktown Heights, New York, thinks Wang鈥檚 abilities are a warning to the cryptographic community: a hash function may be hard work, but some people are prepared to work hard. 鈥淚t鈥檚 like a giant puzzle,鈥� Jutla says. 鈥淢ost people get tired and give up. She did not.鈥�

In fact, Wang found that for some algorithms, just finding the path to a collision is enough to break the algorithm. She broke SHA-0 (SHA-1鈥檚 predecessor) in 1997 with 2⁵⁸ computations instead of the prescribed 2⁸⁰, just by successfully mapping out collision paths.

With MD5, Wang found that the successive rounds of mixing were less regular than for SHA-0, which made finding the paths more difficult. But along with Dengguo Feng at the Chinese Academy of Sciences in Beijing, Xuejia Lai at Shanghai Jiaotong University and Hongbo Yu at Shandong University in Jinan, she still managed it. Crucially, they came up with an algorithm that automatically tweaks or modifies鈥� messages that do not follow the collision path, so that they do. They then use the modified message to generate the collision. When Wang announced at the Crypto 004 conference in Santa Barbara, California, that not only was it possible to unearth a collision after just 2³⁷ inputs, but that she had actually done it on the computer in her lab, everyone in the room was astonished. 鈥淚t was a devastating result and quite moving,鈥� said Stuart Haber of Hewlett-Packard Labs in Princeton, New Jersey, who chaired the session. 鈥淭here was a welcoming sea of applause.鈥�

But bigger news was to come. After hearing about how Wang had broken MD5, another Chinese researcher, Yiqun Lisa Yin, now an independent security consultant based in Greenwich, Connecticut, teamed up with Wang and Yu in a quest to break SHA-1.

This was much harder. The first step in SHA-1 is a 鈥渕essage expansion鈥� that takes the 512-bit message chunks and turns them into 2560-bit chunks. MD5 also contains an expansion, but it is done just by repeating the bits. SHA-1, on the other hand, creates a complex numerical weave involving extra bits generated by adding, subtracting and rotating the initial 512 bits in different ways.

But it wasn鈥檛 quite complex enough to put Wang and her colleagues off. They discovered a mathematical weakness that allowed them to use a computer program to generate pairs of messages that would differ by only 44 of their 2560 bits after undergoing the expansion. Reducing the number of different bits at this stage made it easier to predict what kinds of messages would remain on track for a collision through the whole algorithm. They also applied the message modification technique that was used to break MD5 to increase the probability of finding inputs that would collide. At the annual RSA conference in San Francisco in February, they announced that they had an algorithm that should be able to generate two files with the same SHA-1 hash in just 2⁶⁹ tries, instead of the expected 2⁸⁰ (New 杏吧原创, 26 February, p 4).

This time, the cryptographers were crushed. 鈥淭his is a crisis for the research community,鈥� Burt Kaliski, head of RSA Laboratories in Bedford, Massachusetts, told New 杏吧原创 at the time of the announcement. Wang, however, is more circumspect. 鈥淚 think it鈥檚 good news,鈥� she says. 鈥淧eople can understand whether a hash function is secure and how to design secure hash functions.鈥�

It isn鈥檛 an immediate threat 鈥� no one has actually computed a collision for SHA-1 yet. Wang鈥檚 break consists of an algorithm that could find a collision faster than a brute force attack, but, unlike with MD5, no one has done it. 鈥淲hen a cryptographer says something is broken, it doesn鈥檛 mean you can do it,鈥� Burr says. 鈥淚t just means it could be completed with less work than it ought to require.鈥� Mark Zimmerman, a cryptographer with ICSA Labs in Mechanicsburg, Pennsylvania, puts it a little less delicately. 鈥淚t鈥檚 not Armageddon,鈥� he says. 鈥淏ut it鈥檚 a good kick in the pants.鈥�

However, since February鈥檚 announcement Wang, together with Chi-chih Yao and Frances Yao at City University of Hong Kong, has reduced still further the number of computations required to find a collision. It now stands at 2⁶³, which is a significant figure: harness an array of today鈥檚 computers to implement this algorithm and you could find a pair of colliding messages in about one month. 鈥淚t is a lot of work, but it鈥檚 doable鈥� says Stephen Bellovin of Columbia University in New York.

At the end of October, Burr gathered an army of cryptography researchers in Gaithersburg to discuss the details of Wang鈥檚 break and what to do about it. Many of those present were champing at the bit to confirm that Wang鈥檚 proofs actually work. It would only be possible using distributed computing, where the computing power of huge networks of computers is pooled to perform a task, but Burr thinks it鈥檚 not such a great idea. 鈥淚 don鈥檛 like to encourage this,鈥� he says. He is hesitant because once it has been done and published, anyone can exploit Wang鈥檚 work.

Hackers are unlikely to be able to find the collisions by themselves, he points out: they would have to take over vast numbers of private computers to achieve it. Though that is feasible using a network of computers captured by malicious software, known as 鈥渂ot nets鈥�, it鈥檚 an unlikely scenario. If the researchers implement Wang鈥檚 protocol and publish the result, it would help the hackers enormously. 鈥淚f you create the collisions, you do the heavy lifting for hackers who could not otherwise do it,鈥� Burr says.

People are already starting to exploit collisions that have been generated in MD5 based on Wang鈥檚 attack. Some cryptography researchers have shown how to fake a digital signature on PostScript, PDF and TIFF files, for example. That means the hashed digital signature appended to a contract stating that 鈥淛ohn owes Paul $100鈥� could be added to a forged contract reading 鈥淛ohn owes Paul $50,000鈥�. It鈥檚 likely that the same could happen with SHA-1, whatever measures were put in place to keep its vulnerabilities hidden.

鈥淭he digital signature on a contract stating 鈥楯ohn owes Paul $100鈥� could be added to one reading 鈥楯ohn owes Paul $50,000鈥欌��

But forged digital signatures are not the worst-case scenario: that accolade is reserved for the development of a 鈥減re-image鈥� collision, where it becomes possible to reverse the hash and recreate the initial document. 鈥淭hen it鈥檚 time to panic,鈥� says Bellovin.

That鈥檚 because, if hashes are reversible, many 鈥渟ecure鈥� applications, such as secure internet sites (a web address beginning with 鈥渉ttps鈥� rather than 鈥渉ttp鈥�) would suddenly be extremely insecure: that little closed padlock on your browser would mean nothing. Similarly, passwords and almost every other aspect of digital security would be open to attack. 鈥淥ne-wayness is critical,鈥� says Schneier.

So far, no one has found a way to exploit Wang鈥檚 break in this way. But that may be because cryptographers are only just beginning to explore the consequences of her work. John Kelsey of the National Institute of Standards and Technology doesn鈥檛 think we should wait to find out. 鈥淚 am a little concerned that waiting for someone to publish a pre-image attack might be a little late,鈥� he says.

So where does this leave digital security? One option is simply to tweak SHA-1 to make it a bit safer. Jutla has developed a technique that makes the message expansion part of SHA-1 vastly more complicated, rendering Wang鈥檚 break ineffective. He says it would only make SHA-1 5 per cent slower and has the advantage that it does not require any software or hardware changes. And Yin and Michael Szydlo of RSA Security have a technique called message pre-processing, which would make Wang鈥檚 break ineffective by introducing a step before hashing.

But some think prolonging the life of SHA-1 is foolish and dangerous. 鈥淪HA-1 is broken. It鈥檚 a wounded fish, and the sharks are circling,鈥� says Niels Ferguson, a researcher for Microsoft based in Redmond, Washington.

Ferguson is not alone: the overwhelming consensus at the Gaithersburg workshop was that SHA-1 should be phased out as swiftly as possible. Which raises a particularly difficult question: what do we put in its place?

The obvious choice is SHA-256, an algorithm devised by the NSA specifically for the purpose of taking SHA-1鈥檚 place by 2020, when computing power is expected to be high enough to make a brute force attack on it possible. But some think even this is risky. 鈥淎ll of our designs are similar,鈥� says Schneier. 鈥淚n a way that is good 鈥� we know a lot about it. But it could be bad, it closes us off.鈥� Other cryptographers have suggested that the rapid succession of breaks in hash algorithms recently 鈥� five have been broken in the last 18 months 鈥� means there could be something wrong with the whole lot of them.

鈥淭he rapid succession of breaks in hash algorithms means there could be something wrong with the whole lot of them鈥�

Whatever the eventual solution, it鈥檚 going to be messy. Deploying new hash algorithms will require changes to most of the protocols used in cryptography, digital signatures, e-commerce and virtual private networks. Bellovin, working with Eric Rescorla, a security consultant at Network Resonance in Palo Alto, California, has estimated that it will take up to eight years. Other analysts think that is overly optimistic, and that 20 years might be a more realistic time frame.

Even then, nothing is guaranteed. Another Wang-style surprise could be waiting just around the corner: Schneier thinks it鈥檚 almost inevitable. 鈥淎ttacks always get better,鈥� he says. 鈥淭hey never get worse.鈥�