The doctoral dissertations of the former Helsinki University of Technology (TKK) and Aalto University Schools of Technology (CHEM, ELEC, ENG, SCI) published in electronic format are available in the electronic publications archive of Aalto University - Aaltodoc.
Aalto

Multidimensional Linear Cryptanalysis

Miia Hermelin

Doctoral dissertation for the degree of Doctor of Science in Technology to be presented with due permission of the Faculty of Information and Natural Sciences for public examination and debate in Auditorium T2 at the Aalto University School of Science and Technology (Espoo, Finland) on the 11th of June 2010 at 12 noon.

Overview in PDF format (ISBN 978-952-60-3190-3)   [658 KB]
Dissertation is also available in print (ISBN 978-952-60-3189-7)

Abstract

Linear cryptanalysis is an important tool for studying the security of symmetric ciphers. In 1993 Matsui proposed two algorithms, called Algorithm 1 and Algorithm 2, for recovering information about the secret key of a block cipher. The algorithms exploit a biased probabilistic relation between the input and output of the cipher. This relation is called the (one-dimensional) linear approximation of the cipher. Mathematically, the problem of key recovery is a binary hypothesis testing problem that can be solved with appropriate statistical tools.

The same mathematical tools can be used for realising a distinguishing attack against a stream cipher. The distinguisher outputs whether the given sequence of keystream bits is derived from a cipher or a random source. Sometimes, it is even possible to recover a part of the initial state of the LFSR used in a key stream generator.

Several authors considered using many one-dimensional linear approximations simultaneously in a key recovery attack and various solutions have been proposed. In this thesis a unified methodology for using multiple linear approximations in distinguishing and key recovery attacks is presented. This methodology, which we call multidimensional linear cryptanalysis, allows removing unnecessary and restrictive assumptions. We model the key recovery problems mathematically as hypothesis testing problems and show how to use standard statistical tools for solving them. We also show how the data complexity of linear cryptanalysis on stream ciphers and block ciphers can be reduced by using multiple approximations.

We use well-known mathematical theory for comparing different statistical methods for solving the key recovery problems. We also test the theory in practice with reduced round Serpent. Based on our results, we give recommendations on how multidimensional linear cryptanalysis should be used.

This thesis consists of an overview and of the following 7 publications:

  1. Kaisa Nyberg and Miia Hermelin. 2007. Multidimensional Walsh transform and a characterization of Bent functions. In: P. Vijay Kumar, Tor Helleseth, and Øyvind Ytrehus (editors). Proceedings of the 2007 IEEE Information Theory Workshop on Information Theory for Wireless Networks (ITW 2007). Bergen, Norway. 1-6 July 2007. Pages 83-86. © 2007 Institute of Electrical and Electronics Engineers (IEEE). By permission.
  2. Miia Hermelin and Kaisa Nyberg. 2008. Multidimensional linear distinguishing attacks and Boolean functions. In: Jean-Francis Michon, Pierre Valarcher, and Jean-Baptiste Yunès (editors). Preproceedings of the Fourth International Workshop on Boolean Functions: Cryptography and Applications (BFCA 2008). Copenhagen, Denmark. 19-21 May 2008. Publications des Universités de Rouen et du Havre. © 2008 by authors.
  3. Miia Hermelin, Joo Yeon Cho, and Kaisa Nyberg. 2008. Multidimensional linear cryptanalysis of reduced round Serpent. In: Yi Mu, Willy Susilo, and Jennifer Seberry (editors). Proceedings of the 13th Australasian Conference on Information Security and Privacy (ACISP 2008). Wollongong, Australia. 7-9 July 2008. Berlin, Heidelberg, Germany. Springer. Lecture Notes in Computer Science, volume 5107, pages 203-215. ISBN 978-3-540-69971-2. © 2008 Springer Science+Business Media. By permission.
  4. Miia Hermelin, Joo Yeon Cho, and Kaisa Nyberg. 2009. Multidimensional extension of Matsui's Algorithm 2. In: Orr Dunkelman (editor). Revised Selected Papers of the 16th International Workshop on Fast Software Encryption (FSE 2009). Leuven, Belgium. 22-25 February 2009. Springer. Lecture Notes in Computer Science, volume 5665, pages 209-227. ISBN 978-3-642-03316-2. © 2009 International Association for Cryptologic Research (IACR). By permission.
  5. Miia Hermelin, Joo Yeon Cho, and Kaisa Nyberg. 2009. Statistical tests for key recovery using multidimensional extension of Matsui's Algorithm 1. In: Postersession of the 28th Annual International Conference on the Theory and Applications of Cryptographic Techniques (Eurocrypt 2009). Cologne, Germany. 26-30 April 2009. Also appeared in Helena Handschuh, Stefan Lucks, Bart Preneel, and Phillip Rogaway (editors). Symmetric Cryptography. Dagstuhl Seminar 09031. Dagstuhl, Germany. 11-16 January 2009. Dagstuhl Seminar Proceedings, number 09031. © 2009 by authors.
  6. Joo Yeon Cho and Miia Hermelin. 2010. Improved linear cryptanalysis of SOSEMANUK. In: Donghoon Lee and Seokhie Hong (editors). Revised Selected Papers of the 12th International Conference on Information Security and Cryptology (ICISC 2009). Seoul, Korea. 2-4 December 2009. Berlin, Heidelberg, Germany. Springer. Lecture Notes in Computer Science, volume 5984, pages 101-117. ISBN 978-3-642-14422-6. © 2010 Springer Science+Business Media. By permission.
  7. Miia Hermelin and Kaisa Nyberg. 2010. Dependent linear approximations: The algorithm of Biryukov and others revisited. In: Josef Pieprzyk (editor). Topics in Cryptology. Proceedings of the Cryptographers' Track at the RSA Conference 2010 (CT-RSA 2010). San Francisco, California, USA. 1-5 March 2010. Berlin, Heidelberg, Germany. Springer. Lecture Notes in Computer Science, volume 5985, pages 318-333. ISBN 978-3-642-11924-8. © 2010 Springer Science+Business Media. By permission.

Keywords: multidimensional cryptanalysis, Matsui's algorithm, linear cryptanalysis, block cipher, stream cipher

This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.

© 2010 Aalto University School of Science and Technology

Last update 2011-05-26