Introduction To Network Security: Theory And Practice (2015)

Chapter 2. Data Encryption Algorithms

2.3 Multiple DES

As discussed in Section 2.2.6, applying DES multiple times can effectively extend the length of encryption keys without modifying DES. Multiple DES can therefore be used to resist brute-force attacks. We use DES to denote a multiple DES scheme of applying DES times. By applying DES, it means applying either the encryption algorithm or the decryption algorithm .

2.3.1 Triple-DES with Two Keys

Triple-DES with two keys, denoted by 3DES/2, is the simplest and reasonably secure method against brute-force attacks. It extends the key length to 112 bits long. Let and be two 56-bit encryption keys and a 64-bit plaintext block. The standard 3DES/2 encryption algorithm applies on to obtain , then applies on to obtain , and finally applies on to obtain . That is,

2.7

For convenience, we denote this scheme by .

The following is the 3DES/2 decryption algorithm:

2.8

For convenience, we denote this scheme by .

We note that there are other combinations for 3DES with two keys, such as or . Any of these combinations would serve the purpose. However, only the combination of allows us to use 3DES/2 to decrypt ciphertext string produced by applying single DES with key . This is done as follows: let and let . Then

A major drawback of 3DES is that its software executions are not as efficient as one would like them to be.

2.3.2 2DES and 3DES/3

In addition to 3DES/2, we may also apply DES twice with two keys, denoted by 2DES/2. For simplicity, we use 2DES to denote 2DES/2. Let and be two DES encryption keys and a 64-bit plaintext block. The standard 2DES encryption algorithm and decryption algorithm are described as follows:

However, 2DES is vulnerable to the meet-in-the-middle attack (see Section 2.3.3 for details). Thus, 2DES is considered nonsecure.

We may also apply DES thrice with three keys, denoted by 3DES/3. 3DES/3 has an effective key length of 168 bits. Let , and be three encryption keys. The standard 3DES/3 encryption algorithm and decryption algorithm are described as follows:

2.9

2.10

2.3.3 Meet-in-the-Middle Attacks on 2DES

2DES is vulnerable to the meet-in-the-middle attacks. Suppose that the attacker has obtained two plaintext–ciphertext pairs and , where

That is,

The attacker may then be able to identify, with probability close to 1, the encryption keys and with time complexity much smaller than . The attack can be carried out as follows:

List all 56-bit strings and calculate, for each pair ,

Note that when and , we have . Thus, for each pair with , it is possible that . If there is only one such pair, then we have found the encryption keys and . Otherwise, apply each pair with on to obtain

Again, we note that when and , we have . Thus, if , then is more likely to be the encryption key pair. Indeed, we can show that the possibility that there exist more than one such pair is very small.

Note that for any plaintext block and any candidate for the encryption key pair, the ciphertext block is uniformly distributed (or close to being uniformly distributed). This is the property any good encryption algorithm should possess. Because , there are pairs . As , the expected number of pairs that satisfy is or near

Likewise, the expected number of pairs from these pairs that satisfy and is or near

Thus, the possibility of finding is or near .

The time complexity of executing this attack is in the order of

This is much smaller than .