Network Working Group                                           A. Kukec
Internet-Draft                                      University of Zagreb
Intended status: Informational Standards Track                             S. Krishnan
Expires: May 13, August 16, 2010                                        Ericsson
                                                                S. Jiang
                                            Huawei Technologies Co., Ltd
                                                        November 9, 2009

                                                       February 12, 2010

                       SEND Hash Threat Analysis


   This document analysis the use of hashes in SeND, SEND, possible threats
   and the impact of recent attacks on hash functions used by SeND. SEND.
   Current SeND SEND specification [rfc3971] uses the SHA-1 [sha-1] hash
   algorithm and PKIX X.509 certificates [rfc5280] and does not provide
   support for the hash algorithm agility.  The purpose of the document
   is to provide analysis of possible hash threats and to decide how to
   encode the hash agility support in SeND. SEND.

Status of this Memo

   This Internet-Draft is submitted to IETF in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note that
   other groups may also distribute working documents as Internet-

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   The list of current Internet-Drafts can be accessed at

   The list of Internet-Draft Shadow Directories can be accessed at

   This Internet-Draft will expire on May 13, August 16, 2010.

Copyright Notice

   Copyright (c) 2009 2010 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents
   ( in effect on the date of
   publication of this document.  Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to this document.  Code Components extracted from this document must
   include Simplified BSD License text as described in Section 4.e of
   the Trust Legal Provisions and are provided without warranty as
   described in the BSD License.

   This document may contain material from IETF Documents or IETF
   Contributions published or made publicly available before November
   10, 2008.  The person(s) controlling the copyright in some of this
   material may not have granted the IETF Trust the right to allow
   modifications of such material outside the IETF Standards Process.
   Without obtaining an adequate license from the person(s) controlling
   the copyright in such materials, this document may not be modified
   outside the IETF Standards Process, and derivative works of it may
   not be created outside the IETF Standards Process, except to format
   it for publication as an RFC or to translate it into languages other
   than English.

Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3  4
   2.  Terminology  . . . . . . . . . . . . . . . . . . . . . . . . .  5
   3.  Impact of collision attacks on SeND SEND  . . . . . . . . . . . . .  4
     2.1.  6
     3.1.  Attacks against CGAs in stateless autoconfiguration  . . .  4
     2.2.  6
     3.2.  Attacks against PKIX X.509 certificates in ADD process  . . . . .  5
     2.3.  7
     3.3.  Attacks against the Digital Signature in the RSA
           Signature option . . . . . . . . . . . . . . . . . . . . .  6
     2.4.  8
     3.4.  Attacks against the Key Hash field in the RSA
           Signature option . . . . . . . . . . . . . . . . . . . . .  6
   3.  8
   4.  Support for the hash agility in SeND . . . . . . . . . . . . .  7
     3.1.  The negotiation approach for the SEND hash agility . . . .  7
   4.  Security Considerations  . . . . . . . . . . . . . . . . . . .  9
   5.  IANA  Security Considerations  . . . . . . . . . . . . . . . . . . . . . 10
   6.  References . . . . . . . . . . . . . . . . . . . . . . . . . . 11
     6.1.  Normative References . . . . . . . . . . . . . . . . . . . 11
     6.2.  Informative References . . . . . . . . . . . . . . . . . . 11
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 12 13

1.  Introduction

   SEND [rfc3971] uses the hash algorithm in different ways.  It uses
   the SHA-1 hash algorithm to generate Cryptographically Generated
   Addresses (CGA) [rfc3972], the contents of the Key Hash field and the
   Digital Signature field of the RSA Signature option.  It also uses a
   hash algorithm (SHA-1, MD5, etc.) within the digital signature in the PKIX
   X.509 certificates [rfc5280] used for the router authorization in the ADD
   Authorizaton Delegation Discovery (ADD) process.  Recently there have

   There is a great variaty of hash function, but only MD5 and SHA-1 are
   in the wide use.  They both derive from MD4, which has been demonstrated well
   known for its weaknesses.  First hash attacks
   against affected the collision free property
   compression function of such MD5, while the latest hash functions
   [sha1-coll], and attacks against
   SHA-1 delivered colliding hash in significantlly smaller number of
   rounds compared to the PKIX brute force attack number of rounds
   [sha1-coll].  Attacks against X.509 certificates that improved as well,
   and researchers demonstrated colliding certificate with MD5 hash,
   both for the same and different identities [x509-coll].

   Depending on the way of use of hash algorithm, Internet protocol can
   be affected by the MD5 weakness of the underlaying hash algorithm [x509-coll] function.  This
   document analyzes the effects uses of those attacks and other hash algorithms in SEND, possible weakness
   that hash attacks on the SEND
   protocol.  The document proposes changes could introduce to SEND, and possible ways to make it
   SEND resistant to such attacks.

2.  Terminology

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   document are to be interpreted as described in RFC 2119 [rfc2119].

3.  Impact of collision attacks on SeND SEND

   Due to the hash attacks demonstrated on the aforesaid hash algorithms
   a study was performed to assess the threat of these attacks on the
   cryptographic hash usage in internet protocols [rfc4270]. [RFC4270].  This
   document analyzes the hash usage in SEND following the approach recommended by
   approach [rfc4270] and [new-hashes].

   The basic

   Basic cryptographic properties of a hash function are that it is both
   one-way and collision free.  There are two attacks against the
   one-way one-
   way property, the first-preimage attack and the second-preimage
   attack.  In the first-preimage attack, given a knowledge of a
   particular hash value hash(m), h, an attacker finds an input message m' m such
   that hash(m') yields hash(m). hash(m) = h.  The second-preimage attack deals with
   the fixed
   messages.  Given a knowledge of a fixed value m used as the input
   message to the hash function, an attacker finds a different value m'
   that yields hash(m)=hash(m').  Supposing that the hash function
   produces an n-bit long output, since each output is equally likely,
   an attack takes an order of 2^n operations to be successful.  Due to
   the birthday attack, if the hash function is supplied with a random
   input, it returns one of the k equally-likely values, and the number
   of operations can be reduced to the number of 1.2*2^(n/2) operations.  However, attacks
   Attack against the one-way collision-free property are not
   feasible yet [rfc4270]. deals with two fixed
   messages, both produced by an attacker.  Attacker produces two
   different messages, m and m', such that hash(m)=hash(m').  Up to
   date, all demonstrated attacks are attacks against a collision-free property, in which an attacker
   produces two different messages m and m' such that hash(m)=hash(m').
   property.  Attacks against the one-way property are not yet feasible

   The rest strength of Internet protocol does not have to be necessarily
   affected by the document deals with weakness of the collision attacks.

   We underlaying hash function.  The
   appropriate way of use of the hash algorithm will analyze keep the protocol
   immune, no matter of the hash algorithm weaknesses.  Out of many
   possible hash algorithm uses, such as non-repudiable digital
   signatures, certificate digital signatures, message authentication
   with shared secrets, fingerprints, only the first two can introduce
   weaknesses to the Internet protocol [rfc4270].  The rest of the
   section analyzes the impact of hash attacks attacks, mainly collision
   attacks, on SeND case SEND by case in
   this section. the cases of use.  Through our analysis, we also
   discuss whether we should support the hash agility in SeND.

2.1. SEND.

3.1.  Attacks against CGAs in stateless autoconfiguration

   Hash functions are used in the stateless autoconfiguration process
   that is based on CGAs.  Impacts of collision attacks on current uses
   of CGAs and the CGA hash agility are analyzed in the update of the
   CGA specification
   [rfc4982], which also enables CGAs to support the hash agility. [rfc4982].  CGAs provide the proof-of-ownership of
   the private key corresponding to the public key used to generate the
   CGA.  The collision attack against the CGA assume that attacker
   generates two different sets of CGA Parameters that result in the
   same hash value.  Since CGAs do not deal with the non-repudiation
   feature, while collision attacks are mainly about
   affecting the non-repudiation feature, i.e. in the collision attack
   against the CGA and both of the CGA Parameters sets are choosen chosen by an the attacker, which this attack is not
   useful in the any real-world scenarios.
   Therefore, as [rfc4982] points out CGA based scenario.  CGA-based protocols, including
   SEND, are not affected by the recent collision attacks.  Regarding
   the pre-image attacks, if  If pre-image
   attacks were feasible, an attacker would manage to find the new colliding CGA
   Parameters based on for the
   associated, victim's CGA, and produce the Key Hash field and
   the Digital Signature field afterwards using the new public key.
   Since the strength of all hashes in SEND depends on the strength of
   the CGA, the pre-image attack is potentially dangerous, but it is not
   yet feasible.


3.2.  Attacks against PKIX X.509 certificates in ADD process

   The second

   Another use of hash functions is for the router authorization in the
   ADD process.  Router sends to a host a certification path, which is a
   path between a router and the hosts's host's trust anchor, consisting of PKIX
   X.509 certificates.  Researchers demonstrated attacks against PKIX X.509
   certificates with MD5 signature, signature in 2005 [new-hashes] and in 2007
   [x509-coll].  In 2005 were researchers constructed the original and the false
   certificate that had colliding certificates
   with the same identity data distinguished name, different public keys, and the same digital
   signature, but
   identical signatures, based on different public keys [new-hashes]. keys.  The problem
   for the attacker is that two certificates with the same identity are
   not actually useful in real-world scenarios, because the
   Certification Authority is can take care of not allowed allowing to provide such
   two certificates.  In addition, attacks against the human-readable
   fields demand much more effort than the attacks against non human-readable human-
   readable fields, such as a public key field.  In case of the identity
   field, an attacker is faced with the problem of the prediction and
   the generation of the false but meaningful identity data, which at
   the end might be revealed by the Certification Authority.  Thus, in
   practice, there is a very low probability that collision attacks do not
   affect non human-readable parts of the certificate.  In 2007 were
   researchers demonstrated colliding certificates which differ in the
   identity data and in the public key, but still result in the same
   signature value.  In such attack, even  Even in this case, the real-world scenarios prevent
   the hash algorithm weaknesses to introduce vulnerabilities of the
   certificate or the protocol.  Even if an attacker produced such two
   colliding certificates in order to claim that he was someone else, he
   still needs to predict the content of all fields appearing before the
   public key, e.g. the serial number and validity periods.  Although a
   relying party cannot verify the content of these fields (each
   certificate by itself is unsuspicious), the Certification Authority
   keeps track of those fields and it can reveal the false certificate
   during the fraud analysis.  Even though the real-world scenarios make
   SEND immune to recent hash attacks introduced through X.509
   certificates, theoretically they are possible, but only in case of
   the human-readable fields.  Regarding X.509 certificates in SeND,
   potentially dangerous SEND,
   biggest concer are attacks against the X.509 certificate
   extensions.  For example, an attack against the RFC3779 IP address extension
   which would enable the bogus router to advertize the changed IP
   prefix range, if the IP prefix range used, although, not broader than
   the prefix range of the parent certificate in the ADD chain.

   The public-private key pair associated  Adding
   some form of randomness to the Router Authorization
   Certificate in the ADD process is used both for the CGA generation
   and for the message signing.  Since in the future CGAs might human-readble data would prevent such
   attacks, which can be used
   only with certificates, attacks against certificates are even more
   dangerous.  Generally, the most dangerous are attacks against middle-
   certificates in the certification path, where for the cost of the one
   false certificate, an attacker launches an attack on multiple
   routers.  Regarding the attacks against certificates in SEND, considered once when the
   only attack that SEND is not suspectable to, is an collision attack against the
   Trust Anchor's certificate because it is not exchanged in SeND
   messages, i.e. it is not the part of the certification path in the
   ADD process.


3.3.  Attacks against the Digital Signature in the RSA Signature option

   The computation of the Digital Signature field is described in
   [rfc3971].  The digital signature in the RSA Signature option  It is produced as the SHA-1 hash over the IPv6 addresses,
   the ICMPv6 header, the ND message and other fields, e.g. the Message
   Type Tag and ND options [rfc3971], that is options, and signed with the sender's private key.  The sender's private
   Private key corresponds to the public key in the CGA parameters
   structure.  It is usually authorized through CGAs.  The Digital
   Signature field is vulnerable to recent collision attacks.  Possible
   attack on such explicit digital signature is a typical non-
   repudiation attack, i.e. the Digital Signature field is vulnerable to
   the collision attack.  An attacker produces two different messages, m
   and m', where hash(m) = hash(m').  He underlays one of the messages
   to be signed with the key authorized through CGAs, but uses another
   message afterwards.  If a SEND attacker would manage to find the
   collision in  However, the message made structure of the ICMPv6 and ND fields mentioned
   in the beginning of the paragraph, he could underlay the false
   message.  The fields that make sense to be changed are ND fields, as
   opposite to the ICMPv6 fields which would be easy to reveal.
   However, as denoted in [rfc4270], the structure of at least one at least one of two
   messages (m, m') in a collision attack is strictly predefined.  The previous
   requirement complicates the makes this collision attack, but we
   have attack to take into account that a variant of SHA-1 was already
   affected by recent be much more then the
   simple collision attacks attack, and we have requires the attacker to prepare for
   future improved attacks.

2.4. know or predict
   the communication context.  Theoretically this attack could harm
   SEND, but in real-world situation is extremely hard to achieve it.

3.4.  Attacks against the Key Hash field in the RSA Signature option

   The Key Hash field in the RSA Signature option is a SHA-1 hash of the
   public key from the CGA Parameters structure in the CGA option.  The pre-image attack against
   the Key Hash field  It
   is potentially dangerous, as in the case of all
   other hashes in SEND, because the Key Hash field contains a non
   human-readable data.  However fingerprint that provides the Key Hash field is integrity protection.
   Fingerprints are generally not suspectable
   to affected by the collision attack, since in attacks
   because they involve random data as one of the inputs, which prevents
   recent collision attacks.  In addition, context of the SEND message
   and the protocol makes this attack an unable to introduce new
   vulnerabilities to SEND.  An attacker
   itself chooses has to produce both keys, k and
   k', where such that hash(k) = hash(k').  The
   reason for the former is that  Since the associated public key is already authorized
   through the use of CGAs, CGA, and possibly possibily through the certification
   path in the ADD process.

   process, this attack is of no use for the attacker.  The pre-image
   attack against the Key Hash field, if it was possible, would affect
   SEND since the Key Hash field contains a non human-readable data.

4.  Support for the hash agility in SeND

   While all of SEND

   Previous section analyzed hash functions that CGAs and fingerprints affected by the
   collision attacks (Key Hash field of the Send message) do not
   introduce new vulnerabilities to SEND.  Digital signatures in SeND are the
   Digital Signature field of the SEND message and X.509 certificate
   theoretically are affected by hash the recent collision attacks, these but the
   SEND context prevents those attacks of almost any use in the real-
   world scenarios.  However, recent attacks indicate the possibility of
   for the future improved real-world attacks.  Researchers advise to
   migrate away from currently used hash algorithms.  In order to
   increase the future security of SeND, SEND, we suggest the following possible approaches can be used. support for the
   hash and algorithm agility in SEND.

   o  The most effective and secure would be to bind the hash function
      option with something that can not be changed at all, like
      [rfc4982] does for CGA - encoding CGA.  It encodes the hash function information
      into addresses.  But, there is no possibilty to do that in SeND.  We could decide to use by default the same hash
      function in SeND SEND as in CGA.  The security of all hashes in SeND SEND
      depends on CGA, ie. i.e. if an attacker could break breaks CGA, all other hashes
      are automatically broken.  The use of the hash algorithm embedded
      in CGA protects from the bidding down attacks.  From the security
      point of view, at the moment, this solution is more reasonable
      then defining different hash algorithm for each hash.  Additionally, if using the hash algorithm from the
      CGA, no bidding down attacks are possible.  On the other hand,  The
      disadvantage of this solution is that it introduces the limition limitation
      for SEND to be used exclusively with CGAs.

   o  Another solution is to incorporate the Hash algorithm option into
      the SeND SEND message.  However, if the algorithm is defined in the
      Hash algorithm option in the SeND message, it  This solution is vulnerable to the bidding down

   o  The third possible solution is to encode the algorithm in the CGA.
      However, this will
      This would reduce the strength of the CGAs CGA and make them it vulnerable
      to brute force attacks.

   o  One of the possible solutions  Possible solution is also the hybrid solution, i.e. to solution which would require
      the hash algorithm to be the same as CGA, if CGA option is
      present, and to use the Hash agility option if the CGA option is
      not present.

3.1.  The negotiation approach for the  In such way, SEND hash agility is not bound exclusively to CGA.

   o  None of the previous solutions supports the negotiation of the
      hash function.  Another possibility  One of possible solutions is to use a the negotiation
      approach for the SEND hash agility such as the one based on the Supported
      Signature Algorithm option described in [sig-agility].  Based on
      the processing rules described in [sig-agility] nodes find the
      intersection between the sender's and the receiver's supported
      signature algorithms set, as well as the preferred signature
   algorithm.  When producing and validating hashes in SEND, nodes must
   observe the following rules:

   o  In the ADD process, if any of the certificates in the
      certification path uses the signature algorithm which is not one
      of the signature algorithms negotiated in the signature agility
      process through the use of the Supported Signature Algorithms
      option, nodes must reject the Router Authorization certificate.

   o  In order to produce the Digital Signature field, nodes must use
      the signature algorithm negotiated in the signature agility
      process through the use of the Supported Signature Algorithms

   o  In order to produce the Key Hash field, nodes must use the hash
      algorithm defined associated to the signature algorithm negotiated
      in the signature agility process through the use of the Supported
      Signature Algorithms option.

4. set.

5.  Security Considerations

   This document analyzes the impact of hash attacks in SeND SEND and offeres
   a higher security level for SeND SEND by providing solution for the hash
   agility support.

   The negotiation approach for the hash agility in SeND SEND based on the
   Supported Signature Algorithms option is vulnerable to bidding-down
   attacks, which is usual in the case of any negotiation approach.
   This issue can be mitigated with the appropriate local policies.

5.  IANA Considerations

   There have been no IANA considerations so far in this document.

6.  References

6.1.  Normative References

              Bellovin, S. and E. Rescorla, "Deploying a New Hash
              Algorithm", November 2005.

              Cheneau, T., Maknavicius, M., Sean, S., and M. Vanderveen,
              "Support for Multiple Signature Algorithms in
              Cryptographically generated Addresses (CGAs)",
              draft-cheneau-cga-pk-agility-00 (work in progress),
              February 2009.

   [rfc3971]  Arkko, J., Kempf, J., Zill, B., and P. Nikander, "SEcure
              Neighbor Discovery (SEND)", RFC 3971, March 2005.

   [rfc4270]  Hoffman, P. and B. Schneier, "Attacks on Cryptographic
              Hashed in Internet Protocols", RFC 4270, November 2005.

   [rfc4982]  Bagnulo, M. and J. Arrko, "Support for Multiple Hash
              Algorithms in Cryptographically Generated Addresses
              (CGAs)", RFC 4982, July 2007.

              Cheneau, T. and M. Maknavicius, "Signature Algorithm
              Agility in the Secure Neighbor Discovery (SEND) Protocol",
              draft-cheneau-send-sig-agility-01 (work in progress),
              May 2010.

6.2.  Informative References

   [rfc2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", RFC 2119, March 1997.

   [rfc5280]  Cooper, D., Santesson, S., Farrell, S., Boeyen, S.,
              Housley, R., and W. Polk, "Internet X.509 Public Key
              Infrastructure Certificate and Certificate Revocation List
              (CRL) Profile", RFC rfc5280, May 2008.

6.2.  Informative References

              Bellovin, S. and E. Rescorla, "Deploying a New Hash
              Algorithm", November 2005.

   [sha-1]    NIST, FIBS PUB 180-1, "Secure Hash Standard", April 1995.

              Wang, X., Yin, L., and H. Yu, "Finding Collisions in the
              Full SHA-1. CRYPTO 2005: 17-36", 2005.

              Cheneau, T., Maknavicius, M., Shen, S., and M. Vanderveen,
              "Signature Algorithm Agility in the Secure Neighbor
              Discovery (SEND) Protocol",
              draft-cheneau-csi-send-sig-agility-00 (work in progress),
              October 2009.

              Stevens, M., Lenstra, A., and B. Weger, "Chosen-Prefix
              Collisions for MD5 and Colliding X.509 Certificates for
              Different Identitites. EUROCRYPT 2007: 1-22", 2005.

Authors' Addresses

   Ana Kukec
   University of Zagreb
   Unska 3


   Suresh Krishnan
   8400 Decarie Blvd.
   Town of Mount Royal, QC


   Sheng Jiang
   Huawei Technologies Co., Ltd
   KuiKe Building, No.9 Xinxi Rd.,
   Shang-Di Information Industry Base, Hai-Dian District, Beijing
   P.R. China