A Cryptographically Generated Address (CGA) is an Internet Protocol Version 6 (IPv6) 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 (SEND).
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: modifier: a random 128-bit unsigned integer; subnetPrefix: the 64-bit prefix that defines to which subnet the CGA belongs; collCount: an 8-bit unsigned integer that must be 0, 1, or 2; publicKey: the public key as a DER-encoded ASN.1 structure of the type SubjectPublicKeyInfo; extFields: an optional variable-length field (default length 0).
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 (and including) 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(Sec, subnetPrefix, publicKey, extFields): 2 modifier := random(0x00000000000000000000000000000000, // 16 octets (128 bits) 3 0xffffffffffffffffffffffffffffffff) 4 5 label1: 6 concat := concatenate(modifier, 0x000000000000000000, // 9 zero octets 7 publicKey, extFields) 8 9 digest := SHA1(concat) 10 Hash2 := digest[0:14] // 14*8 = 112 leftmost bits 11 12 if Sec ≠ 0 and Hash2[0:2*Sec] ≠ 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(modifier, subnetPrefix, collCount, 21 publicKey, extFields) 22 23 digest := SHA1(concat) 24 Hash1 := digest[0:8] // 8*8 = 64 leftmost bits 25 26 intID := Hash1 // Hash1 becomes interface identifier... 27 intID[0] := intID[0] binary and 0x1c binary or (Sec << 5) // ...after writing Sec and u/g bits 28 29 CGA := concatenate(subnetPrefix, intID) // concatenate to form the CGA 30 31 if duplicate(CGA): 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 (lines 20 to 24). On line 27, the first three bits are overwritten by the Sec value and the reserved "u" and "g" bits (the seventh and eighth bit) 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 (lines 6 to 15). 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.