Lecture Notes in Computer Science vol:2656 pages:33-50
EUROCRYPT 2003 date:May 04-08, 2003
This paper presents two algorithms for solving the linear and the affine equivalence problem for arbitrary permutations (S-boxes). For a pair of n x n-bit permutations the complexity of the linear equivalence algorithm (LE) is O(n(3)2(n)). The affine equivalence algorithm (AE) has complexity O(n(3)2(2n)). The algorithms are efficient and allow to study linear and affine equivalences for bijective S-boxes of all popular sizes (LE is efficient up to n less than or equal to 32). Using these tools new equivalent representations are found for a variety of ciphers: Rijndael, DES, Camellia, Serpent, Misty, Kasumi, Khazad, etc. The algorithms are furthermore extended for the case of non-bijective n to m-bit S-boxes with a small value of \n - m\ and for the case of almost equivalent S-boxes. The algorithms also provide new attacks on a generalized Even-Mansour scheme. Finally, the paper defines a new problem of S-box decomposition in terms of Substitution Permutations Networks (SPN) with layers of smaller S-boxes. Simple information-theoretic bounds are proved for such decompositions.