“LAST year, I walked away saying thank God she didn’t get a break in SHA-1,” says William Burr. “Well, 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’s 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. “This is a bit like when you see the first water seeping through the dyke,” Burr says. “Will it continue to seep slowly or is it the beginning of the crumbling of the whole thing?”
SHA is short for “secure hash algorithm”. Hash algorithms are mathematical procedures that have a seemingly magical, and extremely useful, ability to “digest” 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.
Advertisement
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. “When I design a protocol, I use them everywhere,” says Bruce Schneier, a cryptographer and security specialist based in Mountain View, California. “They 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 “computationally 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 “collide”. But the hash algorithm makes it practically impossible, given today’s computing power, for anyone to find a collision – and thus render a document or signature vulnerable to tampering – by random guessing or “brute force”. For MD5, it would take an average of 264 guesses to find a collision.
SHA-1 hashes are longer – 160 bits – and it would take an average of 280 guesses to find two documents that share an SHA-1 hash. That would take millions of years to compute on today’s most powerful computers. Or that’s 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 “message” 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 “feel” for the kind of bit strings that will result in a collision. It’s not easy, and seems to require a special kind of mind, but Wang, for one, is able to do it.
“She 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’s Watson Research Center in Yorktown Heights, New York, thinks Wang’s abilities are a warning to the cryptographic community: a hash function may be hard work, but some people are prepared to work hard. “It’s like a giant puzzle,” Jutla says. “Most 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’s predecessor) in 1997 with 258 computations instead of the prescribed 280, 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 237 inputs, but that she had actually done it on the computer in her lab, everyone in the room was astonished. “It was a devastating result and quite moving,” said Stuart Haber of Hewlett-Packard Labs in Princeton, New Jersey, who chaired the session. “There 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 “message 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’t 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 269 tries, instead of the expected 280 (鶹ý, 26 February, p 4).
This time, the cryptographers were crushed. “This is a crisis for the research community,” Burt Kaliski, head of RSA Laboratories in Bedford, Massachusetts, told 鶹ý at the time of the announcement. Wang, however, is more circumspect. “I think it’s good news,” she says. “People can understand whether a hash function is secure and how to design secure hash functions.”
It isn’t an immediate threat – no one has actually computed a collision for SHA-1 yet. Wang’s 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. “When a cryptographer says something is broken, it doesn’t mean you can do it,” Burr says. “It 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. “It’s not Armageddon,” he says. “But it’s a good kick in the pants.”
However, since February’s 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 263, which is a significant figure: harness an array of today’s computers to implement this algorithm and you could find a pair of colliding messages in about one month. “It is a lot of work, but it’s 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’s break and what to do about it. Many of those present were champing at the bit to confirm that Wang’s 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’s not such a great idea. “I don’t like to encourage this,” he says. He is hesitant because once it has been done and published, anyone can exploit Wang’s 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 “bot nets”, it’s an unlikely scenario. If the researchers implement Wang’s protocol and publish the result, it would help the hackers enormously. “If 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’s 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 “John owes Paul $100” could be added to a forged contract reading “John owes Paul $50,000”. It’s likely that the same could happen with SHA-1, whatever measures were put in place to keep its vulnerabilities hidden.
“The digital signature on a contract stating ‘John owes Paul $100’ could be added to one reading ‘John owes Paul $50,000’”
But forged digital signatures are not the worst-case scenario: that accolade is reserved for the development of a “pre-image” collision, where it becomes possible to reverse the hash and recreate the initial document. “Then it’s time to panic,” says Bellovin.
That’s because, if hashes are reversible, many “secure” applications, such as secure internet sites (a web address beginning with “https” rather than “http”) 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. “One-wayness is critical,” says Schneier.
So far, no one has found a way to exploit Wang’s 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’t think we should wait to find out. “I 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’s 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’s break ineffective by introducing a step before hashing.
But some think prolonging the life of SHA-1 is foolish and dangerous. “SHA-1 is broken. It’s 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’s 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. “All of our designs are similar,” says Schneier. “In 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.
“The rapid succession of breaks in hash algorithms means there could be something wrong with the whole lot of them”
Whatever the eventual solution, it’s 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’s almost inevitable. “Attacks always get better,” he says. “They never get worse.”
