Multidimensional linear cryptanalysis

 |  Login

Show simple item record

dc.contributor Aalto-yliopisto fi
dc.contributor Aalto University en Hermelin, Miia 2012-08-24T11:29:04Z 2012-08-24T11:29:04Z 2010
dc.identifier.isbn 978-952-60-3190-3 (electronic)
dc.identifier.isbn 978-952-60-3189-7 (printed) #8195;
dc.identifier.issn 1797-5069
dc.description.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. en
dc.format.extent Verkkokirja (658 KB, 94 s.)
dc.format.mimetype application/pdf
dc.language.iso en en
dc.publisher Aalto-yliopiston teknillinen korkeakoulu en
dc.relation.ispartofseries TKK dissertations in information and computer science, 16 en
dc.relation.haspart [Publication 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. en
dc.relation.haspart [Publication 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. en
dc.relation.haspart [Publication 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. en
dc.relation.haspart [Publication 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. en
dc.relation.haspart [Publication 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. en
dc.relation.haspart [Publication 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. en
dc.relation.haspart [Publication 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. en
dc.subject.other Mathematics
dc.title Multidimensional linear cryptanalysis en
dc.type G5 Artikkeliväitöskirja fi Aalto-yliopiston teknillinen korkeakoulu fi
dc.contributor.department Tietojenkäsittelytieteen laitos fi
dc.contributor.department Department of Information and Computer Science en
dc.subject.keyword multidimensional cryptanalysis en
dc.subject.keyword Matsui's algorithm en
dc.subject.keyword linear cryptanalysis en
dc.subject.keyword block cipher en
dc.subject.keyword stream cipher en
dc.identifier.urn URN:ISBN:978-952-60-3190-3
dc.type.dcmitype text en
dc.type.ontasot Väitöskirja (artikkeli) fi
dc.type.ontasot Doctoral dissertation (article-based) en
dc.contributor.supervisor Nyberg, Kaisa, Prof.

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search archive

Advanced Search

article-iconSubmit a publication


My Account