彩虹表

彩虹表（Rainbow table）是用於加密散列函數逆運算的預先計算好的表，常用於破解加密過的密碼散列。彩虹表常常用於破解長度固定且包含的字符範圍固定的密碼（如信用卡、數字等）。這是以空間換時間的典型實踐，比暴力破解（Brute-force attack）用的時間少，空間更多；但與儲存密碼空間中的每一個密碼及其對應的哈希值（Hash）實現的查找表相比，其花費的時間更多，空間更少。使用加鹽的密鑰派生函數可以使這種攻擊難以實現。

彩虹表是馬丁·赫爾曼早期提出的簡單算法^[1]的應用。

有三個reduction函數的簡化彩虹表

背景

每台需要密碼認證的計算機都包含一個儲存密碼的數據庫，密碼儲存方式有多種，如摘要或純文本。由於儲存密碼的表很容易被竊取，所以以純文本形式儲存密碼非常危險，大多數數據庫會儲存用戶密碼的加密摘要。在這種系統內，即使是認證系統本身都無法簡單地通過查表來獲得用戶密碼。當用戶輸入密碼時，系統會生成一個加密摘要與儲存的加密摘要比較，如果相同就允許訪問請求。

黑客在盜取到散列後的密碼表時，並不能僅憑藉輸入散列後的用戶的加密摘要來獲取權限（使用加密摘要作為輸入密碼並不可行，因為認證系統會把加密摘要再次加密，產生一個與儲存的加密摘要不匹配的摘要）。為了獲取用戶的密碼，黑客必須找到一個能產生相同加密摘要的密碼。

彩虹表是僅通過加密摘要來嘗試獲取用戶密碼的工具之一。

由於有更簡單的逆向散列運算（hash reversal）方法，彩虹表不一定會用到。相比之下，暴力破解法和字典攻擊是更簡單的破解方法。但這些方法在面對存儲了大量密碼的系統時會非常乏力，因為儲存用於逆向查找的所有選項以及搜索大型數據庫十分困難。

若要破解大型的密碼庫，則需要引入儲存相對較少，但可以逆向形成由長鏈密碼的散列值構成的逆向查找表。雖然破解單個的密碼時會花費更多的計算時間，但這會大大降低整體的字典大小，因而可以儲存更長的密碼散列值。彩虹表正是在此類鏈接技術的基礎上改進得到的一種支持碰撞鏈的密碼破解工具。

預先計算的散列鏈

註：這裡表達的散列鏈與哈希鏈中解釋的是不同的散列鏈。

假設有哈希方程H和有限的密碼集合P，需要預先計算出一個數據結構來決定哈希方程H的任一輸出結果h是否可以通過密碼集合P裡面的一個元素p經哈希函數H(p)=h得到。實現這一目的的最簡單的方法是計算出P集合內所有密碼p的哈希值H(p)。但是這個方法需要的儲存空間為Θ(|P|n)，（n代表哈希函數H的一個輸出值的大小）對於較大的|P|，其對於存儲空間的要求會過高。

哈希鏈可以用來減少對於儲存空間的需求。大致想法是通過定義一個歸約函數（reduction function）R來映射散列值h在集合P中對應的密碼p。（注意，這裡的歸約函數並不是真正意義上哈希函數的反函數。)通過交替施行哈希函數與歸約函數，形成交替的明文與哈希值。例如，假設P是6個字符的密碼集合，而哈希值有32比特長，那麼他們形成的長鏈可以表示作：

${\displaystyle \mathbf {aaaaaa} \,{\xrightarrow[{\;H\;}]{}}\,\mathrm {281DAF40} \,{\xrightarrow[{\;R\;}]{}}\,\mathrm {sgfnyd} \,{\xrightarrow[{\;H\;}]{}}\,\mathrm {920ECF10} \,{\xrightarrow[{\;R\;}]{}}\,\mathbf {kiebgt} }$

此處，對於歸約函數的唯一要求是，它能將任意哈希值映射成特定字符的純文本值。

為了生成查找表，可從集合P隨機選一子集，對子集每個元素計算長度為k的哈希鏈，然後只保存每條哈希鏈的初始和末尾密碼。初始密碼稱為起點，末尾密碼稱為終點。在上述哈希鏈的例子中，"aaaaaa"和"kiebgt"即為起點和終點，而哈希鏈中的其他密碼或者哈希值均不會保存。^{[來源請求]}

現在計算給定哈希值h0的逆（即找到對應的密碼），從哈希值h0開始輪流用函數R和H生成一條哈希鏈。如果哈希鏈任何節點與查找表的某個終點發生碰撞，就可以藉由與之對應的起點，重建對應的哈希鏈。而這個哈希鏈很可能包含了需要搜尋的哈希值h0，如果這樣的話，那麼它的前驅節點即為要尋找的密碼p0。^{[來源請求]}

例如哈希值920ECF10，首先施加函數R：

${\displaystyle \mathrm {920ECF10} \,{\xrightarrow[{\;R\;}]{}}\,\mathbf {kiebgt} }$

"kiebgt"在建立的查找表的終點集合中，所以藉由對應的起始密碼"aaaaaa"生成的哈希鏈，直到找到920ECF10：

${\displaystyle \mathbf {aaaaaa} \,{\xrightarrow[{\;H\;}]{}}\,\mathrm {281DAF40} \,{\xrightarrow[{\;R\;}]{}}\,\mathrm {sgfnyd} \,{\xrightarrow[{\;H\;}]{}}\,\mathrm {920ECF10} }$

因此，哈希值"920ECF10"的前驅節點"sgfnyd"即為搜尋的目標密碼。

注意，這裡的哈希鏈並不一定會有要找的哈希值h；可能以h開始的鏈會和起點在h鏈之後的某個查找鏈重合。例如，在以下情況，可以從FB107E70的哈希鏈中找到kiebgt：

${\displaystyle \mathrm {FB107E70} \,{\xrightarrow[{\;R\;}]{}}\,\mathrm {bvtdll} \,{\xrightarrow[{\;H\;}]{}}\,\mathrm {0EE80890} \,{\xrightarrow[{\;R\;}]{}}\,\mathbf {kiebgt} }$

但FB107E70並不在以"aaaaaa"開頭的鏈中。這情況稱為誤報（false alarm）。在這例子可忽略這個匹配然後繼續擴增h鏈同時尋找下個匹配。如果h的哈希鏈在擴增到長度為k後仍然沒有發生匹配，那麼與之對應的密碼一定不在查找表的任何哈希鏈中。

查找表的內容並不依賴於查詢的哈希值。它是在一次性建立之後，被無修改的重複用於查找。增加鏈的長度可以減小表的規模，但同時也會增加查詢時間，這就是彩虹表空間換時間的折中策略。在單元鏈的最簡單情況下，查詢速度會非常快，但表也會非常大。一旦鏈變得更長，查找速度也會降下來，但表的規模變得更小了。

簡單的哈希鏈方法有很多缺陷。最嚴重的問題是，如果兩條鏈中的任何兩個點碰撞（有同樣的值）了，他們後續的所有點都將重合，這將導致在付出了同樣的計算代價之後並不能使表儘可能多的覆蓋到密碼。由於鏈的前部並沒有整個的保存，這使得碰撞不可能有效檢測到。例如，如果鏈3的第三個值和鏈7的第二個值重合了，那麼這兩條鏈將覆蓋幾乎同樣的值，但他們的終點值卻不相同。哈希函數H本身不大可能產生碰撞，因為這就是它最重要的安全特性之一。但對於衰減函數R來說，由於他需要正確的覆蓋掉可能的明文（即之前討論的密碼），所以不會是抗碰撞的。

其他的困難是由選擇正確R函數的重要性導致的。選擇恆等映射作為函數R要比暴力搜索好一點。只有當攻擊者明確知道明文的可能取值是什麼時，他/她才需要選擇一個好的R函數使得時間和空間花費在這些可能的明文上，而不是整個可能的密文空間。儘管把R的取值限定到可能的明文空間能帶來好處，但它的弊端是攻擊者選擇的用於生成哈希鏈的明文子集可能並不能覆蓋所有的可能明文空間。設計一個能匹配明文期望分布的R函數也非常困難。

彩虹表

為了解決簡單的哈希鏈中的碰撞問題，彩虹表選用一系列相關的歸約函數R₁，…，R_k來代替原先的歸約函數R。這樣，如果兩條哈希鏈發生碰撞並且重合，那麼它們的碰撞必定發生在相同的位置，從而它們的終點也將相同。這樣可以通過後處理來排序哈希鏈，從而找出並移除所有終點相同，因而可能是重複的鏈，並生成新的鏈來將整個表補充完整。這樣得到的表中的鏈可能有碰撞的部分，但它們不會發生鏈的重合，從而大幅降低了碰撞的次數。^{[來源請求]}

採用歸約函數列代替歸約函數將改變查找的方式。因為給定的哈希值可能出現在哈希鏈任意位置，需要計算k條不同的鏈：首先假定給定的哈希值出現在哈希鏈最後一位（此時只需施加函數R_k），然後假定哈希值出現在哈希鏈尾二位（此時依次施加函數R_k-1，H和R_k），依此類推，直至找到所需密碼。注意，如果錯誤假定了目標哈希值在哈希鏈的位置，可能會得到一條與表中的鏈部分重合的鏈，從而產生誤報。

常見用途

幾乎所有Unix，Linux和BSD的發行版和變體都使用哈希值，儘管許多應用程序只使用沒有鹽的哈希（通常是MD5）。Microsoft Windows NT / 2000系列使用LAN Manager和NT LAN Manager散列方法（基於MD4）並且也是無保留的，這使其成為常用的生成表。

參考資料

1. Hellman, M. A cryptanalytic time-memory trade-off. IEEE Transactions on Information Theory (Institute of Electrical and Electronics Engineers (IEEE)). 1980, 26 (4): 401–406. ISSN 0018-9448. doi:10.1109/tit.1980.1056220.

參考書籍

• Oechslin, Philippe. Making a Faster Cryptanalytical Time-Memory Trade-Off (PDF). Advances in Cryptology: Proceedings of CRYPTO 2003, 23rd Annual International Cryptology Conference. Lecture Notes in Computer Science (Santa Barbara, California, USA: Springer). 2003-08-17 [2014-09-27]. ISBN 3-540-40674-3. （原始內容 (PDF)存檔於2007-09-26）.

外部連結

• Ophcrack page by Philippe Oechslin The original rainbow table research
• 開放目錄專案中的「Cryptography」