borg2: implement new chunker?

[ThomasWaldmann]

#8803 opens the door for a unique opportunity: re-chunking while doing a borg2 transfer (which will be required anyway for transferring archives from borg1 repos to borg2 repos).

So, if borg2 gets a new chunker before it is released, we could use it there and convert relatively painlessly.

Usually one can not easily switch to a new chunker within an existing repo:

• new-chunked chunks of identical files do not deduplicate with old-chunked ones
• thus, space usage doubles as long as old-chunked archives are present (== for a very long time in usual pruning scenarios)

Requirements for new chunker:

• little to no C code, rather Cython, Python. (*)
• better security properties than buzhash, see https://github.com/borgbackup/borg/wiki/CDC-issues-reported-2025
• not too slow, preferably similarly fast or faster than buzhash
• better to maintain code (buzhash is too much C)
• could be a separate project (like borghash, borgstore, now borgchunk(er)?)

(*) in the borg codebase. nothing against a well-maintained chunker library with more low-level code that is external.

Existing chunkers in borg:

• fixed (fixed block size, relatively simple, fast, Python/Cython, can support sparse files efficiently)
• buzhash (variable block size, CDC, complex, hard to maintain C code, no sparse files support)

Chunker tickets:

• https://github.com/borgbackup/borg/issues?q=is%3Aissue%20state%3Aopen%20label%3A%22c%3A%20chunker%22
• PR Chunker permutation #5070

[darkk]

Speaking of performance impact. My old machine with Core i7-6600U and aes-ni support claims to compute:

• 405 MiB/s of SHA256 per openssl speed -evp SHA256 -bytes 262144
• 190 MiB/s of SHA256 per sha256sum /dev/shm/urandom.2GiB
• 77 M blocks/s of AES-128 per openssl speed -evp AES-128-CBC -bytes 262144
• 321 M block/s of AES-128 per openssl speed -evp AES-128-OCB -bytes 262144
• 224 MiB/s of SipHash12_1u64(Gear64(Last-level-cache))
• 1,344 MiB/s of Buzhash(Last-level-cache)

While SipHash12(Gear64()) is ≈6 times slower than Buzhash it's still ≈3 times faster than AES(), so it might still be an option to consider as a fingerprinting-resisting chunker in terms of CDC-issues-reported-2025.

Also, SipHash-1-2 has imperfect avalanche properties: SMHasher reports maximal pair-wise bit-bias of 25%, but that's probably good enough given quasi-randomized input.

[ThomasWaldmann]

For borg2, we'll use OCB mode, as that is AEAD and very fast:

tw@MacBook ~ % openssl speed -evp AES-256-OCB -bytes 262144
Doing AES-256-OCB ops for 3s on 262144 size blocks: 33707 AES-256-OCB ops in 3.00s
version: 3.5.0
The 'numbers' are in 1000s of bytes per second processed.
type         262144 bytes
AES-256-OCB    2945362.60k

So, almost 3GB/s?

[darkk]

Please, excuse my habit of high-context messages :-) I was speaking assuming the context of chunker parameter extraction attacks. BTW, Breaking and fixing content-defined chunking paper is now available online, so wiki page might be updated.

Indeed, AES-128-OCB does 321 M block/s and AES-256-OCB produces 234 M block/s on the very same machine. However, I think that you mean AES-256-OCB being used for data encryption & authentication, not as a part of chunker.

I'm counting AES blocks (not bytes) as a throughput metric because permutation should be done for the hash value of each and every byte of input that is chunked.

My bad, AES-128-CBC was a wrong way to estimate number of of AES blocks per second. I assume, that happens due to CDC enforcing data dependency, thus breaking some sort pipelining.

It's interesting to see that quite fast Buzhash-based chunker might still be a limiting factor given 3.5 GiB/s of encryption throughput for AES-256-OCB and 4.8 GiB/s for AES-128-OCB.

[ThomasWaldmann]

Good news: in #8881 I started to refactor the chunkers and separated file reading, sparse file / fmap support from the chunking.

That shrinked ChunkerFixed to be trivial, we can differentiate now between chunking and reading/seeking time for benchmarking and hopefully FileReader will be also useful to simplify the buzhash Chunker (and add sparse file / fmap support at the same time).

[ThomasWaldmann]

Chunker refactor is merged, thus it is now easier to add a new chunker.

[ThomasWaldmann]

@darkk please have a look at #8903.

buzhash64 is not using AES, so likely not that cryptographically strong, but using a 64bit hash was suggested by one of these recent CDC security papers. It seems to be about as fast as the 32bit buzhash we use in borg 1.x.

Also, the seed value (aka "chunker secret") could be much more now, up to 64-256bits.

[ThomasWaldmann]

I added optional support for encrypting the rolling hash value before the chunking decision is made. About 7x slower when enabled.