# birthday attack again [closed]

Suppose that we have a d-bit hashing function, and assume that the dimensionality of the input space is unbounded. The probability of finding a collision in 2d/2 steps is 1/2, and we call this a “birthday attack”. Therefore success in one birthday attack is equivalent to a random variable S ∈ {0, 1}, where Pr{S = 1} = 1/2. Obtain the expected number of birthday attacks until a collision is found

## closed as unclear what you're asking by yyyyyyy, otus, Maarten Bodewes♦, Gilles, BivMay 11 '17 at 12:13

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

• So where are you stuck solving your problem? – axapaxa Apr 26 '17 at 16:51
• This appears to be a pure mathematics / statistics problem; solving it doesn't actually require any knowledge about cryptography. All the crypto jargon is just there as a distraction. See e.g. this Q&A thread on stats.SE for how to solve it. – Ilmari Karonen Apr 26 '17 at 18:01

## 1 Answer

This appears to be a basic exercise in elementary probability theory, with crypto jargon sprinkled in as a distraction. No actual knowledge of cryptography is required to solve it as stated. In fact, the only relevant parts of the problem statement are the last two sentences:

"Therefore success in one birthday attack is equivalent to a random variable S ∈ {0, 1}, where Pr{S = 1} = 1/2. Obtain the expected number of birthday attacks until a collision is found."

Now mentally replace the words "birthday attack" above with "coin flip", and you should recognize a familiar problem. If not, see e.g. this Q&A thread on Statistics Stack Exchange for how to solve it.

In fact, from a cryptographer's perspective, the rest of the problem statement is not only irrelevant, but also faulty in at least two ways.

First, the given success probability for a birthday attack is wrong. Even assuming that "2d/2" is actually a typo (or a transcription error) for $2^{d/2}$, the actual success probability for a birthday attack on a $d$-bit hash with $2^{d/2}$ trials is approximately $1 - e^{-1/2} \approx 0.39$, not $1/2$. For a 50% success probability, you actually need about $\sqrt{2 \ln 2} \cdot 2^{d/2}$ $\approx$ $1.177 \cdot 2^{d/2}$ hash evaluations.

Second, if the birthday attack did fail to find a collision after $2^{d/2}$ (or even $1.177 \cdot 2^{d/2}$) steps, no sane cryptographer would ever stop and start over from scratch. Instead, they'd continue the same attack, collecting new hash values until a collision was, in fact, found. Since the probability of each new hash value yielding a collision is proportional to the number of values already collected (in fact, it's exactly equal to the number of previously collected values divided by $2^d$), this is much more efficient than throwing away the previously collected hash values and starting over.

With such a continued attack, the expected number of hash evaluations needed to find the first collision is only about $\sqrt{\pi/2} \cdot 2^{d/2} \approx 1.253 \cdot 2^{d/2}$, only slightly more than the number of hash values needed for a 50% success probability. Even if you want to be, say, 99.9% sure that you'll find a collision, that still requires collecting only about $\sqrt{2 \ln 1000} \cdot 2^{d/2}$ $\approx$ $3.717 \cdot 2^{d/2}$ hash values.

In fact, even if you only have enough memory available to store, say, up to $2^{d/2}$ hash values, and you've hit that limit without finding a collision, it's still much more efficient to just discard (any) one of the previously collected hash values at a time, and replace it with a new one, than to throw away all the previous values at once and start from scratch. Basically, the most effective collision-finding strategy is always to store as many previously collected hash values as you possibly can, so as to maximize the probability that the next hash value happens to match one of them.