In June 2023, Amazon Web Services launched a developer preview of the new Database Encryption SDK in Java for DynamoDB (DB-ESDK for short).

The DB-ESDK is the successor to the DynamoDB Encryption Client (DDBEC) for Java and provides a lot of cool improvements and features, such as searchable encryption through Beacons.

While most of the cool and interesting parts of the DB-ESDK can be found in the User Guide, there are some subtle aspects that you will only discover from reading the source code or talking with the people who designed the cryptography the new SDK uses.

Fortunately for this blog, I was the security engineer responsible for designing the new message format used by the DB-ESDK in 2021.

The final product you see online today is a significant improvement upon my original vision, thanks to the hard work and diligence of the rest of the AWS Crypto Tools team and the cryptographers at Amazon, so please do not ascribe the credit for any of these design decisions solely to me.

As a supplement to the user guide and specification, I’d like to highlight some of the decisions we made and how they benefit anyone who uses the AWS Database Encryption SDK.

But first, a quick disclaimer:

This blog post is the sole opinion of some guy named Scott and does not represent the views or opinions of any company or its employees, least of all Amazon.

Like most humans, Scott is often wrong or mistaken about lots of things. This blog post is provided for educational and entertainment purposes, and should not be taken as an official source for anything except Scott’s personal opinion about cryptography nerd topics.

Seriously. This is just for fun, because crypto is cool.

Contents

1. What is the AWS Database Encryption SDK (DB-ESDK)?
   • Why Use Client-Side Encryption?
2. Design Tenets for the DB-ESDK Message Format
3. Fast Key Derivation
   • Is This Approach Secure?
4. Seamless Schema Migrations
5. Multi-tenancy Support Out-of-the-Box
6. Group Message Agreement

What is the AWS Database Encryption SDK (DB-ESDK)?

The DB-ESDK is an open source Software Development Kit (SDK) that provides client-side encryption for working with database software.

The SDK in question specifically integrates client-side encryption with Amazon DynamoDB. There may be other databases in scope in the future. I have no specific knowledge about their plans or roadmaps.

Why Use Client-Side Encryption?

There’s a more general answer to this question in the AWS documentation, in the context of S3, but the main benefits of client-side encryption are:

1. The data is encrypted before DynamoDB ever sees it, which eliminates some hypothetical data exposure risks.
2. You can get multi-tenancy within one table by using client-side encryption with per-customer keys.

DynamoDB does utilize server-side encryption, but the main reasons to use server-side encryption are to protect against hard drive theft and meet compliance requirements. That isn’t a limitation of DynamoDB or AWS, but of encrypting data-at-rest in general.

With server-side encryption, any running service that an attacker manages to access will necessarily have access to the plaintext data. Whether that’s an acceptable risk for you is determined by your threat model, I have no way of knowing as I write this.

If server-side encryption is not sufficient for your needs, client-side encryption may be worth considering, since it limits the amount of data exposed to the service. Keep in mind that even client-side encryption isn’t a panacea for all threats and attacks, and that the endpoint that can decrypt the data is still a valuable target.

Design Tenets for the DB-ESDK Message Format

This is not an exhaustive nor official list of the design tenets that went into the DB-ESDK. I’m reciting this from memory while in a hotel room in Las Vegas for DEFCON with a mild case of insomnia.

1. Minimize In-Band Protocol Negotiation
   There are (as of the developer preview) two possible algorithm suites acceptable by the DB-ESDK: One with an ECDSA signature, and one without.
   
   The developers do not allow free-form algorithm choices to be specified in an encrypted payload. Instead, if new algorithms need to be supported, additional Format Versions and/or Format Flavors will be specified; and the algorithms for these specified configurations will be reviewed by experts before they’re shipped.
   
   This tenet was motivated by my years of breaking cryptography code and designing PASETO as a secure alternative to JWT.
2. Avoid the Cryptographic Doom Principle
   When decoding a payload, you must verify a signature and/or a message authentication code before you ever attempt decryption.
   
   Even better: Only support authenticated encryption with additional data (AEAD) encryption modes.
3. The Path to a Node in a Structured Document Must Be Authenticated
   Whether you’re working with NoSQL or SQL databases, and whether those SQL databases are row-based or columnar, the fully qualified path to a particular piece of encrypted data is a part of its identity. An attacker must not be able to mutate it freely.
   
   Caveat: Users may be allowed to mutate it if they must, but doing so should force a decryption and re-encryption.
   
   As a consequence of this tenet, the AAD (additional associated data) parameter for each DynamoDB attribute in an item must be a fully canonicalized path for the attribute within the record. Additionally, each attribute must use a different key.
4. Domain Separate Every Use of Hash Functions
   This one’s pretty straightforward to cryptographers. Essentially, you want to minimize the risk of cross-protocol interaction by massively deviating the internal states of hash functions whose output will have different purposes.
   
   This generally reduces the risk of a cross-protocol attack to the probability of a collision, which is quantifiable as the birthday bound of the hash function in question.
5. Liberate Customers From Schemas
   The whole point of NoSQL is to offer schema-free databases, which has advantages for rapid prototyping and adapting to changing requirements. This is so powerful that even some relational databases have added JSON field support.
   
   Why, then, would an Encryption SDK intended for a NoSQL database require you to conform to one true schema over the lifetime of your database table?
   
   It seems rather silly, doesn’t it?
   
   However, supporting the desired flexibility securely is nontrivial, so it’s tempting to implicitly enforce schema-rigidity into a cryptographic design. See below for how we solved this problem.

I’m not going to talk about the Beacons feature or searchable encryption in general in this post, because that warrants an entirely separate discussion; but needless to say, it has its own set of considerations.

Fast Key Derivation

In Tenets 2 and 3 from my list above, I described how each field uses authenticated encryption with a distinct key, and that the fully quantified path to the node is included in the AAD parameter.

This sounds great from a provable security perspective, but what about throughput and performance?

An early design used HKDF-HMAC-SHA384 to independently derive keys for each attribute. This proved to be unacceptably slow once you began encrypting, say, 1000 or so attributes on a given DynamoDB item.

After a lot of analysis, we settled on a solution that is equal parts innovative and conservative from a security perspective:

1. Use HKDF, once, to derive an intermediary key.
2. Use AES-CTR with the intermediary key to obtain a long pseudorandom sequence of bytes, which can be chopped up into a 256-bit per-attribute key and 96-bit IV for each attribute.
   
   Bonus: This means we also don’t need to store an IV in the ciphertext, which saves on bandwidth.

To calculate the key for a given attribute, you need to know the following information:

1. The intermediary key
2. The canonical ordering of all of the attributes in a DynamoDB item, based on their fully qualified path
3. The index of the attribute within said canonical ordering in question

Then you simply calculate the AES-CTR keystream for 44 bytes (the actual AES-CTR nonce is offset by multiples of 3 AES blocks), and Bob’s your uncle.

There is a limitation to this approach: You must not derive more than about 2^30.4 keys and IVs using this technique. The present limits on DynamoDB’s item size prevent anyone from ever reaching threshold, but it’s worth keeping in mind for other designs.

This is calculated by dividing 2^32 (the number of AES blocks that can be iterated over before an attacker can begin to distinguish successive blocks from a random oracle) by 3 (the number of AES blocks we burn per key/IV).

Is This Approach Secure?

The underlying design of Counter Mode as a Stream Cipher draws inspiration from the One-Time Pad. As long as the output is indistinguishable from randomness, it is secure.

When using AES-CTR to encrypt data (as AES-GCM does under-the-hood), the keystream is XORed with the plaintext, which may create collision blocks–even if AES itself is a block cipher which acts like a pseudorandom permutation (and therefore does not collide). AES-GCM lets you encrypt up to 2^32 messages of length 2^36 – 32 bytes each.

Back of the envelope math? Encrypting this way tolerates up to about 2^64 AES blocks just fine. However, we’re using the AES-CTR output directly, so we must be more cautious than that.

According to NIST SP800-90A, AES-CTR_DRBG is secure for up to 2^48 requests (up to at most 2^19 bits, or 2^16 bytes, each). This assumes a 128-bit IV.

The DB-ESDK is using AES-CTR in a similar way (deterministic random bit generation), but for deriving intermediary keys. This is likely the closest analogue to our usage, but we can afford to be even more careful.

NIST SP800-108‘s KDF in Counter Mode is focused on key derivation specifically; from which we borrowed their IV construction (96 bits of label + 32 bits of block counter). However, they’re assuming AES-CMAC for each block rather than AES-ECB. This involves more AES invocations than is necessary here, because it’s aiming to meet the KDF security definition.

If we treat the first 96 bits of the IV as a constant value that must not be changed, this only allows a maximum 2^32 successive AES blocks to be used, due to a more conservative security model than AES-CTR_DRBG requires. Given the other analogous ways AES can be used, this feels sufficiently conservative for our use case.

If there was a weakness in AES-CTR that affects the quality of its keystream in a way that makes what we’re doing dangerous, then AES-CTR wouldn’t be suitable as a stream cipher for AEAD constructions; such as AES-GCM.

Furthermore, there is a traditional KDF (HKDF-HMAC-SHA384, which meets the KDF Security Definition) feeding directly into our usage of AES-CTR.

We’re just using AES-CTR to expand a single KDF-secure key into a sufficiently long stream of random bytes. This is what the algorithm excels at.

In short: It’s a little clever, but not in a way that’s dangerous or weird to the cryptography literature, so I predict most auditors will conclude it’s boring cryptography.

Seamless Schema Migration

As stated in Tenet #4, it would be silly to expect software talking to a NoSQL database to hard-code one true schema forever for each database table. It flies in the face of NoSQL’s entire value proposition.

Consequently, it would be wonderful if the DB-ESDK was schema-free too. It’s not trivial or straightforward to design a secure message format that is schema-free yet resistant to protocol-level attacks based on in-band negotiation (see: Tenet #1), but it is possible.

Fortunately, the previous section lined up the dominoes to make it happen.

In order for our Fast Key Derivation to work, we needed to define some mechanism for canonical field ordering.

Given that any attribute on a DynamoDB item may be signed, encrypted-and-signed, or not protected at all, having a stable canonical field order allows a simple solution.

1. Encode, into the header, a legend of which authenticated fields are encrypted, based on their canonical order. Since this header is always authenticated, an attacker cannot mutate this legend without possessing the correct key.
   
   When you encrypt a record, it will use today’s “schema” to define which fields are encrypted in the legend. If you change the schema tomorrow then try to decrypt old records, it will just work.
   
   Note: Per Tenet #2, we always verify a MAC and/or signature before decrypting, and the legend is in the header which is covered by the MAC and optional signature.
2. Allow users to specify a runtime schema of which fields are authenticated, and which are freeform (i.e. not protected by MACs or signatures).
   
   This authentication schema is not currently encoded in the structured encryption message format (although it’s probably safe to do so).

The reason for permitting unauthenticated fields is to enable workflows that add additional, but not sensitive, attributes to existing encrypted records (e.g. adding beacons for searchable encryption).

It’s not as cool as the cryptography that went into key derivation, but it will make your life easier and it lives up to the spirit of NoSQL.

Multi-tenancy Support Out-of-the-Box

Not only does the DB-ESDK support multi-tenancy (wherein each of your customers has their own key, even if you store all of your data in a single DynamoDB table), it also prevents Confused Deputy attacks and offers Key Commitment; as I’ve written about previously.

To prevent Confused Deputy attacks, the DB-ESDK uses two mechanisms:

1. Encryption Context, which can store metadata about the customer (such as a serial number or KMS Key ID)
2. Header Commitment, which uses a cryptographically secure hash function to authenticate the header with a distinct commitment key

The really cool part about this feature is that it didn’t require special considerations to explicitly add support for; its status as “obviously a secure way to use this SDK” fell naturally out of the previous decisions we already made.

Group Message Agreement

As with the AWS Encryption SDK, the DB-ESDK uses envelope encryption. Each message has a secret 256-bit key at the top of the key hierarchy (which does not need to be unique), a public 256-bit message ID (which must be unique, but is sufficiently large that you can just generate this randomly and never encounter a collision), and one or more key providers that wrap the key.

If you only have one key provider (and thus, one encrypted data key stored in the header), only access to the key will allow you to alter the encrypted or authenticated data contained within. This is obvious.

What’s more interesting is the use case where you wrap the 256-bit message key to multiple key providers. One reason why you may want to do this is disaster recovery and data durability: If a region ever goes down, you can decrypt your data in another region.

When you have multiple agents that can decrypt the same encrypted record, if the authentication key is the same for all parties, then there is a potential for one agent to alter the message without alerting the others that a change has occurred. This is often unexpected, and occasionally undesirable.

There are two ways you can prevent this:

1. Require an ECDSA signature, using an ephemeral keypair, and store the public key in the header. If another node tries to mutate then reauthenticate the message, they will need to generate a new ECDSA keypair; which tips the other agents off that the message has mutated. The AWS Encryption SDK has offered this for years.
   
   However, this requires asymmetric cryptography, which is slower than symmetric cryptography.
2. When encrypting a record, derive a different authentication key and Message Authentication Code per agent, then store all of the MACs in the footer. Each agent can only verify the MAC corresponding to their position in the Encrypted Data Keys field in the header, but all of them can verify the ECDSA signature (if applicable), which also doesn’t need to use ephemeral keypairs (i.e. you can have a long-lived key if appropriate for your threat model).

There are clear benefits of approach two, especially in CPU-bounded workloads where an ECDSA signature is unacceptable. Thus, that is what the DB-ESDK implements.

Closing Thoughts

The AWS Database Encryption SDK (DB-ESDK) is really cool–speaking from my totally biased perspective–and does a lot of carefully-considered and well-engineered things to securely offer the best customer experience that a cryptography library could hope to.

This coolness is in addition to searchable encryption, which any encrypted database (that doesn’t recklessly rely on deterministic encryption) needs to offer in order to be useful.

This is on top of the fact that the DB-ESDK was written in Dafny, a verification-aware programming language. There’s a lot of cool stuff coming out of the Automated Reasoning Group; building with Dafny is one of the cooler ideas.

But most importantly: If you’re curious about using the DB-ESDK in your project, you don’t need to know any of the details in this blog post. That’s most likely why they didn’t land anywhere near the official documentation: Only security nerds will need to care about how they’re implemented, or why they were designed that way. Perhaps your favorite security nerds will appreciate the insight?