Cryptography Reference
In-Depth Information
Staying with SHA: Xiaoyun Wang, Andrew Yao, and Frances Yao presented
an attack against SHA-1 with a 2
63
complexity at CRYPTO '05, which cannot
be tested in practice, of course.
But the sting at CRYPTO '04 was a lecture in the rump session, when the
Chinese Wang and Feng and others presented a full MD5 collision. It consisted
of two 512-bit blocks. Calculating the first block took an IBM P960 supercom-
puter about one hour. The second block was worked at on a regular PC within
from 15 seconds to 5 minutes. (Meanwhile, a notebook computer can do all
this in about 8 hours [Klima] read the article at
algor/SHA/MD5 collisions.pdf
on the Web site.) This earned a standing ovation, an extremely rare thing to
happen at a scientific conference. It gets even better: MD4 collisions were said
to be computable by hand; even HAVAL and RIPE-MD (but not RIPE-MD160)
were said to be breakable, the authors explained, and collisions in SHA-0 could
be found with 2
40
function evaluations — 2000 times faster than Joux's attack.
The eagerly awaited work appeared much later, but no doubts arose about the
correctness of the result. The Python script
algor/SHA/md5coll.py
on our Web
site demonstrates the MD5 collision. Remarkably, the two blocks differ only
in six bytes, and then only in the most significant bit of them. A topic cannot
be completely up to date by nature. Expect to hear of new exciting results by
the time you read this.
Practical Impact of Cryptanalysis
The question is whether these theoretically important successes are significant
for practice. The answer is, unfortunately, yes. But many said 'no' initially
because one cannot yet change checksum-protected documents by calculating
collisions. Some examples show what is possible in spite of this:
In [LenstraMD5], the authors constructed two different valid
X.509 certificates
(we will discuss them later), of which only one was legal. More specifically,
they constructed two official RSA keys with an identical MD5 hash sum. In
practice, a fraud could look like this:
•
Bob creates two different public RSA keys,
A
and
B
, with an identical
MD5 sum. He has
A
signed digitally by VeriSign (see next section).
Since this signs only the MD5 sum, the certificate is automatically valid
for
B
, too.
•
Subsequently, Bob uses the private key of
B
to sign a loan receipt with
Alice. She checks the signature using public key
B
, which she received
