The technique is called convergent encryption, and it came out of Microsoft Research's Farsite project in 2002, in a paper on reclaiming space from duplicate files in a serverless distributed file system. The construction is three lines:
- Hash the file to get a key:
K = H(M) - Encrypt the file with that key:
C = E(K, M) - Store
Kencrypted under your own long-term key, so you can get the file back
The server sees C and a tag derived from it. Two users with the same file arrive at the same K without ever communicating, so they produce the same C, so the server stores it once and hands each of them their own wrapped copy of the key. Storage costs collapse on any corpus with real duplication, which is every consumer backup service that has ever existed.
In 2013, Bellare, Keelveedhi and Ristenpart formalised the family under the name message-locked encryption and proved what it can and cannot deliver. The proofs are worth knowing about, because the limitation is not an implementation defect. It is inherent.
Deterministic encryption cannot hide a guessable file
Ordinary encryption is randomised. Encrypt the same message twice under the same key and you get two different ciphertexts, because a fresh nonce or IV goes into each operation. That is what lets us claim an observer learns nothing at all from the ciphertext, not even whether two ciphertexts hold the same content.
Convergent encryption cannot be randomised, because determinism is the entire point. Same file, same key, same ciphertext, always. Which means anyone who can guess your file can verify the guess:
- Obtain a candidate file, or construct one.
- Run the same derivation to get
Kand produceC. - Compare against the stored ciphertext, or just against its tag.
- A match confirms the plaintext.
This is the confirmation-of-a-file attack, and the security proofs are explicit that message-locked encryption offers meaningful protection only for unpredictable data. For a high-entropy file nobody else could reconstruct, it is fine. For a leaked document, a known photograph, a standard tax form, or a piece of software with a specific version, it provides no confidentiality against anyone holding a copy.
The learn-the-remaining-information attack generalises this to files that are mostly known. If an adversary has a template and needs only the salary figure or the account number, they enumerate the small number of possible completions, encrypt each, and compare. A document that is 99 percent public becomes a search over the remaining 1 percent, and the cryptography does not slow it down.
The side channel is worse than the attack
Deduplication can happen in two places. Server-side, the client uploads everything and the server discards duplicates. Client-side, the client computes the tag first, asks the server whether that block already exists, and skips the upload if it does. Client-side deduplication across all users is the version that saves bandwidth, so it is the version providers wanted.
Harnik, Pinkas and Shulman-Peleg described the consequence in 2010. If the client can tell that an upload was skipped, and skipping means some other user already has that exact file, then the upload interface is an oracle for file existence across the entire service. You do not need an account belonging to your target. You need the file.
From there the attacks are mundane and effective. Upload a document to learn whether it has leaked. Distinguish between candidate versions of a file to fingerprint which build somebody is running. Encode a covert channel by conditionally uploading marker files that a colluding party probes for. The timing difference between an upload that transfers gigabytes and one that returns immediately is not subtle, so hiding the signal is difficult once the mechanism is present.
A related failure appears when the tag is treated as proof of possession. If knowing the hash of a file is sufficient to claim it, then anyone who learns a hash can download content they never had. The 2011 work on proofs of ownership exists to close that specific gap, requiring a claimant to demonstrate knowledge of the file's actual contents rather than a short digest.
The mitigations, and what each one costs
| Approach | How it works | Cost |
|---|---|---|
| Server-side dedup only | Client always uploads; server deduplicates after receipt | Closes the existence oracle, keeps the storage saving, loses the bandwidth saving |
| Randomised upload threshold | Upload anyway for the first few copies of a block, dedup after | Blurs the oracle without removing it; the guarantee is statistical |
| Convergence secret | Mix a per-user or per-group secret into the key derivation | Dedup only within the group sharing the secret; global savings gone |
| Server-aided keys (DupLESS) | Derive the key by running an oblivious PRF with a rate-limited key server | Brute force becomes online and rate-limited; adds a component whose compromise matters |
| No cross-user dedup | Per-user keys, ordinary randomised encryption | Full confidentiality, full storage cost |
The convergence secret approach is what Tahoe-LAFS adopted. Files converge, and therefore deduplicate, only among users who share the same secret, which turns a global oracle into a within-team one. That is the right default: a group that already shares files with each other learns much less from confirming that one of them has a file.
DupLESS, from the same researchers who formalised message-locked encryption, is the more elegant answer. Instead of hashing the file locally, the client runs an oblivious pseudorandom function protocol with a separate key server. The key server learns nothing about the file, the client cannot compute keys without it, and because the server sees each request it can rate-limit them. Guessing attacks become online guessing attacks against a throttle, which is a completely different economic proposition. The cost is an extra service that has to stay up and stay uncompromised, and whose operator must be distinct from the storage provider for the separation to mean anything.
How to read a provider's claims
Two marketing statements that frequently appear on the same page are in tension:
"Your files are encrypted with keys only you hold." and, three sections further down the same page
"We deduplicate across our entire user base, which is how we keep prices low." a pairing you can find on more than one storage marketing page
Cross-user deduplication of encrypted data requires the ciphertext to be a deterministic function of the plaintext, which requires the key to be a function of the plaintext, which means the key is not something only you hold. It is something anyone with the file can compute. Both statements can be technically defensible in isolation and the combination still tells you the confidentiality is conditional on your files being unguessable.
Useful questions when evaluating a service, and reasonable answers to expect:
- Is deduplication cross-user or within-account? Within-account dedup has none of these problems and is the common modern choice.
- Is it client-side or server-side? Server-side avoids the existence oracle entirely.
- Where does the file key come from? A random key wrapped under your account key is the safe answer. A hash of the content is the answer that requires the rest of this article.
- Is there a convergence secret? If yes, dedup is scoped, which is a considered design rather than a default.
The wider pattern
Deduplication is one member of a family of efficiency mechanisms that leak through their own success. Compression before encryption leaks plaintext structure through ciphertext length, which is how CRIME and BREACH recovered session cookies. Caching leaks prior access. Searchable encryption schemes leak access patterns. In each case the optimisation works by making the system behave differently depending on the data, and behaviour that depends on data is observable.
None of this makes convergent encryption a bad tool. For backup systems handling genuinely unpredictable data, or for deduplication scoped inside a team that already shares those files, the trade is sound and the storage savings are large. It becomes a problem when it is deployed silently under a promise of unconditional confidentiality, because the user then believes they have a guarantee that the construction was never able to provide. If you are choosing a service, our comparison of end-to-end encrypted cloud storage covers where the various providers land, and the questions above are the ones that separate them.