Improved Linear Cryptanalysis of reduced-round SIMON-32 and SIMON-48

Mohamed Ahmed Abdelraheem; Javad Alizadeh; Hoda A.  Alkhzaimi; Mohammad Reza Aref; Nasour Bagheri; Praveen Gauravaram

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2015/988

Improved Linear Cryptanalysis of reduced-round SIMON-32 and SIMON-48

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

Abstract

In this paper we analyse two variants of SIMON family of light-weight block ciphers against linear cryptanalysis and present the best linear cryptanalytic results on these variants of reduced-round SIMON to date. We propose a time-memory trade-off method that finds differential/linear trails for any permutation allowing low Hamming weight differential/linear trails. Our method combines low Hamming weight trails found by the correlation matrix representing the target permutation with heavy Hamming weight trails found using a Mixed Integer Programming model representing the target differential/linear trail. Our method enables us to find a 17-round linear approximation for SIMON-48 which is the best current linear approximation for SIMON-48. Using only the correlation matrix method, we are able to find a 14-round linear approximation for SIMON-32 which is also the current best linear approximation for SIMON-32. The presented linear approximations allow us to mount a 23-round key recovery attack on SIMON-32 and a 24-round Key recovery attack on SIMON-48/96 which are the current best results on SIMON-32 and SIMON-48. In addition we have an attack on 24 rounds of SIMON-32 with marginal complexity.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published elsewhere. Minor revision. Indocrypt 2015
Keywords: SIMON linear cryptanalysis linear hull correlation matrix Mixed Integer Programming (MIP)
Contact author(s): mohamed abdelraheem @ sics se
History: 2015-10-13: received
Short URL: https://ia.cr/2015/988
License: CC BY

BibTeX

@misc{cryptoeprint:2015/988,
      author = {Mohamed Ahmed Abdelraheem and Javad Alizadeh and Hoda A.  Alkhzaimi and Mohammad Reza Aref and Nasour Bagheri and Praveen Gauravaram},
      title = {Improved Linear Cryptanalysis of reduced-round SIMON-32 and SIMON-48},
      howpublished = {Cryptology ePrint Archive, Paper 2015/988},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/988}},
      url = {https://eprint.iacr.org/2015/988}
}