Understanding Extended-Nonce Constructions

Most of the data encrypted on the Internet these days uses an AEAD mode, which consists of a stream cipher (which may be built out of a hash function or a block cipher) and a polynomial authenticator (in this order: Encrypt, then Authenticate).

This very loose description of an AEAD mode can describe both AES-GCM and ChaCha20-Poly1305 (although they are very different under-the-hood).

The AEAD modes used to secure most of the Internet has one glaring weakness: If you reuse a nonce, your messages can be decrypted with simple algebra. (In the case of AES-GCM, but not ChaCha20-Poly1305, this kind of misuse allows attackers to also henceforth forge packets at your whim. I don’t like AES-GCM.)

This is a known problem to cryptographers, and there are a couple of solutions for it.

Nonce Misuse-Resistant Authenticated Encryption

The first solution is to use a nonce misuse-resistant mode, such as AES-GCM-SIV, which prevents cryptanalytic attacks from a limited number of nonce reuses for different messages. These constructions are relatively new and less-studied than their contemporary counterparts, but as time goes on we’re slowly accumulating confidence in their security. However, their performance characteristics are a little disappointing.

AES-GCM-SIV is about 70% of the speed in the encrypt path than AES-GCM, but successful decryption is approximately the same speed (since this additional overhead is used to calculate the authentication tag, which is already available to decryptors).

However, the rejection of forged messages in AES-GCM-SIV requires first decrypting the entire message and then recalculating the tag from the message and the authentication key, then comparing it with the provided key.

In AES-GCM, you reject invalid messages before decryption. AES-GCM-SIV is Authenticate-then-Encrypt, instead of Encrypt-then-Authenticate. This two-pass rejection is an additional performance penalty that isn’t often considered by users of nonce misuse-resistant modes.

Extended-Nonce Constructions

The other solution is to use a variant of an existing AEAD mode that accepts an extended nonce–one large enough that users can generate it randomly and never risk collisions in a practical setting.

For example, ChaCha20-Poly1305 accepts a 256-bit key and 96-bit nonce (with an internal 32-bit block counter). If you generate the nonce randomly, you should expect a collision with probability 2^-32 after 2^32 messages.

An extended-nonce variant of ChaCha20-Poly1305, called XChaCha20-Poly1305, accepts a 256-bit key and 192-bit nonce (with an internal 32-bit block counter). Consequently, if you generate a 192-bit nonce randomly, your 2^-32 collision probability occurs after 2^80 messages rather than 2^32.

We’ve talked about these modes before (as evidenced by the links to previous blog posts), but we’ve never really dived into how they work or why they were designed the way they are. So let’s explore this topic and the answers to those questions.

Extended-Nonce Stream Ciphers

For the purposes of this discussion, I’m mostly going to be describing XChaCha (although congruent arguments, and a more readily available security proof, exist for XSalsa20). You could likely adopt these arguments to support an extended-nonce AEAD that works with NIST algorithms exclusively (e.g. SHA-512 and AES-256-GCM, as purely a toy example).

To understand what’s really happening, we need to first take a look at the underlying cipher (n.b. ChaCha), with special attention to its assumptions and the arguments for its security. This might sound intimidating, but I promise it will make sense without needing a Ph.D.

Once we have a feel for the underlying cipher, we need to explore some of the more obvious ways to extend a nonce, and then explain why they’re a bad idea.

Once we have an intuition for all that, we can look at how XSalsa20 and XChaCha were designed, and argue for the security of their designs.

ChaCha Now, Y’all

ChaCha is a variant of the Salsa20 cipher, which is an eSTREAM finalist created by Daniel J Bernstein.

The original ChaCha cipher accepted 128-bit or 256-bit keys and 64-bit nonces, and had a 64-bit internal counter. However, the variant used by the IETF uses 96-bit nonces and 32-bit internal counters to be consistent with other AEAD modes used in TLS.

ChaCha, like Salsa20 before it, is a stream cipher whose core is an ARX-based pseudorandom function (although it’s often called a hash function) whose output is mixed with the plaintext, using XOR. This paper explains its deviation from the original Salsa20 design.

// Encryption
const keystream = chacha20.stream(nonce, key, counter);
const ciphertext = utils.xor(keystream, plaintext);

// Decryption
const keystream = chacha20.stream(nonce, key, counter);
const plaintext = utils.xor(keystream, ciphertext);

The internal state of ChaCha is 512 bits: 128 bits of constants, 256 bits are allocated for the key, and the remaining 128 bits is divided up between the nonce and counter.

The ChaCha internal state looks like this, visually:

0        1        2        3
cccccccc cccccccc cccccccc cccccccc
4        5        6        7
kkkkkkkk kkkkkkkk kkkkkkkk kkkkkkkk
8        9        10       11
kkkkkkkk kkkkkkkk kkkkkkkk kkkkkkkk
12       13       14       15
nnnnnnnn nnnnnnnn nnnnnnnn nnnnnnnn

Once the state is initialized, it copies this state into temporary variables, runs through several rounds (ChaCha20 is 20 rounds, ChaCha12 is 12 rounds, etc.), and then adds the initial values to the final values. We’re not super interested in what these rounds do or why they’re designed the way they are (TL;DR it aims to efficiently maximize bit diffusion), but we are interested in that final addition.

ChaCha rounds are broken up into what are called quarter rounds, which it applies to rows and then diagonals. These quarter rounds consist entirely of 32-bit additions, bitwise rotations, and XOR operations.

The final addition of the initial state (constants, secret key, nonce/counter) to the terminal state of the last round prevents cryptanalysts from inverting the computation (see section 4.2 of the Salsa20 paper). Although the constants and nonce/counter are public inputs, the key is not, and the key takes up half of the 512-bit state.

Main takeaway: The security of both Salsa20 and ChaCha depend on attackers not being able to discover half of the internal state; otherwise they could invert the computation.

One other thing to notice: Those constants at the top of the internal state? That’s the string expand 32-byte k converted into four 32-bit words. A lot of non-symmetric values would have worked here; this was simply chosen to be a Nothing Up My Sleeve number.

That’s all we need to take away from ChaCha’s design. I highly recommend reading the papers for each cipher discussed in this section; they’re incredibly accessible.

The Obvious But Wrong Way to Extend a Nonce

Earlier, we established that the internal state of ChaCha looks like this:

0        1        2        3
cccccccc cccccccc cccccccc cccccccc
4        5        6        7
kkkkkkkk kkkkkkkk kkkkkkkk kkkkkkkk
8        9        10       11
kkkkkkkk kkkkkkkk kkkkkkkk kkkkkkkk
12       13       14       15
nnnnnnnn nnnnnnnn nnnnnnnn nnnnnnnn

It might seem tempting to just overwrite the constants with the additional nonce bytes (or XOR them with the existing constants).

0        1        2        3
nnnnnnnn nnnnnnnn nnnnnnnn nnnnnnnn
4        5        6        7
kkkkkkkk kkkkkkkk kkkkkkkk kkkkkkkk
8        9        10       11
kkkkkkkk kkkkkkkk kkkkkkkk kkkkkkkk
12       13       14       15
nnnnnnnn nnnnnnnn nnnnnnnn nnnnnnnn

This is a bad idea. If those constants were somehow initialized to all 0 bits, and your key was all 0 bits, and your nonce/counter was all 0 bits, ChaCha would output all 0 bits.

Here’s a fun thought experiment: What kind of fun things would result if attackers can change these values?

In the standard AEAD_ChaCha20Poly1305 construction, the Poly1305 key is derived from the block with counter = 0, and encryption starts with counter=1. If you could coerce ChaCha to have an all-zero state, you could force a trivially guessable Poly1305 key and thereby allow chosen-ciphertext attacks.

Of course, this is setting aside the fact that an all-zero key is itself trivial to guess! Don’t use that for your secret key.

The purpose of these constants (and the reason their actual value isn’t super important to the security of ChaCha beyond being an asymmetric pattern of ASCII bytes) is simply to ensure the operations are always diffusing bits, even with very dumb inputs.

With all of that in mind, while it’s tempting to try to extend the nonce by updating the internal ChaCha state with the extra nonce bytes, it’s not a great idea to clobber the ChaCha constants.

There’s something else we can try, which is precisely what XSalsa20 and XChaCha both do.

What XSalsa20 and XChaCha Do

The extended-nonce constructions specified by Daniel J Bernstein in the XSalsa20 paper and this IETF RFC draft both do (effectively) the same thing:

• Take your “extended nonce” of 192 bits, and split it into a 128-bit segment and a 64-bit segment.
• Run the first 128 bits of the nonce (as the full nonce/counter input) through the underlying PRF with the key without the final addition. (This PRF variant is called HSalsa20 and HChaCha respectively.)
• Use the output of the HSalsa20/HChaCha step as the key to encrypt data with the remaining 64 bits of the nonce.

This is a pretty trivial construction, and it costs slightly less than encrypting one additional block of plaintext (which is very fast for both algorithms). Whether or not the X-variant is secure depends entirely on two things: If the normal stream cipher is secure, and if the H-variant of the underlying PRF is secure.

Let’s focus on the difference between HChaCha and ChaCha.

HChaCha

ChaCha outputs blocks of 512 bits which are combined with 512 bits of plaintext (using XOR) to encrypt. The final output is the initial added to the result of N (typically 20) rounds of the ChaCha round function.

HChaCha skips the final addition, but only outputs 256 bits. The specific bytes used to produce the final HChaCha output correspond to the public inputs to HChaCha:

0        1        2        3
cccccccc cccccccc cccccccc cccccccc
12       13       14       15
nnnnnnnn nnnnnnnn nnnnnnnn nnnnnnnn

Because only half the internal state is returned, and it’s the half that corresponds to the public values (constants, nonce), you can get the same half-block security guarantee without needing that final addition. (The final addition is useful for ensuring ChaCha can encrypt large amounts of plaintext efficiently, but here we’re just hashing a subkey out of the extension to the nonce.)

The security proof sketched out in the XSalsa20 paper describes all of this, but in more mathematical notation than plain English.

XChaCha

When you assemble all of the pieces, the security argument for XChaCha looks like this:

1. An attacker cannot recover half of the internal state from ChaCha outputs (due to the final addition which prevents the computation from being inverted).
2. An attacker cannot recover half of the internal state from HChaCha outputs (due to only returning a public computation of these inputs, and half of the internal state not being revealed).
3. The underlying transformations used in ChaCha are an efficient way to ensure high bit diffusion in reduced rounds, and the number of rounds is very conservative for the security target of the cipher.
4. The internal state of the PRF is 512 bits, which targets a 256-bit security level against birthday collisions.
5. The best known attacks only reduce the cost of ChaCha7 to about 2^230, which is computationally infeasible. ChaCha20 remains unaffected by this cryptanalysis.

Note: I won’t call what I wrote here a security proof. My blog is nowhere near formal enough for this sort of analysis, after all!

Closing Thoughts

If you’ve read this far, I hope that you understand:

1. (Loosely) How ChaCha works
2. Why the extended-nonce variant (XChaCha) doesn’t just clobber the constant part of the ChaCha internal state but instead uses HChaCha
3. Why HChaCha is designed the way it is
4. Why ChaCha is secure (and the assumptions it makes)
5. Why HChaCha is secure (and the assumptions it makes)
6. Why the composition XChaCha is secure

If anything isn’t immediately clear, I consider that a bug that needs to be fixed.

Cryptography can be a very difficult subject, but that doesn’t mean it has to be arcane and unapproachable.

Additionally, the next time someone links you to Latacora’s Cryptographic Right Answers page, I hope you can appreciate how much complexity and nuance was glossed over by the authors to arrive at a generally right answer for 99% of users and situations.

(It turns out their recommendation isn’t random-key robust, which matters if you’re designing the next OPAQUE or shadowsocks, if you’re curious about that last 1%.)

Header art by Scruff Kerfluff.