Details
Ciphertext Forgery
The Decrypt API in AWS KMS doesn’t require the caller to specify the CMK. This parameter is required only when the ciphertext was encrypted under an asymmetric CMK. Otherwise, AWS KMS uses the metadata that it adds to the ciphertext blob to determine which CMK was used to encrypt the ciphertext.
This leads to the following attack:
- The attacker creates a CMK that has a key policy that allows access from everyone. This requires no prior knowledge about the victim.
- The attacker generates a ciphertext by calling the Encrypt API with their key.
- The attacker intercepts a ciphertext from the victim, and replaces it entirely with their ciphertext.
- The victim successfully decrypts the ciphertext, as if it was encrypted under their own key. The attacker also learns when this happened, the victim’s AWS Account ID, user agent, encryption context, and IP address.
Similar to the information leakage attack, this attack also requires the victim to have an IAM policy that allows them to access the attacker’s CMK.
The AWS Encryption SDKs also succumb to this attack. They don’t specify the CMK when they call the Decrypt API to unwrap the DEK.
Robustness
The AWS Encryption SDKs allow a single ciphertext to be generated for multiple recipients, with each decrypting using a different key. To that end, it wraps the DEK multiple times, each under a different CMK. The wrapped DEKs can be combined to form a single ciphertext which can be sent to multiple recipients who can use their own credentials to decrypt it. It’s reasonable to expect that all recipients should decrypt the ciphertext to an identical plaintext. However, because of the use of AES-GMAC and AES-GCM, it’s possible to create a ciphertext that decrypts to two valid yet different plaintexts for two different users. In other words, the AWS Encryption SDKs are not robust.
The encryption of a message under two CMKs can be summarized as follows:
- A DEK is randomly generated, and two wrapped DEKs are produced by calling the Encrypt API using the two CMKs
- A per-message AES-GCM key (K) is derived using HKDF from the DEK, a randomly generated message ID, and a fixed algorithm ID.
- A header is formed from the wrapped DEKs, the encryption context, and other metadata. A header authentication tag is computed on the header using AES-GMAC with K and a zero IV.
- The message is encrypted using AES-GCM with K, a non-zero IV, and fixed associated additional data. This produces a message authentication tag.
- The ciphertext consists of the header, the header authentication tag, the encrypted message, and the message authentication tag.
(There’s also a self-signed digital signature that is irrelevant to this discussion).
In order to decrypt a ciphertext, the AWS Encryption SDKs loops over the list of wrapped DEKs and returns the first one that it can successfully unwrap. The attacker therefore can wrap a unique DEK for each recipient. Next, the attacker exploits the non-committing property of GMAC to produce two messages that have the same GMAC tag under two different keys. The attacker has to do this twice, one for the header authentication tag and one for the message authentication tag.
Given a data blob B of one 128-bit block B_1, a GMAC tag is computed as follows:
B_1 * H^2 + B_len * H + J
where H and J depends on the key and B_len depends on the length of B.
To find a message that can produce the same tag under two different keys, one
can add append to B a new block B_2 whose value can be deduced by solving
an algebraic equation. That is, we want to find B_2 such that:
B_1 * H^3 + B_2 * H^2 + B_len * H + J = B_1 * H’^3 + B_2 * H’^2 + B_len * H’ + J’
where H’ and J’ are the corresponding H and J of the other key.
B_2 is the only unknown value in this equation, thus it can be computed using
finite field arithmetics of GF(2^128):
B_2 = [B_1 * (H^3+H’^3) + B_len * (H + H’) + J + J’] * (H^2 + H’^2)^-1.
Figure 2: How to find a message that has the same GMAC tag under two different keys.
The overall attack works as follows:
- The attacker generates a random DEK, derives a per-message key K, and encrypts message M with it using AES in counter mode. This generates a ciphertext C.
- The attacker generates another random DEK’, derives a per-message key K’, and performs trial decryption of C until the decrypted message M’ has desirable properties. For example, if the attacker wants the first bit of M’ different from that of M, this process should only take a few attempts.
- The attacker finds a block C* such that the GMAC of C’ = C || C* under K and K’ are identical. Denote this tag C’_tag.
- The attacker wraps DEK and DEK’ under two recipients’ CMK.
- The attacker forms a header H and adds a block H* to the encryption context such that the new H’ has the same authentication tag H’_tag under K and K’.
- The attacker output H’, H’_tag, C’, C’_tag.
This attack is similar to the one discovered in Facebook Messenger.
Acknowledgement
I’m grateful to Jen Barnason for carefully editing this advisory. I will never publish anything without her approval! I want to thank my friend and coworker Sophie “Queen of Hashing” Schmieg for wonderful discussions and for showing me how the arithmetic in GF(2^128) works. I want to thank Jonathan Bannet for asking the questions that led to this work.