Separable Statistics and Multidimensional Linear Cryptanalysis

S.  Fauskanger; I.  Semaev

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 ciphers multidimensional linear cryptanalysis separable statistics DES
Contact author(s): igor @ ii uib no
History: 2017-10-11: received
Short URL: https://ia.cr/2017/994
License: 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},
      url = {https://eprint.iacr.org/2017/994}
}