# How to prevent accidental nonce reuse with AEAD cipher

I'm trying to correctly implement ChaCha20-Poly1305 in my node.js app (...crypto is hard). I understand that the cipher requires a unique key/nonce pair for each message or the security breaks down.

The nonce doesn't have to be random or unpredictable, so a simple counter is sufficient. My problem is that I can't figure out how to implement an efficient counter that will work with multiple instances of my app running simultaneously on the same machine and guarantee that no nonce will ever be reused.

Basically, I'm wondering how to avoid this footgun.

• Use a timestamp. Apparently not a great idea.
• Use redis INCR. Complicates development environment (I now need redis installed on every computer I develop on), and I'm still left without strong guarantees that I won't get a duplicate value in case of an unexpected shutdown (even with Redis AOF).
• Write to a file or database table every time a nonce is created. This should work, but the performance would not be great, and I'm probably still stuck in the event of an unexpected shutdown.
• Use a UUIDv1 or v4 type thing (from the this comment). Initially v1 seemed perfect (guaranteed uniqueness), but it's tied to the system MAC address, so when I spin up multiple copies of the app, I'm probably killing any type of guarantee. Then there's v4, which should be good, but because the nonce is only 96 bits, I would need to truncate the ID and increase my collision probability (same goes for v1 actually). If I went this route, I was looking at nanoid.
• Regularly rotate keys. I realize that this needs to be done anyway, but I want to minimize how often it needs to happen.
• Something like Twitter's Snowflake. flake-idgen seems well suited for this (guaranteed uniqueness, partitioned by machine/worker or instance id, doesn't require coordination beyond determining instance ids, generates short enough ids).
• Use XChaCha20-Poly1305. It's recommended in the libsodium docs specifically for this reason (the nonce is big enough that you can just throw random values at it and not worry). But, it's not a standard (yet?), and it would require bringing libsodium in for crypto instead of relying on node's built in OpenSSL wrapper. This complicates development (dealing with native bindings) and/or undermines security (constant time issues running crypto in js/WebAssembly...way over my pay grade).

Am I missing something obvious? How do people usually solve this kind of problem? Right now, I'm liking flake-idgen, but it doesn't seem like it's gotten a lot of scrutiny, so it seems possible that there are corner cases that could cause a duplicate id (leap seconds, leap year, accidental server clock reset, malicious NTP server, etc.).

Update: Ok, so the consensus seems to be to just use a random nonce and not worry too much about it. For my scale, I think that will be fine.

I found some issues in testing flake-idgen, so I don't think I would actually use that (although it still looks like a cool project).

My alternative plan would be to write a counter implementation that generates a 64bit BigInt counter (support added in Node 12) + a 16 bit instance ID + maybe 16 random bits for fun. I would persist the counter to disk after every X increments so that I'm not constantly writing to the disk. In the event of an unexpected server shutdown, the system would read from the disk file and add X + 1 to the current counter to ensure no-collisions.

Unsolved problems with this implementation: how to handle wrap around? what happens if the server is reset and there is no disk file to read from?

Thanks for your help on this, and if someone wants to post "just use random" as an answer, I'd be happy to accept it.

• Well, you generally just use a secure random nonce of 64 or, is anywhere possible, 96 bits. This is not about programming, so I asked for migration to crypto.SE. Hope to see you there. – Maarten Bodewes May 20 '19 at 5:26
• Thanks for commenting. I believe the libsodium documentation linked above does not consider a random nonce suitable for use in the IETF variant of ChaCha20-Poly1305 that I'm using. You disagree? I considered posting on crypto.SE, but the questions there tend to be more theoretical, and this is about implementation on a specific platform. Maybe I'm wrong though? – Dominic P May 20 '19 at 5:35
• I think it's somewhat over cautious - up to 2^32 messages should be OK with a random nonce of 96 bits. However, being cautious is what this lib is all about, and that's good security practice. – Maarten Bodewes May 20 '19 at 7:25
• If multiple instances of your app are running, then somewhere in the system there will be a process number, or equivalent, for each instance. Concatenate that process number with a counter to get a unique nonce for the instance. Make sure each instance of your app has a different key so as to ensure a different key/nonce combination for each instance. – rossum May 20 '19 at 14:52
• @PaulUszak What does "holistically secure" mean? – forest May 22 '19 at 23:40

Hard to provide a definitive answer without more information about your application (which would render the question off-topic for Crypto SE). But one relevant technique that many systems use is a hierarchy with two types of key:

• Short-term data encryption keys (a.k.a. DEKs), which are generated randomly in narrow scopes (e.g., individual executions of your application) and used to encrypt the actual data;
• A long-term key encryption key (a.k.a. KEK or master key), that's used to encrypt DEKs.

The idea then is along with each message's ciphertext you include a copy or reference to the encrypted DEK that was used to encrypt the message. A reader, to decrypt the message, first decrypts its DEK and then the ciphertext. This is often called envelope encryption, with the metaphor that each ciphertext is enclosed in an "envelope" that includes its encrypted DEK.

Envelope encryption is commonly coupled with a key management system (KMS), a hardened service that "owns" the master key and performs encryption/decryption operations with it on behalf of authenticated and authorized clients. The idea is that your application instances don't actually get a copy of the master key; instead they must authenticate to the KMS and request it to perform master key operations on their behalf. (Of course you need to think carefully about the performance implications of this—you ideally want a small ratio of KMS encryption/decryption requests to volume of data encrypted/decrypted with the DEKs.)

One reason for the popularity of this architecture is there are cloud services and software products that implement the KMS functionality:

The way this ties into your question about nonce management is that if you have this infrastructure (which you might independently want), the nonce management problem is much simplified because in any context where you're about to encrypt but you can't guarantee you can produce an unique nonce, you can just spawn a new DEK. For example, each instance of your application might just do so at startup, and keep a counter that's guaranteed to be unique within the process.

The cloud vendors have useful conceptual documentation on this if you're interested:

• Thanks for the in-depth explanation. That's very helpful. I did plan to have an application key and a data encryption key, but my setup assumed a long lived DEK that was only rotated occasionally. I didn't even consider embedding an encrypted version for the DEK with the message. I could probably leverage the Authenticated Data functionality of my AEAD cipher to do this in a secure way. It does have performance implications as you mentioned, but the simplicity might be worth it. – Dominic P May 22 '19 at 23:34
• @DominicP Sounds to me like you're misunderstanding how AEAD works. First, it doesn't necessarily embed the metadata along with the ciphertext (see last paragraph of this answer of mine elsewhere). Second, I don't think you mean using the unencrypted DEK as AD, but to be safe, don't do that—AEADs are not generally required to preserve AD confidentiality. In any case, successful decryption all but guarantees you used the correct key. – Luis Casillas May 23 '19 at 0:34
• Maybe I am misunderstanding AEAD. When you suggested I include a copy of the encrypted DEK (yeah, unencrypted would be kind of pointless) with the cipher text, that seemed like a good use case for AD (storing something related to the encrypted message that can be accessed and verified before decryption). But, as you say, if the DEK is tampered with, decryption will fail anyway, so I guess I wouldn't need to verify its integrity. Am I tracking with you, or am I still missing something? – Dominic P May 23 '19 at 2:08
• AD ≠ "storing something related to the encrypted message"; that is contingently often true, but (a) you don't have to store associated data, you just have to supply the same AD at decryption that was supplied at encryption time, and (b) you don't automatically need to authenticate any data that's stored along ciphertext, it really depends on the application. And again, I don't claim you're proposing this, but (c) talk about using a key as AD makes me wary that somebody might AD something confidential, and (d) using an encrypted key as AD doesn't seem to add any security. – Luis Casillas May 23 '19 at 19:00
• Ok, thanks for the clarification. Yeah, I'm with you on a, b, and c. It's just the d part that's hanging me up. If I plan to store the encrypted DEK alongside the cipher text anyway. Why not include it in AD? Is there a downside to that? I realize that if it's been tamped with, decryption of the DEK should fail anyway. But, if it's in AD I won't even bother trying to decrypt the DEK in that case because the authentication will fail. Maybe this opens me up to some kind of timing attack (different failure modes taking different amounts of time)? – Dominic P May 23 '19 at 20:47
• If you are having a sequential conversation, like TLS where each record is sent in order before sending the next record, you should use message sequence numbers for the nonce. These will never overflow in ChaCha even if you managed to send one message per nanosecond for four centuries. As a bonus, you can reject replays and force the attacker to keep up with your conversation, and you can immediately detect incorrect implementations that use nonces insecurely, e.g. because they randomized it or rolled it back.

• If, for some reason, you are using a single key for (say) thousands of conversations in parallel, you can carve up the nonce into smaller pieces and assign to each conversation a unique (say) 16-bit number and then use 48-bit message sequence numbers for the rest, which is still a lot of messages, or 32-bit/32-bit, etc.

• But if you're not restricted to using the same key—and it seems unlikely that you are, since you get to dictate how the key is used—then you can derive subkeys from a master key with a key derivation function, KDF, such as HKDF-SHA256, in what is sometimes called a cascade. In fact, this is exactly how XSalsa20 and XChaCha work, using Salsa20/ChaCha itself as a KDF! (Note: KDF does not just mean password hash; KDFs can be extremely cheap to compute—no costlier than generating a single block of output with ChaCha, for instance!)

• For example, if you have a master key $$k$$ for your application, and many uniquely labelled instances of it, you can use $$k_i := \operatorname{HKDF-Expand}_k(L_i)$$, where $$L_i$$ is a unique label called the ‘info’ for the $$i^{\mathit{th}}$$ instance or purpose. If you don't have HKDF logic handy, but you do have HMAC, it's easy to implement HKDF in terms of HMAC.

In a pinch, if you need a randomized system, you could just choose a sufficiently long info label at random, say 256 bits, and there will be no danger of collision (unless there's a VM rollback, etc.). You could also include a time stamp, counter, favorite color, process id, phase of the moon, or anything else you want in the HKDF info string, as long as you can reason yourself into confidence that it will be unique.

Caveats: In some cryptosystems like AES, there's a high cost to changing keys, and for 128-bit keys, subkey derivation is safe only for a modest number of keys, which is part of why I advise against AES and particularly against AES-128. But there is zero key setup cost in Salsa20 and ChaCha, and the danger of collision in 256-bit keys is negligible no matter how many subkeys you derive within humanity's capacity for computation.

• You may also have the option of generating and storing additional keys, possibly encrypted with a master key, or with a master key pair to separate concerns, or using a deterministic authenticated cipher. But this is getting a bit far afield of the original already broad question.

(Technical details ahead, not necessary for the principal conclusion above.)

A note on XSalsa20 and XChaCha: If you have a library that computes Salsa20 or ChaCha for arbitrary nonce and block counter, you can easily compute XSalsa20 or XChaCha!

XSalsa20 and XChaCha are defined as follows: for 128-bit $$n$$ and 64-bit $$n'$$, the stream $$\operatorname{XSalsa20}_k(n \mathbin\| n')$$ with 192-bit nonce $$n \mathbin\| n'$$ is the stream $$\operatorname{Salsa20}_{k'}(n')$$ where $$k' = \operatorname{HSalsa20}_k(n)$$, and $$\operatorname{HSalsa20}_k(n)$$ is defined as a function of the Salsa20 core which is also used to generate the Salsa20 stream.

Specifically, the Salsa20 core $$\operatorname{Salsa20}(k, i, \sigma)$$ combines a 256-bit/8-word key $$k = (k_0, k_1, \dots, k_7)$$, a 128-bit/4-word input $$i = (i_0, i_1, i_2, i_3)$$ (which, for the stream cipher, is composed of a nonce and a block counter), and a 128-bit/4-word constant $$\sigma = (\sigma_0, \sigma_1, \sigma_2, \sigma_3)$$ into a matrix $$x = \begin{pmatrix} \sigma_0 & k_0 & k_1 & k_2 \\ k_3 & \sigma_1 & i_0 & i_1 \\ i_2 & i_3 & \sigma_2 & k_4 \\ k_5 & k_6 & k_7 & \sigma_3 \end{pmatrix},$$ and returns the 512-bit/16-word string $$\operatorname{Salsa20}(k, i, \sigma) = \pi(x) + x$$ where $$\pi$$ is a permutation. HSalsa20, in contrast, computes $$x' = \pi(x) + x - \begin{pmatrix} \sigma_0 & 0 & 0 & 0 \\ 0 & \sigma_1 & i_0 & i_1 \\ i_2 & i_3 & \sigma_2 & 0 \\ 0 & 0 & 0 & \sigma_3 \end{pmatrix},$$ and returns only the 256-bit/8-word string $$(x'_{00}, x'_{11}, x'_{12}, x'_{13}, x'_{20}, x'_{21}, x'_{22}, x'_{33})$$. (The indexing is a little different for ChaCha, as is the permutation $$\pi$$, but that's all.) Effectively, this is simply returning half the words of just the permutation $$\pi(x)$$, skipping the additions that Salsa20 does at the end, but the difference between those words of HSalsa20 and those words of Salsa20 depends only on the public nonce $$n$$ and the public constant $$\sigma$$ so that breaking HSalsa20 can't be easier than breaking Salsa20.

What this means is if you have a way to generate a single block of output with the Salsa20 or ChaCha stream cipher using a prescribed nonce and block counter, then you can compute HSalsa20 or HChaCha by just subtracting off the nonce/counter and constants to derive an XSalsa20/XChaCha subkey, and from there use your Salsa20/ChaCha code to compute the rest of XSalsa20/XChaCha.

• Ok, yeah i know some of these words :) Thanks for the help. A lot of this is over my head (it's cool to know I could use ChaCha20 to compute XChaCha20, but I wouldn't trust myself to do it right). But, the main thing I'm taking away is that I can use a KDF to derive keys for each instance of my app from a master key. What I'm not totally putting together is how I can use these subkeys in my encryption system. – Dominic P May 23 '19 at 2:24
• @DominicP How were you going to use any key in your encryption system, no matter how you got it? There's nothing special about a subkey; the only connotation carried by the term beyond ‘key’ is that it was reproducibly derived from another key rather than chosen nonreproducibly. – Squeamish Ossifrage May 23 '19 at 3:44

Imo, the timestamp idea gets worse rep than it deserves. It doesn't take 64 bits. 42 bits of timestamp give you 120+ years worth of milliseconds. That leaves you with quite some bits for UUID/randomness/counter of your choosing.

That being said, there is still the point of tampering with the timestamp and depending on your scope and overall setup this can be a serious issue. But there are issues with PRNG/counters as well (remember the WPA2 Krack attack?). Personally, I like my nonces with a little timestamp on the side.

• The problem with timestamps is that clocks are often not monotonic. A device runs out of battery and reboots to 01-01-2000. A system makes an NTP request and sets its clock to whatever the server replies. Someone notices that the timezone is wrong and the clock goes back by a number of hours. – Gilles 'SO- stop being evil' May 23 '19 at 20:57
• @Gilles: So you would take 96 bits from a PRNG over 42 bits timestamp + 54 bits PRNG? Do you consider the risk of a failing/reset/flawed/manipulated PRNG to be neglectable? – Max M. May 23 '19 at 21:58
• The question stipulates that multiple instances of the app may run simultaneously on the same machine, and is worried about nonce collisions between those. This answer doesn't account for that. – Luis Casillas May 23 '19 at 22:05
• @Luis Casillas: That's true. I only addressed his immediate rejection of using timestamps. This might have been better put in a comment. – Max M. May 23 '19 at 22:21
• @MaxM. The risk of a flawed clock is worse than a flawed RNG. All those potential risks you describe are problems with the RNG's monotonicity and apply to the clock as well. The clock has additional risks because it tries not only to be monotonic (or not at all), but also to be accurate. Using part timestamp and part PRNG can only make things worse. If you truly have a reliable clock, which is not all that common, mix it into your RNG. – Gilles 'SO- stop being evil' May 24 '19 at 6:33