Multidimensional linear cryptanalysis

dc.contributorAalto-yliopistofi
dc.contributorAalto Universityen
dc.contributor.authorHermelin, Miia
dc.contributor.departmentTietojenkäsittelytieteen laitosfi
dc.contributor.departmentDepartment of Information and Computer Scienceen
dc.contributor.schoolAalto-yliopiston teknillinen korkeakoulufi
dc.contributor.supervisorNyberg, Kaisa, Prof.
dc.date.accessioned2012-08-24T11:29:04Z
dc.date.available2012-08-24T11:29:04Z
dc.date.issued2010
dc.description.abstractLinear 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.extentVerkkokirja (658 KB, 94 s.)
dc.format.mimetypeapplication/pdf
dc.identifier.isbn978-952-60-3190-3 (electronic)
dc.identifier.isbn978-952-60-3189-7 (printed)#8195;
dc.identifier.issn1797-5069
dc.identifier.urihttps://aaltodoc.aalto.fi/handle/123456789/4802
dc.identifier.urnURN:ISBN:978-952-60-3190-3
dc.language.isoenen
dc.publisherAalto-yliopiston teknillinen korkeakouluen
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.relation.ispartofseriesTKK dissertations in information and computer science, 16en
dc.subject.keywordmultidimensional cryptanalysisen
dc.subject.keywordMatsui's algorithmen
dc.subject.keywordlinear cryptanalysisen
dc.subject.keywordblock cipheren
dc.subject.keywordstream cipheren
dc.subject.otherMathematics
dc.titleMultidimensional linear cryptanalysisen
dc.typeG5 Artikkeliväitöskirjafi
dc.type.dcmitypetexten
dc.type.ontasotVäitöskirja (artikkeli)fi
dc.type.ontasotDoctoral dissertation (article-based)en
local.aalto.digiauthask
local.aalto.digifolderAalto_65272
Files
Original bundle
Now showing 1 - 8 of 8
No Thumbnail Available
Name:
isbn9789526031903.pdf
Size:
642.84 KB
Format:
Adobe Portable Document Format
No Thumbnail Available
Name:
publication1.pdf
Size:
83 KB
Format:
Adobe Portable Document Format
No Thumbnail Available
Name:
publication2.pdf
Size:
102 KB
Format:
Adobe Portable Document Format
No Thumbnail Available
Name:
publication3.pdf
Size:
257.94 KB
Format:
Adobe Portable Document Format
No Thumbnail Available
Name:
publication4.pdf
Size:
406.71 KB
Format:
Adobe Portable Document Format
No Thumbnail Available
Name:
publication5.pdf
Size:
186.77 KB
Format:
Adobe Portable Document Format
No Thumbnail Available
Name:
publication6.pdf
Size:
319.29 KB
Format:
Adobe Portable Document Format
No Thumbnail Available
Name:
publication7.pdf
Size:
334.59 KB
Format:
Adobe Portable Document Format