Multiple Encryption and Triple DES

Multiple Encryption and Triple DES

Given the potential vulnerability of DES to a brute-force attack, there has been considerable interest in finding an alternative. One approach is to design a completely new algorithm, of which AES is a prime example. Another alternative, which would preserve the existing investment in software and equipment, is to use multiple encryption with DES and multiple keys. We begin by examining the simplest example of this second alternative. We then look at the widely accepted triple DES (3DES) approach.

Double DES

The simplest form of multiple encryption has two encryption stages and two keys (Figure 6.1a). Given a plaintext P and two encryption keys K₁ and K₂, ciphertext C is generated as

C = E(K₂, E(K₁, P))

Decryption requires that the keys be applied in reverse order:

P = D(K₁, D(K₂, C))

For DES, this scheme apparently involves a key length of 56 x 2 = 112 bits, of resulting in a dramatic increase in cryptographic strength. But we need to examine the algorithm more closely.

---

[Page 177]

Reduction to a Single Stage

Suppose it were true for DES, for all 56-bit key values, that given any two keys K₁ and K₂, it would be possible to find a key K₃ such that

Equation 6-1

If this were the case, then double encryption, and indeed any number of stages of multiple encryption with DES, would be useless because the result would be equivalent to a single encryption with a single 56-bit key.

On the face of it, it does not appear that Equation (6.1) is likely to hold. Consider that encryption with DES is a mapping of 64-bit blocks to 64-bit blocks. In fact, the mapping can be viewed as a permutation. That is, if we consider all 2⁶⁴ possible input blocks, DES encryption with a specific key will map each block into a unique 64-bit block. Otherwise, if, say, two given input blocks mapped to the same output block, then decryption to recover the original plaintext would be impossible. With 2⁶⁴ possible inputs, how many different mappings are there that generate a permutation of the input blocks? The value is easily seen to be

On the other hand, DES defines one mapping for each different key, for a total number of mappings:

2⁵⁶>10¹⁷

Therefore, it is reasonable to assume that if DES is used twice with different keys, it will produce one of the many mappings that are not defined by a single application of DES. Although there was much supporting evidence for this assumption, it was not until 1992 that the assumption was proved [CAMP92].