Multiple Modes of Operation

Introduction

One approach to lengthen key length is to casade encryption machinery of shorter key lengths. The hope being that equivalent key length for the composite is the sum of key lengths of the participating ciphers. Meet in the middle attacks show that this is not true, although there is a great cost in space to perform these attacks. Space/time tradeoffs are possible that do make such attacks practical.

A question arises as to how to do chaining, such as CBC or OFB, in these multiple modes. It has often been the practice to do such chaining on the inside, and it seemed apparant that this would be the strongest thing to do. In fact, chaining on the inside gives opportunities to attack individual stages independently, and the thereby reduces the effective key length to close to that of a single ciper. There are several methods of exploiting inside chaining, depending on the chaining configuration, and they have been exhaustively analysed by Eli Biham, see Cryptanalysis of multiple modes of operation J. Crypt. 11:1 1998 and Cryptanalysis of triple modes of operation, J. Crypt. 12:3 1999.

An Example

I reproduce from the first Biham paper a diagram of triple mode of operation with CBC applied at each stage on the inside. We will show how to attack this stage by stage using what is called Technique F: The Birthday Technique.

We assume we can feed ciphertext into the box and read the plaintext, and are trying to recover the three keys K1, K2, K3. Choose a ciphertext C and feed it into four consecutive cipher blocks. We write this as (C,C,C,C). After decryption on the first stage, and application of the cipher text chaining, we have (–,H,H,H) where – means unknown and H=C(+)D_K3(C). H is pseudo-random, so after about 2^33 C's we have two which give the same H. For this H we have the second stage equal to (–,–,X,X) where X= H(x)D_K2(H) and the last stage (–,–,–,Y) where Y=X(+)D_K1(X).

The point is, after 2^33 cipher text attempts we have two cipher blocks C and C' and the equation C(+)D_K3(C) = C'(+)D_K3(C') and we (somewhat) know when such a pair C and C' occurs because each gives the same plaintext output in the fourth position. This is all we take from the plain text output — it alerts us to the internal collision. We can solve the equation in K3 by brute force, that is, trying all values of K3 to find the one that fits for the known C and C'.

Once done, knowing K3 we can do a similar game to isolate and force solution of K2, and then K1, for a total work of something on the order of just the work to break a single key by brute force. This is significantly less than our expection of the sum of the three key lengths as the cipher's strength. For example, as triple DES, we would have expected (64-8)*3=168 bit strength, but in this mode we have only about 58 bits of strength.

Conclusions

The Biham paper suggest not using internal feedback such as the CBC|CBC|CBC featured in our example, but rather use traditional chaining around the outside, treating the triple cipher as a single unit. Internal chaining has been shown to introduce pathways for injection of information into the center of the cipher machinery which can be used to the attacker's advanatage.

20 February 2008, Burton Rosenberg