基于完美彩虹表的檢查點算法改進研究*

于紅波, 何 樂, 程子杰,2

1. 清華大學 計算機科學與技術系, 北京100084

2. 賓夕法尼亞州立大學 計算機科學系, 大學城, PA 16802

1 引言

哈希函數是一種可以將任意長度的私有數據映射為固定長度的哈希值的函數. 哈希函數在密碼學領域中被廣泛應用, 其中最為重要的應用場景之一就是口令認證. 為保障安全性, 哈希函數在設計上應具有單向性的特點: 即得到輸入的哈希值十分容易, 而通過哈希值恢復對應的輸入十分困難. 后者就是所謂的原像攻擊, 在信息安全領域一直是一個熱門的問題.

對于原像攻擊, 最直接的解法就是窮舉搜索. 假設目標哈希值的長度為n, 那么在期望上, 每2n次隨機檢索中就會出現一個對應的原像. 然而, 這種解法需要相當龐大的攻擊時間以及計算能力. 為解決這一問題, Hellman[1]于1980 年提出了時間存儲折中攻擊方法, 該方法將預計算與窮舉搜索相結合, 可以用額外的空間開銷來換取攻擊時間. 算法分為兩個階段: 預計算階段和線上檢索階段. 在預計算階段中, 攻擊者進行大量的迭代計算以得到一系列的哈希鏈, 對每一條鏈僅僅保留鏈頭和鏈尾兩點, 舍棄所有中間節點(為節省空間). 當預計算工作結束后, 所得到結果即一張鏈表, 可以在多次檢索中被重復利用. 對于一次線上檢索(目標為分組密碼的密鑰或者哈希函數的原像), 攻擊者只要完成相同的迭代操作, 直至目標與某一個鏈尾節點相匹配為止. 當二者匹配時, 攻擊者就能利用已存儲的對應鏈頭節點恢復整條哈希鏈, 并期望沒有經過迭代的原始目標恰好被該鏈所覆蓋, 從而找到特定目標. 更多細節將在第2 節中進一步討論.

然而, 由于鏈與鏈之間存在碰撞, 線上檢索階段可能出現問題. 可能的情況是, 原始目標并不在當前尾節點所匹配的哈希鏈中, 而是存在于另一條若干輪迭代后才會匹配的哈希鏈, 甚至是存在于一條根本未被預計算所生成的哈希鏈中, 這個現象被稱為“誤報”(false alarm). Hellman[1]曾指出, 由于碰撞這一固有缺陷, 誤報所造成的時間損失能達到整個檢索時間的50%. 2010 年, Hong[2]的論文表明, 在經典的Hellman 表中, 排除誤報的時間代價占了整個檢索時間的14.3%.

自Hellman 提出時間存儲折中攻擊方法后, 密碼學家針對原方法做出了大量的改進和優化. Rivest[3]曾提出一種基于“特異點”(distinguished point) 的方法, 在該方法的規則下, 在預計算階段生成哈希鏈時, 迭代操作直到某個符合特殊條件的特異點方會終止(例如首幾個比特全部為0). 基于特異點模型,Kusuda 和Matsumoto[4]進一步分析了能將時間與存儲協調的優化參數, 并將該方法應用于對DES 的攻擊. Standaert 等人[5]同樣對特異點模型進行了分析, 并完成了攻擊40-bit DES 的FPGA 實現.

2003 年, Oechslin[6]從另一個角度進行改進, 提出了彩虹表算法. 相較于原始的時間存儲折中攻擊方法, 彩虹表主要解決了不同哈希鏈之間存在碰撞這一問題. 后者在每一列使用了不同的約減函數, 保證碰撞不會發生在彩虹表的不同列, 從而大幅減少碰撞的數量. 這一改進確實能大幅提升表在整個空間中的覆蓋率, 同時也能降低發生誤報的風險. 2005 年, Avoine 等人[7]提出了檢查點算法(checkpoints method),算法在哈希鏈中段設置了一系列的檢查點, 作為額外存儲與鏈頭和鏈尾一并保存. 在線上檢索階段, 目標除了要與鏈尾節點匹配之外, 所經過的檢查點也必須一一匹配. 這樣算法只需要分鐘級別的額外開銷, 就可以大幅降低發生誤報所造成的損失, 從而提升算法效率.

在本文中, 我們借鑒了檢查點算法的思想, 以完美彩虹表為基礎, 研究并改進了對檢查點效率的分析模型, 進而得到了復數檢查點在完美彩虹表下的最佳理論位置. 盡管在一般的彩虹表應用, 如位數較多的用戶口令破解中, 生成完美彩虹表需要不切實際的時間與空間開銷, 但由于檢查點算法本身對降低誤報損失有著顯著作用, 我們的結果對于一般的彩虹表仍具有一定啟示性意義.

我們的工作總結如下:

? 我們研究并計算了彩虹表在整個空間中的覆蓋率(即線上檢索的成功率). 如果彩虹表表含有足夠多的元素, 近似于完美表, 那么覆蓋率只取決于表的數量. 我們發現當表的數量l ≥5 時, 覆蓋率就能達到99.99%.

? 我們對檢查點算法進行了理論分析, 推導出檢查點最佳位置的計算式, 該計算式可以推廣到任意數量的檢查點. 進一步地我們計算了最佳位置下的理論收益, 并設置了實驗進行驗證, 同時選取了另外兩個檢查點集(均勻選取和Avoine 等人[7]的選取) 作為對照.

? 我們構造了實驗來檢驗一些其它結論. 結果表明, 在l = 5 的條件下, 5 個檢查點的時間收益可以達到30%. 此外, 在空間開銷相當的條件下, 設置一個檢查點的收益是額外生成新鏈的7 倍.

2 相關工作

這一節將簡要介紹關于時間存儲折中攻擊的算法或概念. 下面的四個小節中, 討論背景均假定為對于一個分組密碼在選擇明文攻擊下的密鑰恢復. 對于哈希函數的原像攻擊, 算法的應用在本質上都是相同的.

2.1 原始的TMTO 方法

這一方法由Hellman[1]于1980 年提出. 算法分為兩個階段, 攻擊者在預計算階段構建一張鏈表, 然后在線上檢索階段利用它恢復密鑰.

在預計算階段, 攻擊者交替地調用分組密碼S 和一個約減函數R 來構造哈希鏈, 這等價于迭代調用f(K)=R(S(K,P0)), 其中K 為一個n-bit 的密鑰, P0為攻擊者所選擇的明文. 注意R 本身是一個輸出長度固定為n-bit 的函數, 所以f(K) 即為將整個密鑰空間映射到自身的哈希函數, 迭代所得即一條條密鑰空間中的哈希鏈. 具體而言, 對于一條哈希鏈(用一個序號i 來加以區分), 攻擊者首先隨機選取鏈頭節點SPi= Ki,1, 然后進行若干步迭代計算Ki,j+1= f(Ki,j), 最終達到鏈尾節點EPi= Ki,t. 在構建了一系列的哈希鏈后, 只有那些鏈頭節點(SP1,SP2,··· ,SPm) 和鏈尾節點(EP1,EP2,··· ,EPm) 會被保留下來. 這些節點隱式地存儲了一張所謂的Hellman 表, 其結構與圖1 中所示的彩虹表的結構十分相似. 由于鏈與鏈之間存在大量碰撞, Hellman 表在整個空間中的覆蓋率十分有限. 為了提升覆蓋率, 攻擊者需要設置多張鏈表, 對應于不同的約減函數.

圖1 彩虹表的結構Figure 1 Structure of rainbow table

在線上檢索階段, 為恢復目標密鑰K0, 攻擊者首先選擇明文P0(與預計算階段選擇的明文相同), 并詢問對應的密文C0=S(K0,P0), 然后計算

之后攻擊者便檢查是否存在某個鏈尾節點EPi與Y1相匹配, 如果不存在, 就不斷地迭代計算Yj+1=f(Yj), 直至匹配某個鏈尾節點為止. 假設若干步之后, Ys= EPi成立, 這意味著f(s)(K0) = f(t?1)(SPi)成立. 由此, 攻擊者期望K0= f(t?1?s)(SPi) = Ki,t?s同樣成立, 這樣就能從SPi中恢復出K0. 然而,由于f 并非是一一映射, 碰撞的存在可能使得兩條不同的哈希鏈在Ki,t?s之后合并, 導致Ys雖與EPi匹配, 然而K0并不在對應的哈希鏈中. 這種現象就被稱為“誤報”. 具體而言, 哈希鏈中任何一個不同于K0的Ki,j, 只要滿足f(c)(Ki,j)=f(c)(K0), 就會導致誤報(其中c ≤t ?j). 在實際情況中, 絕大部分的鏈尾節點匹配都是誤報. 為了解決這一問題, 密碼學家提出了許多改進.

2.2 彩虹表

彩虹表算法由Oechslin[6]于2003 年提出, 該方法可以大幅減少鏈與鏈之間的碰撞與合并. 在原始的TMTO 方法中, Hellman 在不同的表中使用不同的約減函數來提高覆蓋率. 然而, 鏈與鏈之間的碰撞和合并依然大量存在. 例如Ki,p和Kj,q, 一旦二者相等, 由于同一張表中使用的約減函數相同, 鏈i 和鏈j 就會從碰撞處開始合并. 為了避免此類狀況, 彩虹表在其結構上做了一個細微的變化: 設計不同的約減函數{R1,··· ,Rt?1}, 對每一列, 哈希鏈依次調用不同的Ri. 構造哈希鏈的迭代式變為:

彩虹表的結構示意圖見圖1. 其中, t 是單條哈希鏈的長度, m 是單表中哈希鏈的數量. 在彩虹表中,上述所提到的碰撞和合并將大幅減少, 它們僅會出現在p = q 的情況. 也就是說, 碰撞與合并僅僅會發生在彩虹表的同列中, 這使得碰撞與合并的頻率降低到原來的1/t.

2.3 完美表

由于Hellman 表中存在大量鏈與鏈之間的碰撞與合并, 存儲整張鏈表所需的空間開銷巨大, 而且有很大部分的重復和浪費. 為提升空間利用的效率, 攻擊者可以額外計算足夠數量的冗余鏈, 然后將發生碰撞和合并的鏈逐條刪除, 余下兩兩沒有碰撞的鏈. 這樣攻擊者就能在保證覆蓋率的同時, 最大化地降低空間開銷. 對于彩虹表, 消除合并的工作就變得更為簡單. 攻擊者只需要將所有EPi排序, 對EPi進行去重,尾節點相同的哈希鏈僅保留一條即可. 這個想法最早由Borst 等人[8]于1999 年提出, 消除合并后的鏈表就稱為完美表. 在完成尾節點去重工作后, 攻擊者所得到的完美彩虹表滿足每一列中的所有元素互不相同. 當然, 在不同的列中依然會存在有相同的元素, 但由于不同列所使用的約減函數不同, 后續的合并將會被完全避免.

在2010 年, Hong[2]的論文指出, 完美彩虹表和非完美彩虹表中由誤報所造成的時間損失分別占到檢索時間的25.8% 和27.6%, 二者的差距并不大. 此外, 完美彩虹表具有良好的性質, 抹除了一些復雜的因素(如不同列之間的碰撞), 這使得理論分析更加簡便和直觀. 因此, 在本文接下來的部分, 我們關于檢查點算法的分析和討論均主要基于完美彩虹表.

2.4 檢查點

2005 年, Avoine 等人[7]提出了檢查點算法, 他們認為如果判斷一次匹配是否為誤報總是需要t ?s的開銷(即恢復哈希鏈到Ki,t?s的位置), 算法效率很難有顯著的提升. 借助檢查點, 攻擊者就可以“提前”偵測到誤報, 從而降低時間開銷.

假定檢查點的選取位置為α, 對應的值為Xj,α. 在預計算階段, 對于每一條鏈, 除了頭尾兩個節點外,攻擊者還將對每個檢查點位置的哈希值計算對應的G 函數, 將G(Xj,α) 一并保存. 在線上檢索階段, 當某個Ys= EPj匹配時, 攻擊者先檢查每個經過的檢查點是否滿足G(Yα+s?t) = G(Xj,α)(經過的檢查點即α > t ?s 的點). 如果其中任何一個檢查點沒有滿足該等式, 攻擊者便可以認定其為一次誤報. 這是因為G(Yα+s?t)= G(Xj,α) 意味著Yα+s?t= Xj,α, 又Yα+s?t= f(α+s?t)(K0) 且Xj,α= f(α+s?t)(Kj,t?s),故能得知K0=Kj,t?s(在彩虹表中, f(α)(K) 指ft?1(ft?2(···ft?α(K)))).

當然, 即便所有檢查點都通過了檢查, 攻擊者也無法斷定這次匹配不是誤報, 因為碰撞可能恰恰發生在Kj,t?s和它右側的檢查點之間. 圖2 和圖3 顯示了檢查點和碰撞發生點處在不同位置時的效果. 如圖2,碰撞發生在檢查點之后, 那么檢查點所存儲的哈希值就與線上檢索階段所生成的哈希鏈對應元素不匹配,也就是G(Yα+s?t)?=G(Xj,α), 誤報被成功偵測. 若如圖3, 碰撞發生在檢查點之前, 導致Yα+s?t=Xj,α,自然G(Yα+s?t)=G(Xj,α), 誤報偵測失敗.

至于G 函數的選擇問題, 為使算法在空間和時間上更加高效, G 函數應被設計為具有易于存儲和計算的形式. 例如選擇G(X) = X, 存儲全部信息, 則空間代價將成倍地增長, 比較效率也很低. Avoine 等人[7]在論文中建議取G(X) 為X 的最低位比特, 當然這種方式會引入額外的偵測失敗概率. 對于本不應通過檢測的檢查點, 在這種方式下能成功偵測到誤報的概率為:)

圖2 誤報偵測成功Figure 2 False alarm detection success

圖3 誤報偵測失敗Figure 3 False alarm detection failure

3 檢查點算法分析

這一節中, 我們將對檢查點算法的效率進行全面分析, 包括單個或多個檢查點所帶來的時間增益, 以及檢查點的最佳位置選取. 作為分析的基礎, 我們也將討論彩虹表的覆蓋率以及誤報所造成的時間損失.

3.1 列覆蓋率

覆蓋率是彩虹表算法成功概率的體現. 只有已經被彩虹表所覆蓋, 即在預計算階段所涉及到的元素(原像或密鑰) 才能被彩虹表成功恢復, 反之, 只要是彩虹表中的元素, 經過有限次誤報后總是能被正確匹配. 至于誤報發生的次數, 造成的時間損失, 匹配的迭代輪數等, 都與該元素所在的深度, 即其所在的列有關(若元素在彩虹表中出現多次, 則為最靠近鏈尾的列). 一般而言, 元素越靠近鏈尾, 誤報發生的次數越少, 單次誤報損失越大, 所需的迭代輪數越少. 若要更深入地討論這些問題, 首先要解決的是目標處在彩虹表中每一列的期望概率.

定義符號Rj為第j 列的列覆蓋率, 它表示自該列起直至鏈尾, 彩虹表所有不同元素個數與整個空間元素個數的比值. 換言之, Rj就是彩虹表算法在不超過t ?j +1 輪迭代下的成功率, 而目標恰處在第j列的概率就為Rj?Rj+1. 在此再確認一下相關符號和概念: m 為單表中哈希鏈的條數, t 為單條哈希鏈的元素個數, N 為整個空間的元素個數. 假定我們的鏈表是一張極大完美彩虹表. Oechslin[6]曾證明, 給定足夠大的鏈長t, 彩虹表中不造成鏈合并的最大鏈數為mmax(t)=2N/(t+2). 因此, 我們有2N =mt.

記mi為彩虹表中第i 列不同元素的個數. 第i 列的元素為第i ?1 列的元素向整個空間經f 映射而來, 這相當于一個有放回的抽取模型. 于是對于一個空間中的元素, 其出現在第i 列的概率就是:

因此數列{mi} 就滿足遞推關系mi= N ?Pr(i), 起始項m1= m(因為表頭是攻擊者可選的). 當然這個結果只是對于一般的彩虹表, 對于完美彩虹表, 同一列中沒有碰撞, 總是有mi= m. 這個結果一方面表明在相同條件下, 完美彩虹表確實有更高的空間利用率, 另一方面也給完美彩虹表下的分析帶來啟發.

從中可以得出:

對于全表即j = 1, 當t 足夠大的時候, R1可以化簡為R1= 1 ?e?2. 換言之, 對于一張極大完美彩虹表, 依然存在e?2的未覆蓋空間. 對于使用了不同約減函數集的l 張完美彩虹表, 未覆蓋空間為e?2l,對應覆蓋率為1 ?e?2l. 當l = 5 的時候, 覆蓋率即可達到99.99%, 幾乎可以近似認為覆蓋了空間中的所有元素. 因此在本文所構造的實驗環境中, 我們同樣選擇l =5.

3.2 誤報損失

在上節, 我們已經分析了目標在第j 列匹配的概率, 為Rj?Rj+1(補充定義Rt+1= 0). 注意迭代與匹配是從鏈尾即第t 列開始的. 在這一節, 我們將進一步討論誤報所造成的時間損失.

在線上檢索階段, 一次鏈尾匹配意味著兩種可能: 少數情況的正確匹配以及大多數情況的誤報. 而誤報是由線上檢索時計算的迭代鏈與匹配鏈之間的碰撞所引發的. 根據完美彩虹表的性質, 我們可以計算兩條鏈恰碰撞于第c 列的概率, 為:

記Q(x) 為誤報所造成的額外損失, 其中x 為目標所在的列號(對應于匹配的迭代輪數, 二者之和為t+1). 現目標經t+1 ?x 輪迭代后與某個鏈尾節點匹配, 碰撞必然發生在第x 列到第t 列之間的某個位置, 而在無檢查點的情況下, 檢查第c 列的碰撞又需要c 的代價. 這也就意味著:

又由上節, 目標在第j 列匹配的概率為Rj?Rj+1. 故誤報的期望損失為該概率乘以Q(j), 對j 遍歷求和得到. 然而這種計算方式遺漏了一種情況, 即目標根本未被彩虹表所覆蓋的情況, 在該情況下, 導致誤報的碰撞可能發生在任何一列, 這與Q(1) 等價. 綜上所述, 一次誤報所造成的期望時間損失就為:

3.3 檢查點收益

基于以上討論, 這一節我們開始分析檢查點算法所帶來的時間增益, 包括單檢查點的情況和多檢查點的情況. 首先考慮單檢查點的情況. 根據之前對檢查點算法的描述, 只有線上檢索生成的迭代鏈所經過的檢查點才能生效, 過深(過于靠近表頭) 的檢查點沒有判斷的意義. 此外, 對于有效的檢查點, 必須在G 函數結果不同時才算偵測成功, 如果采用式(1)的結果, 成功概率為1/2.

計gα(s) 為檢查點在第α 列, 匹配在第s 列時的檢查點生效概率. gα(s) 的計算見式(2).

在有檢查點情況下, 單次誤報的時間損失就變為:

其中qαgα(t ?i) 即為檢查點算法生效, 免去花i 步驗證碰撞所帶來的收益部分.

再看多檢查點的情況, 假定其位置從右到左依次為α1,…,αn. 多檢查點的收益部分如式(3)所示.

代入gα(c)≈1/2, 上式可簡化為:

3.4 最佳位置

這一節我們進一步討論最佳位置的計算. 首先還是看單檢查點的情況. 將式(4)中的TG 按g(t ?tx)的取值分段展開, 得到:

含有n 的情況難以得到簡潔的形式, 只能代入特定的n 求出最優解析解. 分別取n = 2,3,4,5, 對應的TGn如下式所示.

最終, 所求得的最佳位置如表1 所示.

表1 檢查點的最佳位置Table 1 Optimal positions of checkpoints

此外, 圖4 顯示了不同檢查點數量下, 時間收益的變化趨勢, 其橫坐標為檢查點數目, 縱坐標為提取出固定系數的標準化TG. 從圖中可以看出, 時間收益隨檢查點數目的增長而增長, 但是每個單獨檢查點的收益是在逐步下降的.

4 實驗設計與結果分析

在進行了大量的理論計算后, 我們同樣設計了實驗來驗證我們的理論分析. 測試主要集中在兩個方面,一是測試不同列下的覆蓋率是否與我們的分析相符合, 二是測試不同檢查點選取方案的效果并進行比較.

圖4 不同數量檢查點下的時間收益Figure 4 Total time gain under different checkpoints number

實驗之前我們首先構造了數張完美彩虹表. 相較于分組密碼, 哈希函數加密效率高又不需要私鑰, 且本質上彩虹表算法在二者的應用上沒有區別, 故我們選擇使用哈希函數來代替分組密碼進行測試. 以下為實驗用完美彩虹表的相關規格說明: 所選哈希函數為標準SHA-1, 原像空間為7 位的ASCII-32-95, 彩虹表數量l =5, 每張表鏈數m=107 374, 鏈長t=10 000.

逐列計算每一列中新元素的個數, 并與不同深度下的理論覆蓋率1 ?e?2ld比較, 結果見表2.

表2 理論覆蓋率與實際覆蓋率比較Table 2 Comparison of theoretical coverage and actual coverage

驗證檢查點理論最佳位置的效果是實驗的主要任務. 除了直接測試我們的最佳位置選取方案之外, 我們還設置了對照實驗來比較不同選取方案的效果. 表3 給出了三種檢查點的位置選取方式, 其中第三種為本文中的選取方式, 與表1 相同, 而Control 1 和Control 2 分別為均勻選取和來自Avoine 等人[7]論文中的選取方式.

表3 三種檢查點位置集合Table 3 Three sets of checkpoints position

表4 為關于本文所提出的最佳位置選取方案的相關測試結果, 包括檢查點的額外空間開銷, 空間開銷轉化為新鏈的收益, 最佳位置選取方案的理論收益與實際收益四項. 表5 為l =4 下, 對比三種選取方案的橫向測試結果.

表4 l=5 的實驗結果Table 4 Experiment results at l=5

表5 l=4 的對比結果Table 5 Comparison results at l=4

在此總結上述所有實驗結果. 首先, 關于檢查點算法本身的效率, 在相同的空間開銷下, 使用檢查點算法的收益要遠遠高于產生新鏈的收益. 其次, 當采用合適的選取策略時, 檢查點的收益能在一定程度上得到提升. 雖然差距只有一點點, 我們所提出的策略看起來依然是最為高效的. 最后, 隨著所處位置的深度提升, 不同檢查點帶來的收益會不斷下降. 換言之, 隨著檢查點數目的增長, 最靠近表頭的檢查點的收益會越來越低.

5 總結

本文主要研究了完美彩虹表中的檢查點算法, 對算法進行改進, 使之盡可能高效地降低誤報所造成的時間損失. 在本文中, 我們的研究涉及以下幾個方面. 我們首先分析了多張彩虹表中覆蓋率與所處深度的關系, 從而得到元素于不同列中匹配的概率. 進一步地, 我們推導出單次匹配中由誤報所造成的期望時間損失, 以及檢查點所帶來的期望時間收益的表達式. 基于該表達式, 我們進行近似分析和最優化求解, 提出了n = 1 到n = 5 的最佳位置選取策略. 最后, 我們設置了相關實驗來驗證理論分析的結果, 結果顯示我們的策略要優于已有的結果, 最高能帶來30% 的時間收益.