6 ms·

Restic Cryptography

105 points by FiloSottile 9y ago

bedros 9y ago
I wish the author compares it to borg backup which supports encryption and deduplication
- feld 9y ago
  I use full disk encryption, so I don't care about the encryption feature. But if this is going to be faster than borg for backing up data and deduplication because it's in Go and not in Python I will gladly switch.
  - dom0 9y ago
    From the benchmarks I've seen so far, there is no efficient (in terms of CPU use) deduplicating archiver. Sometimes restic is faster, sometimes Borg, no really clear picture. Compression can make Borg faster as well, when it fits the data set (LZ4 can be fast enough and compress well enough to reduce overall processing time, not just storage requirements).
    - feld 9y ago
      I use ZFS compression so I don't use borg's native compression either. I'm currently using lz4 but I will soon be moving to zstd which will gain me even more performance with similar or better compression.
- Freaky 9y ago
  Borg also supports one potentially-important feature restic does not: compression. https://github.com/restic/restic/issues/21 https://github.com/restic/restic/issues/21
- dom0 9y ago
  https://borgbackup.readthedocs.io/en/latest/internals/security.html#cryptography-in-borg https://borgbackup.readthedocs.io/en/latest/internals/securi...
- captaindiego 9y ago
  A main difference that pops out for me is that Restic supports windows, but Borg does not seem to.
modalduality 9y ago
Does anyone know why they might choose to encrypt-then-MAC vs. an AEAD scheme? Seems less error prone.
- dom0 9y ago
  Nothing error prone about EtM.
  - tuxxy 9y ago
    There's nothing error prone about choosing to do Encrypt-then-MAC, but there could be some issues with how they implemented AES-CTR. Plain and simple, there is just more room to make a grave mistake.
    - dom0 9y ago
      I'll assume that restic does not actually implement AES. I maintain that rolling EtM is effectively not more error prone than correctly using a dedicated AEAD construction, since in either case you are rolling your own crypto, which swamps error proneness differences between these alternatives.
      - tptacek 9y ago
        I'm not sure I follow this. A library implementation of an AEAD, with "Seal" and "Unseal" functions, is almost misuse-resistant (depending on the primitive and how they handle nonces). The same is not true of a library that exports AES-CTR or AES-CBC's Encrypt/Decrypt, plus a MAC! If you're implementing an entire AEAD construction, like GCM or EAX, from scratch, then yes. Don't do that. You probably are safer composing CBC and HMAC than you would be writing your own EAX. But if your library exports an EAX, using it is almost certainly a huge security win over DIY authenticated encryption, even if you can remember the order of operations properly.
    - tedunangst 9y ago
      Well, in comparison, there are plenty of opportunities for grave mistakes with AES-GCM.
loup-vaillant 9y ago
> Anyway applying the mask is pointless, dangerous, and took 45+ minutes to audit. It's not pointless. It facilitates 32-bit limbs¹, which are simpler to implement than 26-bit limbs. (And faster on modern intel processors. My implementation² beats both libsodium and donna by a slight margin.) If you use 26-bit limbs (as they probably do like everyone else), it is still not pointless: it's the only way to conform to official tests vectors and other Poly1305 implementations, making their implementation more reliable than it would be without them. It's also not dangerous, as DJB himself proved in his paper —unless one is uncomfortable with those security margins? [1]: http://loup-vaillant.fr/tutorials/poly1305-design http://loup-vaillant.fr/tutorials/poly1305-design (search "Restricting R") [2]: http://loup-vaillant.fr/projects/monocypher/ http://loup-vaillant.fr/projects/monocypher/ --- I can't fathom why they chose AES over Chacha20, though. Do they plan to rely on bit slicing? Chacha20 would be much simpler than that, and faster too. And if they absolutely want random nonces, they could have just used XSalsa20. (New projects can now use XChacha20, but that may not have been reasonable until a few months ago.)
- FiloSottile 9y ago
  * applying it manually in the application, since it's done by golang.org/x/crypto/poly1305 already
  - loup-vaillant 9y ago
    Oh… now that is beyond silly.
azinman2 9y ago
"To be clear: GCM is awful, but for TLS reasons it's the AEAD with the fastest implementations" I was under the impression was GCM was one of the better AES modes. Why is it awful?
- Johnny_Brahms 9y ago
  GCM is hard to implement. If I were to use one AEAD scheme that I would have to implement myself, I would definitely not use GCM. I whatever I was developing was open source (any project under an OSI-approved license gets a patent grant), I would use OCB mode, which is not only quite easy to get right, but also friggin fast. But hey: Don't trust me. Trust Matthew D Green: > GCM. Galois Counter Mode has quietly become the most popular AE(AD) mode in the field today, despite the fact that everyone hates it. The popularity is due in part to the fact that GCM is extremely fast, but mostly it’s because the mode is patent-free. GCM is ‘on-line’ and can be parallelized, and (best): recent versions of OpenSSL and Crypto++ provide good implementations, mostly because it’s now supported as a TLS ciphersuite. As a side benefit, GCM will occasionally visit your house and fix broken appliances. > Given all these great features, you might ask: why does everyone hate GCM? In truth, the only people who hate GCM are those who’ve had to implement it. You see, GCM is CTR mode encryption with the addition of a Carter-Wegman MAC set in a Galois field. If you just went ‘sfjshhuh?’, you now understand what I’m talking about. Implementing GCM is a hassle in a way that most other AEADs are not. But if you have someone else’s implementation — say OpenSSL’s — it’s a perfectly lovely mode. -- Matthew D Green [1] [1]: https://blog.cryptographyengineering.com/2012/05/19/how-to-choose-authenticated-encryption/ https://blog.cryptographyengineering.com/2012/05/19/how-to-c...
  - iofiiiiiiiii 9y ago
    What AEAD should one default to when one does not have to implement it himself? GCM mode is what I hear used most, so it would be my default but perhaps I should reconsider.
    - dom0 9y ago
      ChaCha20-Poly1305 is a very good compromise for all sorts of hardware.
hsivonen 9y ago
XSalsa20 uses 192-bit nonce in order to make the probability of collision of randomly-generated nonces negligible for some definition of negligible. Is there an explanation for what makes 128-bit nonces acceptable for Restic?
- loup-vaillant 9y ago
  That one bothered me as well, but it may suffice. The probability of collision, for 2^R random values of N bits is about 2^(2R-N). Lets' assume you want a probability of collision of less than 2^-64 (I think this is negligible enough). With 192 bits, this allows up to 2^64 nonces, which is quite hard to exceed in practice. 128 bits however only support up to 2^32 random nonces per key (a few millions). Some applications may exceed this threshold, but this is a backup we're talking about. You probably won't update it more than a million times in your lifetime, which most likely will span less than 30 thousand days from now.

Restic Cryptography

105 points by FiloSottile 9y ago

bedros 9y ago

I wish the author compares it to borg backup which supports encryption and deduplication

feld 9y ago
I use full disk encryption, so I don't care about the encryption feature. But if this is going to be faster than borg for backing up data and deduplication because it's in Go and not in Python I will gladly switch.
- dom0 9y ago
  From the benchmarks I've seen so far, there is no efficient (in terms of CPU use) deduplicating archiver. Sometimes restic is faster, sometimes Borg, no really clear picture. Compression can make Borg faster as well, when it fits the data set (LZ4 can be fast enough and compress well enough to reduce overall processing time, not just storage requirements).
  - feld 9y ago
    I use ZFS compression so I don't use borg's native compression either. I'm currently using lz4 but I will soon be moving to zstd which will gain me even more performance with similar or better compression.
Freaky 9y ago
Borg also supports one potentially-important feature restic does not: compression. https://github.com/restic/restic/issues/21 https://github.com/restic/restic/issues/21
dom0 9y ago
https://borgbackup.readthedocs.io/en/latest/internals/security.html#cryptography-in-borg https://borgbackup.readthedocs.io/en/latest/internals/securi...
captaindiego 9y ago
A main difference that pops out for me is that Restic supports windows, but Borg does not seem to.

modalduality 9y ago

Does anyone know why they might choose to encrypt-then-MAC vs. an AEAD scheme? Seems less error prone.

dom0 9y ago
Nothing error prone about EtM.
- tuxxy 9y ago
  There's nothing error prone about choosing to do Encrypt-then-MAC, but there could be some issues with how they implemented AES-CTR. Plain and simple, there is just more room to make a grave mistake.
  - dom0 9y ago
    I'll assume that restic does not actually implement AES. I maintain that rolling EtM is effectively not more error prone than correctly using a dedicated AEAD construction, since in either case you are rolling your own crypto, which swamps error proneness differences between these alternatives.
    - tptacek 9y ago
      I'm not sure I follow this. A library implementation of an AEAD, with "Seal" and "Unseal" functions, is almost misuse-resistant (depending on the primitive and how they handle nonces). The same is not true of a library that exports AES-CTR or AES-CBC's Encrypt/Decrypt, plus a MAC! If you're implementing an entire AEAD construction, like GCM or EAX, from scratch, then yes. Don't do that. You probably are safer composing CBC and HMAC than you would be writing your own EAX. But if your library exports an EAX, using it is almost certainly a huge security win over DIY authenticated encryption, even if you can remember the order of operations properly.
  - tedunangst 9y ago
    Well, in comparison, there are plenty of opportunities for grave mistakes with AES-GCM.

loup-vaillant 9y ago

> Anyway applying the mask is pointless, dangerous, and took 45+ minutes to audit. It's not pointless. It facilitates 32-bit limbs¹, which are simpler to implement than 26-bit limbs. (And faster on modern intel processors. My implementation² beats both libsodium and donna by a slight margin.) If you use 26-bit limbs (as they probably do like everyone else), it is still not pointless: it's the only way to conform to official tests vectors and other Poly1305 implementations, making their implementation more reliable than it would be without them. It's also not dangerous, as DJB himself proved in his paper —unless one is uncomfortable with those security margins? [1]: http://loup-vaillant.fr/tutorials/poly1305-design http://loup-vaillant.fr/tutorials/poly1305-design (search "Restricting R") [2]: http://loup-vaillant.fr/projects/monocypher/ http://loup-vaillant.fr/projects/monocypher/ --- I can't fathom why they chose AES over Chacha20, though. Do they plan to rely on bit slicing? Chacha20 would be much simpler than that, and faster too. And if they absolutely want random nonces, they could have just used XSalsa20. (New projects can now use XChacha20, but that may not have been reasonable until a few months ago.)

FiloSottile 9y ago
* applying it manually in the application, since it's done by golang.org/x/crypto/poly1305 already
- loup-vaillant 9y ago
  Oh… now that is beyond silly.

azinman2 9y ago

"To be clear: GCM is awful, but for TLS reasons it's the AEAD with the fastest implementations" I was under the impression was GCM was one of the better AES modes. Why is it awful?

Johnny_Brahms 9y ago
GCM is hard to implement. If I were to use one AEAD scheme that I would have to implement myself, I would definitely not use GCM. I whatever I was developing was open source (any project under an OSI-approved license gets a patent grant), I would use OCB mode, which is not only quite easy to get right, but also friggin fast. But hey: Don't trust me. Trust Matthew D Green: > GCM. Galois Counter Mode has quietly become the most popular AE(AD) mode in the field today, despite the fact that everyone hates it. The popularity is due in part to the fact that GCM is extremely fast, but mostly it’s because the mode is patent-free. GCM is ‘on-line’ and can be parallelized, and (best): recent versions of OpenSSL and Crypto++ provide good implementations, mostly because it’s now supported as a TLS ciphersuite. As a side benefit, GCM will occasionally visit your house and fix broken appliances. > Given all these great features, you might ask: why does everyone hate GCM? In truth, the only people who hate GCM are those who’ve had to implement it. You see, GCM is CTR mode encryption with the addition of a Carter-Wegman MAC set in a Galois field. If you just went ‘sfjshhuh?’, you now understand what I’m talking about. Implementing GCM is a hassle in a way that most other AEADs are not. But if you have someone else’s implementation — say OpenSSL’s — it’s a perfectly lovely mode. -- Matthew D Green [1] [1]: https://blog.cryptographyengineering.com/2012/05/19/how-to-choose-authenticated-encryption/ https://blog.cryptographyengineering.com/2012/05/19/how-to-c...
- iofiiiiiiiii 9y ago
  What AEAD should one default to when one does not have to implement it himself? GCM mode is what I hear used most, so it would be my default but perhaps I should reconsider.
  - dom0 9y ago
    ChaCha20-Poly1305 is a very good compromise for all sorts of hardware.

hsivonen 9y ago

XSalsa20 uses 192-bit nonce in order to make the probability of collision of randomly-generated nonces negligible for some definition of negligible. Is there an explanation for what makes 128-bit nonces acceptable for Restic?

loup-vaillant 9y ago
That one bothered me as well, but it may suffice. The probability of collision, for 2^R random values of N bits is about 2^(2R-N). Lets' assume you want a probability of collision of less than 2^-64 (I think this is negligible enough). With 192 bits, this allows up to 2^64 nonces, which is quite hard to exceed in practice. 128 bits however only support up to 2^32 random nonces per key (a few millions). Some applications may exceed this threshold, but this is a backup we're talking about. You probably won't update it more than a million times in your lifetime, which most likely will span less than 30 thousand days from now.