基于完美彩虹表的檢查點(diǎn)算法改進(jìn)研究*

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

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

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

1 引言

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

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

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

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

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

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

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

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

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

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

2 相關(guān)工作

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

2.1 原始的TMTO 方法

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

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

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

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

之后攻擊者便檢查是否存在某個(gè)鏈尾節(jié)點(diǎn)EPi與Y1相匹配, 如果不存在, 就不斷地迭代計(jì)算Yj+1=f(Yj), 直至匹配某個(gè)鏈尾節(jié)點(diǎn)為止. 假設(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并不在對(duì)應(yīng)的哈希鏈中. 這種現(xiàn)象就被稱為“誤報(bào)”. 具體而言, 哈希鏈中任何一個(gè)不同于K0的Ki,j, 只要滿足f(c)(Ki,j)=f(c)(K0), 就會(huì)導(dǎo)致誤報(bào)(其中c ≤t ?j). 在實(shí)際情況中, 絕大部分的鏈尾節(jié)點(diǎn)匹配都是誤報(bào). 為了解決這一問題, 密碼學(xué)家提出了許多改進(jìn).

2.2 彩虹表

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

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

2.3 完美表

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

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

2.4 檢查點(diǎn)

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

假定檢查點(diǎn)的選取位置為α, 對(duì)應(yīng)的值為Xj,α. 在預(yù)計(jì)算階段, 對(duì)于每一條鏈, 除了頭尾兩個(gè)節(jié)點(diǎn)外,攻擊者還將對(duì)每個(gè)檢查點(diǎn)位置的哈希值計(jì)算對(duì)應(yīng)的G 函數(shù), 將G(Xj,α) 一并保存. 在線上檢索階段, 當(dāng)某個(gè)Ys= EPj匹配時(shí), 攻擊者先檢查每個(gè)經(jīng)過的檢查點(diǎn)是否滿足G(Yα+s?t) = G(Xj,α)(經(jīng)過的檢查點(diǎn)即α > t ?s 的點(diǎn)). 如果其中任何一個(gè)檢查點(diǎn)沒有滿足該等式, 攻擊者便可以認(rèn)定其為一次誤報(bào). 這是因?yàn)镚(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)然, 即便所有檢查點(diǎn)都通過了檢查, 攻擊者也無法斷定這次匹配不是誤報(bào), 因?yàn)榕鲎部赡芮∏“l(fā)生在Kj,t?s和它右側(cè)的檢查點(diǎn)之間. 圖2 和圖3 顯示了檢查點(diǎn)和碰撞發(fā)生點(diǎn)處在不同位置時(shí)的效果. 如圖2,碰撞發(fā)生在檢查點(diǎn)之后, 那么檢查點(diǎn)所存儲(chǔ)的哈希值就與線上檢索階段所生成的哈希鏈對(duì)應(yīng)元素不匹配,也就是G(Yα+s?t)?=G(Xj,α), 誤報(bào)被成功偵測(cè). 若如圖3, 碰撞發(fā)生在檢查點(diǎn)之前, 導(dǎo)致Yα+s?t=Xj,α,自然G(Yα+s?t)=G(Xj,α), 誤報(bào)偵測(cè)失敗.

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

圖2 誤報(bào)偵測(cè)成功Figure 2 False alarm detection success

圖3 誤報(bào)偵測(cè)失敗Figure 3 False alarm detection failure

3 檢查點(diǎn)算法分析

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

3.1 列覆蓋率

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

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

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

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

從中可以得出:

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

3.2 誤報(bào)損失

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

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

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

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

3.3 檢查點(diǎn)收益

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

計(jì)gα(s) 為檢查點(diǎn)在第α 列, 匹配在第s 列時(shí)的檢查點(diǎn)生效概率. gα(s) 的計(jì)算見式(2).

在有檢查點(diǎn)情況下, 單次誤報(bào)的時(shí)間損失就變?yōu)?

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

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

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

3.4 最佳位置

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

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

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

表1 檢查點(diǎn)的最佳位置Table 1 Optimal positions of checkpoints

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

4 實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

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

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

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

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

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

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

表3 三種檢查點(diǎn)位置集合Table 3 Three sets of checkpoints position

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

表4 l=5 的實(shí)驗(yàn)結(jié)果Table 4 Experiment results at l=5

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

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

5 總結(jié)

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