Take the 2-minute tour ×
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.

There are 100 bytes with a CRC16. However I only know the first 50.

I want to change byte 5 from a known value X to another value Y, and fix up the CRC16 to be valid - without knowing bytes 50-100.

This is possible with the TCP checksum, because it's just addition. But CRC16 is a polynomial. Is it still possible?

share|improve this question

migrated from security.stackexchange.com Jun 2 '13 at 19:20

This question came from our site for Information security professionals.

2  
Welcome to Information Security! Your question is regarding cryptography theory, and as such probably a better fit on Cryptography, where I expect it migrated shortly. Nothing to worry about though, just thought to let you know this might happen, so there's no need to cross-post your question, but you might want to register with that Stack Exchange daughter website as well to be able to comment on possible answers. Cheers! ;) –  TildalWave Jun 1 '13 at 17:20
2  
If you can control at least 2 of the first 50 bytes you can fix the CRC. –  CodesInChaos Jun 1 '13 at 21:57
    
@CodesInChaos You mean via brute force, or can I solve it as an equation? –  John Jun 2 '13 at 17:57
    
If you XOR two 100 byte strings with valid CRCs then the result has a valid CRC (possibly with a tweak if the CRC is inverted). You can calculate the values using Gaussian Elimination mod 2 without having to understand any extra maths. This works because addition mod 2 has essentially the same features as normal addition. But as @CodesInChaos says, you need to be allowed to change at least 16 bits of the rest of the 100 bytes to some arbitrary values to "fix up" the CRC. –  Barack Obama Jun 2 '13 at 20:11
    
If you post 100 bytes and identify which ones you want changed to what and which ones you don't care about I'll do a demo! –  Barack Obama Jun 2 '13 at 20:16

1 Answer 1

Yes, it is very possible. And quite efficient, too.

$\DeclareMathOperator{\crc}{crc}$CRC is linear, meaning $\crc(x \oplus y) = \crc(x) \oplus \crc(y)$. This property is fantastic for an attacker.

Let your 100-byte message be called $m$. Now suppose you wish to change the value of the byte $a$ to $a'$. Compute $d = a \oplus a'$. Now, pad $d$ with zeroed bytes so that it is in the appropriate place: say your $a$ was byte position 5, so you would put four "zero" bytes in front of it and 95 after it. Let that padded message be called $p$.

Now compute $\crc(p) \oplus \crc(m)$ and you have the CRC check value associated with the altered data, even though you don't have the full original message. Why does this work? Because anything XOR'd with 0 is itself:

$$x \oplus 0 = x$$

So for the 5th byte, we would be XORing our computed value $d$ with it. But for the rest of the bytes, we would be XORing them with 0, leaving them alone. Why do we select $d = a \oplus a'$? Because $a \oplus a = 0$, so

$$a \oplus d = a \oplus a \oplus a' = a'.$$

In other words, by selecting the $d$ we do, we can change $a$ to any arbitrary $a'$. The fact that CRC is linear is key here, because what we are actually computing is $\crc(p) \oplus \crc(m)$, which (by linearity) is the same as $\crc(p \oplus m)$.

Here is a demo in Python, using this library to compute CRC16. In it, I use a string of 100 ASCII '0's and change the 5th one to a '1', forging the CRC value.

>>> import crc16pure as crc
>>> data = '0' * 100 # our real data
>>> known_crc = crc.crc16xmodem(data) # crc(m), this is from the 'DB' (known)
>>> ord('0') ^ ord('1') # calculate d
1
>>> newdata = '\x00'*4 + chr(1) + '\x00'*95 # calculate p
>>> new_crc = crc.crc16xmodem(newdata) # crc(p)
>>> forged = new_crc ^ known_crc # crc(m) xor crc(p)
>>> print forged
36103
>>> crc.crc16xmodem('0' * 4 + '1' + '0' * 95)
36103

Note that in my calculation, I never had to reference 'data' (above, our $m$). I only had to know its CRC value.

Of course, this attack works for any number of known bytes.

share|improve this answer
1  
Many CRCs in actual use do not have the property that $\crc(x⊕y)=\crc(x)⊕\crc(y)$. Instead that have the weaker property that for any three messages $x$, $y$, $z$ of equal length, $\crc(x⊕y⊕z)=\crc(x)⊕\crc(y)⊕\crc(z)$. Look at section 2.2.7.4 of X.25, and consider the effect of the prescribed initialization value, and final complementation. Still the attack remains possible. –  fgrieu Jun 3 '13 at 16:33
    
@fgrieu: Interesting! I wasn't aware of that. Fortunately, as you said, it doesn't seem to affect the basic gist of the above. –  Reid Jun 3 '13 at 17:19

Your Answer

 
discard

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