How many random elements before MD5 produces collisions?

random md5 hash
Ben Throop picture Ben Throop · Oct 14, 2008 · Viewed 80.2k times · Source

I've got an image library on Amazon S3. For each image, I md5 the source URL on my server plus a timestamp to get a unique filename. Since S3 can't have subdirectories, I need to store all of these images in a single flat folder.

Do I need to worry about collisions in the MD5 hash value that gets produced?

Bonus: How many files could I have before I'd start seeing collisions in the hash value that MD5 produces?

Answer

Kornel picture Kornel · Nov 13, 2008

Probability of just two hashes accidentally colliding is 1/2128 which is 1 in 340 undecillion 282 decillion 366 nonillion 920 octillion 938 septillion 463 sextillion 463 quintillion 374 quadrillion 607 trillion 431 billion 768 million 211 thousand 456.

However if you keep all the hashes then the probability is a bit higher thanks to birthday paradox. To have a 50% chance of any hash colliding with any other hash you need 264 hashes. This means that to get a collision, on average, you'll need to hash 6 billion files per second for 100 years.

Related questions

How do I generate random integers within a specific range in Java?

How do I generate a random int value in a specific range? I have tried the following, but those do not work: Attempt 1: randomNum = minimum + (int)(Math.random() * maximum); // Bug: `randomNum` can be bigger than `maximum`. Attempt 2: Random rn = new …

Read More
How do I generate a random int number?

How do I generate a random integer in C#?

Read More
Getting random numbers in Java

I would like to get a random value between 1 to 50 in Java. How may I do that with the help of Math.random();? How do I bound the values that Math.random() returns?

Read More