4 ms·

You saw a full 128 bit collision on real files? They were right not to believe you...

by kevinnk 10y ago

bpchaps 10y ago
Huh. I may stand corrected. I just looked up the odds, and it's uh. A lot higher probability than I thought. Heh. Makes me wonder now. Might've been a rogue rsync at the time or something, then. /shrug.
ubernostrum 10y ago
While it's rare, do remember that hash collisions need to be thought of in birthday-paradox terms, which does increase the chance of observing a collision significantly. Hitting MD5's birthday point (50% chance of collision) requires a couple tens of quintillions of hashes, but that's probably a lot smaller number than people expect, and a not-unreasonable number to see in a sufficiently large-scale data archiving system. (meanwhile there's stuff in the wild using things like Java hashCode() to determine identities, and the birthday point on that is only around 75k IIRC)
- hvidgaard 10y ago
  "probably a lot smaller number than people expect" If you crunch your way through files (and lets assume they're random from the hash functions point of view) for 10 years, you have to calculate the hash of 60.000.000.000 files / second - to have 50% chance of finding a collision. If the average filesize is 1 KB, that is ~56TB data every single second. Md5 is not bad as long as you're not expecting malicious input, or gigantic datasets.
  - Retric 10y ago
    Now spead that across 10 million system admins. An actual MD5 checksum in the Wild is vasty more likely to be brute forced, or a bug. However, it's reasonably likely to have happened.
    - hvidgaard 10y ago
      See my reply to the sibiling comment. I don't believe we've seen an accidential collicion yet.
      - Retric 10y ago
        Your math is off. You tried to calculate the odds that the next block would collide you want the odds that any of them would collide. https://en.wikipedia.org/wiki/Birthday_problem https://en.wikipedia.org/wiki/Birthday_problem X!/((X^n) * (X-n)!) It only takes 23 people to have a 50/50 shot of sharing a birthday. On the plus side MD5 is 128bits.
        hvidgaard 10y ago
        No, I used a reasonable approximation. Sqrt(2^128) is roughly in the ballpark of what is needed to have 50% of a collision, in fact it is slightly lower than the actual number. Incidently sqrt(2^128) is 2^64, which is the number I used.
  - ubernostrum 10y ago
    Well, a couple years ago it was reported that YouTube alone receives 300 hours' worth of video uploads every minute. That's without considering other social-media properties with file-upload capability, or PaaS offerings like AWS. So I'd say it's certain that the requisite number of MD5 hashes have been generated across the aggregate of those systems (assuming enough of them use MD5 in some fashion), and I'd personally bet money there's at least one real-world deployment out there that's handled enough all on its own to hit the birthday point.
    - hvidgaard 10y ago
      Humans really cannot fanthom the magnitude of the numbers involved here. 2^64 is an astronomically large number - it's mindboggling huge. Really, I will put money on the the claim that YouTube have not seen a collision yet. Let me explain: 300 hours every minute, equals 3006024*365.25 = 157.788.000 hours / year. Lets assume it's all HD and 2 gb an hour, that is ~30pb / year. Storing all that video surely uses large capacity harddrive with a 4k sector size, so that it the smallest it makes sense to perform dedupe on. That is ~82726 billion blocks / year. To have 50% probability of a collision, we need to calculate 2^64 blocks, so we need 222985 years of video before there is more than 50% probability. Lets move away from YouTube for a moment, and move towards the IP trafic as a whole. Cisco has estimated the total IP trafic to 27483 pb / month in 2011, if we're looking at the growth it is growing less and less for every year, and from 2010 to 2011 it was only 34% down from 65% from 2005 to 2006. I assume 30% growth from 2011 and forward, and we end up with ~291 exabytes / month, or 3497 exabytes / year in 2020, this is total IP trafic and will include a lot of duplicated data (e.g. Netflix streams). Again, lets assume a 4kb block, and the total estimated IP trafic in 2020 generates ~961e10^15 blocks. We need 2^64 blocks to have a 50% probability of collision, that is more than 19 times of the total estimated IP trafic in 2020, the vast majority of which is duplicated. My claim is that unless you're google, md5 is fine. If you're google, md5 is still fine, but you should be looking to prepare your system to accept a hash with a larger output space.
flabbitybloo 10y ago
http://natmchugh.blogspot.com/2014/10/how-i-made-two-php-files-with-same-md5.html http://natmchugh.blogspot.com/2014/10/how-i-made-two-php-fil... https://s3-eu-west-1.amazonaws.com/md5collisions/a.php https://s3-eu-west-1.amazonaws.com/md5collisions/a.php https://s3-eu-west-1.amazonaws.com/md5collisions/b.php https://s3-eu-west-1.amazonaws.com/md5collisions/b.php Obviously a contrived example, but given the above and other weaknesses md5 should not be considered safe for verifying file contents (at least from a security perspective).
- lomnakkus 10y ago
  Yeah, MD5 has been known to be broken if you can append binary data. (Not sure if that's been "beaten", maybe you don't need full binary data any longer.) ... but accidental collisions? That's still hugely more likely to be "you're misremembering" or "you misread" than a real collision.

You saw a full 128 bit collision on real files? They were right not to believe you...

by kevinnk 10y ago

You saw a full 128 bit collision on real files? They were right not to believe you...

Huh. I may stand corrected. I just looked up the odds, and it's uh. A lot higher probability than I thought. Heh. Makes me wonder now. Might've been a rogue rsync at the time or something, then. /shrug.

ubernostrum 10y ago

While it's rare, do remember that hash collisions need to be thought of in birthday-paradox terms, which does increase the chance of observing a collision significantly. Hitting MD5's birthday point (50% chance of collision) requires a couple tens of quintillions of hashes, but that's probably a lot smaller number than people expect, and a not-unreasonable number to see in a sufficiently large-scale data archiving system. (meanwhile there's stuff in the wild using things like Java hashCode() to determine identities, and the birthday point on that is only around 75k IIRC)

hvidgaard 10y ago
"probably a lot smaller number than people expect" If you crunch your way through files (and lets assume they're random from the hash functions point of view) for 10 years, you have to calculate the hash of 60.000.000.000 files / second - to have 50% chance of finding a collision. If the average filesize is 1 KB, that is ~56TB data every single second. Md5 is not bad as long as you're not expecting malicious input, or gigantic datasets.
- Retric 10y ago
  Now spead that across 10 million system admins. An actual MD5 checksum in the Wild is vasty more likely to be brute forced, or a bug. However, it's reasonably likely to have happened.
  - hvidgaard 10y ago
    See my reply to the sibiling comment. I don't believe we've seen an accidential collicion yet.
    - Retric 10y ago
      Your math is off. You tried to calculate the odds that the next block would collide you want the odds that any of them would collide. https://en.wikipedia.org/wiki/Birthday_problem https://en.wikipedia.org/wiki/Birthday_problem X!/((X^n) * (X-n)!) It only takes 23 people to have a 50/50 shot of sharing a birthday. On the plus side MD5 is 128bits.
      - hvidgaard 10y ago
        No, I used a reasonable approximation. Sqrt(2^128) is roughly in the ballpark of what is needed to have 50% of a collision, in fact it is slightly lower than the actual number. Incidently sqrt(2^128) is 2^64, which is the number I used.
- ubernostrum 10y ago
  Well, a couple years ago it was reported that YouTube alone receives 300 hours' worth of video uploads every minute. That's without considering other social-media properties with file-upload capability, or PaaS offerings like AWS. So I'd say it's certain that the requisite number of MD5 hashes have been generated across the aggregate of those systems (assuming enough of them use MD5 in some fashion), and I'd personally bet money there's at least one real-world deployment out there that's handled enough all on its own to hit the birthday point.
  - hvidgaard 10y ago
    Humans really cannot fanthom the magnitude of the numbers involved here. 2^64 is an astronomically large number - it's mindboggling huge. Really, I will put money on the the claim that YouTube have not seen a collision yet. Let me explain: 300 hours every minute, equals 3006024*365.25 = 157.788.000 hours / year. Lets assume it's all HD and 2 gb an hour, that is ~30pb / year. Storing all that video surely uses large capacity harddrive with a 4k sector size, so that it the smallest it makes sense to perform dedupe on. That is ~82726 billion blocks / year. To have 50% probability of a collision, we need to calculate 2^64 blocks, so we need 222985 years of video before there is more than 50% probability. Lets move away from YouTube for a moment, and move towards the IP trafic as a whole. Cisco has estimated the total IP trafic to 27483 pb / month in 2011, if we're looking at the growth it is growing less and less for every year, and from 2010 to 2011 it was only 34% down from 65% from 2005 to 2006. I assume 30% growth from 2011 and forward, and we end up with ~291 exabytes / month, or 3497 exabytes / year in 2020, this is total IP trafic and will include a lot of duplicated data (e.g. Netflix streams). Again, lets assume a 4kb block, and the total estimated IP trafic in 2020 generates ~961e10^15 blocks. We need 2^64 blocks to have a 50% probability of collision, that is more than 19 times of the total estimated IP trafic in 2020, the vast majority of which is duplicated. My claim is that unless you're google, md5 is fine. If you're google, md5 is still fine, but you should be looking to prepare your system to accept a hash with a larger output space.

flabbitybloo 10y ago

http://natmchugh.blogspot.com/2014/10/how-i-made-two-php-files-with-same-md5.html http://natmchugh.blogspot.com/2014/10/how-i-made-two-php-fil... https://s3-eu-west-1.amazonaws.com/md5collisions/a.php https://s3-eu-west-1.amazonaws.com/md5collisions/a.php https://s3-eu-west-1.amazonaws.com/md5collisions/b.php https://s3-eu-west-1.amazonaws.com/md5collisions/b.php Obviously a contrived example, but given the above and other weaknesses md5 should not be considered safe for verifying file contents (at least from a security perspective).

lomnakkus 10y ago
Yeah, MD5 has been known to be broken if you can append binary data. (Not sure if that's been "beaten", maybe you don't need full binary data any longer.) ... but accidental collisions? That's still hugely more likely to be "you're misremembering" or "you misread" than a real collision.