Can cycle finding techniques reduce the memory usage of the MitM attack against 2DES and 3DES?

A 2DES like cipher $c=E^{(2)}_{K_2}(E^{(1)}_{K_1}(p))$ where both halves have an $n$ bit key is vulnerable to a meet-in-the-middle attack.

Meet-in-the-middle using a big table

Create a table containing $E^{(1)}_{K_1}(p)$ for all possible $K_1$ and computing $D^{(2)}_{K_2}(c)$ for all values of $K_2$, looking for a matching result.

This approach requires a big table with about $2^n$ entries.

Meet-in-the-middle using cycle finding

An alternative approach would be to define a hash function that maps an $n+1$ bit value to another $n+1$ value:

Use $1$ bit of the input to decide between $E^{(1)}_{K}(p)$ and $D^{(2)}_{K}(c)$ and the remaining $n$ bits as key for this function.

A collision of this hash function can either have the same discriminator bit, in which case it's useless for our purposes, or different discriminator bits, in which case it's a successful meeting.

Now search for collisions of this hash function, applying the usual memory reduction techniques like cycle-finding and/or distinguished points. This should require only around $2^{n/2}$ table entries instead of $2^{n}$ table entries, while increasing computation cost only my a small constant factor.

Does this approach work?

• It would help to name the block width of $E^{(1)}$ and $E^{(2)}$, say $b=64$ in the case of DES; and state how from these $b$ bits we determine the $n+1$ bits kept for the iterated function, which is not trivial. – fgrieu Apr 26 '15 at 12:53
• 1) In the simplest case we could truncate. If we need a tweak to repeat the whole experiment with a different hash function (not sure if that's required) we can use any kind of tweakable hash (preferably a cheap one) 2) I don't think the block-size matters at all with most modes of operation (including ECB, CBC and CTR). We simply need a long enough known plaintext/ciphertext pair. – CodesInChaos Apr 26 '15 at 13:08
• Yes, it works. It's a standard trick; kudos for re-discovering it. I see no reason the table size would amount to $2^{n/2}$. The complications in working out exact parameters arise when you work out the details of (a) parallelism, (b) distinguished points, (c) the cost of memory and routing networks, to get the exact optimal tradeoff (if you care about constant factors). – D.W. Apr 27 '15 at 7:10
• Working on a prototype implementation, I noticed that my assumptions about how iterated hashes cycle were wrong. I didn't know that a few cycles and their tails dominate. – CodesInChaos Apr 27 '15 at 9:44

Let $b$ be the width of $E^{(1)}_{K_1}(p)$ and $D^{(2)}_{K_2}(p)$. For the block cipher DES that would be $b=64$, with $n=56$. I'll assume $n+4<b<2n-4$, which holds in this case and simplifies some approximations.

Let $w$ be the width of the function iterated. The question as worded proposes $w=n+1=57$, and thus finds collisions fast, but with $w<b$ only a fraction (like $2^{w-b}=2^{-7}$ with $w<b-4$) are such that they reveal $K_1$ and $K_2$ such that $c=E^{(2)}_{K_2}(E^{(1)}_{K_1}(p))$.

Let's first increase $w$ from $n+1=57$ to $w=b=64$. The collision condition is now precisely such that, when the discriminator bits are different, $c=E^{(2)}_{K_2}(E^{(1)}_{K_1}(p))$ where $K_1$ and $K_2$ are derived from the colliding inputs, and the common output is $E^{(1)}_{K_1}(p)=D^{(2)}_{K_2}(c)$. We expect a find of $(K_1,K_2)$ to have odds about $2^{b-2n}=2^{-48}$ to be the correct one, and that's determined with negligible extra cost, just as in the normal MitM.

I see no reason why the proposed method would not find collision with a usable discriminator bit as expected for a random function, at an expected cost of about $2^{w/2+1}$ evaluations of the function (only a little more with cycle-finding using distinguished points, given the modest $w$; I neglect that). So the expected cost in DES operations is like $2^{2n-w/2+1}=2^{81}$.

Using little RAM by the above technique thus comes at the price of making about $2^{n-w/2+0.4}=2^{24.4}$ times more evaluations of $E^{(1)}$ or $D^{(2)}$ than in basic MitM, which is expected to perform about $2^{n+0.6}$ evaluations (I'm discounting cycle-finding overhead).

Even though, this is an improvement over the obvious time-memory tradeoff for MitM on a memory-bound system, where we split the problem into (at most) $2^r$ runs with $r$ fixed bits in $K_1$, each using all available RAM for $2^{n-r}$ entries, for an expected cost dominated (for $r>4$) by $2^{n+r-1}$ evaluations of $D^{(2)}$ and searches of that in the table. With $r=n-w/2+2=26$, the two techniques make the same $2^{2n-w/2+1}=2^{81}$ number of DES operations, but the MitM makes as many accesses in $2^{n-r}=2^{30}$ values, while cycle-finding using distinguished points makes much less memory accesses (which are more costly than a DES is an ASIC), and requires significantly less memory.

The above calculation suggests to increase the width $w$ of the function we search collisions for, above $w=b$ considered above, up to something closer to $2n$ (this is possible if we have several plaintext-ciphertext pairs, but beware that when $w$ is not a multiple of the native block size we are not sure that the candidate $(K_1,K_2)$ found by collision really works for the full block forming $p$ and $c$ that we used, and when $w$ goes from $b$ to $b+1$ we abruptly need two block cipher operations per evaluation of the iterated function, rather than one; independently, the above cost calculations become invalid for $w$ approaching $2n$).

With that change, the proposed method seems closer to what's studied in section 5.3 on MitM in Paul C. van Oorschot and Michael J. Wiener: Parallel Collision Search with Cryptanalytic Applications (in Journal of Cryptology, January 1999, Volume 12, Issue 1), which seems to use $w=1.5b$ when applied to 2DES (section 6.3); that refines their earlier Improving Implementable Meet-in-the-Middle Attacks by Orders of Magnitude (in proceedings of Crypto 1996).

So yes, cycle-finding techniques can reduce the memory usage (size, and number of accesses) of the MitM attack against 2DES. And it does so with a lesser increase of the number of cipher operations (which has an influence on time) than plain partitioning of the problem, which keeps the product $\;$memory size × cipher operations$\;$ about constant.

It remains that the expected number of cipher operations rises significantly above $2^{n+1}$ in the best (thus complex) improvements in the literature; it seems they are far from achieving what's quantitatively envisioned in this comment (much more RAM and/or DES operations is needed). The advantages (pointed by that comment) of cycle-finding with distinguished points hold:

• Thanks to distinguished points, most DES computations need no memory accesses; this is the biggest cost saver when DES is implemented in ASIC.
• Because collision detection is made only on distinguished points, the RAM requirement is much lower;
• There is little communication required compared to basic MitM distributed on multiple nodes with memory (but more than for the obvious time-memory tradeoff of MitM, where the $2^r$ jobs are entirely independent, at the cost of computing all $D^{(2)}_{K_2}(c)$ in each job).

I wish I had a graph visualizing, on a $\log_2$ scale, the time complexity (in DES operations, and separately memory searches) and memory size achieved by the most obvious time-memory trade-off for MitM, and cycle-finding with a few parameterizations.

• You can't just equate the number of operations with time, you also need to take parallelism into account. (And DJB argues that you can't neglect the cost of memory access circuitry for many attacks either.) With cycle-finding I'd expect the cost of memory to be cheap compared to the cost of all those parallel DES computation circuits. For example such a computer might have ~4 GB of memory and $2^{20}$+ DES circuits, running for ~$2^{36}$ timesteps (where each timestep is one DES invocation). – CodesInChaos Apr 26 '15 at 17:42
• @CodesInChaos: I did the math (it needs a check), and come to the (tentative) conclusion that the method proposed in the question, at least slightly modified to increase the iterated function width $w$ to at least $b$ (64 for DES) rather then $n+1$ (57 for DES), is a significant improvement over MitM with partition into plausible number of runs. However it is far from achieving what's in the above comment, and even the best improvements known do not seem to approach that; my guess is that somewhat you overestimate success odds or underestimate the number of DES operations required. – fgrieu Apr 26 '15 at 20:32