2
$\begingroup$

What is the probability of the first N hash digits colliding? for example i made a script that appends the first 5 digits of the file's sha1 hash to the name of the file.

So will the probability of a collision be 16^5=1048576? Am i properly calculating the probability of a collision.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ In discrete probability any event occurs with probability at most 1. You can expect a collision of the first 5 digits of a SHA1 hash after roughly 1000 hashes because of the birthday bound. $\endgroup$
    – pg1989
    Commented Sep 17, 2013 at 18:35

1 Answer 1

Reset to default
6
$\begingroup$

The birthday problem is the generic name for such questions. You have $n$ values, selected randomly and uniformly in a space of size $t$; the probability that at least two of these values are identical is roughly equal to $n^2/(2t)$. When $n$ becomes close to $\sqrt{t}$, then the probability raises sharply. In your case, with 5 hexadecimal digits, you have a space of size $t = 16^5$, so you can expect your first collision, on average, when you get about 1000 values or so.

An intuitive way to think about it is that $n$ values make about $n^2/2$ pairs, and, "somehow", each pair has probability $1/t$ of being a collision. (The pairs are not independent of each other, but the intuition still works in that case.)

Improve this answer
$\endgroup$
4
  • $\begingroup$ But I am not selecting the items randomly, I am selecting the first five. I am not using the decimal number base I am using hexadecimal. Thanks your answer is easy to understand. $\endgroup$
    – kyle k
    Commented Sep 17, 2013 at 20:17
  • 2
    $\begingroup$ Ah but you are using SHA1 to compute the hash of the filename. SHA1 is very close to a random function, so we can consider the bottom 5 hexadecimal digits as randomly chosen from the set of all such strings. $\endgroup$
    – pg1989
    Commented Sep 17, 2013 at 21:34
  • $\begingroup$ @user pg1989 I am not computing the hash of the file name, i am computing the hash of the file contents, I included a link to my code. $\endgroup$
    – kyle k
    Commented Sep 17, 2013 at 23:13
  • 2
    $\begingroup$ @kylek, the answer is still correct, regardless of what data you are hashing to get the five digits. $\endgroup$
    – John Deters
    Commented Sep 17, 2013 at 23:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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