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 × n-bit permutations the complexity of the linear equivalence algorithm (LE) is O(n 32n). The affine equivalence algorithm (AE) has complexity O(n 322n). 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.
The work described in this paper has been supported in part by the Commission of the European Communities through the IST Programme under Contract IST-1999-12324 and by the Concerted Research Action (GOA) Mefisto.
F.W.O. Research Assistant, sponsored by the Fund for Scientific Research — Flanders (Belgium).
Chapter PDF
Similar content being viewed by others
Keywords
References
K. Aoki, T. Ichikawa, M. Kanda, M. Matsui, S. Moria, J. Nakajima, T. Tokita, Camellia: A 128-Bit Block Cipher Suitable for Multiple Platforms — Design and Analysis, submitted to NESSIE, 2000. Available at http://www.cryptonessie.org.
P.S.L.M. Baretto, V. Rijmen, The Khazad Legacy-Level Block Cipher, submitted to NESSIE, 2000. Available at http://www.cryptonessie.org.
P.S.L.M. Baretto, V. Rijmen, The Whirlpool Hashing Function, submitted to NESSIE, 2000. Available at http://www.cryptonessie.org.
E. Barkan, E. Biham, In how Many Ways Can You Write Rijndael, Proceedings of Asiacrypt 2002, LNCS, to appear. Earlier version at IACR eprint server, http://eprint.iacr.org/.
E. Barkan, E. Biham, The Book of Rijndaels, Available on IACR eprint server, http://eprint.iacr.org/.
E. Biham, R.J. Anderson, L.R. Knudsen, Serpent: A New Block Cipher Proposal, Proceedings of Fast Software Encryption’98, LNCS 1372, pp. 222–238, Springer-Verlag, 1998.
E. Biham, A. Shamir, Differential cryptanalysis of the Data Encryption Standard, Springer-Verlag 1993.
A. Biryukov, A. Shamir, Structural Cryptanalysis of SASAS, LNCS 2045, Proceedings of Eurocrypt 2001, pp. 394–405, Springer-Verlag, 2001.
A. Biryukov, D. Wagner, Advanced Slide Attacks, Proceedings of Fast Software Encryption 2000, LNCS 1807, pp. 589–606, Springer-Verlag, 2000.
N. Courtois, J. Pieprzyk, Cryptanalysis of Block Ciphers with Overdefined Systems of Equations, Proceedings of Asiacrypt’2002, LNCS, to appear. Earlier version at IACR eprint server, http://eprint.iacr.org/.
D. Coppersmith, S. Winograd, Matrix Multiplication via Arithmetic Progressions Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, pp. 1–6, 1987.
J. Daemen, Limitations of the Even-Mansour Construction, Proceedings of Asiacrypt’91, LNCS 739, pp. 495–499, Springer-Verlag, 1991.
J. Daemen, V. Rijmen, The Design of Rijndael, Springer-Verlag, 2002.
S. Even, Y. Mansour, A Construction of a Cipher from a Single Pseudorandom Permutation, Journal of Cryptology, Vol. 10, no. 3, pp. 151–161, Springer-Verlag, 1997.
J. Fuller, W. Millan, On linear Redundancy in the AES S-Box, Available online on http://eprint.iacr.org/, 2002.
M. A. Harrison, On the Classification of Boolean Functions by the General Linear and Affine Group, Journal of the Society for Industrial and Applied Mathematics, Vol. 12, pp. 284–299, 1964.
M.E. Hellman, R. Merkle, R. Schroppel, L. Washington, W. Diffie, S. Pohlig, P. Schweitzer, Results of an initial attempt to cryptanalyze the NBS Data Encryption Standard. Technical report, Stanford University, U.S.A., September 1976.
K. Kim, S. Lee, S. Park, D. Lee, Securing DES S-boxes Against Three Robust Cryptanalysis, Proceedings of SAC’95, pp. 145–157, 1995.
C.S. Lorens, Invertible Boolean Functions, Space General Corporation Report, 1962.
M. Matsui, Linear Cryptanalysis Method for DES Cipher, Proceedings of Eurocrypt’93, LNCS 765, pp. 386–397, Springer-Verlag, 1993.
M. Matsui, New Block Encryption Algorithm MISTY, Proceedings of Fast Software Encryption’ 97, LNCS 1267, pp. 54–68, Springer-Verlag, 1997.
S. Murphy, J.B. Robshaw, Essential Algebraic Structure Within the AES, Proceedings of CRYPTO 2002, LNCS 2442, pp. 17–38, Springer-Verlag 2002.
J. Patarin, L. Goubin, N. Courtois, Improved Algorithms for Isomorphisms of Polynomials, Proceedings of Eurocrypt’98, LNCS 1403, pp. 184–200, Springer-Verlag, 1998.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2003 International Association for Cryptologic Research
About this paper
Cite this paper
Biryukov, A., De Cannière, C., Braeken, A., Preneel, B. (2003). A Toolbox for Cryptanalysis: Linear and Affine Equivalence Algorithms. In: Biham, E. (eds) Advances in Cryptology — EUROCRYPT 2003. EUROCRYPT 2003. Lecture Notes in Computer Science, vol 2656. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-39200-9_3
Download citation
DOI: https://doi.org/10.1007/3-540-39200-9_3
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-14039-9
Online ISBN: 978-3-540-39200-2
eBook Packages: Springer Book Archive