浅析散列函数MD5算法的原理及其碰撞攻击

浅析散列函数MD5算法的原理及其碰撞攻击摘要随着网络技术的广泛应用，网络信息安全越来越引起人们的重视。针对数据在存储时存在大量的安全问题，目前通常将需要存储的数据进行加密然后再存储，应用MD5算法是一个不错的选择。本文详细介绍了MD5算法的概念，对MD5算法的原理、碰撞攻击以及MD5算法破解的重要意义进行探讨。关键字：MD5原理碰撞攻击一、引言现阶段，信息安全性已成为全社会共同关心的问题，密码学研究也越来越被人们所关注。密码学主要研究的是通讯保密。近年来，密码学研究之所以十分活跃，主要原因是它与计算机科学的蓬勃发展息息相关。由于公共和私人的一些机构越来越多的应用电子数据处理，将数据存储在数据库中，因此防止非法泄露、删除、修改等是必须重视的问题。对数据进行加密能够防止他人盗取需要保密的信息，但这只解决了一方面的问题，至于如何防止他人对重要数据进行破坏，如何确定交易者的身份，以及如何防止日后发生纠纷时交易者抵赖，还需要采取其它的手段，这一手段就是数字签名。数字签名技术实际上是在数据加密技术基础上的一种延伸的应用。数字签名经常和单向散列(Hash)函数一起使用，而单向散列(Hash)函数是现代密码学的核心。最常见的散列算法有MD5，SHA和Snefru，MD5是当今非常流行的Hash加密技术，因而本文选取MD5作为研究对象，详细介绍了MD5算法的概念，对MD5算法的原理、碰撞攻击以及MD5算法破解的重要意义进行探讨。二、MD5算法的概念MD5的全称是Message-DigestAlgorthm5(信息--摘要算法),即将任意长度的“字节串”变换成一个128bit的大整数,是一种不可逆的字符串变换算法。通过数学运算,把不同长度的信息转化到128位编码中,形成Hash值,通过比较该数值是否正确,来确定通信双方的合法性,即数字签名功能。在数据传输后,可以通过比较Hash值来判断信息途中是否被截获修改,是否由合法的发送人发送或者合法的接收人接收等。用这种方法,可以防止密钥丢失。三、MD5算法的基本原理该算法输入任意长度的消息,输出128位消息摘要,处理以512位输入数据块为单位。处理报文摘要的过程如下:（1）步骤1:添加填充位。在消息的最后添加适当的填充位使得数据位的长度满足与448模512同余,即length=448mok512。（2）步骤2:填充长度。原始消息长度(二进制位的个数)用64位表示,并附在步骤1的结果后。由这两个步骤得到长度为512整数倍的报文。表示为L个512位的分组:Y0,Y1,……YL-1。其长度为L×512bits。令N=L×16,则长度为N个32位的字。令M×[OLN-1]表示以字为单位的消息表示。（3）步骤3:初始化MD缓冲区。一个128位MD缓冲区用以保存中间和最终Hash函数的结果。它可以表示为4个32位的寄存器(A,B,C,D)。寄存器初始化为以下的16进制值:A=67452301，B=EFCDAB89，C=98BADCFE，D=10325476。寄存器内容如下:字A:01234567字B:89ABCDEF字C:FEDCBA98字D:76543210（4）步骤4:以512位的分组(16个字)为单位处理消息。算法的核心是压缩函数(HMD5)，它包括4轮处理。4轮处理具有相似的结构,但每次使用不同的基本逻辑函数,记为F、G、H、I,如表1所示。每一轮以当前的512位分组(Yq)和128位缓冲区ABCD作为输入,并修改缓冲区的内容。每次使用64元素表T[1L64]中的1/4。该T表有sin函数构造而成。T的第i个元素表示为T[i],其值等于232×abs(sin(i))的整数部分,其中i是弧度。由于abs(sin(i))是一个0到1之间的数,T的每一个元素是一个可以表示成32位的整数。T表提供了随机化的32位模板,消除了在输入数据中的任何规律性的特征,如表2所示。第4轮的输出与第1轮的输入(CVq)相加得到CVq+1,这里的加法是指缓冲区中的4个字与CVq中对应的4个字分别232模相加。(5)步骤5:输出。所有L个512位分组处理完毕,最后的结果就是128位消息摘表1基本逻辑函数的真值表要。每一轮包含对缓冲区ABCD进行16步迭代,每步迭代形为:a←b((a+g(b,c,d,)+Xk+Ti)s)其中a,b,c,d=缓冲区的4个字,它按一定次序随迭代步变化。g=基本逻辑函数F,G,H,I之一s=32位的变量循环左移s位X[k]=M[q×16+k]=消息第q个512位分组的第k个32位字T[i]=矩阵T中的第i个32位字+=模232加法每次循环进行16步操作,其中S的值在4次循环中都有不同的定义,并且在每一步的值也不同。四、MD5算法的碰撞攻击MD5的创始人Rivest猜测,MD5可能是128位的Hash码中最强的算法,即Hash码相同的两条消息所需的代价为264数量级,找到给定摘要的消息所需的代价为2128数量级。虽然如此,但是现有的一些攻击对MD5算法非常不利:（1）Berson已经证明,对单轮的MD5算法,利用差分密码分析,可以在合理的时间内找出摘要相同的两条消息,这一结果对MD5的4轮运算中的每一轮都成立。但是Berson尚不能说明如何将这种攻击推广到具有4轮运算的MD5之上。（2）Boer和Bosselaers说明了如何找到消息分组X和两个有关的链接变量使得它们产生相同的输出,也就是说,对一个512位的分组,MD5压缩函数对缓冲区ABCD的不同值产生相同的输出,称之为伪碰撞。目前尚无法用上述方法成功地攻击MD5算法。（3）Dobbertin提出的攻击对MD5最具威胁,它可使MD5压缩函数产生碰撞。但到目前为止,尚不能用Dobbertin提出的方法对使用初值(IV)的整个消息进行攻击。（4）XiaoyunWang的算法在预定的时间内找到了MD5的一个碰撞。五、MD5算法的破解及其意义一种Hash函数被破解,通常有3种情况：第1种是函数的单向性被攻破,即最彻底的攻破，也就是对于给定的明文及摘要，能够用数学计算的方法，求出另一个也能产生出此摘要的等价的明文；第2种是对于给定的明文及摘要，能够用随机碰撞的方法找到另一个等价的明文；第3种也是用随机碰撞的方法，找到两个具有相同摘要的不同的明文,其工作量比第2种情况要小很多。根据MD5破解算法，对一个消息A及其Hash值H,有可能推出另一则信息B,它的Hash值也是H。如果A是一个符合预先约定格式、有语义的信息,那么推演出的信息B将不是一个符合约定格式、有语义的信息。比如说，A是一个符合X509格式的数字证书，那么推出的B不可能刚好也是一个符合X509格式，而且是伪造者希望的数字证书。众所周知，电子合同需要双方甚至多方电子签名。对于双方签名，相当于先产生A的Hash值H1，然后对A和H1合起来的信息进一步产生Hash值H2。目前的研究发现还无法找到一种方法推出一则信息B刚好产生同样的H1和H2。其次,即使MD5被破解，也有更好的更安全的Hash算法，应该使用Hash码更长、抗密码分析能力更强的Hash函数。参考文献[1]杨义先,林晓东.信息安全综论[J].北京:电信科学出版社,1998（08）：87-89.[2]杨明,齐望东.密码编码学与网络安全[M].北京:电子工业出版社,1997.[3]彭文波.MD5算法原理及应用[EB/OL].中国知网1999.2。[4]桑海,李建宝.加密算法MD5的研究与应用[EB/OL].华南金融电脑1999.7.