Comparing Files: Is it better to use multiple hash algorithms or just one?

Question

I'm looking to compare (for byte-for-byte equality) two binary files.

I already have the process down:

• Check for existence etc.
• Compare file lengths
• Use a hash or CRC of a sort (right now I use MD5) to look for an obvious inequality
• Finally, byte-for-byte compare them (I have a way of doing this in chunks to speed it up).

Note: the last bullet means I am fully aware of, and prepared for, collisions. I am aware that two identical hashes does not imply equality, but two different hashes confirms inequality.

Here are my thoughts on this so far:

• The MD5 function I'm using just takes a file stream and gives me the results. I'm a crypto noob so I don't know much about this algorithm, but if there are random reads and writes (totalling a fraction of the file size) this would likely be much faster than reading in the whole file, or using its ComputeHash(byte[]) overload. That means it would be much faster than reading the file for the byte-for-byte comparison
• On the other hand, to make a hash that's based very strongly on the file's contents so that one small change has a good chance of changing the hash, I would think it would need to read a good chunk of the file, so maybe this isn't much faster.
• The point with the thoughts above is this: if the hash computations for (weak) comparison are significantly faster than the raw comparison, then it appears it would be worth using multiple different hash algorithms before the raw comparison may be necessary. But is this true?

My particular application: These are small (a few KB) binary files I have a user upload to an app we host on our network. If it's different than our network copy I want to force them to update our network before they can do things with it. However, I don't want to limit my function to this application, but learn how far it may go with others.

Now all I'm wondering is this: Is it better to use multiple hash algorithms to do such a comparison?

Bonus Points: If you think I could be using different algorithms for speed, feel free to recommend.

Answer 1

MD5 is vulnerable to a lot of collision attacks, so if you don't trust the users it is possible for them to make files which hash to the same value as other files but which are not in fact the same.

I think you are misunderstanding how a hash works though. It does not read bits and pieces of the file, it processes the whole thing into a small output which is a "signature" of that file. With very, very high probability (if your hash function is good) it is unlikely that two files will create the same hash if they are not, in fact, the same file. But, it is not by itself any faster than comparing piecewise whether two files are equal.

Where it helps is when you have a bunch of files and you want to check whether a new file is the same as one that you already have. You can store the individual hashes of the files, and then just check the hash of the new file against all of the existing hashes. Now instead of manually checking file vs file over and over, you can just compare the small hash values.

Answer 2

No, if you use a good secure hash algorithm such as one of the SHA-2 candidates (e.g. SHA-512/256) then you don't need to use multiple hash algorithms. The hash generated is already unique in the sense that you won't be able to find another file with the same hash (this is called a collision).

MD5, as mentioned, is not secure - you can deliberately create collisions. Currently you need to pre-compute such files at the same time though, you cannot just create a collision for a random, pre-existing file. This may change in the future, and SHA-1 may become vulnerable as well.

SHA-256 is most likely slower than SHA-512 on platforms that use 64 bit computing. So SHA-512 seems to be a good candidate. Note that you will have to balance using SHA-512 with the network speed; for very high bandwidth performing a binary compare may be faster.

Also note that there are many utilities out there that already perform this kind of comparison for copying (for future readers, it seems you only need the comparison); rsync uses MD5, there is git, ZFS already performs hashing etc. etc.

Answer 3

I'd suggest using BLAKE2 instead of MD5 because it is faster than MD5 and it is secure against collision attacks, which MD5 is not. (Disclosure: I'm one of the authors of BLAKE2, but if you ask a cryptographer who is not an author of BLAKE2, they'll agree that BLAKE2 is faster and more secure than MD5.)

And, I'd suggest skipping the byte-for-byte comparison, because unless someday there comes a new cryptographic discovery which breaks BLAKE2, then the byte-for-byte comparison can never give you a different result than the BLAKE2 comparison result.

And do not listen to people who tell you that secure hash functions can sometimes give an accidental collision because of some theoretical argument like the Pigeonhole Principle. That cannot happen in the real universe, only in a hypothetical alternate universe that is a lot bigger or has different physics.

You can listen to people who say that cryptographic hash function can have an intentional collision because the hash function got broken by a new cryptographic breakthrough, but there is no reason to believe that this will happen to BLAKE2 in the forseeable future. It hasn't happened to RIPEMD in 20 years, it hasn't happened to Tiger in 20 years, it hasn't happened to SHA-256 in 10 years, and BLAKE2 is probably a lot stronger than any of those three. (It did happen to SHA-1 eleven years go and Panama 9 years ago, but BLAKE2 is a lot stronger than either of those two.)

Or, if it is better for your application to do the byte-for-byte comparison, then skip doing the hash function comparison. :-) This isn't a case where belt-and-suspenders is better, this is a case where the belt and the suspenders are likely to get snagged on each other and you should just choose the one that is best for you.

The way they can get snagged on each other is that there can be a bug in your code or in the implementation of one or the other. The best way to avoid bugs in code is to not have the code, so delete the code for the less useful one.

Answer 4

If you want to ensure both files are the same, you'll have to resort to comparing them byte-per-byte.

Using a hash algorithm is usually used to (try to) ensure that a file that is supposed to be correct has been correctly transmitted to its destination. You know the hash of the correct file, and if the file you got from a reputable source and the right file is not identical, then it is sure that there was a problem and you should fetch it again. If the hash are identical, in this case it is "quite likely" that the file was correctly transmitted (not 100% sure, but good enough as you know you copied from the right source and from the right file, and having a corresponding hash over a series of mistransmitted bytes is highly unlikely in that case).

But to compare 2 files (without knowing where the 2nd comes from, ie, without knowing if it is already supposed to be a trusted copy of the 1st file) and be sure they are identical, you can only compare the whole files. No shortcuts.

(Which you are already doing in your last step. Good.)

Now, having different hash for the "intermediary step" doesn't sound so useful... if the (single) hash differs, they are different. If they match, you do the final byte-per-byte comparison, and will know for sure if they are the same. Adding an extra "intermedate" hash comparison will not really improve the likelyhood of detecting a collision, and in any case you'll always end up doing the last step, so better to save that extra hash's computation time : it is useless in your case.

Edit : It seems I (unfairly, to me) receive downvotes, whereas my answer adress the "need to be SURE files are equal" issue.

To illustrate why I think hashes, however unlikely a collision can be, are far from being enough for ensuring equality:

If we limit ourselves to just 1kb (or less) length files, and use a 2048 bit "perfect hash" to hash them, here is some eye-opening maths:

# perl
use bignum;

$x = 2 ** (1024*8) ; # nb of possible 1kb files, 
    # ie, files that can be represented with 1048*8 bits ranging from:
    #    "0000000....00000000" (all 8192 bits are zeroes, in binary)
    # to "1111111....11111111" (all 8192 bits are ones)

print "\nNumber of possible 1kb files:\n";
print $x,"\n";

$h = 2 ** 2048 ;   # nb of possible hash values for a 2048 bit hash

print "\nNumber of possible hash values for a 2048 bit hash:\n";
print $h,"\n";

print "\nSo for each hash value, there can be this many files competing for that hashed value\n";
print "(this is a mean value... some slots may receive many, many more files, others many, many times less)\n";
print $x / $h, "\n" ;

Number of possible 1kb files: 1090748135619415929462984244733782862448264161996232692431832786189721331849119295216264234525201987223957291796157025273109870820177184063610979765077554799078906298842192989538609825228048205159696851613591638196771886542609324560121290553901886301017900252535799917200010079600026535836800905297805880952350501630195475653911005312364560014847426035293551245843928918752768696279344088055617515694349945406677825140814900616105920256438504578013326493565836047242407382442812245131517757519164899226365743722432277368075027627883045206501792761700945699168497257879683851737049996900961120515655050115561271491492515342105748966629547032786321505730828430221664970324396138635251626409516168005427623435996308921691446181187406395310665404885739434832877428167407495370993511868756359970390117021823616749458620969857006263612082706715408157066575137281027022310927564910276759160520878304632411049364568754920967322982459184763427383790272448438018526977764941072715611580434690827459339991961414242741410599117426060556483763756314527611362658628383368621157993638020878537675545336789915694234433955666315070087213535470255670312004130725495834508357439653828936077080978550578912967907352780054935621561090795845172954115972927479877527738560008204118558930004777748727761853813510493840581861598652211605960308356405941821189714037868726219481498727603653616298856174822413033485438785324024751419417183012281078209729303537372804574372095228703622776363945290869806258422355148507571039619387449629866808188769662815778153079393179093143648340761738581819563002994422790754955061288818308430079648693232179158765918035565216157115402992120276155607873107937477466841528362987708699450152031231862594203085693838944657061346236704234026821102958954951197087076546186622796294536451620756509351018906023773821539532776208676978589731966330308893304665169436185078350641568336944530051437491311298834367265238595404904273455928723949525227184617404367854754610474377019768025576605881038077270707717942221977090385438585844095492116099852538903974655703943973086090930596963360767529964938414598185705963754561497355827813623833288906309004288017321424808663962671333528009232758350873059614118723781422101460198615747386855096896089189180441339558524822867541113212638793675567650340362970031930023397828465318547238244232028015189689660418822976000815437610652254270163595650875433851147123214227266605403581781469090806576468950587661997186505665475715792896

Number of possible hash values for a 2048 bit hash:
32317006071311007300714876688669951960444102669715484032130345427524655138867890893197201411522913463688717960921898019494119559150490921095088152386448283120630877367300996091750197750389652106796057638384067568276792218642619756161838094338476170470581645852036305042887575891541065808607552399123930385521914333389668342420684974786564569494856176035326322058077805659331026192708460314150258592864177116725943603718461857357598351152301645904403697613233287231227125684710820209725157101726931323469678542580656697935045997268352998638215525166389437335543602135433229604645318478604952148193555853611059596230656

So for each hash value, there can be this many 1k files competing for that hashed value
(this is a mean value... some slots may receive many, many more files, others many, many times less)
33751521821438561184911174488682640477480000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

• the first number, possible number of 1024*8 bits files, ie of 1kb length files, has : 2467 digits in the decimal representation.
• The 2nd number, number of 2038 bit hash values, have 617 digits.
• So for 1kb length files, the last number above shows that there is a HUGE "mean" number (that number has 1850 digits!) of files competing for each hash value...

This is very hard, for me, to dismiss, however unlikely this happens "in real life"... There is orders of magnitudes many more possible files than there are hash values, so to ensure 2 files are identical, you HAVE to compare them byte per byte...)

And I limited myself to 1kb length files, but they can have from 0 to several tb, so the real number of "possible files competing for your 2048 bit hash value" is many, many, many orders of magnitude greater... there are that (much, much bigger number than the one above) many files that could end up in each given hash value (or many more, or many less, for some of the hash values, if the repartition is not equal in each).

And to drive the point further home : https://en.wikipedia.org/wiki/Birthday_problem shows that the possibility of a hash collision between 2 random files can become rapidly bigger than expected, if you have (like we do, IRL, no this planet) many, many files, and there are such a great number of "amount of possible files competing for each hash slot".

"Compare the files bytes per bytes, that's the only way to be sure"

Answer 5

No matter how fast your hash function is, it will always have to:

1. Take in every byte of your data and consider it in processing (it does not consider subsets of your data, which would be a bad idea in the first place)
2. Consume equal or more clock cycles than a simple comparison.

The hash algorithm doesn't "know" the hash until it has fully computed it, so it actually won't even detect the inequality until the entire file has been processed. In this case, where the difference between two files is somewhere in the middle or beginning, the direct comparison will be even faster than the hash algorithm (all other things being equal), unless you implement some data structure to cumbersomely store the intermediate states of computing the hash (again, not a good idea). The moment the direct comparison finds some incongruity, it can immediately halt and return a false result. We can't do that with a hash.

What you describe as finding "obvious inequalities" might be confused with the function of a bloom filter, where you are checking if a file belongs to a large set of files probabilistically. This is used for space efficiency, not compute efficiency. It becomes useful because our set is heavily used, not just checked once, so our single hash computation may cost some CPU, but it pays for itself over time as the hash is used more and more. What you do is compute a simple, non-cryptographic hash function to see if it belongs to a table of hashed keys. If it's there, it might be in the set, if it's not, it cannot be in the set. If you store the actual set somewhere on a server, then the client now has space savings.

Why is this different than just a simple file comparison? Suppose your files are both really large. You employ a super fast hash algorithm to create checksums that you didn't already know for the sake of comparison. Now you check that the files have the same checksum.

1. The checksums don't match. Great. We're done. But could we have done better? What if we just did a byte-for-byte comparison from the beginning? Again, that would be faster. Comparison is one of the simplest things you can do with a computer (so simple that you can express it as just XNOR and AND). Compare that with something like CubeHash. This algorithm is still very simple, but nowhere near as simple as just checking if two bytes match. Meanwhile, you are not taking advantage of your full disk speed if you have an SSD.
2. The checksums match. As you mentioned, we are uncertain if they are equal. We have to do another byte-to-byte comparison. Why didn't we just do that in the first place? We now spent at least 2 times the effort for the same result, with no added benefit.

However, let's say you already knew the checksum of a file because it was computed earlier. It's a given, and costs zero dollars to utilize. Now it may make sense to do a checksum computation to save time because your CPU and disk speed are faster than your Internet connection, so it would save time to first check if the files could be the same, and then do the "worst-case" byte-for-byte comparison if they match. Had it not matched checksums, you would've saved time.

Additional note: Assuming you store the file in some RAM, you get another benefit from raw comparison: a problem that is embarrassingly parallel. Trying to do this with any hash algorithm will result in a race condition and won't work.