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.

Â