[科普中國]-彩虹表

彩虹表是一個(gè)用于加密散列函數(shù)逆運(yùn)算的預(yù)先計(jì)算好的表, 為破解密碼的散列值（或稱哈希值、微縮圖、摘要、指紋、哈希密文）而準(zhǔn)備。一般主流的彩虹表都在100G以上。 這樣的表常常用于恢復(fù)由有限集字符組成的固定長度的純文本密碼。這是空間/時(shí)間替換的典型實(shí)踐, 比每一次嘗試都計(jì)算哈希的暴力破解處理時(shí)間少而儲存空間多，但卻比簡單的對每條輸入散列翻查表的破解方式儲存空間少而處理時(shí)間多。使用加salt的KDF函數(shù)可以使這種攻擊難以實(shí)現(xiàn)。彩虹表是馬丁·赫爾曼早期提出的簡單算法的應(yīng)用。1

背景為了保證后臺數(shù)據(jù)安全,現(xiàn)在的做法都是使用哈希算法對明文密碼進(jìn)行加密后存儲。由于哈希算法不可逆向，因此由密碼逆向出明文運(yùn)算就成了不可能。

起初黑客們通過字典窮舉的方法進(jìn)行破解，這對簡單的密碼和簡單的密碼系統(tǒng)是可行的，但對于復(fù)雜的密碼和密碼系統(tǒng)，則會產(chǎn)生無窮大的字典。為了解決逆向破解的難題，黑客們就產(chǎn)生了彩虹表的技術(shù)。

為了減小規(guī)模太大的不足，黑客生成一個(gè)反查表僅存儲一小部分哈希值，而每條哈希值可逆向產(chǎn)生一個(gè)密碼長鏈（多個(gè)密碼）。雖然在鏈表中反查單個(gè)密文時(shí)需要更多的計(jì)算時(shí)間，但反查表本身要小得多，因此可以存儲更長密碼的哈希值。Rainbow tables是此鏈條技術(shù)的一種改進(jìn)，并提供一種對被稱為“鏈碰撞”的問題的解決方案。其基于Martin Hellman理論(基于內(nèi)存與時(shí)間的權(quán)重理論) 。

介紹為了解決簡單的哈希鏈中的碰撞問題，彩虹表選用一系列相關(guān)的衰減函數(shù)R1，…，Rk來代替原先的衰減函數(shù)R。這樣，如果兩個(gè)哈希鏈發(fā)生碰撞并且重合，那么它們的碰撞必定發(fā)生在相同的位置，從而它們的終點(diǎn)也將相同。這樣，我們可以通過后處理來對哈希鏈進(jìn)行排序，從而找出并移除所有終點(diǎn)相同，因而可能是重復(fù)的鏈，并生成新的鏈來將整個(gè)表補(bǔ)充完整。這樣得到的表中的鏈可能有碰撞的部分，但它們不會發(fā)生鏈的重合，從而大幅降低了碰撞的次數(shù)。2

采用衰減函數(shù)列代替衰減函數(shù)將改變查找的方式。因?yàn)榻o定的哈希值可能出現(xiàn)在哈希鏈中的任意位置，我們需要計(jì)算k條不同的鏈：首先假定給定的哈希值出現(xiàn)在哈希鏈的最后一位（此時(shí)我們只需施加函數(shù)Rk），然后假定哈希值出現(xiàn)在哈希鏈的倒數(shù)第二位（此時(shí)我們依次施加函數(shù)Rk-1，H和Rk），依此類推，直至我們找到所需的密碼。注意，如果我們錯(cuò)誤地假定了目標(biāo)哈希值在哈希鏈中的位置，可能會得到一條與表中的鏈部分重合的鏈，從而產(chǎn)生誤報(bào)。

計(jì)算過程假設(shè)我們有一個(gè)哈希方程H和一個(gè)有限的密碼集合P。我們需要預(yù)先計(jì)算出一個(gè)數(shù)據(jù)結(jié)構(gòu)來幫我們決定哈希方程H的任意一個(gè)輸出結(jié)果h是否可以通過密碼集合P里面的一個(gè)元素p經(jīng)哈希函數(shù)H(p) =h得到。實(shí)現(xiàn)這一目的的最簡單的方法是計(jì)算出P集合內(nèi)所有密碼p的哈希值H(p)。但是這個(gè)方法要求Θ(|P|n)，（n代表哈希函數(shù)H的一個(gè)輸出值的大小，對于較大的|P|，n會變得過高)字節(jié)的空間來儲存結(jié)果。

哈希鏈可以用來減少對于儲存空間的需求。大致想法是通過定義一個(gè)歸約函數(shù)（reduction function）R來影射散列值h在集合P中對應(yīng)的密碼p。（注意，這里的歸約函數(shù)并不是真正意義上哈希函數(shù)的反函數(shù)。)然后通過用歸約函數(shù)來替代哈希函數(shù)，形成交替的密碼和哈希值。例如，如果P是6個(gè)字符的密碼集合，而哈希值有32位長，那么他們形成的長鏈如下：

例子已知一個(gè)32位的哈希值 -〉 獲得哈希值的最后4個(gè)字符。

對于歸約函數(shù)的唯一要求是，它需要能返回特定字符的純文本值。

為了生成查找表，我們從初始密碼集合P中隨機(jī)選擇一個(gè)子集，對子集中的每個(gè)元素計(jì)算長度為k的哈希鏈，然后只保存每條哈希鏈的初始和末尾密碼。我們把初始密碼稱為起點(diǎn)，把末尾密碼稱為終點(diǎn)。在上述哈希鏈的例子中，"aaaaaa"和"kiebgt"即為起點(diǎn)和終點(diǎn)，而哈希鏈中的其他密碼或者哈希值均不會被保存。

現(xiàn)在，對于給定的哈希值h我們來計(jì)算它的逆（即找到對應(yīng)的密碼），從哈希值h開始，我們通過依次施加函數(shù)R和H生成一個(gè)哈希鏈。如果哈希鏈的任何節(jié)點(diǎn)與查找表的某個(gè)終點(diǎn)發(fā)生了碰撞，我們就可以找到與之對應(yīng)的起點(diǎn)，然后用它重建對應(yīng)的哈希鏈。而這個(gè)哈希鏈很可能包含了h，如果這樣的話，那么它的前驅(qū)節(jié)點(diǎn)即為我們要尋找的密碼p。

例如，如果給定的哈希值為920ECF10，我們首先施加函數(shù)R：

因?yàn)?quot;kiebgt"就是我們查找表的一個(gè)終點(diǎn)，所以我們找到對應(yīng)的起始密碼"aaaaaa"，然后搜索由它生成的哈希鏈直到找到920ECF10：

因此，目標(biāo)密碼即為"sgfnyd"。

注意，這里的哈希鏈并不總是會包含我們要尋找的哈希值h；很可能以h開始的鏈會和起點(diǎn)在h鏈之后的某個(gè)查找鏈重合。例如，我們可以從FB107E70的哈希鏈中找到kiebgt：

但FB107E70并不在以"aaaaaa"開頭的鏈中。這種情況被稱為誤報(bào)。在這個(gè)例子中，我們可以忽略這個(gè)匹配然后繼續(xù)擴(kuò)增h鏈同時(shí)尋找下一個(gè)匹配。如果h的哈希鏈在擴(kuò)增到長度為k后仍然沒有發(fā)生匹配，那么與之對應(yīng)的密碼一定不在查找表的任何哈希鏈中。

查找表的內(nèi)容并不依賴于查詢的哈希值。它是在一次性建立之后，被無修改的重復(fù)用于查找。增加鏈的長度可以減小表的規(guī)模，但同時(shí)也會增加查詢時(shí)間，這就是彩虹表空間換時(shí)間的折中策略。在單元鏈的最簡單情況下，查詢速度會非?？?，但表也會非常大。一旦鏈變得更長，查找速度也會降下來，但表的規(guī)模變得更小了。

簡單的哈希鏈方法有很多缺陷。最嚴(yán)重的問題是，如果兩條鏈中的任何兩個(gè)點(diǎn)碰撞（有同樣的值）了，他們后續(xù)的所有點(diǎn)都將重合，這將導(dǎo)致在付出了同樣的計(jì)算代價(jià)之后并不能使表盡可能多的覆蓋到密碼。由于鏈的前部并沒有整個(gè)的保存，這使得碰撞不可能有效檢測到。例如，如果鏈3的第三個(gè)值和鏈7的第二個(gè)值重合了，那么這兩條鏈將覆蓋幾乎同樣的值，但他們的終點(diǎn)值卻不相同。哈希函數(shù)H本身不大可能產(chǎn)生碰撞，因?yàn)檫@就是它最重要的安全特性之一。但對于衰減函數(shù)R來說，由于他需要正確的覆蓋掉可能的明文（即之前討論的密碼），所以不會是抗碰撞的。

其他的困難是由選擇正確R函數(shù)的重要性導(dǎo)致的。選擇恒等映射作為函數(shù)R要比暴力搜索好一點(diǎn)。只有當(dāng)攻擊者明確知道明文的可能取值是什么時(shí)，他/她才需要選擇一個(gè)好的R函數(shù)使得時(shí)間和空間花費(fèi)在這些可能的明文上，而不是整個(gè)可能的密文空間。盡管把R的取值限定到可能的明文空間能帶來好處，但它的弊端是攻擊者選擇的用于生成哈希鏈的明文子集可能并不能覆蓋所有的可能明文空間。設(shè)計(jì)一個(gè)能匹配明文期望分布的R函數(shù)也非常困難。

本詞條內(nèi)容貢獻(xiàn)者為:

王慧維 - 副研究員 - 西南大學(xué)