Hypothetical DES weakness: dual encryption identical to single encryption with specific keys

If there always existed a $k_3$ such that $\operatorname{DES}(k_2, \operatorname{DES}(k_1, M)) = \operatorname{DES}(k_3, M)$, how would that affect the security of the DES block cipher?

• Since this is clearly not the case for DES, you might want to edit you questin to talk about a hypothetical blockcipher with that property. Mar 1 '17 at 7:19
• "Clearly not the case" == "Proven not to be the case"; see math.boisestate.edu/~liljanab/MATH509Spring2012/DesNotGroup.pdf Mar 1 '17 at 14:15

I will take this to mean that it's possible to efficiently find a $k_3$ so that

$$E(k_2,E(k_1,M))=E(k_3,M)$$

which would mean the cipher $E$ has too much structure and given a keylength $n,$ a double encryption like above is as weak as a single encryption and brute force key search would take $O(2^n)$ encryptions at worst.

Mind you, a meet in the middle attack on double encryption for an arbitrary cipher $E$ can break it in time $O(2^n)$ and a few plaintext/ciphertext pairs $(M,C)$ if memory of size $O(2^{(n+\log n)})$ is also available. First form a hash-sorted list of $$\{(k_2,E(k_1,M)):k_1 \in \{0,1\}^n\}$$ sorted on the second coordinate and then keep computing $E^{-1}(k_2,C)$ as $k_2$ ranges over $\{0,1\}^n,$ and looking up to see if it is in the table.

If you find a hit, then try with another P/C pair to confirm the guess is not spurious. This is because the composite permutation may have fixed points.

Edit:. I didn't originally want to make this too abstract, but as pointed out in the comments, what you're asking is whether $E$ forms a group, which it most certainly does not when $E$ is DES.

• Often with DES / TDES the inner key is designated the number 1 and the outer is designated 2. Although we commonly count from left to right this makes sense, as chronologically, you perform the inner encryption first. Mar 1 '17 at 8:37
• @Maarten Bodewes, thanks, fixed. Also I was inverting the plaintext by mistake but you didn't notice that. :-) Mar 1 '17 at 10:15
• It's not just double encryption that would rendered useless if DES were a group, but also Triple DES or any other iterated DES. Fortunately, DES is not a group (see e.g. math.boisestate.edu/~liljanab/MATH509Spring2012/DesNotGroup.pdf)
– J.D.
Mar 1 '17 at 11:35

In the case of DES is would reduce the security of DES itself from "insecure" to "no security at all", and it would reduce the security of 3DES from "you don't have to replace it, but don't use it if you build something new" to "no security at all".

The reason is simple: The keyspace of DES is so small, that it's possible to do a brute force in hours to days in a cluster. If such a key would exist, you could find it with reasonable effort. And such a key would serve as a master-key for every possible encryption: If you decrypt both sides in your equation with $k_3$, you get: $$DES^{-1}(k_3,DES(k_2,DES(k_1,M))) = M$$ Decrypting with $k_3$ removes two layers of encryption, regardless which $k_1,k_2$ were used. So if you get any ciphertext $C = DES(k_1,M)$, simple encrypt it with an arbitrary key $k_2$ once, and then decrypt once with $k_3$ (in the case of 3DES twice), and you get $M = DES^{-1}(k_3,DES(k_2,DES(k_1,M)))$.

Generalizing from DES to an arbitrary symmetric encryption scheme: Existence of such a $k_3$ would render the encryption scheme worthless instantly, if it is true for all $M$ (or only a few values for $k_3$ to cover all $M$). You could consider this the ultimate backdoor and it is unlocked - and there is no way to prevent others from finding it.

• The question is sort of ambiguous so I can see why you read it this way, but I read it as asking if for every pair of keys $k_1, k_2$ there existed another key $k_3$ which they were equivalent to (i.e. the question is asking what happens if DES is a group). That $k_3$ is not a 'skeleton' key that is equivalent to all pairs, rather it is equivalent to just the specific pair $k_1, k_2$. For a different pair, $k_4, k_5$ there would be another key $k_6$ that this new pair is equivalent to.
– J.D.
Mar 1 '17 at 14:26
• @J.D. I think it can be read both ways. The expression "there exists $k_3$, s.t. ..." and an unspecified $M$ makes it ambiguous. I interpreted $M$ as "for all $M$", but maybe that wasn't what was meant in the question.
– tylo
Mar 1 '17 at 14:45