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 .