https://blog.csdn.net/wufaliang003/article/details/79794982
小明：老師，上次您講了MD5算法。用它生成的資訊摘要，真的可以被破解嗎？
老師：有很多種方法可以破解，不過需要明确一點，這裡所謂的破解，并非把摘要還原成原文。為什麼呢？因為固定128位的摘要是有窮的，而原文數量是無窮的，每一個摘要都可以由若幹個原文通過Hash得到。
小明：如果是這樣的話，網上所說的MD5破解到底是怎麼回事呢？
老師：對于MD5的破解，實際上都屬于【碰撞】。比如原文A通過MD5可以生成摘要M，我們并不需要把X還原成A，隻需要找到原文B，生成同樣的摘要M即可。
設MD5的哈希函數是H（X），那麼：
H(A) = M
H(B) = M
任意一個B即為破解結果。
B有可能等于A，也可能不等于A。
用一個形象的說法，A和B的MD5結果“殊途同歸”。
MD5碰撞通常用于登陸密碼的破解。應用系統的資料庫中存儲的使用者密碼通常都是原密碼的MD5哈希值，每當使用者登入時，驗簽過程如下：
如果我們得到了使用者ABC的密碼哈希值E10ADC3949BA59ABBE56E057F20F883E，并不需要還原出原密碼123456，隻需要“碰撞”出另一個原文654321（隻是舉例）即可。登入時，完全可以使用654321作為登陸密碼，欺騙過應用系統的驗簽。
小明：那麼，具體如何來實作MD5摘要的碰撞呢？
老師：MD5碰撞的方法有很多，主要包括暴力枚舉法、字典法、彩虹表法等等。
暴力枚舉法：
老師：暴力枚舉法顧名思義，就是簡單粗暴地枚舉出所有原文，并計算出它們的哈希值，看看哪個哈希值和給定的資訊摘要一緻。這種方法雖然簡單，但是時間複雜度極高。想象一下，僅僅長度8位的密碼就有多少種排列組合的可能性？
小明：隻考慮大小寫字母和數字，每一位有62種可能，那麼8位密碼的排列組合就是62的8次方，218340105584800，約等于二百萬億！
老師：是的，這樣的資料量如果使用普通的單機來破解，恐怕頭發白了也破解不完。不過，我們也可以做一些取巧，優先嘗試生日和有意義的單詞，這樣就可以把窮舉範圍縮小很多。
字典法：
老師：如果說暴力枚舉法是ongoing時間換空間，那麼字典法則是用空間換時間。黑客利用一個巨大的字典，存儲盡可能多的原文和對應的哈希值。每次用給定的資訊摘要查找字典，即可快速找到碰撞的結果。
不過，這樣做雖然每次破解速度很快，但是生成字典需要巨大的空間。仍然以8位密碼舉例，需要多大空間呢？
小明：剛才計算過有218340105584800種可能性，每一對映射占192（128+64）bit。那麼大約需要4.65PB的存儲空間。
老師：沒錯，這樣做的存儲成本實在太大了。當然，我們同樣可以取巧，優先存儲那些常用的密碼及其摘要。
小明：那麼，有沒有什麼方法可以做到時間和空間的均衡呢？
老師：有一種方法可以，那就是下面我要介紹的【彩虹表發】。
彩虹表法：
老師：彩虹表法可以說是對字典法的優化，它采用了一種有趣的資料結構：【彩虹表】。在學習彩虹表之前，我們先來了解兩個基本函數：H(X)和R(X)。
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次為止。
簡單來說，哈希連結清單代表了一組映射關系，其中每組包含K對映射，但隻需要存儲鍊條首位兩個字元串。假設K=10，那麼存儲空間隻有全量字典的十分之一，代價則是破解一個摘要的運算次數也提高了十倍。這就是時間和空間的取舍。雖然做了取舍，但是哈希鍊條存在一個緻命的缺陷：R（X）函數的可靠性。雖然我們盡量把R（X）設計成結果均勻分布的函數，但是再完美的函數也難免會有碰撞的情況，比如下面這樣：
給定資訊摘要：FB107E70
經過多次R（X），H（X）運算，得到結果kiebgt
通過哈希表查找末端kiebgt，可以找出首端aaaaaa
但是，FB107E70并不在aaaaaa到kiebgt的哈希鍊條當中，這就是R（X）的碰撞造成的。
這個問題看似沒什麼影響，既然找不到就重新生成一組首尾映射即可。但是想象一下，當K值較大的時候，哈希鍊很長，一旦兩條不同的哈希鍊在某個節點出現碰撞，後面所有的明文和哈希值全都變成了一毛一樣的值。
這樣造成的後果就是備援存儲。原本兩條哈希鍊可以存儲 2K個映射，由于重複，真正存儲的映射數量不足2K。
這個時候，我們設計了彩虹表。彩虹表對哈希鍊進行了改進，把原先的R（X）的函數改進成從R1（X）到Rk（X）一共K個衰減函數。這樣一來雖然也可能發生碰撞，但是碰撞隻會發生在同一級運算，如R1和R1碰撞，R3和R3碰撞，大大減小了存儲重複的幾率。
小明：好複雜，聽的頭都暈了。那想要破解MD5算法，有沒有比彩虹表更厲害的方法呢？
老師：還真有。
2004年，王小雲教授提出了非常高效的MD5碰撞方法。
2009年，馮登國、謝濤利用差分攻擊，将MD5的碰撞算法複雜度進一步降低。
有興趣的小夥伴可以通過資料進行更深入的學習。
幾點補充：
對于單機來說，暴力枚舉法的時間成本很高，字典法的空間成本很高。但是利用分布式計算和分布式存儲，仍然可以有效破解MD5算法。是以這兩種方法同樣被黑客們廣泛使用。
————————————————
版權聲明：本文為CSDN部落客「HelloWorld搬運工」的原創文章，遵循 CC 4.0 BY-SA 版權協定，轉載請附上原文出處連結及本聲明。
原文連結：https://blog.csdn.net/wufaliang003/article/details/79794982