3

I'm making a program to compare all the files on a 3Tb drive by hash and delete duplicates. I was initially going to use MD5, but was worried that with 3Tb of files, there was a slight chance of a collision that would cause a non duplicate to be deleted.

To remedy this I thought I would switch to SHA1, but then had the thought that if I compared both, there would be even less chance of collision.

Does anyone here know both algorithms well enough to confirm or deny this?

I'm considering the possibility that a SHA1 hash collision would necessarily mean the MD5 hash would also collide, in which case comparing both would just be a waste of time.

Improve this question
4
  • 1
    Your chance of getting an accidental collision is practically zero. Also see Strength of MD5 in finding duplicate files Commented Feb 16, 2018 at 1:38
  • who do you think you are? come off it! Google spent millions and years to produce one SHA collision and you have the audacity to suggest your little 3TB hard drive contains one? give me a break pal. /s TBH though, you have MUCH higher odds that your hard drive has stored the wrong bits. Commented Feb 16, 2018 at 14:21
  • @dandavis - I wasn't proposing my 3Tb has a sha-1 collision, I was worried about the minuscule chance of an MD5 collision. I was asking if anyone here could tell me if a sha-1 collision necessarily implies an MD5 collision, so that I didn't have to dig through each algorithm to decipher that for myself. If the algorithms are sufficiently different that that is not the case, then a concatenation of the two (MD5 hash, and SHA-1 hash) should be an even better comparison then either individually. Given SHA-1 is good enough, I was just curious if the MD5/SHA-1 was better. Commented Feb 16, 2018 at 18:00
  • rolling snake eyes 1000 times in a row then flipping heads 1000 times in a row is rarer than either alone, but don't bet on either. yes, md5!=sha collision-wise. Commented Feb 16, 2018 at 18:44

2 Answers 2

Reset to default
3

First off, yes both MD5 and SHA1 have been retired from cryptographic use because because it's possible to construct pairs of messages which produce the same hash value (aka "collisions"). That said, the chance of hitting a collision at random is absurdly low.

MD5 has a 128-bit output, SHA1 is 160 bits. Let's assume that a file being hashed will hash to one of the 2128 / 2160 possible outputs with equal probability, then on average, you expect to find a collision after hashing 2127 / 2159 different files.

Say you filled a hard drive with 512-bit (64 byte) files. You would need 2133 bits = 1.3 x 1027 TB for MD5, or 2165 bits = 5.8 x 1036 TB to store these files. For comparison, it's estimated that by 2020 the human species will be producing 44 zetabytes (4.4×1010 TB) of data per year.

So even if you hashed every file on the planet with MD5, you only have a 1 in 1026 chance of getting a collision by random chance.

To answer your original question:

To remedy this I thought I would switch to SHA1, but then had the thought that if I compared both, there would be even less chance of collision. Does anyone here know both algorithms well enough to confirm or deny this?

Yes, it's true that since they are different hash functions, the chances of there existing two messages which are collisions for both of them is minuscule. Whether it's less minuscule than the chance of collision in SHA-2/256 or SHA-2/512, I don't know. At this point we're debating astronomic probabilities (ie the chance of getting a collision is smaller than the number of atoms in the universe type thing) so /shrug ?

Now, if you are talking about malicious attacks (ie files specifically crafted to fool MD5 or SHA1), then maybe you have a point. ... In that case use SHA2 (which is 256 bits) and you're fine :)

Improve this answer
4
  • 4
    Actually, due to the Birthday Paradox, you expect to have a collision after 2^64 / 2^80 files. Commented Feb 16, 2018 at 5:24
  • @Mike Ounsworth - Thanks, I had that question as well (whether MD5+SHA-1 [288 bits] comparison is better than SHA-256 [256 bits]), but my question is about SHA-1 comparison vs MD5+SHA-1 comparison. I assume the algorithms are sufficiently different that MD5+SHA-1 would be better, but I'm asking if this is true. Commented Feb 16, 2018 at 18:08
  • Thanks @Mark, I've been meaning to come back and clean up my answer, but haven't had time. Commented Feb 26, 2018 at 15:46
  • @DaveGoldsmith Short answer: yes MD5+SHA-1 is stronger (more bits of security) than SHA-1 by itself. HOWEVER but not as strong as SHA-2 by itself, which will also be faster (better performance) and has no known attacks against it, so I strongly recommend that you just do that. Commented Feb 26, 2018 at 15:51
2

Mike's answer, extended with the birthday paradox comment, is good. This isn't actually an answer to your question but an alternative approach to your problem that will set your mind at ease if you're not already convinced by the math everybody else threw at you.

As everyone here has already said, hash collisions are very, very, very unlikely.

But if you want to be 100% certain before deleting a duplicate that might not be one, simply compare the files in question byte for byte before deleting the copy.

Determining the hash of a file requires you to read the whole file anyway. You will be busy for a while (think several hours up to several days, depending on the speed of your drive) simply generating hashes for all your files. So assuming you find 1% possible duplicates after having hashed every file, having to read these 1% of them again for byte for byte comparison will not add much overhead.

Another (very easy and practically free) test you could add before byte-comparing the files is to compare the file size. If it doesn't match, the files are obviously not identical, even if their hashes collide. But the test is pretty much pointless, since it will almost certainly not safe you from byte-comparing even a single pair of files that have duplicate hashes.

Improve this answer

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.