Crypto roadmap

[enkore]

Coordination and high-level discussion ticket

• "integrate AEAD-style crypto code" (this also adds AES-GCM crypto code, which would be unused at first). At first, only the legacy-compatible mode of the code would be used.
• Implement key-agility and algorithm-agility via DEKs
  • Discussion in add flexible encryption chunk header #1031 and linked spec draft
  • Low-level AEAD-style abstractions in new crypto code, blackbox, aead internally #1034 (with AES-CTR compatible to older borg repos and AES-GCM)
• require OpenSSL >= 1.1.1 (via new crypto code, blackbox, aead internally #1034)
  • AES-256-OCB? 25-50 % faster than AES-GCM (with and without AES-NI). Limited data/key is not a problem since we'll have key agility at this point (also, GCM has the exact same problem and is pretty much the same code-wise; just share the code!) [License: Borg is eligible, no explicit licensing needed, since we're OSI] - Ie. OCB is pretty much the same thing for us as GCM, just faster.
  • Chacha20-Poly1305 - is great because it's AEAD crypto that's faster than any AES-AEAD mode in software.

Note: edited / updated 2022-02 by TW

[enkore]

https://news.ycombinator.com/item?id=11634215 Rdedup – backup deduplication with asymetric encryption (in Rust)

https://github.com/fpgaminer/preserve/blob/master/crypto-spec.md - document describes the cryptography used by Preserve, an encrypted backup system written in Rust.

[enkore]

#1044 (comment) : I don't quite see the point of per-chunk keys. I derived a similar (and somewhat obvious) scheme before for deterministic calculation of random IVs, and there I see the point, not so much for entire keys (assuming that session keys are already used).

[enkore]

Discussion/analysis of keyblob (keyfile, repokey) saving/encryption: #1579

[enkore]

Python 3.6 has SHA-3 and the scrypt KDF.

A set of symmetric modes ie. were the same ID key results in the same chunk IDs, but which use different encryption (ie. no encryption and some encryption) would open some interesting possibilities.

[enkore]

Yes. I've read #1562, but I don't think the mechanism is ripe for 1.1. And given how slowly the field (of hash functions) evolves I'm not sure a more flexible mechanism is needed -- SHA-2 was introduced in ~2000ish, BLAKE in ~2013ish. The mechanism we have (key types) "just works" and is already in place (even with a nice error message - I checked that).

[enkore]

[This is not a response, just a statement]

What's absolutely clear is that there will be no way that borg has a variable feature set depending on some library version (i.e. "Lol, you can't read this repository on this computer, because your OpenSSL is too old."). That's just completely unacceptable for an archiving tool.

[rugk]

Throwing in some info/opinion about AES-GCM… https://twitter.com/tqbf/status/760907360319660032

(BTW, but still better than Encrypt-and-MAC, https://github.com/borgbackup/borg/issues/747…)

—— (@rugk: I generally value your input, but please don't bump tickets just to post previously discussed links again, see #45
—— edit by @enkore).

[gthieleb]

Can one summarize the showstopper for public key encryption (GPG like) or is this discussed in another issue? Reason: I don't want to provide a passphrase for headless backup jobs.

[anarcat]

@gthieleb you should look at #672 (comment)

[enkore]

When changing something about the keyfile, see whether the keyfile encryption can be fixed at the same time.

I wrote about key encrytion here; to summarize, there are two three issues with it:

1. It uses Encrypt-and-MAC in one of the few constellations not being outright broken (CTR mode, no padding and HMAC).
2. It reuses the same key for both AES and HMAC. Again not obviously broken in this specific constellation, but very poor practice.
3. It uses PBKDF2, and it uses comparatively weak parameters. (Using a more modern KDF than PBKDF2 #747, another issue number I know by heart ;)

From #3585 (comment)

[KizzyCode]

What about considering a SIV scheme for future AE(AD) constructions? This would immediately resolve any risk of nonce reuse without the need to maintain any kind of nonce state etc.

Because the current situation is quite unsatisfying. While it is pretty easy to use only one device per repo, the advise

You can avoid this by not continuing to write to the repository after you have lost clientside borg information.

is simply not practical unless you use borg for absolute emergency recoveries only.

[ThomasWaldmann]

aes-gcm-siv looks pretty nice and quite fast and the spec reads like made for our use case - thanks for the pointer!

but that is rather new and not present in openssl (yet?).

[KizzyCode]

but that is rather new and not present in openssl (yet?).

I'm no OpenSSL expert, but according to the changelog SIV was implemented (search for SIV). The API should be something like EVP_aead_aes_128_gcm_siv or EVP_aead_aes_256_gcm_siv.

On the age of SIV: There are multiple flavors of SIV. The oldest construction is the classic AES-SIV (which uses AES-CMAC as MAC) was published 2007. Then there is AES-GCM-SIV which is much newer. Or AES-SIV-PMAC as implemented by miscreant.

However since SIV is a generic construction, you're not even limited to AES. E.g. jedisct1 (the author of libsodium) has also created a trivial XChaCha20-Blake2b-SIV implementation (repo), which could be an option if you decide to opt-in for libsodium.

[rugk]

From the website:

On a platform where counters cannot be maintained, and where no trusted source of randomness exist, deterministic encryption can be used as a last resort.

…does not sound very confident though and rather like "if you cannot use anything else, do this, but we do not recommend it"…

[KizzyCode]

SIV guarantees the following:

But SIV has strong privacy and authenticity properties even if this nonce should somehow get reused: even then, new (header, ciphertext) pairs cannot be forged, and privacy will be compromised only to the extent that an adversary can detect repetitions in (header, plaintext) pairs.

libsodium and it's documentation are designed for people who don't know much about encryption – and therefore this warning is absolutely necessary: even the simple knowledge of data repetition can be enough to break some poorly designed protocols.

However whether this is a problem or not completely depends on the protocol/security model – in some cases it may even be desirable to have a deterministic bidirectional plaintext↔︎ciphertext mapping (e.g. the file names in an encrypting filesystem).

And when it comes to Borg this also should be completely fine, because a malicious server also can easily detect plaintext repetitions (and much more like access patterns etc.).

[ThomasWaldmann]

@KizzyCode i can't find aes-gcm-siv in openssl, can you point me to the declaration or implementation via a URL?

[ThomasWaldmann]

@rugk i read the SIV RFCs and they make clear that using SIV with a rarely-repeating "nonce" is of course much better than using SIV with a fixed "nonce".

that sounds pretty perfect for what we need:

• with our current counter management, in case of "accidents", like "all trusted bookkeeping lost"
• with a potential future random based nonce, in case of a repeating nonce case (which might be unlikely, depending on quality of rng and size of nonces, but possible)

i also liked that siv is able to take a vector of variable length strings and can merge them together for the AD part of AEAD.

the older implementations seem to be a bit slower than aes-gcm-siv, so that's why the latter might be nice for us.

[KizzyCode]

@ThomasWaldmann
Oh, my bad… I read about SIV in the OpenSSL's changelog and did a quick search without noticing that all results were from BoringSSL… 🙈

There are traces of SIV in OpenSSL's documentation (e.g. EVP_CIPHER_CTX_set_padding mentions EVP_CIPH_SIV_MODE), but I haven't been able to find a dedicated API… however I've never used OpenSSL myself directly, so this doesn't mean much 😅

Regarding the performance considerations: while AES-GCM-SIV is faster (and a better choice if available), the performance penalty of the classic algorithms should be negligible in most circumstances due to AESNI or NEON. I/O, compression and Borg's logic are probably much more of a bottleneck than 2*AES per chunk.

[ThomasWaldmann]

I'll edit here a bit and remove outdated and already-done stuff.

[ThomasWaldmann]

Would be cool if PR #6463 could get some review.