彩虹表

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

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

背景

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

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

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

由於有更簡單的逆向雜湊運算（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位元長，那麼他們形成的長鏈可以表示作：

\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：

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

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

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

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

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

\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）並且也是無保留的，這使其成為常用的生成表。

參考資料

^ 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」

[Hellman_1980_pp._401–406-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.

[1]