Hash函数MD5攻击技术研究(6)

Hash函数MD5攻击技术研究

２Ｈａｓｈ函数ＭＤ５攻击技术研究

撞【ｌｏ】。随着ＭＤｘ系歹ｌＪＨａｓｈ函数的发展，对于这些函数的安全性分析也不断深入。Ｂ．ｄｅｎＢｏｅｒ和Ａ．Ｂ０ｓｓｅｌａｅｒｓ找到了针对ＭＤ５算法的一种伪碰撞【１ｌ】１１，即同一明文在不 同初始值下得到相同Ｈａｓｈ值。在１９９６年欧洲密码大会上，Ｈ．Ｄｏｂｂｅｒｔｉｎ公开了另一种形式的伪碰撞【１２】，即在两个不同的初始值下的不同消息的一个碰撞。在１９９８年国际密码大会上，ＥＣｈａｂａｔｌｄ和Ａ．Ｊｏｕｘ证明了用差分攻击方法可以以２姐的概率找到ＳＨＡ．０的一个碰撞【ｌ引。

一些针对Ｈａｓｈ函数的更为有效的攻击方法出现在２００４年。ＥｌｉＢｉｈａｍ和Ｒａｆｔ提出了对ＳＨＡ．０算法的几乎完全碰捌１４】。ＡＡｏｕｘ给出了一个由４个明文块构成的ＳＨＡ．０的碰撞【１５ｌ。在这些成果中，最为显著的是在２００４年国际密码学大会上，王小云等人宣布的对于一系ＹｌＪＨａｓｈ函数的碰撞结果，包括ＭＤ４［１６１、ＭＤ５［１７１、ＨＡＶＡＬ－１２８［１８ｌ和ＲＩＰＥＭＤ算法，其中可以找至ＩＪＭＤ４和ＲＩＰＥＭＤ算法碰撞的复杂性分别低于２８和２１８。王小云提出了一套新的针对ＭＤｘ系列的Ｈａｓｈ函数的分析技术，同时给出了得到满足差分路线的充分条件的方法，以及如何使用明文修改技术来提高碰撞攻击的成功概率。２００５年，王小云等应用此技术对ＭＤ５［１７１、ＳＨＡ－０［１９１、ＳＨＡ－１［２０ｌ算法进行碰撞攻击，取得了很好的效果，在普通的个人电脑上就可以找到相关碰撞的实例。这一攻击技术对现有的Ｈａｓｈ函数提出了严峻的挑战，促进了新的Ｈａｓｈ算法的开发研究：美国ＮＩＳＴ于２００７年开始在全球征集新的Ｈａｓｈ算法。截至２００８年１１月，一共提交了６４个入选算法；２００８年１２月有５１个算法被ＮＩＳＴ接收作为第一轮的候选算法；２００９年７月，ＮＩＳＴ公布了进入第二轮的１４个算法；２０１０年将公布进入最终一轮的５个算法；最终将于２０１２年选出获胜算法并命名为ＳＨＡ－３。

１．２Ｈａｓｈ函数设计原则

Ｈａｓｈ函数的算法是公开的，对于每一个给定的消息串，计算输出的Ｈａｓｈ值是容易的；但是从Ｈａｓｈ值反推算出输入的明文是困难的。实际应用中，安全的Ｈａｓｈ函数必须符合以下三个设计原则：

１．抗碰撞性攻击：由于Ｈａｓｈ函数具有压缩的性质，所以必然存在多个消息串对应同一Ｈａｓｈ值的可能，这就是所说的碰撞的出现。实际应用中由于Ｈａｓｈ函数的抗碰撞性，导致现实中很难找到两个不同的消息串对应同一个Ｈａｓｈ值的情况。

２．抗第一原像攻击：对于任意一个消息串ａ，容易得到它的Ｈａｓｈ值ｈ（ａ）；但是从它Ｉ拘Ｈａｓｈ值ｈ（ａ）很难推出相应的消息串ａ，此时消息串ａ称之为ｈ（ａ）的原像。抗第一原像攻击使得Ｈａｓｈ函数具有单向性的特点。

３．抗第二原像攻击：对于某一给定的消息串ａ，很难找到另一不同的消息串ｂ，使得ｈ（ａ）＝ｈ（ｂ）。抗第二原像攻击使得Ｈａｓｈ函数可以应用于数字签名和身份认证领域。