1
$\begingroup$

Sorry I am new here and learning mathematics and cryptographic problems.

Assume an hash algorithm is collision resistant like SHA256, and the hash value is 64bit in length, (2^{64} possibilities)

Now there is known 20k different hashes.

A brute-force cracker can generate 1e9 hashes per second.

How many days will the cracker have 50% change to hit at least 1 of the 20k hashes? What will be the formula or code to calculate?

$\endgroup$

closed as off-topic by Henrik, GNUSupporter 8964民主女神 地下教會, Xander Henderson, Strants, Mohammad Riazi-Kermani Mar 30 '18 at 1:34

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Henrik, GNUSupporter 8964民主女神 地下教會, Xander Henderson, Strants, Mohammad Riazi-Kermani
If this question can be reworded to fit the rules in the help center, please edit the question.

1
$\begingroup$

Suppose there are N different possible hash outputs. Then the probability of a particular hash colliding with k known outputs is k/N. The probability that it will not collide is therefore (1-k/N). If you have n hashes, the probability that none will collide with one of the k known outputs is (1-k/N)^n. For large N, that can be approximated with e^-(kn/N). So if you want a probability of .5, you have

e^-(kn/N) = .5
kn/N = -ln(.5)
n = -N ln(.5)/k

ln(.5) ~= -0.693, so you have 0.693(N/k). Plugging in N = 2^64, k = 20,000 yields n = 6.3931543 * 10^14. Divide that by 10^9/second, and that's 6.3931543 * 10^5, or 639315.43 seconds, or about 178 hours, or about 7.399 days.

So every week or so, the probability of not having a collision decreases by a factor of 2: after one week, there's a 50% chance of no collisions, after two weeks, 25%, after three weeks 12.5%, etc.

$\endgroup$
  • $\begingroup$ wow Thanks for the answer, 63931.543/24/3600 = 0.7399 days? $\endgroup$ – eee1777 Mar 29 '18 at 19:39
  • $\begingroup$ @eee1777 I had the decimal place in the wrong place in 63931, but the numbers after that should be right $\endgroup$ – Acccumulation Mar 29 '18 at 20:20

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