Multiple Encryption & Double DES
As we know that DES is venerable to the brute-force attack, we are interested to find an alternative.
One possible solution is to design completely new algorithm like AES.
The second solution is to use DES multiple times.
Double DES: Multiple Encryption & Double DES
The simplest form of multiple encryptions has two encryption stages and two keys and is known as Double DES.
- Given a plaintext P and two encryption keys K1 and K2, ciphertext C is generated as C = E(K2, E(K1, P))
- Decryption applies keys in reverse order: P = D(K1, D(K2, C))
- This scheme involves a key length of 56 * 2 = 112 bits, making Brute-Force attack impractical.
- However, other types of attacks are possible:
Reduction to a Single Stage: Multiple Encryption & Double DES
If it is possible to find a key such that: E(K2, E(K1, P)) = E(K3, P) then double encryption, or any number of stages of multiple encryptions with DES, would be useless.
Because the result would be equivalent to a single encryption with a single 56- bit key. o However, by the principle of reverse mapping, such a key is not possible.
Meet-In-The-Middle Attack: Multiple Encryption & Double DES
This attack based on the on the observation that if:
C = E(K2, E(K1, P)), then X = E(K1, P) = D(K2, C)
Given a known (P, C) pair, the attack proceeds as follows:
- First, encrypt P for all 256 possible values of K1.
- Store these results in a table and then sort the table by the values of X.
- Decrypt C using all 256 possible values of K2.
- Moreover, Check the result against the table for a match after every decryption.
- 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, 248 false alarms are possible since there are only 264 ciphertext values whereas 2112 key values.
- Thus, the order of attack can reduce to 248 instead of 2112.