Cryptography
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?

## Solution

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