Strengthening differential and linear attacks using virtual isomorphisms

Abstract

The ciphers y = C (x, k) and y = C(x, k) are isomorphic if there is a computable in both directions map y ↔ y, x ↔ x, k ↔ k. The cipher is vulnerable to an attack if the isomorphic cipher is vulnerable to it. If φ is a substitution and T is an encryption operator, then T = φT φ 1 is a cipher isomorphism. For cryptanalysis it is reasonable to choose substitution φ in such a way that it has a lot of fixed points. It is shown that byte substitution φ can have no more than 130 fixed points. Isomorphic AES (IAES) is proposed where the only non-linear operation is an isomorphic image of the XOR operation. On average, maximum probabilities of IAES differentials are 8.5 times higher in comparison with the original whereas dominance of the linear sum is increased by 3 times. IAES has differentials with zero output difference and probability 1, which slows down replication of active non-linearities and decreases complexity of an attack. Presumably, resistance of AES to linear and differential attacks can be twice reduced by magnitude in comparison with the generally accepted estimates.