Possible attack on Borg - FUD or worth attention?

[git70]

Hi folks!

https://news.ycombinator.com/item?id=43438601

Can someone professionally explain to an amateur if this "attack" is an attack at all?

[ThomasWaldmann]

Definitely not FUD, but maybe not as bad as it may sound at first.

See there: https://github.com/borgbackup/borg/wiki/CDC-issues-reported-2025

[git70]

Thank you Thomas for a detailed explanation, but still some things are not clear to me. There is a high probability that I am too thin for it :(

If I'm too stupid, explain it like a fool:

1. I just make a backup to Borgbase and to Hetzner StorageBox by using ZSTD compression and encryption.
   Am I safe before this attack? Can this supplier break me if he is a bad actor and get to know my files?

2. If so, just use the options --compression obfuscate,2,zstd,6 ?

[git70]

I think I have only now understood the real level of threat = virtually no threat in my case. The initial reaction "damn my backups are threatened" was blushed ;)
I found a further context here: restic/restic#5291

[winterdeaf]

Author of the parallel "Breaking and fixing" paper here. The "fingerprinting" threat model is probably outside of what most users are worried about. Borg's docs discuss it here, and Kien has a blogpost out.
In short: if your backup contains Big_Buck_Bunny.mp4, and the attacker knows about that, they can check whether you also have Sintel.mp4 in your backup by looking at the chunk sizes.

The obfuscate pseudocompressor mostly thwarts the attacks from both papers, when using random reciprocal size variation (especially for larger parameters, e.g. SPEC = 2, at the cost of up to 2x storage cost).
For SPEC=1, we are still concerned about leakage over large files, which is unavoidable (even with randomized padding, observing every chunk reduces the keyspace until key recovery is possible -- and outliers in the chunk distribution make fingerprinting possible).

The optimal approach probably involves a stronger chunking algorithm (where it is not possible to recover the chunking secret by just looking at one chunk, e.g. generating the BuzHash table randomly instead of xoring with a fixed value, and a 64 bit seed) and an efficient padding scheme (like padme). This would stop fingerprinting for both small and large files, and have a storage cost of at most 12%.

[ThomasWaldmann]

Thanks for the feedback! I opened an issue to add the padme algorithm additionally to the 2 algorithms we already have for the obfuscate pseudo compressor: #8705

This is something we could add for borg 1.4.1 considering it is optional and also does not break the deduplication with existing repo contents.

Changing how chunks are cut would break that, so guess that has to wait for borg2 (and somebody implementing it). It would also need re-chunking for existing contents in borg2 transfer. Opened issue #8706 for that.

[winterdeaf]

Note that padme does not pair well with the current chunking scheme. It is actually worse than obfuscate, since it adds less padding, but it would be very efficient if a new chunker is implemented.

As far as we can see, the best way to protect the current chunking scheme is high values of SPEC, or always padding to 8MiB (obfuscate,123 should also work). Both are quite wasteful in terms of space, so maybe only really worth considering for users really worried about fingerprinting.

[ThomasWaldmann]

Guess the only real-world usage of high spec values is if you have little data, lots of space (and time) and a good reason to fear fingerprinting.