基于meet/miss-in-the-middle思想若干密码攻击方法的研究

Since the prism program was exposed in 2013, all the countries in the world have paid more attentions to information storage, management and transmission. As an important part within the infrastructure of information and network security, block ciphers are served as the core cryptographic algorithm which can be used to guarantee the data confidentiality and integrity. Up to now, there are two main aspects including design and cryptanalysis of block ciphers. For cryptanalysis of block ciphers, four attacks, i.e., meet-in-the-middle attack, impossible differential cryptanalysis, biclique cryptanalysis and sieve-in-the-middle attack, have been used to analyze the securities of many popular block ciphers successfully. However, only a few researches focused on the relations between these attacks and the structure, the non-linear layer, the linear layer and the key schedule of block ciphers. In this project, we will evaluate the securities of some light-weight block ciphers, such as TWINE, SIMON and SPECK, by means of these four attacks. Our cryptanalytic results will be better than previous ones. Based on them, the relations between the efficiencies of these attacks and every part of a block cipher will be presented, especially the relations between the efficiency of impossible differential cryptanalysis and the non-linear part of a block cipher, the relations between the efficiency of biclique cryptanalysis and the key schedule of a block cipher, and the relations between the efficiency of sieve-in-the-middle attack and the key schedule of a block cipher. Our results will not only push forward the analysis theory of block cipher dramatically, but also result in considerable improvement of the design theory of block ciphers.

当今，尤其是“棱镜门”事件之后，信息的安全存储、处理和传输越来越重要，而分组密码是实现数据保密性和完整性的核心机制，其研究内容主要包括分组密码的设计和分析。在分组密码的分析中，中间相遇攻击、不可能差分分析、Biclique分析、Sieve-in-the-middle攻击近来被成功地用来评估一些著名分组密码的安全性，但针对它们的攻击效率与分组密码整体结构、非线性层、扩散层和密钥扩展算法的关系研究相对比较少。本项目将运用这些分析方法给出对轻量级分组密码TWINE、SIMON和SPECK的最好攻击结果，进而在此基础上提炼出分组密码各模块对它们的影响，特别是研究非线性部分对搜索不可能差分链的影响和密钥扩展算法对Biclique分析、Sieve-in-the-middle攻击等影响。我们的结果不仅改进了分组密码的分析方法，也影响着人们对算法的使用信心，为分组密码的设计提供理论依据。

本项目首先研究了基于miss/meet-in-the-middle思想的差分分析变形不可能差分分析和中间相遇分析等攻击方法，然后分析若干对称密码算法抵抗这些攻击方法的能力，并在此基础上研究密码算法各个模块对分析方法效率的影响，此外，也研究了基于miss-meet-in-the-middle思想的故障攻击方法。具体来说，第一，利用不可能差分分析攻击了分组密码Camellia和Rijndael。研究了Camellia、Rijndael算法密钥编排方案和加密结构，利用提早剔除技巧首次提出了对13轮Camellia-192的不可能差分分析新方案，并改进了之前对14轮Camellia-256不可能差分攻击的结果，得到了Camellia算法当时最好的分析结果；利用预计算表等技巧提出了对10轮Rijndael-224/256-256、9轮Rijndael-224-224和10轮Rijndael-224-256的最好分析结果；第二，研究了TWINE、Piccolo、Midori的密钥编排方案和加密结构，利用了差分枚举、相关密钥筛、多重集以及轮密钥计划的冗余性等技巧，提出了对26轮TWINE-128的中间相遇攻击，对无白化密钥的14轮Piccolo-80、带前白化密钥的18轮Piccolo-128和10轮Midori128算法的中间相遇攻击，得到了TWINE、Piccolo算法的目前最好的分析结果。第三，研究了不可能差分分析时间复杂度的通用计算公式，新提出的时间复杂度通用计算公式更贴近于实际攻击时计算的结果。第四，改进了不可能差分故障攻击和中间相遇故障攻击等方法的攻击模型，引入相关计算方法，科学地度量故障分析技术的实验结果，精确地评测故障分析技术的攻击效果，提出了不可能差分故障攻击、中间相遇故障攻击和唯密文故障分析LED算法、差分故障分析Whirlpool、PHOTON、TWINE等新方案，所得方案的攻击效率更高、代价更小。