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

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?

-
The reason for the homework tag not existing were discussed in Asking homework questions. –  Paŭlo Ebermann Jan 6 '13 at 12:50
@PaŭloEbermann , Do you think I should edit my question so it will not look like an homework assignment but more like a cryptographic problem? –  Yoni Hassin Jan 6 '13 at 13:07
If you can't fit a full table, why not try using a smaller table? –  Antimony Jan 7 '13 at 7:29
@YoniHassin, I think the info you added needs to be asked to the professor. –  mikeazo Jan 7 '13 at 14:24
I encourage you to read the FAQ on homework questions. In particular, the FAQ asks you to show your work: show us what you've tried so far, where you've gotten stuck, etc. See also Paŭlo Ebermann♦'s answer. The problem is your question is too much like "Do my homework for me" and not enough like "Here is my task, I already did this part, and I have now this problem. Here is what I tried, but which didn't work." –  D.W. Jan 9 '13 at 7:22

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 '13 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 '13 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 '13 at 18:45