Network Working Group                                           A. Kukec
Internet-Draft                                      University of Zagreb
Intended status: Standards Track                             S. Krishnan
Expires: May 7, July 10, 2009                                          Ericsson
                                                                S. Jiang
                                            Huawei Technologies Co., Ltd
                                                        November 3, 2008
                                                         January 6, 2009

                       SeND Hash Threat Analysis

Status of this Memo

   By submitting this Internet-Draft, each author represents that any
   applicable patent or other IPR claims of which he or she

   This Internet-Draft is aware
   have been or will be disclosed, and any of which he or she becomes
   aware will be disclosed, submitted to IETF in accordance full conformance with Section 6 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 7, July 10, 2009.


   This document analysis the use of hashes in SeND, possible threats
   and the impact of recent attacks on hash functions used by SeND.
   Current SeND specification [rfc3971] uses SHA-1 [sha-1] hash
   algorithm and PKIX certificates [rfc3280] 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.

Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
   2.  Terminology  . . . . . . . . . . . . . . . . . . . . . . . . .  4
   3.  Impact of collision attacks on SeND  . . . . . . . . . . . . .  5
     3.1.  Attacks against CGAs in stateless autoconfiguration  . . .  5
     3.2.  Attacks against PKIX certificates in ADD process . . . . .  5
     3.3.  Attacks against Digital Signature in RSA Signature
           option . . . . . . . . . . . . . . . . . . . . . . . . . .  7
     3.4.  Attacks against Key Hash in RSA Signature option . . . . .  7
   4.  Support for the hash agility in SeND . . . . . . . . . . . . .  8
   5.  Security Considerations  . . . . . . . . . . . . . . . . . . .  9
   6.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 10
   7.  References . . . . . . . . . . . . . . . . . . . . . . . . . . 11
     7.1.  Normative References . . . . . . . . . . . . . . . . . . . 11
     7.2.  Informative References . . . . . . . . . . . . . . . . . . 11
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 12
   Intellectual Property and Copyright Statements . . . . . . . . . . 13

1.  Introduction

   SEND [rfc3971] uses the SHA-1 hash algorithm to generate the contents
   of the Key Hash and the Digital Signature fields of the RSA
   signature.  It also uses a hash algorithm (SHA-1,MD5 etc.) in the
   PKIX certificates [rfc3280] used for the router authorization in the
   ADD process.  Recently there have been demonstrated attacks against
   the collision free property of such hash functions [sha1-coll].
   There have also been attacks on the PKIX X.509 certificates that use
   the MD5 hash algorithm [x509-coll] This document analyzes the effects
   of such attacks and other hash attacks on the SEND protocol and
   proposes changes to make it 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

   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 [rfc4270].  Following the approach recommended by
   [rfc4270] and [new-hashes], we will analyze the impact of these
   attacks on SeND case by case in this section.  Through our analysis,
   whether we should support hash agility on SeND is also discussed.

   Up to date, all demonstrated attacks are attacks against a collision-
   free property.  An attacker produces two messages which result in the
   same hash.  Attacks against the one-way property are not yet feasible
   [rfc4270].  There are two attacks against one property.  In the
   first-preimage attack, based on the hash of the real message, an
   attacker finds a false message which results in the same hash.  In
   the second-preimage attack an attacker based on the real message
   itself, finds the false message which results in the same hash.

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 are analyzed in the update of CGA specification [rfc4982],
   which also enables CGAs to support hash agility.  CGAs provide proof-
   of-ownership of the private key corresponding to the public key used
   to generate CGA, and they don't deal with the non-repudiation
   feature, while collision attacks are mainly about affecting non-
   repudiation feature.  CGAs are not suspectable to the collision
   attacks.  In the collision attack, an attacker finds two keys (and
   other CGA parameters) K and K', where CGA = hash(K, ..) = hash(K',
   ..).  Since both keys have to be choosen by an attacker, CGAs are not
   vulnerable to the collision attack.  So, as [rfc4982] points out CGA
   based protocols, including SeND, are not affected by the recent
   collision attacks.  But, CGAs are vulnerable to the preimage attack
   in which an attacker could manage to find the false key K' based on
   node's CGA = hash(K, ..), use key K' to produce the Key Hash field
   and to sign the SeND message afterwards.  In that case, an attacker
   just has to break the CGA, and all other hashes are automatically
   broken, because an attacker can use the false key K' to produce all
   other hashes.  But up to date, the preimage attacks are not yet
   feasible, but might be in the future.

3.2.  Attacks against PKIX certificates in ADD process

   The second use of hash functions is for the router authorization in
   ADD process.  Router sends to host a certification path, which is a
   path between a router and hosts's trust anchor and consists of PKIX
   certificates.  Researchers demonstrated attacks against PKIX
   certificates with MD5 signature, in 2005 [new-hashes] and in 2007

   In 2005 they succeeded to construct the original and the false
   certificate that had the same identity data and digital signature,
   but different public keys [new-hashes].  The problem for the attacker
   is that two certificates with the same identity are not very useful
   in real-world scenarios, while Certification Authority is not allowed
   to provide such two certificates.  Generally, attacks against the
   human-readable fields demand much more effort than the attacks
   against non 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, collision attacks do not
   affect non human-readable parts of the certificate.

   In 2007 were demonstrated certificates which differ in the identity
   data and public key, but still result in the same signature value.
   In such attack, even if an attacker produces such two certificates in
   order to claim that he is someone else, he still needs to predict the
   content of all fields appearing before the public key, eg. serial
   number or validity periods.  Although a relying party cannot verify
   the content of these fields (each certificate by itself is
   unsuspicious), the CA keeps track of those fields and during the
   fraud analysis, the false certificate can be revealed.  Future
   attacks might affect other human-readable fields.  Attacks against
   the validity period field and the IP address extension might have an
   implication to the current SeND protocol.  An attack against the IP
   address extension might enable the router to advertize changed IP
   prefix range, although, not broader than the prefix range of the
   parent certificate in the ADD chain.

   The certificate key in SeND is used both for the CGA generation and
   for message signing.  In the future, CGA might not be used at all in
   SeND, just certificates.  Thus, attacks against certificates are
   potentially very dangerous.  Generally, the most dangerous are
   attacks against middle-certificates in the certification path, where
   for the cost of one false certificate, attacker launches attack on
   multiple routers.  In such scenarios, we will be at least safe from
   attacks against Trust Anchor's certificate because it is not
   exchanged in SeND messages.

3.3.  Attacks against Digital Signature in RSA Signature option

   The digital signature in RSA Signature option is produced as the
   SHA-1 hash of IPv6 addresses, ICMPv6 header, ND message and other
   fields like Message Type Tag and ND options [rfc3971], and is signed
   with the sender's private key, which corresponds to the public key
   from the CGA parameters structure and is authorized usually through
   CGAs.  The possible attack on such explicit digital signature is
   typical non-repudiation attack.  The Digital Signature field is
   vulnerable to the collision attack.  In such collision attack an
   attacker produces two messages M and M', where hash(M) = hash(M'),
   underlays one of the messages to be signed with authorized keys
   (through CGAs), but uses another message afterwards.  However, the
   structure of at least one of two messages in collision attack is
   strictly predefined [rfc4270].  But we have to take into account that
   a variant of SHA-1 was already affected by recent collision attacks
   and we have to prepare for future improved attacks.

3.4.  Attacks against Key Hash in RSA Signature option

   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 of
   SeND message.  Key Hash field is potentially dangerous because it
   contains a non human-readable data.  Since in the collision attack an
   attacker itself chooses both keys, K and K', where hash(K) =
   hash(K'), the Key Hash field is not suspectable to the collision
   attack.  The preimage attack in which an attacker derives the key K'
   based on hash(K) could be theoretically more useful.  But even in
   that case, if an attacker signes the SeND message with the key K', he
   has to break also the CGA, since the Digital Signature is verified
   against the CGA and possibly against a certification path.

4.  Support for the hash agility in SeND

   While all of analyzed hash functions in SeND are theoretically
   affected by recent hash attacks, these attacks indicate the
   possibility of future real-world attacks.  In order to increase the
   future security of SeND, we suggest the support for the hash and
   algorithm agility in SeND.

   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 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 as in CGA.  The
   security of all hashes in SeND depends on CGA, ie. if an attacker
   could break CGA, all other hashes are automatically broken.  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.

   Another solution is to incorporate the Hash algorithm option into
   SeND message, and use different hash algorithms for different hashes,
   or the same algorithm for all hashes.  As already mentioned, from the
   security point of view, it is reasonable to define just one
   algorithm, because additional algorithms does not increase the
   security.  If that algorithm is defined in the Hash algorithm option
   in SeND message, it is vulnerable to the bidding down attack.  On the
   other hand, different algorithms provides additional flexibility, and
   in the future SeND might be used completely without CGAs.

5.  Security Considerations

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

6.  IANA Considerations

   This document defines three new registries that have been created and
   are maintained by IANA.

   o  Hash Algorithm for Key Hash field (HA-KH).  The values in this
      name space are 5-bit unsigned integers.

   o  Hash Algorithm for Digital Signature field (HA-DS).  The values in
      this name space are 5-bit unsigned integers.

   o  Signature Algorithm (SA).  The values only analyzes the possible hash threats in this name space are 5-bit
      unsigned integers.

   Initial values for these registries are given below.  Future
   assignments are to be made through Standards Action [rfc2434].
   Assignments for each registry consist of a name, a value SEND and a RFC
   number where
   introduces the registry is defined.

   The following initial values are assigned for HA-KH in this document:

             Name        | Value |  RFCs
            SHA-1        |  TBD1 | this document possible mechanisms to support hash agility.  The following initial values
   actual SEND extensions are assigned for HA-DS defined in this document:

             Name        | Value |  RFCs
            SHA-1        |  TBD2 | this document

   The following initial values other documents.  There are assigned for HA-KH in this document:

             Name        | Value |  RFCs
       RSASSA-PKCS1-v1_5 |  TBD3 | no
   IANA actions required by this document

   This document defines one new Neighbor Discovery Protocol [rfc4861]
   options, which must be assigned Option Type values within the option
   numbering space for Neighbor Discovery Protocol messages:

      The Hash algorithm option (TBA1), described in Section 4.1. document.

7.  References

7.1.  Normative References

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

   [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.

7.2.  Informative References

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

   [rfc2434]  Narten, T. and H. Alvestrand, "Guidelines for Writing an
              IANA Considerations Section in RFCs", RFC 2434,
              April 1998.

   [rfc3280]  Housley, R., "Internet X.509 Public Key Infrastructure
              Certificate and Certificate Revocation List (CRL)
              Profile", RFC rfc3280, April 2002.

   [rfc4861]  Narten, T., Nordmark, E., Simpson, W., and H. Solliman,
              "Neighbor Discovery for IP Version 6 (IPv6)", RFC 4861,
              April 1998.

   [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.

              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


Full Copyright Statement

   Copyright (C) The Notice

   Copyright (c) 2009 IETF Trust (2008).

   This document is subject to the rights, licenses and restrictions
   contained in BCP 78, and except the persons identified as set forth therein, the authors
   retain all their rights.

   document and the information contained herein are provided on an

Intellectual Property

   The IETF takes no position regarding the validity or scope of any
   Intellectual Property Rights or other authors.  All rights that might be claimed to
   pertain to the implementation or use of the technology described in
   this reserved.

   This document or the extent to which any license under such rights
   might or might not be available; nor does it represent that it has
   made any independent effort to identify any such rights.  Information
   on the procedures with respect is subject to rights in RFC documents can be
   found in BCP 78 and BCP 79.

   Copies of IPR disclosures made to the IETF Secretariat and any
   assurances of licenses Trust's Legal
   Provisions Relating to be made available, or the result of an
   attempt made to obtain a general license or permission for IETF Documents
   ( in effect on the use date of
   such proprietary rights by implementers or users
   publication of this
   specification can be obtained from the IETF on-line IPR repository at

   The IETF invites any interested party to bring to its attention any
   copyrights, patents or patent applications, or other proprietary document.  Please review these documents
   carefully, as they describe your rights that may cover technology that may be required and restrictions with respect
   to implement this standard.  Please address the information to the IETF at document.