# Can anybody please explain why is the probabilty of finding a desired message for random chaining values equal $2^{-224}$?

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.

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.

• 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? Dec 5, 2019 at 18:41
• @kirill. $(2^{32})/(2^{256})$ is an excellent approximation with the numbers at hand. I've now separated the approximation, and its rigorous derivation.
– fgrieu
Dec 5, 2019 at 21:50