Paper 2016/667

Multivariate Profiling of Hulls for Linear Cryptanalysis

Andrey Bogdanov, Elmar Tischhauser, and Philip S. Vejre


Extensions of linear cryptanalysis making use of multiple approximations, such as multiple and 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 extended by Blondeau and Nyberg to also cover an updated wrong key randomization hypothesis, using similar assumptions. However, a recent result by Nyberg shows the equivalence of linear dependence and statistical dependence of linear approximations, which essentially invalidates a crucial assumption on which all these multidimensional models are based. In this paper, we develop a model for linear cryptanalysis using multiple linearly independent approximations which takes key-dependence into account and complies with Nyberg's result. Our model considers an arbitrary multivariate joint distribution of the correlations, and in particular avoids any assumptions regarding normality. The analysis of this distribution is then tailored to concrete ciphers in a practically feasible way by combining a signal/noise decomposition approach for the linear hulls with a profiling of the actual multivariate distribution of the signal correlations for a large number of keys, thereby entirely avoiding assumptions regarding the shape of this distribution. As an application of our model, we provide an attack on 26 rounds of PRESENT which is faster and requires less data than previous attacks, while using more realistic assumptions and far fewer approximations. We successfully extend the attack to present the first 27-round attack which takes key-dependence into account.

Note: Major changes and updates to contents.

Available format(s)
Publication info
Published by the IACR in FSE 2018
linear cryptanalysismultivariatemultidimensional cryptanalysiskey dependencePRESENTkey recoverydiscriminant analysisstatistical attack
Contact author(s)
psve @ dtu dk
2018-02-23: last of 3 revisions
2016-07-01: received
See all versions
Short URL
Creative Commons Attribution


      author = {Andrey Bogdanov and Elmar Tischhauser and Philip S.  Vejre},
      title = {Multivariate Profiling of Hulls for Linear Cryptanalysis},
      howpublished = {Cryptology ePrint Archive, Paper 2016/667},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.