Paper 2017/994

Separable Statistics and Multidimensional Linear Cryptanalysis

S. Fauskanger and I. Semaev

Abstract

Multidimensional linear cryptanalysis of block ciphers is improved in this work by introducing a number of new ideas. Firstly, formulae is given to compute approximate multidimensional distributions of encryption internal bits. Conventional statistics like LLR(Logarithmic Likelihood Ratio) do not fit to work in Matsui's Algorithm 2 for large dimension data, as the observation depend on too many cipher key bits. So, secondly, a new statistic which reflects the structure of the cipher round is constructed instead. Thirdly, computing the statistic values which fall into a critical region is presented as an optimisation problem for which an efficient algorithm is suggested. The algorithm works much faster than brute forcing all relevant key bits to compute the statistic. An attack for 16-round DES was implemented. We got an improvement over Matsui's attack on DES in data and time complexity keeping success probability the same.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
block ciphersmultidimensional linear cryptanalysisseparable statisticsDES
Contact author(s)
igor @ ii uib no
History
2017-10-11: received
Short URL
https://ia.cr/2017/994
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/994,
      author = {S.  Fauskanger and I.  Semaev},
      title = {Separable Statistics and Multidimensional Linear Cryptanalysis},
      howpublished = {Cryptology ePrint Archive, Paper 2017/994},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/994}},
      url = {https://eprint.iacr.org/2017/994}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.