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

Zhengbin Liu; Yongqiang Li; Lin Jiao; Mingsheng Wang

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

Abstract

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.

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published elsewhere. Minor revision. IEEE TIT
DOI: 10.1109/TIT.2020.3040543
Keywords: automatic search differential trail linear trail ARX HIGHT SPECK
Contact author(s): yongq lee @ gmail com
jiaolin_jl @ 126 com
History: 2020-11-30: revised; 2019-12-10: received; See all versions
Short URL: https://ia.cr/2019/1438
License: CC BY

BibTeX

@misc{cryptoeprint:2019/1438,
      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{https://eprint.iacr.org/2019/1438}},
      url = {https://eprint.iacr.org/2019/1438}
}