Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
1  
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. –  pg1989 Sep 17 '13 at 18:35

1 Answer 1

up vote 3 down vote accepted

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.)

share|improve this answer
    
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. –  kyle k Sep 17 '13 at 20:17
1  
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. –  pg1989 Sep 17 '13 at 21:34
    
@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. –  kyle k Sep 17 '13 at 23:13
1  
@kylek, the answer is still correct, regardless of what data you are hashing to get the five digits. –  John Deters Sep 17 '13 at 23:43

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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