Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I was having a discussion with a colleague yesterday whose education and experience exceeded mine. He said something yesterday that sounded incorrect to me intuitively, but I don't have the knowledge to contradict it.

He claimed that the only reason a secure cryptographic hash is better at detecting tampering or corruption is because it has more bits in the output (e.g. SHA-256 has a 256-bit output vs. CRC32's 32-bit output). Right now, we're only talking about detecting corruption/tampering, not recovering data.

My intuition tells me that given the choice of CRC32 or SHA256 (and taking only the low 32 bits), the hash is going to be much more secure as far as detecting changed bits (particularly in the face of a malicious and intelligent attacker, but even due to corruption in "just the wrong way").

Can someone either tell me why I'm wrong & the 2 are essentially equivalent, or support my intuition with math and or proof/reasoning?

share|improve this question

2 Answers 2

up vote 4 down vote accepted

If we're talking about a malicious and intelligent attacker, you are mostly wrong, but not for the reasons you might expect.

If we assume an intelligent attacker, then a CRC does not help; they can obviously modify a file, and either figure out how to update the CRC32, or how to make sure that the modifications do not change the CRC.

On the other hand, if we use a SHA256 hash, that's not much better; if they can modify the hash as well, then they can compute the SHA256 on the new file, and replace that hash with that. If they cannot modify the hash of the file, then if we truncate the hash to 32 bits, then they can try to modify the file $2^{32}$ different ways, and compute the hash on each; it's likely that they'll find a modification that leaves the hash unchanged. This is obviously more work for the attacker; however it might be a weekend project for a single PC.

So, the bottom line is that there isn't a great deal of difference between a CRC and 32 bits of SHA256 in this scenario.

And, if we start looking at random changes, the CRC might actually be stronger in that case; if a random change is isolated to be entirely within a block of 32 bits, then a CRC will always detect the change (because the CRC will always change); the SHA256 will detect it with probability $1 - 2^{-32}$.

The first answer we have for strong integrity checking is to use a Message Authentication Code; this assumes that the entity generating the MAC and the entity checking for corruption share a secret key (that no one else has); this key is stirred into the generated checksum, and someone who doesn't know the secret key cannot modify the message and the checksum (with any probability better than random guessing).

share|improve this answer
    
thanks very much for the informative & well-reasoned answer. One question: when you say the SHA256 will detect it with probability 2^−32, I assume this is intended to say with probability 1-2^-32, correct? Even though a difference of 1-part--in-4 billion seems small to a layperson, we all know to an attacker, that's interesting... –  Dan Oct 31 at 19:59
    
@Dan: yes, you are correct; I've corrected my answer –  poncho Oct 31 at 20:33

A CRC or some other similar scheme is superior as they can be engineered such that single character changes or transpositions can be detected. A Bitcoin address uses a truncated hash function as a "checksum" but it is easily possible to have two valid addresses differing by one character

1ByteCoinAddressesMatch1kpCWNXmHKW 
1ByteCoinAddressesMatch1kpCxNXmHKW

or by a transposition

1ByteCoinAddressesMatchcNN781jjwLY 
1ByteCoinAddressesMatchcNN718jjwLY

I believe these scenarios would be impossible with even a common 16-bit CRC.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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