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

Hash函数MD5攻击技术研究

第三章ＭＤ５的碰撞攻击１９

２．研究ｒ（ｄ２，ａ２，ｂ１）部分，根据Ｆ函数的性质、△ｄ２、△ａ２，可以得出：△①６＝【－２３，２２，２１，２０，１９，１８，１７，１６，１４，１３，１２，１１】，在经过Ｖ６＝ｃ１＋ｍ６＋ｍ６＋ｔ６，异或差分进行了变化，△１ｌ，６＝．２１６＋２１４＋２１３＋２１２＋２１１，即ＡＷ６＝【．１６，１４，１３，１２，１１】。

３．经过循环左移１７比特，ＡｔｌＪ６＜＜＜１７＝【一１，３１，３０，２９，２８】。Ａｃ２继承了△Ｖ６＜＜＜１７的比特变化，其中，第１比特的差分进行了扩展了６个比特，使得ｃ：【－６，５，４，３，２，１】，其他比特没有进行扩展。

４．Ａｃ２还继承了Ａｄ２＝２３１这部分的值，联合ＡｔｌＪ６＜＜＜１７＝【３１，３０，２９，２８】，这些部分共同构建了Ｃ２［３２，３１，３０，２９，２８】。

详细解析第８步中各比特的由来：

第８步在文献［１７１中是个关键的步骤，控制好该步的差分对最终产生碰撞有着重要的作用。该步的差分是由前７步差分共同作用产生的，即（ａｃ：，Ａｄ：，Ａａ：，Ａｂ。）一△ｂ：。为了控制好差分路径，使得经过第８步的运算以后，达到ｂ２ｔ－ｂ２【１，１６，－１７，１８，１９，２０，一２１，一２４】的差分特性，必须控制好前面的△ｃ２，△ｄ２，△ｂ。的值。前７步的运算为第８步提供了以下前提条件：

ｂ１’＝ｂ１；△ａ２，

ａ２＇＝ａ２［７，－＇－，２２，－２３】；

ｄ２．－ｄ２【一７，２４，３２】；

Ｃ２’＝Ｃ２【１，２，３，４，５，－６，７，８，９，１０，１１，一１２，－２４，一２５，－２６，２７，２８，２９，３０，３１，３２】

第８步的运算如下：

ｂｅ－ｃ？＋（（ｂ１＋Ｆ（ｃ２Ｆ，ｄ２，ａ２）＋ｍ７＋ｔ７）＜＜＜２２）

ｂ２ｔ＝ｃ；Ｆ’＋（（ｂｌ’＋Ｆ（ｃ；’，ｄ２＇，ａ２Ｉ）＋ｍ７ｌ＋ｔ７１）＜＜＜２２）

ｂ：的表达式中有两个ｃ：，为了更好的区分，用ｃ罗和Ｃ２Ｆ分别表示。从上面两个表达式可以看出：在第８步运算中明文没有引入差分，所以ｍ７ｔ＝ｍ，；常数ｔ，是个定值，所以ｔＴ＇＝ｔ，；第４步的运算中没有引入差分，所以ｂ，Ｉ－ｂ，。设西７＝Ｆ（ｃ２，ｄ２，ａ２）＝（ｃ２

同样的定义ｌｌ『ｔ。Ａｄ２）Ｖ（，ｃ２Ａａ２），同样的定义巾’；ｌＩ，７＝ｂｌ＋Ｆ（ｃ２，ｄ２，ａ２）＋ｍ７＋ｔ７，

应用Ｆ函数的性质，对第八步的Ｆ函数进行研究：

１．采用Ｆ函数的第一个性质：Ｆ（ｘ，Ｙｚ）＝Ｆ（１）（＇Ｙｚ），当且仅当Ｙ＝Ｚ。第８步中ｄ２．ｉ－ａ２．ｉ，这个条件确保ｃ；的第ｉ比特的变化不会影响ｂ：，其中ｉ＝ｌ，２，４，５，２５，２７，２９，３０，３１。

２．采用Ｆ函数的第三个性质：Ｆ（Ｘ，Ｙｚ）＝Ｆ（Ｘ，Ｙ－Ｉｚ），当且仅当Ｘ＝Ｉ。第８步中１２２ｄ＝１，这个条件确保了ａ，的第ｉ比特的变化不会影响ｂ，，其中ｉ＝１３，１４，１５，１６，１７，１８，１９，２０，２１，２２，２３。

对第８步输出值ｂ，不变化的部分进行分析：１．ｃ：【１７］＝０，ａ：【１７】＝１确保ｂ：的第７比特没有变化。