How can we exhibit an [AES-GCM][1] 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.
