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

1. 清華大學(xué) 計算機科學(xué)與技術(shù)系, 北京100084

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

1 引言

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

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

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

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

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

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

我們的工作總結(jié)如下:

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

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

? 我們構(gòu)造了實驗來檢驗一些其它結(jié)論. 結(jié)果表明, 在l = 5 的條件下, 5 個檢查點的時間收益可以達(dá)到30%. 此外, 在空間開銷相當(dāng)?shù)臈l件下, 設(shè)置一個檢查點的收益是額外生成新鏈的7 倍.

2 相關(guān)工作

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

2.1 原始的TMTO 方法

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

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

圖1 彩虹表的結(jié)構(gòu)Figure 1 Structure of rainbow table

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

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

2.2 彩虹表

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

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

2.3 完美表

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

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

2.4 檢查點

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

假定檢查點的選取位置為α, 對應(yīng)的值為Xj,α. 在預(yù)計算階段, 對于每一條鏈, 除了頭尾兩個節(jié)點外,攻擊者還將對每個檢查點位置的哈希值計算對應(yīng)的G 函數(shù), 將G(Xj,α) 一并保存. 在線上檢索階段, 當(dāng)某個Ys= EPj匹配時, 攻擊者先檢查每個經(jīng)過的檢查點是否滿足G(Yα+s?t) = G(Xj,α)(經(jīng)過的檢查點即α > t ?s 的點). 如果其中任何一個檢查點沒有滿足該等式, 攻擊者便可以認(rèn)定其為一次誤報. 這是因為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)))).

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

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

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

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

3 檢查點算法分析

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

3.1 列覆蓋率

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

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

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

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

從中可以得出:

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

3.2 誤報損失

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

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

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

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

3.3 檢查點收益

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

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

在有檢查點情況下, 單次誤報的時間損失就變?yōu)?

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

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

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

3.4 最佳位置

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

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

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

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

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

4 實驗設(shè)計與結(jié)果分析

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

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

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

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

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

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

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

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

表4 l=5 的實驗結(jié)果Table 4 Experiment results at l=5

表5 l=4 的對比結(jié)果Table 5 Comparison results at l=4

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

5 總結(jié)

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