6
$\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
    $\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 '14 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 - reinstate Monica Oct 15 '14 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 - reinstate Monica Oct 15 '14 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 '14 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 - reinstate Monica Oct 15 '14 at 18:37
8
$\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$
  • 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 '14 at 16:56
  • 2
    $\begingroup$ @Gutblender Indeed, MD5 does many computations on whole file. $\endgroup$ – LightBit Oct 15 '14 at 17:06
  • 1
    $\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$ – Stephen Touset Oct 15 '14 at 19:28
8
$\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$
  • $\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 '14 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 - reinstate Monica Oct 15 '14 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 '14 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 - reinstate Monica Oct 15 '14 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 '14 at 20:28
3
$\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$
  • 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$ – CodesInChaos Sep 27 '16 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 '16 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$ – CodesInChaos Sep 28 '16 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$ – CodesInChaos Sep 28 '16 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 '16 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$
  • $\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 '16 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$ – Olivier Dulac Sep 27 '16 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$ – CodesInChaos Sep 27 '16 at 18:57

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.