**Changing probabilities of differentials and linear sums via isomorphisms of ciphers**

*Alexander Rostovtsev*

**Abstract: **\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.

**Category / Keywords: **secret-key cryptography / AES, block ciphers, linear cryptanalysis

**Date: **received 11 Mar 2009

**Contact author: **rostovtsev at ssl stu neva ru

**Available format(s): **PDF | BibTeX Citation

**Version: **20090314:051352 (All versions of this report)

**Short URL: **ia.cr/2009/117

[ Cryptology ePrint archive ]