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