9 ms·

Why it's hard to write a dupefinder

• bpchaps 11y 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 11y ago
    I 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 11y ago
    You saw a full 128 bit collision on real files? They were right not to believe you...
    • bpchaps 11y 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 11y 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 11y 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 11y 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 11y ago
            See my reply to the sibiling comment. I don't believe we've seen an accidential collicion yet.
            • Retric 11y 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 11y 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 11y ago
    • flabbitybloo 11y 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 11y 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.
  • marcoperaza 11y ago
    Like 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 11y 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 11y ago
      Mind 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 11y ago
    MD5 + File byte size should be a reliable indicator that two files are actually the same.
    • troels 11y ago
      Still not a guarantee though ..
    • yoodenvranx 11y ago
      What is more unique? A 64 bit checksum + 64 bit filesize or a 128 bit checksum?
      • jzwinck 11y ago
        The 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 11y ago
          I 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 11y ago
            You'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 11y ago
              Very 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 11y ago
    Show the collision or it didn't happen. Sure it wasn't sum instead of md5sum?
    • bpchaps 11y ago
      Read my comment 30 minutes before yours. I'm pretty much conceding. This was also 5 years ago on a rhel4 machine, fwiw.
• signa11 11y ago
  one simple option might be to just use sha256 sums on files. if done incrementally, it's not that expensive computationally, unless files are very large (couple of gb's). one way to mitigate that might be take a _few_ random, say, 1k chunks of file content, and hash those. as long as you have a map of (offset, hash) de-duping should be just fine. the only thing is, i don't really know, what an upper bound on 'few samples' would be like. asymptotically, it should approach file-size/chunk-size, but ideally, it should be way less than that. any ideas on how to determine a minimal but complete set ?
  • Someone 11y ago
    The minimal set is to use full content of the file. Consider the case of a log file and its backup made one short log message earlier. If you want to gamble on using only a partial hash, I would hash the last few kb of each file, as that (at least based on this 30-second 'analysis' of the problem domain) likely would work better in practice. Theoretically, it is as vulnerable, though. Edit: if you have a VM image on your disk, and that small append happens to a log file in the image, that small change can happen anywhere. It also can be even smaller; someone might run 'touch' on an already existing file. Theoretically, that could be a one-byte change.
    • daurnimator 11y ago
      The idea is to use a two stage process: 1. take a sha1 hash of the last 4KB of each file. 2. for any equal hashes, compare the whole file. With this method you should be able to skip reading many large files in their entirety.
      • Someone 11y ago
        That is an idea, and it would, in typical cases, avoid reading most large files in their entirety, but it is not what I read in signa11's comment.
    • gpvos 11y ago
      A length check would catch the log file case. But really, just hash the whole file. As an optimization, you might want to check for files with holes in them ("sparse" files). Not sure how to do that, though.
• rurban 11y ago
  we wrote such dupefinders as fun hackathon contest organized by the dallas perl user group 2013: http://perlmonks.org/?node_id=1067570 http://perlmonks.org/?node_id=1067570 discussion at http://mail.pm.org/pipermail/dfw-pm/2013-December/thread.html http://mail.pm.org/pipermail/dfw-pm/2013-December/thread.htm... => http://dfw.pm.org/winners.html http://dfw.pm.org/winners.html it is really not easy. I used as only one bloom hashes, which explains why mine was fastest and smallest, but unfortunately not correct.
• deleted 11y ago
  [deleted]
• gwillen 11y ago
  I can think of a slightly more general solution to the problem of not being sure if A and B are different views on the same file or not, especially if you plan to hardlink one to the other: Hardlink A to a tempfile, hardlink the tempfile in place of both A and B, then remove the tempfile. This will give the right outcome regardless of whether A and B are secretly the same underlying file (assuming that they are on the same filesystem).
• mixu 11y ago
  I wrote one of these for fun a while back using the following approach: - Files are indexed by inode and device, files with the same inode + device are considered equal. (My main use case for this was to bundle up JS files.) - Files are then indexed by size; only files with the same size are compared. - During comparison, the files are read at block sizes increasing in powers of two, starting with 2k. The blocks are hashed and compared, and if they do not match the comparison is stopped early (often without having to read the full file). If all the hashes are equal, then the files are considered to be equal. - Hashes are only computed when needed and cached in memory. Since the hash block size increases in powers of two, only a few dozen hashes are needed even for large files (reducing memory usage compared to a fixed hash block size). link: https://github.com/mixu/file-dedupe https://github.com/mixu/file-dedupe
  • liw 11y ago
    I wrote mine along similar lines, except without using hashing at all. Files of identical size are compared byte-by-byte instead, until first difference or end of file. As many files as possible at a time, of course, to avoid having to read through files multiple times. This avoids any uncertainty about hash collisions. To find out how many files of each size you have: find ~ -type f -printf '%s\n' | sort | uniq -c | sort -n
    • hvidgaard 11y ago
      A hash is often use for an online algorithm. If you know the hash you know there is a potential for dedupe, and you can do a byte for byte comparison. I suppose you could use size as a prefilter for dedupe. This is if you do dedupe on a file level. Dedupe on block level doesn't care about the content, only the blocks, and it's not unusual to see for instance mp3 files with the same mp3 stream but different metadata. You cannot do the latter without hashing.
  • pjc50 11y ago
    The "compare by front first" method sounds quite like a prefix tree.
• pixelbeat 11y ago
  The approach that http://www.pixelbeat.org/fslint http://www.pixelbeat.org/fslint takes is to md5 and sha1 the files to avoid false positives. The core of the duplicate detection is the shell script here: https://github.com/pixelb/fslint/blob/ffcd3b85/fslint/findup#L162 https://github.com/pixelb/fslint/blob/ffcd3b85/fslint/findup...
• coroutines 11y ago
  Friend wrote this a long time ago when he was a young C++ coder. It's hosted on another friends' Github but the author is John Brooks, the author of Ricochet. https://github.com/rburchell/fastdup https://github.com/rburchell/fastdup :-)
• oever 11y ago
  I did some quick checks to investigate how size helps with deduplication. Size is a fast initial differentiator because scanning for file size only needs to read metadata, but how good does it differentiate? # all files find ~ -type f | wc -l 1098045 # files with a unique size find ~ -type f -printf '%s\n'|sort|uniq -c|grep ' 1 '|wc -l 48437 # most prevalent sizes (prevalence vs size) find ~ -type f -printf '%s\n'|sort |uniq -c |sort -nr|head 36972 0 12707 24 9480 22 8036 39 5025 12 4804 26 3879 6 3232 76 2946 38 2855 20 In my home dir, less than 5% of files have a unique size.