Join Log in
Score:1
PaulV1990 avatar Crypto

Clarification on nonce collision calculation

gb flag
PaulV1990

I've been working on a AES256-GCM implementation (in Java). I'm a little bit stuck on the part where i need to decide how often i need to rotate my key.

I've got a lot of information from this posts: Safety of random nonce with AES-GCM?

And the website if refers to: https://www.imperialviolet.org/2015/05/16/aeads.html

It states the following quote:

This is because if you throw 2$^{32}$ balls at 2$^{96}$ buckets then you have roughly a 2$^{-33}$ chance of getting two in the same bucket.

How is this calculation done? The only solution i can think about is:

2$^{(95-128)}$=2$^{-33}$

I would like to know the following:

  1. Is this the correct calculation?
  2. Is the 2$^{95}$ chosen, because only 50% is needed and 2$^{96}$ / 2 = 2$^{95}$
  3. Subtracting by 128 refers to the total length of the IV or something else?
42
0 + 0
Score:1
Daniel S avatar Crypto
ru flag
Daniel S

I'm afraid that it's a significantly more complex calculation based on the mathematics of the birthday problem. Per the link, if we throw $n$ balls into $d$ buckets then the probability $p(n;d)$ of a collision is approximately $$p(n;d)\approx 1-\exp\left(-\frac{n(n-1)}{2d}\right)= \frac{n(n-1)}{2d}+O\left(\frac{n^4}{d^2}\right)$$ (the second approximation following from the Taylor series for $\exp(x)$).

Plugging in $n=2^{32}$ and $d=2^{96}$ gives $p\approx 2^{-33}$. More generally if $n=2^a$ and $d=2^b$ we will have $p\approx 2^{2a-b-1}$ provided that $2a$ noticeably less than $b$.

0 + 0
PaulV1990 avatar
gb flag
PaulV1990
Thank you for this answer.
0
Reply
PaulV1990 avatar
gb flag
PaulV1990
Appending this comment, hit enter to soon after saying thanks and formatting takes some time. I was calculating a bit different, according to these posts: - https://math.stackexchange.com/questions/883983/birthday-paradox-huge-numbers - https://preshing.com/20110504/hash-collision-probabilities/ It gives the same result with the rule you mentioned: $a^2 < b$ The simplified version in those links was: $$ \frac{a^2}{2b} $$ With my values: $$ \frac{{(2^{32}})^{2}}{2 \cdot 2^{96}} = \frac{1}{2^{33}} = 2^{-33} $$
0
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.