While seeking attacks on my variation on CBCC in the last few weeks, I have learned a great deal about authentication of CBC packets. I record here much or most of what I have learned because it is enough to easily forget and the source material is hard to find and read. Others may find it useful.

First an important misconception that some may hold as I did. CBC encryption of a packet smears plaintext differences thruout the current and subsequent cipher blocks. By contrast, CBC decryption of ciphertext with a one bit error in the ciphertext shows up only thruout the current block and that bit in the next block. This is indeed what it means to be self synchronizing. An immediate consequence of this is that cutting and pasting ciphertext from different packets but with the same key, will result largely in the corresponding plaintext upon decryption. There will be one garbled block at the splice of the plaintext. The inventors of CBCC presumed that this garble will cause a failure in the simple redundancy check.

First I collect a few schemes. They have in common some sort of simple cheap redundancy added to the plaintext check before the encryption and checked after the decryption.

In each of the following it is required that the payload, P1, P2, ...Pn, satisfy a redundancy check to be specified later.

  1. C0 = E(packet serial number)
    Ci = E(Ci−1 xor Pi) for i starting at 1
    Transmit Ci starting from i = 1.
  2. P0 = packet serial number; C−1 = 0
    Ci = E(Ci−1 xor Pi) for i starting at 0
    Transmit Ci starting from i = 1.
  3. C0 = new random number each packet
    Ci = E(Ci−1 xor Pi) for i starting at 1
    Transmit Ci starting from i = 0.
Decryption is clear in each case but a new rule is that the decrypted text is not revealed, even to the legitimate recipient, if the redundancy check fails.

Schemes 1 and 2 are identical but these expressions fit into different patterns. Scheme 3 Characterizes the Kerberos V5 message packet where the random number is called the “confounder”.

The Kerberos redundancy check used a 32 bit CRC. See:

S. Stubblebine and V. Gligor, On Message Integrity in Cryptographic Protocols, IEEE Computer Society Symposium on Research in Security and Privacy, Oakland, CA, May, 1992, pp. 85-104. (Electronic version not available :(
That attack manages, with about 5500 chosen plaintext packets, to produce a bogus ciphertext which decrypts to plaintext where most of the payload is controlled by the attacker. The attack requires chosen plaintext of about 2n/2 blocks where n is the number of redundant bits.
The above paper lays out details of an attack on a Kerberos V5 encrypted message. I was hung up for a while on the purpose of the “comp_data”. Here is the deal. Due to the attacker not knowing what the nonce or confounder value will be after he submits packet i for encryption, he cannot know what the partial CRC calculation state for his decrypted packet fragment will be. He must know, and better, control this, to achieve smooth splicing. He can compute comp_data so that the lower layer will compute a CRC that feeds into the CRC calculation that communications layer will do on his data before it encrypts it. The lower layer thinks the entire submitted packed will be checked by the receiver but comp_data has been selected to make the CRC for the subpacket and whole packet the same. The prefix of the ciphered packet will thus have a known effect on the CRC calculation as the eventual bogus packet is decrypted.

Nature of Redundancy Check

The paper shows why the complexity of CRC presents little computational cost to the attacker. A simple checksum of as many bits should do as well. There is nothing in the paper to indicate that increasing the redundant bit count to n costs the attacker less than submitting 2n/2 blocks of chosen ciphertext.

Given that ciphertext errors do not propagate to the end of decrypted plaintext, the redundancy check must cover all of the plaintext, as does a simple checksum.

I advocate either a simple arithmetic add or boolean xor of 128 bits, probably in agreement with the width of the block cipher. The redundancy requirement is that the sum of the plaintext be 0. I think that the only properties of this redundancy that we require stem from being an abelian group. Indeed any simply computed abelian group with 2128 elements will do. If “•” is the group operator then R0 = group identity and for i from 1 to n: Ri = Ri−1 • Pi. The redundancy requirement is that Rn = R0.

I have chosen to describe the redundancy check without saying which part of the plaintext serves as “the check”. The code that performs this check after the decryption does not depend on this. There are even situations where the payload provider can ensure redundancy without extra space.

The Context of the Crypto

The purposes that I have in mind require strong control over packet serial numbers. I assume a crypto environment where it is as hard to defeat the serial number counter on either end, as it is to steal the key. I think that either of the equivalent schemes 1 or 2 above, combined with the abelian redundancy provides this protection. I can imagine other environments where this may not be the case. Some additional attacks assuming oracles without counters, may be possible where one can reset the counter without changing or discovering the key. If the decryptor or encryptor, with its state, can be duplicated there may be a problem.

In Summary

Encryptor
Accept Redundant Payload: P1, P2, ...Pn
R0 = group identity (e.g. 0)
Ri = Ri−1 • Pi for i from 1 to n
Require that Rn be group identity
P0 = packet serial number; C−1 = 0
Ci = E(Ci−1 xor Pi) for i from 0 to n
Transmit Ci for i from 1 to n.
Increment serial number.
Decryptor
Receive C'i for i from 1 to n, (Hopefully C'i = Ci)
C'0 = E(packet serial number)
P'i = C'i−1 xor E−1(C'i) for i from 1 to n
Compute R' from P' just as R was computed from P.
Require that R'n be group identity and that R'i not be the identity unless i = 0 or i = n.
Deliver Redundant Payload: P'1, P'2, ...P'n
Increment serial number.
Notation
In the above E(x) denotes the J bit output of the block encryption of the J bit value: x.
“•” denotes the operator of an abelian group of size 2J.
The payload is a sequence of (J bit values).
Claim
If the keys for the block cipher, E, are known only to the encryptor and the decryptor, then (1) any packets delivered by the decryptor will be identical to those accepted by the encrytor, and in the same order, and (2) If the encrypted packets received by the decryptor are the same as the packets transmitted by the encryptor, the plain text delivered by the decryptor will be just that accepted by the encryptor.
I need to compare the above with CCM. See this before you use any of these ideas.
See an attack that takes a modest amount of known plain text but about 2J computational steps to corrupt the authentication. For some purposes the cost of “offline cycles” is very much less than invoking an oracle.