Attacks on Cryptographic Hashes in Internet Protocols
RFC 4270

• Status
• IESG evaluation record
• IESG writeups
• Email expansions
• History

• Versions
• 04

Network Working Group                                         P. Hoffman
Request for Comments: 4270                                VPN Consortium
Category: Informational                                      B. Schneier
                                           Counterpane Internet Security
                                                           November 2005

         Attacks on Cryptographic Hashes in Internet Protocols

Status of This Memo

   This memo provides information for the Internet community.  It does
   not specify an Internet standard of any kind.  Distribution of this
   memo is unlimited.

Copyright Notice

   Copyright (C) The Internet Society (2005).

Abstract

   Recent announcements of better-than-expected collision attacks in
   popular hash algorithms have caused some people to question whether
   common Internet protocols need to be changed, and if so, how.  This
   document summarizes the use of hashes in many protocols, discusses
   how the collision attacks affect and do not affect the protocols,
   shows how to thwart known attacks on digital certificates, and
   discusses future directions for protocol designers.

1.  Introduction

   In summer 2004, a team of researchers showed concrete evidence that
   the MD5 hash algorithm was susceptible to collision attacks
   [MD5-attack].  In early 2005, the same team demonstrated a similar
   attack on a variant of the SHA-1 [RFC3174] hash algorithm, with a
   prediction that the normally used SHA-1 would also be susceptible
   with a large amount of work (but at a level below what should be
   required if SHA-1 worked properly) [SHA-1-attack].  Also in early
   2005, researchers showed a specific construction of PKIX certificates
   [RFC3280] that use MD5 for signing [PKIX-MD5-construction], and
   another researcher showed a faster method for finding MD5 collisions
   (eight hours on a 1.6-GHz computer) [MD5-faster].

   Because of these announcements, there has been a great deal of
   discussion by cryptography experts, protocol designers, and other
   concerned people about what, if anything, should be done based on the

Hoffman & Schneier           Informational                      [Page 1]
RFC 4270                   Attacks on Hashes               November 2005

   news.  Unfortunately, some of these discussions have been based on
   erroneous interpretations of both the news and on how hash algorithms
   are used in common Internet protocols.

   Hash algorithms are used by cryptographers in a variety of security
   protocols, for a variety of purposes, at all levels of the Internet
   protocol stack.  They are used because they have two security
   properties: to be one way and collision free.  (There is more about
   these properties in the next section; they're easier to explain in
   terms of breaking them.)  The recent attacks have demonstrated that
   one of those security properties is not true.  While it is certainly
   possible, and at a first glance even probable, that the broken
   security property will not affect the overall security of many
   specific Internet protocols, the conservative security approach is to
   change hash algorithms.  The Internet protocol community needs to
   migrate in an orderly manner away from SHA-1 and MD5 -- especially
   MD5 -- and toward more secure hash algorithms.

   This document summarizes what is currently known about hash
   algorithms and the Internet protocols that use them.  It also gives
   advice on how to avoid the currently known problems with MD5 and
   SHA-1, and what to consider if predicted attacks become real.

   A high-level summary of the current situation is:

   o  Both MD5 and SHA-1 have newly found attacks against them, the
      attacks against MD5 being much more severe than the attacks
      against SHA-1.

   o  The attacks against MD5 are practical on any modern computer.

   o  The attacks against SHA-1 are not feasible with today's computers,
      but will be if the attacks are improved or Moore's Law continues
      to make computing power cheaper.

   o  Many common Internet protocols use hashes in ways that are
      unaffected by these attacks.

   o  Most of the affected protocols use digital signatures.

   o  Better hash algorithms will reduce the susceptibility of these
      attacks to an acceptable level for all users.

2.  Hash Algorithms and Attacks on Them

   A "perfect" hash algorithm has a few basic properties.  The algorithm
   converts a chunk of data (normally, a message) of any size into a
   fixed-size result.  The length of the result is called the "hash

Hoffman & Schneier           Informational                      [Page 2]
RFC 4270                   Attacks on Hashes               November 2005

   length" and is often denoted as "L"; the result of applying the hash
   algorithm on a particular chunk of data is called the "hash value"
   for that data.  Any two different messages of any size should have an