[prev in list] [next in list] [prev in thread] [next in thread] 

List:       cryptography
Subject:    Re: [Cryptography] reality +- mathematical guarantees
From:       Jerry Leichter <leichter () lrw ! com>
Date:       2015-06-09 20:48:16
Message-ID: CF6E16C6-659C-4F55-A349-AEE8501E49AB () lrw ! com
[Download RAW message or body]

On Jun 8, 2015, at 8:07 PM, John Denker <jsd@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

_______________________________________________
The cryptography mailing list
cryptography@metzdowd.com
http://www.metzdowd.com/mailman/listinfo/cryptography


[prev in list] [next in list] [prev in thread] [next in thread]