Key hierarchies and combinations

Creating this for a space to discuss a feature request: https://github.com/aws/aws-encryption-sdk-python/issues/201

# Original Request

The original request was for a mechanism to support cryptographic deletion of data based on specific encryption context values.

There are two general use cases that were described:

1. Each encryption context contains a single identifiable encryption context value.
* All encrypted messages containing identifiable value **X** can be cryptographically deleted at once by operating on some value for **X**.
* ex:
* Each encryption context contains a user ID.
* All messages containing user ID `user-id-001` can be cryptographically deleted when user `user-id-001` makes a request.
1. Each encryption context can contain *one or more* identifiable encryption context values.
* All encrypted messages containing *any* identifiable values in their encryption context can be cryptographically deleted by operating on *any* associated identifiable value.
* ex:
* Each encryption context can contain multiple values, such as user ID and application ID.
* All messages containing user ID `user-id-001` can be cryptographically deleted when user `user-id-001` makes a request.
* All messages containing application ID `app-id-001` can be cryptographically deleted when the owner of application `app-id-001` makes a request.

# Proposed Solution 1

One possible solution to these problems would be to define a key hierarchy that would allow intermediate key selection based on encryption context, potentially combining multiple intermediate keys, with the end goal of keeping the root of trust in a single master key but enabling cryptographic deletion of data with specific encryption contexts.

I think the described behavior breaks down into a few necessary features that would create separate layers to this:

1. Tooling to define a key hierarchy and store intermediate keys.
1. A key selection mechanism to provide extension points for how to select the correct key.
1. A mechanism to select more than one key and combine them.

I think that layer 1 alone would be useful, as would layers 1+2, in addition to 1+2+3 doing what you described.

## 1.1 Key Hierarchy

In addition to use cases like that described in the original feature request, I think that tooling to manage a key hierarchy could also provide a nice alternative to data key caching that would still allow a reduction in call frequency to an upstream keyring. I'm envisioning something, probably a CMM, that behaves in a similar way to the KMS re-authorization flow in DynamoDB server-side encryption[1]. This would enable a reduction in KMS call frequency while still enabling each encrypted message to have a unique data key.

A naive solution to this could be to simply have the encrypted data key be an AWS Encryption SDK encrypted message, but I do not think that this would scale well, especially once we introduce the concept of multiple intermediate keys, either as separate layers or as required combinations.

## 1.2 Intermediate Key Selection

A key selection extension point would enable users to define custom criteria for locating an intermediate key. This could be based on the encryption context, the keyring trace, or anything else in the encryption/decryption materials request.

## 1.3 Multiple Intermediate Keys

I really like the idea outlined in the original feature request of a single encrypted message requiring multiple, independent, intermediate keys.

There are two basic ways that I could see these multiple keys being used: either nested within each other with a chain of key hierarchy keyrings, or in parallel with a single keyring having intermediate key selection criteria that can result in multiple keys and those keys being combined in some way (HKDF? XOR?) to arrive at the actual intermediate key material.

The parallel approach has some benefits over the nested approach, such as reduced encrypted data key size and simpler configuration.

I think that "both" is probably the right answer here.

[1] https://docs.aws.amazon.com/kms/latest/developerguide/services-dynamodb.html#dynamodb-encrypt

Start with the linked original request and this issue's proposed layers: key hierarchy tooling, intermediate key selection, and combining multiple keys. No implementation files, tests, entry points, or acceptance criteria are identified, so the work first requires settling the design and defining what completion means.

Written by the indexing model from the issue text.