Paper 2017/178

Optimal Differential Trails in SIMON-like Ciphers

Zhengbin Liu, Yongqiang Li, and Mingsheng Wang

Abstract

In the present paper, we propose an automatic search algorithm for optimal differential trails in SIMON-like ciphers. First, we give a more accurate upper bound on the differential probability of SIMON-like round function. It is shown that when the Hamming weight of the input difference $\alpha$, which is denoted by $wt(\alpha )$, is less than one half of the input size, the corresponding maximum differential probability of SIMON-like round function is less than or equal to $2^{-wt(\alpha )-1}$. Based on this, we adapt Matsui's algorithm and propose an efficient algorithm for searching for optimal differential trails. With the proposed algorithm, we find the provably optimal differential 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 differential trails for SIMON$64$, SIMON$$ and SIMON$$ are reported. The provably optimal differential trails for $$, $$ and $$ rounds of SIMECK$$ are also found respectively, which confirm the results given by K$$lbl et al. \cite{KolblR15}. Besides the optimal differential trails, we also find the $$, $$, $$, $$ and $$-round differentials for SIMON$$, and $$, $$ and $$-round differentials for SIMECK$$, respectively. As far as we know, these are the best differential distinguishers for SIMON and SIMECK so far. Compared with the approach based on SAT/SMT solvers used by K$$lbl et al., our algorithm is more efficient and more practical to evaluate the security against differential cryptanalysis in the design of SIMON-like ciphers.