Paper 2014/681

Improved Linear Cryptanalysis of Reduced-round SIMON

Mohamed Ahmed Abdelraheem, Javad Alizadeh, Hoda A. Alkhzaimi, Mohammad Reza Aref, Nasour Bagheri, Praveen Gauravaram, and Martin M. Lauridsen


SIMON is a family of ten lightweight block ciphers published by Beaulieu et al.\ from U.S. National Security Agency (NSA). In this paper we investigate the security of SIMON against different variants of linear cryptanalysis techniques, i.e.\ classical and multiple linear cryptanalysis and linear hulls. We present a connection between linear- and differential characteristics as well as differentials and linear hulls in SIMON. We employ it to adapt the current known results on differential cryptanalysis of SIMON into the linear setting. In addition to finding a linear approximation with a single characteristic, we show the effect of the linear hulls in SIMON by finding better approximations that enable us to improve the previous results. Our best linear cryptanalysis employs average squared correlation of the linear hull of SIMON based on correlation matrices. The result covers 21 out of 32 rounds of SIMON32/64 with time and data complexity $2^{54.56}$ and $2^{30.56}$ respectively. We have implemented our attacks for small scale variants of SIMON and our experiments confirm the theoretical biases and correlation presented in this work. So far, our results are the best known with respect to linear cryptanalysis for any variant of SIMON.

Available format(s)
Publication info
Preprint. MINOR revision.
SIMONlinear cryptanalysismultiple linear cryptanalysislinear hullcorrelation matrixbranch and bound
Contact author(s)
na bagheri @ gmail com
2014-12-02: last of 3 revisions
2014-08-31: received
See all versions
Short URL
Creative Commons Attribution


      author = {Mohamed Ahmed Abdelraheem and Javad Alizadeh and Hoda A.  Alkhzaimi and Mohammad Reza Aref and Nasour Bagheri and Praveen Gauravaram and Martin M.  Lauridsen},
      title = {Improved Linear Cryptanalysis of Reduced-round SIMON},
      howpublished = {Cryptology ePrint Archive, Paper 2014/681},
      year = {2014},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.