What checksum algorithm should I use?

57
votes

I'm building a system which needs to be able to find if blobs of bytes have been updated. Rather than storing the whole blob (they can be up to 5MBs), I'm thinking I should compute a checksum of it, store this and compute the same checksum a little bit later, to see whether the blob has been updated.

The goal is to minimize the following (in that order) :

  • size of the checksum
  • time to compute
  • likeliness of collisions (2 identical checksums happening even if the content has been modified).

It is acceptable for our system to have collision not more than 1/1,000,000. The concern is not security, but simply update/error detection, so rare collisions are ok. (Which is why I put it last in the things to minimize).

Also, we cannot modify the blobs of text ourselves.

Of course, md5, crc or sha1 come to mind, and if I wanted a quick solution, I'd go for it. However, more than a quick solution, I'm looking for what could be a comparison of different methods as well as the pros and cons.

2
md5sha1checksumcrc
What is your concern, here? Are you simply checking to see whether your data blobs have changed since some earlier time, or are you trying to detect a malicious alteration? – dajames
Just trying to see if there has been any update in them. – Julien Genestoux
If you're not concerned about the possibility of malicious alteration but just want to track changes, and if (as you say elsewhere) you can live with an accidental collision probablility of one in a million, then go with CRC -- it's faster than MD5 or SHA and the chance of collisions is well within your spec. – dajames
I would recommend CRC-64. It is much much faster than cryptographic hashes and should meet your requirements for collision probability. – President James K. Polk

2 Answers

29
votes

I suggest you have a look to this SO page, CRC vs MD5/SHA1.
Speed and collisions are discussed in this other thread.
And as always Wikipedia is your friend.

If I had to choose, there is an important question to answer: do you want that in any case there is no collision - or, at least, that the probability is so low that it is close to the chance that the Moon collides with Earth within the next 5 minutes?

If yes, choose the SHA family.
In your case I would change the way the update check is being done.
For instance, an incremental number could be associated with the blob, and be sent instead of the hash, the request for update would be required if the number is different on the other side. The collision probability in this case goes from ~10^-18 to ~0 (basically 0 + bug probability )...

Edit following comments

Found this algorithm, Adler-32, which is good for long messages (MB) with a CRC of 32 bits, i.e. about ~1/10^9 (MD5 is 128 bits long).
It is fast to calculate.
Adler-32. There is some come sample (link) at the bottom.

1
votes

Blake2 is the fastest hash function you can use and that is mainly adopted:

BLAKE2 is not only faster than the other good hash functions, it is even faster than MD5 or SHA-1 Source

Winner of SHA-3 contest was Keccak algorithm but is not yet has a popular implementation is not adopted by default in GNU/Linux distributions. Instead, Blake2 that was a SHA-3 contest candidate is faster than Keccak and is part of GNU coreutils. So on you GNU/Linux distribution you can use b2sum to use Blake2 hash algorithm.