One Ciphertext, Two Valid Plaintexts: Why AEAD Needs Key Commitment

Modern encryption is almost always AEAD: authenticated encryption with associated data. AES-GCM and ChaCha20-Poly1305 are the two you meet everywhere, in TLS, in disk encryption, in message formats, in cloud key management. They give you confidentiality plus an authentication tag, and decryption either returns the plaintext or returns an error. The security definition behind that tag is about forgery. An attacker who does not know the key cannot produce a ciphertext that verifies. That definition holds. What it says nothing about is the situation where the attacker does know one or more keys and gets to choose the ciphertext. What a key multi-collision looks like Take AES-GCM. Its authentication tag is computed with GHASH, a polynomial evaluation over a binary field, and the relationship between the ciphertext blocks and the tag is linear in that field. Linearity is convenient for speed, and it is also solvable. Given two keys the attacker controls, K1 and K2, that linearity lets them set up a system of equations and solve for a ciphertext whose tag verifies under both. Decrypting it with K1 yields one plaintext. Decrypting the same bytes with K2 yields a completely different plaintext. Neither decryption throws an error, because from each key's point of view the tag is correct. Both plaintexts can be attacker-chosen and meaningful. The 2019 paper that named this attack demonstrated a file that was a valid image either way, which is where the memorable label came from: the two decryptions showed different pictures, and the second one had a salamander in it that the reporting system never saw. The property that was missing. An AEAD is key committing if a ciphertext can verify under at most one key. AES-GCM, AES-GCM-SIV, and ChaCha20-Poly1305 are not key committing, and were never claimed to be. The property simply was not part of the design goal, and for a long time no widely deployed system depended on it. The system it broke: message franking Here is the problem th