分组密码中间相遇攻击的自动化及量子安全性分析

The meet-in-the-middle(MITM) attack has shown the best single-key attacks on all versions of AES. The MITM attack is complicated and error-prone. Quantum MITM attack is not clear. This project will study the automatic search of MITM attack and quantum MITM attack, containing: 1. Automatic search of the best MITM distinguisher by describing MITM distinguisher with local expressions, linear constraints. 2. Automatic search of the best key recovery process, including automatic search of key-bridging technique. 3. Optimization and improvement techniques of MITM attack and automatic search of improved MITM attack, including key dependent sieve technique, differential enumeration technique, and automatic search of improved MITM attack with optimization techniques. 4. Quantum MITM attack and complexity evaluation. This attack involves extensive knowledge, such as differential cryptanalysis. Moreover, the automatic search of key recovery attack can be applied to other cryptanalysis. The project will improve the efficiency of classical and quantum security evaluations of block ciphers, and promote the development of other cryptanalysis. This project is significant for the analysis and design of block ciphers.

中间相遇攻击给出了单密钥攻击模型下对AES分组密码各版本最优的攻击结果。但是中间相遇攻击的实现过程繁复并易于出错，量子中间相遇攻击方法不清晰。本项目主要研究中间相遇攻击的自动化搜索方法及量子中间相遇攻击，包括：1.通过逻辑表达式或者线性约束不等式等方式，研究中间相遇区分器的自动化搜索方法。2.密钥恢复过程的自动化搜索方法，包括密钥桥的自动化搜索方法。3.中间相遇攻击的优化改进技术及其自动化搜索方法,包括密钥相关筛法、差分枚举等改进技术，以及组合这些技术的中间相遇攻击的自动化搜索方法。4.量子中间相遇攻击的分析方法和复杂度估计。中间相遇攻击不仅涉及差分分析相关领域的技术内容，而且其密钥恢复过程的自动化搜索方法可改进应用于其他攻击方法。该研究不仅能够促进全面高效的评估分组密码的经典和量子安全性，而且能够促进其他攻击方法的发展，对分组密码分析与设计均有着重要的意义。

在单密钥攻击模型下，中间相遇攻击给出了AES各版本的最优密钥恢复攻击，是对称密码基本的重要分析方法之一。本项目主要研究中间相遇攻击方法，包括分组密码区分器的自动分析、密钥恢复攻击的密钥桥技术、中间相遇攻击技术的改进等。本项目按照研究内容，在以下几方面取得了研究进展。（1）首次提出了分组密码Demirci-Selcuk（DS）中间相遇攻击的基于约束规划的自动分析方法，该方法既包含区分器，也涵盖基本的密钥恢复攻击的自动化。（2）对分组密码SKINNY提出了DS中间相遇密钥恢复攻击的密钥桥技术的自动分析的方法理论，直接将SKINNY-128-384的攻击时间复杂度降低了2^{16.18}。（3）改进了AES类杂凑函数的中间相遇原像攻击，并首次提出了该攻击的自动分析方法，利用提出的方法将AES128类杂凑函数的原像攻击原有的7轮攻击推进到8轮。提出了一种基于反弹技术的低QRAM的量子碰撞攻击方法，并且提出了利用非饱和超级S盒的自动化搜索经典碰撞攻击和量子碰撞攻击最优差分路线的方法，成功给出了AES-MMO、AES-MP和Grostl等杂凑函数的改进攻击。（4）首次提出了序列密码的线性相关攻击的基于约束规划的自动分析模型，对采用二次比特乘部件的密码的相关度计算不精确问题，提出了二次布尔函数相关度计算的多项式时间算法。利用提出的自动分析方法和相关度计算方法，给出了对MORUS所有版本的目前最优的线性攻击结果。MORUS是国际著名加密认证竞赛CAESAR竞赛的最后一轮的七个算法之一。项目完成论文13篇，其中包含顶级论文美密1篇，欧密1篇，亚密3篇，对称密码专题会议FSE3篇，DCC1篇。本项目研究了对称密码中间相遇攻击的自动分析方法，对更加全面评估对称密码的安全性具有重要的意义，能够更好地支撑对称密码的设计。