序列密码的关键代数分析方法研究

The main objective of this project is to research the key algebraic cryptanalysis methods against stream ciphers. Stream ciphers are an important technique to guarantee the information confidentiality and integrity, and analyzing their abilities to resist all kinds of attacks scientifically is necessary to judge the ciphers' security bounds properly. As a natural bridge between symmetric cryptography and algebraic theory, algebraic analysis focuses more on providing ingenious attacks according to the internal structure of ciphers, compared with statistical analysis. However, the research of algebraic analysis is still in its infancy so far. For the existing typical stream ciphers, how to construct more efficient and universal new algebraic cryptanalysis methods is a crucial problem in the field of cryptography. Based on the former work of the applicant, this project will further study the important problems of key algebraic cryptanalysis methods against stream ciphers, especially the algorithm design of the automatic paths searching for guess-and-determine attacks, the model optimization of cube attacks by the reduction of division property and mixed integer programming problem, the sheet establishment of analysis process for algebraic attacks on symmetric ciphers and so on. During the project period, the applicant will make efforts to achieve substantial progress on the theory deepening, attack efficiency improving and application scope expanding for the algebraic analysis methods against stream ciphers.

本项目的主要目标是研究序列密码的关键代数分析方法。序列密码是保障信息机密性和完整性的重要技术，只有通过系统地分析其抵抗各类攻击的能力，才能适度地判断其安全性。相比于统计分析方法，代数分析作为一种联系对称密码学与代数理论的天然桥梁，更侧重于利用密码算法的内部结构提供精巧的攻击构造。但是，到目前为止，对代数分析方法的研究仍处于初级阶段。针对现有典型序列密码，如何构造更加高效、普适的代数分析方法是密码学领域的一个重要科学问题。本项目拟基于申请人已有的研究基础，进一步研究序列密码关键代数分析方法中的重点问题，特别是设计猜测确定路径的高效自动化搜索算法、基于可分性质和混合整数规划问题归约优化立方攻击模型、建立对称密码代数攻击分析流程单等兼具理论和实际应用意义的问题。在项目周期内，申请人将致力于在序列密码代数分析方法的理论深化、攻击效果改进和适用范围扩展等方面取得实质性进展。

在项目研究期间，按原定计划研究了序列密码的关键代数分析方法，包括：“设计猜测确定路径的高效自动化搜索算法”、“基于可分性质和混合整数规划问题归约优化立方攻击模型”、“简化对称密码代数攻击分析流程”等问题。共发表论文13篇，授权发明专利1项，其中CCF/CACR A类论文3篇，CCF/CACR B类论文8篇，CCF T1和T2类论文各1篇，部分论文发表在IEEE Transactions on Information Theory、Designs Codes and Cryptography、ASIACRYPT2020、FSE 2020等密码学领域高水平的期刊和会议上。.在关键代数分析方法方面，我们研究了猜测确定路径自动化搜索算法，提出了初始猜测集修正启发式算法搜索轨迹技术，通过猜测基迭代删去了非必须猜测变量，提出了猜测-确定路径修改框架及其自动化算法，突破了重要技术问题，应用至SNOW-V、SNOW-Vi、AEGIS等密码算法；首次建立了可分性质与动态立方攻击、偏差立方区分器之间的理论联系，提出了基于可分性质的动态立方攻击新方法，改进了Grain、Kreyvium、Acorn等序列密码的攻击结果；针对大S盒的积分分析，提出了新的可分传播表，相关方法可以考察大S盒的细节，进而给出更为精确的基于比特可分性质的积分区分器自动化搜索方法，刷新了ICEBERG、KHAZAD、Camellia等分组密码的攻击结果；理论上证明了关于对称密码原语的线性化代数攻击的有效性和必要条件。在对称密码算法分析中的相关问题研究方面，我们提出了模加操作密码学性质的新计算方法，提出了依赖进位的差分分布表和线性近似表，进而可以搜索ARX类密码算法的最优差分路径和最优线性路径；基于密码函数中求解差分方程的思想，提出了基于状态值的不可能差分区分器的自动化搜索算法，可以刻画密钥编排影响、考察依赖数据操作和大S盒细节等，解决了传统方法的局限；给出了SIMON类轮函数的平方相关度上界，提供了SIMON和SPECK的最优线性特征自动化搜索方法；提出了基于遗传算法的ARX类分组密码智能差分分析方法。在序列密码设计和对称密码应用方面，研究了序列密码设计理论，设计了轻量级认证加密算法FAN，给出了轻量的8比特S盒构造方法及其电路，提出了新LPN求解算法等。这些最新成果为对称密码的设计与分析提供了理论和技术上的支持。