Supporting Hash Algorithms Agility in Cryptographically Generated Addresses (CGAs)
draft-zhou-6man-cga-hashagil-00

Abstract

This document provides a discussion for solutions supporting hash algorithms agility in Cryptographically Generated Addresses (CGAs) defined in RFC 3972.

Status of This Memo

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

Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at http:/⁠/⁠datatracker.ietf.org/⁠drafts/⁠current/⁠.

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

This Internet-Draft will expire on May 09, 2013.

Copyright Notice

Copyright (c) 2012 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. 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.

Table of Contents

• 1. Introduction
• 1.1. Terminology
• 1.2. CGAs
• 1.3. Security of CGAs
• 1.4. Security Challenges in the Future
• 2. Potential Solutions
• 2.1. Security Discussions
• 2.2. Compatibility Discussions
• 3. Conclusions
• 4. IANA Considerations
• 5. Security Considerations
• 6. References
• 6.1. Normative References
• 6.2. Informative References
• Authors' Addresses

1. Introduction

In this document, a support for multiple hash algorithms without limiting security parameter or downgrading the security level of CGAs is provided. The proposed solution follows the idea of encoding the hash algorithm identity in the CGA addresses to prevent from downgrading attacks, the detailed description of downgrading attack can be found in Section 4.1, RFC 4982.

1.1. 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 [RFC2119].

1.2. CGAs

Cryptographically Generated Addresses (CGAs) [RFC3972] are a kind of stateless addresses, which means the addresses are used when a site is not particularly concerned with the exact addresses hosts use as long as they are unique and properly routable. In contrast with other kinds of stateless addresses, CGAs are mainly used in situations where security is a concern, especially when address ownership and data integrity are required.

CGAs have been used in Secure Neighbor Discovery (SEND)[RFC3971], Mobility in IPv6(MIPv6)[RFC4866], Site Multihoming by IPv6 Intermediation (Shim6)[RFC5533], and securing DHCPv6 [I-D.ietf-dhc-secure-dhcpv6].

CGAs provide address ownership by hashing a public key and other information included in the accompanying CGA parameters to part of the IPv6 address (59 bits), and all messages sent by the host with a CGA go along with a signature calculated using the private key associated with the public key. A receiver firstly recalculates the hash of the CGA parameters and compares the result with the CGA, if the they are equal, the CGA is valid, then the receiver continues to verify the signature.

1.3. Security of CGAs

The security of a CGA implementation relies on the public key cryptographic system adopted and the hash implementation. For the public key cryptographic system, SEND [RFC3971] recommends using only RSA for compatibility between implementations, some other protocols may have their own choices by encoding algorithm identifier in SubjectPublicKeyInfo [RFC3280]. For the hash implementation, it is a bit more complex, because not only hash algorithms are concerned, but also the output length of a hash algorithm is to be considered.

For a perfect hash algorithm, the computation time an attacker takes to find a collision is 2^(L/2) , the time it takes t o find a second-preimage is 2^L, where L is the hash length[RFC4270]. For a practical hash algorithm, the effort an attacker needs could be less. So in addition to choosing a cryptographically strong hash algorithm, it is better to keep the hash length as long as it is originally designed.

But there are some cases that cannot afford to hold the full hash length, CGA being one of them because the number of bits in an IPv6 address is quite limited (128 bits in total including 64 bits for subnet network prefix) and a hash value has to be truncated from 160 bits to 59 bits [RFC3972][RFC4982]. A technique called "hash extension" is proposed to compensate for the security loss induced by hash value truncation [hash-extension], by which both the attacker's and defender's efforts to calculate the same short hash value is increased by the same proportion, but the ratio of them is still bound by 2^L theoretically, where L is the truncated hash value length. In the case of CGA defined in [RFC3972], L equals 59 and the proportion is 2^(16*SEC), where SEC is chosen from 0 to 7. Currently, SEC values between 0 and 2 are sufficient for most IPv6 nodes. As computers become faster, higher SEC values will slowly become useful.

1.4. Security Challenges in the Future

Crypto-analysis of the hash algorithms has made fast progress since 2004, as shown in [RFC4270], which promotes [RFC4982] to enable multiple hash algorithms in CGAs so that once the current hash algorithm does not satisfy future requirements ,e.g., potential future applications of the CGAs may need a more cryptographically secure hash algorithm than SHA-1, the transition to an alternative hash function is as easy as possible.

But where to encode the hash identity ? There are two options considered in [RFC4982] : in a CGA address or in a CGA parameter. For the first option, there are only two places left to insert coding of hash algorithm identity, 3 bits of security parameter SEC and 59 bits of truncated hash value. To occupy SEC bits will make some SEC values unusable, to occupy bits assigned to hash value will further weaken the hash security since hash value length is of essentiality. For the second option, the advantage is that current CGA address allocation is not affected at all, especially truncated hash value is not to be weakened and SEC can choose from the whole range from 0 to 7, but the problem is that this approach is vulnerable to bidding down attacks or downgrading attacks if no other security measures are taken.

[RFC4982] took the first option and occupied the same 3 bits SEC is using for hash algorithm identity, that is

          SEC Value   | Meaning  
   -------------------+-------
          000         | sec=0 and SHA-1
          001         | sec=1 and SHA-1
          010         | sec=2 and SHA-1       

And other SEC values have not yet been defined. As shown in[I-D.zhou-6man-mhash-cga], reusing SEC will limit both the security parameter values and available hash algorithms and ultimately make CGAs less flexible to be used for variant protocols. For example, as mentioned in [RFC3972] it is suggested to start using a low sec value and to replace addresses with higher ones only when denial-of-service attacks based on brute-force search become a significant problem in some situations, and it is suggested to start with higher sec values directly in some situations where CGAs are used as a part of a strong authentication or secrecy mechanism.

[I-D.zhou-6man-mhash-cga] took the first option and occupied 3 bits from the 59 bits assigned to hash value, and proposed to compensate the security loss by increasing hash extension security from 2^(16*SEC) to 2^(16*SEC+3) . The only concern to this approach is that the ratio of attacker's and defender's work to obtain the same CGA address is decreased from 2^59 to 2^56.

Besides crypto-analysis of hash algorithms, the rapid progress in faster and cheaper processors, e.g., GPU, is another challenge to the security of CGAs in the near future. A GPU is effectively a set of 500 or 1000 microprocessors and much faster than a generic processor when doing highly parallel tasks, which means some calculation performed years ago about the safety of hashes may be wrong by 2 or 3 orders of magnitude – in short, hashes should be 10 bits longer than expected a few years ago. And technology is continue changing along the path.

The security challenges show both higher SEC values and stronger hash algorithms are required. For applications flexibility, a wide range of SEC values are preferred. Because stronger hash algorithms are also restricted by the theoretical security bound which is a function of hash length, it is better to have more bits assigned to hash value in CGAs. Thus the requirements for CGAs in the future may be: reasonable variant SEC values, as long as possible bits for hash value in a CGA , reasonable hash algorithm agility, and compatibility with current CGA implementations.

2. Potential Solutions

There could be four types of potential solutions for enhancement of current CGAs, as shown in Figure 2.

       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |        SEC in CGA         |     SEC in CGA Parameter          |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 | HID |[RFC 4982]               I |  II                               |
 | in  |[I-D.zhou-6man-mhash-cga]  | *SEC values =0... 255             |
 | CGA |                           | *hash length = 59~60 bits         |
 |     |                           | *HID max numbers =4~8             |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 | HID |                      III  | IV                                |
 | in  |*SEC values =0...7         |*SEC values =0...255               |
 | CGA |*hash length = 59 bits     |*hash length = 62 bits             |
 |Para-|*HID max numbers =255      |*HID max numbers =255              |
 |meter|                           |                                   |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Type I solutions keep security parameter SEC in CGA address, I,e., bits 0~2 in the interface identifier (the last 64 bits a in IPv6 address), and let HID, encoding of hash algorithms, occupy bits in the interface identifier, either reusing SEC bits as in [RFC4982], or reclaim some bits from the 59 bits assigned to hash value as in [I-D.zhou-6man-mhash-cga], the summary of the SEC values, hash length, and HID max number can be found in the previous section.

Type II solutions reclaim SEC bits and assign some or all of the 3 bits to HID, and put SEC in CGA parameters. Thus the length of hash value in a interface identifier can be 59 bits or 60 bits, the maximum number of supported hash algorithms can be 4 or 8. SEC then could choose values from 0 to 255 providing more flexibility.

Type III solutions keep SEC bits in CGA and put HID in CGA parameters. Thus SEC values are unchanged, the length of hash value in a interface identifier is still 59 bits, the maximum number of supported hash algorithms could be 255 far more than what is actually needed.

Type IV solutions reclaim SEC bits and put both SEC and HID in CGA parameters. Thus the length of hash value in a interface identifier can be 62 bits, the maximum number of supported hash algorithms could be 255 far more than what is actually needed, SEC then could choose values from 0 to 255 providing more flexibility.

2.1. Security Discussions

According to the security requirements for the future CGAs as mentioned in the previous section: reasonable variant SEC values, long bits for hash value in a CGA , reasonable hash algorithm agility, Type II, III, IV are all preferable to type I solutions.

But as shown in Section 4, [RFC4982], all other solutions except type I are vulnerable to downgrading attacks if no other security measures are taken. Specifically, addresses of type II and IV are at risks of attacks of using a less value of the SEC field, addresses of type III and IV are at risks of attacks of using a weaker hash algorithm. It is arguable which kind of attacks are easier to implement. If the goal of CGA is to counter against downgrading attacks using less SEC values, then type III solutions are suitable; if the goal of CGA is to counter against downgrading attacks using weaker hash algorithms, then type II solutions are preferable. Type I solutions are immune to all the above mentioned downgrading attacks.

To defend against downgrading attacks, receivers, who verify the CGA addresses, may adopt their own policy filter and refuse to trust CGA addresses if the hash algorithm is deemed to weak, or the SEC field too short. This offers a protection against attempts to weaken the security of CGA by presenting insufficient values in parameter fields for addresses of type II, III and IV. The senders who want to benefit from CGAs and obtain greater protection SHOULD adopt higher SEC values and stronger hash algorithms, but whether the effort of a sender is effective, is actually dependent on the protection level of policy at the receiver side . If the receiver is so dumb as to accept any malformed address , there is nothing the sender can do.

Type I solutions are attractive in secure against downgrading attacks, because SEC values and hash algorithms are hard coded in the addresses. But type I solutions do not prevent careless senders themselves from choosing low SEC value or weaker hash algorithm. Security policy at the receiver side is still necessary.

Using additional security measures, e.g., security policy, besides the security mechanism in CGAs themselves is reasonable and necessary. CGAs are only utensils that could be used by any internet protocols, it is the responsibility of those protocols that should manage the risk of using CGAs improperly. And those protocols have variant security requirements, it is impossible for the intrinsic security embedded in CGAs to fit for all their requirements.

2.2. Compatibility Discussions

The solution of [RFC4982] in type I has a disadvantage that sometime in the future two different implementations may have different interpretation for the same SEC values, so a long time is required between the deprecation of the old value and the reassignment in order to prevent misinterpretation of the value by old implementations.

While other solutions do not have the problem of misinterpretation, they do need to consider the compatibility problem with current CGA implementations. Various compatibility solutions could be taken. For example, currently undefined SEC=111 in [RFC4982] could be used to denote that actual security parameter and hash algorithm identity are included in CGA parameters. For another example, version information could be added in CGA parameters or in CGA addresses, thus CGA without version information is looked as conforming to current implementation.

3. Conclusions

According to the above analysis, no solution type is absolutely better than others considering multiple factors, and any solution type could be compensated by additional security mechanism since CGA is only part of a bigger picture, e.g., security policy could be applied. But considering later flexibility, cryptanalysis progress and computing capability advancement, current CGA solution (RFC4982) is debatable.

4. IANA Considerations

This document includes no request for IANA now, but may have request once the final solution is determined.

5. Security Considerations

See security discussions.

6. References

6.1. Normative References

6.2. Informative References

Authors' Addresses