Nonce Length Math
I made a table of nonce lengths and collision probabilities.
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}
Nonce length | Number of nonces | ||||
---|---|---|---|---|---|
2^{32} | 2^{48} | 2^{64} | 2^{96} | 2^{128} | |
64 bit | ½ | 1 | 1 | 1 | 1 |
96 bit | 2^{-33} | ½ | 1 | 1 | 1 |
128 bit | 2^{-65} | 2^{-33} | ½ | 1 | 1 |
192 bit | 2^{-129} | 2^{-97} | 2^{-65} | ½ | 1 |
256 bit | 2^{-193} | 2^{-161} | 2^{-129} | 2^{-65} | ½ |
384 bit | 2^{-321} | 2^{-289} | 2^{-257} | 2^{-193} | 2^{-129} |
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:
- probabilities you can test for in CI/CD, i.e., >2^{-16}; and
- 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.