0
$\begingroup$

I'm taking 2 medium-length strings (50-70 chars) and hash them using md5 to get results like d2ae4f4919a10958e2c603782f0ec1cc, then recording the first 5 symbols of the hash to provide a (unique) short key. If md5 distribution is (almost) random then would the chances of a collision be 16^5 ([0-9a-f]^5) = 2/1.048.576, or different? Am I extremely lucky to get 2 hashes like d2ae4f4919a10958e2c603782f0ec1cc and d2ae41c1935738ca4a06ba28aad3e555 which start with the same 5 alphanumerals, or there's something else going on? The strings start the same, but it shouldn't matter should it.

$\endgroup$

1 Answer 1

1
$\begingroup$

The number of possible truncated hashes is $d=16^5$. Assuming MD5 is perfectly random, by the birthday bound, your probability of seeing at least one collision is approximately

$$ 1 - \left(\frac{d-1}{d}\right)^{n \text{ choose } 2}, $$ where $n$ is the number of strings you hashed. It doesn't take many to hit 50%. In fact, the above equals 50% when $n= 1206$.

So no, you're not extraordinarily lucky. This was pretty likely.

$\endgroup$
4
  • $\begingroup$ so it is 16^5. and i've hashed 10 strings... but ok $\endgroup$
    – ADC
    Jul 31 at 20:58
  • 1
    $\begingroup$ $n$ never reaches $1206$. OP said they were creating hashes in groups of two, and then comparing only the two results hashed in that group. In which case, $n$ never exceeds $2$, and the probability is very close to $1$ that they should not see two hashes collide. $\endgroup$
    – aiootp
    Jul 31 at 22:46
  • 1
    $\begingroup$ @aiootp thx you're right but i guess the birthday calculation is what i needed to know i'm using this tool now bdayprob.com if i need to take more strings in future $\endgroup$
    – ADC
    Jul 31 at 23:49
  • $\begingroup$ After hashing 10 strings, probability of at least 1 collision is about 1/23302. So what's described is unlikely, but no impossibly unlikely. $\endgroup$
    – fgrieu
    Aug 4 at 10:16

Your Answer

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

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