# How many hashes for high probability of finding a collision (specific case)?

Suppose Bob managed to obtain 220 different digests that were generated by a hash function employed by a target system. The hash function outputs 8-byte digest of a message. Bob now wants to find a message that hashes into 1 (one) of the obtained digests. How many different messages should Bob approximately hash until there is a good probability that a generated digest will match 1 of the obtained digests?

My answer is $$\sqrt{2^{64}}$$ ($$= 2^{32}$$) messages for a probability of 0.5. Is this correct?

• Lower, since you have multi-target Sep 24 '19 at 9:07
• @kelalaka: your reasoning is right, but your "Lower" (than $2^{32}$) is incorrect. To the OP: your estimate is incorrect.
– fgrieu
Sep 24 '19 at 9:11
• How did you come to your conclusion that it would be $\sqrt{2^{64}}$? Sep 24 '19 at 9:12
• @AleksanderRas, since the hash function outputs 8-bytes digest of a message. Sep 24 '19 at 9:24
• @fgrieu, any suggestion on how to approach this problem? Sep 24 '19 at 9:28

Let's assume that there are no prior collisions (two different messages that generate an identical hash) for the first $$2^{64}$$ messages.

If you want to find a message for one hash then you would have to try all these $$2^{64}$$ messages to reach the probability of 1 (100%). Since you mentioned good probability we can say that we would have to try half of that for a probability of 0.5 (50%). That means that we would have to try $$2^{64} / \space 2$$ possibilities which would be $$2^{63}$$.

Now you also already have a list of 220 hashes. That means that you can reduce it because we previously only calculated it for one hash, so the solution is:

$$\frac{2^{63}}{220} \approx 4.2 \times 10^{16}$$ for a probability of $$0.5$$ to find a message that hashes to one hash in your list.

• @kelalaka, would appreciate on how to approach this problem. Thank you. Sep 24 '19 at 9:42
• @alexkanderRas, so it is like solving for expected value? Sep 24 '19 at 11:14
• @wongsimon What do you mean? Sep 24 '19 at 11:34
• @aleskansdraRas, sorry my mistake. I thought it was similar to finding expected value as in probability. I am wrong, but now I understand your solution. Thank you for your assistance. Sep 24 '19 at 11:41
• Suppose the messages are unbounded in length. Then the probability of finding at least one preimage after $2^{64}$ messages is not 100%; rather, it is the CDF at $2^{64}$ of the negative binomial distribution for one success with a success probability of $220/2^{64}$. Specifically, it is about $1 - (1 - 220/2^{64})^{2^{64}} \approx 1 - e^{-220}$. Granted, that is very close to $1$; my point is that the reasoning is wrong unless the search is going through a space of exactly $2^{64}$ possible messages. Sep 24 '19 at 17:07