A New Method for Searching Optimal Differential and Linear Trails in ARX Ciphers
A New Method for Searching Optimal Differential and Linear Trails in ARX Ciphers
复制标题
DOI：
10.1109/tit.2020.3040543
复制
发表时间：
2021-02
影响因子：
2.5
通讯作者：
Zhengbin Liu;Yongqiang Li;Lin Jiao;Mingsheng Wang
中科院分区：
文献类型：
--
作者：
Zhengbin Liu;Yongqiang Li;Lin Jiao;Mingsheng Wang
在本文中，我们提出了一个自动工具来搜索最佳的差分和线性的ARX密码的痕迹。结果表明，模加法运算可以分解为一系列带有进位的小模加法运算，从而将ARX密码转化为类S盒密码。基于此，我们引入了进位相关差分分布表（CDDT）和进位相关线性近似表（CLAT）的概念。在此基础上，我们给出了一种有效的方法来跟踪一个大模加法的所有可能的输出差和线性掩码，同时返回它们的差分概率和线性相关。然后介绍了一种改进的Matsui算法，该算法可以在ARX密码中找到最优的差分和线性路径。此外，我们的工具的效力的优越性也证实了圆形减少版本的HIGHT和SPECK的实验结果。更具体地说，我们找到了最佳的差分轨迹高达10轮的高，首次报道。我们还找到了SPECK 32/48/64/96/128的10、12、16、8和8轮的最优差分试验，并首次报道了SPECK 48和SPECK 64的可证明的最优差分试验。首次发现了最多可达9轮HIHT的最优线性轨迹，并分别找到了SPECK 32/48/64/96/128的22、13、15、9和9轮的最优线性轨迹。这些结果评估的安全性，对差分和线性密码分析的HIGHT和SPECK。此外，我们的工具是有用的，以估计的安全性在设计的ARX密码。
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.