9 ms·

Why I Have Settled on XChaCha20+Blake3 for AEAD

127 points by vlmutolo 5y ago

cjg 5y ago
"8. Source: My Ass" :-)
vlmutolo 5y ago
Not my blog. Author works on a backup/archival tool called "Asuran", which I assume motivates a lot of the research into AEAD. I had never heard of the "partitioning oracle" attack, which is a really interesting way to exploit Poly1305 tags under certain conditions. I never would have assumed that it's practical to generate multiple ciphertexts that all authenticate under the same Poly1305 tag. That property leads to some interesting attacks.
- Aachen 5y ago
  You might also be interested in RSA blind signatures. They hardly ever come up so I was surprised to learn what seemed like an important property years after I thought I knew what RSA did.
speedgoose 5y ago
In my understanding, Blake3 is fast mostly because it does fewer rounds than blake2. The logic is that there is no need to be conservative in the number of rounds because the current public attacks work only on few rounds so we can just do a bit more rounds and be good. I personally avoid Blake3 and stick with blake2.
- thatonelutenist 5y ago
  It's a bit more complicated than that. Yes, the core of blake3 is a modified blake2b with fewer rounds, and yes the person who wrote the "Too much Crypto" paper is one of the blake authors, but there are other aspects of the construction that contribute as well. Blake3 operates in a merkle tree mode using the modified blake2 as a node hashing function, which, in and of itself complicates attacks for reasons explained in the blake3 paper. Blake2 also didn't really have that many rounds to start with, Blake3 only reduces the round count from 10 to 7. A good _most_ of the speedup in Blake3 is due to the change in construction, the merkle tree mode allowing for unbounded parallelism, and not having the SIMD-friendly version be a variant. The parallel variants of Blake2 are already _almost_ as fast as Blake3 even without the round reduction (hell, BLAKE2sp can actually be faster than Blake3 in the right conditions).
  - CiPHPerCoder 5y ago
    Worth noting that the 10 and 7 are double ChaCha rounds, which means that the strength of BLAKE3's bit diffusion is closer to ChaCha14 than ChaCha7. Given that the best attack against ChaCha fails to break ChaCha8, it's reasonable to conclude that BLAKE3 is secure.
  - masklinn 5y ago
    Merkle tree of what, file blocks?
    - thatonelutenist 5y ago
      Its section 2.1 of the paper: https://github.com/BLAKE3-team/BLAKE3-specs/blob/master/blake3.pdf https://github.com/BLAKE3-team/BLAKE3-specs/blob/master/blak... Though, note, blake3 still provides enhanced resistance against the attacks against blake2 even in the case where you only have one block, due to the change in how the fundamental hashing primitive is used.
- oconnor663 5y ago
  Reducing the rounds from 10 to 7 results in a ~10/7 = ~1.4x speedup. But single-threaded BLAKE3 is 5-6x faster than BLAKE2b, and most of that comes from SIMD optimizations. Thatonelutenist (the author of the original post) points out in a sibling comment that BLAKE2sp closes a lot of that gap, and that's very true. BLAKE2sp and BLAKE2bp can take advantage of many of the same SIMD optimizations that BLAKE3 can. But not all :) A fully optimized implementation of BLAKE2bp/sp is about 2x faster than BLAKE2b and more than 3x faster than BLAKE2s. That's an enormous speedup. Consider that SHA-3 has a reputation for being slow, but the software speed difference between SHA-512 and SHA3-256 is smaller than this. There are some complications when you get into short input performance, but any application that needs to hash files (where short input performance is dominated by the cost of opening the file) would almost certainly be better served by BLAKE2bp/sp than by BLAKE2b/s. In that sense, I think the biggest practical advantage of BLAKE3 is just that it doesn't ask users to navigate these tradeoffs. We discussed this a bit in the intro section of the BLAKE3 paper.
rdpintqogeogsaa 5y ago
Meanwhile, XChaCha20 is still stuck at the stage of being a draft at the IETF with no apparent movement for close to two years now[0]. I'd like to see it be standardized considering it's ubiquity that possibly dwarves that of pure ChaCha20. [0] https://datatracker.ietf.org/doc/draft-irtf-cfrg-xchacha/ https://datatracker.ietf.org/doc/draft-irtf-cfrg-xchacha/
- tptacek 5y ago
  On the other hand: who cares? IETF standards only matter if we let them matter. No cryptography engineer believes that XChaCha20 is problematic for lack of an RFC.
  - R0b0t1 5y ago
    Ah, but lots of middle manager types do.
    - tptacek 5y ago
      If middle managers are dictating your cryptography decisions, (1) you've got bigger problems and (2) you're using AES, not Chapoly.
      - some_furry 5y ago
        Correct: Middle managers almost universally care about NIST recommended algorithms.
        flatiron 5y ago
        "is it in tls 1.3? ok good, ship it"
    - deleted 5y ago
      [deleted]
  - rdpintqogeogsaa 5y ago
chasil 5y ago
As much as we see AES-GCM, this particular observation has concerned me: "The GCM slide provides a list of pros and cons to using GCM, none of which seem like a terribly big deal, but misses out the single biggest, indeed killer failure of the whole mode, the fact that if you for some reason fail to increment the counter, you're sending what's effectively plaintext (it's recoverable with a simple XOR). It's an incredibly brittle mode, the equivalent of the historically frighteningly misuse-prone RC4, and one I won't touch with a barge pole because you're one single machine instruction away from a catastrophic failure of the whole cryptosystem, or one single IV reuse away from the same. This isn't just theoretical, it actually happened to Colin Percival, a very experienced crypto developer, in his backup program tarsnap. You can't even salvage just the authentication from it, that fails as well with a single IV reuse ("Authentication Failures in NIST version of GCM", Antoine Joux)." https://www.metzdowd.com/pipermail/cryptography/2016-March/028824.html https://www.metzdowd.com/pipermail/cryptography/2016-March/0...
- diamondlovesyou 5y ago
  If this particular failure mode is so easy to crack, why is testing specifically for this failure mode not acceptable (ie via continuous integration testing)?
- api 5y ago
  SIV modes fix this.
  - tptacek 5y ago
    SIV mode (mostly) fixes this by (usually) jettisoning most of the benefit of using GCM in the first place, which is that it is very fast when hardware-accelerated. Compared with large random nonces, I think nonce-misuse-resistance is somewhat oversold.
    - api 5y ago
      No it doesn't. SIV is almost as fast as AES-GCM when implemented with AES-CTR and GMAC (in my benchmarks on x64 and Apple M1). It requires two passes to encrypt but on the second pass the packet is in L1 cache already. EDIT: nonce misuse resistance is IMHO a robustness thing. Yes large nonces give you similar bounds, but there are numerous banana peels like cloning VMs, live migration, IoT devices with bad PRNGs, incorrectly implemented concurrent counters, concurrent counters that work fine on x64 and fail on ARM, etc. that can cause nonce reuse. Sudden death from nonce reuse just give me the willies. Kind of a big footgun.
SAI_Peregrinus 5y ago
I don't like that the author seems to be confusing Blake3's MAC mode with HMAC. Just because it's a hash with a key that's safe to use as a MAC (and acts as a PRF) doesn't mean it's HMAC, there's no double hashing nor is there the use of the HMAC-specific padding constants. HMAC is a particular standard, not any hash-based MAC. I agree that XChaCha20+Blake3 is a good construction. It's also "easy" to make an XChaCha20-Blake3-SIV construction, by using the Blake3 MAC of the plaintext as the Nonce for XChaCha20 as well as the tag. That makes it a deterministic key-committing authenticated encryption with associated data. If you stick a 256-bit random nonce in the AAD, then you have a full Authenticated Hedged Encryption with Associated Data (AHEAD) system. The disadvantage is (as always with SIV-like constructions) that it's two-pass, so not suitable for streaming encryption, but still good for quite a few uses and a bit safer than non-deterministic AEADs.
- thatonelutenist 5y ago
  That's a valid point on wording, that I tried to toe carefully with the "effectively an HMAC", as this post was written for a more general audience and I didn't want to go too far into the details, I wrote it to have something to point to when the inevitable questions roll in. Balancing the lies-to-children is always a hard job
  - SAI_Peregrinus 5y ago
    I'd just say it's 'effectively a MAC ("eg HMAC")'. Small but important distinction.
  - stouset 5y ago
    What's your perspective on reusing the same key between XChaCha20 and Blake3 invocations? While not necessarily a footgun in practice, reusing the same key between two contexts is generally avoided as a matter of good cryptographic hygiene. You could either require a single larger key that's (effectively) a key for each cipher concatenated with one-another, or use one 256-bit key from which you derive independent keys via a pass through the hashing function. I personally prefer something closer to the former, since it requires less cryptography in general and there aren't many situations where you're sweating the size difference between 512-bit keys vs. 256-bit keys. I suspect most systems implementing XChaCha20+Blake3 just reuse the key, which is probably fine... but it leaves a bad taste in my mouth and seems like just another potential risk that's not all that difficult to sidestep. And we're going to feel really dumb one day if it turns out there is a way to exploit that kind of key reuse after all.
searealist 5y ago
If you are using the reduced rounds of Blake3, seems like you might as well also go to XChaCha12 or XChaCha8?
- loeg 5y ago
  I.e., as one of the Blake3 authors calls for in Too Much Crypto (2019)[1] (8-round ChaCha in particular). There is a 2021 update in the Conclusion section: > Edit (May 24, 2021): 17 months after the original publication of this paper, its most concrete impact seems to be the adoption of ChaCha8 in a number of projects, notably thanks to its addition to the chacha20 crate of the RustCrypto project. We are not aware of new research results contradicting the paper’s claims, nor of results that would justify (from our point of view) a revision of the proposed reduced-round versions in §§5.3. [1]: https://eprint.iacr.org/2019/1492.pdf https://eprint.iacr.org/2019/1492.pdf (PDF)
some_furry 5y ago
This isn't an AEAD, it's just AE. AEAD implies the support for additional Authenticated Data (AD); this is just Encrypt-them-MAC, which is a good construction for authenticated encryption, but it's not AEAD (by definition). If you want an AEAD, I designed one based on ChaCha20 and BLAKE3 as a proof-of-concept a while ago: https://github.com/soatok/experimental-caead https://github.com/soatok/experimental-caead The important details: 1. You need to split a single key into 2 distinct keys (1 for [X]ChaCha, 1 for BLAKE3). 2. You need a canonical way to feed the ciphertext and AAD into BLAKE3. 3. You need to ensure your MACs are compared in constant-time. The GitHub repository I linked above does all this.
- thatonelutenist 5y ago
  The library that this was written for does in fact do all of the above, and I actually did look at your library for inspiration when I was doing background research. Big fan of your blog by the way. Though given the blog post is devoid of the context, and its apparently blown up a little, this is a valid wording concern and I'll edit the title.
- tptacek 5y ago
  I think this is an interesting conversation, but as normative feedback it seems pretty pedantic. The "AAD" in "AEAD" is message metadata; canonically, it's stuff like sequence numbers and metadata that appear in headers that need to be in cleartext to make transports work. Another example: Chapoly AAD is used to incorporate the transcript hash into every AEAD invocation of the WireGuard handshake. It seems like the obvious way you'd get AAD into generically-composed ChaCha+Blake is simply to include it in the Blake KMAC along with the ciphertext. In other words: the obvious way. Is there a footgun here that doesn't have an equivalent in GCM? I don't see it. The KDF point doesn't really have anything to do with AAD, right --- all you're saying here is that you need to KDF the ChaCha and Blake keys. I guess you're pointing out that GCM and Chapoly effectively do this for you in library implementations. Which, sure.
  - some_furry 5y ago
    > The KDF point doesn't really have anything to do with AAD, right --- all you're saying here is that you need to KDF the ChaCha and Blake keys. I guess you're pointing out that GCM and Chapoly effectively do this for you in library implementations. Which, sure. The motivation for the KDF point is just to ensure we're not using the same key for two different algorithms. This condition almost never leads to any practical security risks (unless you're, I dunno, mixing AES-CBC with CBC-MAC?), but it makes people who care a lot about security proofs happier if we avoid it.
nayuki 5y ago
> and how the [AES] block size is too small > The block size [of ChaCha20] is 512 bits, compared to AES’s 128 bits, making a wide variety of attacks, such as birthday bound or PRP-PRF distinguishing attacks many orders of magnitude less practical It's too bad the AES competition didn't accept Rijndael's option of 256-bit block size. I wonder why? ( https://en.wikipedia.org/wiki/Advanced_Encryption_Standard#cite_note-blocksize-2 https://en.wikipedia.org/wiki/Advanced_Encryption_Standard#c... )
- some_furry 5y ago
  IIRC, the AES competition specifically called for a 128-bit block size, citing the hardware requirements of that era. (This is an invitation to invoke Cunningham's Law if I'm misremembering.)
- tptacek 5y ago
  The 16 byte block size was part of the brief for the AES competition; it was established before Rijndael was selected.
gjs278 5y ago
these are all terrible names and acronyms
Rebelgecko 5y ago
Is OCB usage picking up now that it's no longer patent-encumbered? IIRC it has great performance compared to other AEAD methods
- formerly_proven 5y ago
  Yes, OCB is still around 50 % faster than the next best[1] AEAD (which is AES-GCM) and almost 3x faster than Chapoly on current x86 and comes pretty close to 10 GB/s/core on a desktop CPU. That being said, all of these are really, really fast in absolute terms, way beyond line-rate even for 10 GbE, which is a measly 1.2 GB/s. In practical terms, all of these modern algorithms are so fast (with hardware support for AES) that very few applications will see a significant burden from symmetric crypto, so you can choose pretty much whatever you feel comfortable with. EtM was usually quite a bit worse, as the hashes used for hMac were usually much slower in comparison. Though Blake3 would seem to eliminate that concern. [1] in terms of performance, on a modern x86, with AES-NI
  - Monory 5y ago
    More and more both personal computers and servers are using ARM CPUs without AES acceleration, though. Also, write speeds of modern SSDs comes to be over 5 GBps.
    - formerly_proven 5y ago
      > More and more both personal computers and servers are using ARM CPUs without AES acceleration, though. The RPi SoC is an exception here - most ARMv8 SoCs should have AES instructions. > Also, write speeds of modern SSDs comes to be over 5 GBps. True, but I don't think the expectation is to utilize that throughput with a single application, rather, to still have fast I/O even under load or with multiple applications, and to satisfy burst I/O quickly.
- CiPHPerCoder 5y ago
  OCB isn't committing, so it doesn't solve the stated problem.
oconnor663 5y ago
> Blake3 is fast, several times faster than ChaCha20 on my machine The speed differences between BLAKE3 and ChaCha20 depend a lot on what benchmarks you run, and I want to elaborate a bit on the details, in case anyone running benchmarks sees something different and wonders why. The whole BLAKE family is derived from ChaCha, and there are some close performance relationships between them. As CiPHPerCoder pointed out in another comment, what the BLAKE family calls "rounds" are what ChaCha calls "doublerounds", so we need to multiply by two to compare them. Since BLAKE3 does 7 rounds, its performance should be vaguely similar to ChaCha14, or a factor of ~20/14 faster than ChaCha20. SIMD optimizations matter an enormous amount here. An implementation of BLAKE3 or ChaCha20 using recent AVX-512 SIMD instructions and running on a CPU that supports them, can be an order of magnitude faster than a generic implementation. This affects both functions equally, but it means that you need to be very carful when benchmarking, to make sure that the implementations you're testing have all been similarly optimized. One wrinkle here is that, even if BLAKE3 and ChaCha20 are both implementated with AVX-512 optimizations, ChaCha20 will be able to take advantage of many of those optimizations at smaller input sizes. That's because each 64-byte ChaCha20 output block is independent of all the others, so full AVX-512 parallelism can kick in at 16*64 = 1024 bytes of output. (The number 16 comes from the fact that ChaCha20 and BLAKE3 use 32-bit words, and 16 of those words fit in a 512-bit vector.) In contrast, BLAKE3 on the input side needs to parallelize 1024-byte chunks/leaves, rather than individual blocks, so it needs 16*1024 = 16384 bytes of input to reach the same degree of parallelism. So if you benchmark an input size below 16 KiB, you might find that ChaCha20 is faster for that reason. (Note that BLAKE3's output side is more similar to ChaCha20 than it is to BLAKE3's input side. But in practice the official BLAKE3 implementations have some missing optimizations in the XOF.) Another difference that will come up is multithreading. Both BLAKE3 and ChaCha20 can be multithreaded in theory, but multithreading ChaCha20 is almost never done. This is for a few reasons: 1) BLAKE3's multithreading capabilities have to do with its Merkle tree structure and are one of the things that make it special, so of course the official implementation wants to showcase that. In contrast, any block-based stream cipher like AES-CTR or ChaCha20 can be trivially multithreaded, and it's not very interesting to demonstrate it. 2) Hashing gigantic files is something we actually need to do sometimes, and multithreading can be beneficial in that use case, when we don't have a read bottleneck. In contrast, encrypting a gigantic file is pretty rare, and it tends to involve prohibitive memory requirements and/or an output bottleneck. Most encrypted ciphertexts tend to be pretty small, like TLS records, and it's rare to have a good use case for multithreaded ChaCha20. So if you're benchmarking BLAKE3 (b3sum) against large input files, there's a good chance your benchmark is benefitting from multithreading. But if you try to encrypt the same file, and you manage not to have an output bottleneck, your ChaCha20 implementation almost certainly isn't multithreaded. So that's another thing we need to be careful about when we compare them.
upofadown 5y ago
>10. Even AES256 has a block size of 128 bits, which means you can start expecting collisions after 2^64 encryptions. This sounds like a lot, and the exact details of how this can cause a mode of operation to break down depend on the particular mode, but that’s a not an unachievable amount of data, the internet does that much every few months (assuming 1 block per encryption)... Correct me if I am wrong, but doesn't the fact that the internet is not encrypting everything with the same key and nonce mean that you can't just add up all the data transferred for this? Or does this mean that in the future we might be encrypting 256 EB(10^18) sessions/files?
- aidenn0 5y ago
  It's giving an idea of the order of magnitude. Kind of like comparing outputs of an industry to outputs of countries. It's also an argument that we are within a few orders of magnitude of it mattering today, so therefore tomorrow we could be in trouble.
- thatonelutenist 5y ago
  Of course you can't, its just a visual aid. The point is to say that if a cipher _completely_ breaks down at (some imaginable amount of data), then its probably not behaving itself too well at (some much more reasonable, but still large, amount of data). AES-CTR already starts to questionable in some respects at 2^40 encryption with the same key (nonce isn't relevant, it changes with every block anyway), which is only 128TiB. Sure that's a lot for the average joe, but one could eaisly imagine someone wanting to encrypt that much data with a single key, just go checkout /r/datahoarder if you don't believe me. And sure, good key rotation fixes that, but that's another foot-gun, and how should the average end user know if their application is using proper key rotation or not?
staticassertion 5y ago
So the major reason to not use this is... that no one does this. Right? I wrote up an implementation of this and it was fairly trivial. The properties all make sense - the main change here is swapping poly1305 for blake3. But BLAKE3 promises (and we seem to trust this!) everything Poly1305 does and collision resistance.

127 points by vlmutolo 5y ago

cjg 5y ago

"8. Source: My Ass" :-)

Not my blog. Author works on a backup/archival tool called "Asuran", which I assume motivates a lot of the research into AEAD. I had never heard of the "partitioning oracle" attack, which is a really interesting way to exploit Poly1305 tags under certain conditions. I never would have assumed that it's practical to generate multiple ciphertexts that all authenticate under the same Poly1305 tag. That property leads to some interesting attacks.

Aachen 5y ago
You might also be interested in RSA blind signatures. They hardly ever come up so I was surprised to learn what seemed like an important property years after I thought I knew what RSA did.

speedgoose 5y ago

In my understanding, Blake3 is fast mostly because it does fewer rounds than blake2. The logic is that there is no need to be conservative in the number of rounds because the current public attacks work only on few rounds so we can just do a bit more rounds and be good. I personally avoid Blake3 and stick with blake2.

thatonelutenist 5y ago
It's a bit more complicated than that. Yes, the core of blake3 is a modified blake2b with fewer rounds, and yes the person who wrote the "Too much Crypto" paper is one of the blake authors, but there are other aspects of the construction that contribute as well. Blake3 operates in a merkle tree mode using the modified blake2 as a node hashing function, which, in and of itself complicates attacks for reasons explained in the blake3 paper. Blake2 also didn't really have that many rounds to start with, Blake3 only reduces the round count from 10 to 7. A good _most_ of the speedup in Blake3 is due to the change in construction, the merkle tree mode allowing for unbounded parallelism, and not having the SIMD-friendly version be a variant. The parallel variants of Blake2 are already _almost_ as fast as Blake3 even without the round reduction (hell, BLAKE2sp can actually be faster than Blake3 in the right conditions).
- CiPHPerCoder 5y ago
  Worth noting that the 10 and 7 are double ChaCha rounds, which means that the strength of BLAKE3's bit diffusion is closer to ChaCha14 than ChaCha7. Given that the best attack against ChaCha fails to break ChaCha8, it's reasonable to conclude that BLAKE3 is secure.
- masklinn 5y ago
  Merkle tree of what, file blocks?
  - thatonelutenist 5y ago
    Its section 2.1 of the paper: https://github.com/BLAKE3-team/BLAKE3-specs/blob/master/blake3.pdf https://github.com/BLAKE3-team/BLAKE3-specs/blob/master/blak... Though, note, blake3 still provides enhanced resistance against the attacks against blake2 even in the case where you only have one block, due to the change in how the fundamental hashing primitive is used.
oconnor663 5y ago
Reducing the rounds from 10 to 7 results in a ~10/7 = ~1.4x speedup. But single-threaded BLAKE3 is 5-6x faster than BLAKE2b, and most of that comes from SIMD optimizations. Thatonelutenist (the author of the original post) points out in a sibling comment that BLAKE2sp closes a lot of that gap, and that's very true. BLAKE2sp and BLAKE2bp can take advantage of many of the same SIMD optimizations that BLAKE3 can. But not all :) A fully optimized implementation of BLAKE2bp/sp is about 2x faster than BLAKE2b and more than 3x faster than BLAKE2s. That's an enormous speedup. Consider that SHA-3 has a reputation for being slow, but the software speed difference between SHA-512 and SHA3-256 is smaller than this. There are some complications when you get into short input performance, but any application that needs to hash files (where short input performance is dominated by the cost of opening the file) would almost certainly be better served by BLAKE2bp/sp than by BLAKE2b/s. In that sense, I think the biggest practical advantage of BLAKE3 is just that it doesn't ask users to navigate these tradeoffs. We discussed this a bit in the intro section of the BLAKE3 paper.

rdpintqogeogsaa 5y ago

Meanwhile, XChaCha20 is still stuck at the stage of being a draft at the IETF with no apparent movement for close to two years now[0]. I'd like to see it be standardized considering it's ubiquity that possibly dwarves that of pure ChaCha20. [0] https://datatracker.ietf.org/doc/draft-irtf-cfrg-xchacha/ https://datatracker.ietf.org/doc/draft-irtf-cfrg-xchacha/

tptacek 5y ago
On the other hand: who cares? IETF standards only matter if we let them matter. No cryptography engineer believes that XChaCha20 is problematic for lack of an RFC.
- R0b0t1 5y ago
  Ah, but lots of middle manager types do.
  - tptacek 5y ago
    If middle managers are dictating your cryptography decisions, (1) you've got bigger problems and (2) you're using AES, not Chapoly.
    - some_furry 5y ago
      Correct: Middle managers almost universally care about NIST recommended algorithms.
      - flatiron 5y ago
        "is it in tls 1.3? ok good, ship it"
  - deleted 5y ago
    [deleted]
- rdpintqogeogsaa 5y ago

chasil 5y ago

As much as we see AES-GCM, this particular observation has concerned me: "The GCM slide provides a list of pros and cons to using GCM, none of which seem like a terribly big deal, but misses out the single biggest, indeed killer failure of the whole mode, the fact that if you for some reason fail to increment the counter, you're sending what's effectively plaintext (it's recoverable with a simple XOR). It's an incredibly brittle mode, the equivalent of the historically frighteningly misuse-prone RC4, and one I won't touch with a barge pole because you're one single machine instruction away from a catastrophic failure of the whole cryptosystem, or one single IV reuse away from the same. This isn't just theoretical, it actually happened to Colin Percival, a very experienced crypto developer, in his backup program tarsnap. You can't even salvage just the authentication from it, that fails as well with a single IV reuse ("Authentication Failures in NIST version of GCM", Antoine Joux)." https://www.metzdowd.com/pipermail/cryptography/2016-March/028824.html https://www.metzdowd.com/pipermail/cryptography/2016-March/0...

diamondlovesyou 5y ago
If this particular failure mode is so easy to crack, why is testing specifically for this failure mode not acceptable (ie via continuous integration testing)?
api 5y ago
SIV modes fix this.
- tptacek 5y ago
  SIV mode (mostly) fixes this by (usually) jettisoning most of the benefit of using GCM in the first place, which is that it is very fast when hardware-accelerated. Compared with large random nonces, I think nonce-misuse-resistance is somewhat oversold.
  - api 5y ago
    No it doesn't. SIV is almost as fast as AES-GCM when implemented with AES-CTR and GMAC (in my benchmarks on x64 and Apple M1). It requires two passes to encrypt but on the second pass the packet is in L1 cache already. EDIT: nonce misuse resistance is IMHO a robustness thing. Yes large nonces give you similar bounds, but there are numerous banana peels like cloning VMs, live migration, IoT devices with bad PRNGs, incorrectly implemented concurrent counters, concurrent counters that work fine on x64 and fail on ARM, etc. that can cause nonce reuse. Sudden death from nonce reuse just give me the willies. Kind of a big footgun.

SAI_Peregrinus 5y ago

I don't like that the author seems to be confusing Blake3's MAC mode with HMAC. Just because it's a hash with a key that's safe to use as a MAC (and acts as a PRF) doesn't mean it's HMAC, there's no double hashing nor is there the use of the HMAC-specific padding constants. HMAC is a particular standard, not any hash-based MAC. I agree that XChaCha20+Blake3 is a good construction. It's also "easy" to make an XChaCha20-Blake3-SIV construction, by using the Blake3 MAC of the plaintext as the Nonce for XChaCha20 as well as the tag. That makes it a deterministic key-committing authenticated encryption with associated data. If you stick a 256-bit random nonce in the AAD, then you have a full Authenticated Hedged Encryption with Associated Data (AHEAD) system. The disadvantage is (as always with SIV-like constructions) that it's two-pass, so not suitable for streaming encryption, but still good for quite a few uses and a bit safer than non-deterministic AEADs.

thatonelutenist 5y ago
That's a valid point on wording, that I tried to toe carefully with the "effectively an HMAC", as this post was written for a more general audience and I didn't want to go too far into the details, I wrote it to have something to point to when the inevitable questions roll in. Balancing the lies-to-children is always a hard job
- SAI_Peregrinus 5y ago
  I'd just say it's 'effectively a MAC ("eg HMAC")'. Small but important distinction.
- stouset 5y ago
  What's your perspective on reusing the same key between XChaCha20 and Blake3 invocations? While not necessarily a footgun in practice, reusing the same key between two contexts is generally avoided as a matter of good cryptographic hygiene. You could either require a single larger key that's (effectively) a key for each cipher concatenated with one-another, or use one 256-bit key from which you derive independent keys via a pass through the hashing function. I personally prefer something closer to the former, since it requires less cryptography in general and there aren't many situations where you're sweating the size difference between 512-bit keys vs. 256-bit keys. I suspect most systems implementing XChaCha20+Blake3 just reuse the key, which is probably fine... but it leaves a bad taste in my mouth and seems like just another potential risk that's not all that difficult to sidestep. And we're going to feel really dumb one day if it turns out there is a way to exploit that kind of key reuse after all.

searealist 5y ago

If you are using the reduced rounds of Blake3, seems like you might as well also go to XChaCha12 or XChaCha8?

loeg 5y ago
I.e., as one of the Blake3 authors calls for in Too Much Crypto (2019)[1] (8-round ChaCha in particular). There is a 2021 update in the Conclusion section: > Edit (May 24, 2021): 17 months after the original publication of this paper, its most concrete impact seems to be the adoption of ChaCha8 in a number of projects, notably thanks to its addition to the chacha20 crate of the RustCrypto project. We are not aware of new research results contradicting the paper’s claims, nor of results that would justify (from our point of view) a revision of the proposed reduced-round versions in §§5.3. [1]: https://eprint.iacr.org/2019/1492.pdf https://eprint.iacr.org/2019/1492.pdf (PDF)

some_furry 5y ago

This isn't an AEAD, it's just AE. AEAD implies the support for additional Authenticated Data (AD); this is just Encrypt-them-MAC, which is a good construction for authenticated encryption, but it's not AEAD (by definition). If you want an AEAD, I designed one based on ChaCha20 and BLAKE3 as a proof-of-concept a while ago: https://github.com/soatok/experimental-caead https://github.com/soatok/experimental-caead The important details: 1. You need to split a single key into 2 distinct keys (1 for [X]ChaCha, 1 for BLAKE3). 2. You need a canonical way to feed the ciphertext and AAD into BLAKE3. 3. You need to ensure your MACs are compared in constant-time. The GitHub repository I linked above does all this.

thatonelutenist 5y ago
The library that this was written for does in fact do all of the above, and I actually did look at your library for inspiration when I was doing background research. Big fan of your blog by the way. Though given the blog post is devoid of the context, and its apparently blown up a little, this is a valid wording concern and I'll edit the title.
tptacek 5y ago
I think this is an interesting conversation, but as normative feedback it seems pretty pedantic. The "AAD" in "AEAD" is message metadata; canonically, it's stuff like sequence numbers and metadata that appear in headers that need to be in cleartext to make transports work. Another example: Chapoly AAD is used to incorporate the transcript hash into every AEAD invocation of the WireGuard handshake. It seems like the obvious way you'd get AAD into generically-composed ChaCha+Blake is simply to include it in the Blake KMAC along with the ciphertext. In other words: the obvious way. Is there a footgun here that doesn't have an equivalent in GCM? I don't see it. The KDF point doesn't really have anything to do with AAD, right --- all you're saying here is that you need to KDF the ChaCha and Blake keys. I guess you're pointing out that GCM and Chapoly effectively do this for you in library implementations. Which, sure.
- some_furry 5y ago
  > The KDF point doesn't really have anything to do with AAD, right --- all you're saying here is that you need to KDF the ChaCha and Blake keys. I guess you're pointing out that GCM and Chapoly effectively do this for you in library implementations. Which, sure. The motivation for the KDF point is just to ensure we're not using the same key for two different algorithms. This condition almost never leads to any practical security risks (unless you're, I dunno, mixing AES-CBC with CBC-MAC?), but it makes people who care a lot about security proofs happier if we avoid it.

nayuki 5y ago

> and how the [AES] block size is too small > The block size [of ChaCha20] is 512 bits, compared to AES’s 128 bits, making a wide variety of attacks, such as birthday bound or PRP-PRF distinguishing attacks many orders of magnitude less practical It's too bad the AES competition didn't accept Rijndael's option of 256-bit block size. I wonder why? ( https://en.wikipedia.org/wiki/Advanced_Encryption_Standard#cite_note-blocksize-2 https://en.wikipedia.org/wiki/Advanced_Encryption_Standard#c... )

some_furry 5y ago
IIRC, the AES competition specifically called for a 128-bit block size, citing the hardware requirements of that era. (This is an invitation to invoke Cunningham's Law if I'm misremembering.)
tptacek 5y ago
The 16 byte block size was part of the brief for the AES competition; it was established before Rijndael was selected.

gjs278 5y ago

these are all terrible names and acronyms

Rebelgecko 5y ago

Is OCB usage picking up now that it's no longer patent-encumbered? IIRC it has great performance compared to other AEAD methods

formerly_proven 5y ago
Yes, OCB is still around 50 % faster than the next best[1] AEAD (which is AES-GCM) and almost 3x faster than Chapoly on current x86 and comes pretty close to 10 GB/s/core on a desktop CPU. That being said, all of these are really, really fast in absolute terms, way beyond line-rate even for 10 GbE, which is a measly 1.2 GB/s. In practical terms, all of these modern algorithms are so fast (with hardware support for AES) that very few applications will see a significant burden from symmetric crypto, so you can choose pretty much whatever you feel comfortable with. EtM was usually quite a bit worse, as the hashes used for hMac were usually much slower in comparison. Though Blake3 would seem to eliminate that concern. [1] in terms of performance, on a modern x86, with AES-NI
- Monory 5y ago
  More and more both personal computers and servers are using ARM CPUs without AES acceleration, though. Also, write speeds of modern SSDs comes to be over 5 GBps.
  - formerly_proven 5y ago
    > More and more both personal computers and servers are using ARM CPUs without AES acceleration, though. The RPi SoC is an exception here - most ARMv8 SoCs should have AES instructions. > Also, write speeds of modern SSDs comes to be over 5 GBps. True, but I don't think the expectation is to utilize that throughput with a single application, rather, to still have fast I/O even under load or with multiple applications, and to satisfy burst I/O quickly.
CiPHPerCoder 5y ago
OCB isn't committing, so it doesn't solve the stated problem.

oconnor663 5y ago

> Blake3 is fast, several times faster than ChaCha20 on my machine The speed differences between BLAKE3 and ChaCha20 depend a lot on what benchmarks you run, and I want to elaborate a bit on the details, in case anyone running benchmarks sees something different and wonders why. The whole BLAKE family is derived from ChaCha, and there are some close performance relationships between them. As CiPHPerCoder pointed out in another comment, what the BLAKE family calls "rounds" are what ChaCha calls "doublerounds", so we need to multiply by two to compare them. Since BLAKE3 does 7 rounds, its performance should be vaguely similar to ChaCha14, or a factor of ~20/14 faster than ChaCha20. SIMD optimizations matter an enormous amount here. An implementation of BLAKE3 or ChaCha20 using recent AVX-512 SIMD instructions and running on a CPU that supports them, can be an order of magnitude faster than a generic implementation. This affects both functions equally, but it means that you need to be very carful when benchmarking, to make sure that the implementations you're testing have all been similarly optimized. One wrinkle here is that, even if BLAKE3 and ChaCha20 are both implementated with AVX-512 optimizations, ChaCha20 will be able to take advantage of many of those optimizations at smaller input sizes. That's because each 64-byte ChaCha20 output block is independent of all the others, so full AVX-512 parallelism can kick in at 16*64 = 1024 bytes of output. (The number 16 comes from the fact that ChaCha20 and BLAKE3 use 32-bit words, and 16 of those words fit in a 512-bit vector.) In contrast, BLAKE3 on the input side needs to parallelize 1024-byte chunks/leaves, rather than individual blocks, so it needs 16*1024 = 16384 bytes of input to reach the same degree of parallelism. So if you benchmark an input size below 16 KiB, you might find that ChaCha20 is faster for that reason. (Note that BLAKE3's output side is more similar to ChaCha20 than it is to BLAKE3's input side. But in practice the official BLAKE3 implementations have some missing optimizations in the XOF.) Another difference that will come up is multithreading. Both BLAKE3 and ChaCha20 can be multithreaded in theory, but multithreading ChaCha20 is almost never done. This is for a few reasons: 1) BLAKE3's multithreading capabilities have to do with its Merkle tree structure and are one of the things that make it special, so of course the official implementation wants to showcase that. In contrast, any block-based stream cipher like AES-CTR or ChaCha20 can be trivially multithreaded, and it's not very interesting to demonstrate it. 2) Hashing gigantic files is something we actually need to do sometimes, and multithreading can be beneficial in that use case, when we don't have a read bottleneck. In contrast, encrypting a gigantic file is pretty rare, and it tends to involve prohibitive memory requirements and/or an output bottleneck. Most encrypted ciphertexts tend to be pretty small, like TLS records, and it's rare to have a good use case for multithreaded ChaCha20. So if you're benchmarking BLAKE3 (b3sum) against large input files, there's a good chance your benchmark is benefitting from multithreading. But if you try to encrypt the same file, and you manage not to have an output bottleneck, your ChaCha20 implementation almost certainly isn't multithreaded. So that's another thing we need to be careful about when we compare them.

upofadown 5y ago

>10. Even AES256 has a block size of 128 bits, which means you can start expecting collisions after 2^64 encryptions. This sounds like a lot, and the exact details of how this can cause a mode of operation to break down depend on the particular mode, but that’s a not an unachievable amount of data, the internet does that much every few months (assuming 1 block per encryption)... Correct me if I am wrong, but doesn't the fact that the internet is not encrypting everything with the same key and nonce mean that you can't just add up all the data transferred for this? Or does this mean that in the future we might be encrypting 256 EB(10^18) sessions/files?

aidenn0 5y ago
It's giving an idea of the order of magnitude. Kind of like comparing outputs of an industry to outputs of countries. It's also an argument that we are within a few orders of magnitude of it mattering today, so therefore tomorrow we could be in trouble.
thatonelutenist 5y ago
Of course you can't, its just a visual aid. The point is to say that if a cipher _completely_ breaks down at (some imaginable amount of data), then its probably not behaving itself too well at (some much more reasonable, but still large, amount of data). AES-CTR already starts to questionable in some respects at 2^40 encryption with the same key (nonce isn't relevant, it changes with every block anyway), which is only 128TiB. Sure that's a lot for the average joe, but one could eaisly imagine someone wanting to encrypt that much data with a single key, just go checkout /r/datahoarder if you don't believe me. And sure, good key rotation fixes that, but that's another foot-gun, and how should the average end user know if their application is using proper key rotation or not?

staticassertion 5y ago

So the major reason to not use this is... that no one does this. Right? I wrote up an implementation of this and it was fairly trivial. The properties all make sense - the main change here is swapping poly1305 for blake3. But BLAKE3 promises (and we seem to trust this!) everything Poly1305 does and collision resistance.