Paper 2019/1438

A new method for Searching Optimal Differential and Linear Trails in ARX Ciphers

Zhengbin Liu, Yongqiang Li, Lin Jiao, and Mingsheng Wang


In this paper, we propose an automatic tool to search for optimal differential and linear trails in ARX ciphers. It's shown that a modulo addition can be divided into sequential small modulo additions with carry bit, which turns an ARX cipher into an S-box-like cipher. From this insight, we introduce the concepts of carry-bit-dependent difference distribution table (CDDT) and carry-bit-dependent linear approximation table (CLAT). Based on them, we give efficient methods to trace all possible output differences and linear masks of a big modulo addition, with returning their differential probabilities and linear correlations simultaneously. Then an adapted Matsui's algorithm is introduced, which can find the optimal differential and linear trails in ARX ciphers. Besides, the superiority of our tool's potency is also confirmed by experimental results for round-reduced versions of HIGHT and SPECK. More specifically, we find the optimal differential trails for up to 10 rounds of HIGHT, reported for the first time. We also find the optimal differential trails for 10, 12, 16, 8 and 8 rounds of SPECK32/48/64/96/128, and report the provably optimal differential trails for SPECK48 and SPECK64 for the first time. The optimal linear trails for up to 9 rounds of HIGHT are reported for the first time, and the optimal linear trails for 22, 13, 15, 9 and 9 rounds of SPECK32/48/64/96/128 are also found respectively. These results evaluate the security of HIGHT and SPECK against differential and linear cryptanalysis. Also, our tool is useful to estimate the security in the design of ARX ciphers.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Minor revision.IEEE TIT
automatic searchdifferential traillinear trailARXHIGHTSPECK
Contact author(s)
yongq lee @ gmail com
jiaolin_jl @ 126 com
2020-11-30: revised
2019-12-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Zhengbin Liu and Yongqiang Li and Lin Jiao and Mingsheng Wang},
      title = {A new method for Searching Optimal Differential and Linear Trails in ARX Ciphers},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1438},
      year = {2019},
      doi = {10.1109/TIT.2020.3040543},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.