Join Log in
Score:1
pajacol avatar Crypto

Meet in the middle time complexity

in flag
pajacol

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?

448
0 + 0
des
kelalaka avatar
in flag
kelalaka
Related and duplicates ...[Why does applying 56-bit DES twice only give 57 bits of security?](https://crypto.stackexchange.com/q/25073/18298)
0
Reply
fgrieu avatar
ng flag
fgrieu
Realted [question on how to make the attack practical](https://crypto.stackexchange.com/q/25258/555) (since with it's ludicrous $2^{62}$-bit RAM requirement, it's not).
0
Reply
Score:4
poncho avatar Crypto
my flag
poncho

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

0 + 0
fgrieu avatar
ng flag
fgrieu
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.
1
Reply
pajacol avatar
in flag
pajacol
Would the space complexity of 2^56 increase if I use hash table or radix sort?
0
Reply
poncho avatar
my flag
poncho
@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
0
Reply
kr flag
zwol
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.
0
Reply
sh flag
Paŭlo Ebermann
@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$.)
0
Reply
kr flag
zwol
@PaŭloEbermann Yeah, I agree it's an abuse of notation but it's not that unusual IME when talking about costs of attacks on ciphers. The idea is that the only thing we care about is the exponent: going from $2^{112}$ to $2^{56}$ represents a significant weakening of the cipher.
0
Reply
Score:1
Yotam Sofer avatar Crypto
cl flag
Yotam Sofer
  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)).
0 + 0
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.