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?

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

  • $\begingroup$ @kelalaka, would appreciate on how to approach this problem. Thank you. $\endgroup$
    – wongsimon
    Sep 24 '19 at 9:42
  • $\begingroup$ @alexkanderRas, so it is like solving for expected value? $\endgroup$
    – wongsimon
    Sep 24 '19 at 11:14
  • $\begingroup$ @wongsimon What do you mean? $\endgroup$ Sep 24 '19 at 11:34
  • $\begingroup$ @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. $\endgroup$
    – wongsimon
    Sep 24 '19 at 11:41
  • 2
    $\begingroup$ 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. $\endgroup$ Sep 24 '19 at 17:07

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.