DES : Is Double Encryption using same key twice equivalent to single DES using different key but of same size

Question

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.

Answer 1

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.

Answer 2

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))$