本文目的

在我的上一篇文章《 》中，我描述了md5算法的基本步驟，今天跟大家分享一下破解md5的原理。參考文獻在文末，有興趣的讀者可以讀讀。

符號

文本中出現諸如M0，M1，以粗體字母+非粗體數字組合的符號等同於公式中該字母和以該數字作為下標的符號。

MD5算法回顧

首先我們來大概回顧一下MD5算法。

1. 填充。將消息E的長度進行填充，使其滿足對512取餘為448。
2. 補充數據長度。將原消息以64位表示，並添加到填充的數據之後，我們得到M。
3. 初始化緩存器。A：01 23 45 67；B：89 ab dc ed；C：fe dc ba 98；D：76 54 32 10。A，B，C，D都是32位的緩存器，在下一步運算中使用。
4. 進行迭代處理。M的長度是512的整數倍（448+64），我們將數據M以512長度為單位進行劃分，此時M=（M0,M1,M2....M(N-1)），在運算中我們將這512位用16個32位的數來表示。接下來，我們對M進行遍歷，對其中的每一項進行四輪運算，每一輪都要進行16則計算，計算的結果緩存到A，B，C，D緩存器中，並對下一次迭代產生影響。
5. 輸出。我們從A的低位字節開會，到D的高位字節結束，每一個都是32位，最終拼接的結果就是4*32 = 128位，這就是MD5計算的結果。

上述迭代的過程我們稱之為雜湊運算。可以描述成這樣：

公式中的Mi表示為M中下標為i的元素，H0是緩存器中的初始值（A，B，C，D），Hi表示第i-1輪中緩存器中的結果，四輪運算我們抽象成函數f。

差分攻擊簡介

哈希函數最重要的分析方法是差分攻擊，同時也是分析分組密碼最重要的方法之一。差分攻擊大部分是使用異或運算的異或差分攻擊，由Eli Biham和Adi Shamir在分析類似DES加密體系的安全性中提出的，他們描述差分密碼分析是一種分析純文本對（原文）中的特殊差異對產生的密碼文本對的差異的影響的方法。

在本文中，我們使用整數模減（(A-B) mod C）來進行差分分析。

差分攻擊原理

兩個數之間的差我們表示為：

對於M=（M0,M1,M2,....,M(N-1)）和M'=（M0',M1',M2',....,M(N-1)'）。哈希函數的整個過程的差我們可以表示為：

在上式中，△H0表示初始值（A，B，C，D）之間的差，顯然是0。△H表示最終兩個消息之間的差，△Hi表示在第i次迭代之後結果的差，當然也是下次迭代的初始差值。我們的目標很簡單，假如我們使得最終的結果△H=0的話，也就是M和M'的哈希結果是一樣的，M和M'就產生了碰撞。

差分優化

要想使得碰撞發生，即△H為0，需要滿足的充分條件多達290多條（N=2），分佈在每一輪運算的計算上，附錄中給出了表格。要想滿足這些條件，提高碰撞的可能性，我們使用消息修改技術。有兩種修改方式。

1、對於任意的消息塊（Mi,Mi'）第一輪運算的非0“差”。

其中△R，第二個下標表示輪數。我們通過修改Mi的值，保證在第一輪運算中滿足差分的條件。

2、使用多消息修改機制，我們不僅能保證第一輪運算滿足充分條件，同時也能都大幅提高第二輪運算條件滿足的幾率。

MD5差分攻擊

對於MD5的差分攻擊，同其他哈希函數大同小異。這裡我們攻擊的目標是1024位M=（M0,M1）的消息體。我們的目的就是根據差分值計算M'=（M0',M1'）,使得MD5(M)=MD5(M')。

步驟描述如下：

1. 隨機產生M0
2. 使用消息修改算法修改M0，使之儘量滿足充分條件；
3. 如果所有的充分條件都滿足，則計算MD5的輸出並將其作為後半部分的鏈接變量，如果不滿足，則回到第2步，重新隨機選擇；
4. 隨機產生M1
5. 使用和前半部分相同的方法計算後半部分的輸出。需要注意的是，後半部分計算使用的鏈接變量初始值為前半部分的輸出

總結

該攻擊方法只用於尋找產生碰撞的消息對，對於實際應用來說，滿足差分的充分條件的幾率很小。

參考文獻

1. Xiaoyun Wang,Hongbo Yu,How to Break MD5 and Other Hash Functions
2. E. Biham, A. Shamir. Differential Cryptanalysis of the Data Encryption Standard
3. The MD5 Message-Digest Algorithm

附錄

摘自王小云論文

摘自王小云論文

關注技術大白，帶你閱讀技術書籍，瞭解技術內幕！