彩虹表

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

彩虹表是馬丁・赫爾曼早期提出的簡單演算法的應用。

## 背景

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

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

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

由於有更簡單的逆向雜湊運算（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 函式也非常困難。

## 彩虹表

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

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

## 常見用途

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

## 參考資料

### 參考書籍

* Oechslin, Philippe. Making a Faster Cryptanalytical Time-Memory Trade-Off (PDF). Lecture Notes in Computer Science. Santa Barbara, California, USA: Springer. 2003-08-17 [2014-09-27]. ISBN3-540-40674-3. （原始內容 (PDF) 存檔於 2007-09-26）.

## 外部連結

* Ophcrack page by Philippe Oechslin The original rainbow table research
* 開放式目錄計劃中和 Cryptography 相關的內容