[Docs] [txt|pdf] [Tracker] [WG] [Email] [Diff1] [Diff2] [Nits] [IPR]

Versions: (draft-arkko-send-cga) 00 01 02 03 04 05 06 RFC 3972

Securing Neighbor Discovery                                      T. Aura
Internet-Draft                                        Microsoft Research
Expires: August 6, 2004                                 February 6, 2004


              Cryptographically Generated Addresses (CGA)
                         draft-ietf-send-cga-05

Status of this Memo

   This document is an Internet-Draft and is in full conformance with
   all provisions of Section 10 of RFC2026.

   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 August 6, 2004.

Copyright Notice

   Copyright (C) The Internet Society (2004). All Rights Reserved.

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 where
   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 other security
   infrastructure.




Aura                     Expires August 6, 2004                 [Page 1]


Internet-Draft    Cryptographically Generated Addresses (CGA)    February 2004


Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
   2.  CGA Format . . . . . . . . . . . . . . . . . . . . . . . . . .  5
   3.  CGA Parameters and Hash Values . . . . . . . . . . . . . . . .  7
   4.  CGA Generation . . . . . . . . . . . . . . . . . . . . . . . .  8
   5.  CGA Verification . . . . . . . . . . . . . . . . . . . . . . . 10
   6.  CGA Signatures . . . . . . . . . . . . . . . . . . . . . . . . 12
   7.  Security Considerations  . . . . . . . . . . . . . . . . . . . 14
   7.1 Security Goals and Limitations . . . . . . . . . . . . . . . . 14
   7.2 Hash extension . . . . . . . . . . . . . . . . . . . . . . . . 14
   7.3 Privacy Considerations . . . . . . . . . . . . . . . . . . . . 16
   7.4 Related protocols  . . . . . . . . . . . . . . . . . . . . . . 17
   8.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 18
       Normative References . . . . . . . . . . . . . . . . . . . . . 19
       Informative References . . . . . . . . . . . . . . . . . . . . 20
       Author's Address . . . . . . . . . . . . . . . . . . . . . . . 21
   A.  Example of CGA Generation  . . . . . . . . . . . . . . . . . . 22
   B.  Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 24
       Intellectual Property and Copyright Statements . . . . . . . . 25































Aura                     Expires August 6, 2004                 [Page 2]


Internet-Draft    Cryptographically Generated Addresses (CGA)    February 2004


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 [I-D.ietf-send-ndopt]. 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.

   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 that is sent from the CGA, and how to verify
      the signature.

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

   It is important to 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. What the attacker cannot
   do is to 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 authentication, 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.

   The key words MUST, MUST NOT, REQUIRED, SHALL, SHALL NOT, SHOULD,
   SHOULD NOT, RECOMMENDED,  MAY, and OPTIONAL in this document are to



Aura                     Expires August 6, 2004                 [Page 3]


Internet-Draft    Cryptographically Generated Addresses (CGA)    February 2004


   be interpreted as described in [RFC2119].


















































Aura                     Expires August 6, 2004                 [Page 4]


Internet-Draft    Cryptographically Generated Addresses (CGA)    February 2004


2. CGA Format

   When talking about addresses, this document refers to IPv6 addresses
   where 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 0 on the left.

   A cryptographically generated address (CGA) has a security parameter
   (Sec), which determines its strength against brute-force attacks. The
   security parameter is a 3-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:

       Sec = (interface identifier & 0xe000000000000000) >> 61

   The CGA is associated with a set of parameters, which 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




Aura                     Expires August 6, 2004                 [Page 5]


Internet-Draft    Cryptographically Generated Addresses (CGA)    February 2004


   A cryptographically generated address is an IPv6 address for which
   the following two equations hold:

       Hash1 & Mask1  ==  interface identifier & Mask1
       Hash2 & Mask2  ==  0x0000000000000000000000000000














































Aura                     Expires August 6, 2004                 [Page 6]


Internet-Draft    Cryptographically Generated Addresses (CGA)    February 2004


3. CGA Parameters and Hash Values

   Each CGA is associated with a public key and auxiliary parameters.
   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]. For SEND, the public
   key SHOULD be an RSA encryption key with the object identifier
   rsaEncryption (i.e., "1.2.840.113549.1.1.1") and the subject public
   key field SHOULD be formatted as an ASN.1 data structure of the type
   RSAEncryptionKey defined in [PKCS.1.2002]. The RSA key length SHOULD
   be at least 384 bits. Other public key types or format SHOULD NOT be
   used for SEND to avoid incompatibilities [I-D.ietf-send-ndopt].

   The auxiliary parameters are the following three unsigned integers:

   o  a 128-bit modifier, which can be any value,

   o  a 64-bit subnet prefix, which is equal to the subnet prefix of the
      CGA, and

   o  an 8-bit collision count, which can have values 0, 1 and 2.

   We use the name "CGA Parameters" for the data structure that is the
   concatenation (from left to right) of the 16-octet modifier, the
   8-octet subnet prefix, the 1-octet collision count, and the
   variable-length encoded public key (i.e., the SubjectPublicKeyInfo
   structure).

   The two hash values MUST be computed as follows. The SHA-1 hash
   algorithm [FIPS.180-1.1995] is applied to the public key and
   auxiliary parameters. When computing Hash1, 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 computing Hash2, 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.














Aura                     Expires August 6, 2004                 [Page 7]


Internet-Draft    Cryptographically Generated Addresses (CGA)    February 2004


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 3-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 pseudorandom 128-bit value.

   2.  Concatenate from left to right the modifier, 9 zero octets, and
       the encoded public key. 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 and the encoded public key.
       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) both 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 address collision detection if required, as per
       [I-D.ietf-send-ndopt]. 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, and the encoded public key.

   The output of the address generation algorithm is a new CGA and a CGA



Aura                     Expires August 6, 2004                 [Page 8]


Internet-Draft    Cryptographically Generated Addresses (CGA)    February 2004


   Parameters data structure.

   The initial value of the modifier in step (1) SHOULD be chosen
   randomly in order 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.

   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 0, 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.
   It is intentional that generating 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
   such modified versions of the algorithm 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. It is
   important to 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.










Aura                     Expires August 6, 2004                 [Page 9]


Internet-Draft    Cryptographically Generated Addresses (CGA)    February 2004


5. CGA Verification

   CGA verification takes as input an IPv6 address and a CGA Parameters
   data structure. The CGA Parameters consist of the concatenated
   modifier, subnet prefix, collision count, and public key. 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, and
       the public key. 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 non-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 bytes from the
   beginning of the CGA Parameters and by decoding the following
   SubjectPublicKeyInfo data structure. Future versions of this



Aura                     Expires August 6, 2004                [Page 10]


Internet-Draft    Cryptographically Generated Addresses (CGA)    February 2004


   specification may add new fields to the end of the CGA Parameters and
   the verifier SHOULD ignore any unrecognized data that follows the
   encoded public key.

   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 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 OID rsaEncryption and key
   length between 384 and 2048 bits. Implementations MAY support longer
   keys. Future versions of this specification may recommend support for
   longer keys.


























Aura                     Expires August 6, 2004                [Page 11]


Internet-Draft    Cryptographically Generated Addresses (CGA)    February 2004


6. CGA Signatures

   This section defines the procedures for generating and verifying CGA
   signatures. In order 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 needs to 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 using the RSASSA-PKCS1-v1_5
      [PKCS.1.2002] signature algorithm with the SHA-1 hash algorithm.
      The inputs to the generation operation are the private key and the
      concatenation created above.

   The SEND protocol specification [I-D.ietf-send-ndopt] 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 accidental
   type collision with messages of other protocols that use the same
   public key but 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 this data is 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
   [I-D.ietf-send-ndopt] for precise information about how SEND handles
   the type tag.

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



Aura                     Expires August 6, 2004                [Page 12]


Internet-Draft    Cryptographically Generated Addresses (CGA)    February 2004


   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 using the RSASSA-PKCS1-v1_5 [PKCS.1.2002]
      algorithm with the SHA-1 hash algorithm. The inputs to the
      verification operation are the public key (i.e., the
      RSAEncryptionKey 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.






































Aura                     Expires August 6, 2004                [Page 13]


Internet-Draft    Cryptographically Generated Addresses (CGA)    February 2004


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 of the address 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. What the attacker
   cannot do is to 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 fact 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.

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.

   In order 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



Aura                     Expires August 6, 2004                [Page 14]


Internet-Draft    Cryptographically Generated Addresses (CGA)    February 2004


   by the same parameterized factor while keeping the cost of address
   use and verification constant. This provides protection also 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, 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 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 where the main design goals are lower cost and smaller
   size rather than increased 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.

   In order to make it possible for mobile nodes whose subnet prefix
   changes frequently to use Sec values greater than 0, we have decided
   not to include the subnet prefix in the input of Hash2. The result is
   weaker than 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



Aura                     Expires August 6, 2004                [Page 15]


Internet-Draft    Cryptographically Generated Addresses (CGA)    February 2004


   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-based
   authentication 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 mechanisms,
   it would 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, the deliberate collisions caused by
   a DoS attacker are detected and ignored.) Second, an attacker who is
   doing a brute-force search to match a given CGA can try all different
   values of 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 pseudonymity as the IPv6 address privacy
   extensions defined in RFC 3041 [RFC3041]. An IP host can generate
   multiple pseudorandom CGAs by executing the CGA generation algorithm
   of Section 4 multiple times and using a different random or
   pseudorandom 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.

   There are two apparent limitations to this privacy protection.
   However, as we will explain below, neither limitation 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 by the fact that 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, while the nodes that



Aura                     Expires August 6, 2004                [Page 16]


Internet-Draft    Cryptographically Generated Addresses (CGA)    February 2004


   have high privacy requirements (e.g., client PCs and mobile hosts)
   are unlikely targets for expensive brute-force DoS attacks and can do
   with lower Sec values.

   Second, the public key of the address owner is revealed in the
   authenticated SEND messages. This means that if the address owner
   wants to be pseudonymous towards the nodes in the local links that it
   accesses, it should not only generate 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 ever change the public key for privacy reasons.

7.4 Related protocols

   While 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-key attacks where a signed message from one protocol is
   replayed in another protocol. This means that other protocols
   (perhaps 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 take someone else's public key
   and create a CGA from it, 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 signing it. 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, some cautionary notes should be made about using CGA-based
   authentication for other purposes than SEND. First, the other
   protocols should include type tags and the sender address in all
   signed messages in the same way as SEND does. Because of the
   possibility of related-protocol attacks, it is advisable to use the
   public key only for signing and not for encryption. Second, CGA-based
   authentication is particularly suitable for securing neighbor
   discovery [RFC2461] and duplicate address detection [RFC2462] because
   these are network-layer signaling protocols where IPv6 addresses are
   natural endpoint identifiers. In any protocol that aims to protect
   higher-layer data, CGA-based authentication alone is not sufficient
   and there must also be a secure mechanism for mapping higher-layer
   identifiers, such as DNS names, to IP addresses.



Aura                     Expires August 6, 2004                [Page 17]


Internet-Draft    Cryptographically Generated Addresses (CGA)    February 2004


8. IANA Considerations

   This document defines a new CGA Message Type name space for use as
   type tags in messages that may be signed 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.




























Aura                     Expires August 6, 2004                [Page 18]


Internet-Draft    Cryptographically Generated Addresses (CGA)    February 2004


Normative References

   [I-D.ietf-send-ndopt]
              Arkko, J., Kempf, J., Sommerfeld, B., Zill, B. and P.
              Nikander, "SEcure Neighbor Discovery (SEND)",
              draft-ietf-send-ndopt-03 (work in progress), January 2003.

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

   [RFC2434]  Narten, T. and H. Alvestrand, "Guidelines for Writing an
              IANA Considerations Section in RFCs", BCP 26, RFC 2434,
              October 1998.

   [PKCS.1.2002]
              RSA Laboratories, "RSA Encryption Standard, Version 2.1",
              Public-Key Cryptography Standard PKCS 1, June 2002.

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













Aura                     Expires August 6, 2004                [Page 19]


Internet-Draft    Cryptographically Generated Addresses (CGA)    February 2004


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.

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












Aura                     Expires August 6, 2004                [Page 20]


Internet-Draft    Cryptographically Generated Addresses (CGA)    February 2004


Author's Address

   Tuomas Aura
   Microsoft Research
   Roger Needham Building
   7 JJ Thomson Avenue
   Cambridge  CB3 0FB
   United Kingdom

   Phone: +44 1223 479708
   EMail: tuomaura@microsoft.com








































Aura                     Expires August 6, 2004                [Page 21]


Internet-Draft    Cryptographically Generated Addresses (CGA)    February 2004


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
   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 64 first bits of the SHA-1 hash value of the above input are
   Hash1=fd4a 5bf6 ffb4 ca6c. We form an interface identifier from this
   by writing Sec=1 into the three leftmost bits and by setting bits 6
   and 7 (the "u" and "g" bits) to zero. The new interface identifier is
   3c4a:5bf6:ffb4:ca6c.




Aura                     Expires August 6, 2004                [Page 22]


Internet-Draft    Cryptographically Generated Addresses (CGA)    February 2004


   Finally, we form the IPv6 address fe80::3c4a:5bf6:ffb4:ca6c. This is
   the new CGA. No address collisions were detected this time.
   (Collisions are very rare.) The CGA Parameters data structure
   associated with the address is the same as the input to Hash1 above.















































Aura                     Expires August 6, 2004                [Page 23]


Internet-Draft    Cryptographically Generated Addresses (CGA)    February 2004


Appendix B. Acknowledgements

   The author gratefully acknowledges the contributions of Jari Arkko,
   Francis DuPont, Pasi Eronen, Christian Huitema, Pekka Nikander,
   Michael Roe, Dave Thaler, and several other participants of the SEND
   working group.













































Aura                     Expires August 6, 2004                [Page 24]


Internet-Draft    Cryptographically Generated Addresses (CGA)    February 2004


Intellectual Property Statement

   The IETF takes no position regarding the validity or scope of any
   intellectual property or other rights that might be claimed to
   pertain to the implementation or use of the technology described in
   this document or the extent to which any license under such rights
   might or might not be available; neither does it represent that it
   has made any effort to identify any such rights. Information on the
   IETF's procedures with respect to rights in standards-track and
   standards-related documentation can be found in BCP-11. Copies of
   claims of rights made available for publication and any assurances of
   licenses to be made available, or the result of an attempt made to
   obtain a general license or permission for the use of such
   proprietary rights by implementors or users of this specification can
   be obtained from the IETF Secretariat.

   The IETF invites any interested party to bring to its attention any
   copyrights, patents or patent applications, or other proprietary
   rights which may cover technology that may be required to practice
   this standard. Please address the information to the IETF Executive
   Director.

   The IETF has been notified of intellectual property rights claimed in
   regard to some or all of the specification contained in this
   document. For more information consult the online list of claimed
   rights.


Full Copyright Statement

   Copyright (C) The Internet Society (2004). All Rights Reserved.

   This document and translations of it may be copied and furnished to
   others, and derivative works that comment on or otherwise explain it
   or assist in its implementation may be prepared, copied, published
   and distributed, in whole or in part, without restriction of any
   kind, provided that the above copyright notice and this paragraph are
   included on all such copies and derivative works. However, this
   document itself may not be modified in any way, such as by removing
   the copyright notice or references to the Internet Society or other
   Internet organizations, except as needed for the purpose of
   developing Internet standards in which case the procedures for
   copyrights defined in the Internet Standards process must be
   followed, or as required to translate it into languages other than
   English.

   The limited permissions granted above are perpetual and will not be
   revoked by the Internet Society or its successors or assignees.



Aura                     Expires August 6, 2004                [Page 25]


Internet-Draft    Cryptographically Generated Addresses (CGA)    February 2004


   This document and the information contained herein is provided on an
   "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
   TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
   BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
   HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
   MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.


Acknowledgment

   Funding for the RFC Editor function is currently provided by the
   Internet Society.







































Aura                     Expires August 6, 2004                [Page 26]


Html markup produced by rfcmarkup 1.129c, available from https://tools.ietf.org/tools/rfcmarkup/