# Attacking 2DES efficiently

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?

-
I think this paper was state-of-the-art when it was written, although the $\hspace{2.09 in}$ situation might have changed since then. $\;$ –  Ricky Demer Oct 30 '13 at 18:06

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

-
It is highly possible that I don't know how to count. I'll presently fix my numbers. –  Thomas Pornin Oct 30 '13 at 19:38
The attacker needs to remember more than $2^{45}$ bits at lots of points, for example, to keep track of the current range, to compute the last ciphertext block, to sort those blocks, and to decrypt the known ciphertext. $\;$ –  Ricky Demer Oct 30 '13 at 19:48
It is not substantially more. Keeping track of the current range, decryption and so on use only a few hundred more bits, i.e. completely negligible with regards to $2^{45}$. For the sorting, the heap sort will use negligible extra space; merge sort is probably more efficient if dealing with, say, hard disks, and will need some temporary extra space, but that can be arranged to be less than $2^{45}$. If that really bothers you, make that $2^{18}$ ranges of $2^{38}$ keys, and you will have all the extra room you may need (a lot more, actually). –  Thomas Pornin Oct 30 '13 at 20:04
This works, and might score well for homework, unless the $2^{45}$ is deliberately misleading. But this is vastly more costly than collision-based search as outlined in this other answer, in term of block cipher operations, memory used, and memory accesses. –  fgrieu Oct 31 '13 at 7:03
Well, given the way the question was phrased, I just assumed that it was homework, and went for the expected homework-level answer. –  Thomas Pornin Nov 1 '13 at 0:55

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.

-
It would help to state that $G(x)$ [resp. $H(y)$] is encryption [resp. decryption] with key $x$ [resp. $y$] of plaintext [resp. ciphertext] of one known plaintext/ciphertext pair; and that $G$ and $H$, thus $Q$, behave as random functions, justifying the likely existence of a cycle short enough to be found. I wonder what the expected number of block cipher executions is to exhibit a $(x,y)$ candidate in a DES context, and how using some memory could help. A detail: some or vice versa seems needed to reach the stated probability of $1/2$ rather than $1/4$. –  fgrieu Oct 31 '13 at 6:57
Thanks, fgrieu, I have added some more details to the text. What do you mean in your last sentence? –  Dmitry Khovratovich Oct 31 '13 at 12:31
Unless I err: odds that the last call for the first iteration was with G and for the second iteration with H is $1/4$; but odds that the last call for the first iteration was with a different function than the second is $1/2$, and that seems to be what really matters. –  fgrieu Oct 31 '13 at 13:59
Oh, indeed, thanks. I definitely meant "G and H" or "H and G". –  Dmitry Khovratovich Oct 31 '13 at 16:18