Cryptographically Generated Address


A Cryptographically Generated Address is an Internet Protocol Version 6 address that has a host identifier computed from a cryptographic hash function. This procedure is a method for binding a public signature key to an IPv6 address in the Secure Neighbor Discovery Protocol.

Methodology

A Cryptographically Generated Address is formed by replacing the least-significant 64 bits of the 128-bit IPv6 address with the cryptographic hash of the public key of the address owner. The messages are signed with the corresponding private key. Only if the source address and the public key are known can the verifier authenticate the message from that corresponding sender. This method requires no public key infrastructure. Valid CGAs may be generated by any sender, including a potential attacker, but they cannot use any existing CGAs.

Characteristics

A Cryptographically Generated Address is an IPv6 address whose interface identifier has been generated according to the CGA generation method. The interface identifier is formed by the least-significant 64 bits of an IPv6 address and is used to identify the host's network interface on its subnet. The subnet is determined by the most-significant 64 bits, the subnet prefix.
Apart from the public key that is to be bound to the CGA, the CGA generation method takes several other input parameters including the predefined subnet prefix. These parameters, along with other parameters that are generated during the execution of the CGA generation method, form a set of parameters called the CGA Parameters data structure. The complete set of CGA Parameters has to be known in order to be able to verify the corresponding CGA.
The CGA Parameters data structure consists of:
Additionally, a security parameter Sec determines the CGA's strength against brute-force attacks. This is a 3-bit unsigned integer that can have any value from 0 up to 7 and is encoded in the three leftmost bits of the CGA's interface identifier. The higher the value of Sec, the higher the level of security, but also the longer it generally takes to generate a CGA. For convenience, the intermediate Sec values in the pseudocode below are assumed to be stored as 8-bit unsigned integers that cannot have a value greater than 7.

CGA generation method

The following piece of pseudocode represents the CGA generation method, which is used to create a new Cryptographically Generated Address.
1 procedure generateCGA:
2 modifier := random
4
5 label1:
6 concat := concatenate
8
9 digest := SHA1
10 Hash2 := digest // 14*8 = 112 leftmost bits
11
12 if Sec ≠ 0 and Hash2 ≠ 0: // 2*Sec*8 = 16*Sec leftmost bits
13 modifier := modifier + 1
14 goto label1
15 end if
16
17 collCount := 0x00 // 8-bit collision count
18
19 label2:
20 concat := concatenate
22
23 digest := SHA1
24 Hash1 := digest // 8*8 = 64 leftmost bits
25
26 intID := Hash1 // Hash1 becomes interface identifier...
27 intID := intID binary and 0x1c binary or //...after writing Sec and u/g bits
28
29 CGA := concatenate // concatenate to form the CGA
30
31 if duplicate:
32 collCount := collCount + 1
33
34 if collCount = 3:
35 abort
36 end if
37
38 goto label2
39 end if
40
41 return CGA, [modifier, subnetPrefix, collCount, publicKey, extFields
42 end procedure
The CGA's interface identifier is largely formed by Hash1, which is taken from the first 64 bits of the digested CGA Parameters data structure. [On line 27, the first three bits are overwritten by the Sec value and the reserved "u" and "g" bits are set to 0.
The Sec parameter implements a hash extension by enforcing the first 16 times Sec bits of another hash, Hash2, to be 0. This hash is the result of the digested CGA Parameters data structure with subnetPrefix and collCount essentially set to 0. A brute-force search is performed to find a suitable Hash2, incrementing the modifier by 1 each iteration. Because more bits need to be 0 with a higher Sec value, the average time required to perform the search increases exponentially with the value of Sec.
After concatenating the subnet prefix and the generated interface identifier to create the CGA, duplicate address detection may be performed. If the address is already in use, then the collision counter collCount is incremented by 1 and a new interface identifier is generated. Because collCount is not used in calculating Hash2, it is not necessary to search for a new Hash2 when an address collision occurs. For a similar reason, subnetPrefix is not used either so that if the subnet prefix of the address changes but the host's public key does not, then the same modifier could be reused and there is no need to search for a new Hash2.
On line 41 the CGA is returned, along with the CGA Parameters data structure.

CGA verification method

A Cryptographically Generated Address is used to verify that received signed messages were sent by the host to which that address has been assigned. This is done by verifying that the key pair used for signing has been bound to the CGA. Because the authenticity of the public key can be verified this way, there is no need for a public key infrastructure. If the host itself is required to be authenticated as well, however, then the CGA itself needs to be authenticated beforehand since the bound public key cannot be trusted if the address is not trusted in such a case.
The CGA verification method, in which a public key is verified to be bound to a CGA, requires the corresponding CGA Parameters data structure as input and can be implemented as follows.
1 procedure verifyCGA:
2 if collCount > 2 or CGA ≠ subnetPrefix:
3 return false
4 end if
5
6 concat := concatenate
8
9 digest := SHA1
10 Hash1 := digest // 8*8 = 64 leftmost bits
11 Hash1 := Hash1 binary and 0x1c // ignore Sec and u/g bits
12
13 intID := CGA // interface identifier
14 intID := intID binary and 0x1c // ignore Sec and u/g bits
15
16 if Hash1 ≠ intID:
17 return false
18 end if
19
20 Sec := CGA >> 5 // extract Sec from interface identifier
21
22 concat := concatenate
24
25 digest := SHA1
26 Hash2 := digest // 14*8 = 112 leftmost bits
27
28 if Sec ≠ 0 and Hash2 ≠ 0: // 2*Sec*8 = 16*Sec leftmost bits
29 return false
30 end if
31
32 return true // verification succeeded
33 end procedure
The method starts with checking if collCount from the CGA Parameters data structure has a valid value and if subnetPrefix from the same data structure matches the CGA's subnet prefix. This is done for [|security reasons].
From line 6 to 18, Hash1 is calculated from the CGA Parameters data structure and the relevant bits are compared to those of the CGA's interface identifier. In this case, this is done by setting the first three bits and the seventh and eighth bit of both Hash1 and the interface identifier to 0 on lines 11 and 14 for easy comparison.
After extracting Sec from the CGA's interface identifier, Hash2 is calculated and the first 16 times Sec bits of the hash are compared to 0. If all checks turn out well, then the public key has been verified to be bound to that CGA.

Security

In order for an attacker to make a client believe it received a valid message from a certain CGA that isn't owned by the attacker, the attacker must find a hash collision for the relevant bits of Hash1 and Hash2 by performing a brute-force attack. If the attacker finds a set of CGA Parameters that can be used to generate the same CGA as the target CGA, then the attacker can impersonate the host who actually owns the CGA without being detected.
Of the 64 bits of Hash1, only 59 are used in the interface identifier since 5 bits are being overwritten. For a CGA with Sec equal to 0, this means that the cost of finding a set of CGA Parameters that yield the desired 59 bits is approximately . A larger value of Sec, however, increases this cost by a factor of to because the first 16 times Sec bits of Hash2 then become relevant. In the CGA generation process, the cost of generating an address is increased by the same factor depending on the value of Sec, but the cost of using and verifying a CGA remains constant.
Because Sec is not part of the CGA Parameters data structure but of the address itself, an attacker cannot use a Sec value smaller than that of the target address in an attempt to skip the brute-force attack on Hash2. This would namely yield a different CGA from the target CGA since at least one of the three leftmost bits of the interface identifier would not match. If the target Sec value is written to the interface identifier anyway, then Hash2 will be found to lack the required amount of leftmost 0-bits during the verification process.
During the CGA generation process, it is very unlikely that three address collisions occur. If a duplicate address would be detected for the third time, then this would most likely be due to a configuration or implementation error or a denial-of-service attack. For this reason, the number of valid values for collCount is limited to the range from 0 to 2. This parameter must be verified to be in this range during the CGA verification process in order to prevent an attacker from exploiting it and trying all different values without the need to perform another brute-force search for Hash2 each time a different value is tried.
By including the subnet prefix in the digest operation that results in Hash1, it can be prevented that an attacker is able to use a single pre-computed database to attack addresses with different subnet prefixes. A verifier can also be sure that the public key has been bound to this exact address and not possibly to an address with the same interface identifier but a different subnet prefix. Since the CGA specification prescribes to use the subnetPrefix from the CGA Parameters data structure for the digest operations, it must be verified that it matches the subnet prefix of the CGA during the CGA verification process.