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

Hash函数MD5攻击技术研究

第三章ＭＤ５的碰撞攻击

第三章ＭＤ５的碰撞攻击

３．１碰撞攻击的整体思想

破译ＭＤ５算法是个系统工程例。在破译过程中，首先，要从整体上确立一个框架，确定一个产生碰撞的总体思路；其次，根据整体思路应用明文修改等相关技术和非线性函数的特性等来实现差分路径；最后，尽可能简化实现差分路径的充分条件，降低计算复杂度，提高计算机“搜索”到碰撞的概率。

３．１．１引入明文差分

破译ＭＤ５算法的关键之一是在明文中引入差分。好的明文差分有以下几个特点：首先，要有尽可能多的“自由字＂，这样可以放宽产生碰撞的充分条件，提高碰撞概率；其次，明文中第一次出现差分的位置应该尽量远离第一个字，这对于消息修改技术至关重要，可以使明文存在更大的修改空间，同时也有利于计算机的成功搜索；再次，实现碰撞所需要的充分条件越少越好，这样可以有效的降低计算复杂度；最后，明文的“块数”越少，说明实现碰撞的技术水平越高。目前，发表的三种ＭＤ５算法的碰撞实例［１７，２３，２４］，都是采用“两个明文块＂，即１０２４位的明文，其中文献［１７，２３】的两个明文块的差分的位置都是位置对称、符号相反，这种差分的引入是针对Ｈａｓｈ函数ＭＤ结构的特点而设计的，它能使得第一明文块和第二明文块分别产生的差分值能够位置对称，符号相反（第３２位除外），最终的Ｈａｓｈ值是将两个值相加。这样，两个明文块产生的差分最终将抵消（第３２位以溢出的形式抵消），从而产生了碰撞。文献ｆ２４】差分的引入摆脱了对称的模式，但其差分的消除仍遵循上述原则。最后要说明的是，以上三种ＭＤ５算法的碰撞实例，在寻找碰撞的过程中，都需要利用明文修改技术来确保得到碰撞所需的明文。３．１．２选择差分路径

破译ＭＤ５算法的关键之二是要选择好差分路径。差分路径的控制很大程序上是利用符号差分的扩展来实现的，使得整个差分按照整体的需要进行。选择差分路径时，要尽量减少差分中的汉明重量。一般情况下，尽量把差分引到第３２位，由于该位置的特殊性，容易消除差分。

在选择差分路径的过程中，必须关注每一步运算中差分的继承和非线性函数的位运算。以ＭＤ５第１２步为例，ｂ３＝ｃ３＋（（ｂ２＋Ｆ．（ｃ３，ｄ３，ａ３）＋ｍ１１＋ｔ１１）＜＜＜２２），令