分组密码和哈希函数的结构化分析

Block ciphers and hash functions play a fundamental role in cryptography. Due to the similarity in the design and security analysis of block ciphers and hash functions, an attack on a block cipher will affect the security of a hash function based on it, and vise visa. In this proposal we adopt top-down approach to analyze the structure of block ciphers and hash functions. . For structural analysis of block ciphers, we use popular provable security model to find block cipher structures with best efficiency and simplicity. At the same time we will develop better algorithms for finding the longest impossible differential of block cipher structures and apply it to find the longest impossible differential for the AES、IDEA etc.. For the construction of hash functions, we will find a simple method for deciding if the compression function of a block-cipher-based hash function has optimum collision resistance and preimage resistance. We also find new collision and preimage attacks on structures in SHA3 finalists JH and Grøstl. This new attack can also be applied to MD4-family hash functions， including MD5, SHA1 and SHA2 etc..

在密码学中，分组密码和哈希函数扮演着基础的角色。由于分组密码和哈希算法设计的相似性以及安全分析技术的类似性，一个分组密码的结构的安全性与相对应哈希函数的安全性互相影响。本项目采用自顶而下的方法对分组密码和哈希函数进行结构化分析。. 在分组密码结构方面，利用现有可证明安全模型，使用可证明安全方法寻找到简洁高效的分组密码结构。同时提出更好的寻找分组密码结构不可能差分链的方法，期望能够寻找到AES、IDEA等算法的最长的不可能差分链。. 在哈希函数的构造方面，寻找到判别一个基于分组密码构造的压缩函数是否达到最优安全性，包括最优抗碰撞性、最优抗原像性的简单方法。对SHA3最后一轮的候选算法JH及Grøstl提出新的碰撞和原像攻击,并使该方法能够以低于生日攻击复杂度和穷举搜索复杂度对一般性的MD4家族的哈希函数结构进行攻击,包括MD5、SHA1、SHA2等。

本项目对分组密码和哈希函数的结构进行了研究，取得了下述结果：. 1. 我们对分组密码中知名的 Lai-Massey 结构的伪随机性进行了分析。我们首次证明了经过一定的轮数，对任意信息论意义下计算无边界攻击者，Lai-Massey 结构是与一个伪随机置换在超越生日界限下选择密文不可区分的。同时我们对 Lai-Massey 结构和 Feistel 结构对抗通用性攻击进行了区分，通过研究我们发现，Lai-Massey 结构与 Feistel 结构在 5 轮以内对抗已知通用攻击方面存在着差别。 . 2. 我们改进了分组密码结构中 Wu-Wang 不可能差分链的搜索方法，我们的方法比 Wu-Wang 方法更为通用，可以在更短的时间内寻找到更多的不可能差分链。. 3. 我们对基于分组密码的哈希函数构造进行了新的分析，对基于分组密码的哈希函数进行全面性的分析归纳。我们成功的攻破了韩国学者 Lee 等人提出的基于分组密码的哈希函数构造，否定了该构造具有设计者宣称的理想抗碰撞安全性。对于基于分组密码构造最优安全的哈希函数，我们提出了一个简单的判断准则。