Authors: Thai āthaidnā Duong
The following security vulnerabilities was discovered and reported to Amazon, affecting AWS KMS and all versions of AWS Encryption SDKs prior to version 2.0.0:
The first two bugs are somewhat surprising because they show that the ciphertext format can lead to vulnerabilities. These bugs (and the infamous alg: āNoneā bugs in JWT) belong to a class of vulnerabilities called in-band protocol negotiation. This is the second time weāve found in-band protocol negotiation vulnerabilities in AWS cryptography libraries; see this bug in S3 Crypto SDK discovered by my colleague Sophie Schmieg.
In JWT and S3 SDK the culprit is the algorithm fieldāhere it is the key ID. Because the key ID is used to determine which decryption key to use, it canāt be meaningfully authenticated despite being under the attackerās control. If the key ID is a URL indicating where to fetch the key, the attacker can replace it with their own URL, and learn side-channel information such as the timing and machines on which the decryption happens (this can also lead to SSRF issues, but thatās another topic for another day).
In AWS, the key ID is a unique Amazon Resource Name. If an attacker were to capture a ciphertext from a user and replace its key ID with their own, the victimās AWS account ID, encryption context, user agent, and IP address would be logged to the attackerās AWS account whenever the victim attempted to decrypt the modified ciphertext.
The last bug shows that the non-committing property of AES-GCM (and other AEAD ciphers such as AES-GCM-SIV or (X)ChaCha20Poly1305) is especially problematic in multi-recipient settings. These ciphers have a property that can cause nonidentical plaintexts when decrypting a single ciphertext with two different keys! For example, you can send a single encrypted email to Alice and Bob which, upon decryption, reads āattackā to Alice and āretreatā to Bob. The AWS Encryption SDKs are vulnerable to this attack because they allow a single ciphertext to be generated for multiple recipients, with each decrypting using a different key. I believe this kind of problem is prevalent. I briefly looked at JWE and I think it is vulnerable.
Amazon has fixed these bugs in release 2.0.0 of the SDKs. A new major version was required because, unfortunately, the fix for the last bug requires a breaking change from earlier versions. All users are recommended to upgrade. More details about Amazonās mitigations can be found in their announcement.
Weāre collaborating with Shay Gueron on a paper regarding fast committing AEADs.
The Encrypt API in AWS KMS encrypts plaintext into ciphertext by using a customer master key (CMK). The ciphertext format is undocumented, but it contains metadata that specifies the CMK and the encryption algorithm. I reverse-engineered the format and found the location of the CMK. Externally the CMK is identified by its key ARN, but within a ciphertext it is represented by an internal ID, which remained stable during my testing.
When I replaced the internal ID of a CMK in a ciphertext with the internal ID of another CMK, I found that AWS KMS attempted to decrypt the ciphertext with the new CMK. The encryption failed and the failure eventāincluding the AWS Account ID, the user agent and the IP address of the callerāwas logged to Cloud Trail in the account that owned the replacement CMK.
This enables the following attack:
This attack requires the victim to have an IAM policy that allows them to access the attackerās CMK. I found that this practice was allowed by the AWS Visual Policy Editor, but I donāt know whether it is common.
The AWS Encryption SDKs also succumb to this attack. The SDKs implement envelope encryption: encrypting data with a data encryption key (DEK) and then wrapping the DEK with a CMK using the Encrypt API in AWS KMS. The wrapped DEK is stored as part of the final ciphertext (format is defined here). The attacker can mount this attack by replacing the CMK in the wrapped DEK with their own.
{
"eventVersion": "1.05",
"userIdentity": {
"type": "AWSAccount",
"principalId": "<redacted this is the principal ID of the victim>",
"accountId": "<redacted - this is the AWS account ID of the victim>"
},
"eventTime": "2020-06-21T21:05:04Z",
"eventSource": "kms.amazonaws.com",
"eventName": "Decrypt",
"awsRegion": "us-west-2",
"sourceIPAddress": "<redacted - this is the IP address of the victim>",
"userAgent": "<redacted - this is the user agent of the victim>",
"errorCode": "InvalidCiphertextException",
"requestParameters": {
// The encryption context might include other data from the victim
"encryptionContext": {
"aws-crypto-public-key": "AzfNOGOnNYFmpHspKrAm1L6XtRybONkmkhmB/IriKSA7b2NsV4MEPMph9yX2KTPKWw=="
},
"encryptionAlgorithm": "SYMMETRIC_DEFAULT"
},
"responseElements": null,
"requestID": "aeced8e8-75a2-42c3-96ac-d1fa2a1c5ee6",
"eventID": "780a0a6e-4ad8-43d4-a426-75d05022f870",
"readOnly": true,
"resources": [
{
"accountId": "<redacted - this is the account ID of the attacker>",
"type": "AWS::KMS::Key",
"ARN": <redacted - this is the key ARN of the attacker>
}
],
"eventType": "AwsApiCall",
"recipientAccountId": "<redacted - this is the account ID of the attacker>",
"sharedEventID": "033e147c-8a36-42f5-9d6c-9e071eb752b7"
}
Figure 1: A failure event logged to the attackerās Cloud Trail when the victim attempted to decrypt a modified ciphertext containing the attackerās CMK.
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:
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.
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:
(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:
This attack is similar to the one discovered in Facebook Messenger.
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.