Paper 2009/117
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 nonlinear 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 nonlinear, 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 nonlinear conjugate diffusion map and nonlinear conjugate to XOR operation with round key. Probabilities of differentials (biases of linear sums) of byte substitution of conjugate diffusion map are 812 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.
Metadata
 Available format(s)
 Category
 Secretkey cryptography
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 AESblock cipherslinear cryptanalysis
 Contact author(s)
 rostovtsev @ ssl stu neva ru
 History
 20090314: received
 Short URL
 https://ia.cr/2009/117
 License

CC BY
BibTeX
@misc{cryptoeprint:2009/117, 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{https://eprint.iacr.org/2009/117}}, url = {https://eprint.iacr.org/2009/117} }