Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
2  
Keywords are "asymptotic complexity" and "order of magnitude". –  Thomas Aug 30 '13 at 5:44
add comment

1 Answer

up vote 4 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.