8 ms·

Aren't all hashing algorithms vulnerable to the possibility for collisions (albeit with different degrees of difficulty)? It sounds like the problem here is mor

Aren't all hashing algorithms vulnerable to the possibility for collisions (albeit with different degrees of difficulty)? It sounds like the problem here is more related to the logic that relies on a hash alone to make important decisions. Not saying that MD5 is a good choice in this case, just that we may be blaming the wrong thing.

malka 11y ago
Yeah, but MD5 is broken in the sense that you can generate a collision on purpose.
kedean 11y ago
The collision-resistance property that all good hashes should have (and md5 lacks) states that an attacker with an input and its hash cannot arbitrarily produce a second input with the same hash. The possibility of it happening in the wild will always exist with hashes by their finite nature, but the only way an attacker should be able to find collisions is by enumerating the input space (rainbow table generation).
- jimrandomh 11y ago
  No, the property you describe is called "preimage resistance". Collision resistance is stronger; it states that an attacker should not be able to create a pair of inputs with the same hash. In the case of md5, creating a pair of inputs with the same hash is easier than creating another input with the same hash as something else which you didn't yourself generate. The MD5 algorithm is known to lack collision resistance, but whether it has preimage resistance is less certain; mathematical advances have weakened its preimage resistance, but not yet to the point of demonstrating a practical preimage attack.
  - 4mnt 11y ago
    > In the case of md5, creating a pair of inputs with the same hash is easier than creating another input with the same hash as something else which you didn't yourself generate. This is the case with all instances of seeking a collision, due to the birthday paradox [0] 0: https://en.wikipedia.org/wiki/Birthday_attack https://en.wikipedia.org/wiki/Birthday_attack
    - cstejerean 11y ago
      The birthday paradox helps with the case of finding any two random inputs that have the same hash. The problem with MD5 is that it's feasible to craft two specific inputs that happen to have the same hash.
  - kedean 11y ago
    My mistake, I always mixed those two up. Both properties address OP, though, as MD5 is not suspected to have preimage resistance either (it's just not to the point of somebody having done it yet).
  - garrettr_ 11y ago
    Nitpick: the property OP describes is actually second pre-image resistance, not preimage resistance (or collision resistance). See https://en.wikipedia.org/wiki/Cryptographic_hash_function#Properties https://en.wikipedia.org/wiki/Cryptographic_hash_function#Pr...
mikeash 11y ago
Your parenthetical is the key, though. There's a big difference between a hash algorithm where generating a collision requires a few minutes of work on a cheap computer (MD5, now) and a hash algorithm where generating a collision requires a computer the size of the universe operating for a trillion trillion years (any good cryptographically secure hash).
- dperfect 11y ago
  Cool - didn't realize the difference was so great. I've always known that the good algorithms are better because they're more difficult to brute-force, but always wondered if it's just a matter of a few years before the "impossible" becomes possible. Your illustration helps clarify that improbability in my mind - thanks!
  - rictic 11y ago
    MD5 is also supposed to require a tremendous amount of computation, it's just that there are weaknesses in the algorithm that were eventually discovered, such that an attacker can short circuit much of that work. The reason that SHA-1 is being sunset is that some preliminary results by researchers suggest that it also has weaknesses that can enable it to be short circuited, and that researchers appear to be on a path to discovering those weaknesses.
    - dperfect 11y ago
      Hmmm... so the takeaway for me is that when designing critical systems that rely on hashes/fingerprints as identifiers, we should probably treat those as transient identifiers with a reasonable expectation of migrating them as newer algorithms replace older broken ones. Does that sound right?
      - Diederich 11y ago
        That's correct.
hinkley 11y ago
Yes, but the complexity of finding a collision in SHA1 is about 2^14 higher than MD5, and even SHA1 is being sunset by many people.

malka 11y ago

Yeah, but MD5 is broken in the sense that you can generate a collision on purpose.

kedean 11y ago

The collision-resistance property that all good hashes should have (and md5 lacks) states that an attacker with an input and its hash cannot arbitrarily produce a second input with the same hash. The possibility of it happening in the wild will always exist with hashes by their finite nature, but the only way an attacker should be able to find collisions is by enumerating the input space (rainbow table generation).

jimrandomh 11y ago
No, the property you describe is called "preimage resistance". Collision resistance is stronger; it states that an attacker should not be able to create a pair of inputs with the same hash. In the case of md5, creating a pair of inputs with the same hash is easier than creating another input with the same hash as something else which you didn't yourself generate. The MD5 algorithm is known to lack collision resistance, but whether it has preimage resistance is less certain; mathematical advances have weakened its preimage resistance, but not yet to the point of demonstrating a practical preimage attack.
- 4mnt 11y ago
  > In the case of md5, creating a pair of inputs with the same hash is easier than creating another input with the same hash as something else which you didn't yourself generate. This is the case with all instances of seeking a collision, due to the birthday paradox [0] 0: https://en.wikipedia.org/wiki/Birthday_attack https://en.wikipedia.org/wiki/Birthday_attack
  - cstejerean 11y ago
    The birthday paradox helps with the case of finding any two random inputs that have the same hash. The problem with MD5 is that it's feasible to craft two specific inputs that happen to have the same hash.
- kedean 11y ago
  My mistake, I always mixed those two up. Both properties address OP, though, as MD5 is not suspected to have preimage resistance either (it's just not to the point of somebody having done it yet).
- garrettr_ 11y ago
  Nitpick: the property OP describes is actually second pre-image resistance, not preimage resistance (or collision resistance). See https://en.wikipedia.org/wiki/Cryptographic_hash_function#Properties https://en.wikipedia.org/wiki/Cryptographic_hash_function#Pr...

mikeash 11y ago

Your parenthetical is the key, though. There's a big difference between a hash algorithm where generating a collision requires a few minutes of work on a cheap computer (MD5, now) and a hash algorithm where generating a collision requires a computer the size of the universe operating for a trillion trillion years (any good cryptographically secure hash).

dperfect 11y ago
Cool - didn't realize the difference was so great. I've always known that the good algorithms are better because they're more difficult to brute-force, but always wondered if it's just a matter of a few years before the "impossible" becomes possible. Your illustration helps clarify that improbability in my mind - thanks!
- rictic 11y ago
  MD5 is also supposed to require a tremendous amount of computation, it's just that there are weaknesses in the algorithm that were eventually discovered, such that an attacker can short circuit much of that work. The reason that SHA-1 is being sunset is that some preliminary results by researchers suggest that it also has weaknesses that can enable it to be short circuited, and that researchers appear to be on a path to discovering those weaknesses.
  - dperfect 11y ago
    Hmmm... so the takeaway for me is that when designing critical systems that rely on hashes/fingerprints as identifiers, we should probably treat those as transient identifiers with a reasonable expectation of migrating them as newer algorithms replace older broken ones. Does that sound right?
    - Diederich 11y ago
      That's correct.

hinkley 11y ago

Yes, but the complexity of finding a collision in SHA1 is about 2^14 higher than MD5, and even SHA1 is being sunset by many people.