Introduction
The purpose of this note is to show how easy it is to modify the message underneath a stream cipher - even if it is 'protected' by a CRC. The message is simply modified by xoring the ciphertext with the required modification. (Analogous attacks work for different combining functions such as addition or subtraction) The assumption is made that the relevant contents of the message are known but that for nefarious reasons the attacker wants to change this seemingly secure communication.
original process:
Encrypt Decrypt
C = R xor P P = R xor C
modified process: calculate:
M = P xor P'
where P' is the required plaintext and modify the encrypted message:
Encrypt Modify Decrypt
C = R xor P C' = C xor M P' = R xor C'
(NB: R xor C' = R xor C xor M = P xor M, which is P')
It should be noted that nothing has been said about the nature of the random stream used by the cipher - it could be a PseudoRandom Generator or a even a One-Time Pad.
CRC Properties
The CRC is a 'linear' function, in that it satisfies properties such as:
for all x, y: CRC(x xor y) = CRC(x) xor CRC(y)
If you equate xor with addition and a CRC to division by its polynomial, then this is analagous to saying:
(x + y)/z = x/z + y/z
where z is a number comparable to the CRC's polynomial.
In particular:
if CRC(x) = 0 then for all y: CRC(x xor y) = CRC(y)
Method
Imagine a message of the following form:
PPPP PPPP PPPP PPPP PPPP PPPP KKKK
Where each 'P' represents a byte of plaintext and each 'K' a byte of the CRC.
This is then encrypted, by xoring with a key stream, to produce the ciphertext:
CCCC CCCC CCCC CCCC CCCC CCCC CCCC
Let's imagine that you want to change the second block of ciphertext in order to change the second block of plaintext in the decoded message. This is done with a simple xor:
CCCC ZZZZ CCCC CCCC CCCC CCCC CCCC
However the CRC will come out wrong. Specifically, the change in the CRC is the xor of the original CRC with the CRC of a message:
0000 MMMM 0000 0000 0000 0000
where MMMM is the xor of the original and the new ciphertext (CCCC xor ZZZZ).
The difficulty is that as we do not know what the value of the CRC is, we cannot compute the change to it. However, we can tell when there is no change to the CRC.
If you can construct a message:
0000 MMMM 0000 QQQQ 0000 0000
which has a CRC = 0000, this can be used to change the message under the cipher without any change in the CRC.
This is nice in that you don't need to know all of the original message in order to be able to construct the message that represents the required change. It is useful, however, to have some knowledge of the message structure. For example in a payment system you might know that a message has the form:
Payer Account Name
Payer Account Number
Payee Account Name
Payee Account Number
Currency Type
Currency Value
Date
Time
CRC
You know the payee name and account number but don't know the payer. You can change the payee account number to match your own and corrupt the payer name to preserve the CRC. The payer account number should not change (otherwise the transfer might bounce) and the audit trail may look strange, but the net result is an otherwise plausible transfer request.
One other observation is that even if your required change is very long, the additional change needed to preserve the CRC needs never be longer than the CRC.
You might even choose to change the CRC itself rather than some other part of the message. However, the method outlined will still work even if a different cipher is used for the CRC
A good exposition of CRCs and the various ways of programming them is given at The CRC Pitstop on Ross Williams' website. These are valuable techniques in the context of overcoming noisy channels. However, where authentication is concerned, cryptographic hash functions such as SHA-1 are essential - combined with the use of a secret key or the Digital Signature Algorithm.
© November 2000, Keith Lockstone, Mark Lomas
Comments welcome: Keith