差分攻擊

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]