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