biscoe916 commented 4 months ago

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

RSA vs ECC Performance (Operations per Second)

Security Level (bits)	RSA Key Size	ECC Curve Size	RSA Signs/sec	ECC Signs/sec	RSA Verifies/sec	ECC Verifies/sec	RSA KeyGen/sec	ECC KeyGen/sec
80	1024	160	667	1,667	10,000	500	10	1,667
112	2048	224	143	1,250	5,000	357	1.25	1,250
128	3072	256	67	1,000	3,333	312	0.5	1,000
192	7680	384	10	667	1,538	200	0.125	667
256	15360	521	2.5	500	833	154	0.05	500

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

Retrieve the KAS ECC public key.
Generate an ephemeral ECC key pair.
Use the ephemeral private key and the KAS public key to derive a shared secret.
Derive wrapping key from shared secret
Generate random payload key
Encrypt the payload using the payload key.
Encrypt the payload key using wrapping key.
Construct the key access object with:
- Ephemeral public key
- Wrapped Key
- KAS key ID

Decryption

Generate an ECC key pair for the client.
Send a rewrap request to KAS, including:
- Key access object (which includes the ephemeral public key and KAS key ID)
- Client public key
KAS validates the request.
KAS extracts the ephemeral public key.
KAS uses the ephemeral public key and the KAS ECC private key to derive the shared secret 1.
KAS derives the wrapping key using the shared secret 1.
KAS decrypts wrapped key using the wrapping key
KAS generates an ephemeral ECC key pair.
KAS uses the client public key and the KAS ephemeral private key to derive a shared secret 2.
KAS derives a session key from the shared secret 2.
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 4 - 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 commented 4 months ago

~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 commented 4 months ago

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 commented 4 months ago

@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 commented 4 months ago

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 commented 4 months ago

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 commented 3 months ago

How will this work with kas federation?

willackerly commented 1 month ago

@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

opentdf / platform

ADR: Move platform from RSA to ECC #1196

Background

RSA vs. ECC Strength and Performance

RSA vs ECC Performance (Operations per Second)

Standards and compliance

How ECC "rewrap" will work

Encryption

Decryption

Options

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

Example

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

Example

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

Example

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

Example