# [Resource Topic] 2009/117: Changing probabilities of differentials and linear sums via isomorphisms of ciphers

Welcome to the resource topic for 2009/117

Title:
Changing probabilities of differentials and linear sums via isomorphisms of ciphers

Authors: 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.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.