# Break double encryption

Let $E_k$ : {0,1}$^l$ be a block cipher encryption function with block-size $l$ and key-length $n$.

In class, we saw that a double encryption with two independent keys $E{}'_{k_1k_2}(x)$ = $E_{k_1}(E_{k_2}(x))$,

can be brute-forced in $O(2^n)$ time and $O((l + n)2^n)$ space using the meet-in-the-middle attack:

create a table with $2^n$ entries mapping keys of length $l$ to entries of length n by encrypting the known plain text $x$ with all possible keys $k_2$, then search the table by decrypting the corresponding cipher text $c$ using all possible keys $k_1$.

Suppose you only have $O((l + m)2^m)$ space (where $m < n$), Give an algorithm to break the double encryption in time $O(2^{2n-m})$.

I am stuck for days, can't figure out the trick that will allow such an efficient algorithm.

Any ideas? Tips? Hints?

This is homework of course(Tag not exists for some reason).

Is it sufficient to show that if we choose smaller $n$ the encryption will be broken with non neglect-able probability? Or I must show an algorithm that ALWAYS brake the encryption?

-
Are you sure about the $O(2n)$ time in your given algorithm? Shouldn't this be $O(2·2^n) = O(2^n)$? – Paŭlo Ebermann Jan 6 at 12:48
The reason for the homework tag not existing were discussed in Asking homework questions. – Paŭlo Ebermann Jan 6 at 12:50
Correct, fixed :) – Yoni Hassin Jan 6 at 12:50
If you can't fit a full table, why not try using a smaller table? – Antimony Jan 7 at 7:29
@YoniHassin, I think the info you added needs to be asked to the professor. – mikeazo Jan 7 at 14:24
Hint: suppose someone told you $n-m$ bits of $k_2$; how much time/space would a meet-in-the-middle attack take then?
It will take $O(2^{2n-m})$ but with low (non neglectable) probability, while using $n$ entries will have very high probability (almost 1). – Yoni Hassin Jan 7 at 16:23
Go through it again: if you know $n-m$ bits of the key, it'll take less than $O(2^{2n-m})$ time; how much exactly? How much space? And, once you have that, how do you extend that observation to the case where you weren't given the hint? – poncho Jan 7 at 16:27
Again, do the exercise: if $k_1$ has $n$ unknown bits, and $k_2$ has $m$ unknown bits, how much time would it take to recover the unknown bits? How much space? Once you have answered that question, it should be simple to use that as a black-box to solve the case where both $k_1$ and $k_2$ has $n$ unknown bits. – poncho Jan 7 at 18:45