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

Hash函数MD5攻击技术研究

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

３．２．２比特跟踪技术的应用

文献１１７１是用两个明文块（Ｍ。，Ｍ，），明文长度共为１０２４比特，对应的差分明文块为（Ｍ。’，Ｍ１’），经过两次ＭＤ５运算，（Ｍｏ，Ｍ１）和（Ｍｏ’，Ｍ。’）产生相同的Ｈａｓｈ值，这就成功找到了碰撞。本文通过对第一次ＭＤ５迭代运算的前８步进行研究，所以只关注Ｍｏ和Ｍｏ’，其中：ＡＭｏ＝Ｍｏ＇－Ｍｏ＝（０，０，０，０，２３１，０，０，０，０，０，０，２１５，０，０，２３１，０）。从这里可以看出，ｍ。开始引入差分，本文结合文献【１７】，以前８步为例，介绍比特跟踪技术对差分路径的控制。

第５步分析：

第５步的表达式：ａ２＝ｂ。＋（（ａ１＋Ｆ（ｂ１，Ｃａ，ｄ１）＋ｍ４＋ｔ４）＜＜＜７），开始引入了差分，

＆ｒｎ。＝２３１，在前４步的过程中，明文没有引入差分，所以ａｘ，ｂ，，Ｃ１，ｄ，都没有出现差分，即８１＝ａ１’，ｄｌ＝ｄ１’，ｃａ＝Ｃ１’，ｂｌ＝ｂ１’。Ａａ２＝（△ｌＩ，４【３１】＜＜＜７）＝（（一２３１）＜＜＜７）＝－２６。根据基础知识，第３２比特的“＋”和“．”是相同的，所以，此时明文引入的差分２３１，看成．２３１来处理，经过循环左移，△ａ，的模差分为．２６，为了下面步骤的需要，需要将这个模差分进行扩展，满足ａ２【＋７，＋８，＋９，…，＋２２，．２３】。此时要求ａ２，７＝ａ２，８＝ａ２，９＝…＝ａ２刀＝Ｏ，ａ２，２３＝１。

第６步分析：

第６步的表达式：ｄ２－－ａ２＋（（ｄ１＋Ｆ（ａ２，ｂ１，ｃ１）＋ｍ５＋ｔ５）＜＜＜１２），这步明文Ａｍ５＝Ｏ，

Ａｄ２＝Ａａ２＋（△Ｖ５＜＜＜１２），Ａｄ：的差分由两部分组成：首先，△ｄ：继承了Ａａ２＝．２６这部分的值；其次，（胛。＜＜＜１２）产生了后面所需要的差分２２３＋２３１。

根据前面的基础知识，为了达到这个目标，需要充分利用Ｆ函数的性质：

１．利用Ｆ（Ｘ，Ｙｚ）＝Ｆｎｘ，ＹＺ），当且仅当Ｙ＝Ｚ。第６步中ｂ。ｊ＝ｃｌｊ，这个条件确保ａ：的第ｉ比特的变化不会影响ｄ：，其中ｉ＝７，８，９，１０，１１，１３，１４，１５，１６，１７，１８，１９，２１，２２，２３。

２．２２３＋２３１是由胖，［１２】和Ａｑｓ，［２０】经过循环左移１２比特形成的。此时由于没有差分的扩展，满足Ａｑｓ，［１２】＝△中，【１２】＝１，胛；［２０１＝Ａ①，［２０１＝１。此时要求ｂｚ［１２１－％［１２１＝１，ｂｌ［２０１－ｑ［２０１＝１，即ｂｌ【１２】＝１，％［１２１＝０，ｂｘ［２０１＝１，ｃａ［２０］＝Ｏ（见文献【１７】表４）。

第７步分析：

第７步表达式：ｃ２＝ｄ２＋（（Ｃｌ＋Ｆ（ｄ２，ａ２，ｂ１）＋ｍ６＋ｔ６）＜＜＜１７），这步明文ａｍ６＝Ｏ，

Ａｃ：＝Ａｄ，＋ＯＦ。＜＜＜１２），同第６步的分析一样，△ｃ，的差分由两部分组成：

１．Ａｃ２继承了Ａｄ２＝－２６＋２２３这部分的值，而且都进行了扩展，ｃ２【７，８，９，１０，１１，－１２】这些变化都是由．２６引起的：设Ｃ：。的第７到１２比特为？？？？？？，由于Ｃ２嘲＝０，其中ｉ＝７，８，９，１０，１１，Ｃ２【１２】－１，差分计算？？？？？７．１０００００＝．２６，这样就实现了Ｃ２【７，８，９，１０，１１，一１２】的变化。同理，２２３导致了ｃ２【－２４，－２５，－２６，２７】的变化。