基于ARX结构的轻量密码算法的密码分析研究

A broad class of lightweight cryptographic algorithms are designed by employing a combination of modular addition, bit rotation and XOR, and these algorithms are called ARX ciphers. The advantage of these designs is that they are very simple, efficient and easy to implement in software or in hardware.. Although ARX ciphers have many advantages, there is still no rigorous understanding of the security of ARX ciphers. By introuducing correlated differential distrubution tables and linear approximation tables, we will systematically investigate the security of ARX ciphers against differential cryptanalysis and linear cryptanalysis. For SIMON-like algorithms, we will give an explicit relation between linear correlation of the round function and the hamming weight of the input masks. We will give the automatic search algorithms for differential trails and linear trails for ARX ciphers. Then we will make differential attack and linear attack on the ARX cihpers TEA, XTEA, HIGHT, SPECK, SIMON and SIMECK.

在轻量级密码算法中，有一类算法仅使用了模加运算（Add）、循环移位（Rotation）、异或运算（XOR）这三种运算，这类算法称为具有ARX结构的密码算法，简称ARX密码算法。ARX密码算法的优点是设计非常简单、并且非常适于软、硬件实现。. 虽然ARX密码算法有许多优点，但是到目前为止，学术界对于ARX密码算法的安全性仍然缺乏透彻的研究。本课题将研究ARX密码算法对于差分分析和线性分析的安全性。我们通过引入相关差分分布表和相关线性逼近表的概念, 发展系统性的理论和算法解决ARX密码算法差分特征和线性特征的自动化搜索问题；对于SIMON-like算法，确切地证明轮函数的线性相关系数与输入掩码的汉明重量的确切关系。然后在这些算法的基础上，我们对已有的ARX密码算法TEA、XTEA、HIGHT、SPECK、SIMON和SIMECK进行差分和线性分析。

该项目研究ARX结构相关的密码算法的密码分析，主要做了如下的的几个工作： （1）对美国国家安全局设计的基于ARX结构的轻量密码算法SIMON，SPECK及相关的密码算法 SIMECK, HIGHT等各种版本完成了全面的差分及线性分析；（2）考虑到密钥编排算法的影响，定义了新的不可能差分和不可能多面体变换的概念， 我们设计了一个基于SAT的自动化搜索工具用于搜索新定义的不可能差分和不可能多面体变换，与传统的方法具有很多的优势和广泛的应用范围。