I search here for attacks on a combined cipher authentication scheme inspired by rumors of details on the CBCC scheme out of Xerox. I am not aware of any improvements I bring over CBCC but a long checksum. I refer briefly here to CBCC which attempts authentication by stacking a simple plaintext checksum protocol upon CBC mode encryption. The germ of the ideas is that only someone who knows the shared secret key can produce ciphertext that decrypts to plaintext that passes the simple checksum test. I speculate here about a particular attack on the authentication part. As it stands the attack does not succeed but it penetrates further than my earlier analysis allowed for. Also see Steve Bellovin’s paper “Problem Areas for the IP Security Protocols” which addresses these issues. I may revise this page after I have understood his points.

I suppose a great deal of known plaintext. I also suppose a 64 bit block cipher. Mallet’s goal is merely to get some bogus plaintext value thru the authentication mechanism in order to gum up the works and thus deny service.

Known Plaintext Attack

Mallet has collected a partial code book of pairs <x, Ek(x)> for the current key k.

When the size of the book has grown to around 232, Mallet will occasionally recognize an opportunity to substitute a cipher block for another that will decrypt to a corrupted plaintext value that Mallet knows. He can decide, based on this corrupted value and other information in the packet, whether to make the substitution. Mallet knows but can not control this value. If he makes the substitution the modified ciphertext block will produce the predicted plaintext value but the substituted value for the ciphertext block also feeds into the decoding of the following plaintext block in a way that Mallet is extraordinarily unlikely to be able to control. Mallet is in a position to foresee this faux pas and avoid it. This means that Mallet must have in his collection enough values to maintain the ruse until the end of the packet. Seeing as how he is able to corrupt just one packet in 232 this is unlikely.

Perhaps it suits Mallet’s purpose to perform corruption only at the end of packets; the last cipher blocks of a packet. Mallet will know the value of the corrupted plaintext value that he has the opportunity of causing but that value is extraordinarily unlikely (2−64) of satisfying the simple checksum. Even if it did the payload would have been uncorrupted and the IV for the next packet would have been put into a state to cause an alarm when it arrives.

Chosen Plaintext Attack

Analyzing a chosen plaintext attack proceeds along similar lines. We assume that the entire packet payload must be delivered to the CBCC encryption module before any ciphertext for the packet is revealed.

This attack begins after Mallet has a modest code book with N translations. He contemplates corrupting the last M blocks of the ciphertext of some packet for which he knows the plaintext.

Mallet knows the plaintext and ciphertext for this packet. He performs an M deep loop of NM steps trying all combinations of substitutions for the M cipher blocks. For each trial he knows how the bogus cipher block would decrypt from his code book. For each of these he can compute the checksum that the recipient would see. After about 263 steps he will find a combination of substitutions which produce a good decryption. He then passes the ciphertext on to the recipient with the bogus cipher blocks.

By this scheme he will know the decryption but have little control over it. In the outer layers of the loop, however, he may discard unpromising possibilities based on seeing the hypothetical decrypts of the early blocks and not spend time seeking good but useless decrypts. Depending on the redundancy of the semantics of the plaintext, the search may or may not be fruitful to the attacker.

There are two problems with this, however: (1) The time taken in the innermost loop approaches 264 for any values of N and M for which this is likely to succeed; (2) It is a Pyrrhic victory for the chosen plain text was presumably in route Mallet’s legitimate destination within the system. This latter point is connected in the nature of scenarios where you can postulate chosen plaintext in the context of an otherwise secure system depending on integrity. Mallet can only corrupt the data for the destination whose source allowed the insertion of the chosen plaintext. You might say that a compression service is provided that compresses data from Mallet to form the plaintext. The corresponding decompressing software is vulnerable to corrupted compressed material and so dies a horrible death, bringing the system down with it.

Regarding the first point this cannot be a pre-calculation for it must be done in light of the state vector for the beginning of the packet to be corrupted. 264 steps is a lot of computing to finish in the latency toleration for a comm link. It can be parallelized but is it still difficult. On the other hand you can delay each packet for a few hundred milliseconds and if no attack is found send it on its way uncorrupted. On the average you will have to go thru the inner loop about 264 times per corrupted packet but this need not be all devoted to one packet.

Rijndael is a 128 bit block cipher and even these near misses are irrelevant.

A related chosen plaintext attack was reported 9 years ago:

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 is aimed at a Kerberos protocol that used a 32 bit CRC check. The shortness of the check affords that attack penetration when about 232 blocks have passed. Furthermore that attack allows the attacker to better choose the content of the decrypted bogus packet. By contrast my attack might be called sabotage whereas the Stubblebine-Gligor attack may allow true penetration. Their attack is limited by the size of the code book. Mine is limited by computational ability of the attacker.
I argue here for a stronger yet mathematically simpler property that implies validity of CBCC.