Skip to main content
9 of 14
Did the math, and YES it is an improvment over MitM with partition
fgrieu
  • 145.5k
  • 12
  • 319
  • 611

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+1}=2^{25}$ more evaluations of $E^{(1)}$ or $D^{(2)}$ than in basic MitM (I have silently dropped small factors here and there, but hope this holds within a factor of $2$ except for the cycle-finding overhead). Even though, this is an improvement over the obvious time-memory tradeoff for MitM, where we split the problem into (at most) $2^r$ runs each using a manageable table of $2^{n-r}$ entries, for an expected cost dominated by $2^{n+r-1}$ evaluations of $D^{(2)}$ and search 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 the cycle-finding techniques using distinguished points makes much less memory accesses (which are more costly than a DES is an ASIC), and require 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 independently that the above cost calculations become invalid for $w$ approaching $2n$).

With that change, the proposed method seems closer to what's studied in the section 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$; 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 to achieve a sizable reduction in memory, the expected number of cipher operations rises way above $2^{n+1}$. My reading of the best (thus complex) improvements in the literature is that they are far from achieving what's envisioned in this comment.

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 on one hand, and cycle-finding with a few parameterizations.

fgrieu
  • 145.5k
  • 12
  • 319
  • 611