Paper 2014/973 Original: eprint.iacr.org/2014/973 ↗

Improved Linear (hull) Cryptanalysis of Round-reduced Versions of SIMON

Abstract

SIMON is a family of lightweight block ciphers designed by the U.S. National Security Agency (NSA) that has attracted much attention since its publication in 2013. In this paper, we thoroughly investigate the properties of linear approximations of the bitwise AND operation with dependent input bits. By using a Mixed-integer Linear Programming based technique presented in Aasicrypt 2014 for automatic search for characteristics, we obtain improved linear characteristics for several versions of the SIMON family. Moreover, by employing a recently published method for automatic enumeration of differential and linear characteristics by Sun et. al., we present an improved linear hull analysis of some versions of the SIMON family, which are the best results for linear cryptanalysis of SIMON published so far. Specifically, for SIMON$128$, where the number denotes the block length, a 34-round linear characteristic with correlation $2^{-61}$ is found, which is the longest linear characteristic that can be used in a key-recovery attack for SIMON$128$ published so far. Besides, several linear hulls superior to the best ones known previously are presented as follows: linear hulls for the 13-round SIMON$32$ with potential $2^{-28.99}$ versus previous $2^{-31.69}$, for the 15-round SIMON$48$ with potential $2^{-42.28}$ versus previous $2^{-44.11}$ and linear hulls for the 21-round SIMON$64$ with potential $2^{-60.72}$ versus previous $2^{-62.53}$.