在我的上一篇文章《MD5算法，看這篇就夠了》中，我描述了md5算法的基本步驟，今天跟大家分享一下破解md5的原理。參考文獻在文末，有興趣的讀者可以讀讀。
符號文本中出現(xiàn)諸如
M
0，M
1，以粗體字母+非粗體數(shù)字組合的符號等同于公式中該字母和以該數(shù)字作為下標的符號。MD5算法回顧首先我們來大概回顧一下MD5算法。
填充。將消息E的長度進行填充，使其滿足對512取余為448。補充數(shù)據(jù)長度。將原消息以64位表示，并添加到填充的數(shù)據(jù)之后，我們得到M。初始化緩存器。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位的緩存器，在下一步運算中使用。進行迭代處理。M的長度是512的整數(shù)倍（448+64），我們將數(shù)據(jù)M以512長度為單位進行劃分，此時M=（M
0,M
1,M
2....M
(N-1)），在運算中我們將這512位用16個32位的數(shù)來表示。接下來，我們對M進行遍歷，對其中的每一項進行四輪運算，每一輪都要進行16則計算，計算的結果緩存到A，B，C，D緩存器中，并對下一次迭代產(chǎn)生影響。輸出。我們從A的低位字節(jié)開會，到D的高位字節(jié)結束，每一個都是32位，最終拼接的結果就是4*32 = 128位，這就是MD5計算的結果。上述迭代的過程我們稱之為雜湊運算?？梢悦枋龀蛇@樣：
公式中的
M
i表示為M中下標為i的元素，H
0是緩存器中的初始值（A，B，C，D），H
i表示第i-1輪中緩存器中的結果，四輪運算我們抽象成函數(shù)f
。差分攻擊簡介哈希函數(shù)最重要的分析方法是差分攻擊，同時也是分析分組密碼最重要的方法之一。差分攻擊大部分是使用異或運算的異或差分攻擊，由Eli Biham和Adi Shamir在分析類似DES加密體系的安全性中提出的，他們描述差分密碼分析是一種分析純文本對（原文）中的特殊差異對產(chǎn)生的密碼文本對的差異的影響的方法。
在本文中，我們使用整數(shù)模減（(A-B) mod C）來進行差分分析。
差分攻擊原理兩個數(shù)之間的差我們表示為：
對于M=（
M
0,M
1,M
2,....,M
(N-1)）和M'=（M
0',M
1',M
2',....,M
(N-1)'）。哈希函數(shù)的整個過程的差我們可以表示為：在上式中，△
H
0表示初始值（A，B，C，D）之間的差，顯然是0。△H表示最終兩個消息之間的差，△H
i表示在第i次迭代之后結果的差，當然也是下次迭代的初始差值。我們的目標很簡單，假如我們使得最終的結果△H=0的話，也就是M和M'的哈希結果是一樣的，M和M'就產(chǎn)生了碰撞。差分優(yōu)化要想使得碰撞發(fā)生，即△H為0，需要滿足的充分條件多達290多條（N=2），分布在每一輪運算的計算上，附錄中給出了表格。要想滿足這些條件，提高碰撞的可能性，我們使用消息修改技術。有兩種修改方式。
1、對于任意的消息塊（
M
i,M
i'）第一輪運算的非0“差”。其中△R，第二個下標表示輪數(shù)。我們通過修改
M
i的值，保證在第一輪運算中滿足差分的條件。2、使用多消息修改機制，我們不僅能保證第一輪運算滿足充分條件，同時也能都大幅提高第二輪運算條件滿足的幾率。
MD5差分攻擊對于MD5的差分攻擊，同其他哈希函數(shù)大同小異。這里我們攻擊的目標是1024位M=（
M
0,M
1）的消息體。我們的目的就是根據(jù)差分值計算M'=（M
0',M
1'）,使得MD5(M)=MD5(M')。步驟描述如下：
隨機產(chǎn)生M
0使用消息修改算法修改M
0，使之盡量滿足充分條件；如果所有的充分條件都滿足，則計算MD5的輸出并將其作為后半部分的鏈接變量，如果不滿足，則回到第2步，重新隨機選擇；隨機產(chǎn)生M
1使用和前半部分相同的方法計算后半部分的輸出。需要注意的是，后半部分計算使用的鏈接變量初始值為前半部分的輸出總結該攻擊方法只用于尋找產(chǎn)生碰撞的消息對，對于實際應用來說，滿足差分的充分條件的幾率很小。
參考文獻Xiaoyun Wang,Hongbo Yu,How to Break MD5 and Other Hash FunctionsE. Biham, A. Shamir. Differential Cryptanalysis of the Data Encryption StandardThe MD5 Message-Digest Algorithm附錄摘自王小云論文
摘自王小云論文
關注技術大白，帶你閱讀技術書籍，了解技術內幕！
1.《md5 MD5破解原理》援引自互聯(lián)網(wǎng)，旨在傳遞更多網(wǎng)絡信息知識，僅代表作者本人觀點，與本網(wǎng)站無關，侵刪請聯(lián)系頁腳下方聯(lián)系方式。
2.《md5 MD5破解原理》僅供讀者參考，本網(wǎng)站未對該內容進行證實，對其原創(chuàng)性、真實性、完整性、及時性不作任何保證。
3.文章轉載時請保留本站內容來源地址，http://f99ss.com/keji/346448.html