FW: [IP] One cryptographer's perspective on the SHA-1 result

[Trei, Peter]

Full disclosure: Burt Kaliski and I share an employer.

Peter Trei

-----Original Message-----
From: owner-ip at v2.listbox.com [mailto:owner-ip at v2.listbox.com]On 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" <BKaliski at rsasecurity.com>
Subject: One cryptographer's perspective on the SHA-1 result
To: <dave at farber.net>
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 many cryptographers to urge the
abandonment of MD5 for SHA-1, which had withstood a great deal of analysis
and was widely believed to be "still secure."

It is easy to understand, with this history, why the recent SHA-1 result
would be so unnerving.

Cryptographers are notoriously conservative in their definition of security,
and the "break" in SHA-1 is accordingly much more a crisis for the designers
of these algorithms than for their users.

Thankfully, the practical impact on most applications today is still
limited.  For instance, as others have already observed, existing signatures
are not at risk due to a collision attack.  Nor are the many applications
that rely only on the one-way property or the pseudo-randomness of SHA-1.

New signatures, moreover, are only at risk if a signer is willing to sign a
message essentially as directed by the attacker.  And for such situations,
the cautious signer can just incorporate a little random data at the
beginning of the message to thwart the attack.

But for the research community, the situation is quite challenging.

As my colleague, Dag Ströman, pointed out to me, the MD/SHA family (which
also includes the RIPEMD functions) exhibits characteristics of a
"monoculture": the algorithms share many similarities, and attack strategies
on one are somewhat readily (though with impressive effort) adapted to the
others.

Even though no similar flaws have been reported in SHA-256 yet, several
months of analysis will be needed by the cryptographic community before any
reassuring conclusions can be drawn.

Beyond that, it is now clear that the industry needs an open evaluation
process -- like the Advanced Encryption Standard competition -- to establish
a new hash function standard for the long term, or at least an alternative
if SHA-256 and above turn out still to be good enough after review.

At the Cryptographers' Panel at the RSA Conference last week, we played
clips of previous panel statements to see how they'd stood the test of time.
In one of those clips, from 1997, I discussed the dependence of so much
modern cryptography on these hash functions and wondered whether we, as an
industry, had enough of them.  In hindsight, I wish I had been more forceful
in expressing my concern, because last week's result from the Chinese team
suggest that the answer, even then, was probably "no."

Too bad we didn't start working on the new ones back then.

-- Burt

Burt Kaliski
Chief Scientist 
RSA Security Inc.

 

 


----------



-------------------------------------
You are subscribed as ptrei at rsasecurity.com
To manage your subscription, go to
  http://v2.listbox.com/member/?listname=ip

Archives at: http://www.interesting-people.org/archives/interesting-people/

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com