Attacking 2DES efficiently

Question

Meet in the middle on 2DES uses $2^{56}$ memory. Given the fact that the attacker has only $2^{45}$ memory. How can the attacker adjust the attack so even with this memory limit, it will still be more efficient than looking after all the existing keys?

I guess you can separate this to a few lookups - a few tables - each time containing a different subset while making sure each row get compared. which should still be more efficient than $O(n^2)$. Is this the answer?

Answer 1

The attacker splits the range of $2^{56}$ keys for the first DES into $2^{17}$ ranges of size $2^{39}$. He will then run $2^{17}$ times the following meet-in-the-middle attack, once for each range:

• For all the keys in the range, the attacker computes the first DES on the known plaintext, yielding $2^{39}$ 64-bit words, for a total size of $2^{45}$ bits.
• The attacker sorts them in ascending order.
• For all $2^{56}$ possible keys for the second DES, the attacker decrypts the known ciphertext, and looks for the block in the sorted list.

Worst case is that the attacker needs to do this for all $2^{17}$ ranges, for a total number of DES encryptions of about $2^{56+17} = 2^{73}$, which is still vastly faster than $2^{112}$. At no point does the attacker needs to remember more than $2^{45}$ bits. The sorting steps are negligible ($2^{17}·39·2^{39} \approx 2^{50}$ comparison-and-swaps) and the lookups can be optimized with indirect indexes (the $2^{39}$ words will be more or less regularly spread, so we can do better than a simple dichotomy).

Answer 2

We are talking about attacking double-DES here, which encrypts a 64-bit block $P$ with two 56-bit keys $K_1,K_2$ as $C = E_{K_2}(E_{K_1}(P))$. As noted by Diffie and Hellman already in late 70s, to attack it with a one or two plaintexts as follows. Suppose we know that $P_0$ is encrypted to $C_0$, then

• for all possible $K_1$ compute $E_{K_1}(P)$ (partial encryption) and store the intermediate state $S$ and $K_1$ in a hash table;
• for all possible $K_2$ compute $E_{K_1}^{-1}(C)$ (partial decryption) and store the resulting intermediate state $S'$ and $K_2$ in another table;
• check if exist such $S = S'$. If so, a pair $(K_1,K_2)$ is a candidate pair of keys.

Since the states are 64-bit, our filter yields $2^{56+56-64} = 2^{48}$ candidate key pairs, which can be tested on a second (plaintext, ciphertext) pair. The complexity of the attack is $2^{56}$, hence Double-DES provides only 56 bits of security.

Meet-in-the-middle attack can be done memoryless in the same way as memoryless collision search with the Pollard's $\rho$-method. Let's recall it.

The collision search for function $F:\{0,1\}^n\rightarrow\{0,1\}^n$ works as follows: start with random $x$ and iterate in parallel $x\rightarrow F(x)\rightarrow F^2(x)\rightarrow \ldots$ and $x\rightarrow F^2(x)\rightarrow F^4(x)\rightarrow \ldots$. When two iterations collide after $i$ steps, we get that $F^i(x) = F^{2i}(x)$, which in turn implies that $F^{i-1}(x)$ and $F^{2i-1}(x)$ are collisions for $F$. This method works for most randomly-looking $F$ and has complexity $O(2^{n/2})$.

For the meet-in-the-middle attack you slightly modify the algorithm. Suppose that you have to find $x,y$ such that $G(x) = H(y)$. In our Double-DES example $G(x) = E_{x}(P)$ and $H(y) = E_{y}^{-1}(C)$. Then you define

• $Q(z) = G(z)$ if $z$ ends with 0 (or any other predicate)
• $Q(z) = H(z)$ if $z$ ends with 1.

Then you iterate $x\rightarrow Q(x)\rightarrow Q^2(x)\rightarrow \ldots$ and $x\rightarrow Q^2(x)\rightarrow Q^4(x)\rightarrow \ldots$. When you get a collision $Q^i(x) = Q^{2i}(x)$ then with probability $1/2$ the last call for the first iteration was with $G$ and for the second iteration with $H$ or vice versa, so you actually have $G(Q^{i-1}(x)) = H(Q^{2i-1}(x))$, which solves the meet-in-the-middle problem.

Note that we implicitly converted states to keys. This is easy as states are wider, and can be done by simply trimming any 8 bits. If states were shorter, then a more sophisticated procedure had to be used, and the complexity would grow.