In one book it says

a set of permutations with the composition operation is a group. This implies that using two permutations one after another cannot strengthen the security of a cipher, because we can always find a permutation that can do the same job because of the closure property.

If I try to understand the bold part, is below explanation correct?

Assume you have a set of all permutations of "abc", that is: Your set is: "abc" ,"acb", "bca", "bac", "cab, "cba". Let's take "abc".

Permute it once and get say: "cba" (Let's say permuting once means you encrypt it).

Now let's assume you want to strengthen above permutation by permuting it once again (encrypt it once more), e.g. now you permute "cba" and arrive at "bac". In theory one could have arrived at "bac" from "abc" in a single permutation too (in a single encryption), thus additional permutation didn't really make much sense from this point of view. Because it says basically what you can do in two permutations you can effectively also do in a single permutation.

  • $\begingroup$ There always is such a "single" permutation. If you can describe or find it is another matter. If above would be the case then 3DES would be as strong as single DES, obviously it isn't. $\endgroup$ – Maarten Bodewes Feb 21 '18 at 23:27

At component level, such as Sboxes, you are essentially correct. This is why an (unkeyed, fixed) SBox is never composed with another SBox, without some kind of other mechanism, such as key bit addition, or a permutation of bits between adjacent SBoxes [as suggested by @Paul Uszak].

Note that above, I interpret the word "permutation" as a fixed, unkeyed map. When keys are mixed in, and we view the full cipher globally things change drastically. In this case, the permutation which is the composition of two (or three for triple DES) permutations is extremely difficult to determine since

  1. the search space is so large
  2. there are no shortcuts, the permutations are not presented in lookup table form, plus random keys are involved so we now have essentially random permutations.
  • $\begingroup$ ... or a permutation of bits between adjacent SBoxes. $\endgroup$ – Paul Uszak Feb 21 '18 at 22:17
  • $\begingroup$ What about DES? That's a keyed permutation, right? And stacking DES is a well known technique of strengthening the cipher: see triple DES. I guess there need to be some kind of (size) constraints for your answer to be correct? $\endgroup$ – Maarten Bodewes Feb 22 '18 at 13:20
  • $\begingroup$ Sure, thats a valid caveat. I had nterpreted the question at the component level... $\endgroup$ – kodlu Feb 22 '18 at 19:48

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.