Consider an SPN operating on blocks of size $m\ell$ bits. Suppose that each round consists of adding the round key (bitwise xor), applying $m$ S-boxes (so that each S-box operates on $\ell$ bits), and finally applying the P-box, that is, a fixed permutation of indices. To be more precise let $$S=(\{0,1\}^{\ell m},(S_{2^\ell})^m,\sigma),$$ $$T=(\{0,1\}^{\ell m},S_{\ell m},\pi_P)$$

be the concatenation of the S-boxes, and the P-box, respectively, when thought of as a cryptosystems.

We say that a cryptosystem $A=(P,K_1,e_1)$ can be embedded in the cryptosystem $B = (P,K_1,e_2)$ if there exists a map $\phi:K_1 \rightarrow K_2 $ such that $e_1(x,k_1)=e_2(x,\phi(k_1))$ for all $x \in P,k_1 \in K_1$. We say that two cryptosystems are equivalent if they can be embedded into each other.

Why is it the case that the product cryptosystems $T \times S$ and $S \times T$ are not equivalent? In other words, why do they not commute?

It is easily seen that adding a round key commutes with the P-box. The possibility of interchanging the S-boxes and P-box would therefore threaten the whole security of the considered SPN.

I am interested in the proof that this is not so.

  • $\begingroup$ It seems as though you are stating that symbol substitutions (S-Boxes) and positional permutations (P-Boxes) do not commute, when in fact they do. It is the addition of round keys that does not commute with S-Boxes. $\endgroup$ – N.jackoson Jan 30 '18 at 22:15

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.