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 \(n^k\) possible choices for \((N_1,\dots,N_k)\), only \(n(n-1)(k-2)\cdots(n-k+1)\) choices have no collisions. Thus, the probability of a collision is \[p = 1 - \left(1-\frac{1}{n}\right) \cdot \left(1-\frac{2}{n}\right) \cdots \left(1-\frac{k-1}{n}\right). \]
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)/n\) since the \(i-1\) previous nonces contain at most \(i-1\) distinct values. Applying the union bound, we get the upper bound \[p = \Pr\left[\bigcup_{i=1}^{k} A_i \right] \leq \sum_{i=1}^{k} \Pr[A_i] \leq \frac{k(k-1)}{2n}.\]
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
| Nonce length / Invocations | 232 | 248 | 264 | 296 | 2128 |
|---|---|---|---|---|---|
| 64 bit | ~0.5 | ~1 | ~1 | ~1 | ~1 |
| 96 bit | 2-32 | ~0.5 | ~1 | ~1 | ~1 |
| 128 bit | 2-64 | 2-32 | ~0.5 | ~1 | ~1 |
| 192 bit | 2-128 | 2-96 | 2-64 | ~0.5 | ~1 |
| 256 bit | 2-192 | 2-160 | 2-128 | 2-64 | ~0.5 |
| 384 bit | 2-320 | 2-288 | 2-256 | 2-192 | 2-128 |
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 ~2-32.
If you liked this random slice of applied crypto, please come to my RWC 2024 talk for more. Oh, and subscribe.