Can you summarize the following document?
        
  每一臺需要密碼認證的計算機都包含一個儲存密碼的資料庫,密碼儲存方式有多種,例如摘要或純文字。由於儲存密碼的表很容易被竊取,所以以純文字形式儲存密碼是非常危險的。因此大多數資料庫會儲存使用者密碼的加密摘要。在這種系統內,即使是認證系統本身都無法簡單地通過查表來獲得使用者密碼。然而,當使用者輸入密碼時,系統會生成一個加密過的訊息摘要與儲存的加密摘要進行比較,如果相同就允許訪問請求。  黑客在盜取到雜湊後的密碼錶時,並不能僅憑藉輸入雜湊後的使用者的加密摘要來獲取許可權(使用加密摘要作為輸入密碼並不可行,因為認證系統會把加密摘要再次進行雜湊,產生一個與儲存的加密摘要不匹配的訊息摘要)。為了獲取使用者的密碼,黑客必須找到一個能產生相同加密摘要的密碼。  彩虹表就是僅通過加密摘要來嘗試獲取使用者密碼的工具之一。  由於存在更為簡單的逆向雜湊運算(hash reversal) 的方法, 彩虹表不總是會被用到。相比之下,暴力破解法和字典攻擊法是更為簡單的破解方法。但是這些方法在面對儲存有大量密碼的系統時會非常乏力(儲存用於逆向查詢的所有選項以及對大型資料庫進行搜尋是十分困難的)。  若要破解大型的密碼庫,則需要引入儲存相對較少,但可以逆向形成長鏈密碼的雜湊值的逆向查詢表。雖然在破解單個的密碼時會花費更多的計算時間,但這會大大降低整體的字典大小,因而可以儲存更長的密碼的雜湊值。彩虹表正是在此類連結技術的基礎上改進得到的一種支援碰撞鏈的密碼破解工具。

  "注:這裡表達的雜湊鏈與雜湊鏈中解釋的是不同的雜湊鏈。"  假設我們有一個雜湊方程H和一個有限的密碼集合P。我們需要預先計算出一個資料結構來幫我們決定雜湊方程H的任意一個輸出結果"h"是否可以通過密碼集合P裡面的一個元素"p"經雜湊函式H("p") = "h"得到。實現這一目的的最簡單的方法是計算出P集合內所有密碼"p"的雜湊值H("p")。但是這個方法要求Θ(|P|"n"),("n"代表雜湊函式H的一個輸出值的大小,對於較大的|P|,"n"會變得過高)位元組的空間來儲存結果。  雜湊鏈可以用來減少對於儲存空間的需求。大致想法是通過定義一個"歸約函式"(reduction function)R來對映雜湊值"h"在集合P中對應的密碼"p"。(注意,這裡的歸約函式並不是真正意義上雜湊函式的反函式。)然後通過用歸約函式來替代雜湊函式,形成交替的密碼和雜湊值。例如,如果P是6個字元的密碼集合,而雜湊值有32位長,那麼他們形成的長鏈如下:  已知一個32位的雜湊值 -〉 獲得雜湊值的最後4個字元。  對於歸約函式的唯一要求是,它需要能返回特定字元的純文字值。  為了生成查詢表,我們從"初始密碼"集合P中隨機選擇一個子集,對子集中的每個元素計算長度為"k"的雜湊鏈,然後"只"儲存每條雜湊鏈的初始和末尾密碼。我們把初始密碼稱為"起點",把末尾密碼稱為"終點"。在上述雜湊鏈的例子中,"aaaaaa"和"kiebgt"即為起點和終點,而雜湊鏈中的其他密碼或者雜湊值均不會被儲存。  現在,對於給定的雜湊值"h"我們來計算它的逆(即找到對應的密碼),從雜湊值"h"開始,我們通過依次施加函式R和H生成一個雜湊鏈。如果雜湊鏈的任何節點與查詢表的某個"終點"發生了碰撞,我們就可以找到與之對應的"起點",然後用它重建對應的雜湊鏈。而這個雜湊鏈很可能包含了"h",如果這樣的話,那麼它的前驅節點即為我們要尋找的密碼"p"。  例如,如果給定的雜湊值為920ECF10,我們首先施加函式R:  因為"kiebgt"就是我們查詢表的一個"終點",所以我們找到對應的起始密碼"aaaaaa",然後搜尋由它生成的雜湊鏈直到找到920ECF10:  因此,目標密碼即為"sgfnyd"。  注意,這裡的雜湊鏈並不"總是"會包含我們要尋找的雜湊值"h";很可能以"h"開始的鏈會和"起點"在"h"鏈之後的某個查詢鏈重合。例如,我們可以從FB107E70的雜湊鏈中找到kiebgt:  但FB107E70並不在以"aaaaaa"開頭的鏈中。這種情況被稱為"誤報"。在這個例子中,我們可以忽略這個匹配然後繼續擴增"h"鏈同時尋找下一個匹配。如果"h"的雜湊鏈在擴增到長度為"k"後仍然沒有發生匹配,那麼與之對應的密碼一定不在查詢表的任何雜湊鏈中。 查詢表的內容並不依賴於查詢的雜湊值。它是在一次性建立之後,被無修改的重複用於查詢。增加鏈的長度可以減小表的規模,但同時也會增加查詢時間,這就是彩虹表空間換時間的折中策略。在單元鏈的最簡單情況下,查詢速度會非常快,但表也會非常大。一旦鏈變得更長,查詢速度也會降下來,但表的規模變得更小了。  簡單的雜湊鏈方法有很多缺陷。最嚴重的問題是,如果兩條鏈中的任何兩個點"碰撞"(有同樣的值)了,他們後續的所有點都將重合,這將導致在付出了同樣的計算代價之後並不能使表儘可能多的覆蓋到密碼。由於鏈的前部並沒有整個的儲存,這使得"碰撞"不可能有效檢測到。例如,如果鏈3的第三個值和鏈7的第二個值重合了,那麼這兩條鏈將覆蓋幾乎同樣的值,但他們的終點值卻不相同。雜湊函式H本身不大可能產生碰撞,因為這就是它最重要的安全特性之一。但對於衰減函式R來說,由於他需要正確的覆蓋掉可能的明文(即之前討論的密碼),所以不會是抗碰撞的。  其他的困難是由選擇正確R函式的重要性導致的。選擇恆等對映作為函式R要比暴力搜尋好一點。只有當攻擊者明確知道明文的可能取值是什麼時,他/她才需要選擇一個好的R函式使得時間和空間花費在這些可能的明文上,而不是整個可能的密文空間。儘管把R的取值限定到可能的明文空間能帶來好處,但它的弊端是攻擊者選擇的用於生成雜湊鏈的明文子集可能並不能覆蓋所有的可能明文空間。設計一個能匹配明文期望分佈的R函式也非常困難。

  為了解決簡單的雜湊鏈中的碰撞問題,彩虹表選用一系列相關的衰減函式R,...,R來代替原先的衰減函式R。這樣,如果兩個雜湊鏈發生碰撞並且重合,那麼它們的碰撞必定發生在相同的位置,從而它們的終點也將相同。這樣,我們可以通過後處理來對雜湊鏈進行排序,從而找出並移除所有終點相同,因而可能是重複的鏈,並生成新的鏈來將整個表補充完整。這樣得到的表中的鏈可能有碰撞的部分,但它們不會發生鏈的重合,從而大幅降低了碰撞的次數。  採用衰減函式列代替衰減函式將改變查詢的方式。因為給定的雜湊值可能出現在雜湊鏈中的任意位置,我們需要計算"k"條不同的鏈:首先假定給定的雜湊值出現在雜湊鏈的最後一位(此時我們只需施加函式R),然後假定雜湊值出現在雜湊鏈的倒數第二位(此時我們依次施加函式R,H和R),依此類推,直至我們找到所需的密碼。注意,如果我們錯誤地假定了目標雜湊值在雜湊鏈中的位置,可能會得到一條與表中的鏈部分重合的鏈,從而產生誤報。

  幾乎所有Unix,Linux和BSD的發行版和變體都使用雜湊值,儘管許多應用程式只使用沒有鹽的雜湊(通常是MD5)。Microsoft Windows NT / 2000系列使用LAN Manager和NT LAN Manager雜湊方法(基於MD4)並且也是無保留的,這使其成為最常用的生成表之一。
彩虹表是一個用於加密雜湊函式逆運算的預先計算好的表,常用於破解加密過的密碼雜湊。 彩虹表常常用於破解長度固定且包含的字元範圍固定的密碼(如信用卡、數字等)。這是以空間換時間的典型實踐,比暴力破解(Brute force)使用的時間更少,空間更多;但與儲存密碼空間中的每一個密碼及其對應的雜湊值(Hash)實現的查詢表相比,其花費的時間更多,空間更少。使用加鹽的金鑰派生函式可以使這種攻擊難以實現。