CRC32 vs. low 32 bits of cryptographic hash

Question

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?

Answer 1

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).

Answer 2

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.