RE: Proof that CRCs are not secure

[vince_cavanna@agilent.com]

Hi David,
In fact it is VERY EASY to figure out what to change to make the CRC come
out hte same. See for example, at http://surf.to/anarchriz , the technique
used by hackers to "reverse" the CRC. Follow the links to "CRC Essay". In
essence, for data protected by a 32 bit CRC, if you want to make an
arbitrary change in the data you can always compensate by changing an
additional 32 bits so the CRC will be consistent. The paper explains, in a
long-winded way, how to compute the compensatory 32 bits. Basically you need
to compute the 32 input bits that will take the CRC circuit (a 32 bit state
machine) from one arbitrary (what it is after the changes) present state to
the desired (what it would have been without the changes) next state. The
CRC is far from being a one-way hash function since it is very easy to find
an alternate message that results in the same CRC as the original message.
Vince

|-----Original Message-----
|From: Black_David@emc.com [mailto:Black_David@emc.com]
|Sent: Monday, April 23, 2001 8:52 AM
|To: ips@ece.cmu.edu
|Subject: Proof that CRCs are not secure
|
|
|A while back, there was some interest in using a CRC
|as a secure integrity checksum (e.g., by adding it
|to IPSec).  This was rejected on principle as being
|insecure.  I recently stumbled across a practical
|demonstration of this insecurity.
|
|The WEP protocol for 802.11b wireless security made
|the mistake of using a CRC as their integrity checksum,
|and as a result can be attacked by tampering with
|data in flight - the fact that the data was tampered
|with is undetectable even when everything is encrypted
|because it's too easy to figure out which bits have
|to be flipped in the CRC to hide the tampering.  This
|is described in the fourth paragraph of the "Problems"
|section at:
|
|http://www.isaac.cs.berkeley.edu/isaac/wep-faq.html
|
|<SECURITY-EXPERT-COMMENT>
|Lest I get jumped on by the security experts, a
|contributing factor to this WEP vulnerability is
|the use of a stream cipher (RC4) rather than a
|block cipher (e.g., DES, AES) - i.e., this simple
|bit-flipping attack won't work against a good block
|cipher, but such an approach requires confidentiality
|(i.e., encryption) to obtain cryptographic integrity.
|The usual design approach is to use something like
|a keyed HMAC (cf. RFC 2104) to support cryptographic
|integrity without requiring confidentiality.
|</SECURITY-EXPERT-COMMENT>
|
|This doesn't change anything the WG is currently doing -
|there is no active proposal to use a CRC for cryptographic
|integrity, and this does not affect the use of CRCs
|in header digests, data digests, and the like.  This
|is just an FYI based on past discussion of this topic.
|
|Thanks,
|--David
|
|---------------------------------------------------
|David L. Black, Senior Technologist
|EMC Corporation, 42 South St., Hopkinton, MA  01748
|+1 (508) 435-1000 x75140     FAX: +1 (508) 497-8500
|black_david@emc.com       Mobile: +1 (978) 394-7754
|---------------------------------------------------
|