Small file size and directory order information leakage

[nadalle]

After talking to Thomas Waldmann on IRC, I'm opening a ticket mostly to document this issue.

Currently, borg's model for storing chunks in the repository leaks information about the size and (potentially) directory structure of small files. Size and directory structure information can often be used to determine information about the content of the files themselves, through various fingerprint / watermark attacks.

Files in borg are chunked, compressed, and then the chunks are stored in the repository using PUT commands. These PUT commands necessarily contain the size of the chunk being stored, and additionally the segment files in the repository contain these sizes in easily parsed form.

For small files, the size of the chunks prior to compression will typically just be the size of the file itself. Additionally, a great many modern file formats are not compressible, and in any event an attacker can simply compress the data too. In this way, the chunk sizes can leak information about the size of small files.

Additionally, chunks will tend to be stored in temporal order in their associated segment files. Since the order borg processed the files in will be some directory ordering, the temporal order in the repository should typically match a directory sort order, which leaks additional information.

As a hypothetical example of how size and directory structure information can be used as a data fingerprint, consider the common method of fingerprinting CD's based on their track length. Even if a CD was encoded to mp3, it's typically possible to convert file size back to track length by assuming a standard bitrate.

It should then be evident that a database of CD track lengths is sufficient to show that a directory of encrypted files contains the CD tracks with high confidence, just by comparing the ratios of the file sizes to the ratios of track lengths. This can be done without reading any of the data, just the file sizes.

Many other more advanced sorts of watermarking attacks are possible.

There are various potential ways to solve this information leak. A few ideas:

• Pad small files up to the chunk size.
• Bundle multiple files into a chunk somehow.
• More generally, differentiate between segment records (known to the remote server) and chunks (known to the client). Make the records all the same size.

Regardless of whether this is fixed any time soon, it seemed worth documenting better. The current documentation states "[...] all your files/dirs data and metadata are stored in their encrypted form into the repository" so a leak of file size and directory order information seems notable.

[nadalle]

As an additional note, storing chunks post-compression leaks some information on large files too. For example, imagine I store a compressible file such as a VM image. After it gets chunked and compressed, an attacker can see a sequence of blocks, each of which was compressible by a certain amount. If the attacker has a copy of the file, this ought to be sufficient to show that borg stored that large file.

[ThomasWaldmann]

The small file fingerprinting is a somehow known problem.

If one uses compression, the sizes are not as precisely as original, but of course an attacker could also try matching with all compression algorithms / levels if he has the original files.

The large file fingerprinting would not work like that.

The chunker is seeded with a random value that is part of borg's key material and different for each repo.
So the attacker's and the victim's chunker will cut chunks at different places, so the sequence of chunk sizes does not give a fingerprint. Also, the overall size of all chunks of such a large file after compression is influenced by that, so that's not easy to match either.

[enkore]

The random chunk seed is only useful iff an attacker cannot observe how a known (big) file is chunked. Additionally, chunk boundaries are low in entropy due to their small variance.

Broadly speaking, this sort of fingerprinting is difficult to defeat in an online backup system, because there are more channels to consider (like I/O timing of the source read operations leaking into the I/O timing of the network side).

Some other tools (duplicacy, casync to name two) chunk an aggregate (basically a tar); similar issues regarding compression apply. These are additionally vulnerable to CRIME/BREACH-like attacks between aggregate-co-located files, if compression is used (as is .tar.gz & friends).

https://en.wikipedia.org/wiki/BREACH
https://en.wikipedia.org/wiki/CRIME

[enkore]

Regarding directory order - borg traverses in inode-ordering (since 1.1), not native (usually hashed) directory order, or sorted by name/mtime/whatever. 1.0 uses hashed order, which of course results in poor performance.

Off-hand I'd say neither hashed dent order nor inode order recovery are really that valuable. Inode order tells you something about the allocation order of the inodes (depending on the FS), hashed order tells you... something?

[ThomasWaldmann]

See PR ^^^.

[ThomasWaldmann]

While thinking about attacks against the random chunker seed: we could move from a static seed stored in the key to a per-backup (or even per-file) generated seed.

Update: no, that does not work. We always need to chunk in the same way (per repo) or new chunks made from same input file won't dedup against old chunks made from that file.

[ThomasWaldmann]

Documented by #3710 and #3720.