3 ms·

If collisions are not too hard to find, isn't the process just: 1: Steal database 2: find collision 3: authenticate with the input that hashes to the same valu

If collisions are not too hard to find, isn't the process just: 1: Steal database 2: find collision 3: authenticate with the input that hashes to the same value What stops that from happening?

teraflop 12y ago
Re-read that comment, particularly the part about the difference between a collision attack and a preimage attack. MD5 is (currently) vulnerable to collisions, but not to preimages. So you can find two inputs that have the same hash, but not an input that hashes to some particular value in a database.
vectorjohn 12y ago
@teraflop - Oh, so does that just mean basically that you can, e.g. generate a bunch of MD5 hashes and some will be the same? But if you have a target you're basically SOL finding a collision for that? That would make sense if that's what it means.
- teraflop 12y ago
  Yep. More specifically: if you just hash a bunch of arbitrary strings that aren't specially-constructed for the purpose of colliding, then collisions are basically random, and extremely improbable. But you can fairly easily generate two files, differing only in a small number of bits, with the same MD5 hash by taking advantage of the structure of the algorithm. Examples here: http://www.mscs.dal.ca/~selinger/md5collision/ http://www.mscs.dal.ca/~selinger/md5collision/
  - emn13 12y ago
    Another consequence of that is that even MD5 collisions aren't at all trivial to exploit in general. An attacker can create a collision, but it's a slow process, and the colliding content is pretty constrained. You'd probably need to be very well informed, and invest quite some creativity to find two messages that are "valid" to whatever system is processing those and have sufficiently different meanings to be useful to you. Clearly doable in specific instances, but it's not going to be an addition to the script-kiddie attack handbook anytime soon.

If collisions are not too hard to find, isn't the process just: 1: Steal database 2: find collision 3: authenticate with the input that hashes to the same value What stops that from happening?

teraflop 12y ago

Re-read that comment, particularly the part about the difference between a collision attack and a preimage attack. MD5 is (currently) vulnerable to collisions, but not to preimages. So you can find two inputs that have the same hash, but not an input that hashes to some particular value in a database.

vectorjohn 12y ago

@teraflop - Oh, so does that just mean basically that you can, e.g. generate a bunch of MD5 hashes and some will be the same? But if you have a target you're basically SOL finding a collision for that? That would make sense if that's what it means.

teraflop 12y ago
Yep. More specifically: if you just hash a bunch of arbitrary strings that aren't specially-constructed for the purpose of colliding, then collisions are basically random, and extremely improbable. But you can fairly easily generate two files, differing only in a small number of bits, with the same MD5 hash by taking advantage of the structure of the algorithm. Examples here: http://www.mscs.dal.ca/~selinger/md5collision/ http://www.mscs.dal.ca/~selinger/md5collision/
- emn13 12y ago
  Another consequence of that is that even MD5 collisions aren't at all trivial to exploit in general. An attacker can create a collision, but it's a slow process, and the colliding content is pretty constrained. You'd probably need to be very well informed, and invest quite some creativity to find two messages that are "valid" to whatever system is processing those and have sufficiently different meanings to be useful to you. Clearly doable in specific instances, but it's not going to be an addition to the script-kiddie attack handbook anytime soon.