So, to encode a two-byte message 0x0102, Bob would interpret it as the polynomial m(x) = x8 + x, divide it by x2 + x + 1 using polynomial division, and get a remainder polynomial r(x) = 1. In hexadecimal notation, the remainder has the value 0x01. He would then append the remainder value as the CRC check value and transmit the message 0x010201 to Alice.
Upon receiving the message, Alice would perform the same computation and check whether the received CRC value 0x01 is equal to the computed CRC value. Let’s assume there was an error during transmission – an accidental bit flip – so that Alice received the message 0x010101. In that case, the CRC value computed by Alice would be 0x02 and Alice would detect the transmission error.
At first glance, this looks very similar to a MAC and, especially in systems that already support CRCs, it might be tempting to use CRC as a replacement for a MAC. Don’t! Recall that MACs are built on top of cryptographic hash functions, and cryptographic hash functions are collision-resistant. CRCs, on the other hand, are not collision resistant.
As an example, Listing 11.1 shows the Python code for computing CRC-8. This CRC uses generator polynomial x2 + x + 1 and outputs an 8-bit CRC value.
Listing 11.1: Python code for computing CRC-8 using generator polynomial x2+x+1
def crc8(data, n, poly, crc=0):
g = 1 << n | poly # Generator polynomial
for d in data:
crc ^= d << (n – 8)
for _ in range(8):
crc <<= 1
if crc & (1 << n):
crc ^= g
return crc
Now, if you compute CRC-8 checksum values for different 2-byte messages using the code shown in Listing 11.2, you can quickly verify yourself that messages 0x020B, 0x030C, 0x0419, and many others have the same CRC value of 0x1B.
Listing 11.2: Python code to compute CRC-8 for different 2-byte messages
for i in range(0,256):
for j in range(0, 256):
if crc8([i,j], 8, 0x07) == 0x1b:
print(f”Message {hex(i)}, {hex(j)} has CRC 0x1b”)
Consequently, if Alice and Bob were to use CRCs to protect their message integrity against malicious attacker Mallory rather than accidental transmission errors, it would be very easy for Mallory to find messages that have an identical CRC check value. That, in turn, would allow Mallory to exchange a message that Bob sent to Alice without her noticing it (and vice versa). And that is exactly the reason why a MAC needs to be collision-resistant. Moreover, and maybe even more importantly, even if Mallory cannot be bothered to find collisions for the CRC value already in place, he can simply compute the matching CRC value for a message of his choice and replace both the message and the CRC. This is possible because there is no secret information going into the CRC. To summarize, a CRC will only protect you against accidental, random transmission errors, but not against an intelligent attacker.
Leave a Reply