As technology improves and more sophisticated attacks are developed, encryptions systems become less secure and need to be replaced. There are two main approaches to achieving increased security. The first involves using encryption multiple times and leads, for example, to triple encryption. The second approach is to find a new system that is more secure, a potentially lengthy process.

We start by describing the idea behind multiple encryption schemes. The idea is to encrypt the same plaintext multiple times using the same algorithm with different keys. Double encryption encrypts the plaintext by first encrypting with one key and then encrypting again using another key. For example, if the keyspace for single encryption has 56 bits, hence $2^{56}$ keys, then the new keyspace consists of $2^{112}$ keys. One might guess that double encryption should therefore double the security. This, however, is not true. Merkle and Hellman showed that the double encryption scheme actually has the security level of a 57-bit key. The reduction from $2^{112}$ to $2^{57}$ makes use of the meet-in-the-middle attack, which is described in the next section.

Since double encryption has a weakness, triple encryption is often used. This appears to have a level of security approximately equivalent to a 112-bit key (when the single encryption has a 56-bit key). There are at least two ways that triple encryption can be implemented. One is to choose three keys, $K_1\text{,}{K}_2\text{,}{K}_3$, and perform $E_{K_1}(E_{K_2}(E_{K_3}(m)))$. This type of triple encryption is sometimes called EEE. The other is to choose two keys, $K_1$ and $K_2$, and perform $E_{K_1}(D_{K_2}(E_{K_1}(m)))$. This is sometimes called EDE. When $K_1=K_2$, this reduces to single encryption. Therefore, a triple encryption machine that is communicating with an older machine that still uses single encryption can simply set $K_1=K_2$ and proceed. This compatibility is the reason for using $D_{K_2}$ instead of $E_{K_2}$ in the middle; the use of $D$ instead of $E$ gives no extra cryptographic strength. Both versions of triple encryption are resistant to meet-in-the-middle attacks (compare with Exercise 11). However, there are other attacks on the two-key version ([Merkle-Hellman] and [van Oorschot-Wiener]) that indicate possible weaknesses, though they require so much memory as to be impractical.

Another strengthening of encryption was proposed by Rivest. Choose three keys, $K_1\text{,}{K}_2\text{,}{K}_3$, and perform $K_3\oplus E_{K_2}(K_1\oplus m)$. In other words, modify the plaintext by XORing with $K_1$, then apply encryption with $K_2$, then XOR the result with $K_3$. This method, when used with DES, is known as DESX and has been shown to be fairly secure. See [Kilian-Rogaway].