AWS KMS keyring encrypt behavior is incorrect

[mattsb42-aws]

Intent

When a user configures a KMS keyring with key IDs, they are stating an intent that they need each of those CMKs to be able to independently decrypt the resulting encrypted message.

For example, if I configure a KMS keyring with CMKs A, B, and C and use that keyring to encrypt a message, then I expect three things to be true:

1. CMK A can decrypt the encrypted message.
2. CMK B can decrypt the encrypted message.
3. CMK C can decrypt the encrypted message.

If any of these are not true of the resulting encrypted message, then the keyring has failed to honor my intent.

The key IDs that I provide to the keyring are the CMKs that I want the keyring to use.

Separate from the statement of what CMKs I want the keyring to use, I can also provide a client supplier. The client supplier provides the KMS client that the keyring needs in order to interact with each CMK.

It is important to note, however, that the client supplier does NOT describe my intent for what CMKs I want to use. It instead describes my intent for how and where I want to talk to KMS.

Put another way, the key ID list is my expressed intent of what the KMS keyring needs to do while the client supplier's behavior is my expressed intent of how the KMS keyring needs to do that.

Encrypt vs Decrypt

The intent of the AWS Encryption SDK framework on decrypt is very different than the intent on encrypt.

On encrypt, the caller describes their intent for the requirements to decrypt the resulting message.

On decrypt, the caller provides resources that attempt to do that decryption.

This is a fundamentally asymmetric relationship with very different implications. If we encounter a problem on encrypt, we cannot fully honor the decryption requirements and so we MUST stop. If we encounter a problem on decrypt, then within the bounds of the keyring responsibility all we know is that we have not yet located a resource that satisfies those decryption requirements.

Requirements

This intent and behavior can be reduced to the following two requirements:

1. On encrypt, if any configured CMK cannot be used, that is an error and encryption MUST halt.
2. On decrypt, the keyring will never halt decryption because of a failure to decrypt.

The Problem

In the KMS keyring specification, when discussing the generator CMK, we state[1]:

If the client supplier does not provide any client for the given region for this KMS GenerateDataKey call, OnEncrypt MUST NOT modify the encryption materials
and MUST fail.

In short: if the generator CMK fails for any reason then the OnEncrypt call MUST fail.

However, when discussing the additional CMKs, we state[2]:

If the client supplier does not provide any client for the given region for this Encrypt call, OnEncrypt MUST skip that particular CMK.

This is a problem for two reasons.

1. If the client supplier fails to supply a client for a CMK, the resulting encrypted message will not honor the intent that I described in my initial listing of CMKs.
2. The client supplier is overriding my intent of which CMKs to use.

For example, if I configure a KMS keyring with CMKs A, B, and C and use that keyring to encrypt a message and my client supplier supplies clients for CMKS A and B but not for C, then the following are true:

1. CMK A can decrypt the encrypted message.
2. CMK B can decrypt the encrypted message.
3. CMK C CANNOT decrypt the encrypted message.

Importantly, I have no idea that this just happened.

If I want to make sure that the keyring actually used all of the CMKs that I asked it to, I now need to parse the keyring trace to determine what CMKs the keyring actually used.

This is unnecessary additional effort that is being forced on me to verify that the keyring did what I told it to do.

Why is this not a problem on decrypt?

In the description of OnDecrypt, the KMS keyring spec states:

If the client supplier does not provide any client for the given region for this Decrypt call, OnDecrypt MUST skip that particular encrypted data key.

As described in Encrypt vs Decrypt, this is exactly the behavior that we need on decrypt.

The Current State

The C implementation[3] matches the behavior described in Intent, which is not compatible with the spec.

The Javascript implementation[4] matches the behavior currently described in the spec, which is not compatible with the behavior described in Intent.

The Java[5] and Python[6] implementations match the behavior described in Intent, but neither of those is published yet.

[1] https://github.com/awslabs/aws-encryption-sdk-specification/blame/master/framework/kms-keyring.md#L164-L169
[2] https://github.com/awslabs/aws-encryption-sdk-specification/blame/master/framework/kms-keyring.md#L215
[3] https://github.com/aws/aws-encryption-sdk-c/blob/5ae44a1b8be21248a0917fbc995d48cbfe8b2590/aws-encryption-sdk-cpp/source/kms_keyring.cpp#L260-L267
[4] https://github.com/aws/aws-encryption-sdk-javascript/blob/523b61dcd9bc06cc1b2828ad36c892fa9744433d/modules/kms-keyring/src/kms_keyring.ts#L148-L149
[5] https://github.com/aws/aws-encryption-sdk-java/blob/20557289c6e1e3483d501c96362e8fbfa1fc3527/src/main/java/com/amazonaws/encryptionsdk/kms/AwsKmsDataKeyEncryptionDao.java#L102-L111
[6] https://github.com/aws/aws-encryption-sdk-python/blob/04b5f9442521ea2e5a2649b8007779aacbd41469/src/aws_encryption_sdk/keyrings/aws_kms/__init__.py#L326