Network Working Group                                           A. Kukec
Internet-Draft                                      University of Zagreb
Intended status: Standards Track Informational                               S. Krishnan
Expires: September 7, 2010 January 12, 2011                                       Ericsson
                                                                S. Jiang
                                            Huawei Technologies Co., Ltd
                                                           March 6,
                                                           July 11, 2010

                       SEND Hash Threat Analysis


   This document analysis analyzes the use of hashes in SEND, Secure Neighbor Discovery
   (SEND), the possible threats to these hashes and the impact of recent
   attacks on hash functions used by SEND.
   Current  The SEND specification [rfc3971]
   [RFC3971] currently uses the SHA-1 [sha-1] [SHA1] hash algorithm and X.509 PKIX
   certificates [rfc5280] [RFC5280] and does not provide support for the hash
   algorithm agility.  The purpose of the  This document
   is to provide provides an analysis of possible hash
   threats and to decide how to
   encode the hash agility support algorithms used in 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. (IETF).  Note that other groups may also distribute
   working documents as Internet-Drafts.  The list of current Internet-
   Drafts is at

   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 September 7, 2010. January 12, 2011.

Copyright Notice

   Copyright (c) 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 Simplified 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
   2.  Terminology . . . . . . . . . . . . . . . . . . . . . . . . .  4 . 3
   3.  Impact of collision attacks on SEND . . . . . . . . . . . . .  5 . 3
     3.1.  Attacks against CGAs used in stateless autoconfiguration SEND . . .  5 . . . . . . . . . . 3
     3.2.  Attacks against X.509 PKIX certificates in ADD Authorization
           Delegation Discovery process  . . . .  6 . . . . . . . . . . . 4
     3.3.  Attacks against the Digital Signature in the SEND RSA
           Signature option  . . . . . . . . . . . . . . . . . . . . .  7 4
     3.4.  Attacks against the Key Hash field in of the SEND RSA
           Signature option  . . . . . . . . . . . . . . . . . . . . .  7 4
   4.  Support for the hash agility in SEND  Conclusion  . . . . . . . . . . . . . . . . .  8 . . . . . . . . . 4
   5.  IANA  Security Considerations . . . . . . . . . . . . . . . . . . . . . 10 5
   6.  Security Considerations  Acknowledgements  . . . . . . . . . . . . . . . . . . . . 11 . . . 5
   7.  References  . . . . . . . . . . . . . . . . . . . . . . . . . . 12 5
     7.1.  Normative References  . . . . . . . . . . . . . . . . . . . 12 5
     7.2.  Informative References  . . . . . . . . . . . . . . . . . . 12 5
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . . . 14 6

1.  Introduction

   SEND [rfc3971] [RFC3971] 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 indirectly uses a hash algorithm (SHA-1,
   MD5, etc.)
   within the digital signature in X.509 the PKIX certificates [rfc5280] [RFC5280] used for the router
   authorization in the Authorizaton Authorization Delegation Discovery (ADD) Discovery(ADD) process.

   There is a great variaty
   Recently there have been demonstrated attacks against the collision
   free property of such hash functions, but only MD5 functions [SHA1-COLL], and SHA-1
   are in attacks on the wide use, which is also
   PKIX X.509 certificates that use the case for SEND.  They both
   derive from MD4, which has been well known for its weaknesses.  First MD5 hash attacks affected algorithm [X509-COLL].
   The document analyzes the compression function impacts of MD5, while the
   latest hash these attacks against SHA variants delivered colliding hashes
   in significantlly smaller number of rounds compared to the brute
   force attack number of rounds [sha1-coll].  Apart from the
   aforementioned hash attacks, researchers also demonstrated attacks
   against X.509 certificates.  They demonstrated colliding X.509
   certificates with MD5 hash, both with the same and different
   distinguished names [new-hashes] [x509-coll].

   Depending on the way how the Internet protocol uses the hash
   algorithm, Internet protocol can be affected by the weakness of the
   underlaying hash function.  This document analyzes uses of hash
   algorithms in SEND, possible vulnerabilities that hash attacks could
   introduce to SEND, SEND and offers suggestions on how it
   recommends mechanisms to make 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]. [RFC2119].

3.  Impact of collision attacks on SEND

   Due to the hash attacks demonstrated on the aforesaid hash algorithms

   [RFC4270] performed a study was performed to assess the threat of these theaforementioned
   attacks on the use of cryptographic hash usage hashes in Internet protocols. protocols .
   This document analyzes the hash usage in SEND following the recommended approach
   [rfc4270] [new-hashes].

   Basic cryptographic properties
   recommended by [RFC4270] and [NEW-HASHES].

   The following sections discuss the various aspects of a hash function are that it is both
   one-way usage in
   SEND and collision free.  There determine whether they are two attacks against affected by the one-
   way property, attacks on the first-preimage attack
   underlying hash functions.

3.1.  Attacks against CGAs used in SEND

   Cryptographically Generated Addresses (CGAs) are defined in [RFC3972]
   and the second-preimage
   attack.  In the first-preimage attack, given a knowledge of are used to securely associate a
   particular hash value h, an attacker finds an input message m such
   that hash(m) = h.  The second-preimage attack deals cryptographic public key with fixed
   messages.  Given a knowledge an
   IPv6 address in the SEND protocol.  Impacts of a fixed value m used collision attacks on
   current uses of CGAs are analyzed in [RFC4982].  The basic idea
   behind collision attacks, as described in Section 4 of [RFC4270], is
   on the input
   message to the non-repudiation feature of hash algorithms.  Since CGAs do not
   provide non-repudiation features anyway.  Therefore, as [RFC4982]
   points out CGA based protocols, including SEND, are not affected by
   collision attacks on hash function, functions.  If pre-image attacks were to
   become feasible, an attacker finds a different value m'
   that yields hash(m)=hash(m').  Supposing can find new CGA Parameters that can
   generate 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 same CGA as the hash function is supplied with a random
   input, it returns one victim.  This class of attacks could be
   potentially dangerous since the k equally-likely values, and the number security of operations can be reduced to SEND messages relies on
   the number strength of 1.2*2^(n/2) operations.
   Attack against the collision-free property deals with two fixed
   messages, both produced by an attacker.  What happens is that the
   attacker produces two different messages, m and m', such CGA.

3.2.  Attacks against PKIX certificates in Authorization Delegation
      Discovery process

   To protect Router Discovery, SEND requires that
   hash(m)=hash(m').  Up routers be authorized
   to date, all demonstrated attacks act as routers.  Routers are attacks
   against authorized by provisioning them with
   certificates from a collision-free property.  Attacks against trust anchor, and the one-way
   property hosts are not yet feasible [rfc4270].

   The strength of Internet protocol does not have to be necessarily
   affected by the weakness of the underlaying hash function.  The
   appropriate way of use of the hash algorithm will 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 configured with shared secrets, fingerprints, only
   the first two can introduce
   weaknesses trust anchor(s) used to the Internet protocol [rfc4270].  The rest of the
   section analyzes the impact of hash attacks, mainly collision
   attacks, on SEND by the cases of use.  Through our analysis, we also
   discuss whether we should support the hash agility in SEND.

3.1.  Attacks authorize routers.  Researchers
   demonstrated attacks against CGAs in stateless autoconfiguration

   Hash functions are used PKIX certificates with MD5 signatures in the stateless autoconfiguration process
   which is based on CGAs.  Impacts of collision attacks on current uses
   of CGAs
   2005 [NEW-HASHES] and the CGA hash agility are analyzed in the update of the
   CGA specification [rfc4982].  CGAs provide the proof-of-ownership 2007 [X509-COLL].  An attacker can take
   advantage of
   the sender's private key corresponding these vulnerabilities to obtain an certificate with a
   different identity and use the public key used certificate to
   generate the CGA.  Simply stated, their main purpose is impersonate a router.
   For this attack to assure
   that succeed the sender of the message is the same as attacker needs to predict the sender content
   of the
   previous message.  As such, CGAs do not deal with the non-repudiation
   feature.  The collision attack against the CGA assumes that the
   attacker generates two different, colliding sets all fields (some of CGA Parameters
   that result in the same hash value.  Since CGAs do not deal with the
   non-repudiation feature, and both CGA Parameters sets them are chosen by
   the attacker itself, this attack does not introduce any
   vulnerabilities to SEND.  If pre-image attacks were feasible, an
   attacker would find colliding CGA Parameters for the 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 X.509 certificates in ADD process

   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 host's trust anchor, consisting of
   X.509 certificates.  Researchers demonstrated attacks against X.509
   certificates with MD5 signature in 2005 [new-hashes] and in 2007
   [x509-coll].  In 2005 researchers constructed colliding certificates
   with the same distinguished name, different public keys, and
   identical signatures.  Potential problem for the attacker here is
   that two certificates with the same identity can be easily revealed
   by the appropriately configured Certification Authority that does not
   allowe to provide two certificates with the same identities.  Human-
   readable fields significantly complicate the attack.  In case of the
   identity field an attacker is faced with the problem of the
   prediction and the generation of the two different, false but
   meaningful identities, which at the end might be revealed by the
   Certification Authority.  Thus, although theoretically possible,
   real-world circumstances such as the context of the human-readable
   fields, make these attacks with colliding certificates with the same
   identities impossible.  In 2007 researchers demonstrated colliding
   certificates which differ in the identity data and in the public key,
   but still result in the same signature value.  Even in this case, the
   real-world scenarios prevent the hash algorithm weaknesses to
   introduce vulnerabilities to X.509 certificates or to SEND.  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 (some of them are human-readable fields) human-readable) 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 real-world
   scenarios make SEND immune to recent hash attacks introduced through
   X.509 certificates, theoretically they are possible.  Regarding X.509
   certificates in SEND, biggest concer are potential attacks 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.  Adding some form of randomness to the
   such human-readble data such would prevent attacks, which can be
   considered once when the collision attack improve.

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

   The computation of the Digital Signature field is described
   [rfc3971].  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, and signed with the sender's private key.
   Private key corresponds to the public key in the CGA parameters
   structure.  It is usually authorized through CGAs.  The Digital
   Signature field the example of the non-repudiation digital singature,
   and it is vulnerable to recent collision attacks.  Possible attacks
   on such explicit digital signature is a typical non-repudiation
   attack in which the 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.  However, the structure of at least one of two messages
   in a collision attack is strictly predefined.  The previous
   requirement makes this collision attack to be much more then the
   simple collision attack.  It requires the attacker to know or predict
   the communication context.  Theoretically this attack could harm
   SEND, but in real-world situation is 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.  It
   is a fingerprint that provides the integrity protection.
   Fingerprints are generally not affected by the collision 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 unable to introduce new
   vulnerabilities to SEND.  An attacker has to produce both keys, k and
   k', such that hash(k) = hash(k').  Since the key is authorized
   through CGA, and possibily through the certification in the ADD
   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

   Previous section showed that recent hash attacks against CGAs and
   fingerprints (Key Hash field of the Send message) do not introduce
   new vulnerabilities to SEND.  Digital signatures in the Digital
   Signature field of the SEND message and in the X.509 certificate
   theoretically could introduce new vulnerabilities to SEND, but only
   in limited circumstances.  SEND context prevents those attacks of
   almost any use in the real-world scenarios.

   However, recent attacks indicate the possibility for the future
   improved real-world attacks.  Researchers advise to migrate away from
   currently used hash algorithms.  In November 2007, NIST announced an
   opened competition for a new SHA-3 function.  The selection of the
   public key including the serial number and validity periods.  Even
   though a
   winning function will be in 2012.  In order to increase relying party cannot verify the future
   security content of SEND, we suggest these fields, the support for
   CA can identify the hash and algorithm
   agility forged certificate, if necessary.

3.3.  Attacks against the Digital Signature in SEND.

   o the SEND RSA Signature

   The most effective and secure would be to bind digital signature in the hash function RSA Signature option is produced by
   signing, with something that can not be changed at all, like
      [rfc4982] does for CGA.  It encodes the hash function information
      into addresses.  We could decide to use by default sender's private key, the same SHA-1 hash
      function over certain
   fields in SEND the Neighbor Discovery message as described in CGA.  The security Section 5.2
   of all hashes in SEND
      depends on CGA, i.e. if [RFC3971].  It is possible for an attacker breaks CGA, all other hashes
      are automatically broken.  The use of to come up with two
   different Neighbor Discovery messages m and m' that result in the hash algorithm embedded
   same value in CGA protects from the bidding down attacks.  From Digital Signature field.  Since the security
      point structure of view, at
   the moment, this solution is more reasonable
      then defining different hash algorithm for each hash.  The
      disadvantage of this solution Neighbor Discovery messages is that well defined, it introduces the limitation
      for SEND to be used exclusively with CGAs.

   o  Another solution is not possible
   to incorporate use this vulnerability in real world attacks.

3.4.  Attacks against the Key Hash algorithm option into field of the SEND message.  This solution is vulnerable to the bidding down

   o RSA Signature

   The third possible solution is to encode the algorithm SEND RSA signature option described in the CGA. Section 5.2 of [RFC3971]
   defines a Key Hash field.  This would reduce the strength field contains a SHA-1 hash of the CGA and make it vulnerable
   public key that was used to brute force attacks.

   o  Possible solution is also generate the hybrid solution which would require CGA.  To use a collision
   attack on this field, the hash algorithm attacker needs to be come up with another
   public key (k') that produces the same hash as CGA, if CGA option the real key (k).  But
   the real key (k) is
      present, and to use already authorized through a parallel mechanism
   (either CGAs or router certificates).  Hence collision attacks are
   not possible on the Key Hash agility option if field.  Pre-image attacks on the CGA option is
      not present.  In such way, SEND is Key
   Hash field are not bound exclusively to CGA.

   o  None of useful for the previous solutions supports same reason (any other key that
   hashes into the negotiation of same Key Hash value will be detected due to a
   mismatch with the
      hash function.  One of possible solutions is CGA or the negotiation
      approach for router certificate).

4.  Conclusion

   Current attacks on hash functions do not constitute any practical
   threat to the digital signatures used in SEND hash agility based on (both in the Supported
      Signature Algorithm RSA
   signature option described and in [sig-agility].  Based on the processing rules X.509 certificates).  Attacks on CGAs, as
   described in [sig-agility] nodes find the
      intersection between [RFC4982], will compromise the sender's security of SEND and they
   need to be addressed by encoding the receiver's supported
      signature algorithms set. hash algorithm information into
   the CGA as specified in [RFC4982].

5.  IANA Considerations

   There are no IANA actions resulting from this document.

6.  Security Considerations

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

   The negotiation approach for the
   functions hash agility in SEND based attacks have on SEND.  It concludes that the
   Supported Signature Algorithms option is vulnerable only
   practical attack on SEND stems from a successful attack on an
   underlying CGA.  It does not add any new vulnerabilities to bidding-down
   attacks, which is usual in the case SEND.

6.  Acknowledgements

   The authors would like to thank Lars Eggert, Pete McCann, Julien
   Laganier, Jari Arkko, Paul Hoffman, Pasi Eronen, Adrian Farrel, Dan
   Romascanu, Tim Pol, Richard Woundy and Marcelo Bagnulo for reviewing
   earlier versions of any negotiation approach.
   This issue can be mitigated with the appropriate local policies. this document and providing comments to make it

7.  References

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

   [rfc3972]  Aura, T., "Cryptographically Generated Addresses (CGA)",
              RFC 3972, March 2005.


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


   [RFC4982]  Bagnulo, M. and J. Arrko, Arkko, "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.

7.2.  Informative References


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


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

   [RFC3972]  Aura, T., "Cryptographically Generated Addresses (CGA)",
              RFC 3972, March 2005.

   [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, 5280, May 2008.


   [SHA1]     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