1
$\begingroup$

I was wondering, if there is an MD5 hash collision in the UNSIGNED MEDIUMINT Range (0 - 16777215). Sadly, I'm unable to run a script to check this myself, due to Memory (RAM) limitations. The answer is probably no; the next step would be - how many characters are even needed, until the first collision is found?

An MD5 hash has 32 Characters. If you only would use, lets say, the first nine characters from all MD5 hashes in the MEDIUMINT range, would they still all be unique?

The reason behind this: I'm trying to find a simple way to basically use an MD5 hash for every number in the MEDIUMINT range, to create a short, unique string, preferably not longer than 9 letters -- as abstraction to the actual number (so instead of an 1, you get something like c4ca4238a)

Are the first nine characters of all MD5 hashes in the UNSIGNED MEDIUMINT (whitout 0) range unique?

$\endgroup$

migrated from cstheory.stackexchange.com Sep 26 '12 at 15:10

This question came from our site for theoretical computer scientists and researchers in related fields.

5
$\begingroup$

Just to complete Yuval's answer, there are plenty of collisions if you pick the first 9 digits of the MD5.

For example:

md5('40236')  = f46657d67 3d95ccf8d12b1075ab7c653
md5('400704') = f46657d67 e7a3de02f64013bfcbd932c

Let $m = 2^{36}$ (nine hex digits), $n = 2^{24}$ (three bytes for an UNSIGNED MEDIUMINT); assuming that MD5 is a good hash :), the probability $P(n)$ of a collision is:

$1 - m! / (( m - n )! * m^n) \approx 1 - e^{-n^2/2m} = 1 - \frac{1}{e^{2048}}$

And you'll find a collision on the first 9 digits with high probability ($P(n) \approx 0.99$) every $n = 2^{20}$ strings picked (whatever they are). See Birthday problem on Wikipedia.

So even if you use the binary encoding (three bytes) you obviously get plenty collisions:

Starting from 000000, the first is:

md5( 0x013701 ) = 8015b8be cf7b0a7e744cd54ac76a302f
md5( 0x0725c6 ) = 8015b8be cf8140319e919766901824bf

Note that 0x0725c6 is a 19 bit number.

$\endgroup$
4
$\begingroup$

Every number in the range $0$ to $2^{24}-1$ can be represented by:

  • $8$ digits
  • $6$ lower-case letters
  • $5$ symbols, each of which is either a digit or a lower-case letter
  • $4$ symbols, each of which is either a digit, a lower-case letter, an upper-case letter, a comma, or a period

There's no need to bother with MD5.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy