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

Back to home page