I am having trouble understanding the meet in the middle attack and how it works on double DES.
I understand that on single DES the key length is 2^56 but why when using double DES is it 2^57? Can someone explain it in simple terms please?
-
You should use cryptography stack exchange when dealing with crypto primitives. Here's a decent explanation for the attack: crypto.stackexchange.com/a/25625/24949 – Z.T. May 8 '16 at 12:31
There is a concept of effective/actual key strength. For Double DES the effective key strength is 2^57 even though double DES uses 2^112 keys. The below example will make it clear.
Assume that you are a cryptanalyst who has access to the plain text and encrypted text. Your aim is to recover the secret key. Assume AAA (plaintext) -> XXX (After 1st encryption) -> ZZZ (after 2nd encryption).
You start with AAA and try all the 2^56 combinations for secret key by encrypting AAA. This will give you a big list of possible values for XXX. Next you take ZZZ and try all the 2^56 combinations for secret key by decrypting ZZZ. This will give you a big list of possible values for XXX.
The amount of effort you have put in 2^56 + 2^56 = 2^57.
Now do a simple lookup between the two lists to find a matching value. As soon you see a matching value XXX in both the lists, you have found out the secret key. So this means that with effort of 2^57 keys you have broken the encryption.
Recovering the key for double-DES takes three steps. Given the plaintext and the ciphertext you do the following:
- Encrypt the plaintext with all 2^56 possible keys and write down the results
- Decrypt the ciphertext with all 2^56 possible keys and write down the results
- Check where the results are the same. That is your key.
Note that all you had to do to recover the key was using DES 2 * 2^56 times, which makes 2^57.
