What is a practical method for for finding a triple of keys that maps a given plaintext to a given ciphertext using EDE?
I think this requires something similar to a man-in-the-middle attack...
$\begingroup$
$\endgroup$
2
-
1$\begingroup$ Welcome to Cryptography. Your question in the title is off-topic here though it is about Cryptography. What is the practical method? What is the name of the encryption algorithm? $\endgroup$– kelalakaCommented Mar 4, 2019 at 8:21
-
1$\begingroup$ @fgrieu This sounds awfully much like an answer, fgrieu. I've removed "implement" from the title, I presume that "find" was implied. It can always be reverted, but note questions asking for code are considered off topic. $\endgroup$– Maarten Bodewes ♦Commented Mar 5, 2019 at 13:43
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Indeed, that's a case for Meet-in-the-Middle.
Notice that $E_{K_3}(D_{K_2}(E_{K_1}(P)))=C$ if and only if $D_{K_2}(E_{K_1}(P))=D_{K_3}(C)$. Therefore, finding $(K_1,K_2)$ and $K_3$ making the two sides equal solves the problem. Both sides take random-like values when $(K_1,K_2)$ and $K_3$ vary. Therefore trying $2^{b/2}$ values (e.g. incremental) of $(K_1,K_2)$ and $K_3$ leads to collision with fair probability (where $b$ is the block size in bits).
For an actual implementation with $b=64$ (as in DES), I would
- fix an arbitrary $K_1$ and compute $Q=E_{K_1}(P)$
- tabulate values of $D_{K_2}(Q)$ for incremental values of $K_2$ in a data structure allowing fast access given the result and recovery of $K_2$. Well over $2^{31}$ values of $D_{K_2}(Q)$ fit in my computer's available memory of 30 GB.
- compute $D_{K_3}(C)$ for incremental $K_3$ until getting a match.
Success is expected with about $3\cdot 2^{32}$ DES operations, which is very feasible.
Note: in the above, incremental must deal with the fact that the low-order bits of DES key bytes is ignored, so as to lower DES's resistance against brute force attack.
That has cost $\mathcal O(2^{b/2})$ effort and memory. The memory, but not the effort, can be reduced a lot, and the attack made parallel (reducing time), using techniques in Paul C. van Oorschot and Michael J. Wiener, Parallel Collision Search with Cryptanalytic Applications, in Journal of Cryptology, 1999. That would be a must for $b=128$ of AES.
