Attack Review

I argue for a stronger yet mathematically simpler property that implies that CBCC provides integrity or authentication.

I will assume that the IV for each packet is unknown to the attacker. Perhaps the IV is the simple block encryption of the serial number of the packet. I assume that the encryptor demands the entire packet before it reveals any of the ciphertext. Let X be the set of values that can be fed to the block cipher. In the cases of interest X is either [0, 2⁶⁴−1] or [0, 2¹²⁸−1]. Consider an abelian group whose elements are X, such as add or XOR. The group is chosen independently of the key and known to the attacker. Let f be the operator of the group. A good packet is one whose sum (using f) over each plaintext block is 0 (the group identity). The task for the attacker is to choose a good packet which when encrypted with the key=k and IV=i yields the encrypted packet. The attacker may then see that packet and then choose an alternative encrypted packet which when decrypted with k and i produces a good packet different from the original.

The attacker does not know k or i but has a large collection of plaintext-ciphertext pairs for k.

I summarize:

The attacker knows neither the key nor the initial vector for the packet.
Attacker chooses all of the plaintext bits of a packet. He must choose a good packet lest it be rejected by the encryptor.
Packet by packet encryption: The attacker sees the ciphertext but only after the good packet has been submitted to the encryptor. See note below.
The attacker has a Partial Code Book (PCB) which is a collection of N random pairs of plaintext and ciphertext blocks for the current key. He has not been able to influence which pairs those are.
The attacker gets to see any decryption of a ciphertext that he chooses and submits to the decrypter, but only if it decrypts to a good packet.
Of course the attacker cannot reset the counter which controls the IV without a new cipher key being selected.

The attacker can accumulate pairs for his PCB, but not of his choosing, for he can neither choose nor know the IV. The basic integrity claim, moderated below, is that the attacker can produce no cipher packets that will decrypt to good packets. He can only pass on encrypted packets produced by the encrypter who knows both the key and IV. Even then, he must pass them on in exactly the same sequence that they were produced.

To set notation, the blocks of the plaintext are P_j for 0 ≤ j ≤ n. That the plaintext packet is good is the requirement that cs_n = O where cs₋₁ = O and for 0 ≤ j ≤ n; cs_j = cs_j−1 • P_j where “•” is the group operator and “O” is the group identity. E(x) is the encryption of text x and D(E(x)) = x. Block j of the encrypted packet is C_j. C₀ = E(E(sn) xor P₀) and for 0 < j ≤ n; C_j = E(C_j−1 xor P_j). “sn” is the packet serial number and E(sn) serves as the initial vector.

The attacker may attempt to find a substitute encrypted packet for delivery as follows. He chooses some encrypted block in some packet and searches for substitute encrypted blocks for that and the following blocks of the encrypted packet. The modified encrypted packet need not be the same length but it must decrypt to a good packet. The attacker can consult his PCB and consider alternate encrypted blocks for which he knows the block decryption.

Suppose that the attacker chooses ciphertext block C_j. He considers substituting C'_j for C_j because he knows D(C'_j) from his PCB. He already knows C_j−1. He can thus predict the decryption of the corrupted plaintext block P'_j = C_j−1 xor D(C'_j). Next he checks to see of the abelian checksum is zero and in the likely case that it not he must either try another value for C'_j or try propagating the ruse further into the packet. Each step of this process has a probability of success of 2^−J in case of a block cipher of J bits. If he does not succeed he must eventually pass the uncorrupted encrypted packet thru lest the time-out of the communications protocols call attention to his efforts. He can restart his efforts with the arrival of the next encrypted packet. All of the combinatorial work or the attacker must be done while these timeouts are running. These work can be done in parallel.

Pre Computations

Once the PCB has become modestly large, even a few hundred entries, the attacker can build an inventory of encrypted packet tails to be grafted onto the beginning of a new encrypted packet. To be suitable, such a tail would have to match the partial checksum and also the current cipher chaining state. These tails would not have to be stored as they could be quickly recomputed but the index from 2*J bits to the recipe for rebuilding the tail would have to be stored. With the birthday effect this would succeed after about 2^J cipher blocks. This is much slower than the above plan for it must send 2^J ciphered blocks thru the channel.

Packet by packet encryption

The attacker may thus not choose plain text blocks late in the packet based on early ciphertext blocks. This is called an adaptive chosen plaintext, I think. I am not aware of attacks without this stricture but it makes the arguments simpler. Nor am I aware of having made explicit use of the principle. This rule is connected with using an initial vector with each packet. Unless the PCB holds a decryption of a serial number, the chained cipher state cannot be known or constructively influenced by the attacker.

Rationale for non-standard crypto model

I used an abelian group as having fewer properties than say a CRC. This is to make clearer the properties that the claimed integrity depends upon. In particular I do not need the non commutativity and non associativity of CRC, but I do need a large set of check values. Any abelian group gives just as much structure as I think I need. It is a good exercise to see why this model does not fall to the permuted cipher block attack that defeats PCBC.

I define a “good packet” rather than committing where the checksum is. I found that I was spending too much time wondering whether there were advantages of putting it first or last.