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

One ciphertext can produce two distinct plaintexts when decrypted using different keys, a phenomenon known as multi-collision. This issue arises in authenticated encryption with associated data (AEAD) schemes, which provide both confidentiality and message authentication. AES-GCM and ChaCha20-Poly1305 are common AEAD algorithms used in various applications, such as TLS, disk encryption, and cloud key management.

However, these algorithms are not designed to be key committing, meaning a single ciphertext can verify correctly under multiple keys.

The security definition for AEAD encryption focuses on preventing an attacker without the key from forging a valid ciphertext. However, it does not address the scenario where an attacker possesses one or more keys and can choose the ciphertext. In such cases, the attacker can exploit the linearity in the encryption process to find a ciphertext that verifies under multiple keys, resulting in two different plaintexts.

The 2019 paper that introduced this attack demonstrated a file that decrypted correctly as either an image or a salamander. This property of producing different plaintexts from the same ciphertext is problematic for systems relying on AEAD encryption for message integrity. One example is Facebook Messenger, which used AES-GCM for encrypting attachments.

An attacker could send an abusive image whose reported form appeared innocent. When a user reported the message, the platform would verify the franking commitment correctly, but the verification would reveal the wrong image.

The 2021 follow-up highlighted the severity of this issue. If a key is derived from a password, an attacker can perform a more efficient password guessing attack using a non-committing AEAD. By constructing a ciphertext that verifies under multiple candidate keys simultaneously, the attacker can determine whether the true password is within that set of candidates. This converts a linear search into a binary search over the password space, significantly accelerating the attack.

The flaw in AEAD encryption schemes has broader implications beyond messaging. It affects various protocols relying on key derivation from passwords, password-based encryption, envelope encryption with key rotation, and deduplicated cloud storage. In any scenario where multiple recipients decrypt the same ciphertext using different keys, a non-committing AEAD allows malicious senders to send different content to different recipients while maintaining the appearance of a single conversation.

To mitigate this vulnerability, researchers have proposed three solutions. The padding fix involves prepending a fixed block of zero bytes to the plaintext before encryption. During decryption, the system checks if this fixed block remains unchanged. If it does, the message is rejected, preventing the multi-collision attack. Another approach involves using a different encryption scheme that is inherently key committing.

However, this may require significant changes to existing codebases. The third solution focuses on properly designing protocols that avoid relying on successful decryption as evidence of a specific key or sender.