Multivariate Profiling of Hulls for Linear Cryptanalysis

Authors

  • Andrey Bogdanov Technical University of Denmark, Kongens Lyngby, Denmark
  • Elmar Tischhauser Technical University of Denmark, Kongens Lyngby, Denmark
  • Philip S. Vejre Technical University of Denmark, Kongens Lyngby, Denmark

DOI:

https://doi.org/10.13154/tosc.v2018.i1.101-125

Keywords:

linear cryptanalysis, multivariate, multidimensional cryptanalysis, key-dependence, PRESENT, key recovery, statistical attack

Abstract

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.

Published

2018-03-01

Issue

Section

Articles

How to Cite

Multivariate Profiling of Hulls for Linear Cryptanalysis. (2018). IACR Transactions on Symmetric Cryptology, 2018(1), 101-125. https://doi.org/10.13154/tosc.v2018.i1.101-125