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.
Category / Keywords: secret-key cryptography / SIMON, linear cryptanalysis, linear hull, correlation matrix, Mixed Integer Programming (MIP) Original Publication (with minor differences): Indocrypt 2015 Date: received 12 Oct 2015 Contact author: mohamed abdelraheem at sics se Available format(s): PDF | BibTeX Citation Version: 20151013:194159 (All versions of this report) Short URL: ia.cr/2015/988 Discussion forum: Show discussion | Start new discussion