# Meet-in-the-middle with checking complexity

In regards to meet in the middle type attacks, I have been considering the amount of operations in order to successfully find a key given two sets of plaintext / ciphertext pairs. All of the sources I have checked have stated that the maximum number of trials that are needed is $2^{n+1}$, however this does not seem to take into account the operations needed to validate key guess.

So taking 2DES as an example where one encryption has an effective key size of 56 bits. A meet in the middle attack against 2DES would need $2^{56}$ encryption plus $2^{56}$ decryption operations resulting in $2^{56}$ possible key matches. However each potential key match would then need to be verified on a second (or more) plaintext / ciphertext pair, adding another two operations to verify each match. The result is a maximum of $4 \times 2^{56}$ operations.

Is there a reason the checks are not included in this attack? Or is there a flaw in my thinking here?

• Keywords are "asymptotic complexity" and "order of magnitude". – Thomas Aug 30 '13 at 5:44

Well, one assumption you appear to be making is that, with 2DES, there will be approximately $2^{56}$ possible key matches. Actually, there are an expected $2^{48}$ possible key matches; here's why:

Let us assume we're running the meet-in-the-middle attack on 2DES, and consider an arbitrary incorrect encryption trial (that is, we try an encryption key that is not the correct one). If DES acts anything like what we expect, we'll arrive with an effectively random 64 bit value. We will do a trial decryption if that value appears somewhere in the decrypt list; there are $2^{56}$ values on that list, and so that specific random 64 bit value will appear an expected $2^{-8}$ times; hence for each incorrect encryption key, we will need to perform an expected $2^{-8}$ verification tests. There are $2^{56}$ (actually, $2^{56}-1$, however that difference is lost in the noise) incorrect keys, and hence we expect to need to perform $2^{56} \times 2^{-8} = 2^{48}$ tests on incorrect keys (plus the one test on the correct key).

This gets into the more fundamental question of "what do we actually mean when we give a complexity estimate?". Well, it isn't as straight-forward as you might think; if we say that a specific attack uses $2^{100}$ foo operations, we do not mean that it uses precisely $2^{100}$ of those operations (and never requires $2^{100}+1$ of them), or that it doesn't require any bar operations; what we mean is that the time the attack takes is bounded by those $2^{100}$ foo operations; the time taken by any additional foo operations, or any needed bar operations doesn't significantly increase the attack time, where significantly means "doesn't increase the attack time by more than a factor drastically larger than 1".

Remember, the goal of these estimates is not because we're actually interested in running the attacks; instead, what they're there for is to allow us to be confident that the attack takes much longer than any possible adversary has the budget for. A factor of 2 might sound significant; however we typically can't estimate the adversary's budget that accurately (especially if we're talking about adversaries in the future); what we attempt to do is to design our systems so that an attack is (say) $2^{40}$ times what an adversary might have; compared to $2^{40}$, a single factor 2 is actually not significant.

Stepping back to your example, what this means that if we have an attack which acts in two phases:

• Generate a potential set of solutions (taking time $A$)

• Validate those potential solutions (taking total time $B$)

then we'll say that attack takes time about $max(A, B)$; that's because the time taken is dominated by whichever takes the longer (and if they're both the same, the fact that the attack actually takes twice as long isn't a significant factor).

In the 2DES attack (which follows this model), $A$ is much larger, and so we basically ignore $B$ (not because we don't think that it's important, but it doesn't slow down the attack to a degree that we care about).

The best case I can think of is $O(n)2^{n+1}$, where n is the number of bits in the key used in DES. First we'll encrypt plaintext $P$ with $2^n$ keys. Each pair (ciphertext, key) can be stored in an AVL tree. The worst case insertion complexity is $O(log(2^n))$ i.e., $O(n)$. So total complexity of the first half of the algorithm is $n \times 2^n$. Similarly for the second half of the algorithm The final cipher text will be decrypted with $2^n$ keys in the worst case. Then there will be a lookup using the result of the decryption in the AVL tree. The worst case complexity for this lookup is $O(log(2^n))$ i.e., $O(n)$. So the worst case complexity of the second part of the algorithm is $n \times 2^n$ as well. Hence the total complexity is $2 O(n) 2^n$ i.e., $O(n)2^{n+1}$. This can be approximated as $n2^{n+1}$. Now we know that $n$ is $56$. So basically we are talking about $56 \times 2^{57}$ which again can be approximated by $64 \times 2^{57}$ i.e., $2^{63}$ and that is not safe nowadays.