Paper 2009/117

Changing probabilities of differentials and linear sums via isomorphisms of ciphers

Alexander Rostovtsev


\begin{document} Ciphers $y=C(x, k)$ and $Y=C_{1}(X, K)$ are isomorphic if there exists invertible computable in both directions map $y \leftrightarrow Y$, $x \leftrightarrow X$, $k \leftrightarrow K$. Cipher is vulnerable if and only if isomorphic cipher is vulnerable. Instead of computing the key of a cipher it is sufficient to find suitable isomorphic cipher and compute its key. If $\varphi $ is arbitrary substitution and $T$ is round substitution, its conjugate $T_{1}=\varphi T\varphi ^{ - 1}$ is cipher isomorphism. Conjugate substitutions have the same cycle type. Conjugation can be composed with affine maps. Combining conjugation and affine equivalence, sometimes we can transform non-linear special $S$-box to conjugate affine substitution $S_{1}$. Usually for given $S$, $S_{1}$ there are many different auxiliary substitutions $\varphi $. Conjugate diffusion map and XOR operation become non-linear, but taking appropriate $\varphi $ we can get large probabilities of differentials and linear sums of diffusion map and XOR. For example AES substitution (as finite field inverting) is approximately conjugate with bit changing substitution. That conjugate substitution has differentials and linear sums of probability 1. Corresponding byte substitution $\varphi $ defines non-linear conjugate diffusion map and non-linear conjugate to XOR operation with round key. Probabilities of differentials (biases of linear sums) of byte substitution of conjugate diffusion map are 8-12 times more then corresponding values of original $S$-box. Probabilities of differentials of conjugate XOR with the round key byte depends on the round key and can be 1 for some key bytes.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
AESblock cipherslinear cryptanalysis
Contact author(s)
rostovtsev @ ssl stu neva ru
2009-03-14: received
Short URL
Creative Commons Attribution


      author = {Alexander Rostovtsev},
      title = {Changing probabilities of differentials and linear sums via isomorphisms of ciphers},
      howpublished = {Cryptology ePrint Archive, Paper 2009/117},
      year = {2009},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.