Request for Comments: 3972 Microsoft Research
Category: Standards Track March 2005
Cryptographically Generated Addresses (CGA)
Status of This Memo
This document specifies an Internet standards track protocol for the
Internet community, and requests discussion and suggestions for
improvements. Please refer to the current edition of the "Internet
Official Protocol Standards" (STD 1) for the standardization state
and status of this protocol. Distribution of this memo is unlimited.
Copyright Notice
Copyright (C) The Internet Society (2004).
Abstract
This document describes a method for binding a public signature key
to an IPv6 address in the Secure Neighbor Discovery (SEND) protocol.
Cryptographically Generated Addresses (CGA) are IPv6 addresses for
which the interface identifier is generated by computing a
cryptographic one-way hash function from a public key and auxiliary
parameters. The binding between the public key and the address can
be verified by re-computing the hash value and by comparing the hash
with the interface identifier. Messages sent from an IPv6 address
can be protected by attaching the public key and auxiliary parameters
and by signing the message with the corresponding private key. The
protection works without a certification authority or any security
infrastructure.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 2
2. CGA Format . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3. CGA Parameters and Hash Values . . . . . . . . . . . . . . . . 5
4. CGA Generation . . . . . . . . . . . . . . . . . . . . . . . . 6
5. CGA Verification . . . . . . . . . . . . . . . . . . . . . . . 9
6. CGA Signatures . . . . . . . . . . . . . . . . . . . . . . . . 10
7. Security Considerations . . . . . . . . . . . . . . . . . . . 12
7.1. Security Goals and Limitations . . . . . . . . . . . . . 12
7.2. Hash Extension . . . . . . . . . . . . . . . . . . . . . 13
7.3. Privacy Considerations . . . . . . . . . . . . . . . . . 15
7.4. Related Protocols . . . . . . . . . . . . . . . . . . . 15
8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 16
9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 17
9.1. Normative References . . . . . . . . . . . . . . . . . . 17
9.2. Informative References . . . . . . . . . . . . . . . . . 18
Appendices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
A. Example of CGA Generation. . . . . . . . . . . . . . . . . 20
B. Acknowledgements . . . . . . . . . . . . . . . . . . . . . 21
Author’s Address . . . . . . . . . . . . . . . . . . . . . . . . . 21
Full Copyright Statements. . . . . . . . . . . . . . . . . . . . . 22
1. Introduction
This document specifies a method for securely associating a
cryptographic public key with an IPv6 address in the Secure Neighbor
Discovery (SEND) protocol [RFC3971]. The basic idea is to generate
the interface identifier (i.e., the rightmost 64 bits) of the IPv6
address by computing a cryptographic hash of the public key. The
resulting IPv6 address is called a cryptographically generated
address (CGA). The corresponding private key can then be used to
sign messages sent from the address. An introduction to CGAs and
their application to SEND can be found in [Aura03] and [AAKMNR02].
This document specifies:
o how to generate a CGA from the cryptographic hash of a public key
and auxiliary parameters,
o how to verify the association between the public key and the CGA,
and
o how to sign a message sent from the CGA, and how to verify the
signature.
To verify the association between the address and the public key, the
verifier needs to know the address itself, the public key, and the
values of the auxiliary parameters. The verifier can then go on to
verify messages signed by the owner of the public key (i.e., the
address owner). No additional security infrastructure, such as a
public key infrastructure (PKI), certification authorities, or other
trusted servers, is needed.
Note that because CGAs themselves are not certified, an attacker can
create a new CGA from any subnet prefix and its own (or anyone
else’s) public key. However, the attacker cannot take a CGA created
by someone else and send signed messages that appear to come from the
owner of that address.
The address format and the CGA parameter format are defined in
Sections 2 and 3. Detailed algorithms for generating addresses and
for verifying them are given in Sections 4 and 5, respectively.
Section 6 defines the procedures for generating and verifying CGA
signatures. The security considerations in Section 7 include
limitations of CGA-based security, the reasoning behind the hash
extension technique that enables effective hash lengths above the
64-bit limit of the interface identifier, the implications of CGAs on
privacy, and protection against related-protocol attacks.
In this document, the key words MUST, MUST NOT, REQUIRED, SHALL,
SHALL NOT, SHOULD, SHOULD NOT, RECOMMENDED, MAY, and OPTIONAL are to
be interpreted as described in [RFC2119].
2. CGA Format
When talking about addresses, this document refers to IPv6 addresses
in which the leftmost 64 bits of a 128-bit address form the subnet
prefix and the rightmost 64 bits of the address form the interface
identifier [RFC3513]. We number the bits of the interface identifier
starting from bit zero on the left.
A cryptographically generated address (CGA) has a security parameter
(Sec) that determines its strength against brute-force attacks. The
security parameter is a three-bit unsigned integer, and it is encoded
in the three leftmost bits (i.e., bits 0 - 2) of the interface
identifier. This can be written as follows:
Sec = (interface identifier & 0xe000000000000000) >> 61
The CGA is associated with a set of parameters that consist of a
public key and auxiliary parameters. Two hash values Hash1 (64 bits)
and Hash2 (112 bits) are computed from the parameters. The formats
of the public key and auxiliary parameters, and the way to compute
the hash values, are defined in Section 3.
A cryptographically generated address is defined as an IPv6 address
that satisfies the following two conditions:
o The first hash value, Hash1, equals the interface identifier of
the address. Bits 0, 1, 2, 6, and 7 (i.e., the bits that encode
the security parameter Sec and the "u" and "g" bits from the
standard IPv6 address architecture format of interface identifiers
[RFC3513]) are ignored in the comparison.
o The 16*Sec leftmost bits of the second hash value, Hash2, are
zero.
The above definition can be stated in terms of the following two bit
masks:
Mask1 (64 bits) = 0x1cffffffffffffff
Mask2 (112 bits) = 0x0000000000000000000000000000 if Sec=0,
0xffff000000000000000000000000 if Sec=1,
0xffffffff00000000000000000000 if Sec=2,
0xffffffffffff0000000000000000 if Sec=3,
0xffffffffffffffff000000000000 if Sec=4,
0xffffffffffffffffffff00000000 if Sec=5,
0xffffffffffffffffffffffff0000 if Sec=6, and
0xffffffffffffffffffffffffffff if Sec=7
A cryptographically generated address is an IPv6 address for which
the following two equations hold:
Hash1 & Mask1 == interface identifier & Mask1
Hash2 & Mask2 == 0x0000000000000000000000000000
3. CGA Parameters and Hash Values
Each CGA is associated with a CGA Parameters data structure, which
has the following format:
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+ +
| |
+ Modifier (16 octets) +
| |
+ +
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+ Subnet Prefix (8 octets) +
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|Collision Count| |
+-+-+-+-+-+-+-+-+ |
| |
~ Public Key (variable length) ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
~ Extension Fields (optional, variable length) ~
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Modifier
This field contains a 128-bit unsigned integer, which can be any
value. The modifier is used during CGA generation to implement
the hash extension and to enhance privacy by adding randomness to
the address.
Subnet Prefix
This field contains the 64-bit subnet prefix of the CGA.
Collision Count
This is an eight-bit unsigned integer that MUST be 0, 1, or 2.
The collision count is incremented during CGA generation to
recover from an address collision detected by duplicate address
detection.
Public Key
This is a variable-length field containing the public key of the
address owner. The public key MUST be formatted as a DER-encoded
[ITU.X690.2002] ASN.1 structure of the type SubjectPublicKeyInfo,
defined in the Internet X.509 certificate profile [RFC3280]. SEND
SHOULD use an RSA public/private key pair. When RSA is used, the
algorithm identifier MUST be rsaEncryption, which is
1.2.840.113549.1.1.1, and the RSA public key MUST be formatted by
using the RSAPublicKey type as specified in Section 2.3.1 of RFC
3279 [RFC3279]. The RSA key length SHOULD be at least 384 bits.
Other public key types are undesirable in SEND, as they may result
in incompatibilities between implementations. The length of this
field is determined by the ASN.1 encoding.
Extension Fields
This is an optional variable-length field that is not used in the
current specification. Future versions of this specification may
use this field for additional data items that need to be included
in the CGA Parameters data structure. IETF standards action is
required to specify the use of the extension fields.
Implementations MUST ignore the value of any unrecognized
extension fields.
The two hash values MUST be computed as follows. The SHA-1 hash
algorithm [FIPS.180-1.1995] is applied to the CGA Parameters. When
Hash1 is computed, the input to the SHA-1 algorithm is the CGA
Parameters data structure. The 64-bit Hash1 is obtained by taking
the leftmost 64 bits of the 160-bit SHA-1 hash value. When Hash2 is
computed, the input is the same CGA Parameters data structure except
that the subnet prefix and collision count are set to zero. The
112-bit Hash2 is obtained by taking the leftmost 112 bits of the
160-bit SHA-1 hash value. Note that the hash values are computed
over the entire CGA Parameters data structure, including any
unrecognized extension fields.
4. CGA Generation
The process of generating a new CGA takes three input values: a
64-bit subnet prefix, the public key of the address owner as a
DER-encoded ASN.1 structure of the type SubjectPublicKeyInfo, and the
security parameter Sec, which is an unsigned three-bit integer. The
cost of generating a new CGA depends exponentially on the security
parameter Sec, which can have values from 0 to 7.
A CGA and associated parameters SHOULD be generated as follows:
1. Set the modifier to a random or pseudo-random 128-bit value.
2. Concatenate from left to right the modifier, 9 zero octets, the
encoded public key, and any optional extension fields. Execute
the SHA-1 algorithm on the concatenation. Take the 112 leftmost
bits of the SHA-1 hash value. The result is Hash2.
3. Compare the 16*Sec leftmost bits of Hash2 with zero. If they are
all zero (or if Sec=0), continue with step 4. Otherwise,
increment the modifier by one and go back to step 2.
4. Set the 8-bit collision count to zero.
5. Concatenate from left to right the final modifier value, the
subnet prefix, the collision count, the encoded public key, and
any optional extension fields. Execute the SHA-1 algorithm on the
concatenation. Take the 64 leftmost bits of the SHA-1 hash value.
The result is Hash1.
6. Form an interface identifier from Hash1 by writing the value of
Sec into the three leftmost bits and by setting bits 6 and 7
(i.e., the "u" and "g" bits) to zero.
7. Concatenate the 64-bit subnet prefix and the 64-bit interface
identifier to form a 128-bit IPv6 address with the subnet prefix
to the left and interface identifier to the right, as in a
standard IPv6 address [RFC3513].
8. Perform duplicate address detection if required, as per [RFC3971].
If an address collision is detected, increment the collision count
by one and go back to step 5. However, after three collisions,
stop and report the error.
9. Form the CGA Parameters data structure by concatenating from left
to right the final modifier value, the subnet prefix, the final
collision count value, the encoded public key, and any optional
extension fields.
The output of the address generation algorithm is a new CGA and a CGA
Parameters data structure.
The initial value of the modifier in step 1 SHOULD be chosen randomly
to make addresses generated from the same public key unlinkable,
which enhances privacy (see Section 7.3). The quality of the random
number generator does not affect the strength of the binding between
the address and the public key. Implementations that have no strong
random numbers available MAY use a non-cryptographic pseudo-random
number generator initialized with the current time of day.
For Sec=0, the above algorithm is deterministic and relatively fast.
Nodes that implement CGA generation MAY always use the security
parameter value Sec=0. If Sec=0, steps 2 - 3 of the generation
algorithm can be skipped.
For Sec values greater than zero, the above algorithm is not
guaranteed to terminate after a certain number of iterations. The
brute-force search in steps 2 - 3 takes O(2^(16*Sec)) iterations to
complete. The algorithm has been intentionally designed so that the
generation of CGAs with high Sec values is infeasible with current
technology.
Implementations MAY use optimized or otherwise modified versions of
the above algorithm for CGA generation. However, the output of any
modified versions MUST fulfill the following two requirements.
First, the resulting CGA and CGA Parameters data structure MUST be
formatted as specified in Sections 2 - 3. Second, the CGA
verification procedure defined in Section 5 MUST succeed when invoked
on the output of the CGA generation algorithm. Note that some
optimizations involve trade-offs between privacy and the cost of
address generation.
One optimization is particularly important. If the subnet prefix of
the address changes but the address owner’s public key does not, the
old modifier value MAY be reused. If it is reused, the algorithm
SHOULD be started from step 4. This optimization avoids repeating
the expensive search for an acceptable modifier value but may, in
some situations, make it easier for an observer to link two addresses
to each other.
Note that this document does not specify whether duplicate address
detection should be performed and how the detection is done. Step 8
only defines what to do if some form of duplicate address detection
is performed and an address collision is detected.
Future versions of this specification may specify additional inputs
to the CGA generation algorithm that are concatenated as extension
fields to the end of the CGA Parameters data structure. No such
extension fields are defined in this document.
5. CGA Verification
CGA verification takes an IPv6 address and a CGA Parameters data
structure as input. The CGA Parameters consist of the concatenated
modifier, subnet prefix, collision count, public key, and optional
extension fields. The verification either succeeds or fails.
The CGA MUST be verified with the following steps:
1. Check that the collision count in the CGA Parameters data
structure is 0, 1, or 2. The CGA verification fails if the
collision count is out of the valid range.
2. Check that the subnet prefix in the CGA Parameters data structure
is equal to the subnet prefix (i.e., the leftmost 64 bits) of the
address. The CGA verification fails if the prefix values differ.
3. Execute the SHA-1 algorithm on the CGA Parameters data structure.
Take the 64 leftmost bits of the SHA-1 hash value. The result is
Hash1.
4. Compare Hash1 with the interface identifier (i.e., the rightmost
64 bits) of the address. Differences in the three leftmost bits
and in bits 6 and 7 (i.e., the "u" and "g" bits) are ignored. If
the 64-bit values differ (other than in the five ignored bits),
the CGA verification fails.
5. Read the security parameter Sec from the three leftmost bits of
the 64-bit interface identifier of the address. (Sec is an
unsigned 3-bit integer.)
6. Concatenate from left to right the modifier, 9 zero octets, the
public key, and any extension fields that follow the public key in
the CGA Parameters data structure. Execute the SHA-1 algorithm on
the concatenation. Take the 112 leftmost bits of the SHA-1 hash
value. The result is Hash2.
7. Compare the 16*Sec leftmost bits of Hash2 with zero. If any one
of them is not zero, the CGA verification fails. Otherwise, the
verification succeeds. (If Sec=0, the CGA verification never
fails at this step.)
If the verification fails at any step, the execution of the algorithm
MUST be stopped immediately. On the other hand, if the verification
succeeds, the verifier knows that the public key in the CGA
Parameters is the authentic public key of the address owner. The
verifier can extract the public key by removing 25 octets from the
beginning of the CGA Parameters and by decoding the following
SubjectPublicKeyInfo data structure.
Note that the values of bits 6 and 7 (the "u" and "g" bits) of the
interface identifier are ignored during CGA verification. In the
SEND protocol, after the verification succeeds, the verifier SHOULD
process all CGAs in the same way regardless of the Sec, modifier, and
collision count values. In particular, the verifier in the SEND
protocol SHOULD NOT have any security policy that differentiates
between addresses based on the value of Sec. That way, the address
generator is free to choose any value of Sec.
All nodes that implement CGA verification MUST be able to process all
security parameter values Sec = 0, 1, 2, 3, 4, 5, 6, 7. The
verification procedure is relatively fast and always requires at most
two computations of the SHA-1 hash function. If Sec=0, the
verification never fails in steps 6 - 7 and these steps can be
skipped.
Nodes that implement CGA verification for SEND SHOULD be able to
process RSA public keys that have the algorithm identifier
rsaEncryption and, key length between 384 and 2,048 bits.
Implementations MAY support longer keys. Future versions of this
specification may recommend support for longer keys.
Implementations of CGA verification MUST ignore the value of any
unrecognized extension fields that follow the public key in the CGA
Parameters data structure. However, implementations MUST include any
such unrecognized data in the hash input when computing Hash1 in step
3 and Hash2 in step 6 of the CGA verification algorithm. This is
important to ensure upward compatibility with future extensions.