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

Hash函数MD5攻击技术研究

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

∑１１＝ｂ２＋Ｆ（ｃ３，ｄ３，ａ３）＋ｍ１，＋‘ｌｌ，其中ｔｎ是常数。ｂ３的差分有以下两个来源：

１．直接继承ｃ。的差分。

２．间接继承∑。，的差分：第一是ｂ：的差分，第二是Ｆ（ｃ，，ｄ，，ａ。）的差分，第三是ｍ，，的差分（如果ｍ，，有差分的前提下）。

在计算ｂ，运算中，只有Ｆ函数是位运算，其他都是在模２３２下的加法运算。在这个过程中，首先充分关注Ｆ函数，利用Ｆ函数的性质，产生下面步骤所需要的差分，同时消除不需要的差分；其次，符号差分的扩展很大程度上是依靠∑”来实现的。在模差分确定的前提下，符号差分有多种可能，必须根据需要来选择；最后，结合第３２位的特殊性和符号差分的扩展，跟踪循环左移对这个差分继承的影响。

３．１．３确定充分条件

破译ＭＤ５算法的关键之三是控制差分路径的充分条件。充分条件越少，对明文的限制程度越小，越容易找到碰撞。在ＭＤ５中利用Ｆ函数、Ｇ函数、Ｈ函数和Ｉ函数的性质，循环左移的性质和差分路径的整体需要，来确定差分的充分条件。

在确定充分条件的过程中，必须利用非线性函数的性质。ＭＤ５算法中有Ｆ函数、Ｇ函数、Ｈ函数和Ｉ函数这四个非线性函数，现在以Ｆ函数和Ｈ函数为例，总结非线性函数的特性【３１】。

从Ｆ（Ｘ，Ｙｚ）－－（ｘ八ⅥＶ（－ｉＸＡＹ）的表达式，可以看出Ｆ函数是一个选择函数。选择函数的意思是：Ｆ函数的值的选取是根据Ｘ的值来决定选取Ｙ或者Ｚ的值：即如果Ｘ＝Ｉ，Ｆ函数的值等于Ｙ的值；如果Ｘ＝０，Ｆ函数的值等于Ｚ的值。Ｘ的值对Ｆ函数的值起到一个选取的作用。根据上述所说的Ｆ函数的选取的性质，我们可以总结出Ｆ函数的三个性质：

１．Ｆ（Ｘ，Ｙｚ）＝Ｆ（１Ｘ，Ｙｚ），当且仅当Ｙ＝ｚ；

２．Ｆ（Ｘ，Ｙｚ）＝Ｆ（Ｘ，－Ｉ

３．Ｆ（Ｘ，Ｙｚ）＝Ｆ（Ｘ，Ｙ

具有以下两个性质：

１．Ｘ，Ｙ

２．ｘ，ＹＹ１ｚ），当且仅当ｘ＝Ｏ；ｚ），当且仅当ｘ＝１；从Ｈ（Ｘ，ＹＺ）＝ＸｏＹＯＺ的表达式，可以看出Ｈ函数是个对称函数，该函数ｚ这三个参数中相同的位有奇数个１，Ｈ函数的值对应的位为１；Ｚ这三个参数中相同的位有偶数个１，Ｈ函数的值对应的位为Ｏ。总之，在寻找ＭＤ５碰撞的过程中，上述三个方面都很关键，他们相辅相成，相互协调，必须统一起来整体考虑。