31
$\begingroup$

Are checksums basically toned-down versions of cryptographic hashes? As in: they are supposed to detect errors that occur naturally/randomly as opposed to being designed to prevent a knowledgeable attacker's meticulous engineering feature?

So, essentially they are non-secure versions of cryptographic hashes, one could say? Thus for the same reason, these checksums are "cheaper" to compute than cryptographic hashes? (e.g. CRC32 vs SHA-256)

Sorry for my poor english and potentially trivial question. I just need to get the concepts straightened out.

|improve this question
$\endgroup$
  • $\begingroup$ Crc is not a "secure cryptographic hash". It has very different properties. Hashes can't be easiky reversed. Crc lets you know what bytes to add in order to produce the desired crc. $\endgroup$ – JDługosz Feb 22 '16 at 4:51
40
$\begingroup$

Are checksums basically toned-down versions of cryptographic hashes? As in: they are supposed to detect errors that occur naturally/randomly as opposed to being designed to prevent a knowledgeable attacker's meticulous engineering feat?

That is one way to look at it. However, hash functions have many purposes. They are also meant to be one-way (an attacker cannot know the preimage without guessing), for which there is no parallel with checksums.

So, essentially they are non-secure versions of cryptographic hashes, one could say? Thus for the same reason, these checksums are "cheaper" to compute than cryptographic hashes? (e.g. CRC32 vs SHA-256)

Due to their different requirements, checksums are not just "worse, but faster hashes". They are meant to prevent particular kinds of errors. Cyclic redundancy check can detect e.g. all 1-2 bit errors in short inputs, as well as some other common classes of errors in typical applications (e.g. bursts errors). This is better than a truncated cryptographic hash of similar length would be able to do.

A cryptographic hash truncated to 32 bits can easily collide with two inputs that differ in only one or two bits, whereas a CRC won't. The CRC is geared towards reliably detecting error patterns that commonly occur in transit, so it will do better on those kinds of errors and worse on others. The short hash does optimally over all inputs, and as a result does worse than CRC on the inputs CRC is good at dealing with.

|improve this answer
$\endgroup$
  • 2
    $\begingroup$ @ArtjomB. A cryptographic hash truncated to 32 bits can easily collide with two inputs that differ in only one or two bits, whereas a CRC won't. The CRC is geared towards reliably detecting error patterns that commonly occur in transit, so it will do better on those kinds of errors and worse on others. The short hash does optimally over all inputs, and as a result does worse than CRC on the inputs CRC is good at dealing with. $\endgroup$ – Thomas Feb 21 '16 at 19:21
  • 3
    $\begingroup$ @ArtjomB. An 8-bit checksum will let you detect any single-bit (or even single-byte) change anywhere in the string; a cryptographic hash truncated to 8 bits would have a 1/256 chance of not detecting a change (or whatever size). Thus, while a crypto is stronger against a malicious opponent, a checksum is better against small random changes (i.e. data transmission errors). Which one you should use depends on what you're trying to protect against. BTW, checksums and CRCs are significantly different things; CRCs protect against several classes of (random) errors that checksums do poorly at. $\endgroup$ – Gordon Davisson Feb 21 '16 at 19:22
  • 3
    $\begingroup$ I see now that you wanted to stress that CRC always detects 1-2 bit errors (depending on the chosen polynomial) and a hash not necessarily. I've just read A Painless Guide to CRC Error Detection Algorithms, which makes this fact clear and the Wikipedia page doesn't for some reason. $\endgroup$ – Artjom B. Feb 21 '16 at 20:24
  • 4
    $\begingroup$ @OlegV.Volkov, with some types of errors you have a 100% chance of detection. To see why you can consider the parity check, which detects all one-bit flips. $\endgroup$ – otus Feb 21 '16 at 21:32
  • 2
    $\begingroup$ @OlegV.Volkov: CRC8 is suitable for short packets, but with an order-128 polynomial it would be inadequate to guard anything over 15 bytes of payload. How big were your packets? $\endgroup$ – supercat Feb 22 '16 at 6:52
9
$\begingroup$

I think it's more helpful to think of checksums as toned-down versions of message authentication codes (not hashes).

Message authentication codes (MACs) are designed to detect any modification to a message, while it is in transit. They are secure against even adversarially-chosen modifications.

Checksums are designed to detect some modifications to a message, while it is in transit. They are designed to detect random modifications: the kinds of modifications that might happen by chance (e.g., due to a burst of noise, or interference, or something), but not adversarial modifications.

As a result, checksums can be faster than MACs. But MACs can be made pretty fast....

|improve this answer
$\endgroup$
  • 6
    $\begingroup$ The key difference between a MAC and a hash is that the MAC is keyed and the hash is not. The CRC is not keyed either, so it seems more appropriate to compare the CRC to a hash. $\endgroup$ – kasperd Feb 22 '16 at 9:42
  • 3
    $\begingroup$ @kasperd, that's a difference, but far from the only relevant difference. For instance, hashes are required to be one-way; a MAC isn't, and a checksum isn't. You could compare the CRC to a hash, but then you'd find that a hash has extra requirements that don't show up for checksums and seem orthogonal, so the comparison gets messy. In contrast, MACs and checksums serve a similar purpose, with the only difference being adversarial vs not, so I personally find it more intuitive to think of checksums as being vaguely analogous to MACs. $\endgroup$ – D.W. Feb 22 '16 at 18:43
4
$\begingroup$

From my point of view, they would be extremely distant relatives. But I understand the point: both generate fixed length values that can help to indicate when integrity was somehow compromised. They should stay as distant tools with different purposes that should not be confused, but there is CRC32 to complicate the difference.

CRC32 is a checksum that derives a 32 bit long digest, that is used, for instance, to check if a compressed file was damaged while being transferred. However, the fact that it generates a 32 bit long digest led to the believe that it can be used as a cryptographic hash for integrity control. In particular, they are used as a hash function in industrial networks, where the hardware capability is usually heavily bounded and real cryptographic hashes can be a heavy choice. That does not mean that they can actually replace a cryptographic hash function to any extent, but it shows that the descriptions of both families of functions are so similar that could be mistaken by an inattentive observer.

|improve this answer
$\endgroup$
0
$\begingroup$

A MAC ensures a receiver that a message is authentically generated by a sender using a shared secret (key). The MAC is a pair of algorithms: generate and verify. Typically, a sender generates a tag to append to a message. This tag is generated by mixing the message, the secret key and a counter and then hashing the result. The receiver can then use the same process to verify that the message is authentic. There are no guarantees made by the MAC other than the fact that there is a low probability of two messages of having the same MAC (1/2^n). Which makes a MAC good for authentication.

According to the study done by Koopman et al.*, the 15 bit CRC in CAN guarantees that all message collisions are at least 6bits in hamming distance away from each other. This means that an error will always be detected in a message frame (82 bits) with 1-5 random bit flips. The same guarantee of error detection does not hold if you try to MAC an 82bit message into a 15bit MAC. This is why CRCs are still used today for error detection.

*Koopman, Philip, and Tridib Chakravarty. "Cyclic redundancy code (CRC) polynomial selection for embedded networks." Dependable Systems and Networks, 2004 International Conference on. IEEE, 2004.

|improve this answer
$\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.