ACryptographically Generated Address(CGA) is anInternet Protocol Version 6(IPv6) address that has a host identifier computed from acryptographic hash function.[1]This procedure is a method for binding apublic signature keyto anIPv6 addressin theSecure Neighbor Discovery Protocol(SEND).[2]
Characteristics
editA 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-bitunsignedinteger;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 aDER-encodedASN.1structure of the type SubjectPublicKeyInfo;extFields:an optional variable-length field (default length 0).
Additionally, a security parameterSecdetermines the CGA's strength againstbrute-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 ofSec,the higher the level of security, but also the longer it generally takes to generate a CGA. For convenience, the intermediateSecvalues 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
editThe following piece of pseudocode represents the CGA generation method, which is used to create a new Cryptographically Generated Address.
1proceduregenerateCGA(Sec,subnetPrefix,publicKey,extFields): 2modifier:= random(0x00000000000000000000000000000000, // 16 octets (128 bits) 3 0xffffffffffffffffffffffffffffffff) 4 5label1: 6concat:= concatenate(modifier,0x000000000000000000, // 9 zero octets 7publicKey,extFields) 8 9digest:= SHA1(concat) 10Hash2:=digest[0:14] // 14*8 = 112 leftmost bits 11 12ifSec≠ 0andHash2[0:2*Sec] ≠ 0: // 2*Sec*8 = 16*Sec leftmost bits 13modifier:=modifier+ 1 14gotolabel1 15end if 16 17collCount:= 0x00 // 8-bit collision count 18 19label2: 20concat:= concatenate(modifier,subnetPrefix,collCount, 21publicKey,extFields) 22 23digest:= SHA1(concat) 24Hash1:=digest[0:8] // 8*8 = 64 leftmost bits 25 26intID:=Hash1// Hash1 becomes interface identifier... 27intID[0]:=intID[0]binary and0x1cbinary or(Sec<< 5) //...after writing Sec and u/g bits 28 29CGA:= concatenate(subnetPrefix,intID) // concatenate to form the CGA 30 31ifduplicate(CGA): 32collCount:=collCount+ 1 33 34ifcollCount= 3: 35abort 36end if 37 38gotolabel2 39end if 40 41return[CGA,[modifier,subnetPrefix,collCount,publicKey,extFields]] 42end procedure
The CGA's interface identifier is largely formed byHash1,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 theSecvalue and the reserved "u" and "g" bits (the seventh and eighth bit) are set to 0.
TheSecparameter implements a hash extension by enforcing the first 16 timesSecbits of another hash,Hash2,to be 0. This hash is the result of the digested CGA Parameters data structure withsubnetPrefixandcollCountessentially set to 0. Abrute-force searchis performed to find a suitableHash2,incrementing themodifierby 1 each iteration (lines 6 to 15). Because more bits need to be 0 with a higherSecvalue, the average time required to perform the search increases exponentially with the value ofSec.
After concatenating the subnet prefix and the generated interface identifier to create the CGA,duplicate address detectionmay be performed. If the address is already in use, then the collision countercollCountis incremented by 1 and a new interface identifier is generated (lines 20 to 39). BecausecollCountis not used in calculatingHash2,it is not necessary to search for a newHash2when an address collision occurs. For a similar reason,subnetPrefixis 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 newHash2.
On line 41 the CGA is returned, along with the CGA Parameters data structure.
CGA verification method
editA 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 (assuming it has not been verified by other methods than CGA).
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.
1procedureverifyCGA(CGA,[modifier,subnetPrefix,collCount,publicKey,extFields]): 2ifcollCount> 2orCGA[0:8] ≠subnetPrefix: 3returnfalse 4end if 5 6concat:= concatenate(modifier,subnetPrefix,collCount, 7publicKey,extFields) 8 9digest:= SHA1(concat) 10Hash1:=digest[0:8] // 8*8 = 64 leftmost bits 11Hash1[0]:=Hash1[0]binary and0x1c // ignore Sec and u/g bits 12 13intID:=CGA[8:16] // interface identifier (64 rightmost bits) 14intID[0]:=intID[0]binary and0x1c // ignore Sec and u/g bits 15 16ifHash1≠intID: 17returnfalse 18end if 19 20Sec:=CGA[8] >> 5 // extract Sec from interface identifier 21 22concat:= concatenate(modifier,0x000000000000000000, // 9 zero octets 23publicKey,extFields) 24 25digest:= SHA1(concat) 26Hash2:=digest[0:14] // 14*8 = 112 leftmost bits 27 28ifSec≠ 0andHash2[0:2*Sec] ≠ 0: // 2*Sec*8 = 16*Sec leftmost bits 29returnfalse 30end if 31 32returntrue // verification succeeded 33end procedure
The method starts with checking ifcollCountfrom the CGA Parameters data structure has a valid value and ifsubnetPrefixfrom the same data structure matches the CGA's subnet prefix (on line 2). This is done forsecurity reasons.
From line 6 to 18,Hash1is calculated from the CGA Parameters data structure (which includes the public key and the subnet prefix) 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 (Sec) and the seventh and eighth bit ( "u" and "g" bits) of bothHash1and the interface identifier to 0 on lines 11 and 14 for easy comparison.
After extractingSecfrom the CGA's interface identifier,Hash2is calculated and the first 16 timesSecbits of the hash are compared to 0 (lines 22 to 30). If all checks turn out well, then the public key has been verified to be bound to (i.e. to be valid for) that CGA.
Security
editIn order for anattackerto make aclientbelieve it received a valid message from a certain CGA that isn't owned by the attacker, the attacker must find ahash collisionfor the relevant bits ofHash1andHash2by performing abrute-force attack.If the attacker finds a set of CGA Parameters (including a public key for which the attacker knows the private key) 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 (except perhaps when the client has contacted the host before and notices that the public key has changed but the CGA has not).
Of the 64 bits ofHash1,only 59 are used in the interface identifier since 5 bits are being overwritten. For a CGA withSecequal to 0, this means that the cost of finding a set of CGA Parameters that yield the desired 59 bits is approximately(inbig O notation). A larger value ofSec,however, increases this cost by a factor oftobecause the first 16 timesSecbits ofHash2then become relevant (i.e. it implements a hash extension by demanding those bits to be equal to 0). In the CGA generation process, the cost of generating an address is increased by the same factor depending on the value ofSec,but the cost of using and verifying a CGA remains constant.
BecauseSecis not part of the CGA Parameters data structure but of the address itself, an attacker cannot use aSecvalue smaller than that of the target address (like 0) in an attempt to skip (or scale down) the brute-force attack onHash2.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 targetSecvalue is written to the interface identifier anyway, thenHash2will (almost certainly) 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 adenial-of-service attack.For this reason, the number of valid values forcollCountis 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 forHash2each time a different value is tried.
By including the subnet prefix in the digest operation that results inHash1,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 thesubnetPrefixfrom 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.