什麼是彩虹表？

---

2014.5.2更新：補充了彩虹表的一些關鍵特性（感謝 @Rubin Xu ）；同時重寫了答案中的所有例子。 2016.3.19更新：評論中有些人在問R函數的問題，又搜索資料補充了一節。

以前我也跟其他很多人一樣，認為彩虹表就是描述「明文-&>密文」對應關係的一個大型資料庫，破解時通過密文直接反查明文。
今天因某些需要而詳細了解了彩虹表的一些細節，才發現其原理比之前想像的更值得稱讚。它所謂的time-memory trade-off，並不是簡單地「以空間換時間」，而是雙向的「交易」，在二者之間達到平衡。
在此分享一些心得。本部分內容本答案主要參考資料為英文維基的Rainbow table詞條（Rainbow table）。答案末尾分隔線後附上一個簡化的比喻，希望能給更多的人說清楚這個問題。

• 彩虹表的前身

在彩虹表之前，已經出現了對哈希函數的破解演算法，被稱為「預計算的哈希鏈集」（Precomputed hash chains）。
當面對要破解的哈希函數H，首先要定義一個約簡函數（reduction function）R，該函數的定義域和值域需要和哈希函數相反，通過該函數可以將哈希值約簡為一個與原文相同格式的值（"plain text" value）。需要強調的是，由於哈希函數H是不可逆的，所以對於密文進行R運算幾乎不可能得到明文原文。例如，五位字母明文「zhihu」進行H運算後得到了「D2A82C9A」，而對「D2A82C9A」進行R運算後得到另一個五位字母格式的值「vfkkd」。因為這個值落在H的定義域中，因此可以對它繼續進行H運算。
就這樣，將H運算、R運算、H運算……這個過程反覆地重複下去，重複一個特定的次數k以後，就得到一條哈希鏈，例如k為2時得到：

這條鏈條並不需要完整地保存下來，只需要保存其起節點和末節點即可，例如上例中只需要保存起節點「zhihu」和末節點「crepa」。以大量的隨機明文作為起節點，通過上述步驟計算出哈希鏈並將終節點進行儲存，即可得到一張哈希鏈集。
這張集合需要如何使用呢？例如，我們知道哈希運算後的密文為「0CAFC376」，則先對其進行一次R運算，得到「crepa」。

正巧在本例中，它等於集合中的一個末節點，因此我們可以猜測，明文有極大的可能存在於以起節點「zhihu」開頭、末節點「crepa」結尾的這條哈希鏈中。（注意可能性並不是100%，因為函數H和R均有可能發生碰撞，從不同的輸入值得到相同的輸出值。）
為了驗證我們的猜測，可以從起節點「zhihu」開始重複哈希鏈的計算過程：

算到這裡我們發現，「vfkkd」進行哈希運算的結果正是密文「0CAFC376」，這樣就找到了所需的明文。
如果密文不是「0CAFC376」而是「D2A82C9A」，第一次R運算後的結果並未在末節點中找到，則再重複一次H運算+R運算，這時又得到了末節點中的值「crepa」，則我們還是從起節點「zhihu」開始計算，這次可得到「D2A82C9A」對應的明文為「zhihu」。
如果如是重複了k（=2）次之後，仍然沒有在末節點中找到對應的值，則可以斷定，所需的明文不在這張集合中——集合中並未儲存長度大於k的哈希鏈，因此再計算也沒有意義了。
如果讓我來解釋哈希鏈的意義，我認為，每一條哈希鏈實際上是代表了屬性相同的一組明文：每一個明文都可以通過起節點迅速的計算得出，計算次數不大於k，因而可以大大節約時間。對每一組明文，只需要保存其特徵值（起節點和末節點），儲存空間只需約1/k，因而大大節約了空間。

• R的問題

在構造哈希鏈的時候，一個優秀的函數R功不可沒。首先R需要能將值域限定在固定的範圍——例如給定的長度範圍、給定的字元取值範圍等等——之內，否則的話，哈希鏈中大量的計算結果並不在可接受的取值範圍內，一條鏈條無法對應多個明文，鏈條就失去了意義；其次R必須同哈希函數一樣，盡量保證輸出值在值域中的均勻分布，減少碰撞的概率。
然而實際上，很難找到能滿足這些需求的完美的R函數。當計算中發生碰撞時，就會出現如下的情況：

圖中加粗的部分，所涉及到的明文是完全重複的，因此這兩條哈希鏈能解密的明文數量就遠小於理論上的明文數2×k。不幸的是，由於集合只保存鏈條的首末節點，因此這樣的重複鏈條並不能被迅速地發現。隨著碰撞的增加，這樣的重複鏈條會逐漸造成嚴重的冗餘和浪費。

• 彩虹表的改進點

對於這個問題，2003年提出的彩虹表演算法進行了針對性的改進。它在各步的運算中，並不使用統一的R函數，而是分別使用R1…Rk共k個不同的R函數（下劃線表示下標）。這樣生成的哈希鏈集即被稱為彩虹表。（在不同的運算位置使用不同的R函數，就像彩虹由內而外的不同位置上顯示出不同的顏色一樣。）這樣一來，如果發生碰撞，通常會是下圖的情況：

不難發現，當兩個鏈條發生碰撞的位置並非相同的序列位置時，後續的R函數的不一致使得鏈條的後續部分也不相同，從而最大程度地減小了鏈條中的重複節點，保證了鏈條的有效性。
同時，如果在極端情況下，兩個鏈條有1/k的概率在同一序列位置上發生碰撞，導致後續鏈條完全一致，這樣的鏈條也會因為末節點相同而檢測出來，可以丟棄其中一條而不浪費存儲空間。
彩虹表的使用比哈希鏈集稍微麻煩一些。首先，假設要破解的密文位於任一鏈條的k-1位置處，對其進行Rk運算，看是否能夠在末節點中找到對應的值。如果找到，則可以如前所述，使用起節點驗證其正確性。否則，需要繼續假設密文位於k-2位置處，這時就需要進行Rk-1、H、Rk兩步運算，然後在末節點中查找結果。如是反覆，最不利條件下需要將密文進行完整的R1、H、…Rk運算後，才能得知密文是否存在於彩虹表之中。

• 時間、空間的平衡

通過彩虹表的使用方法可以明顯地看出，一條哈希鏈實際代表的是一組明文的解密規則：

等價於k條子規則：

類似的，前述的哈希鏈集也可以進行這樣的拆解，只不過其拆解後的子規則的運算過程中有很多中間結果可以復用，因此其最大計算次數為k，平均計算次數為；而彩虹表的最大計算次數為，平均計算次數為。可見，要解相同個數的明文，彩虹表的代價會高於哈希鏈集。不過，因為彩虹表可以節省不少重複鏈條的存儲和計算的代價，所以還是值得的。
同時，對於相同個數的明文，當k越大時，破解的期望時間就越長，但彩虹表所佔用的空間就越小；相反，k越小時，彩虹表本身就越大，相應的破解時間就越短。這正是保持空間、時間二者平衡的精髓所在。RainbowCrack中rtgen工具使用的默認k值好像是2100。極端的，令k=1，簡化函數R(x)=x，這樣的彩虹表就變成了通常的錯誤理解，即將明文、密文對應關係全部保存的表。此時由於k極小，因而得到的表的體積極大，甚至可能超出儲存能力。（當然，對於範圍較小的明文，如6位以下數字英文的組合，或是全世界常用密碼的集合，生成k=1的表還是不費什麼事的。）

• 再談R函數

先重複一下前面所說的R函數所需的性質：

1. R需要能將值域限定在固定的範圍之內。事實上，在計算和下載彩虹表時，不同類型的猜解範圍是需要用不同的庫的，例如下載網站List of Rainbow Tables上，按照不同的哈希函數、字符集、密碼長度等分為很多個不同的庫，這些庫所使用的R函數都是不一樣的，這樣才能保證R函數的值域和所需的猜解範圍保持一致。
2. R需要盡量保證輸出值在值域中的均勻分布，減少碰撞的概率。對於碰撞的檢測和處理在前面已經有過說明。

當然，這兩點性質並不能保證R是H的反函數——按照哈希函數的定義，H的反函數預期是不存在的。我們可以參考一些演示用的R函數，來看看它是什麼樣的情況：

1. 本例來自hash - Example Rainbow Table Generation，其中假設明文為5位數字，則R函數是取哈希值中前5個數字。例如，對於明文，H(A)=827ccb0eea8a706c4c34a16891f84e7b，則；H(B)=71b8e22700e63c2a0c1bad6506549d3b，則，以此類推。（這個R函數其實是有點問題的，當哈希值中的數字少於5個時，如果處理不好可能導致均勻性被破壞。）
2. 本例來自rainbowtable，將R函數定義為哈希值在值域範圍大小內的求余結果，即。可推廣的是，當彩虹表中需要用到R1、R2、……、Rk共k個R函數時，可以令快速得到。理論上，此函數是一個可以用於任意猜解範圍的通用R函數，遺憾的是看上去求余運算會大大拖慢運算的速度。

由上述例子可以看出，一般而言，R的第1條性質是由開發者自行限制保證的，而第2條性質是利用H函數生成的哈希值本身的均勻性。
實際中，不同的彩虹表工具使用的R函數是各不相同的。如果有條件的話，我再補充一下實際代碼中用到的R函數。

• 彩虹表的防禦

關於彩虹表的防禦方式，大多與彩虹表的原理，即其生成步驟中用到的函數H有關。
最常用的方法，在其它的答案中也提到了，那就是加鹽（salt），這其實是改變了哈希函數H的形式。由於彩虹表在生成和破解的過程中，都反覆用到了函數H，H如果發生了改變，則已有的彩虹表數據就完全無法使用，必須針對特定的H重新生成，這樣就提高了破解的難度。
防禦彩虹表的另一種方法是提高H函數的計算難度，例如將H定義為計算一千次MD5後的結果。由於H在演算法中的重複性，當單次H函數的計算耗時增加，意味著彩虹表的生成時間會大大的增加，從而也能提高破解的成本。

===========簡化比喻的分隔線==============

如果將哈希後的密文比作一把鎖，暴力破解的方法就是現場製作各種各樣不同齒形的鑰匙，再來嘗試能否開鎖，這樣耗時無疑很長；我以前錯誤理解的「彩虹表」，是事先製作好所有齒形的鑰匙，全部拿過來嘗試開鎖，這樣雖然省去了製作鑰匙的時間，但是後來發現這些鑰匙實在是太多了，沒法全部帶在身上。而真正的彩虹表，是將鑰匙按照某種規律進行分組，每組鑰匙中只需要帶最有特點的一個，當發現某個「特徵鑰匙」差一點就能開鎖了，則當場對該鑰匙進行簡單的打磨，直到能開鎖為止。這種方法是既省力又省時的。

---

通俗點就是個一竄鑰匙圈 大小決定鑰匙的數量 鑰匙數量越大 開門幾率越大 破解密碼或MD5的值幾率就越大

---

把各種可能的密碼按照一定的方式處理，例如哈希加密後生成的數據表，拿到密碼的哈希值時，從哈希值反查原始密碼

---

對哈希加密的攻擊，可以分為兩種。第一種是猜。這種攻擊有字典攻擊和暴力攻擊。字典攻擊是事先做好字典去猜，暴利攻擊是窮舉給定長度的各種字元的組合。第二種是查。就是知道哈希值後希望破譯明文，這需要建立密文對應於明文的字典庫。彩虹表其實也相當於一種字典，不過它是用一種哈希鏈的存儲方式去存儲字典，在儲存上只需要保存這個鏈的首尾的值就可以，中間值通過哈希函數推算。彩虹表做到了時間和空間的平衡。

---

綜上，彩虹表就是利用常用的加密方法，窮舉一定範圍內的明文，利用密文索引它，然後找到密文後，通過密文就能得到明文了。

---

對於不可逆的加密如md5
那麼最簡單的破解就是構造一個巨大的彩虹表rainbow table

簡單說就是窮舉可能的密碼組合，比如遍歷所有9位數字，從10000,0000到99999,9999
將每個數字的md5 hash散列存入資料庫。

然後當用戶查詢某個加密後的字元串md5 hash時，就去這個資料庫里查詢挨個比對，如果能查到，就可以反推出原字元串是多少。如果查不出來，也只能說明這個rainbow table不夠大，沒有包含用戶的密碼,本質上這就是一種暴力攻擊brute force attack

一般來說，最簡單的提升加密強度的方法就是「加鹽」，所謂的salt,這樣的話，能極大提升攻擊成本，因為對於每位用戶的密碼，都加不同的salt,這樣你每破解一個用戶的密碼，都需要重建一次彩虹表。

但我個人更推薦，md5+salt+自己的演算法，這種雜揉的方式

舉個簡單例子，比如md5+salt後字元串是AAAABBBBCCCC
那在自己演算法處理後變成也變成一個類似散列，這樣黑客拿到這個散列去「碰撞密碼」不可能得到真實密碼，因為這個散列本身就是變形後的，所有的提供公開密碼破解碰撞服務的網站，都不可能單獨為某一個單獨的網站（比如你的）開發一個新的解密借口，一般頂多是常用的論壇/cms,如 discuz/dedecms這些加密方式會被收錄。

所以這樣能最大保證，當你的網站資料庫泄露後，用戶的數據不受影響
當然如果你的全站被端，核心加密演算法被得知，那的確還是會有影響的
anyway,你能防住99%的script kids就可以了，1%的高手如果真盯上你，你首先應該感到榮
幸。

黑客們除了自己建的彩虹表，一般常去的網站是cmd5.com,我從2007年起就經常使用它，很少讓我失望 : )

---

@Smallay 講的很好，補充剛看到的文章吧。

科普：彩虹表破解開機密碼、MD5演算法等的原理_91Ri.org

---

1. 破解時間和存儲空間的trade-off
2. 與之對應的兩個極端是窮搜索與查表法
3. 彩虹表的原理是計算少量數據，但是它們可以用來推演出全部的數據（這裡就不展開了，看看wikipedia 上咋說吧）
4. 彩虹表的不足之處也在推演的方法上。加個隨機字元串（可以明文存儲；重複率不高即可）即可 (鹽, salt) 防禦彩虹表

---

你們說的我看不懂，我以為是彩虹手錶，我以前在韓國展覽會見過，在黑暗環境下能發出彩虹色的光，白天不怎麼明顯，但手錶內殼也是彩色的，缺點就是指針略有點看不清，後來再沒見過，好像沒上市。

---

推薦閱讀：