3

I am about to build a caching system based on md5 to generate file names out of lists of natural numbers. The inputs would be groups like: 1,18,94,100,266,1854.

I know there are some collisions in md5 but in all my reasearch I discovered only 2 of them. I know the chances to stumble upon one is very unlikely, however I wonder if there is anywhere a list with all of the md5 collisions discovered so far?

10
  • 2
    Is there a reason you're not using SHA-1 instead? So far there haven't been any practical collisions discovered.
    – Polynomial
    Aug 4, 2012 at 8:17
  • 1
    If your caching system doesn't need to worry against a malicious entity trying to create collisions, then you can safely use MD5 - if it's just your program against lady luck, the probability of stumbling upon a collision is basically zero. Otherwise, I recommend SHA256.
    – Thomas
    Aug 4, 2012 at 8:44
  • 3
    Also, the concept of checking against a "collision blacklist" is so anti-KISS that my eyes are bleeding. If an attacker can create one collision, he can most certainly create another, making your blacklist useless.
    – Thomas
    Aug 4, 2012 at 8:48
  • 1
    I'm not sure I'd advocate SHA256 for non-security-sensitive indexing purposes, since SHA1 is much faster. But both will do the job :)
    – Polynomial
    Aug 4, 2012 at 9:50
  • @Polynomial I meant SHA256 if the application is security-sensitive, the "otherwise" was a bit ambiguous, sorry. If speed was a real concern I would go for something like Skein though, but I agree that SHA-1 would be somewhat faster than SHA256 (but then I'm pretty sure a caching system would be dominated by disk latency/throughput, making speed irrelevant overall, but this is speculation).
    – Thomas
    Aug 4, 2012 at 11:07

2 Answers 2

11

See this page for a downloadable implementation of a generator of MD5 collisions, using Klima's method. On a Core2 2.4 GHz CPU, it produces on average one collision every 14 seconds (and that's using only one core; since the research entirely fits L1 cache, it scales optimally on multi-core CPU). I let it run a few weeks, and measured that over more than 100000 collisions.

So no, there's no index of all MD5 collisions. You'd better use a robust hash function. Try SHA-256 first; it is the usual recommendation. If (and only if) you hit an actual, measured performance issue with SHA-256, then you might look for alternate functions (a 2.4 GHZ Core2 CPU could still hash a few millions file names per second, so it takes a rather special situation for SHA-256 to actually have performance issues).

-9

It's impossible for you to encounter collision using group names in ascii for sure, so far ascii doesnt suffer from collision issue, as it has largely limited space which is reducing the collision probability.

You cant prove that the ascii comma separated digits produce collision for an unique key with md5, it can handle this much, which is provable empirically

3
  • 7
    Where do you get these untrue notions from? The encoding of the input to any even vaguely good hash has little to no effect on collisions....
    – nealmcb
    Aug 5, 2012 at 0:57
  • Pls check out MD5 collisions. Sep 1, 2012 at 14:54
  • Can you supply a reference of some kind?
    – E.S.
    Apr 6, 2015 at 19:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .