cryptanalysis block-cipher meet-in-the-middle-attack
Updated Sun, 26 Jun 2022 17:16:59 GMT

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?


Hint: suppose someone told you $n-m$ bits of $k_2$; how much time/space would a meet-in-the-middle attack take then?

Comments (3)

  • +0 – It will take $O(2^{2n-m})$ but with low (non neglectable) probability, while using $n$ entries will have very high probability (almost 1). — Jan 07, 2013 at 16:23  
  • +1 – 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? — Jan 07, 2013 at 16:27  
  • +1 – 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. — Jan 07, 2013 at 18:45