You are looking at a specific version 20160705:125337 of this paper. See the latest version.

Paper 2016/667

Multivariate Linear Cryptanalysis: The Past and Future of PRESENT

Andrey Bogdanov and Elmar Tischhauser and Philip S. Vejre

Abstract

Extensions of linear cryptanalysis making use of multiple approximations such as multidimensional linear cryptanalysis are an important tool in symmetric-key cryptanalysis, among others being responsible for the best known attacks on ciphers such as Serpent and PRESENT. At CRYPTO 2015, Huang et al. provided a refined analysis of the key-dependent capacity leading to a refined key equivalence hypothesis, however at the cost of additional assumptions. Their analysis was recently extended by Blondeau and Nyberg to also cover an updated wrong key randomization hypothesis, using similar assumptions. As a consequence, the effectiveness of multidimensional linear attacks seems significantly reduced, e.g. to only 24 rounds for PRESENT. It is therefore an important open problem how to take key dependent behaviour for both right and wrong keys into account without introducing other limiting assumptions in the process. In this paper, we address this issue by proposing multivariate linear cryptanalysis as a new technique for using multiple linear approximations. Based on multivariate statistics and featuring a novel distinguishing technique based on quadratic discriminant analysis, it allows more realistic modelling of key dependence, while not relying on the limiting assumptions of previous work. Furthermore, it comes with a flexible signal/noise decomposition approach to allow for a realistic estimation of correlations. As an application of multivariate linear cryptanalysis, we provide attacks on 26 and 27 rounds (the latter marginally faster than exhaustive search) of PRESENT under much more realistic assumptions than previous work.

Note: Added acknowledgements and fixed minor typos.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
linear cryptanalysismultivariatemultidimensional cryptanalysiskey variancePRESENTkey recoverydiscriminant analysisstatistical attack
Contact author(s)
psve @ dtu dk
History
2018-02-23: last of 3 revisions
2016-07-01: received
See all versions
Short URL
https://ia.cr/2016/667
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.