More About Block Ciphers - Understanding Cryptography - page 138

Let's look at an example.
Example 5.3. As an example, if we double-encrypt with DES and choose to test
three plaintext-ciphertext pairs, the likelihood of a faulty key pair surviving all three
key tests is:

2 2 · 56 − 3 · 64 = 2 − 80 .

Let us examine the computational complexity of the meet-in-the-middle attack.
In the first phase of the attack, corresponding to the left arrow in the figure, we per-
form 2 κ encryptions and store them in 2 κ memory locations. In the second stage,
corresponding to the right arrow in the figure, we perform a maximum of 2 κ decryp-
tions and table look-ups. We ignore multiple key tests at this stage. The total cost
for the meet-in-the-middle attack is:

number of encryptions and decryptions = 2 κ + 2 κ = 2 κ+1
number of storage locations = 2 κ

This compares to 2 κ encryptions or decryptions and essentially no storage cost in
the case of a brute-force attack against a single encryption. Even though the storage
requirements go up quite a bit, the costs in computation and memory are still only
proportional to 2 κ . Thus, it is widely believed that double encryption is not worth
the effort. Instead, triple encryption should be used; this method is described in the
following section.
Note that for a more exact complexity analysis of the meet-in-the-middle attack,
we would also need take the cost of sorting the table entries in Phase I into account
as well as the table look-ups in Phase II. For our purposes, however, we can ignore
these additional costs.

5.3.2 Triple Encryption

Compared to double encryption, a much more secure approach is the encryption of
a block of data three times in a row:

y = e k 3 ( e k 2 ( e k 1 ( x ))) .

In practice, often a variant of the triple encryption from above is used:

y = e k 1 ( e − 1

k 2 ( e k 3 ( x ))) .

This type of triple encryption is sometimes referred to as encryption-decryption-
encryption (EDE). The reason for this has nothing to do with security. If k 1 = k 2 ,
the operation effectively performed is

y = e k 3 ( x ) ,