« DIY Industrial Design: "MyPod" | Main | The patchwork of medical privacy laws »
August 23, 2004
MD5 dead; SHA-1 on life support
Some new attacks against the commonly-used SHA-1 and MD5 secure hash algorithms were announced at a rump session at the Crypto 2004 conference on Tuesday, as well as some less-commonly used secure hash algorithms, including the original SHA (now called SHA-0 to avoid confusion), RIPEMD, HAVAL-128, and MD4. Although these attacks in their present form probably won't enable any system compromises, they have algorithm, protocol, and system designers looking around anxiously for alternatives.
As background, secure hash algorithms are intended to fulfill two requirements: first, that it be computationally infeasible to find two strings that hash to the same hash value ("collision-resistance"), and second, that it be computationally infeasible to find a string that hashes to a given hash value ("preimage-resistance"). Collision-resistance is clearly a stronger requirement, since you can construct a collision once you can find a preimage, but producing collisions does not necessarily imply that you can find a preimage for any given hash. Most systems don't depend strongly on the collision-resistance property. Even without finding a flaw in the algorithm, there's a property known as the birthday paradox that means that finding a collision by brute force takes a lot less work than finding a preimage by brute force.
None of the attacks provide a way to find a preimage for either SHA-1 or MD5, but collisions have been found for the first time in MD5, in a reduced-round version of SHA-1, and in SHA-0. I'm not sure whether collisions had previously been found in the other algorithms, but I don't think so.
It was just becoming possible to find an MD5 collision by brute force, and there was a $10 000 bounty for a successful collision and a project to find a collision and claim the bounty through massively parallel distributed computing. The attacks presented at Crypto 2004 require substantially less computational work than the brute-force attack used in this project.
It was also strongly suspected that there were weaknesses in SHA-0, and some weaker attacks had been found on MD4 and MD5 in the past, making the breakage of those algorithms somewhat unsurprising.
So the only algorithm left standing is SHA-1, and even it looks weak, and there isn't an obvious replacement, although Tiger, longer-hash versions of SHA-1, and AES-CBC have been suggested. Bruce Schneier has called upon the National Institute of Standards and Technology to initiate a search for a replacement algorithm, and Hal Finney thinks that at least the technique Joux used against SHA-0 could be used against a wide variety of secure hash functions.
The first version of the MD5 paper had some minor errors, which have been corrected in the current version (main page, PDF). Markku-Juhani O. Saarinen posted some thoughts and the extracted data files from the paper: 1, 2.
It's interesting that none of the three papers presented at this conference were presented by a citizen of the United States; the MD5 (etc.) paper was published by a Chinese team headed by Xiaoyun Wang, the attack on SHA-0 was presented by French cryptographer Arnold Joux, and the attack on SHA-1 was presented by Israeli cryptographers Biham and Chen.
Cryptographic research in the US has suffered somewhat from the Digital Millennium Copyright Act. For example, Ian Goldberg, a prominent cryptographer who worked at the University of California at Berkeley before the Digital Millennium Copyright Act was enacted, explains why he left the United States in his comments on proposals to tighten Canadian copyright restrictions:
On an individual note, I have personally been involved in the mess that is the US DMCA; some of my own work as a cryptographic researcher, as well as that of my colleagues, has come under question as to whether merely publishing an academic paper is a violation of its anticircumvention provisions. Canada has developed a strong cryptographic industry, partially as a result of a more restrictive US legal regime in this area, and this industry, as well as our high quality of research and education, would be directly threatened if DMCA-like provisions were introduced here. I will not live or work in a country that imposes such restrictions on scientific inquiry. We must not allow academic speech to be chilled, stifled, and censored by any person, group of people, or industry.
Other cryptographers in the US have also scaled back their research to avoid running afoul of the DMCA. Who can say whether one of these attacks would have been discovered by an American cryptographer in the absence of that law? Our national security depends in part on our ability to deploy cryptographic algorithms, such as secure hash functions, before the intelligence services of other nations find a way to crack them. The DMCA may therefore be putting our national security in peril if, for example, Israel's Mossad has progressed farther than Biham and Chen on cracking SHA-1.
(I took some other notes for this post.)
Posted by kragen at August 23, 2004 01:21 PM