If we encrypt a plain text using Double DES but with same key K1,
Can we get the same result as if we would encrypt the plain text using single DES but with different key, say K2.

What I'm asking is can we achieve this for same size of K1 and K2 :

DES(K1,DES(K1,m)) = DES(K2,m)

What would be effective key bits for the first ?

I know this is the case for Mono-Alphabetic shift cipher but I'm confused for DES.
By Key Size I mean like 64 Bit key for which their are 2^55 computations.

  • $\begingroup$ For four keys $K$ (the DES weak keys) it holds that $m\mapsto\text{DES}(K,\text{DES}(K,m))$ is identity. Thus if what's asked held for all keys $K_1$, then there would be a DES key $K_2$ making DES encryption identity. I seems feasible to disprove that one. $\endgroup$ – fgrieu Sep 29 '20 at 18:07

Can we get the same result as if we would encrypt the plain text using single DES but with different key, say K2.

It has not been formally proven, but it is extremely plausible to assume that there isn't an equivalent 'double key', that is, for a K1, there isn't a K2 where DES(K1, DES(K1, M)) = DES(K2, M) for all values M (or even a number of values of M.

What has been proven (and is somewhat similar) is that there exist K1, K2 values for which there is no K3 for which DES( K1, DES( K2, M )) = DES( K3, M ) always holds; this is known as the 'DES is not a group' theorem (although it is typically expressed differently). However, this result does not immediately imply what you are asking about.

  • $\begingroup$ Reference: Keith W. Campbell and Michael J. Wiener, DES is not a group, in proceedings of Crypto 1992 (free access). $\endgroup$ – fgrieu Sep 29 '20 at 17:28

For each key a block cipher selects a permutation from all possible permutations from $\{0,1\}^\ell \to \{0,1\}^\ell$ where $\ell$ is the block cipher. For DES, $\ell = 64$.

The number of permutations is $2^{64}!$ and the number of possible effective keys of DES is $2^{56}$. by Stirling's approximation

$$ 2^{64}! \approx \sqrt{2\pi 2^{64}} \bigl(2^{64}/e\bigr)^{2^{64}}.$$ Compare this with $2^{56}$ and see that it is tiny.

The short answer is that the DES is not forming a group under functional composition.

  • For a single $m$ there can be different keys $K_1$ and $K_2$ in DES that behaves like the single key for the double encryption at this point. $DES(K_1,(DES(K_1,m)) = DES(K_2,m)$ Never seen one since it was not a point in the academy. As pointed by poncho, we can find one by

    • select a random $m$

    • select $2^{32}$ random $K_1$ and build a table for $DES(K_1,(DES(K_1,m))$.

    • select $2^{32}$ random $K_2$ and look in the table.

      we expect a collision with 50%.

  • When considering for every $m$ in the message space $\{0,1\}^{64}$ you need to find keys that that the double encryption of the one key is equal to the other. Hard to find from the previous and there is no known even the general case $DES(K_1,(DES(K_2,m)) = DES(K_3,m))$

  • $\begingroup$ Never seen one, mostly because no one has ever looked. Finding such a $K_1, K_2, m$ triplet should be within the capability of a laptop given a few hours... $\endgroup$ – poncho Sep 29 '20 at 17:42
  • $\begingroup$ @poncho yes, nobody looked and therefore we did not see. I'm not pretty sure about a few hours. $\endgroup$ – kelalaka Sep 29 '20 at 17:44
  • $\begingroup$ Should be a few hours (and perhaps quicker); it should take an expected $2^{33}$ DES encryptions (and $2^{32}$ DES key scheduling setups), along with the table manipulation (and you can avoid most cache misses with a bit of cleverness); looking at software DES performance, that should be doable in an hour on a single core $\endgroup$ – poncho Sep 29 '20 at 17:50
  • $\begingroup$ Probability calculations made under the assumption that DES is a PRP are not valid proofs of the property asked. With these kinds of arguments, DES is not a group would be trivial. $\endgroup$ – fgrieu Sep 29 '20 at 18:12
  • $\begingroup$ @fgrieu It would have given a glimpse that for any block cipher probability of such a tuple... $\endgroup$ – kelalaka Sep 29 '20 at 18:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.