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 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 [EMAIL PROTECTED] 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 [EMAIL PROTECTED]