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, P_{1}, P_{2}, ...P_{n}, satisfy a redundancy check to be specified later.

- C
_{0}= E(packet serial number)

C_{i}= E(C_{i−1}xor P_{i}) for i starting at 1

Transmit C_{i}starting from i = 1. - P
_{0}= packet serial number; C_{−1}= 0

C_{i}= E(C_{i−1}xor P_{i}) for i starting at 0

Transmit C_{i}starting from i = 1. - C
_{0}= new random number each packet

C_{i}= E(C_{i−1}xor P_{i}) for i starting at 1

Transmit C_{i}starting from i = 0.

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 2

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 “

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 2^{128} elements will do.
If “•” is the group operator then R_{0} = group identity and for i from 1 to n: R_{i} = R_{i−1} • P_{i}.
The redundancy requirement is that R_{n} = R_{0}.

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 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.

- Encryptor
- Accept Redundant Payload: P
_{1}, P_{2}, ...P_{n}

R_{0}= group identity (e.g. 0)

R_{i}= R_{i−1}• P_{i}for i from 1 to n

Require that R_{n}be group identity

P_{0}= packet serial number; C_{−1}= 0

C_{i}= E(C_{i−1}xor P_{i}) for i from 0 to n

Transmit C_{i}for i from 1 to n.

Increment serial number. - Decryptor
- Receive C'
_{i}for i from 1 to n, (Hopefully C'_{i}= C_{i})

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 2^{J}.

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.

See an attack that takes a modest amount of known plain text but about 2