Network Working Group A. Kukec Internet-Draft University of Zagreb Intended status:
Standards TrackInformational S. Krishnan Expires: JulySeptember 10, 2009 Ericsson S. Jiang Huawei Technologies Co., Ltd January 6,March 9, 2009 SeND Hash Threat Analysis draft-ietf-csi-hash-threat-02draft-ietf-csi-hash-threat-03 Status of this Memo This Internet-Draft is submitted to IETF in full conformance with the provisions of BCP 78 and BCP 79. 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. 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- Drafts. 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 http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. This Internet-Draft will expire on JulySeptember 10, 2009. Copyright Notice Copyright (c) 2009 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 (http://trustee.ietf.org/license-info). Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Abstract 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 the SHA-1 [sha-1] hash algorithm and PKIX certificates [rfc3280][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. Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 34 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 45 3. Impact of collision attacks on SeND . . . . . . . . . . . . . 56 3.1. Attacks against CGAs in stateless autoconfiguration . . . 56 3.2. Attacks against PKIX certificates in ADD process . . . . . 57 3.3. Attacks against the Digital Signature in RSAthe SEND Universal Signature option . . . . . . . . . . . . . . . . . . . . . . . . . . 78 3.4. Attacks against the Key Hash in RSAthe SEND Universal Signature option . . . . . 7 4. Support for the hash agility in SeND. . . . . . . . . . . . . 8 5. Security Considerations. . . 8 4. Support for the hash agility in SeND . . . . . . . . . . . . . 9 4.1. The negotiation approach for the SEND hash agility . . . . 9 6. IANA5. Security Considerations . . . . . . . . . . . . . . . . . . . . . 10 7.11 6. References . . . . . . . . . . . . . . . . . . . . . . . . . . 11 7.1.12 6.1. Normative References . . . . . . . . . . . . . . . . . . . 11 7.2.12 6.2. Informative References . . . . . . . . . . . . . . . . . . 1112 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 12 Intellectual Property and Copyright Statements . . . . . . . . . . 1314 1. Introduction SEND [rfc3971] uses the SHA-1 hash algorithm to generate the contents of the Key Hash field and the Digital Signature fieldsfield of the RSA signature.Signature option. It also uses a hash algorithm (SHA-1,MD5(SHA-1, MD5, etc.) in the PKIX certificates [rfc3280][rfc5280] 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[sha1-coll], and attacks on the PKIX X.509 certificates that use the MD5 hash algorithm [x509-coll] This document analyzes the effects of suchthose attacks and other possible hash attacks on the SEND protocol andprotocol. The document proposes changes to make it resistant to such attacks. 2. Terminology The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 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[new-hashes]. The basic cryptographic properties of these attacks on SeND case by case in this section. Through our analysis, whether we should supporta hash agility on SeNDfunction are that it is also discussed. Up to date, all demonstrated attacksboth one-way and collision free. There are two attacks against the one-way property, the first-preimage attack and the second-preimage attack. In the first-preimage attack, given a collision- free property. Anknowledge of a particular value hash(m), an attacker finds an input message m' such that hash(m') yields hash(m). 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 two messages which result inan 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 same hash. Attacksbirthday 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 against the one-way property are not yet feasible [rfc4270]. ThereUp to date, all demonstrated attacks are twoattacks against one property. In the first-preimage attack, based on the hash of the real message, an attacker findsa false message which resultscollision-free property, in the same hash. In the second-preimage attackwhich an attacker based on the real message itself, findsproduces two different messages m and m' such that hash(m)=hash(m'). We will analyze the false message which resultsimpact of hash attacks on SeND case by case in this section. Through our analysis, we also discuss whether we should support the same hash.hash agility in 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 are analyzed in the update of the CGA specification [rfc4982], which also enables CGAs to support the hash agility. CGAs provide proof- of-ownershipthe proof-of-ownership of the private key corresponding to the public key used to generate CGA, and they don'tthe CGA. CGAs do not deal with the non-repudiation feature, while collision attacks are mainly about affecting non- repudiation feature. CGAs are not suspectable tothe collision attacks. Innon-repudiation feature, i.e. in the collision attack, an attacker finds two keys (and other CGA parameters) K and K', whereattack against the CGA = hash(K, ..) = hash(K', ..). Sinceboth keys have to beof the CGA Parameters sets are choosen by an attacker, CGAs arewhich is not vulnerable touseful in the collision attack. So,real-world scenarios. Therefore, as [rfc4982] points out CGA based protocols, including SeND, are not affected by the recent collision attacks. But, CGAs are vulnerable toRegarding the preimage attack in whichpre-image attacks, if pre-image attacks were feasible, an attacker couldwould manage to find the false key K'new CGA Parameters based on node's CGA = hash(K, ..), use key K' tothe associated, victim's CGA, and produce the Key Hash field and to signthe SeND message afterwards. In that case, an attacker just has to breakDigital Signature field afterwards using the CGA, andnew public key. Since the strength of all otherhashes are automatically broken, because an attacker can usein SEND depends on the false key K' to produce all other hashes. But up to date,strength of the preimage attacks areCGA, the pre-image attack is potentially dangerous, but it is not yet feasible, but might be in the future.feasible. 3.2. Attacks against PKIX certificates in ADD process The second 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 trust anchor and consistsanchor, consisting of PKIX certificates. Researchers demonstrated attacks against PKIX certificates with MD5 signature, in 2005 [new-hashes] and in 2007 [x509-coll].[X509-COLL]. In 2005 they succeeded to constructwere constructed the original and the false certificate that had the same identity data and the same digital signature, but different public keys [new-hashes]. The problem for the attacker is that two certificates with the same identity are not veryactually useful in real-world scenarios, whilebecause the Certification Authority is not allowed to provide such two certificates. Generally,In addition, 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 in the public key, but still result in the same signature value. In such attack, even if an attacker producesproduced such two certificates in order to claim that he iswas someone else, he still needs to predict the content of all fields appearing before the public key, eg.e.g. the serial number orand validity periods. Although a relying party cannot verify the content of these fields (each certificate by itself is unsuspicious), the CACertification Authority keeps track of those fields and during the fraud analysis,it can reveal the false certificate can be revealed. Future attacks might affect other human-readable fields. Attacksduring the fraud analysis. Regarding certificates in SeND, potentially dangerous are attacks against the validity period field and the IP address extension might haveX.509 certificate extensions. For example, an implication to the current SeND protocol. Anattack against the IP address extension mightwould enable the router to advertize the changed IP prefix range, although, not broader than the prefix range of the parent certificate in the ADD chain. The certificatepublic-private key pair associated to the Router Authorization Certificate in SeNDthe ADD process is used both for the CGA generation and for the message signing. InSince in the future, CGAfuture CGAs might notbe used at all in SeND, just certificates. Thus,only with certificates, attacks against certificates are potentially veryeven more dangerous. Generally, the most dangerous are attacks against middle-certificatesmiddle- certificates in the certification path, where for the cost of the one false certificate, an attacker launches an attack on multiple routers. In such scenarios, we will be at least safe fromRegarding the attacks against certificates in SEND, the only attack that SEND is not suspectable to, is an attack against the Trust Anchor's certificate because it is not exchanged in SeND messages.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 SEND Universal Signature option The SEND Universal Signature option is an updated version of the RSA Signature option, defined in [sig-agility]. In combination with the public key agility support described in [pk-agility], it allows the node to use the public key signing algorithm different then the RSA- based signing algorithm. No matter of the type of the SEND Universal Signature option, the Digital Signature field is computed in the same way as the Digital Signature field of the RSA Signature option descibed in [rfc3971]. The digital signature in the RSA Signature option is produced as the SHA-1 hash ofover the IPv6 addresses, the ICMPv6 header, the ND message and other fields likefields, e.g. the Message Type Tag and ND options [rfc3971], andthat is signed with the sender's private key, whichkey. The sender's private key corresponds to the public key fromin the CGA parameters structure andstructure. It is authorizedusually authorized through CGAs. The possible attack on such explicit digital signature is a typical non-repudiation attack. Theattack, i.e. the Digital Signature field is vulnerable to the collision attack. In such collision attack anAn attacker produces two messages Mdifferent messages, m and M',m', where hash(M)hash(m) = hash(M'),hash(m'). He underlays one of the messages to be signed with the key authorized keys (through CGAs),through CGAs, but uses another message afterwards. However, as denoted in [rfc4270], the structure of at least one of two messages in a collision attack is strictly predefined [rfc4270]. Butpredefined. The previous requirement complicates the collision attack, 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 the Key Hash in RSAthe SEND Universal Signature option The Key Hash field in the RSA SignatureSEND Universal signature option is a SHA-1 hash of the public key from the CGA parametersParameters structure in the CGA option of SeND message.option. The pre-image attack against the Key Hash field is potentially dangerousdangerous, as in the case of all other hashes in SEND, because itthe Key Hash field 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'),However the Key Hash field is not suspectable to the collision attack. The preimageattack, since in the collision attack in whichan attacker derivesitself chooses both keys, k and k', where hash(k) = hash(k'). The reason for the key K' based on hash(K) could be theoretically more useful. But even informer is that case, if an attacker signes the SeND message withthe associated public key K', he has to break also the CGA, since the Digital Signatureis verified againstalready authorized through the CGAuse of CGAs, and possibly against athe certification path.path in the ADD process. 4. Support for the hash agility in SeND While all of analyzed hash functions in SeND are theoretically affected by recenthash 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. 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 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 fromhash algorithm from the CGA, no bidding down attacks are possible. On the other hand, this solution introduces the limition for SEND to be used exclusively with CGAs. o Another solution is to incorporate the Hash algorithm option into the SeND message. However, if the algorithm is defined in the Hash algorithm option in the SeND message, it is vulnerable to the bidding down attack. o The third possible solution is to encode the algorithm in the CGA. However, this will reduce the strength of the CGAs and make them vulnerable to brute force attacks. o One of the possible solutions is also the hybrid solution, i.e. to 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. 4.1. The negotiation approach for the SEND hash agility None of the previous solutions supports the negotiation of the hash function. Therefore we propose the negotiation approach for the SEND hash agility 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 CGA, no bidding down attacks are possible. Another solution isRouter Authorization certificate. o In order to incorporateproduce the Hash algorithm option into SeND message, andDigital Signature field, nodes MUST use different hash algorithms for different hashes, orthe samesignature algorithm for all hashes. As already mentioned, fromnegotiated in the security pointsignature agility process through the use of view, it is reasonablethe Supported Signature Algorithms option. o In order to define just one algorithm, because additional algorithms does not increaseproduce the security. If thatKey Hash field, nodes MUST use the hash algorithm isdefined inassociated to the Hashsignature algorithm optionnegotiated in SeND message, it is vulnerable tothe bidding down attack. Onsignature agility process through the other hand, different algorithms provides additional flexibility, and inuse of the future SeND might be used completely without CGAs.Supported Signature Algorithms option. 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 only analyzesThe negotiation approach for the possiblehash threatsagility in SEND and introducesSeND based on the possible mechanismsSupported Signature Algorithms option is vulnerable to support hash agility. The actual SEND extensions are definedbidding-down attacks, which is usual in other documents. There are no IANA actions required by this document. 7.the case of any negotiation approach. This issue can be mitigated with the appropriate local policies. 6. References 126.96.36.199. Normative References [new-hashes] Bellovin, S. and E. Rescorla, "Deploying a New Hash Algorithm", November 2005. [pk-agility] 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. 7.2.[sig-agility] Cheneau, T. and M. Maknavicius, "Signature Algorithm Agility in the Secure Neighbor Discovery (SEND) Protocol", draft-cheneau-send-sig-agility-00 (work in progress), February 2009. 6.2. Informative References [rfc2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", RFC 2119, March 1997. [rfc3280][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 rfc3280, April 2002.rfc5280, May 2008. [sha-1] NIST, FIBS PUB 180-1, "Secure Hash Standard", April 1995. [sha1-coll] Wang, X., Yin, L., and H. Yu, "Finding Collisions in the Full SHA-1. CRYPTO 2005: 17-36", 2005. [x509-coll] 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 Zagreb Croatia Email: firstname.lastname@example.org Suresh Krishnan Ericsson 8400 Decarie Blvd. Town of Mount Royal, QC Canada Email: email@example.com Sheng Jiang Huawei Technologies Co., Ltd KuiKe Building, No.9 Xinxi Rd., Shang-Di Information Industry Base, Hai-Dian District, Beijing P.R. China Email: firstname.lastname@example.org Full Copyright Statement Copyright Notice Copyright (c) 2009 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 (http://trustee.ietf.org/license-info) 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.