概念

差分攻击是通过比较分析有特定区别的明文在通过加密后的变化传播情况来攻击密码算法的。差分攻击是针对对称分组加密算法提出的攻击方法，看起来是最有效的攻击DES的方法（之所以说看起来，是因为差分攻击需要很大的空间复杂度，实际上可能不如野蛮攻击具有可操作性）。2000年以前，差分攻击就被证明对MD5的一次循环是有效的，但对全部4次循环似乎难以奏效。但是随着对MD5研究的进展，情况有了变化。

2005年，王小云、来学嘉等使用差分攻击的思路，提出了对MD5差分的攻击方法。该方式提出了充分条件的概念，并列出了一系列的充分条件（大约有290个），如果这些充分条件都能得到满足，那么一定能产生碰撞。于是MD5的强抗碰撞性不能得到满足，即该攻击方法可以寻找消息对，使得。不过，这一系列的充分条件很难同时满足。尽管王小云、来学嘉等进一步提出了消息修改算法，通过修改相应比特位的方法来达到满足这一系列充分条件，但是仍然有37条充分条件不能满足。这就意味着，从理论上来讲，该算法只需测试条随机消息就可以找到完全满足充分条件的消息对，从而找到碰撞，即。这是一个相当有意义的成果，意味着任何人在自己的笔记本上都可以计算出碰撞的消息对。当然，这里产生碰撞的消息对是随机的。

这里概要描述一下MD5的差分攻击方法。和分别表示两个不同的512比特的消息，其中，各为32比特的字串。记是和之间的差，。表示函数输出的差分。差分攻击通过计算合理的后续消息串使最后输出的差分为零，最终算法能产生两个1024比特的消息串和，使得。该算法在攻击过程中制定了差分值，算法设计者认为指定的差分值可以使最后完全消除输出差分的概率较大。

工作原理

MD5算法的链接变量就是最后输出的函数值，初始状态的链接变量都是相同的，所以。

如果确定了1024比特消息串，根据制定的输入差分值，也能确定。满足输入差分条件后，显然，并不是任何一对1024比特消息串和对应的都能满足输出差分条件。算法设计者提出了290条充分条件，只有满足这些充分条件的一对消息串才能满足所有的输入/输出差分。充分条件是一系列对MD5链接变量的限制条件。由于MD5算法由若干轮计算构成，每轮计算都会更新链接变量，所以不同的轮都有不同的充分条件。这样，全部的充分条件的数量达到了290条。随机选取一条消息，使之满足全部充分条件的概率是微乎其微的。于是算法设计者进一步提出了消息修改算法，该算法可以使MD5计算过程中第一轮中所有的充分条件和第二轮中一部分充分条件能够满足。经过消息修改以后，仍然会有37条充分条件不能得到满足。如果随机选取的消息经过消息修改后不能满足最后37条充分条件，就重新随机选取新的消息，直到满足所有的充分条件为止。

差分攻击的算法可以描述如下：

（1）随机产生512比特的消息，作为1024比特消息串的前半部分；

（2）使用消息修改算法修改，使之尽量满足充分条件；

（3）如果所有的充分条件都满足，则计算MD5的输出并将其作为后半部分的链接变量，如果不满足，则回到第（2）步，重新随机选择；

（4）随机产生512比特的消息，作为1024比特消息串的后半部分；

（5）使用和前半部分相同的方法计算后半部分的输出。需要注意的是，后半部分计算使用的链接变量初始值为前半部分的输出。1

参考资料