散列函数攻击算法研究

《散列函数攻击算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、浙江大学信电系-电子与通信工程-微电子01班李喆2016-10-26散列函数攻击算法研究Hash函数是传统密码学的重要分支，以MD5、SHA-1为代表的经典Hash函数曾经被广泛应用于各种加密和验证场景，例如在互联网安全协议HTTPS的SSL加密，大量的网站采用了SHA-1算法进行身份验证。由于Hash算法的广泛应用，以及在密码协议中的重要角色，Hash算法的安全性一直是密码界的关注点。散列函数中，应用最为广泛的便是MD5。自其诞生以来，相关的破解研究就一直不断。1993年,DenBoer和Bosselaers首次公开发现了MD5的伪碰撞：两个不同的初始化向量可以生成完全相同的MD5摘要；19

2、96年，Dobbertin发现了一个MD5的碰撞对；2004年3月，MD5CRK项目演示了针对MD5算法的生日攻击；同年8月，王小云教授的团队对MD4、MD5、HAVAL-128和RIPEMD等四个著名算法实现了加速后的杂凑碰撞，使得MD5的破解进入了可接受的运算范围；第二年3月，王小云等人演示了两个不同公钥的X.509证书的MD5值相同；不久后，VlastimilKlima改进了算法，使得可以利用单台计算机，在数小时内完成碰撞；2006年3月，Klima公布了一个算法，将运算量减少到一分钟；2010年，十二月，谢涛和冯登国宣布第一个单块MD5碰撞，他们向社区发出挑战，奖励在2013年1月之前

3、找到不同的64字节碰撞算法的人；2012年，MarcStevens响应该挑战，公布了单块消息碰撞，以及相关的碰撞算法和源码。至此，MD5已经可以在秒为单位的时间内构建碰撞。在同期的时间里，SHA-1遭到相同的碰撞攻击，最终的改进在最佳状态达到了0C21，的复杂度1,最坏情况0(215)。随后，SHA-1、MD5等算法被SHA-22以及SHA-3等继任者相许代替，基本退出了历史舞台。自王小云教授采用特例化的差分攻击3破解了MD5以来，如何寻找差分和差分路径的方法成为了国内外密码学家关注的焦点，攻击算法针对Hash函数的内在结构缺陷进行攻击，构造高效的攻击算法。王小云教授的算法正是利用了MD5中活

4、动状态的高位bit不能尽快的充分混合4，从而找到有效的差分和差分路劲成功攻击了MD5算法。本文将从基础的协议开始，分析并构建散列函数的攻击算法，分析散列算法作为密码协议基础的基本性质和弱点。1.散列函数的基本结构散列函数从根本上来讲是一种多对一映射，将一个有限或者无限的集合，通过一个函数，映射到一个有限的集合上。所有散列函数都有如下一个基本特性：如果两个散列值是不相同的(根据同一函数b那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果。但另一方面，散列函数的输入和输出不是一一对应的，如果两个散列值相同，两个输入值很可能是相同的，但并不能绝对肯定二者一定相等。输入一些数据

5、计算出散列值，然后部分改变输入值，一个具有强混淆特性的散列函数会产生一个完全不同的散列值。典型的散列函数都有无限定义域，比如任意长度的字节字符串，和有限的值域，比如固定长度的比特串。在某些情况下，散列函数可以设计成具有相同大小的定义域和值域间的一一对应。一一对应的散列函数也称为排列。可逆性可以通过使用一系列的对于输入值的可逆“混合”运算而得到。散列函数属于多对一的非解码映射，因此，往往用于验证或者传递，也因此，函数的计算表达式往往是公开的，因此，只有足够复杂和精细设计的散列函数，才能够安全的传递信息。在实践中，Hash函数的构成运算，往往是取余，四则运算、位运算、分组以及迭代。我们先从一个基本

6、的Hash函数开始，逐步分析散列函数的构成及其缘由：/i(n)=(an+h)modm该函数可以将任意整数映射到大小为

7、m

8、的集合，由同余的周期性，我们可知：h(n4-km)=(a(n+km)+b)modm=(an+Z?)modm+0=h(n)因此，当知晓函数的表达式时，此种散列函数可以直接构造碰撞，为了提高Hash函数的单向性，消除其周期性，在Hash函数的运算组成中，引入了位运算：h(n)=((anxork)+h)modm此时，由于位运算的特性，/iCn)的周期性被打破，因此，位运算起了混淆的作用。此时，如果对/i(n)进行暴力碰撞，由简单的鸽笼原理可知，复杂度至多为000，因此，m增大有利

9、于减少碰撞。进一步分析，由于函数中混淆由位运算承担，但是不管经过多少次位运算，运算的位数是固定的，也就是说，当输入的数据n足够大，位数远远大于时，有：h(n)=(ann+(anzxork)+h)modm(nn»nz)那么，显而易见，此时的h(n)的高位并未参与位运算，将再次出现周期性："(n+m*2f)=(anh+(anfxorfe)+b+m*2Z)modm=h(n)(nh»nhI>Z(/c))这