Author(s): Bruce Schneier

ISBN: 0471128457

Publication Date: 01/01/96

Previous | Table of Contents | Next |

Combining Block Ciphers

There are many ways to combine block algorithms to get new algorithms. The impetus behind these schemes is to try to increase security without going through the trouble of designing a new algorithm. DES is a secure algorithm; it has been cryptanalyzed for a good 20 years and the most practical way to break it is still brute force. However, the key is too short. Wouldn’t it be nice to use DES as a building block for another algorithm with a longer key? We’d have the best of both worlds: the assurance of two decades of cryptanalysis plus a long key.

**Multiple encryption** is one combination technique: using an algorithm to encrypt the same plaintext block multiple times with multiple keys. Cascading is like multiple encryption, but uses different algorithms. There are other techniques.

Encrypting a plaintext block twice with the same key, whether with the same algorithm or a different one, is not smart. For the same algorithm, it does not affect the complexity of a brute-force search. (Remember, you assume a cryptanalyst knows the algorithm including the number of encryptions used.) For different algorithms, it may or may not. If you are going to use any of the techniques in this chapter, make sure the multiple keys are different and independent.

A naìve way of improving the security of a block algorithm is to encrypt a block twice with two different keys. First encrypt a block with the first key, then encrypt the resulting ciphertext with the second key. Decryption is the reverse process.

*C*=*E*_{K2}(*E*_{K1}(*P*))*P*=*D*_{K1}(*D*_{K2}(*C*))

If the block algorithm is a group (see Section 11.3), then there is always a *K*_{3} such that

*C*=*E*_{K2}(*E*_{K1}(*P*)) =*E*_{K3}(*P*)

If this is not the case, the resultant doubly-encrypted ciphertext block should be much harder to break using an exhaustive search. Instead of 2^{n} attempts (where *n* is the bit length of the key), it would require 2^{2n} attempts. If the algorithm is a 64-bit algorithm, the doubly-encrypted ciphertext would require 2^{128} attempts to find the key.

This turns out not to be true for a known-plaintext attack. Merkle and Hellman [1075] developed a time-memory trade-off that could break this double-encryption scheme in 2^{n + 1} encryptions, not in 2^{2n} encryptions. (They showed this for DES, but the result can be generalized to any block algorithm.) The attack is called a **meet-in-the-middle attack;** it works by encrypting from one end, decrypting from the other, and matching the results in the middle.

In this attack, the cryptanalyst knows *P*_{1}, *C*_{1}, *P*_{2}, and *C*_{2}, such that

*C*_{1}=*E*_{K}_{2}(*E*_{K1}(*P*_{1}))*C*_{2}=*E*_{K2}(*E*_{K1}(*P*_{2}))

For each possible *K*, he computes *E*_{K}(*P*_{1}) and stores the result in memory. After collecting them all, he computes *D*_{K}(*C*_{1}) for each *K* and looks for the same result in memory. If he finds it, it is possible that the current key is *K*_{2} and the key in memory is *K*_{1}. He tries encrypting *P*_{2} with *K*_{1} and *K*_{2}; if he gets *C*_{2} he can be pretty sure (with a probability of success of 1 in 2^{2m – 2n}, where *m* is the block size) that he has both *K*_{1} and *K*_{2}. If not, he keeps looking. The maximum number of encryption trials he will probably have to run is 2*2* ^{n}*, or 2

This attack requires a lot of memory: 2^{n} blocks. For a 56-bit algorithm, this translates to 2^{56} 64-bit blocks, or 10^{17} bytes. This is still considerably more memory storage than one could comfortably comprehend, but it’s enough to convince the most paranoid of cryptographers that double encryption is not worth anything.

For a 128-bit key, the amount of memory required is an enormous 10^{39} bytes. If we assume that a way exists to store a bit of information on a single atom of aluminum, the memory device required to launch this attack would be a cube of solid aluminum over a kilometer on a side. And then you need some place to put it! The meet-in-the middle attack seems infeasible for keys this size.

Another double-encryption method, sometimes called **Davies-Price**, is a variant of CBC [435].

*C*_{i}=*E*_{K1}(*P*_{i}⊕*E*_{K2}(*C*_{i - 1}))*P*_{i}=*D*_{K1}(*C*_{i}) ⊕*E*_{K2}(*C*_{i - 1})

They claim “no special virtue of this mode,” but it seems to be vulnerable to the same meet-in-the-middle attacks as other double-encryption modes.

*Triple Encryption with Two Keys*

A better idea, proposed by Tuchman in [1551], operates on a block three times with two keys: with the first key, then with the second key, and finally with the first key again. He suggested that the sender first encrypt with the first key, then decrypt with the second key, and finally encrypt with the first key. The receiver decrypts with the first key, then encrypts with the second key, and finally decrypts with the first key.

*C*=*E*_{K1}(*D*_{K2}(*E*_{K1}(*P*)))*P*=*D*_{K1}(*E*_{K2}(*D*_{K1}(*C*)))

Previous | Table of Contents | Next |