9
$\begingroup$

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

I already have the process down:

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.

$\endgroup$
6
  • 6
    $\begingroup$ Byte-for-byte comparison is faster than MD5 or CRC, unless you don't want to upload whole file and you compute hash on client's computer. But if files are small why bother? Is this cryptography related? $\endgroup$
    – LightBit
    Oct 15, 2014 at 16:13
  • $\begingroup$ If you are not afraid of obnoxious users creating deliberate hash collisions then you could of course just use rsync or one of the many related utilities. $\endgroup$
    – Maarten Bodewes
    Oct 15, 2014 at 16:24
  • 2
    $\begingroup$ @LightBit Or if you can pre-compute hashes they will speed up the protocol later on. If you use something like ZFS then you get this functionality for free, if I'm not mistaken. $\endgroup$
    – Maarten Bodewes
    Oct 15, 2014 at 16:26
  • $\begingroup$ @owlstead That is true. I think in all this I have discovered that the whole "compare hashes" shortcut pretty much requires that you do as you say and store them. We have so many of these files (and they're so small) that I doubt it would be worth it to save hashes for eeeeevery one for this case. $\endgroup$
    – Gutblender
    Oct 15, 2014 at 17:21
  • $\begingroup$ @Gutblender True, makes much less sense for small files. Although hashes of course are really small, 32 bytes at most. And you could create a hash tree and check a complete folder at once as well. $\endgroup$
    – Maarten Bodewes
    Oct 15, 2014 at 18:37

5 Answers 5

11
$\begingroup$

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.

$\endgroup$
5
  • 2
    $\begingroup$ And so, if MD5 reads pretty much the whole file I'd be better off just doing a byte-for-byte comparison since I gotta read the whole file anyway. And about collisions: see my edit. $\endgroup$
    – Gutblender
    Oct 15, 2014 at 16:56
  • 2
    $\begingroup$ @Gutblender Indeed, MD5 does many computations on whole file. $\endgroup$
    – LightBit
    Oct 15, 2014 at 17:06
  • 3
    $\begingroup$ What MD5 (or, ideally, a better hash function like SHA-2 or BLAKE2b) gets you is a short token that you can compare to later. Doing a byte-by-byte comparison involves reading both files entire contents from disk in order to compare them. If you, for instance, have 100 files and a new one is uploaded, you would have to compare against all 100 (or if you store them in sorted order, you can use a binary search). With a hash, you read each file once and then compare the short 128-bit or 256-bit string for each of them (again, using a binary search through, e.g., a database index). $\endgroup$ Oct 15, 2014 at 19:28
  • $\begingroup$ @LightBit not quite on the whole file at the same time. You can compute MD5 or any modern hash by going through the file sequentially, just using 64 bytes (or a slightly larger chunk size) at a time, we store intermediate values and update them chunk by chunk. At the end of the data we just have to know the total length of the data we processed and do a final transform to compute the final hash. All bytes are used but all of them only during the processing of the chunk it's in, we don't revisit older data. $\endgroup$ Nov 21, 2021 at 14:49
  • $\begingroup$ @HennoBrandsma I did not say "at the same time". $\endgroup$
    – LightBit
    Nov 23, 2021 at 11:43
10
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ See my edit; I'm not worried about collisions. And I know I'll get the right answer from my function. I'm concerned with speed alone. $\endgroup$
    – Gutblender
    Oct 15, 2014 at 16:58
  • $\begingroup$ How can you be prepared for collisions? If you see the same hash value, you will skip (and your result will be incorrect). If you don't you are back to square one. $\endgroup$
    – Maarten Bodewes
    Oct 15, 2014 at 17:11
  • $\begingroup$ Read my question again. My idea (was, I guess) to use the hashes to look for an obvious inequality. If none is found, finally a byte-for-byte comparison is in order. Plus one to your answer, though, for recommending algorithms. $\endgroup$
    – Gutblender
    Oct 15, 2014 at 17:17
  • $\begingroup$ I understand that, but are you only going to copy files with no obvious inequalities? So, if there is no obvious inequality, you leave it? Wouldn't that cause corruption? $\endgroup$
    – Maarten Bodewes
    Oct 15, 2014 at 18:35
  • $\begingroup$ I'm not sure what you mean by "leave it." If there is no obvious inequality, I do the final test that is right 100% of the time: byte-by-byte. How would I cause corruption? I'm not writing to any file for this test. $\endgroup$
    – Gutblender
    Oct 15, 2014 at 20:28
4
$\begingroup$

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.

$\endgroup$
7
  • 3
    $\begingroup$ You might want to tone down your BLAKE2 advertising a bit. Your argument equally applies to other collision resistant hashes. You can mention BLAKE2 as a particularly fast and still secure choice, but it shouldn't be the main focus of your answer, since the question isn't about choosing a hash function. $\endgroup$ Sep 27, 2016 at 10:00
  • $\begingroup$ Surely the pigeonhole principle applies in small universes too? Or if you mean that the numbers say it's mind-bogglingly improbably to hit a collision, then I suggest you show the numbers. Also, you might add some references to that "X is probably a lot stronger" claim which you keep repeating. Especially if you are one of the authors, who should have some readily available. $\endgroup$
    – ilkkachu
    Sep 27, 2016 at 21:35
  • 3
    $\begingroup$ @ilkkachu The irrelevance for accidential collisions follows directly from the output size and the birthday problem. A generic collision attack has a cost of $2^{n/2}$ for an n bit hash, which should be sill infeasible for several decades for a 256 bit hash (and completely infeasible for 512 bit hashes). Cryptography is all about things that exist but are infeasible to find, so the pigeonhole principle has little practical relevance. $\endgroup$ Sep 28, 2016 at 9:42
  • 2
    $\begingroup$ @ilkkachu Comparing strength against cryptoanalysis is difficult because we can't know future developments. The best we can do is looking at round reduced attacks. I'm pretty comfortable claiming that BLAKE2 is stronger than RIPEMD160, Tiger or SHA1. SHA256 has a larger fraction of broken rounds than BLAKE2, but on the other hand it has seen more analysis over the years. So I think that BLAKE2 is probably stronger than SHA2 but weaker than SHA3, but that's not certain. $\endgroup$ Sep 28, 2016 at 9:45
  • 1
    $\begingroup$ Re: BLAKE2 advertising: the Q was about speed, so it doesn't seem right to recommend switching from MD5 to SHA2 or anything else slower. BLAKE2 is the only alternative I can think of that is secure, is faster than MD5, and is widely-used/widely-available. $\endgroup$
    – Zooko
    Sep 30, 2016 at 21:25
0
$\begingroup$

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"

$\endgroup$
3
  • $\begingroup$ I don't think that's correct. A secure hash function (not MD5) can tell you whether two files whose sources you do not trust are identical or not. That's the definition of "security" for a secure hash function. What you said is correct for MD5, though, which is why MD5 is not secure. $\endgroup$
    – Zooko
    Sep 26, 2016 at 21:25
  • $\begingroup$ @zooko: well, if your file is N bytes, and the hash is M bytes, and (usually) m<N (m is usually many orders of magnitude smaller than N) : there will be a LOT of possible collisions (see: pidgeonhole principle)... so, like I said in the first sentence: "If you want to ensure both files are the same, you'll have to resort to comparing them byte-per-byte." They may be "very rare in usual circumstances", but it's not enough to rely on luck, whatever the odds, if you need certainty... $\endgroup$ Sep 27, 2016 at 11:17
  • $\begingroup$ @OlivierDulac Since the risk of bugs or random hardware errors vastly exceeds the change of random collisions in a good cryptographic hash, that definition of certainty is rather silly. $\endgroup$ Sep 27, 2016 at 18:57
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.