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$96$ and SIMON$128$ are reported. The provably optimal differential trails for $13$, $19$ and $25$ rounds of SIMECK$32/48/64$ are also found respectively, which confirm the results given by K$\ddot{o}$lbl et al. \cite{KolblR15}. Besides the optimal differential trails, we also find the $14$, $17$, $23$, $31$ and $41$-round differentials for SIMON$32/48/64/96/128$, and $14$, $21$ and $27$-round differentials for SIMECK$32/48/64$, 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$\ddot{o}$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.