对称密码算法的相关密钥攻击研究

Symmetric cipher algorithm is an important part of cryptographic algorithms. Most existing symmetric cipher algorithms rely on iterations to achieve diffusion and confusion of the information and then resist the linear attack, differential attack, algebraic attack. There are two problems with this kind of symmetric cipher algorithms. The first is that it is difficult to overcome the related key attack. The second is that there exists weakness in key expansion. In addition, the existing related-key attacks are related to a specific cryptographic algorithm. There is no a general theory for systematic analysis. In the attack process, the use of the information is inadequate. This project aims to propose a general model for related-key attack and then provide theoretical foundation for cryptographic module/logic for defending the related-key attack. We first analyze the existing related-key attacks and then study the conditions and mechanisms for generating related-key. Then we study the relationship between the actual computational complexity and the amount of information. At last, we propose a optimal related-key attack method. The theoretical results of this project will promote the design and analysis of cryptographic algorithms.

对称密码算法是密码算法的重要组成部分，一般是利用多次迭代机制来实现的。虽然多次迭代可以通过信息扩散和混淆来有效地抵抗线性、差分、代数等攻击，但是基于多次迭代的设计方法较难抵抗相关密钥攻击，并且这类对称密码算法的密钥扩展环节存在一些安全弱点。此外，现有相关密钥攻击主要是对具体的密码算法给出的，缺少系统化的一般性理论分析结果，且攻击过程中所利用的信息是不够充分的。本课题旨在建立相关密钥攻击的一般模型,并形成理论和分析成果，用于指导和设计充分抵抗相关密钥攻击的密码模块或密码逻辑，以及对一些对称密码算法进行相关密钥攻击分析。课题首先对已有相关密钥攻击进行归纳提升，然后研究相关密钥形成的条件和机制、实际计算复杂与利用信息量的关系，最后提出优化的相关密钥攻击方法，并形成系统化的理论结果。本课题的实施将为现有密码算法设计和安全性分析提供理论指导。

对称密码算法是密码算法的重要组成部分，一般是利用多次迭代机制来实现的。虽然多次迭代可以通过信息扩散和混淆来有效地抵抗线性、差分、代数等攻击，但是基于多次迭代的设计方法较难抵抗相关密钥攻击，并且这类对称密码算法的密钥扩展环节存在一些安全弱点。此外，现有相关密钥攻击主要是对具体的密码算法给出的，缺少系统化的一般性理论分析结果，且攻击过程中所利用的信息是不够充分的。本课题的主要内容及成果包括：(1)对已有对称密码算法包括序列密码、分组密码、Hash 函数的相关密钥攻击方法归纳并提升。由于对称密码中一般利用线性变换来实现信息的扩散，利用S-盒来实现信息的混淆。研究中提出了一种新的提出了一种新的布尔函数的信息扩散和混淆的定义方法，证明了n元可逆布尔线性变换的最大信息扩散度和混淆度皆为n-1，同时给出了最大扩散度和混淆度为n的可逆布尔非线性变换的构造，表明AES、SM4、CAST等算法通过可逆线性变换实现信息扩散的技术不是最优的。（2）在相关密钥攻击一般理论模型指导下，对相关具体对称密码算法的安全性进行分析。根据横向迭代和纵向迭代，建立相关密钥攻击模型。利用信息论深入分析了几种差分的关系，扩展了传统的差分定义，采用概率证明给出两种运算，四种差分的关系。利用以上关系，研究中给出多个理论证明结论，在相关密钥差分攻击中引入信息论，充分考虑每1bit信息的利用率，可以有效提高相关密钥攻击的效率。（3）在相关密钥攻击理论模型和应用下，给出充分抵抗相关密钥攻击的密码模块的系统性设计原则，并对已有的相关对称密码算法进行相关密钥攻击，给出抵抗攻击的方案。