Why I Have Settled on XChaCha20+Blake3 for AEAD
mccarty.io
mccarty.io
"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/0...
Compared with large random nonces, I think nonce-misuse-resistance is somewhat oversold.
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.
A nice property of the XChaCha+Blake scheme proposed here is that Blake doesn't have any nonce dependency at all, and most of the terror of nonce misuse comes from how the MAC deals with repeated nonces, not how the underlying stream cipher does (though, obviously, a reliably repeating nonce gives you a pretty devastating confidentiality failure).
I think most people would agree about that if you omit parts of cryptographic algorithms, it is not surprising that it's now broken.
Also who even implements GCM by hand? Who's supposed to forget to increment that counter?
> the equivalent of the historically frighteningly misuse-prone RC4
Libraries let you call RC4(data, key) and it would work as designed. It was up to you to realize that you shouldn't reuse the key. With GCM, incrementing the counter is done in the library and not exposed for you to forget.
Don't roll your own crypto is the only takeaway here.
(You can't really forget to increment the underlying CTR counter; your system won't work.)
GCM has two counters, the message-block-counter (4 bytes), and the message counter / nonce (12 bytes). The former is inside the crypto library, the latter is supplied by the client and can be mismanaged like any other IV.
For more info see for example:
* https://www.cs.uaf.edu/2012/fall/cs441/students/sc_ps3.pdf
* A presentation at CCC about how hackers broke the different security features or PS3 including ECDSA https://media.ccc.de/v/27c3-4087-en-console_hacking_2010#t=2...
"Everything else sucks" is why I "settle" for volunteer-supported, free, UNIX-like OS. It is why I "settle" for using djb's software (the stuff IETF would never approve of, not just the crypto work). It does not mean I think that these solutions are ideal in any objective sense. It means "everything else sucks". And when these solutions help me avoid the pain of having to use "everything else", then it stands to reason they will appear not only better than everything else but even high quality in an objective sense. (To use Gutmann's analogy, the oasis looks refreshing, regardless of the actual water quality.)
Another example are the discussions on the k language/intepreter on HN. Commenters would focus on crticisms of k instead of considering why other solutions cannot achieve the same performance. As one person put it, the question should not be "Why is this so concise and fast?" but "Why is everything else so bloated and slow?" (paraphrasing)
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.
Balancing the lies-to-children is always a hard job
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.
But the point of my question wasn't necessarily to debate those two approaches as much as it was to politely bring up the detail of using independent keys for each cipher. I'm not sure I'd necessarily call it a footgun as much as I would call it proper hygiene.
XChaCha20+Blake3 as an encrypt-then-mac AEAD is just simple enough that people might think to wire it up themselves.
One of the nice things about Blake3 is that it does have a KDF mode built in. And a MAC mode. And there's a (stalled) proposal to build in an AHEAD mode, though IMO it needs more academic security analysis (IIRC that's part of why it stalled). It might not be as interestingly innovative as the sponge construction Keccak introduced, but it's a very versatile primitive with excellent software performance.
The SIV modes are great, they're much easier to use. When used in a full AHEAD construction (where you stick a random nonce in the AAD of a deterministic AEAD) you get nearly a "best of both worlds" non-deterministic encryption but without the catastrophic failure properties of something like GCM. But they're inherently 2-pass. So the user might have to deal with "chunking" their data, which can be annoying if they're streaming, etc. And since there are two passes over the plaintext with two different algorithms (one for the MAC to make the SIV, one to encrypt) that's two "traces" a side-channel observing attacker has which can make some attacks more powerful.
[0] https://datatracker.ietf.org/doc/draft-irtf-cfrg-xchacha/
This is actually how it's supposed to work: RFCs are meant, at least somewhat routinely, to trail implementations. "Loose consensus and working code" used to be the motto. Get XChaCha20 deployed, and then let the IETF standardize it because they have to. That's what happened with Curve25519.
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.
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
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.
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.
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.
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.
I think that's a good argument against just composing constructions "on the fly" casually, but to me, there are some kind of clear benefits to replacing the poly mac in Chapoly with a hash KMAC; it's worth going through this exercise (maybe just once) and then considering using it instead of a "standard" AEAD.
By way of example: with the KDF and encoding --- which you can pull from x/crypto --- it seems like you could pretty easily make this proposed system fit Golang's AEAD interface.
Next time it will be title text.
Maaaybe- if you're doing the composition yourself.
You have to differentiate between the AAD and the ciphertext somehow, and you can screw that up (e.g. not putting the split location in the AD, sending it unauthenticated instead), while if you're using somebody else's GCM implementation they hopefully handle this correctly.
If somebody tells you to "do AEAD with this block cipher and this generic MAC", it's tempting to just ... find an implementation of the block cipher, find an implementation of the MAC, and play legos- neglecting subtleties like the split location, proper key derivation, etc.
It's far less tempting to implement GCM by composing implementations of CTR and GMAC because ... where would you even find an implementation of GMAC that's not part of a GCM implementation anyways?
I personally avoid Blake3 and stick with blake2.
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).
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.
Given that the best attack against ChaCha fails to break ChaCha8, it's reasonable to conclude that BLAKE3 is secure.
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.
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.
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?
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?
> 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#c... )
(This is an invitation to invoke Cunningham's Law if I'm misremembering.)
[1] in terms of performance, on a modern x86, with AES-NI
Also, write speeds of modern SSDs comes to be over 5 GBps.
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.
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.
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 (PDF)