Re: CRC as authentication?

Paul Rubin wrote:
I'm wondering why we can't use encrypted CRC's as authentication,
instead of the more expensive universal hashes that require field
multiplication.

You can. If the polynomial is secret, and if you use the CRC correctly,
conditions on how you use it, then the resulting hash is an AXU-2 hash.
This was analyzed by Hugo Krawczyk in his CRYPTO 1994 paper. Sadly,
I believe the resulting construction is patented.

(An example of how to use it correctly: for a 128-bit CRC, append 128
zero bits to the end of the message to ensure the CRC register contents
are fully scrambled.)

I don't believe the result is as fast as the state-of-the-art universal
hash schemes, but it's probably pretty good, given how simple it is.

The CRC 'hash' is not universal, because among other things we know
that if M1 and M2 differ in exactly one bit, the CRC's differ.

Well, it's \epsilon-AXU2 ("almost xor-universal"), because if the polynomial
is secret (and if the CRC is used correctly), then the resulting difference
in the two CRCs cannot be predicted.
.

Relevant Pages

  • Re: 16 bit crc reverse engineering, problem
    ... problem is we dont have the documents for this ecu. ... but they dont specify what crc they are. ... then two messages of the same length that differ in only one bit location will differ in their CRCs in exactly the same way. ...
    (sci.crypt)
  • Re: Removing duplicate files
    ... Files are compared using the checksum value. ... If CRC are equal, ... files could differ but have the same check-sum. ...
    (microsoft.public.windowsxp.general)