15
$\begingroup$

In the "Introduction to Cryptography: With Coding Theory" by Trappe and Washington, in the chapter about DES algorithm the authors say that:

"if a cryptosystem is such that double encryption is equivalent to a single encryption, then there is no additional security obtained by double encryption"

Why is this?

$\endgroup$
  • 14
    $\begingroup$ I assume the question is really, "how can double encryption be equivalent to single encryption"? Because the if/then is pretty straightforward. $\endgroup$ – chepner Oct 17 at 13:59
  • $\begingroup$ Is @chepner's interpretation correct? Because this question can be edit'd to better reflect what you're interested in asking. $\endgroup$ – Nat Oct 17 at 14:45
  • $\begingroup$ Well if it's equivalent, you have the same binary blob either way. It's pretty obvious that it's none better than just encrypting once. No? What's interesting is that even if it's not equivalent, then the logic 1+1 = 2 isn't true (think meet in the middle). $\endgroup$ – Damon Oct 17 at 17:35
29
$\begingroup$

This is simply saying that if a cryptosystem has a functional composition that is

$$ h_{k}(x) = f_{k_1}(g_{k_2}(x)) $$

then you can find a key for single encryption that works as the double encryption.

For example: consider the permutation cipher where a permutation is a key. The permutations are forming a group, named permutation group, under the composition. Therefore, double encryption in permutation cipher is just another permutation, i.e. another key. Therefore you will not get a benefit.

To see this, let simplify the alphabet into 5 letters and let $P$ and $Q$ be two keys for a 5 letter permutation cipher:

$$P = \begin{pmatrix}1 & 2 & 3 & 4 & 5 \\2 & 4 & 1 & 3 & 5 \end{pmatrix} \text{ and } Q = \begin{pmatrix}1 & 2 & 3 & 4 & 5 \\ 5 & 4 & 3 & 2 & 1 \end{pmatrix}$$ The compositon of the two keys is

$$R =QP = \begin{pmatrix}1 & 2 & 3 & 4 & 5 \\4 & 2 & 5 & 3 & 1 \end{pmatrix}$$ and this is another permutation $R$, i.e. $R$ is a key that works as a single key.

Now turn back to DES:

Campbell and Wiener in 1992 showed that DES is not a group (paywalled) (and paywall-free). They showed that that the size of the subgroup generated by the set of DES permutations is greater than $10^{2499}$. Therefore this value is far greater than potential attacks on DES which would exploit a small subgroup. As a result, DES has no such weakness. Actually, we will be surprised that a well-designed block cipher will be forming a group.

If there is such property that is the DES forms a subgroup of the permutation group then there exists a known-plaintext attack on DES that requires, on average $2^{28}$ steps showed by Judy H. Moore and Simmons (paywalled).

Also, forming a group will reduce the Triple-DES or more generally the multiple encryptions into single encryption.


The academical works on DES closure

‡ This work claimed to be described briefly in a posting to sci.crypt on Usenet News, 1992 May 18. This needs a link!

$\endgroup$
  • 2
    $\begingroup$ Another simple example of a “group” cipher is the XOR cipher, where (M^K1)^K2 = M^(K1^K2). $\endgroup$ – dan04 Oct 17 at 19:41
  • $\begingroup$ @dan04 Yes, with cycle length 2. The permutation group is a better example since the Block ciphers are actually randomly selecting permutations from the possible permutations. We expect that a probabilistic adversary cannot distinguish them from Random Permutations. $\endgroup$ – kelalaka Oct 17 at 19:57
  • 5
    $\begingroup$ ... and then there are those who think that ROT-13 is too easy to break and apply it twice $\endgroup$ – Hagen von Eitzen Oct 18 at 7:31
  • 1
    $\begingroup$ This answer has several places where the grammar is awkward and it's hard to tell which direction a statement is being made in, like "providing conclusive proof that DES is not" and "Actually, we will be surprised that a well-designed block cipher will have this property." (where it's unclear if "this property" is the positive or negative). Etc. $\endgroup$ – R.. Oct 18 at 13:22
  • $\begingroup$ @R.. does it better now? $\endgroup$ – kelalaka Oct 18 at 14:40

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.