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 that made this matter in production. In an end-to-end encrypted messenger, the server cannot read messages. So when a user reports an abusive message, how does the platform verify that the reported text was actually sent, rather than typed up by the reporter?
The answer is message franking. The sender commits to the plaintext, the server blindly signs that commitment on the way through without learning the content, and the recipient can later open the commitment to prove to the platform what was really sent. Facebook Messenger deployed a scheme of this shape.
Attachments were handled slightly differently from text: the file was encrypted with AES-GCM under an attachment key, and the franking commitment covered the encrypted blob rather than the decrypted file. A sender who could produce a blob that decrypted two ways could therefore send an abusive image whose reported form was innocuous. The report would arrive, the platform would verify it correctly, and the verification would show the wrong picture.
The attack was reported and fixed. What survived it is the general lesson: a protocol that treats "this ciphertext decrypted successfully" as evidence about which key or which sender was involved is relying on a property the cipher does not have.
Partitioning oracles: turning it into a password attack
A 2021 follow-up made the consequence sharper. If a key is derived from a password, an attacker who can send ciphertexts to a server and observe whether decryption succeeded normally learns one bit per guess: this password, yes or no.
With a non-committing AEAD, they can do much better. Build a ciphertext that verifies under a thousand candidate keys at once, send it, and a success tells you the true password is somewhere in that set of a thousand. A failure eliminates all thousand. That converts a linear search into a binary search over the password space, and the researchers demonstrated it against a widely used proxy protocol that authenticated clients with a shared password, along with password-based encryption in other tools.
The cipher did exactly what it was specified to do in every one of these cases. The failure sat in the assumption each protocol layered on top: that a successful decryption identifies a key.
Where else the assumption shows up
Once you know the shape, it appears in more places than the messaging case.
| Setting | The assumption being made | Committing AEAD needed |
|---|---|---|
| TLS record layer | None. Both endpoints agreed on one key through the handshake. | No |
| Multi-recipient encryption | Every recipient who decrypts sees the same message. | Yes |
| Abuse reporting and franking | What the reporter reveals is what the sender sent. | Yes |
| Password-based encryption over a network | A decryption failure rules out exactly one candidate password. | Yes |
| Envelope encryption with key rotation | A blob decrypting under a data key identifies which key wrapped it. | Depends on the format |
| Deduplicated cloud storage | Ciphertext identity implies plaintext identity. | Yes |
The multi-recipient row is the group-chat case, which is where this matters most for messaging. If a single ciphertext goes to many members and each unwraps a different key, non-committing AEAD means a malicious sender can show different members different content while everyone believes they are in one conversation. Group protocols such as MLS derive per-epoch keys shared across the group rather than per-recipient blobs, which changes the exposure, but any format where recipients hold different keys over the same bytes needs to think about this.
How the fix works
Three approaches are in circulation, in rough order of how disruptive they are to existing code.
The padding fix. Prepend a fixed block of zero bytes to the plaintext before encryption, and on decryption reject the message unless that block comes back as zeros. Because the attacker must now satisfy a fixed known prefix under both keys as well as the tag, the multi-collision problem becomes hard. The 2022 analysis that formalised this approach is what most implementations now cite. It costs one extra block and no new primitives, which is why it won.
Explicit commitment alongside the ciphertext. Derive a commitment value from the key with a hash or a KDF, ship it next to the ciphertext, and check it before decrypting. This is clean, adds bytes on the wire, and is easy to reason about because the commitment is a hash and hashes are collision resistant. Constructions in this family generally derive both a commitment and the encryption subkey from the original key using HKDF.
Encrypt then MAC over the key. Older and heavier, but a MAC computed over the key itself commits to it directly. Some protocols already do something equivalent without having framed it this way.
Cloud key management SDKs and file-encryption formats have been adding key commitment since 2020, and the property is now documented in Crypto Forum Research Group drafts on AEAD properties, so a spec author can point at a definition instead of inventing one. If you maintain a message or file format that encrypts to multiple keys, this is a question worth answering explicitly in the spec rather than inheriting from whichever library was convenient.
What this says about reading security proofs
Every result here was reachable from the published definitions. AES-GCM was proven secure against the goals it was designed for, and it met them. The gap opened where protocol designers read "authenticated" as a broader word than the definition supports, and then built systems whose safety rested on the broader reading.
That pattern recurs. Nonce reuse in GCM is a similar case, where a documented precondition gets violated by deployment reality and the consequences are severe.
The practical habit that comes out of it is narrow and useful. When a design says "if this decrypts, then X," write down what X is and check whether the cipher's own documentation claims it. Confidentiality, integrity against forgery, and identification of the key are three separate properties, and only the first two come standard.
Originally published at havenmessenger.com
Top comments (0)