# 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 | 2^{32} |
2^{48} |
2^{64} |
2^{96} |
2^{128} |
---|---|---|---|---|---|

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.