16
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – user9070
    Commented Mar 27, 2016 at 8:51
  • 1
    $\begingroup$ This is not about cryptography, nobody would say CRC is a cryptographic hash. $\endgroup$
    – fkraiem
    Commented Mar 27, 2016 at 9:32
  • 2
    $\begingroup$ I have a longer explanation posted previously: stackoverflow.com/a/7005801/839689 $\endgroup$
    – Nayuki
    Commented Mar 27, 2016 at 16:26

2 Answers 2

21
$\begingroup$

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.

$\endgroup$
2
  • 6
    $\begingroup$ 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. $\endgroup$
    – Reid
    Commented Mar 27, 2016 at 15:16
  • $\begingroup$ 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.. $\endgroup$
    – fgrieu
    Commented Apr 5, 2016 at 16:36
3
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ You state exactly the same identity for CRC that I give in the question, and in practice I found that it did not hold. $\endgroup$
    – user9070
    Commented Mar 28, 2016 at 11:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.