# Meet in the middle time complexity

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?

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).

• Additions: A hash table strategy is facilitated because the 64-bit values searched are essentialy random. We can e.g. use the high-order 48 bits of the value searched directly as index into a smaller hash tables. A bonus is these 48 bits need not be stored, as they would for a full hash table. It can be shown that even if we have room for $2^8+2^{8/2}$ entries per smaller hash table (with 16-bit searched value and 56-bit content for the key), and forget the rest, there's still excellent chance of success. This strategy less than doubles the RAM compared to the $2^{62}$-bit baseline.
– fgrieu
Sep 20 '21 at 12:25
• Would the space complexity of 2^56 increase if I use hash table or radix sort? Sep 20 '21 at 13:19
• @pajacol: not largely (that is, it should remain within a constant factor that's not drastically far from 1) - of course, the details would depend on the implementation Sep 20 '21 at 14:29
• This is a good answer but I think it's missing a crucial detail: 2DES has an 112-bit key and meet-in-the-middle gives you a $O(2^{56})$ attack on it. In other words, meet-in-the-middle demonstrates that (given ideal cracking gear) 2DES is no stronger than single DES. The constant factor in front of the big O is not the point.
– zwol
Sep 20 '21 at 22:27
• @zwol if you are ignoring constant factors, then $2^{56}$ is also a constant factor. (I think using the $O(...)$ notation with a constant is a strange abuse of notation. $O(2^{128}) = O(2^{56}) = O(1)$ in the usual meaning of $O$.) Sep 20 '21 at 23:10
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)).