[Cryptography] reality +- mathematical guarantees

[Jerry Leichter]

On Jun 8, 2015, at 8:07 PM, John Denker <jsd at av8n.com> wrote:
>> Of course you do have a stochastic guarantee, with md5sum, but no
>> hard one like you do with CRC32.
> In the real world, there are no "hard" guarantees, not
> for any form of error correction ... nor for anything else.
> Specifically:  There are lots of ways in which a channel 
> can fail that will not reliably be detected using CRC32.
I think you're missing his point.  CRC32 - or any CRC-like (remainder mod a suitable polynomial in a suitable ring) provides certain specific hard guarantees.  For example, any single-bit change in the input will definitely change the checksum; any change of two bits where the two bits are not more than n apart (n the degree of the polynomial) will definitely change the output; and I forget what else.

These are deterministic guarantees.  There are also probabilistic guarantees:  Any random change (where the random choice is from a distribution independent of the polynomial) has only a 1 in 2^n chance of leaving the checksum unchanged.  (This is usually looked at the other way around:  If you change any number of bits of an input string, a randomly chosen (uniformly from a suitable set) polynomial will have a 1 in 2^n chance of producing a different output for the changed input.  See http://www.xmailserver.org/rabin.pdf .)

CRC's are, of course, not cryptographically secure.  On the other hand, the cryptographically secure checksums provide *only* probabilistic guarantees - it's *possible* that two strings differing in only a single bit will have the same checksum; it's just immensely unlikely.  (Actually, to the degree that a cryptographically secure checksum looks like a random function, it *must* be the case that there are pairs of strings differing in only one bit that produce the same checksum, since that would be true for an actual random function!  *Finding* such a pair is a whole other story, of course.)

CRC's are not the only kind of non-cryptographic checksums out there.  But all of them - and their more powerful cousins, error-correcting codes, *all* provide hard, deterministic guarantees against failure due to some well-defined class of errors, and probabilistic guarantees against errors outside the class.

There is almost no overlap in reasonable use cases for CRC-like and cryptographically-secure checksums.  CRC-like checksums are good against  changes randomly chosen from distributions of changes that are strongly biased toward those that CRC will definitely catch.  For example, CRC's are a good choice for protection against burst noise, where bit errors are highly likely to be close together.  Except in the rather specialized approach Rabin's paper suggests, they are not useful against non-random changes.  Cryptographically secure checksums, on the other hand, are appropriate against non-random deliberate attacks.

The birthday paradox is irrelevant for most uses of CRC-like checksums, but highly relevant against most uses of cryptographically secure checksums.  As a result, effective CRC-like checksums can be much smaller than cryptographically secure checksums - as well as being much cheaper to compute.  They are simply different tools appropriate for different jobs.

                                                        -- Jerry