×

A toolbox for cryptanalysis: Linear and affine equivalence algorithms. (English) Zbl 1038.94521

Biham, Eli (ed.), Advances in cryptology – EUROCRYPT 2003. International conference on the theory and applications of cryptographic techniques, Warsaw, Poland, May 4–8, 2003. Proceedings. Berlin: Springer (ISBN 3-540-14039-5/pbk). Lect. Notes Comput. Sci. 2656, 33-50 (2003).
Summary: This paper presents two algorithms for solving the linear and the affine equivalence problem for arbitrary permutations (S-boxes). For a pair of \(n\times 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 one to study linear and affine equivalences for bijective S-boxes of all popular sizes (LE is efficient up to \(n \leq 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 nonbijective \(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 with layers of smaller S-boxes. Simple information-theoretic bounds are proved for such decompositions.
For the entire collection see [Zbl 1020.00023].

MSC:

94A60 Cryptography
68P25 Data encryption (aspects in computer science)
94A17 Measures of information, entropy
PDFBibTeX XMLCite
Full Text: Link