# AES-GCM ciphertext that deciphers under two keys

How can we exhibit an AES-GCM ciphertext, including IV and 128-bit authentication tag, and distinct keys $$K_0$$ and $$K_1$$, so that decryption succeeds for both keys?

What degree of control do we have on the respective plaintexts obtained by such decryption? Can that extend to the point that this nightmare (referring page) of the same encrypted and authenticated ciphertext decrypting to two meaningful but wildly different documents holds (for some standard document/archive format)?

Numerical example (or link to that) welcome!

Update: I'm told this is as described there by Yevgeniy Dodis, Paul Grubbs, Thomas Ristenpart and Joanne Woodage's Fast Message Franking: From Invisible Salamanders to Encryptment, in proceedings of Crypto 2018; but I'd like an independent answer focusing on the how (even if that's not detailed), and leaving out Associated Data if that's not essential.

How can we exhibit an [AES-GCM] ciphertext, including IV and 128-bit authentication tag, and distinct keys $$K_0$$ and $$K_1$$, so that decryption succeeds for both keys?

It's quite easy (if you grok linear algebra in $$GF(2^{128})$$

Here's what you do:

• You arbitrarily select the keys $$K_0$$ and $$K_1$$, the nonce and the ciphertext/AAD (except for one block, which can be anywhere, including in the AAD); we'll assume that the one block is at indes $$i$$ (where the last block of the ciphertext is index 2, the next to last is index 3, and so on - this rather odd convention is related to how GCM works internally).

We then compute the GCM authentication key $$H_0 = AES_{K_0}(0)$$ and $$H_1 = AES_{K_1}(0)$$

Then, the tag for the message with $$K_0$$ can be expressed as:

$$C_0 + M_i H_0^i$$

where $$C_0$$ is a function of $$K_0$$, the nonce and the selected message, AAD blocks, and $$M_i$$ is the value we'll place into ciphertext block $$i$$. One easy way to compute it is to insert a 0 where $$M_i$$ would go, and compute the tag as normal.

Similarly, the tag for the message with $$K_1$$ is:

$$C_1 + M_i H_1^i$$

So, to find $$M_i$$ so that they have the same tag, we equate the two, resulting in:

$$M_i = (H_0^i + H_1^i)^{-1}(C_0 + C_1)$$

(Remember, we're in $$GF(2^{128})$$; addition and subtraction are the same operation, so we usually express it as addition; in a different field, this would be written as $$(H_0^i - H_1^i)^{-1}(C_0 - C_1)$$)

Put that into the ciphertext, include the appropriate tag (computable by the above formula), and there you go.

This approach can be extended to finding a message that'll decrypt with $$k$$ different keys (by using $$k-1$$ free blocks).

Can that extend to the point that this nightmare of the same encrypted and authenticated ciphertext decrypting to two meaningful but wildly different documents holds (for some standard document/archive format)?

Not quite; the attacker can pick the ciphertext so that it'll decrypt under one of the keys to a chosen message (except for that one block); however that gives him no control over the other decryption.

By making a reasonable assumption on AES, it would appear provable that the attacker cannot do significantly better (at least for 96 bit nonces). GCM translates ciphertext to plaintext (assuming a valid decryption) by the operation $$P_i = C_i \oplus AES_k( N(i) )$$, where $$N(i)$$ is the nonce and the block index combined). Hence, the xor of the two decrypted plaintexts will be, for that block $$AES_{k_0}( N(i) ) \oplus AES_{k_1}( N(i))$$, and that wouldn't be controllable.

Nonce sizes other than 96 bits would be harder to analyze (as $$N(i)$$ now becomes a function of the key); however there wouldn't be an obvious approach to break that either.

• Thanks! I (now) read there has been some creative work towards partly chosen dual plaintexts so that both are meaningful. E.g. this (with presentation). Basically there are tiny segments of plaintext that are chosen for both plaintexts, using brute force; and large portions chosen for one plaintext or the other; and the semantic of file formats makes both plaintexts nearly as good as chosen (here one if a JPEG, the other a BMP, and both are valid for some software).
– fgrieu
Oct 9 '20 at 5:49