Home | | **Cryptography and Network Security** | Multiple Encryption and Triple DES(Data Encryption Standard)

Given the potential vulnerability of DES to a brute-force attack, there has been considerable interest in finding an alternative.

**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*1 and *K*2, ciphertext *C *is generated as

*C *= E(*K*2, E(*K*1,
*P*))

Decryption requires that the keys be applied in reverse order:

*P *= D(*K*1, D(*K*2,
*C*))

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

** REDUCTION TO A SINGLE STAGE
**Suppose it were true for DES, for all 56-bit key values,
that given any two keys

E(*K*2,
E(*K*1, *P*)) = E(*K*3, *P*) **(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 equiv- alent 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 264 pos- sible 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 264 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:

256 6 1017

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 proven [CAMP92].

** MEET-IN-THE-MIDDLE ATTACK **Thus,
the use of double DES results in a mapping that is not equivalent to a single
DES encryption. But there is a way to attack this scheme, one that does not
depend on any particular property of DES but that will work against any block
encryption cipher.

The algorithm, known as a **meet-in-the-middle attack**, was first
described in [DIFF77]. It is based on the observation that, if we have

Given a known pair,
(*P*, *C*), the attack proceeds
as follows. First,
encrypt *P *for all 256 possible
values of *K*1. Store these results in a
table and then sort the table by the values
of *X*. Next, decrypt
*C
*using all 256 possible values
of *K*2. As each decryption is produced, check the result against
the table for a match. If a match occurs,
then test the two resulting
keys against a new known plaintext–ciphertext pair. If the two keys
produce the correct
ciphertext, accept them as the correct keys.

For
any given plaintext *P*, there are 264 possible
ciphertext values that could be produced by double DES. Double DES uses, in
effect, a 112-bit key, so that there
are 2112 possible
keys. Therefore, on average, for a given plaintext *P*, the

number
of different 112-bit keys that will produce a given ciphertext *C *is

2112/264 = 248. Thus, the foregoing procedure will produce
about 248 false
alarms on the first (*P*, *C*) pair.
A similar argument
indicates that with an additional 64 bits of known plaintext and ciphertext, the false alarm rate is reduced to 248 - 64 = 2 - 16.
Put another way, if the
meet-in-the-middle attack is performed on two blocks of known
plaintext–ciphertext, the probability that the correct keys are determined is 1 - 2 - 16. The result is that a known plaintext
attack will succeed
against double DES, which has a key size of 112
bits, with an effort on the order of 256, which is not much more than the 255 required
for single DES.

Triple DES with Two
Keys

An obvious counter to the meet-in-the-middle attack is
to use three stages of encryption with three different keys. This raises
the cost of the meet-in-the-middle attack to 2112, which
is beyond what is practical now
and far into the future. However, it has the drawback of requiring a key length
of 56 * 3 = 168 bits, which may be somewhat unwieldy.

As
an alternative, Tuchman proposed a triple encryption method that uses only two keys [TUCH79]. The function
follows an encrypt-decrypt-encrypt (EDE) sequence (Figure 6.1b):

*C *= E(*K*1, D(*K*2,
E(*K*1, *P*)))

*P *= D(*K*1, E(*K*2,
D(*K*1, *C*)))

There is no cryptographic significance to the use of decryption for the second stage. Its only advantage is that it allows users
of 3DES to decrypt data encrypted by users
of the older single DES:

*C
*= E(*K*1, D(*K*1,
E(*K*1, *P*))) = E(*K*1, *P*)

*P *= D(*K*1, E(*K*1,
D(*K*1, *C*))) = D(*K*1, *C*)

3DES
with two keys is a relatively popular alternative to DES and has been adopted
for use in the key management standards ANS X9.17 and ISO 8732.1

Currently, there are no
practical cryptanalytic attacks on 3DES. Coppersmith
[COPP94] notes that the cost of a brute-force key search on 3DES is on the order of 2112 L (5 * 1033) and estimates that the
cost of differential cryptanalysis suffers an exponential growth,
compared to single
DES, exceeding 1052.

It
is worth looking at several proposed attacks on 3DES that, although not
practical, give a flavor for the types of attacks that have been considered and
that could form the basis for more successful future attacks.

The first serious proposal came from Merkle and
Hellman [MERK81]. Their plan involves finding plaintext values that produce
a first intermediate value of *A *= 0

(Figure 6.1b) and
then using the
meet-in-the-middle attack to determine the
two keys. The level of effort is 256, but the technique
requires 256 chosen plaintext–ciphertext pairs, which
is a number unlikely to be provided
by the holder of the keys.

A known-plaintext attack is outlined in
[VANO90]. This method is an improvement over the chosen-plaintext approach but requires
more effort. The attack is based on the observation that if we know *A *and *C *(Figure 6.1b), then the problem reduces to that of an attack
on
double DES. Of course, the attacker
does not know *A*, even
if *P *and *C *are known, as long
as the two keys are unknown. However, the attacker can choose a potential value of
*A *and then try to find a known (*P*,
*C*) pair
that produces *A*. The attack proceeds as follows.

**1.
**Obtain *n *(*P*, *C*) pairs.
This is the known plaintext. Place these in a table (Table 1)
sorted on the values
of *P *(Figure
6.2b).

**2.
**Pick an arbitrary value *a *for *A*, and create a second table (Figure 6.2c) with entries
defined in the following fashion. For each of the 256 possible
keys *K*1 = *i*, calculate
the plaintext value *Pi *that produces
*a*:

*Pi *= D(*i*, *a*)

For each *Pi *that
matches an entry in Table 1, create an entry in Table 2 consisting
of the *K*1 value and the value of *B *that is
produced for the (*P*, *C*) pair from Table
1, assuming that value of *K*1:

*B *= D(*i*, *C*)

At
the end of this step, sort Table 2 on the values of *B*.

**1.
**We now have a number of candidate values of *K*1 in Table 2 and are in a position to search for a value of *K*2. For each of the 256 possible keys *K*2 = *j*, calculate the
second intermediate value for our chosen value of *a*:

*Bj *= D(*j*, *a*)

At each step, look up *Bj *in Table 2. If there is a match, then the corresponding key *i *from Table
2 plus this value of *j *are
candidate values for the unknown keys (*K*1, *K*2). Why? Because we have found a pair of keys (*i*, *j*) that produce
a known (*P*, *C*) pair (Figure 6.2a).

**2.
**Test each candidate pair of keys (*i*, *j*) on a few other plaintext–ciphertext pairs. If
a pair of keys produces
the desired ciphertext, the task is complete. If no pair succeeds, repeat from step 1 with a new value of *a*.

For
a given known (*P*, *C*), the probability of selecting the unique value of
*a *that leads to success is 1/264.
Thus, given *n *(*P*, *C*) pairs, the probability
of success for a single selected
value of *a *is *n*/264.
A basic result from probability theory is
that the expected number of
draws required to draw one
red ball out of a bin containing
*n *red balls and *N *- *n *green balls is (*N *+ 1)/(*n *+ 1) if the balls are not replaced.
So the expected number of values of *a *that must be
tried is, for large *n*,

Triple
DES with Three Keys

Although the
attacks just described appear impractical, anyone
using two-key 3DES may feel some concern.
Thus, many researchers now feel that three-key 3DES is the preferred alternative (e.g.,
[KALI96a]). Three-key 3DES has an effective key length
of 168 bits and is defined as

*C
*= E(*K*3, D(*K*2,
E(*K*1, *P*)))

Backward
compatibility with DES is provided by putting *K*3 = *K*2 or *K*1 = *K*2.

A number
of Internet-based applications have adopted three-key 3DES, including PGP and
S/MIME, both discussed in Chapter 18.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Cryptography and Network Security Principles and Practice : One Symmetric Ciphers : Block Cipher Operation : Multiple Encryption and Triple DES(Data Encryption Standard) |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.