Your Encryption Might Be Lying to You: Invisible Salamanders and Partitioning Oracles

When we say a file is "encrypted," most people imagine a locked box, one key opens it, and inside is exactly one message. That mental model is comforting. It's also wrong for many of the encryption schemes the industry relies on every day.

Over the past several years, cryptographic researchers have uncovered a class of attacks that exploit a subtle gap between what we assume authenticated encryption does and what it actually guarantees. The two most important results in this space are the Invisible Salamanders attack (Dodis, Grubbs, Ristenpart, and Woodage, 2018) and Partitioning Oracle Attacks (Len, Grubbs, and Ristenpart, 2021). At Databeamer, where we build zero-knowledge secure collaboration infrastructure, understanding these attacks isn't academic, it directly shapes how we design our encryption layer.

This post explains what these attacks are, why they matter, and what you should look for if you're building or evaluating any system that handles encrypted data for multiple parties.

The property nobody asked for

The core issue is deceptively simple. Widely used AEAD (Authenticated Encryption with Associated Data) schemes, including AES-GCM, XSalsa20/Poly1305, and ChaCha20/Poly1305, were designed to guarantee two things: confidentiality (nobody without the key can read the plaintext) and integrity (nobody can tamper with the ciphertext without detection). They deliver on both promises.

But there is a third property that most engineers implicitly assume these schemes have, which was never part of the contract: key commitment. Key commitment means that a given ciphertext can only be decrypted by one key to produce a valid plaintext. Without this property, an attacker who knows two different keys can craft a single ciphertext that decrypts to two completely different plaintexts depending on which key is used, and both decryptions pass authentication.

This isn't a theoretical curiosity. It's a practical exploit.

Invisible Salamanders: One ciphertext, two realities

The name "Invisible Salamanders" comes from the 2018 paper that demonstrated a concrete attack against Facebook Messenger's abuse reporting system. Facebook's Secret Conversations feature used AES-GCM for end-to-end encryption of attachments, with a "message franking" mechanism that allowed recipients to report abusive content to Facebook for moderation.

The attack worked like this: a malicious sender could craft a single encrypted attachment that decrypted to an abusive image for the recipient, but decrypted to a completely innocuous image when Facebook's moderation servers tried to verify the report. The abusive content was, from the moderator's perspective, invisible, hence the name.

How is this possible? In AES-GCM, the authentication tag is computed using a polynomial evaluation over a finite field (GF(2¹²⁸)). Given two known keys, an attacker can set up a linear equation over this field and solve for a "sacrificial" ciphertext block that forces the polynomial to produce a valid tag under both keys. The field arithmetic itself is trivially fast, a laptop can do it in milliseconds. The real engineering challenge in practical attacks is finding plaintexts that are simultaneously valid in two file formats (a working JPEG and a working PDF, for example), which is where most of the work in papers like Albertini et al. (2022) actually goes.

The critical insight is that this isn't a break of AES-GCM as specified. The AEAD security definition simply doesn't say anything about what happens when the attacker controls multiple keys. AES-GCM was never designed to be a commitment scheme, it just happens that most systems treat it as one.

Partitioning Oracles: From salamanders to key recovery

If Invisible Salamanders showed that non-committing encryption enables deception, Partitioning Oracle Attacks showed it enables key recovery.

The 2021 paper by Len, Grubbs, and Ristenpart introduced a new class of chosen-ciphertext attack. The setup requires a server that will attempt to decrypt a submitted ciphertext and reveal whether decryption succeeded or failed, a decryption oracle. Many real-world systems provide exactly this, sometimes explicitly (an API that returns an error on invalid ciphertext) and sometimes implicitly (through timing differences or behavioural side channels).

The attack works by exploiting key multi-collisions. Because AES-GCM is not key-committing, an attacker can construct a single ciphertext that is valid under many keys simultaneously, not just two, but potentially thousands. Each crafted ciphertext effectively "partitions" the key space: if decryption succeeds, the server's key must be in the valid set; if it fails, the key is elsewhere. By submitting a sequence of carefully chosen ciphertexts, the attacker performs a binary search over the key space, narrowing down the server's secret key with logarithmic efficiency.

For password-derived keys, where the key space might be millions rather than 2¹²⁸, this is devastating. The researchers demonstrated a practical attack against Shadowsocks proxy servers, recovering passwords far faster than brute force. They also surveyed early implementations of the OPAQUE password-authenticated key exchange protocol and found several vulnerable to the same technique.

Where this shows up in practice

It's tempting to dismiss these attacks as niche. After all, the attacker needs to control or know multiple keys, or needs a decryption oracle. But the scenarios where these conditions hold are more common than you'd think.

Envelope encryption is ubiquitous in cloud services: a data encryption key (DEK) encrypts the payload, and the DEK itself is wrapped under each recipient's key encryption key (KEK). If the AEAD used for the payload is non-committing, a malicious party who knows multiple KEKs can substitute the DEK to make the same ciphertext decrypt differently for different recipients.

End-to-end encrypted messaging and file sharing, the exact domain Databeamer operates in, inherently involves multiple keys. When a sender encrypts a file that multiple recipients will decrypt, or when an intermediary (like a compliance scanner or abuse reporting system) also holds a key, the multi-key scenario is baked into the architecture.

Password-based encryption anywhere a server decrypts user-submitted ciphertexts with a password-derived key is potentially vulnerable to partitioning oracle attacks, unless the AEAD scheme is committing.

What "committing" means and how to get it

A key-committing (or simply committing) AEAD scheme ensures that no ciphertext can be valid under more than one key. Achieving this turns out to be straightforward in principle, though the details matter for performance and compatibility.

The most common approaches are:

Hash-then-encrypt: Prepend a hash (or HMAC) of the key to the ciphertext. The verifier checks that the hash matches before attempting decryption. This is conceptually simple but adds an extra hash computation and leaks key identity, the hash reveals which key was used. If indistinguishability is required, salting the hash with the nonce addresses this.

Encrypt-then-MAC with a collision-resistant MAC: Constructions like CTR-then-HMAC-SHA-256 are naturally committing, because the HMAC output is a collision-resistant commitment to the key. The MAC output must be at least 256 bits (not truncated) to preserve collision resistance.

Purpose-built committing AEADs: The research community has been actively working on efficient committing constructions. Schemes based on the duplex/sponge construction (like those in the Keccak family) tend to be inherently committing, and there are proposals for committing modes built on top of existing block ciphers.

Padding-based transforms: The padding fix from Albertini et al. (USENIX Security 2022) prepends a known constant (such as a block of zeros) to the plaintext before encryption; the recipient verifies this prefix after decryption. Because no single ciphertext can produce that exact prefix under two different keys, the prefix acts as an implicit commitment. The same paper also proposes a more general UtC ("UNAE-to-Committing") transform. Care must be taken to avoid timing side channels during prefix verification.

What we do at Databeamer

Databeamer's encryption layer uses ChaCha20/Poly1305, one of the schemes explicitly identified in the partitioning oracles paper as non-committing. We chose it for its performance characteristics, constant-time implementation simplicity, and resistance to timing side channels. But we don't pretend that Poly1305's authentication tag is a commitment to the key.

Our zero-knowledge model means that we never hold decryption keys, but our users operate in multi-party scenarios where the Invisible Salamanders threat model applies directly: files are encrypted for multiple recipients, and the integrity of what each party decrypts must be guaranteed. So on top of ChaCha20/Poly1305, we layer a key commitment scheme that binds each ciphertext to exactly one key. The Poly1305 tag gives us integrity; the commitment gives us the guarantee that two recipients cannot be tricked into seeing different content from the same ciphertext.

This is the kind of subtlety that separates "we use encryption" from "we understand what our encryption actually guarantees." If you're building systems where multiple parties interact with the same ciphertexts, file sharing, collaboration, messaging, compliance workflows, the distinction matters.