Nonce Length Math

I made a table of nonce lengths and collision probabilities.

Silhouette of a person with long hair writing equations on a whiteboard with their right h
Photo by ThisisEngineering RAEng / Unsplash

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
232 248 264 296 2128
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
Upper bounds on the probability of nonce collision.

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.

Subscribe to Ciphertext Compression

Don’t miss out on the latest issues. Sign up now to get access to the library of members-only issues.