Please give help! how can I calculate the probability of collision? I need a mathematical equation for my studying.

Assume, I am using SHA256 to hash 100-bits. Thus:

SHA256 {100} = 256-bits (hash values) I would like to know the probability of collision.

This website: https://preshing.com/20110504/hash-collision-probabilities/

Gave an equation: $K^2 / 2N$

But I could not know what is $K$ and $N$? Is K is the output which is (256-bits) and $N$ is the input which is (100-bits)

Please Help and Thanks in advance...

  • 1
    $\begingroup$ Umm... did you read the entire web page you linked to? It defines $k$ and $N$ very close to the top. $\endgroup$ – Ilmari Karonen Dec 8 '18 at 15:26
  • $\begingroup$ $n$ is the output size of the hash function, $k$ is the randomly generated unique inputs. it is $k^2/2n$ $\endgroup$ – kelalaka Dec 8 '18 at 15:28
  • $\begingroup$ well, then based on the equation: 100^2 / 2^256 right? $\endgroup$ – Al-Ani Dec 8 '18 at 15:34

$n$ is the output size of the given hash function. To find a collision you try randomly generated $k$ different inputs. When we say the output size is $n$, it means that the output space has $2^n$ elements.

What you see on that website is the general case of the collision probability. We normally talk about the 50% probability (birthday attack) on the hash collisions as

$$ k = \sqrt{2^n}$$ You can also see the general result from the birthday paradox.

To have birthday attack with 50% percentage you will need $k = 2^{128} \approx 4.0 × 10^{38}$ randomly generated differently input for a hash function with output size $n= 256$


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.