0:00

As discussed in the previous module,

DES is considered broken with brute force implementations that can find the key in hours.

Given the potential vulnerability of DES to 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 and will be discussed later in this module.

Another alternative which would preserve the existing investment in software and

equipment is to use multiple encryptions with DES with multiple keys.

We examined the widely accepted Triple DES or 3DES approach.

Triple DES or 3DES,

enables the increase and key size without needing to design an entirely new algorithm.

To make brute force attack infeasible,

we need to increase the key length so that

the attacker's effort grows exponentially with the key length.

For the multiple encryption approach,

the simplest form of multiple encryption has

two encryption stages and two keys and it's called Double-DES.

In Double-DES, for the encryption,

2DES encryption cipher sequentially applied where

the key K1 is used first and then the key K2 is used for the following DES cipher.

To reverse the encryption,

Double-DES decryption uses key K2 first and then the key K1 after.

This can also be expressed in math as it's

shown and in the mathematical expression those that

are inside the parenthesis are computed or processed first.

The use of two independent keys,

keys of one and keys of two,

K1 and K2 are 112 bits long.

Twice as long as a single key and can provide 112 bits of entropy for the ciphertext.

So, the computational effort of a brute force attacker,

who only analyzes the Double-DES input and the output P and C,

it's effort will grow by O of two to the 112.

However, the attacker can

significantly reduce its complexity by conducting meet in the middle attack.

Such meet in the middle attack can apply to

any block encryptions ciphers which are sequentially processed.

Instead of focusing only on the input and

the output of the entire chain of cipher components,

the meet in the middle attack also stores and

computes the transitional value between the cipher components.

We call that value X here.

Let's explain meet in the middle with a diagram.

Here is a double encryption.

For example, if the encryption function is DES,

then this is a Double-DES.

In Double-DES, the plaintext goes through

the first DES encryption function with a key of K1.

And then, the output of that DES encryption gets

input to another DES encryption using the key K2.

The meet in the middle attacker knows that there is an intermediate value,

in this case, X, which are in between the two DES functions.

Given a known plaintext or a pair of P and C that is known to the attacker,

the attacker first takes the known plaintext P and

computes the first DES function with the key of K1.

The attacker varies the key K1 which value does not know,

and stores all of the two to the 56 possible pair of values K1 and X.

The attacker then takes the ciphertext C and

computes in the backward direction to compute X that is,

it will compute the decryption of C to compute X.

Whenever the attacker computes the DES decryption from C,

it compares the result with the X values that it

computed and stored from using P

and the encryption computations in the forward direction.

When there's a match for X,

it has a candidate K1 and K2 which it can then use to try another

known plaintext ciphertext pair of P and C. There can be false alarms,

but the false alarm rate grows exponentially with

the number of known plaintext ciphertext pairs,

limiting the number of known plaintexts that is required for the attacker.

If it were the correct key pair of K1, K2 then,

it will always yield the correct P,

C regardless of the plaintext P that the attacker tries.

This reduces the attacker effort to O of two to the 56 because now,

the attacker can compute the DES separately.

More specifically, the attacker will need to compute all the

two to the 56 computations for the first DES cipher from P. And then,

half of the two to the 56 or

two to the 55 decryption computations for the second DES cipher from C on average.

That is on average, the computational effort will be two to the 56 plus two to the 55,

which is O of two to the 56.

This complexity of O of two to the 56 is significantly less than O of two to the 112.

Taking the ratio between the two,

the difference is more than 10 to the 21st power.

On the other hand,

comparing it with DES,

it only increases the complexity by one exponent with base two.

Therefore, Double-DES with just a naive way of using

multiple DES ciphers with different keys is not secured enough

because the meet in the middle attack exploits the vulnerability of

double encryption approaches which

effectively lowers the attack complexity to find the key.

Meet in the middle attack can be used against any double encryption approach,

regardless of the cipher algorithm that was applied twice.