6 ms·
One of the odd things I've seen that marks a "good" admin from a "bad" admin is their reliance on md5s as a checksum for file differences for anything in bulk.
by bpchaps 10y ago
One of the odd things I've seen that marks a "good" admin from a "bad" admin is their reliance on md5s as a checksum for file differences for anything in bulk. It's extremely rare to see a collision, but it definitely happens (I've seen it once after a decently sized config change. Nobody believed me :( ). That's not to say it's not a useful hash, just that it should be used with caution.
- steve19 10y agoI will be honest dude, I don't believe a legit config file change could result in a collision (where appending random comments until a collision is found is not a legit edit, that's bruteforcing) But I do believe you thought it did, if that's any consolation ;) ... but I would loved to be proved wrong.
- kevinnk 10y agoYou saw a full 128 bit collision on real files? They were right not to believe you...
- bpchaps 10y agoHuh. 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 agoWhile 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 agoNow 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 agoSee my reply to the sibiling comment. I don't believe we've seen an accidential collicion yet.
- Retric 10y agoYour 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 agoNo, 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
- flabbitybloo 10y agohttp://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 agoYeah, 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.
- marcoperaza 10y agoLike others are saying, that's extremely unlikely to happen by chance, near impossible. If I saw such a collision, I'd strongly suspect the collision was intentional and malicious. Edit: After discounting bugs in whatever software found the collision. It could be a bug in the script.
- secfirstmd 10y ago"Crypto collision used to hijack Windows Update goes mainstream" http://www.theregister.co.uk/2014/11/05/md5_hash_collision/ http://www.theregister.co.uk/2014/11/05/md5_hash_collision/
- duskwuff 10y agoMind that that was intentional. Due to known weaknesses in MD5, it's much easier to engineer a collision than it is to come across one accidentally.
- true_religion 10y agoMD5 + File byte size should be a reliable indicator that two files are actually the same.
- troels 10y agoStill not a guarantee though ..
- yoodenvranx 10y agoWhat is more unique? A 64 bit checksum + 64 bit filesize or a 128 bit checksum?
- jzwinck 10y agoThe 128 bit checksum, because the real entropy of the file size is closer to 10-20 bits (most files aren't very large, and large files are sometimes multiples of common sizes like 1 KB). That's assuming a non-malicious, non-pathological system.
- yoodenvranx 10y agoI am pretty sure that this is a stupid question, but what about a 127 bit checksum and then 1 bit which shows if the filesize in bytes is even or odd vs a normal 128 bit checksum?
- jzwinck 10y agoYou're still giving up entropy because even-numbered file sizes are quite a bit more common: $ find / -ls | awk '{print $7}' >/tmp/filesizes $ rev /tmp/filesizes | cut -b1 | sort -n | uniq -c | sort -n 5718 5 5816 3 5823 1 5901 9 6463 7 7549 4 7958 8 8240 0 8991 6 14507 2
- bpchaps 10y agoVery cool. I just tried it on my own machine and got this (archlinux with lots and lots of python libraries/data junk): Changed the command up a bit since it was including zero byte files and directories: sudo find / -size +0 -type f -ls | awk '{print $7,$NF}' > /tmp/filesizes 110920 7 111306 5 111312 1 111345 9 111362 3 130138 0 130511 4 131528 8 139000 2 152213 6 Some other interesting things (dirname is too slow...): cat filesizes | grep "6 " | awk '{print $NF}' | sed 's/\/[^/]*$//' | sort | uniq -c | sort -nr | head 1607 /usr/share/man/man3 906 /home/matt/.cache/mozilla/firefox/8jc2n3qa.default/cache2/entries 825 /usr/bin 808 /home/matt/.tmux/resurrect Then again a lot of this is flawed because it's looking at /sys. Too lazy to fix it now :)
- sliken 10y agoShow the collision or it didn't happen. Sure it wasn't sum instead of md5sum?
- bpchaps 10y agoRead my comment 30 minutes before yours. I'm pretty much conceding. This was also 5 years ago on a rhel4 machine, fwiw.