14
$\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?

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

Improve this answer
$\endgroup$
  • 2
    $\begingroup$ CBC should be CRC, I think $\endgroup$ – TonyK Mar 27 '16 at 14:28
  • 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 Mar 27 '16 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♦ Apr 5 '16 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.

Improve this answer
$\endgroup$
  • 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 Mar 28 '16 at 11:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy