Key Commitment and Why an AEAD Can Decrypt Under Two Keys

The standard security definition of an authenticated cipher says that an adversary without the key cannot produce a ciphertext and tag that verifies. It says nothing about whether a ciphertext can verify under two keys. That omission is not a modelling lapse; the definition was built for a setting where the receiver holds one key and the question never arises. Once receivers hold several keys — during rotation, across tenants, in multi-party protocols — the question becomes concrete, and most AEAD constructions answer it badly.

A scheme where a ciphertext verifies under at most one key is called committing. A scheme where an adversary can produce a ciphertext that verifies under two keys of its choosing is not. GCM and CCM are both, in the general case, not committing. The statement has an air of paradox: the tag is 128 bits, and the adversary cannot compute it for either key without the key. The resolution is that the adversary does not compute the tag for a key it does not hold — it constructs the ciphertext by choosing keys first, then solving for a message that satisfies both.

The attack shape

Suppose the adversary wants a ciphertext $C$ with tag $T$ that decrypts to plaintext $P_1$ under key $K_1$ and to a different plaintext $P_2$ under key $K_2$, and such that both decryptions verify. It proceeds by choosing $K_1$ and $K_2$ itself, both unknown to the victim.

The crucial degree of freedom is that the adversary controls which of the two keys it fixes and which it solves for. With a single-block message and GCM’s 128-bit tag, the tag equation

$$T = \mathrm{GHASH}_H(A, C) \oplus E_K(J_0)$$

contains one unknown, the 128-bit initial counter block value $E_K(J_0)$, which the adversary cannot compute. But the adversary is not required to hit a target tag: it picks $T$ freely and solves for the plaintext, because for a single-block message the plaintext is a function of $T$ and $E_K(J_0)$ and the keystream, all of which are determined by the key. Choosing the key determines the plaintext that makes the tag verify. The adversary repeats for the second key, and either the two plaintexts coincide — the ciphertext then decrypts to the same message under both keys, which is uninteresting — or they differ, in which case the adversary has a ciphertext whose verification result depends on which key the receiver holds.

For GCM specifically, the construction needs one block of search per attempt, because the plaintext is determined by the key and the adversary has to check whether the two plaintexts differ in a way that is useful. The search is over keys, not over tags, and the success probability is high enough that the attack is practical in settings where the adversary can propose its own keys.

Where two-key ciphertexts matter

Key rotation is the canonical setting. A system rotates from $K_1$ to $K_2$ and keeps accepting ciphertexts under both during the transition. An adversary that can inject a ciphertext under one key — an encrypted message in a store-and-forward system, a wrapped secret, a configuration blob — can construct it so that the old key decrypts it to a benign value and the new key decrypts it to something else. Receivers that have finished rotating see one message; receivers that have not see another. The window during which both are accepted is exactly the window in which the divergence is exploitable.

Encrypted messaging with franking is the other well-documented case. A franking scheme attaches to each message a commitment that allows the recipient to prove to a moderator that a particular ciphertext was sent, typically bound to the key. If a ciphertext verifies under two keys, a malicious sender can produce one ciphertext, claim it was sent under a key it made up, and have the claim verify — the moderator’s check that the ciphertext is authentic under the claimed key succeeds. The documented construction of such a collision for AES-GCM-SIV, in a paper by Albertini and coauthors, is the clearest published demonstration of the pattern.

Password-based encryption and key wrapping have a third variant. An attacker who controls the plaintext can construct a ciphertext that verifies under a guessed password and under a second key, then observe whether a victim accepts it — a test that would otherwise require knowing the password.

Why the modes are not committing

The reason is structural in all of them. In GCM, the tag is $\mathrm{GHASH}_H(A, C) \oplus E_K(J_0)$. An adversary that knows $H$ and $E_K(J_0)$ can compute tags freely — that is exactly the nonce-reuse attack described in recovering the GCM authentication key. Building a non-committing ciphertext is the same computation run in a different direction, with the adversary choosing the key rather than recovering it.

The general pattern is that an AEAD’s tag is a function of the key through a small number of derived values. If an adversary can search over keys and check consistency cheaply, it can find keys under which a given ciphertext is consistent. Nothing about the design prevents this, because the design’s security goal never included it. The standard model asks whether an adversary can produce a valid ciphertext under a key it does not know; it does not ask whether it can produce a ciphertext valid under a key it chose.

Making a scheme committing requires binding the key to the ciphertext in a way that cannot be satisfied for two keys simultaneously. Two general approaches are used, both departing from the plain AEAD interface.

The mechanics can be written down without any key material. Let $F_K(T)$ denote the plaintext that the mode assigns to a given ciphertext and tag under key $K$; for GCM and for CTR-based modes this function is explicit, because the keystream and the tag offset are both derived from $K$ and the nonce. The adversary computes $F_{K_1}(T)$ and $F_{K_2}(T)$ for two candidate keys and a tag of its choosing, and it succeeds when the two results differ. Each candidate is checked with the public mode description alone.

The first is to make the tag cover a key-commitment value: a hash of the key, or of a per-key identifier, included in the authenticated data. Then a ciphertext that verifies under $K_1$ fails under $K_2$ unless the commitment values collide, which is a hash collision problem. This is sound but requires protocol changes and a place to put the commitment.

The second is to derive the tag key from the message key with a function that is collision-resistant in a stronger sense, so that finding two keys producing the same tag is equivalent to a hard problem. Constructions in the literature achieve this by hashing the key together with the nonce and the ciphertext, and by using a hash function with a security level matching the tag.

What key commitment costs

The cost depends entirely on how much of the ciphertext the commitment covers. A commitment over a per-message identifier is nearly free, because it is a hash of a few bytes. A commitment that covers the entire ciphertext requires a second pass over the whole message with a hash, which reintroduces the two-pass cost that SIV and other synthetic-IV modes already pay, and is incompatible with the streaming property discussed in releasing unverified plaintext.

There is a middle position. When the protocol already has a per-message unique identifier that the receiver knows independently — a message sequence number, a record number, a storage object identifier — that identifier can be placed in the associated data. That does not make the scheme committing by itself: the adversary can still pick keys that make the tag verify for a given identifier. But it removes the attacker’s freedom to choose the context, which is the practical prerequisite for most of the attacks. The franking attack requires the adversary to be able to claim a key it chose; the rotation attack requires a window where two keys are accepted. Binding the identifier narrows the attack surface even when commitment is not achieved.

The design lesson, in the language of the previous articles, is that an AEAD gives a guarantee relative to a key. Systems that hold several keys at once are asking a different question, and the modes that answer it are the ones designed for it. GCM and CCM were not, and neither makes a claim to; the specification’s security statement is a statement about one key, one nonce, and one message.

None of this invalidates the modes for single-key settings, which is most of them. It does mean that the multi-key settings — rotation, franking, escrow, multi-tenant sharing — need either a committing construction or a protocol-level commitment, and that the choice should be made when the protocol is designed rather than when the rotation is scheduled.