摘要: 密码学里的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函数的分析理论具有重要的意义.