How to generate a nonce for ChaCha20 Poly1305?

Question

I am using a self implementation of ChaCha20 with Poly1305. Since the nonce is only 96 bits it cannot be chosen at random. Can anyone suggest an efficient method to generate nonce from the key ?

Answer 1

The RFC 7539 describe your needs.

The uniqueness:

The most important security consideration in implementing this document is the uniqueness of the nonce used in ChaCha20. Counters and LFSRs are both acceptable ways of generating unique nonces, as is encrypting a counter using a 64-bit cipher such as DES. Note that it is not acceptable to use a truncation of a counter encrypted with a 128-bit or 256-bit cipher, because such a truncation may repeat after a short time. (The bolds are mine)

LFSR's and counters are very efficient. Use a 96-bit binary counter or 96-bit length LFSR with a primitive polynomial. One must be careful during system reboots and especially system and power failures since you have to store the nonce somewhere to recover correctly. You need to make sure that when a failure occurs either do a long-jump on the counter/LFSR or generate a fresh new key.

Randomly generating:

You can also generate it randomly while considering the birthday bound $\mathcal{O}(\sqrt n)$. You should stop way before generating $2^{48}$ nonces under the same key to hit a collision. You can adjust the advantage of the adversary with the birthday calculations.

Combining Both

One can also combine counters/LFSR with random generation. For example, use a 48-bit binary counter and 48-bit random. For each nonce generation increment the counter/LFSR and generate a new 48-bit random.

This is more reliable than single counter/LFSR or random based one. During a failure, if the system did not correctly write the last step/stage of the counter/LFSR, then the random part would be helpful to mitigate the repeat of a previous nonce.

Consequences of repeating a nonce:

If a nonce is repeated, then both the one-time Poly1305 key and the keystream are identical between the messages. This reveals the XOR of the plaintexts, because the XOR of the plaintexts is equal to the XOR of the ciphertexts.