The Security of SIMON-like Ciphers Against Linear Cryptanalysis

In the present paper, we analyze the security of SIMON-like ciphers against linear cryptanalysis. First, an upper bound is derived on the squared correlation of SIMON-like round function. It is shown that the upper bound on the squared correlation of SIMON-like round function decreases with the Hamming weight of output mask increasing. Based on this, we derive an upper bound on the squared correlation of linear trails for SIMON and SIMECK, which is $2^{-2R+2}$ for any $R$-round linear trail. We also extend this upper bound to SIMON-like ciphers. Meanwhile, an automatic search algorithm is proposed, which can find the optimal linear trails in SIMON-like ciphers under the Markov assumption. With the proposed algorithm, we find the provably optimal linear trails for $12$, $16$, $19$, $28$ and $37$ rounds of SIMON$32/48/64/96/128$. To the best of our knowledge, it is the first time that the provably optimal linear trails for SIMON$64$, SIMON$96$ and SIMON$128$ are reported. The provably optimal linear trails for $13$, $19$ and $25$ rounds of SIMECK$32/48/64$ are also found respectively. Besides the optimal linear trails, we also find the $23$, $31$ and $41$-round linear hulls for SIMON$64/96/128$, and $13$, $21$ and $27$-round linear hulls for SIMECK$32/48/64$. As far as we know, these are the best linear hull distinguishers for SIMON and SIMECK so far. Compared with the approach based on SAT/SMT solvers in \cite{KolblLT15}, our search algorithm is more efficient and practical to evaluate the security against linear cryptanalysis in the design of SIMON-like ciphers