Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

It is commonly understood that CRC satisfies the linear identity with respect to the $\oplus$ (XOR) operation:

$\operatorname{CRC}(a) \oplus \operatorname{CRC}(b) = \operatorname{CRC}(a \oplus b)$

But after some experimentation and research it appears that this is not generally true.

The particular algorithm in question is the one used in HDLC, ANSI X3.66, ITU-T V.42, Ethernet, Serial ATA, MPEG-2, PKZIP, Gzip, Bzip2, PNG (see Wikipedia) which uses the polynomial $\mathtt{0x04C11DB7}$.

In what sense is CRC linear? Is this a misconception?

share|improve this question
    
I'm not asking for a proof, like the linked StackOverflow question. I'm asking if this is a misconception, because it does not appear to be true in practice. – TruthSerum Mar 27 at 8:51
1  
This is not about cryptography, nobody would say CRC is a cryptographic hash. – fkraiem Mar 27 at 9:32
1  
I have a longer explanation posted previously: stackoverflow.com/a/7005801/839689 – Nayuki Mar 27 at 16:26
up vote 18 down vote accepted

In practice, CRC operations are often started with a nonzero state. Because of this, the actual equation is usually of the form:

$$crc(a) \oplus crc(b) = crc( a \oplus b ) \oplus c$$

for some constant $c$ (which depends on the length of $a$, $b$).

An alternative way of expressing this is, for three any equal-length bitstrings $a, b, c$, we have:

$$crc(a) \oplus crc(b) \oplus crc(c) = crc( a \oplus b \oplus c ) $$

The technical term for this relationship is affine; in cryptography, we treat it as linear because, for attacks that assume linearity, affine works just as well.

share|improve this answer
2  
CBC should be CRC, I think – TonyK Mar 27 at 14:28
5  
Setting $c=0$ in the alternate equation might be a useful exercise: $crc(a) \oplus crc(b) \oplus crc(0) = crc(a \oplus b)$. Then, one naturally questions what $crc(0)$ evaluates to, tying into your point about starting at a nonzero state. – Reid Mar 27 at 15:16
    
Thanks, this is just what I was looking and hoping for. – TruthSerum Mar 27 at 19:03
    
Ah, that corrects a long-standing terminology problem I have had, with (wrongly) using linear where affine was meant in a cryptanalytic context! I'll have to scrub my earlier answers.. – fgrieu Apr 5 at 16:36

My answer to how to recalculate a CRC32 on a large byte array

and the comment which follows may explain it.

The linearity comes from the fact that CRC is a remainder of dividing a high degree polynomial with binary coefficients (=data) by a fixed degree polynomial with binary coefficients (=crc polynomial).

Adding of polynomials with binary coefficients is equivalent to an xor operation (and it is obviously linear). So if the data changes, and you know the xor between the old data and the new data, you can calculate CRC of the new data from the CRC of the old data and vice versa.

From security perspective, this makes CRC unreliable way to tell if the data has changed if the data has a padding or even some useless bits in the middle. Those can be easily adjusted to produce the correct "remainder" polynomial by calculating the CRC of each free-to-be-adjusted bit and then solving the system of simultaneous linear equations (to produce intentional collision of CRCs).

Which makes producing CRC collision a trivial problem. This makes CRC unsuitable to detect malicious changes.

share|improve this answer
    
You state exactly the same identity for CRC that I give in the question, and in practice I found that it did not hold. – TruthSerum Mar 28 at 11:06

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.