It normally seems poor form to replicate function in communications protocols. Extra bits must generally be moved and more processing and more code is required. I explore here excuses and reasons for doing so in a particular case.

Most computer communications protocols have some degree of error control. The controlled errors include damaged data, and missing and duplicate packets. Crypto protocols also guard against such errors, generally concentrating on protecting against errors that are deliberately introduced to confuse and delude. It seems natural to seek a protocol to combat both natural and mischievous errors; to guard against both innocent and malevolent demons. I suggest here that that is usually a bad idea.

Symmetric crypto may easily be adapted to provide efficient strong authentication. If we use the simplest checksum (circa 1950) on the plain text and append to the plaintext, the XOR of that sum and a packet serial number, then a cipher block mode such as CBC will garble some packet upon innocent or malevolent changes to the ciphertext. The CBC crypto layer has transformed a naïvely simple checksum into strong authentication!

This idea seems to have surfaced in CBCC mode by Xerox.

How many bits should we use in the checksum? As far as I can see a 32 bit checksum means that the saboteur has one chance in 232 of causing a problem. The other 232−1 tries will result in an unmistakable error alarm. But this depends partly on answering the original point of this note: Do we need conventional error control in addition to strong authentication?

If this protocol is supported by an additional conventional error control service, then the first violation of the naïve checksum may be taken as strong evidence of a flaw in the underlying error control logic, or evidence for malicious tampering with the cipher stream.

If the naïve checksum of the plaintext serves as error control for the transmission medium, we must expect the opponent to try to simulate innocent channel transmission errors and thus get many chances to cause mischief. Reasoning about this situation requires attention to the possibility of corruption on the reverse channel. This worries me. This is why I advocate an underlying conventional error control service.

Regarding the size of the checksum: It seems to me that a 64 bit checksum is inexpensive for most applications. A 32 bit sum might be justified with careful attention to the above risks. Consider the possibility of the opponent reinserting an encrypted packet after the 32 bit counter has wrapped.

There are a few variations that I will mention that all seem equivalent regarding security. There is no reason to put the checksum at the beginning. There is no gain except packet size to XORing the sum with the serial number. Adding the sum to the serial number is as good. I would prefer an “add” instruction to an “xor” for the checksum for there is probably little or no cost and superstition regarding possible attacks. Perhaps carrying the IV from one packet to the next is as good as a serial number. Each session would begin with a new IV.

A Pitfall we have avoided

I have learned a great deal since I began this note. Most of this was the result of web surfing and finding reported problems and weaknesses. I had not noticed that the self synchronizing property that cipher block mode protocols (CBC, CFB, etc.) usually aspire to, defeat the more obvious authentication schemes that I had advocated, such as merely appending a serial number to the end of each packet. Resynchronization means that the serial number may come thru unscathed even while the middle of the packet is entirely garbled. PCBC tried to solve this but it was observed later that permuted blocks of ciphertext are undetected.

Attacks

It would seem that Mallet (the attacker) must manipulate the ciphertext so as to cause the correct checksum and serial number, or at least to cause their XOR to be as expected. Permuting encrypted blocks certainly does not do this in CBC mode. This scheme is certainly not vulnerable to permuted cipher blocks. While the naïve checksum is vulnerable to permuted words and certainly permuted plaintext blocks, the nature of CBC cause the encryption of plaintext to be highly sensitive to its location within the packet. In particular it is sensitive to what has come before. This is an argument for chaining IV between packets.

The idea behind this scheme is that any corruption of the ciphertext must change some first encrypted block. This will produce a change in the corresponding plaintext. Even if Mallet has achieved chosen plaintext he will not know the result of the effect on the resulting plaintext.

Assume chosen plaintext but a concealed IV. Mallet will be able to build a list of pairs <x, Ek(x)>. Out of ignorance of k, however, he will be unable to choose the values of x. With a 64 bit cipher block and after nearly 232 blocks have past, it will become likely that he gets the opportunity to match a previously observed value with a new value and then produce a known corrupted plaintext value. He will know this possible corrupted value before he commits to doing the cipher block substitution. Rijndael, on the other hand is a 128 bit block cipher! Limiting a session to substantially less than 264 blocks is not burdensome.

Here I explore attacks on CBCC.

Background Assumptions

Each session generates a shared secret key between the two end points.
Either the secret key or the IV should different for each session.
For each direction in each session, a sequence of packets is sent.
Each packet is a sequence of blocks.
There is no recovery within a session to a discrepancy of the naïve checksum error.
The recipient never acts on packet values until the entire packet has been authenticated by the simple checksum.
The entire packet payload must be delivered to the CBCC encryption module before any ciphertext is revealed.

Pointers from Zooko:
Public Workshop on Symmetric Key Block Cipher; Modes of Operation This page has pointers to papers from the workshop! Live 2014 October.

The introduction to ISO9797 claims to provide a clear definition how to build a MAC on top of a block cipher.