6. CGA Signatures
This section defines the procedures for generating and verifying CGA
signatures. To sign a message, a node needs the CGA, the associated
CGA Parameters data structure, the message, and the private
cryptographic key that corresponds to the public key in the CGA
Parameters. The node also must have a 128-bit type tag for the
message from the CGA Message Type name space.
To sign a message, a node SHOULD do the following:
o Concatenate the 128-bit type tag (in network byte order) and the
message with the type tag to the left and the message to the
right. The concatenation is the message to be signed in the next
step.
o Generate the RSA signature by using the RSASSA-PKCS1-v1_5
[RFC3447] signature algorithm with the SHA-1 hash algorithm. The
private key and the concatenation created above are the inputs to
the generation operation.
The SEND protocol specification [RFC3971] defines several messages
that contain a signature in the Signature Option. The SEND protocol
specification also defines a type tag from the CGA Message Type name
space. The same type tag is used for all the SEND messages that have
the Signature Option. This type tag is an IANA-allocated 128 bit
integer that has been chosen at random to prevent an accidental type
collision with messages of other protocols that use the same public
key but that may or may not use IANA-allocated type tags.
The CGA, the CGA Parameters data structure, the message, and the
signature are sent to the verifier. The SEND protocol specification
defines how these data items are sent in SEND protocol messages.
Note that the 128-bit type tag is not included in the SEND protocol
messages because the verifier knows its value implicitly from the
ICMP message type field in the SEND message. See the SEND
specification [RFC3971] for precise information about how SEND
handles the type tag.
To verify a signature, the verifier needs the CGA, the associated CGA
Parameters data structure, the message, and the signature. The
verifier also needs to have the 128-bit type tag for the message.
To verify the signature, a node SHOULD do the following:
o Verify the CGA as defined in Section 5. The inputs to the CGA
verification are the CGA and the CGA Parameters data structure.
o Concatenate the 128-bit type tag and the message with the type tag
to the left and the message to the right. The concatenation is
the message whose signature is to be verified in the next step.
o Verify the RSA signature by using the RSASSA-PKCS1-v1_5 [RFC3447]
algorithm with the SHA-1 hash algorithm. The inputs to the
verification operation are the public key (i.e., the RSAPublicKey
structure from the SubjectPublicKeyInfo structure that is a part
of the CGA Parameters data structure), the concatenation created
above, and the signature.
The verifier MUST accept the signature as authentic only if both the
CGA verification and the signature verification succeed.
7. Security Considerations
7.1. Security Goals and Limitations
The purpose of CGAs is to prevent stealing and spoofing of existing
IPv6 addresses. The public key of the address owner is bound
cryptographically to the address. The address owner can use the
corresponding private key to assert its ownership and to sign SEND
messages sent from the address.
It is important to understand that an attacker can create a new
address from an arbitrary subnet prefix and its own (or someone
else’s) public key because CGAs are not certified. However, the
attacker cannot impersonate somebody else’s address. This is because
the attacker would have to find a collision of the cryptographic hash
value Hash1. (The property of the hash function needed here is
called second pre-image resistance [MOV97].)
For each valid CGA Parameters data structure, there are 4*(Sec+1)
different CGAs that match the value. This is because decrementing
the Sec value in the three leftmost bits of the interface identifier
does not invalidate the address, and the verifier ignores the values
of the "u" and "g" bits. In SEND, this does not have any security or
implementation implications.
Another limitation of CGAs is that there is no mechanism for proving
that an address is not a CGA. Thus, an attacker could take someone
else’s CGA and present it as a non-cryptographically generated
address (e.g., as an RFC 3041 address [RFC3041]). An attacker does
not benefit from this because although SEND nodes accept both signed
and unsigned messages from every address, they give priority to the
information in the signed messages.
The minimum RSA key length required for SEND is only 384 bits. So
short keys are vulnerable to integer-factoring attacks and cannot be
used for strong authentication or secrecy. On the other hand, the
cost of factoring 384-bit keys is currently high enough to prevent
most denial-of-service attacks. Implementations that initially use
short RSA keys SHOULD be prepared to switch to longer keys when
denial-of-service attacks arising from integer factoring become a
problem.
The impact of a key compromise on CGAs depends on the application for
which they are used. In SEND, it is not a major concern. If the
private signature key is compromised because the SEND node has itself
been compromised, the attacker does not need to spoof SEND messages
from the node. When it is discovered that a node has been
compromised, a new signature key and a new CGA SHOULD be generated.
On the other hand, if the RSA key is compromised because integer-
factoring attacks for the chosen key length have become practical,
the key has to be replaced with a longer one, as explained above. In
either case, the address change effectively revokes the old public
key. It is not necessary to have any additional key revocation
mechanism or to limit the lifetimes of the signature keys.
7.2. Hash Extension
As computers become faster, the 64 bits of the interface identifier
will not be sufficient to prevent attackers from searching for hash
collisions. It helps somewhat that we include the subnet prefix of
the address in the hash input. This prevents the attacker from using
a single pre-computed database to attack addresses with different
subnet prefixes. The attacker needs to create a separate database
for each subnet prefix. Link-local addresses are, however, left
vulnerable because the same prefix is used by all IPv6 nodes.
To prevent the CGA technology from becoming outdated as computers
become faster, the hash technique used to generate CGAs must be
extended somehow. The chosen extension technique is to increase the
cost of both address generation and brute-force attacks by the same
parameterized factor while keeping the cost of address use and
verification constant. This also provides protection for link-local
addresses. Introduction of the hash extension is the main difference
between this document and earlier CGA proposals [OR01][Nik01][MC02].
To achieve the effective extension of the hash length, the input to
the second hash function, Hash2, is modified (by changing the
modifier value) until the leftmost 16*Sec bits of the hash value are
zero. This increases the cost of address generation approximately by
a factor of 2^(16*Sec). It also increases the cost of brute-force
attacks by the same factor. That is, the cost of creating a CGA
Parameters data structure that binds the attacker’s public key with
somebody else’s address is increased from O(2^59) to
O(2^(59+16*Sec)). The address generator may choose the security
parameter Sec depending on its own computational capacity, the
perceived risk of attacks, and the expected lifetime of the address.
Currently, Sec values between 0 and 2 are sufficient for most IPv6
nodes. As computers become faster, higher Sec values will slowly
become useful.
Theoretically, if no hash extension is used (i.e., Sec=0) and a
typical attacker is able to tap into N local networks at the same
time, an attack against link-local addresses is N times as efficient
as an attack against addresses of a specific network. The effect
could be countered by using a slightly higher Sec value for link-
local addresses. When higher Sec values (such that 2^(16*Sec) > N)
are used for all addresses, the relative advantage of attacking
link-local addresses becomes insignificant.
The effectiveness of the hash extension depends on the assumption
that the computational capacities of the attacker and the address
generator will grow at the same (potentially exponential) rate. This
is not necessarily true if the addresses are generated on low-end
mobile devices, for which the main design goals are to lower cost and
decrease size, rather than increase computing power. But there is no
reason for doing so. The expensive part of the address generation
(steps 1 - 3 of the generation algorithm) may be delegated to a more
powerful computer. Moreover, this work can be done in advance or
offline, rather than in real time, when a new address is needed.
To make it possible for mobile nodes whose subnet prefixes change
frequently to use Sec values greater than zero, we have decided not
to include the subnet prefix in the input of Hash2. The result is
weaker than it would be if the subnet prefix were included in the
input of both hashes. On the other hand, our scheme is at least as
strong as using the hash extension technique without including the
subnet prefix in either hash. It is also at least as strong as not
using the hash extension but including the subnet prefix. This
trade-off was made because mobile nodes frequently move to insecure
networks, where they are at the risk of denial-of-service (DoS)
attacks (for example, during the duplicate address detection
procedure).
In most networks, the goal of Secure Neighbor Discovery and CGA
signatures is to prevent denial-of-service attacks. Therefore, it is
usually sensible to start by using a low Sec value and to replace
addresses with stronger ones only when denial-of-service attacks
based on brute-force search become a significant problem. If CGAs
were used as a part of a strong authentication or secrecy mechanism,
it might be necessary to start with higher Sec values.
The collision count value is used to modify the input to Hash1 if
there is an address collision. It is important not to allow
collision count values higher than 2. First, it is extremely
unlikely that three collisions would occur and the reason is certain
to be either a configuration or implementation error or a denial-of-
service attack. (When the SEND protocol is used, deliberate
collisions caused by a DoS attacker are detected and ignored.)
Second, an attacker doing a brute-force search to match a given CGA
can try all different values of a collision count without repeating
the brute-force search for the modifier value. Thus, if higher
values are allowed for the collision count, the hash extension
technique becomes less effective in preventing brute force attacks.
7.3. Privacy Considerations
CGAs can give the same level of pseudonymity as the IPv6 address
privacy extensions defined in RFC 3041 [RFC3041]. An IP host can
generate multiple pseudo-random CGAs by executing the CGA generation
algorithm of Section 4 multiple times and by using a different random
or pseudo-random initial value for the modifier every time. The host
should change its address periodically as in [RFC3041]. When privacy
protection is needed, the (pseudo)random number generator used in
address generation SHOULD be strong enough to produce unpredictable
and unlinkable values. Advice on random number generation can be
found in [RFC1750].
There are two apparent limitations to this privacy protection.
However, as will be explained below, neither is very serious.
First, the high cost of address generation may prevent hosts that use
a high Sec value from changing their address frequently. This
problem is mitigated because the expensive part of the address
generation may be done in advance or offline, as explained in the
previous section. It should also be noted that the nodes that
benefit most from high Sec values (e.g., DNS servers, routers, and
data servers) usually do not require pseudonymity, and the nodes that
have high privacy requirements (e.g., client PCs and mobile hosts)
are unlikely targets for expensive brute-force DoS attacks and can
make do with lower Sec values.
Second, the public key of the address owner is revealed in the signed
SEND messages. This means that if the address owner wants to be
pseudonymous toward the nodes in the local links that it accesses, it
should generate not only a new address but also a new public key.
With typical local-link technologies, however, a node’s link-layer
address is a unique identifier for the node. As long as the node
keeps using the same link-layer address, it makes little sense to
change the public key for privacy reasons.
7.4. Related Protocols
Although this document defines CGAs only for the purposes of Secure
Neighbor Discovery, other protocols could be defined elsewhere that
use the same addresses and public keys. This raises the possibility
of related-protocol attacks in which a signed message from one
protocol is replayed in another protocol. This means that other
protocols (perhaps even those designed without an intimate knowledge
of SEND) could endanger the security of SEND. What makes this threat
even more significant is that the attacker could create a CGA from
someone else’s public key and then replay signed messages from a
protocol that has nothing to do with CGAs or IP addresses.
To prevent the related-protocol attacks, a type tag is prepended to
every message before it is signed. The type tags are 128-bit
randomly chosen values, which prevents accidental type collisions
with even poorly designed protocols that do not use any type tags.
Moreover, the SEND protocol includes the sender’s CGA address in all
signed messages. This makes it even more difficult for an attacker
to take signed messages from some other context and to replay them as
SEND messages.
Finally, a strong cautionary note has to be made about using CGA
signatures for purposes other than SEND. First, the other protocols
MUST include a type tag and the sender address in all signed messages
in the same way that SEND does. Each protocol MUST define its own
type tag values as explained in Section 8. Moreover, because of the
possibility of related-protocol attacks, the public key MUST be used
only for signing, and it MUST NOT be used for encryption. Second,
the minimum RSA key length of 384 bits may be too short for many
applications and the impact of key compromise on the particular
protocol must be evaluated. Third, CGA-based authorization is
particularly suitable for securing neighbor discovery [RFC2461] and
duplicate address detection [RFC2462] because these are network-layer
signaling protocols for which IPv6 addresses are natural endpoint
identifiers. In any protocol that uses other identifiers, such as
DNS names, CGA signatures alone are not a sufficient security
mechanism. There must also be a secure way of mapping the other
identifiers to IPv6 addresses. If the goal is not to verify claims
about IPv6 addresses, CGA signatures are probably not the right
solution.
8. IANA Considerations
This document defines a new CGA Message Type name space for use as
type tags in messages that may be signed by using CGA signatures.
The values in this name space are 128-bit unsigned integers. Values
in this name space are allocated on a First Come First Served basis
[RFC2434]. IANA assigns new 128-bit values directly without a
review.
The requester SHOULD generate the new values with a strong random-
number generator. Continuous ranges of at most 256 values can be
requested provided that the 120 most significant bits of the values
have been generated with a strong random-number generator.
IANA does not generate random values for the requester. IANA
allocates requested values without verifying the way in which they
have been generated. The name space is essentially unlimited, and
any number of individual values and ranges of at most 256 values can
be allocated.
CGA Message Type values for private use MAY be generated with a
strong random-number generator without IANA allocation.
This document does not define any new values in any name space.
9. References
9.1. Normative References
[RFC3971] Arkko, J., Ed., Kempf, J., Sommerfeld, B., Zill,
B., and P. Nikander, "SEcure Neighbor Discovery
(SEND)", RFC 3971, March 2005.
[RFC3279] Bassham, L., Polk, W., and R. Housley, "Algorithms
and Identifiers for the Internet X.509 Public Key
Infrastructure Certificate and Certificate
Revocation List (CRL) Profile", RFC 3279, April
2002.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC3513] Hinden, R. and S. Deering, "Internet Protocol
Version 6 (IPv6) Addressing Architecture", RFC
3513, April 2003.
[RFC3280] Housley, R., Polk, W., Ford, W., and D. Solo,
"Internet X.509 Public Key Infrastructure
Certificate and Certificate Revocation List (CRL)
Profile", RFC 3280, April 2002.
[ITU.X690.2002] International Telecommunications Union,
"Information Technology - ASN.1 encoding rules:
Specification of Basic Encoding Rules (BER),
Canonical Encoding Rules (CER) and Distinguished
Encoding Rules (DER)", ITU-T Recommendation X.690,
July 2002.
[RFC3447] Jonsson, J. and B. Kaliski, "Public-Key
Cryptography Standards (PKCS) #1: RSA Cryptography
Specifications Version 2.1", RFC 3447, February
2003.
[RFC2434] Narten, T. and H. Alvestrand, "Guidelines for
Writing an IANA Considerations Section in RFCs",
BCP 26, RFC 2434, October 1998.
[FIPS.180-1.1995] National Institute of Standards and Technology,
"Secure Hash Standard", Federal Information
Processing Standards Publication FIPS PUB 180-1,
April 1995,
<http://www.itl.nist.gov/fipspubs/fip180-1.htm>.
9.2. Informative References
[AAKMNR02] Arkko, J., Aura, T., Kempf, J., Mantyla, V.,
Nikander, P., and M. Roe, "Securing IPv6 neighbor
discovery and router discovery", ACM Workshop on
Wireless Security (WiSe 2002), Atlanta, GA USA ,
September 2002.
[Aura03] Aura, T., "Cryptographically Generated Addresses
(CGA)", 6th Information Security Conference
(ISC’03), Bristol, UK, October 2003.
[RFC1750] Eastlake, D., Crocker, S., and J. Schiller,
"Randomness Recommendations for Security", RFC
1750, December 1994.
[MOV97] Menezes, A., van Oorschot, P., and S. Vanstone,
"Handbook of Applied Cryptography", CRC Press ,
1997.
[MC02] Montenegro, G. and C. Castelluccia, "Statistically
unique and cryptographically verifiable identifiers
and addresses", ISOC Symposium on Network and
Distributed System Security (NDSS 2002), San Diego,
CA USA , February 2002.
[RFC3041] Narten, T. and R. Draves, "Privacy Extensions for
Stateless Address Autoconfiguration in IPv6", RFC
3041, January 2001.
[RFC2461] Narten, T., Nordmark, E., and W. Simpson, "Neighbor
Discovery for IP Version 6 (IPv6)", RFC 2461,
December 1998.
[Nik01] Nikander, P., "A scaleable architecture for IPv6
address ownership", draft-nikander-addr-ownership-
00 (work in progress), March 2001.
[OR01] O’Shea, G. and M. Roe, "Child-proof authentication
for MIPv6 (CAM)", ACM Computer Communications
Review 31(2), April 2001.
[RFC2462] Thomson, S. and T. Narten, "IPv6 Stateless Address
Autoconfiguration", RFC 2462, December 1998.
Appendix A. Example of CGA Generation
We generate a CGA with Sec=1 from the subnet prefix fe80:: and the
following public key:
305c 300d 0609 2a86 4886 f70d 0101 0105 0003 4b00 3048 0241
00c2 c2f1 3730 5454 f10b d9ce a368 44b5 30e9 211a 4b26 2b16
467c b7df ba1f 595c 0194 f275 be5a 4d38 6f2c 3c23 8250 8773
c786 7f9b 3b9e 63a0 9c7b c48f 7a54 ebef af02 0301 0001
The modifier is initialized to a random value 89a8 a8b2 e858 d8b8
f263 3f44 d2d4 ce9a. The input to Hash2 is:
89a8 a8b2 e858 d8b8 f263 3f44 d2d4 ce9a 0000 0000 0000 0000 00
305c 300d 0609 2a86 4886 f70d 0101 0105 0003 4b00 3048 0241
00c2 c2f1 3730 5454 f10b d9ce a368 44b5 30e9 211a 4b26 2b16
467c b7df ba1f 595c 0194 f275 be5a 4d38 6f2c 3c23 8250 8773
c786 7f9b 3b9e 63a0 9c7b c48f 7a54 ebef af02 0301 0001
The 112 first bits of the SHA-1 hash value computed from the above
input are Hash2=436b 9a70 dbfd dbf1 926e 6e66 29c0. This does not
begin with 16*Sec=16 zero bits. Thus, we must increment the modifier
by one and recompute the hash. The new input to Hash2 is:
89a8 a8b2 e858 d8b8 f263 3f44 d2d4 ce9b 0000 0000 0000 0000 00
305c 300d 0609 2a86 4886 f70d 0101 0105 0003 4b00 3048 0241
00c2 c2f1 3730 5454 f10b d9ce a368 44b5 30e9 211a 4b26 2b16
467c b7df ba1f 595c 0194 f275 be5a 4d38 6f2c 3c23 8250 8773
c786 7f9b 3b9e 63a0 9c7b c48f 7a54 ebef af02 0301 0001
The new hash value is Hash2=0000 01ca 680b 8388 8d09 12df fcce. The
16 leftmost bits of Hash2 are all zero. Thus, we found a suitable
modifier. (We were very lucky to find it so soon.)
The input to Hash1 is:
89a8 a8b2 e858 d8b8 f263 3f44 d2d4 ce9b fe80 0000 0000 0000 00
305c 300d 0609 2a86 4886 f70d 0101 0105 0003 4b00 3048 0241