基于代数攻击的序列密码逆向分析方法研究

The basic principle of algebraic attacks is to express the whole cipher as a large system of multivariate algebraic equations, which can be solved to recover the secret key. Recently, standard algebraic attacks, fast algebraic attacks and cube attacks have given great influence on the design and analysis of stream ciphers. In this project, we focus on analysis methods of stream ciphers based on algebraic attacks and the main contents of the project consist of three problems: research on spectral attacks and the spectral immunity of periodic sequences; algebraic attacks on some typical models of stream ciphers; improvement of cube attacks on Trivium. Our aims are to provide more theoretical foundations and technologies for further applications of algebraic attacks.

代数攻击的基本思想是将密码算法的安全性完全规约到关于密钥的多变元非线性方程系统的求解问题上。近年来, 基于代数攻击的分析方法, 包括标准代数攻击、快速代数攻击、cube攻击（选择IV代数攻击）等已经对序列密码的设计和分析产生了重大影响。本申请项目关注基于代数攻击的序列密码逆向分析方法研究, 主要研究内容有: 序列的谱攻击和谱免疫度的研究; LFSR和NFSR复合结构下的序列密码模型所对应方程系统的特点和规律分析; 对Trivium算法的cube攻击的改进。通过本项目的研究工作, 可以为序列密码代数攻击逆向分析的进一步发展提供理论支撑和应用指导。

本申请项目关注基于代数攻击的序列密码逆向分析方法研究，重点对基于LFSR和NFSR复合结构的序列密码算法和典型非线性序列源进行分析和研究。按照项目研究计划，在对基于LFSR和NFSR串联结构的Grain v1序列密码算法的sampling resistance的研究过程中，发现sampling resistance的本质就是代数攻击列方程解方程的思想，通过引入动态控制比特和非线性方程改进了Grain v1算法的sampling resistance，从而给出一系列折中范围更广泛的内部状态恢复攻击。同时，将建立内部联系的研究方法扩展到分组密码算法分析，得到了一些有价值的理论研究成果，如SKINNY算法的不可能差分攻击、SP型分组密码算法的截断差分研究、Feistel结构的不可能差分和零相关分析的可证明安全和一类Feistel结构的中间相遇攻击。进一步，项目还对序列密码中使用的一类重要非线性序列——环上序列给出了一种全新的压缩方式，并证明了很多情形下该压缩方式也具有最高权位的保熵性，这丰富了相关领域的研究结果，也为环上序列的应用提供了新的思路。本项目的研究成果表明：将代数攻击的列方程找联系的方法与已有的其他攻击方法结合可以改进一些密码算法的攻击效果。项目资助发表论文8篇，其中SCI检索5篇，EI检索1篇。培养硕士生1名，已经顺利取得硕士学位。项目研究推动了2017年全国密码数学挑战赛中的“极大布尔多项式方程组可满足性问题”的解决，获得全国密码数学挑战赛一等奖1项。