Meet in the middle time complexity

Question

Hello,
I am wondering why it is stated that double encrypted message with 2 DES keys is possible to break in worst case in $2\times2^{56}$ time using meet in the middle attack.

Here is my reasoning:

1. Example plaintext & ciphertext pair: AAAAAAAAAAAAAAAA & 35E16A5E44161DB8 (keys to break: BABABABABABABABA & CDCDCDCDCDCDCDCD), additional plaintext & ciphertext pairs to check in step 4 because keyspace is large enough that it is probable that there are many key pairs that would succeed with just one pair: 0000000000000000 & 84EC2BA1A2748F7B ; 1111111111111111 & 549A6B5696E02B5E ; 2222222222222222 & 7BB2C14B23A807C3 ; 3333333333333333 & 3BD27AAF1E0EB4F7
2. I generate array with 2^56 entries, n-th entry is pair (n-th key ; DES encrypted plaintext AAAAAAAAAAAAAAAA with n-th key). It will look like this (keys are in ascending order with correct parity bits):
   0101010101010101 3AE716954DC04E25
   0101010101010102 2B74C1D96CDE840B
   0101010101010104 3367B1FBB4D2FFA7
   0101010101010107 8880DA13709C9198
   0101010101010108 80181B831CDC8D61
   010101010101010B 0F6CD43C15297456
   .....
3. Now I have to sort array by ciphertexts in column 2
4. Now I try to decrypt ciphertext 35E16A5E44161DB8 with consecutive keys and search for this value in column 2 by binary search:
   Attempt #1: key 0101010101010101 gives 477B6FD8296E1956 search key in sorted array, if key is found check other plaintext & ciphertext pairs, should fail
   Attempt #2: key 0101010101010102 gives 107272EB5D1BFF28 search key in sorted array, if key is found check other plaintext & ciphertext pairs, should fail
   Attempt #3: key 0101010101010104 gives 23153894F3FF825E search key in sorted array, if key is found check other plaintext & ciphertext pairs, should fail
   Attempt #4: key 0101010101010107 gives D0D497791C20B166 search key in sorted array, if key is found check other plaintext & ciphertext pairs, should fail
   Attempt #5: key 0101010101010108 gives 8A830E5E7927C541 search key in sorted array, if key is found check other plaintext & ciphertext pairs, should fail
   Attempt #6: key 010101010101010B gives BA7A15AA12A62C02 search key in sorted array, if key is found check other plaintext & ciphertext pairs, should fail
   .....
   Attempt #57873028282430310: key CDCDCDCDCDCDCDCD gives AC972FC04E884797 search key in sorted array, if key is found check other plaintext & ciphertext pairs, should succeed

For me it appears that step 3 is necessary to be able to perform step 4

If I was right, then time complexity would be around $2^{56}\times\log(2^{56}) = 56\times2^{56}$ using optimal sorting algorithm. What am I missing in my reasoning?

Answer 1

What am I missing in my reasoning?

Two things:

• There are other strategies other than sorting to find collisions; one obvious one is to build a huge hash table. Now, in practice, sorting would probably go faster (because a hash table that huge would be impractical), but theoretically, a hash table would allow the $O(1)$ accesses that this complexity analysis implicitly assumes.

• $O(n \log n)$ is not actually the optimal sorting time. It is if the only operations you can perform on the data are comparisons and data movement; however we're not actually constrained that way. One obvious approach would be to do a radix sorting method, which can have considerably better time complexity.

Now, to be honest, we typically ignore the time taken by these noncryptographical operations (such as searching and sorting), unless they take a really large fraction of the total time. Quite frankly there can be a lot of details when you go down to that level (such as the complexity of dealing with $O(2^{56})$ data), and instead we just count DES evaluations.

We're not actually trying to break 2DES; instead, we're showing that breaking 2DES could actually be achievable in practical time. If we were actually trying to break it, we might end up using a lambda search instead, which would have a constant factor increase in complexity and is not guaranteed, would be easier to implement (as the lambda search would use much less memory, and still being easy to parallelize).

Answer 2

1. You can save all the options on a (huge) Hashtable (dictionary) -> which approaches O(1), so you don't need to sort.
2. You can sort by radix (or bucket) sort (less than nlog(n)).