Title: A Toolbox for Cryptanalysis: Linear and Affine Equivalence Algorithms
Authors: Biryukov, Alex ×
De Cannière, Christophe
Braeken, An
Preneel, Bart #
Issue Date: 2003
Publisher: Springer
Series Title: Lecture Notes in Computer Science vol:2656 pages:33-50
Conference: EUROCRYPT 2003 date:May 04-08, 2003
Abstract: 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.
ISSN: 0302-9743
Publication status: published
KU Leuven publication type: IT
Appears in Collections:ESAT - STADIUS, Stadius Centre for Dynamical Systems, Signal Processing and Data Analytics
Electrical Engineering - miscellaneous
× corresponding author
# (joint) last author

Files in This Item:
File Status SizeFormat
article-16.pdf Published 231KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science