Summary

Butterfly Keys are a novel cryptographic construction that allow a device to request an arbitrary number of certificates, each with different signing keys and each encrypted with a different encryption key, using a request that contains only one verification public key "seed" and one encryption public key "seed" and two “expansion functions.” The expansion functions allow a second party to calculate an arbitrarily long sequence of statistically uncorrelated (as far as an outside observer is concerned) public keys such that only the original device knows the corresponding private keys. Without butterfly keys, the device would have to send a unique verification key and a unique encryption key for each certificate. Butterfly keys reduce upload size, allowing requests to be made when there is only spotty connectivity, reduce the work to be done by the requester to calculate the keys, and smoothen peak requests.

A core principle of PKI implementations is that all private keys should be generated on the device that is going to use them. If private keys are generated off the device (and then installed on it), and if the device appears to misbehave, the device owner can claim that the misbehavior was actually carried out by whoever generated the keys. However, in the original CAMP design, a single device had over 100,000 certificates per year. Generating 100,000 distinct certificate requests would be a significant computational burden, and arguably an unnecessary one given that most vehicles are only in operation for about 5% of the time. Additionally, 100,000 distinct certificate requests would take a long time to upload and, if connections from the onboard equipment (device) to the CA are unreliable, there is a risk that certificate requests would not complete successfully within a single communication session.

The CAMP design thus updated its approach to use butterfly keys to address both these concerns. In the butterfly key approach, the certificate requester only needs to generate a single key pair and include the public key in a single certificate request. The difference from the standard approach is that the requester also creates an expansion function that allows a single public key to be expanded into multiple public keys and a single private key to be expanded into multiple private keys, while ensuring that only someone who knows the original private key will know the expanded private keys (i.e., the device). This reduces the computational burden on the device (it only has to generate one key) and also the size of the upload (reduced to less than 1K bytes). The cost is that the download of certificate responses increases in size.

Preliminaries

i and j Values

1. For pseudonym certificates, the i value used in any certificate is the global i value.
   1. The clock time corresponding to the global i=0 shall be as per Special Cryptographic Primitives in SCMS. 
   2. The increment period for the global i value shall be fixed at 1 week, i.e., 7*24 hours, where hours is the field defined under the type Duration in IEEE 1609.2. 
   3. The j value shall range from 0 to j_max-1. For POC and CV Pilots, j_max for all devices is fixed at 20.
      
2. For identification certificates, the i value used in any certificate is the local i value corresponding to the enrollment certificate used for requesting that identification certificate. 
   1. The clock time corresponding to that local i=0 shall be the value of toBeSigned.validityPeriod.start field of the enrollment certificate. 
   2. The increment period for that local i value shall be the value of toBeSigned.validityPeriod.duration field (minus the overlap period, see PoC Certificate Expiration Timelines, CV Pilot PROD Certificate Expiration Timelines) of the identification certificate. 
   3. For POC and CV Pilots, the j value for all devices is fixed at 0.

Description

Butterfly keys make use of ECDLP as follows. There is an agreed “base point” called G (this is standard practice for elliptic curve cryptography). The device generates two ECC key-pairs (a, A = aG) (seed for the signing keys) and (p, P = pG) (seed for keys used for encrypting the certificates, i.e., encryption keys), and descriptions of two expansion functions f1 (for signing keys) and f2 (for encryption keys). The expansion functions map an integer ι to another integer in a range from 0 to l, the order of the elliptic curve. Functions f1 and f2 are designed to be cryptographically secure, which roughly means that the output looks random so that given two values of {f1(ι), ι} (or, {f2(ι), ι}), a third party cannot tell whether the two values were generated by the same version of f1 (or, f2), or by different versions. The vehicle stores a, p, and descriptions of f1 and f2, and sends A, P, and description of f1 and f2 encrypted to the SCMS. In the CAMP design, the expansion functions are defined as:

1. f1(k, ι) = f1^int(k, ι) mod l, where 
   1. f1^int(k, ι) is the big-endian integer representation of (AES(k, x+1) XOR (x+1)) || (AES(k, x+2) XOR (x+2)) || (AES(k, x+3) XOR (x+3)), 
   2. x+1, x+2, and x+3 are obtained by simply incrementing x by 1 each time, e.g., if x = 01 … 00, then x+1 = 01 … 01, x+2 = 01 … 10, x+3 = 01 … 11, 
   3. 128-bit input x for AES is derived from time period ι = (i, j) as: (0³² || i || j || 0³²). 
2. f2(k, ι) is defined in an identical way as f1(k, ι), except x is derived as: (1³² || i || j || 0³²).

The “description” of f1 and f2 are simply the AES keys ck (for signing keys) and ek (for encryption keys): to generate f1 and f2 the device simply generates 2 AES keys ck and ek, and to send the description of f1 and f2 the device sends ck and ek.

Now the SCMS has the ability to generate an extremely large number of derived points: it can generate

• B_ι = A + f1(ck, ι) * G, with A = aG (signing keys)
• Q_ι = P + f2(ek, ι) * G, with P = pG (encryption keys)

The corresponding private keys will be

• b_ι = a + f1(ck, ι) (signing keys)
• q_ι = p + f2(ek, ι) (encryption keys)

Since the SCMS doesn’t know the original value of a (or, p), it cannot know any of the b_ι (or, q_ι) values, so it can generate an arbitrary number of public keys for which only the vehicle knows the corresponding private keys. Additionally, because the expansion functions are cryptographically secure, anyone who doesn’t know the description of f1 cannot tell whether two different signing public keys belong to the same series {B_ι} or to different series. This means that the RA, described in detail later, can safely use f1 to create an expanded list of signing public keys to send to the CA, and the CA will not be able to tell that the keys belong to the same vehicle.

In the CAMP SCMS, this underlying approach is used as follows. Note: There are a couple of minor technical differences between this description and the CAMP approach – explained after this description, which focuses on the core butterfly key operations and omits optimizations that might obscure the explanation:

• Device generates two 128-bit AES keys ck and ek, for expansion functions of signing keys and encryption keys, respectively, and two “caterpillar” key pairs:
  • (a, A = aG) used for signing, i.e., A to be placed in the certificate
  • (p, P = pG) used for encryption of the certificate

Device sends {ck, ek, A, P} to the RA. Note: ck will define the expansion function for the signing keys and ek will define the expansion function for the encryption keys.

• RA uses ck to generate {B_ι}, the series of “cocoon” signing public keys for the certificate requests, and ek to generate {Q_ι}, the series of cocoon encryption public keys for encrypting the certificate response, pairs each B_ι with the corresponding Q_ι, and sends the pairs {B_ι, Q_ι} to the CA.
• CA does not know which public keys have come from the same device, but RA knows which public keys are in the requests, so CA must further randomize the public keys to hide them from RA. For each request, CA generates a unique random integer c and sets the public key in each certificate to the “butterfly” value (B_ι + cG). CA then uses Q_ι to encrypt the response, which contains:
  • Certificate containing the public key (B_ι + cG)
  • CA’s contribution to the private key, c
• RA sends the encrypted message to the device along with the corresponding ι.
• Device uses ek, p, ι to calculate q_ι. It uses q_ι to decrypt the response and recover the certificate containing the public key (B_ι + cG) and CA’s contribution to the private key, c. It then uses ck, a, ι to calculate b_ι. The private key for the certificate is then:
  • Butterfly private key = b_ι (calculated above) + c (provided by CA)

Device should at this point check that the recovered private key corresponds to the public key certified by the certificate to ensure that it has been sent the correct certificate.

This means that the device has obtained a set of certificates such that:

• Only the device knows the private keys
• RA does not know the public keys in the certificates
• CA cannot tell from the requests alone which requests have come from the same device

Notes:

1. In the CAMP design, there are a couple of differences. First, implicit certificates are used by a device, so the CA’s contribution to the private key is calculated slightly differently; however, the principle is the same, namely that the CA modifies the public key and sends information to the vehicle that allows it to make the corresponding modification to the private key. Moreover, in the table below, butterfly keys process has been summarized for both explicit and implicit certificates. Second, the CA additionally signs (using its private key) the encrypted implicit certificate to prevent a man-in-the-middle (MITM) attack by the RA. To launch the MITM attack, the RA can simply use a different public key of its choice (for which it knows the corresponding private key) in the request to the CA, so that it can decrypt the encrypted response by the CA, view the underlying certificate, and then while responding to the vehicle encrypt the certificate with the right public key.
2. Since the RA knows the public encryption key J_ι, it could in principle create a fake response to the vehicle. This would allow the RA to give a set of known certificates to a target vehicle, allowing the RA to track. However, any fake response will not have been created with the CA private key and so the vehicle can detect this attack and discard the resulting keys.
3. The per-certificate value c generated by the CA is vital in hiding the final certified public key from the RA. If c were a constant, all the certificates would be related to their requests in some known way, and the RA could work out the set of certificates corresponding to a set of certificate requests and track the vehicle. Likewise, if the CA generates c with bad randomness, or with randomness that is known to the RA, then the RA may be able to work out which certificate belongs to which vehicle. (see Random Number Generators under CB2: Types of Cryptographic Algorithms and Approved Random Number Generators for further details on “good randomness.”).
4. Test vectors for butterfly expansion function are available at http://stash.campllc.org/projects/SCMS/repos/crypto-test-vectors/browse/bfkeyexp.txt