ADR: Move platform from RSA to ECC

[biscoe916]

Background

Recently, we've discussed at length how we might improve the performance of the platform, while not compromising security. One of the more obvious levers to pull is to improve the performance of the various cryptographic operations that takes place in the platform - both on the client, as well as on the backend.

RSA is currently the algorithm supported across all of our clients, and backend services. It's used for rewrapping payload keys, validating auth tokens, and, for deployments with DPOP enabled, validating DPOP signatures.

This ADR proposes switching to ECC as it is superior across several dimensions we care about:

RSA vs. ECC Strength and Performance

Security Level (Bits)	RSA Key Size (Bits)	ECC Key Size (Bits)	RSA Performance (Ops/sec)	ECC Performance (Ops/sec)
80	1024	160	700	5,300
112	2048	224	75	1,000
128	3072	256	30	450
192	7680	384	1	50
256	15360	521	0.1	5

Standards and compliance

NIST has approved ECC algorithms as part of their cryptographic standards. ECC is also FIPS 140-2/140-3 compliant.

How ECC "rewrap" will work

Rewrap using elliptic curves will use ECIES (Elliptic Curve Integrated Encryption Scheme), in the same way the NanoTDF specification does. Below is step by step, how a symmetric key is create/derived, and protected.

ECIES is a hybrid encryption scheme, meaning it uses both public-key (asymmetric) and secret-key (symmetric) cryptography. The high-level steps involved in an ECIES fit for our purposes are:

Encryption

1. Retrieve the KAS ECC public key.
2. Generate an ephemeral ECC key pair.
3. Use the ephemeral private key and the KAS public key to derive a shared secret.
4. Derive a payload key (symmetric) from the shared secret.
5. Encrypt the payload using the payload key.
6. Construct the key access object with:
   • Ephemeral public key
   • KAS key ID

Decryption

1. Generate an ECC key pair for the client.
2. Send a rewrap request to KAS, including:
   • Key access object (which includes the ephemeral public key and KAS key ID)
   • Client public key
3. KAS validates the request.
4. KAS extracts the ephemeral public key.
5. KAS uses the ephemeral public key and the KAS ECC private key to derive the shared secret 1.
6. KAS derives the payload key using the shared secret 1.
7. KAS generates an ephemeral ECC key pair.
8. KAS uses the client public key and the KAS ephemeral private key to derive a shared secret 2.
9. KAS derives a session key from the shared secret 2.
10. KAS encrypts the payload key using the session key.

Options

Option 1 - Use existing spec w/ "ec-wrapped" type

We can use the existing spec, and just add a new Key Access Object type - probably ec-wrapped, or something similar.

The ephemeral public key which was used to derive the shared secret would be placed in the wrappedKey field. The problem with this approach is that our SDKs would need to include functionality to inspect the ECC public keys to determine which curve was used. Option 2 proposes using the type field to also specify the curve.

Example

{
  "type": "ec-wrapped",
  "url": "https:\/\/kas.example.com:5000",
  "kid": "NzbLsXh8uDCcd-6MNwXF4W_7noWXFZAfHkxZsRGC9Xs",
  "sid": "AD234EJ0F98ASDFSJ+NZCVSADFI0ERASDF==",
  "protocol": "kas",
  "wrappedKey": "MIGbMBAGByqGSM49AgEGBSuBBAAjA4GGAAQBTJeOqKR1Kpc8SVSf96VeVOISm3OOWqXFBLb14W3R1basXn5QpSe2+AtfZ/xru5AworbY2KaxAzD7nXLsJwLNgsbAKIsz75wOzDrDtjw4wkpEdH1492WKgOPVSzYTrbsjTtHrnLN4Yd1jvBXv+EFMsMEU+wEws=",
  "policyBinding": {
     "alg": "HS256",
     "hash": "ZoJTNW24UGBSuBBAAjA4GGAAQBTJeOqKR1Kpc8SVSf96VeVMhnXIif0mSnqLVCU="
  },
  "encryptedMetadata": "ZoJTNW24UMhnXIif0mSnqLVCU=",
  "tdf_spec_version:": "x.y.z"
}

Option 2 - Use existing spec w/ curve as the KAO type

Same as option one, but we use the type field to specify which curve was used. Probably unnecessary as the curve is encoded into the key.

Example

{
  "type": "ec-wrapped:secp521r1",
  "url": "https:\/\/kas.example.com:5000",
  "kid": "NzbLsXh8uDCcd-6MNwXF4W_7noWXFZAfHkxZsRGC9Xs",
  "sid": "AD234EJ0F98ASDFSJ+NZCVSADFI0ERASDF==",
  "protocol": "kas",
  "wrappedKey": "MIGbMBAGByqGSM49AgEGBSuBBAAjA4GGAAQBTJeOqKR1Kpc8SVSf96VeVOISm3OOWqXFBLb14W3R1basXn5QpSe2+AtfZ/xru5AworbY2KaxAzD7nXLsJwLNgsbAKIsz75wOzDrDtjw4wkpEdH1492WKgOPVSzYTrbsjTtHrnLN4Yd1jvBXv+EFMsMEU+wEws=",
  "policyBinding": {
     "alg": "HS256",
     "hash": "ZoJTNW24UGBSuBBAAjA4GGAAQBTJeOqKR1Kpc8SVSf96VeVMhnXIif0mSnqLVCU="
  },
  "encryptedMetadata": "ZoJTNW24UMhnXIif0mSnqLVCU=",
  "tdf_spec_version:": "x.y.z"
}

Option 3 - Update the spec to more closely resemble NanoTDF's fields

This approach uses the ec-wrapped type, but adds the ephemeralPublicKey field to be more clear that what's being passed to the KAS isn't a wrappedKey exactly, but instead a public key used to derive the shares secret.

Example

{
  "type": "ec-wrapped",
  "url": "https:\/\/kas.example.com:5000",
  "kid": "2",
  "sid": "AD234EJ0F98ASDFSJ+NZCVSADFI0ERASDF==",
  "protocol": "kas",
  "ephemeralPublicKey": "MIGbMBAGByqGSM49AgEGBSuBBAAjA4GGAAQBTJeOqKR1Kpc8SVSf96VeVOISm3OOWqXFBLb14W3R1basXn5QpSe2+AtfZ/xru5AworbY2KaxAzD7nXLsJwLNgsbAKIsz75wOzDrDtjw4wkpEdH1492WKgOPVSzYTrbsjTtHrnLN4Yd1jvBXv+EFMsMEU+wEws=",
  "policyBinding": {
     "alg": "HS256",
     "hash": "ZoJTNW24UGBSuBBAAjA4GGAAQBTJeOqKR1Kpc8SVSf96VeVMhnXIif0mSnqLVCU="
  },
  "encryptedMetadata": "ZoJTNW24UMhnXIif0mSnqLVCU=",
  "tdf_spec_version:": "x.y.z"
}

Option 3 - Update the spec to more closely resemble NanoTDF's fields

This approach uses the ec-wrapped type, but adds the ephemeralPublicKey field to be more clear that what's being passed to the KAS isn't a wrappedKey exactly, but instead a public key used to derive the shares secret.

Example

{
  "type": "ec-wrapped",
  "url": "https:\/\/kas.example.com:5000",
  "kid": "2",
  "sid": "AD234EJ0F98ASDFSJ+NZCVSADFI0ERASDF==",
  "protocol": "kas",
  "ephemeralPublicKey": "MIGbMBAGByqGSM49AgEGBSuBBAAjA4GGAAQBTJeOqKR1Kpc8SVSf96VeVOISm3OOWqXFBLb14W3R1basXn5QpSe2+AtfZ/xru5AworbY2KaxAzD7nXLsJwLNgsbAKIsz75wOzDrDtjw4wkpEdH1492WKgOPVSzYTrbsjTtHrnLN4Yd1jvBXv+EFMsMEU+wEws=",
  "wrappedKey": "MIGbMBAGByqGSM49AgEGBSuBBAAjA4GGws=",
  "policyBinding": {
     "alg": "HS256",
     "hash": "ZoJTNW24UGBSuBBAAjA4GGAAQBTJeOqKR1Kpc8SVSf96VeVMhnXIif0mSnqLVCU="
  },
  "encryptedMetadata": "ZoJTNW24UMhnXIif0mSnqLVCU=",
  "tdf_spec_version:": "x.y.z"
}

[jrschumacher]

~It's worth noting that without knowing the curve, we will be accepting an O(N) cost. I like the idea of requiring the curve, but would use a different character like ec-wrapped:ed25519 for easier parsing.~

Edit: not correct

[biscoe916]

It's worth noting that without knowing the curve, we will be accepting an O(N) cost. I like the idea of requiring the curve, but would use a different character like ec-wrapped:ed25519 for easier parsing.

Yea, good call. I updated option two to reflect your suggestion.

[strantalis]

@biscoe916 Are we wrapping the key in this method? Just thinking we should maybe remove wrapped from type if we aren't actually wrapping the symmetric key anymore in the manifest.

Couple more questions

• Have we thought about introducing an alg field here like what was done in policyBinding?
• What is the impact on this when it comes to key splitting? Do we just derive the symmetric key first then generate splits from that. If this is the case I think thats the inverse of whats currently done in the sdk.

[biscoe916]

Yea, I had a few examples like ec-protected, but dropped them for this doc - figured we'd have the discussion as to what the type string should actually be once we've selected an option.

I also considered adding an alg field, open to discussing it. That would solve the, "where do we put the curve" question.

Regarding splits, you would need to gen an ephemeral key pair, followed by deriving a shared secret, then symmetric key, for every key access object. Then combine for the payload key. That's off the cuff, though. There may be a different/better way.

[jrschumacher]

It's worth noting that without knowing the curve, we will be accepting an O(N) cost. I like the idea of requiring the curve, but would use a different character like ec-wrapped:ed25519 for easier parsing.

We determined that this isn't true. (🏆 to @biscoe916)

[dmihalcik-virtru]

How will this work with kas federation?

[willackerly]

@biscoe916 looks like ECIES flow proposed at the beginning of the ADR looks great. The format of the KAO in option 4 makes sense with that in mind.

Also for KAS purposes, make it explicit that we'll generate 256, 384 and 521 keys by default so that SDKs have max flexibility if thats what we want

[dmihalcik-virtru]

It isn't obvious, but IIUC the first options (1-3) imply a derived key is used for the DEK, while option 4 would use a wrapped key (encapsulated with the ECIES). Is this correct (as Will implies)?

[dmihalcik-virtru]

Also may I suggest an alternate name than ephemeralPublicKey? Like encryptorPublicKey or wrapperPublicKey? Something that implies the intent/meaning of the value

[dmihalcik-virtru]

Can we include the ephemeral key data encoded directly with the wrapped key bytes?

Something like: https://github.com/ecies/go/blob/v2.0.10/ecies.go#L13

[strantalis]

This has been implemented.