Full disclosure: Burt Kaliski and I share an employer.
Peter Trei
-Original Message-
From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] Behalf
Of David Farber
Sent: Wednesday, February 23, 2005 7:48 PM
To: Ip
Subject: [IP] One cryptographer's perspective on the SHA-1 result
From: "Kaliski, Burt" <[EMAIL PROTECTED]>
Subject: One cryptographer's perspective on the SHA-1 result
To: <[EMAIL PROTECTED]>
Date: Wed, 23 Feb 2005 19:43:43 -0500
Hi Dave --
As you might expect, the recent breakthrough on SHA-1 hash was a topic of
widespread discussion at the annual RSA Conference last week in San
Francisco. Commercial cryptography is one of few fields in IT which has
totally absorbed the "open review" process. We know from experience that an
ongoing and aggressive analysis of our current technology, searching out
potential weaknesses, is a critical part of the process by which we
strengthen it for the future.
RSA Laboratories has just posted a brief note on the recent SHA-1 result, to
supplement our earlier notes about MD5 and other hashes, at
http://www.rsasecurity.com/rsalabs.
In my opinion, the latest result on SHA-1 -- once confirmed -- will be one
of the most significant results in cryptanalysis in the last decade. Hard
work indeed brings a profit, as the proverb says, and the perseverance of
Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu appears to have paid off with
this unexpected special attack on SHA-1 that can find collisions in less
than the promised 2^80 threshold.
It is a delight to congratulate the Shandong University team on their
achievement, and especially Dr. Yiqun Lisa Yin, for many years my colleague
at RSA Laboratories, and one of the co-inventors of RSA Security's RC6 block
cipher.
This attack seems to have uncovered an unexpected weakness in one of the
essential properties of SHA-1, a one-way hash function with a 160-bit
output. Essentially, this new research suggests that it is considerably
less difficult than expected to create two somewhat different data files
that can be reduced and compressed to an identical hash value.
Cryptographers call these "collisions" in hash outputs.
A hash function takes a variable-length digital input and coverts it into a
fixed-length pseudo-random hash value that can serve as a useful
"fingerprint" for the input file. A one-way hash function like SHA-1 is
easy to compute in one direction, but it's very difficult to reconstitute
the initial file from the hash value. A good hash function is also expected
to be "collision-free." That is, it should be hard to generate two input
files which, put through the hash function, generate the same hash value.
(Hash functions collisions must exist, of course, since the hash inputs can
be longer than the outputs -- but the design goal is to make them hard to
find in practice.)
These attributes have made the one-way hash one of the most useful
"primitives" in modern cryptography. Hash functions are, for example,
essential in deriving message authentication codes (MACs) and "message
digests," the small file that is actually cryptographically "signed" to
create a "digital signature" for larger files, in a typical public key
crypto application.
MIT Professor Ron Rivest, one of the founders of RSA Security, created three
one-way hashes that were widely used by cryptographers over the past 20
years (MD2, MD4, and MD5), but each of those was eventually deprecated as
subtle weaknesses were discovered that suggested that the internal design
was less robust than desired against potential future attacks.
Any successful attack on SHA-1 based on the new result would still involve a
huge amount of computer processing, so this latest research is unlikely (as
many have said) to have any significant impact on past or current
applications. It is, however, a wake-up call for cryptographers and the
industry leaders concerned with the long-term vitality of our technology.
The SHA (aka SHA-0) hash function was developed for the US government in
1995 for use within the Digital Signature Standard. Its design was based on
MD4. SHA was upgraded to SHA-1 early in its life cycle, apparently to
address undisclosed weaknesses discovered by the NSA, and today SHA-1 is the
industry standard. It is widely used and has been trusted by both
developers and applied crypto engineers, although routine efforts to enhance
SHA-1 with longer output values have led to the quiet development of
SHA-256, SHA-385, and SHA-512 as design options for long-term applications.
Although RSA Security, and most standards organizations, have recommended
the use of SHA-1 for several years, Rivest's MD5 is still widely used in
many applications despite research in the 1990s that discovered "pseudo"
collisions within the internal operations of MD5. Then, last summer, there
were additional results on MD5 that led
