Hunting Invisible Salamanders: Cryptographic (in)Security with Attacker-Controlled Keys

Overview: Paul Grubbs, an applied cryptography researcher from Cornell University, presents research on the failure modes of authenticated encryption (AE) when evaluated under threat models where attackers control or influence encryption keys. The talk explores key-committing security, a fundamental property lacking in ubiquitous AEAD schemes like AES-GCM and ChaCha20-Poly1305. Grubbs explains how non-committing encryption allows adversaries to construct ciphertexts that produce multiple valid plaintexts under different keys, demonstrating exploits against Facebook’s message franking protocol and partitioning oracle attacks against password-based systems.

Key Topics: - Authenticated encryption (AEAD) assumptions and key-committing definitions - Multi-key ciphertext collisions in AES-GCM via polynomial interpolation - Evasion of abuse reporting in Facebook's message franking protocol - Partitioning oracles and logarithmic speedups in password recovery

Technical Details: Standard authenticated encryption with associated data (AEAD) provably guarantees confidentiality (IND-CPA) and integrity (INT-CTXT) under the assumption that keys are uniformly random and secret. However, modern applications increasingly deploy AE in settings where adversaries supply, choose, or brute-force keys—such as in password-authenticated key exchange (PAKE), encrypted group messaging, and abuse reporting. Grubbs formalizes the concept of committing AE: an encryption scheme is committing if a given ciphertext can decrypt validly under at most one secret key. Because AES-GCM combines Counter (CTR) mode with the GHASH polynomial MAC over the Galois field GF(2^128), it is strictly non-committing.

Grubbs demonstrates that CTR mode allows an adversary to choose two arbitrary plaintexts and derive a ciphertext that produces both plaintexts under two distinct keys by calculating the XOR of the respective keystreams. To satisfy the GHASH authentication tag under both keys, the attacker sets up a system of linear equations in GF(2^128) or applies polynomial interpolation. By adjusting ciphertext blocks, the attacker crafts a single ciphertext and tag that validates successfully under both keys. Using higher-degree polynomials, this technique scales to hundreds of thousands of keys (e.g., generating a single ciphertext valid under 131,000 keys). Grubbs illustrates this with a polyglot file that decrypts to a cat image under key 1 and an "invisible salamander" image under key 2, carefully aligning JPEG and BMP headers and comment length fields to satisfy both format parsers.

The author presents two major attack classes enabled by non-committing AE. The first breaks Facebook's message franking protocol, an abuse reporting mechanism for end-to-end encrypted messaging. A malicious sender delivers an abusive message to a victim; when the victim reports the message by forwarding the decryption key to Facebook, the server uses a secondary key derived from the franking tag. By exploiting non-committing GCM, the sender crafts the ciphertext so that Facebook's decryption reveals a completely benign message, evading moderation. The second attack introduces partitioning oracles against password-based authenticated encryption, including the Shadowsocks UDP proxy and prototype implementations of the OPAQUE PAKE standard. Instead of testing passwords individually, an attacker transmits ciphertexts valid under large subsets of passwords. Using binary search over key partitions, the attack recovers passwords in O(log N) online queries (e.g., searching 1,000,000 passwords in just 20 queries).

Key Takeaways: Cryptographic engineers must recognize that standard AEAD schemes like AES-GCM and ChaCha20-Poly1305 do not guarantee key commitment and are vulnerable when keys are untrusted or low-entropy. Protocols involving abuse reporting, group key distribution, or password-based encryption must adopt committing AEAD constructions, such as Encrypt-then-HMAC or committing key envelopes. While standard TLS remains secure because session keys are random and hidden, application-layer protocols must explicitly account for attacker-controlled key models.

(AI summary — Gemini Flash)