Australian cloud for business software — built and run in Sydney since 2002

NetLeverage
NetLeverage

Is my data shared with other customers in deduplicated backup storage?

Technical article
Backup & Recovery

About this article: This article is reviewed against the cited sources. This is source research, not lab validation. Check the stated versions and your own requirements before making changes.

It depends on where the provider draws the boundary around "the same store". If identical blocks are kept once across many customers, the saving is larger. But if the backup client first asks the store "do you already have this block?", the answer can tell a stranger that some customer holds a particular file. Published research describes that leak for cross-user, client-side deduplication. It is a documented class of risk. None of the papers measures a backup provider.

Where each customer has its own store and its own keys, the leak does not arise. The price is a smaller saving, which shows up in the bill. The practical output is a set of questions to put to a provider in writing.

What does "shared" mean in deduplicated storage?

Deduplication stores a block of data once and records a reference each time the same block turns up again. The scope of "the same" can be drawn at three levels:

  • one machine,
  • one customer (all of that customer's machines), or
  • every customer on the platform.

The wider the scope, the more duplicates the store finds. Operating system files and common application files are identical on thousands of servers, so cross-customer scope saves real space. That saving is the reason providers consider it.

Sharing blocks does not by itself let other customers read your files, and a reference to a block is not a way to browse it. The question is narrower: what can someone learn from the way the store behaves?

How can sharing reveal another customer's data?

The mechanism is described by Boyd, Davies, Gjøsteen, Raddum and Toorani in a paper from the ARES 2018 conference (Definitions for Plaintext-Existence Hiding in Cloud Storage). In client-side deduplication, "a client initially sends a short descriptor (hash) of the file, the server then checks its storage and signals the client to upload the file only if the server does not have the hash value stored already."

The paper then states the consequence: "If the server informs the client that it does not require transmission of the full file then this (inherently) informs the client that at least one copy of the file has already been stored by the server." The attacker needs only a customer account on the same service and a guess about the content.

The paper credits Harnik, Pinkas and Shulman-Peleg with describing three uses of this signal:

  1. Identifying files: finding out that a particular file is stored.
  2. Learning file contents: guessing a file and inferring that it exists in the cloud.
  3. Covert channels: using the presence or absence of a file to pass a message.

Two examples from the papers show how little is needed. In the first, an attacker who knows an employee's contract format builds a template of it, "and if she receives sig = 0 for any of them then she knows that she has found a match with Alice's real contract." In the second, from Zuo and colleagues (Bandwidth-efficient Storage Services for Mitigating Side Channel Attack), a colleague who knows a payroll document except for the salary uploads one version per possible salary, and the version that is not uploaded in full shows the salary. Zuo et al. say the attacker "can monitor and measure the amount of network traffic" even though the connection is encrypted.

Both examples are about guessable documents with low variation. They are not about browsing someone's storage.

The original 2010 paper by Harnik, Pinkas and Shulman-Peleg was published in IEEE Security & Privacy magazine, volume 8, issue 6 (pages 40–47, as Boyd et al. cite it). The description of it above follows the two later papers.

Does this apply to backup products?

The papers study cloud storage services in general. A backup agent that sends block fingerprints before uploading, and that is told which blocks to skip, follows the same pattern. That is reasoning from the papers, not a vendor statement and not a finding about any product. Whether a given backup service works this way is a matter for its documentation and for the questions below.

Does encryption solve it?

Encryption of the stored data does not remove the signal. Boyd et al. write that the usual way of allowing deduplication on encrypted data, deterministic encryption with keys that depend on the message, "does not negate the following side channel that is present in all client-side deduplicating storage systems." Zuo et al. make the same point about convergent or message-locked encryption: the attacker can still watch whether a file was uploaded in full.

Zuo et al. also describe the blunt fix: encrypt each user's files with the user's own key, so identical files from different users produce different ciphertexts. In their words, this "prevents the cross-user deduplication in the server, but substantially increases bandwidth and storage overheads."

So "encrypted" and "not shared" are separate properties. A label saying one tells you nothing about the other.

How do stores reduce the risk?

Approach What it does What it costs Source
Separate store and keys per customer No block is matched across customers, so there is nothing to learn Each customer stores its own copy of common files Zuo et al. (per-user keys)
Noisy answer to "do you have this?" The server sometimes asks for the upload even when it already holds the block, so a skipped upload is not proof More uploads and a residual chance of leaking; the server must choose a rule Boyd et al.; Zuo et al. (the randomised threshold of Harnik et al.)
Deduplicate only at the server The client always uploads, so traffic shows nothing; the store matches afterwards The bandwidth saving is lost, and storage is still shared Zuo et al. ("target-based" deduplication)

Zuo et al. say of the randomised-threshold idea that it has a risk of leakage and uses high bandwidth. Boyd et al. describe the same trade-off: with a noisy answer there is "a clear tradeoff between security (probability that an adversarial client can infer storage status of some file) and efficiency (number of expected uploads of each file)."

The papers cited do not examine every possible signal, such as timing. Server-side-only deduplication removes the traffic signal that Zuo et al. rely on; it should not be assumed to remove every other signal.

What do restic and Borg document about sharing?

Both open-source tools scope deduplication to one repository, and both document who is trusted inside it.

  • restic references content by SHA-256 hash. A random polynomial is chosen when a repository is created and stored in its config file "so that watermark attacks are much harder". The threat model says an attacker who can observe chunk sizes created for a known file "can derive the secret chunker polynomial", and that knowing it "might in some cases allow an attacker to check whether certain large files are stored in a repository." restic reports a mitigation in 0.18.0: chunks are assigned to pack files at random. It also says that if one key leaks and several hosts share a repository, the attacker "will get access to the backup data of every host", and that changing the master key means copying into a new repository (restic design reference).
  • Borg derives the chunk ID with a keyed primitive, id = AUTHENTICATOR(id_key, data), and uses a secret random per-repository chunker seed. It states that when several clients update the same repository, "Borg fails to provide confidentiality." (Borg security; Borg data structures).

The practical reading is the same for both: one repository is one trust boundary. Parties that must not learn about each other's files belong in separate repositories, even though separate repositories cannot share blocks.

Worked numbers

Example (illustrative): a provider holds backups for three customers, each with 2,000 GB of data (decimal gigabytes). In each, 400 GB is the same operating system and application files that every customer has. The other 1,600 GB is specific to each customer.

  • Separate stores: 3 × 2,000 GB = 6,000 GB stored.
  • One shared store: 3 × 1,600 GB + 400 GB held once = 4,800 GB + 400 GB = 5,200 GB stored.
  • Difference: 6,000 GB − 5,200 GB = 800 GB, which is 800 ÷ 6,000 = 13.3% of the separate-store figure. At a rate of R per GB-month, that is 800 × R per month across the three customers, or about 267 × R each.

Here the whole saving comes from the 400 GB that every customer holds. The 1,600 GB that belongs to one customer is not shared in either design. This follows from how deduplication works rather than from a measured result. It suggests that the question for a buyer is not only "shared or not", but also what the saving would be on their own data, and whether the provider can quote a price with separate stores.

How do you check this with your provider?

Ask these in writing and keep the answers with the contract:

  1. At what scope are duplicate blocks matched: per machine, per customer or across customers?
  2. Does the backup agent send fingerprints and wait to be told what to skip (client-side), or does it always upload and the store matches afterwards (server-side)?
  3. If blocks are matched across customers, are they encrypted with a key that belongs to one customer, or with a key derived from the content?
  4. Is the "already stored" answer ever randomised?
  5. Can your data be placed in a separate store and keyed separately, and how does the quote change?
  6. If you hold your own keys, do those keys cover only your data?

For a tool you run yourself, treat each repository as one trust boundary. For restic and Borg that follows from the documentation above: the keys, the chunker secret and the deduplication scope all belong to the repository.

Risks and limits

Risk: asking for a separate store raises the stored volume. Zuo et al. say per-user keys "substantially increase bandwidth and storage overheads" and "substantially decrease the deduplication efficiency", and give no figure for a backup store, so ask the provider for a quote on your own data before deciding.

  • The attack in the papers needs an account on the same service and a guess at the content. It confirms a guess, as the examples show. It does not list or read another customer's files.
  • The published work is general cloud storage research from 2010, 2017 and 2018. None of it tests a backup product, so a provider's own design may differ.
  • The restic and Borg pages show no dates. restic's page names itself "restic 0.19.1" and Borg's pages name version 1.4.5. Later versions may change the details.
  • Whether an attacker could use some other signal, such as timing, against a particular service is not covered by the sources cited.

Sources