轻量级密码算法的代数攻击

Lightweight cryptography has been a very hot topic for the last few years. Algebraic attacks have been regarded as an important tool for the design and analysis of ciphers. Cube attacks are a new kind of algebraic attacks which were discovered a few years ago and have been applied to analysis of many cryptosystems including stream ciphers, block ciphers and hash functions. The restriction of computational resource is a bottleneck for algebraic attacks, especially for cube attacks. The estimation of algebraic degrees is an essential issue in algebraic attacks. In the preliminary study, our research group proposed a heuristic algorithm for searching the best cubes, and successfully mounted the best distinguisher on reduced Trivium, based on the idea of cube attacks. Recently, we have discovered an effective method for estimating the algebraic degrees of the stream ciphers Trivium and Grain. This research project first focuses on the security analysis of the three typically lightweight ciphers Trivium, Grain and SIMON, by exploiting new methods for estimating the upper bound on the algebraic degrees of ciphers and combining algebraic techniques with symbolic computation and high performance computing on graphics processing units (GPU), then generalizes the analysis to many other lightweight ciphers which have similar structures as Trivium, Grain or SIMON, and simultaneously targets at exploring new techniques and innovation models of algebraic attacks, which will finally perfect the theories and techniques of algebraic attacks, especially for cube attacks, and lay the foundation for designing and analyzing cryptographic algorithms.

轻量级密码学是近年来非常热门的研究领域。代数攻击是设计与分析密码算法的重要工具。立方攻击是最近几年出现的新型代数攻击，已被应用到流密码、分组密码和杂凑函数等密码体制的分析中。计算资源的限制是代数攻击尤其是立方攻击的瓶颈，代数次数的估计是代数攻击中的基本问题。在前期研究中，本课题组提出了一种搜索最优立方的新策略，并基于立方攻击的思想，成功构造了流密码Trivium最好的区分器。最近，我们发现了估计流密码Trivium和Grain代数次数的一种有效方法。本课题首先针对典型轻量级密码Trivium、Grain和SIMON进行研究，在提出估计密码算法代数次数上界的新方法的基础上，利用代数技术结合符号计算与GPU高性能计算进行安全性分析，然后针对许多具有相似结构的轻量级密码算法进行相应的研究，同时探索代数攻击的新技术和新模型，最终完善代数攻击特别是立方攻击的理论与技术，为设计与分析密码算法奠定基础。

在许多新兴领域中，常常涉及高度受限设备的互联与通信，例如传感器网络、分布式控制系统和物联网等。在这些领域中，数据安全与隐私保护都极其重要。资源受限环境下的轻量级密码学因此成为近年来的热门研究领域。在项目执行期间，项目组研究了轻量级密码算法的代数次数估计、非线性反馈轻量级密码算法的立方攻击和具有其他结构的低代数次数密码算法的代数攻击技术，以及轻量级密码算法的硬件实现优化方法。所取得的重要结果包括：1）提出了数值映射的新技术，首次建立了非线性反馈密码系统的代数次数上界的理论估计模型，将传统算法的指数级复杂度降为线性复杂度，在Trivium等密码算法的区分攻击方面取得了国际先进水平的成果。2）基于代数与概率统计方法，提出了相关立方攻击的密码分析新模型，能够将威胁小的弱密钥区分器转化为威胁大的密钥恢复攻击，针对欧洲eStream计划获胜算法Trivium进行了安全性分析，得到了835轮Trivium算法的实际部分密钥恢复攻击。3）针对SHA-3杂凑函数的代数结构，提出一种将非线性方程系统转化为线性方程系统的新技术，改进了SHA-3的3轮和4轮原像攻击，并首次解决了与SHA-3相关的3轮和4轮原像挑战问题;通过将S盒在子空间上进行线性化的技术，将Shamir等人提出的差分连接器从1轮提升至2-3轮，结合差分密码分析方法，针对缩减轮SHA-3，给出了实际碰撞攻击，攻击复杂度和轮数优于Shamir等人(Journal of Cryptology 2014)的结果。4)提出了轻量级密码算法的硬件实现优化方法，对eSTREAM 工程面向硬件的3个获胜算法和2个类似Grain 的小状态序列密码Lizard 和Plantlet 进行了硬件实现，并且针对不同的硬件应用场景，分别使用常规、串行、并行三种方式进行定向优化。在项目执行期间，发表学术论文11篇，包括密码学旗舰会议和顶级期刊论文5篇，其中Crypto 1篇、Eurocrypt 2篇、Asiacrypt 1篇和Journal of Cryptology 1篇。培养博士生4名和硕士生2名。项目负责人获得中国密码学会优秀青年奖。