Nonce Length Math

I find myself frequently redoing this math, most recently this morning for my RWC 2024 slides. So, I decided to slightly edit my notes and publish them.

Probability of Nonce Collision

Given \(k\) uniformly random \(n\)-bit nonces \((N_1,\dots,N_k)\), we want to compute the probability \(p\) that there's a collision.

Of the \((2^n)^k\) possible choices for \((N_1,\dots,N_k)\), only \((2^n)(2^n-1)(2^n-2)\cdots(2^n-k+1)\) choices have no collisions. Thus, the probability of a collision is \begin{equation} p = 1 - \left(1-\frac{1}{2^n}\right) \cdot \left(1-\frac{2}{2^n}\right) \cdots \left(1-\frac{k-1}{2^n}\right). \end{equation}

But this equation is unwieldy so let's try a different approach. Let \(A_i\) be the event that \(N_i\) collides with one of the previous nonces \(\{N_1,\dots,N_{i-1}\}\). Then \(\Pr[A_i]\) is at most \((i-1)/(2^{n})\) since the \(i-1\) previous nonces contain at most \(i-1\) distinct values. Applying the union bound, we get the upper bound \begin{equation} p = \Pr\left[\bigcup_{i=1}^{k} A_i \right] \leq \sum_{i=1}^{k} \Pr[A_i] \leq \frac{k(k-1)}{2*2^{n}}. \end{equation}

Turns out that this bound is tight up to a factor of 2, but the proof uses exponentials, and I am not feeling that mathy right now. So, I'll instead direct you to Appendix A on page 273 of Mihir Bellare and Phillip Rogaway's cryptography notes.

Worked Examples

Let the number of nonces \(k = 2^{\ell}\) for some \(\ell\), then we can further simplify equation (2) as \begin{equation} p \leq \frac{2^{\ell}(2^{\ell} - 1)}{2 * 2^n} \leq \frac{2^{2\ell}}{2^{n+1}} = 2^{2\ell - n - 1}. \end{equation}

But NIST says 2^-32 is okay? The GCM specification (SP 800-38D, Section 8) says that the probability of a collision should be upper bounded by 2^-32. I don't think this is good enough, 2^-32 is one in four billion or it will definitely happen to you in production odds. And recall that repeating the nonce in a scheme like AES-GCM is pretty much game over.

But the TLS 1.3 RFC says 2^-57 is okay? The TLS 1.3 specification (RFC 8446, Section 5.5) endorses a safer safety margin of 2^-57. This is one in a hundred million billion, so unlikely to happen to you, but I still can't guarantee that it won't happen to you.

Almost-Never Probabilities Considered Harmful

You should only ever have two kinds of probabilities:

1. probabilities you can test for in CI/CD, i.e., >2^-16; and
2. probabilities that will never happen in production, i.e., <2^-80.

I don't know whom I learnt this from, but I think it traces its lineage to the PARIS256 attack by Sean Devlin and Filippo Valsorda which was triggered with probability about 2^-32.

If you liked this random slice of applied crypto, please come to my RWC 2024 talk for more. Oh, and subscribe.

Correction (May 27, 2024): An earlier version of this post had an off-by-one error in the worked examples. This has now been corrected. Thanks to Sc00bz for pointing out the error.