Collision Attack on the Full Extended MD4 and Pseudo-Preimage Attack on RIPEMD
Collision Attack on the Full Extended MD4 and Pseudo-Preimage Attack on RIPEMD
复制标题
DOI：
10.1007/s11390-013-1317-5
复制
发表时间：
2013-02
影响因子：
0.7
通讯作者：
Gao-Li Wang
中科院分区：
文献类型：
--
作者：
Gao-Li Wang
密码学里的 Hash 函数在现代通信, 金融, 计算机等许多领域有着极为广泛的应用, 是许多密码算法与密码协议安全的基本前提条件. 其中一个最重要的应用是在数字签名中, 它是保证数字签名方案安全而有效的必要条件. Hash 函数的三个安全特性, 包括抗碰撞攻击 (collisionresistance), 抗原根攻击 (preimageresistance) 和抗第二原根攻击 (secondpreimageresistance), 是保密通信系统和密码学上需要重点满足的安全属性. 分析 Hash 函数的安全性, 能够为设计出安全的 Hash 函数提供理论基础和技术支持, 因而具有重要的现实应用背景. 对于双管道结构 Hash 函数 ExtendedMD4 和 RIPEMD, 本文分别给出了碰撞攻击和伪原根攻击. 王小云教授提出 “模差分方法”, 用该方法对于 MD 家族中的 MD4, RIPEMD, MD5, HAVAL, SHA-0, SHA-1 等一系列国际通用 Hash 函数进行了碰撞攻击. 对于 MD 家族中的双管道结构 (double-branch) Hash 函数 RIPEMD-128, RIPEMD-160, ExtendedMD4 等, 在用模差分方法对其进行碰撞攻击时, 保证两个管道的碰撞差分路线都成立的充分条件经常互相矛盾, 从而导致整个差分路线不可能成立. 因此到目前为止, 还没有公开的对于完整 RIPEMD-128, RIPEMD-160, ExtendedMD4 算法的碰撞攻击. 本文第三节采用模差分方法对 ExtendedMD4 算法进行了碰撞攻击, 找到了 ExtendedMD4 算法的碰撞实例. 在消息修改过程中采取了更精细的态度, 对于两个管道的充分条件, 在保证它们不产生矛盾的前提下进行消息修改, 从而保证碰撞差分路线的正确性. 随着对于 MD5 等一系列国际通用 Hash 函数的碰撞攻击, 对 Hash 函数的原根攻击也取得了很大进展. 在中间相遇攻击 (meet-in-the-middleattack) 的基础上, 发展出了对于 Hash 函数原根攻击的新方法. 这些方法对于单管道结构 Hash 函数很有效, 但是由于双管道结构 Hash 函数 RIPEMD 的中间状态的长度 (2n) 是 Hash 值长度 (n) 的 2 倍, 直接使用中间相遇攻击的思想对 RIPEMD 进行原根攻击的计算复杂度是 2n, 这与穷举攻击相比没有优势. 本文第四, 五节将现有的对于 Hash 函数原根攻击的方法加以推广, 提出了对完整 RIPEMD 算法的伪原根攻击的方法, 该方法比穷举攻击有效. 本文采用的方法对于分析其它双管道结构 Hash 函数也会起到借鉴的作用, 对于完善 Hash 函数的分析理论具有重要的意义.Abstract: The cryptographic hash functions Extended MD4 and RIPEMD are double-branch hash functions, which consist of two parallel branches. Extended MD4 was proposed by Rivest in 1990, and RIPEMD was devised in the framework of the RIPE project (RACE Integrity Primitives Evaluation, 1988~ 1992). On the basis of differential analysis and meet-in-the-middle attack principle, this paper proposes a collision attack on the full Extended MD4 and a pseudo-preimage attack on the full RIPEMD respectively. The collision attack on Extended MD4 holds with a complexity of 2 37, and a collision instance is presented. The pseudo-preimage attack on RIPEMD holds with a complexity of 2 125, 4, which optimizes the complexity order for brute-force attack. The results in this study will also be beneficial to the analysis of other double-branch hash functions such as RIPEMD-160.