算法學習——漫畫：如何破解MD5算法？

作者：玻璃貓；
來源：程序員小灰

在之前的漫畫中，我們介紹了MD5算法的基本概念和底層原理，沒看過的小夥伴們可以點擊下面的鏈接：

算法學習——漫畫：什麼是MD5算法？（推薦）

這一次，我們來講解如何破解MD5算法。

設MD5的哈希函數是H（X），那麼：

H(A) = M

H(B) = M

任意一個B即為破解結果。

B有可能等於A，也可能不等於A。

用一個形象的說法，A和B的MD5結果“殊途同歸”。

MD5碰撞通常用於登陸密碼的破解。應用系統的數據庫中存儲的用戶密碼通常都是原密碼的MD5哈希值，每當用戶登錄時，驗簽過程如下：

如果我們得到了用戶ABC的密碼哈希值E10ADC3949BA59ABBE56E057F20F883E，並不需要還原出原密碼123456，只需要“碰撞”出另一個原文654321（只是舉例）即可。登錄時，完全可以使用654321作為登陸密碼，欺騙過應用系統的驗籤。

暴力枚舉法

字典法

彩虹表法

H（X）：生成信息摘要的哈希函數，比如MD5，比如SHA256。

R（X）：從信息摘要轉換成另一個字符串的衰減函數（Reduce）。其中R（X）的定義域是H（X）的值域，R（X）的值域是H（X）的定義域。但要注意的是，R（X）並非H（X）的反函數。

通過交替運算H和R若干次，可以形成一個原文和哈希值的鏈條。假設原文是aaaaaa，哈希值長度32bit，那麼哈希鏈表就是下面的樣子：

這個鏈條有多長呢？假設H（X）和R（X）的交替重複K次，那麼鏈條長度就是2K+1。同時，我們只需把鏈表的首段和末端存入哈希表中：

給定信息摘要：920ECF10

如何得到原文呢？只需進行R（X）運算：

R（920ECF10） = kiebgt

查詢哈希表可以找到末端kiebgt對應的首端是aaaaaa，因此摘要920ECF10的原文“極有可能”在aaaaaa到kiebgt的這個鏈條當中。

接下來從aaaaaa開始，重新交替運算R（X）與H（X），看一看摘要值920ECF10是否是其中一次H（X）的結果。從鏈條看來，答案是肯定的，因此920ECF10的原文就是920ECF10的前置節點sgfnyd。

需要補充的是，如果給定的摘要值經過一次R（X）運算，結果在哈希表中找不到，可以繼續交替H（X）R（X）直到第K次為止。

給定信息摘要：FB107E70

經過多次R（X），H（X）運算，得到結果kiebgt

通過哈希表查找末端kiebgt，可以找出首端aaaaaa

但是，FB107E70並不在aaaaaa到kiebgt的哈希鏈條當中，這就是R（X）的碰撞造成的。

這個問題看似沒什麼影響，既然找不到就重新生成一組首尾映射即可。但是想象一下，當K值較大的時候，哈希鏈很長，一旦兩條不同的哈希鏈在某個節點出現碰撞，後面所有的明文和哈希值全都變成了一毛一樣的值。

這樣造成的後果就是冗餘存儲。原本兩條哈希鏈可以存儲 2K個映射，由於重複，真正存儲的映射數量不足2K。

2004年，王小云教授提出了非常高效的MD5碰撞方法。

2009年，馮登國、謝濤利用差分攻擊，將MD5的碰撞算法複雜度進一步降低。

幾點補充：

對於單機來說，暴力枚舉法的時間成本很高，字典法的空間成本很高。但是利用分佈式計算和分佈式存儲，仍然可以有效破解MD5算法。因此這兩種方法同樣被黑客們廣泛使用。