Skip to main content

2003 | OriginalPaper | Buchkapitel

A Toolbox for Cryptanalysis: Linear and Affine Equivalence Algorithms

verfasst von : Alex Biryukov, Christophe De Cannière, An Braeken, Bart Preneel

Erschienen in: Advances in Cryptology — EUROCRYPT 2003

Verlag: Springer Berlin Heidelberg

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

This paper presents two algorithms for solving the linear and the affine equivalence problem for arbitrary permutations (S-boxes). For a pair of n × n-bit permutations the complexity of the linear equivalence algorithm (LE) is O(n32n). The affine equivalence algorithm (AE) has complexity O(n322n). 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 ≤ 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.

Metadaten
Titel
A Toolbox for Cryptanalysis: Linear and Affine Equivalence Algorithms
verfasst von
Alex Biryukov
Christophe De Cannière
An Braeken
Bart Preneel
Copyright-Jahr
2003
Verlag
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/3-540-39200-9_3

Premium Partner