Re: CRC as authentication?
 From: daw@xxxxxxxxxxxxxxxxxxxxxxxx (David Wagner)
 Date: Mon, 11 Sep 2006 08:56:43 +0000 (UTC)
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 AXU2 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 128bit 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 stateoftheart 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 \epsilonAXU2 ("almost xoruniversal"), because if the polynomial
is secret (and if the CRC is used correctly), then the resulting difference
in the two CRCs cannot be predicted.
.
 FollowUps:
 Re: CRC as authentication?
 From: Rob Warnock
 Re: CRC as authentication?
 References:
 CRC as authentication?
 From: Paul Rubin
 CRC as authentication?
 Prev by Date: Re: CRC as authentication?
 Next by Date: Re: CRC as authentication?
 Previous by thread: Re: CRC as authentication?
 Next by thread: Re: CRC as authentication?
 Index(es):
Relevant Pages
