Can someone explain why does probability is equal $2^{-224}$ in the following piece of paper? The length of messages blocks in Hamsi is equal 32 and the length of chaining values is equal 256. enter image description here

enter image description here


The second paragraph of section 2 of the quoted paper tells the domain of the function $\mathcal F:\{0,1\}^{32}\times\{0,1\}^{256}\to\{0,1\}^{256}$.

Under the reasonable assumption that for fixed second input ($h_{i-1}$ in the question's statement), $\mathcal F$ behaves as a random function of the first input ($M_i$ in the question's statement), then for each value of the first input the probability that the output matches a fixed target value ($h^*_i$ in the question's statement) is $p=2^{-256}$. That will be repeated for the $n=2^{32}$ possible first inputs.

One way to conclude is to know that if an event has probability $p$ of occurring at each (independent) experiment, then the expected number of events for $n$ experiments is $n\,p$, and the probability of at least one event is barely below that value $n\,p$ as long as it remains small. Here $p=2^{-256}$, $n=2^{32}$, $n\,p=2^{32-256}=2^{-224}$ (as asserted in the question's statement). That's very small, thus the approximation made is valid.

The more mathematical way: the probability of no match for one first input is $1-p$. The probability of no match after $n$ inputs is $(1-p)^n$. The probability of at least one match after $n$ inputs (as discussed in the question's statement) is $1-(1-p)^n$. Using that $1-(1-p)^n=1-e^{n\log(1-p)}$, that $\log(1-p)=-p+o(p)$ (using little-O notation), that $e^x=1+x+o(x)$, it comes that $1-(1-p)^n=n\,p+o(n\,p)$. Hence $1-(1-p)^n$ is about $n\,p$. The error made with this approximation is always by excess. When $n\,p<0.3$, the relative error is less than $16\%$. For lower values of $n\,p$, that upper bound of the relative error becomes barely above $n\,p/2$.

Other useful data points are that if $n$ is large, then $n\,p=1\implies1-(1-p)^n\gtrapprox1-e^{-1}\gtrapprox63\%$; and $n\,p=2\implies1-(1-p)^n\gtrapprox1-e^{-2}\gtrapprox86\%$ This explains the "high probability" after about $2^{224}$ random values of $h_{i-1}$ in the question's statement.

| improve this answer | |
  • $\begingroup$ I didnt completely understood the last paragraph, but basically what you meant that the probability that the for one fixed input try you get a match is $2^{-256}$, and you have $2^{32}$ tries, so its $(2^{32})/(2^{256})$. Did i understand correctly? $\endgroup$ – Kirill Dec 5 '19 at 18:41
  • $\begingroup$ @kirill. $(2^{32})/(2^{256})$ is an excellent approximation with the numbers at hand. I've now separated the approximation, and its rigorous derivation. $\endgroup$ – fgrieu Dec 5 '19 at 21:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.