Paper 2014/681

Improved Linear Cryptanalysis of Round Reduced SIMON

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

Abstract

SIMON is a family of ten lightweight block ciphers published by Beaulieu et al. from U.S. National Security Agency (NSA). A cipher in this family with $K$-bit key and $N$-bit block is called SIMON ${N}/{K}$. In this paper we investigate the security of SIMON against different variants of linear cryptanalysis, i.e., classic linear, multiple linear and linear hull attacks. We present a connection between linear characteristic and differential characteristic, multiple linear and differential and linear hull and differential, and employ it to adapt the current known results on differential cryptanalysis of SIMON to linear cryptanalysis of this block cipher. Our best linear cryptanalysis covers SIMON 32/64 reduced to 20 rounds out of 32 rounds with the data complexity $2^{31.69}$ and time complexity $2^{59.69}$. We have implemented our attacks for small scale variants of SIMON and our experiments confirm the theoretical bias presented in this work. So far, our results are the best known with respect to linear cryptanalysis for any variant of SIMON.