簡 玲， 徐賽賽， 邱衛(wèi)東， 郭奕東

(1上海市公安局網(wǎng)絡(luò)安全保衛(wèi)總隊(duì)，上海200025；2上海交通大學(xué)電子信息與電氣工程學(xué)院，上海200240)

0 引言

口令作為一種身份認(rèn)證與授權(quán)控制的基本手段，廣泛應(yīng)該在各類信息系統(tǒng)中。然而，無論是對(duì)于網(wǎng)頁應(yīng)用還是文件類應(yīng)用，口令的明文傳輸與存儲(chǔ)都是一個(gè)嚴(yán)重的安全漏洞，將為攻擊者大開方便之門。密碼學(xué)上對(duì)這一問題的解決方案是使用哈希函數(shù)對(duì)口令進(jìn)行加密。

哈希函數(shù)又稱單項(xiàng)散列函數(shù)、雜湊函數(shù)，它接受任意長度的輸入消息，輸出固定長度的比特串。哈希函數(shù)具有以下性質(zhì):對(duì)于任意長度的輸入，都能快速容易地計(jì)算哈希輸出?無法根據(jù)已有哈希值逆向計(jì)算輸入消息，這也是其稱之為單項(xiàng)的原因?對(duì)于給定消息，難以找到另一個(gè)消息使它們的哈希相同。目前廣泛使用的哈希函數(shù)包括MD5、SHA1等。

由于哈希函數(shù)的這些密碼學(xué)性質(zhì)，用其加密、保護(hù)口令是十分合適的，被業(yè)界大量應(yīng)用。

因?yàn)楣：瘮?shù)的單向不可逆性，對(duì)于受到哈希保護(hù)的加密口令，兩種基本的恢復(fù)手段是以時(shí)間為代價(jià)的暴力攻擊以及以空間為代價(jià)的查表法。然而在口令明文空間較大時(shí)，這兩種策略由于需要消耗太多的資源，都無法在工程上實(shí)現(xiàn)。另一種廣泛采用的口令恢復(fù)方法字典攻擊，是查表法的一個(gè)變種，但這種策略受限于字典的好壞，僅僅能恢復(fù)一些簡單口令有效。

彩虹表算法是Oechslin在2003年于前人的基礎(chǔ)上提出的一種新的算法，以時(shí)間空間折中思想為核心，為口令恢復(fù)提供了一種新的思路。

1 彩虹表算法

1.1 時(shí)間空間折中

彩虹表的算法基于Hellman于1980年發(fā)表論文[1]中的時(shí)間空間折中思想。它通過預(yù)計(jì)算，生成Hellman表，Hellman表由不同的哈希鏈組成，然而每條哈希鏈僅僅保存鏈?zhǔn)着c鏈尾，因此進(jìn)行了空間的壓縮。在查找Hellman表時(shí)，通過一定的計(jì)算可以恢復(fù)出整條哈希鏈。因此相對(duì)于原始的查表法，Hellman表壓縮了空間?而相對(duì)與暴力攻擊的方法，由于查表本質(zhì)上是利用預(yù)計(jì)算的計(jì)算結(jié)果，節(jié)省了時(shí)間。

然而，原始的Hellman表存在明顯的缺陷。由于采用的是一致的還原函數(shù)，導(dǎo)致在生成哈希鏈的過程中會(huì)產(chǎn)生碰撞，造成哈希鏈的合并，浪費(fèi)計(jì)算資源并且降低了破解效率。表越大，造成哈希鏈合并的概率越高。

為了處理鏈合并帶來的問題，Oechslin于2003年的論文[2]中，提出了彩虹表的思想。相較于Hellman表，彩虹表的本質(zhì)在于在彩虹鏈的不同位置采用不同的還原函數(shù)。這樣，即使兩條鏈發(fā)生碰撞，由于列不同，之后的彩虹鏈不會(huì)進(jìn)行合并。除非兩條彩虹鏈恰巧在同一列發(fā)生碰撞，而這樣的概率是相當(dāng)?shù)偷摹?/p>

由于彩虹表良好的性質(zhì)，目前已有多個(gè)項(xiàng)目將彩虹表應(yīng)用于口令恢復(fù)中。

1.2 彩虹表生成

彩虹表由多條鏈長相同的彩虹鏈構(gòu)成。在彩虹鏈的計(jì)算過程中，有Hash與Reduct兩個(gè)關(guān)鍵函數(shù)。Hash(p)＝H為目標(biāo)的哈希函數(shù)，輸入口令p，輸入哈希值H。Reduct(H)＝p為自定義還原函數(shù)，將哈希值映射到口令空間。注意到還原函數(shù)還原后得到的口令p并不是H的原始口令，另外由于哈希的空間遠(yuǎn)大于口令空間，因此存在多個(gè)Hash能夠還原回同一口令。由于彩虹表相對(duì)于Hellman表，在不同列采用不同的還原函數(shù)是最大的不同，因此存在一組還原函數(shù)Reduct1，Reduct2……Reductl，其中l(wèi)為彩虹鏈的鏈長。

在彩虹表的計(jì)算工程中，最基本的計(jì)算步驟為:

圖1 彩虹表結(jié)構(gòu)

因此，一張鏈長為l，鏈數(shù)為n的彩虹表，邏輯構(gòu)成如下圖所示:

圖2 彩虹表結(jié)構(gòu)

在彩虹表生成，又叫做預(yù)計(jì)算，的過程中，隨機(jī)或者按照某些規(guī)則選取不同的鏈?zhǔn)?，完整?jì)算整條鏈得到鏈尾。在存儲(chǔ)時(shí)只需要存儲(chǔ)鏈?zhǔn)着c鏈尾，中間的節(jié)點(diǎn)可以在查表時(shí)根據(jù)鏈?zhǔn)子?jì)算獲得，因此壓縮了空間。

1.2 彩虹表查找

由于彩虹表存儲(chǔ)的僅僅是彩虹鏈的鏈?zhǔn)着c鏈尾，不是簡單的哈希/口令鍵值對(duì)，因此無法通過簡單的二分查找法直接，直接搜索哈希值，得到明文口令。

參考圖1，哈希值在彩虹鏈中出現(xiàn)的位置總是在前后兩個(gè)口令之間的第i列，0≤i≤l－1，因此，在查找時(shí)，分別假設(shè)哈希值出現(xiàn)在第i列，若推算出的鏈尾與彩虹表的某條鏈尾一致，那么該哈希值前的口令即為所查口令。其完整查找步驟如下:

1)設(shè)定i＝l，l為彩虹鏈的鏈長?

2)設(shè)定i－－ ?若i≤0 ，跳轉(zhuǎn)步驟 6

3)假設(shè)所查哈希值H在表中第i列，推算至鏈尾p?

4)在哈希表的鏈尾中查找p。若未找到，跳轉(zhuǎn)步驟2?若找到，得到p出現(xiàn)在第c條鏈鏈尾?

5)從第c條鏈鏈?zhǔn)子?jì)算鏈直至pc，i，驗(yàn)證 Hash(pc，i)＝ ＝H。若是，則得到正確口令pc，i，查找成功，查找結(jié)束?否則判定為誤報(bào)，跳轉(zhuǎn)步驟2?

6)查找結(jié)束，查找失敗?

相較于普通的查表法，彩虹表以查表時(shí)的計(jì)算量為代價(jià)，壓縮了表的大小，使其在工程上有了使用的價(jià)值。

2 基于GPU的彩虹表生成

雖然在恢復(fù)口令，查詢表的過程中，彩虹表的算法做到了時(shí)間空間的折中。然而彩虹表的生成，即彩虹表的預(yù)計(jì)算，依然需要消耗大量的計(jì)算能力。生成一場(chǎng)鏈長為l，鏈數(shù)為n的彩虹表，需要進(jìn)行n×l次F函數(shù)。為了生成成功率達(dá)到一定程度的彩虹表，鏈長與鏈數(shù)必須達(dá)到一定的數(shù)量，因此也造成了彩虹表生成時(shí)的龐大計(jì)算量。

鑒于此問題，本文提出利用GPU(Graphic Processing Unit，圖形處理器)進(jìn)行彩虹表生成的技術(shù)，依托GPU的高計(jì)算能力，加速彩虹表的生成。本文通過OpenCL語言，在AMD GPU上開發(fā)了彩虹表生成程序，相比CPU生成時(shí)間只有原來的幾十分之一。

2.1 GPU通用計(jì)算與OpenCL

近10年來，隨著GPU的高速發(fā)展，GPU已經(jīng)不再是只能進(jìn)行圖形計(jì)算的單一處理芯片，現(xiàn)代GPU的架構(gòu)已經(jīng)適用于通用計(jì)算。

相比于CPU，GPU在硬件設(shè)計(jì)上更多的電路被用于ALU(A-rithmetic Logic Unit，算數(shù)邏輯單元)，而在其他方面進(jìn)行了弱化，因此GPU更適合計(jì)算密集的大數(shù)據(jù)并行計(jì)算任務(wù)。而CPU在硬件上更多的單元被分配給cache(高速緩沖存儲(chǔ)器)和控制單元，因此適合于處理分支密集和隨機(jī)訪問的串行計(jì)算任務(wù)。

OpenCL(Open Computing Language)是由Khronos Group維護(hù)的開放標(biāo)準(zhǔn)的跨平臺(tái)、并行編程架構(gòu)。主流的GPU生產(chǎn)廠商，如Nvidia、AMD、Intel等，都對(duì) OpenCL標(biāo)準(zhǔn)進(jìn)行了支持。 利用OpenCL框架，可以非常容易地以SIMT(Single Instruction Multiple Thread)技術(shù)調(diào)用GPU的計(jì)算資源。

2.2 基于GPU的彩虹表生成

彩虹表的生成過程中，鏈與鏈之間相互獨(dú)立。每條彩虹鏈的計(jì)算過程一致，區(qū)別僅在于鏈?zhǔn)椎牟煌?。因此，彩虹表的生成是一種具有先天并行性的單指令多數(shù)據(jù)任務(wù)，又由于其需要特別大的計(jì)算量，特別適合于利用GPU進(jìn)行加速。

利用CPU進(jìn)行彩虹表生成時(shí)，CPU需要生成鏈?zhǔn)?，逐次串行地?jì)算每一條彩虹鏈得到鏈尾，然后將鏈?zhǔn)着c鏈尾寫入文件。

利用GPU加速彩虹表生成時(shí)，鏈?zhǔn)椎纳梢廊豢緾PU進(jìn)行控制維護(hù)。鏈?zhǔn)椎纳刹呗赃x擇線性遞增而非隨機(jī)選擇，這樣僅需向GPU傳入一個(gè)初始鏈?zhǔn)?，GPU的線程可以通過各自線程ID計(jì)算得到不同的鏈?zhǔn)祝瑴p少了輸入的數(shù)據(jù)傳輸量。每個(gè)GPU線程分別負(fù)責(zé)一條彩虹鏈的計(jì)算，得到線程的鏈?zhǔn)缀筮M(jìn)行多次Hash與Reduct直至算至鏈尾并輸出。GPU計(jì)算完成后，通過PCI－E總線將鏈尾傳輸至內(nèi)存，CPU繼續(xù)負(fù)責(zé)將鏈?zhǔn)着c鏈尾對(duì)應(yīng)并寫入文件。其基本流程可見下圖:

圖3 GPU加速的彩虹表生成流程

由于GPU的計(jì)算與鏈尾數(shù)據(jù)傳輸、寫文件等是相對(duì)獨(dú)立的過程，因此可以采用流水線技術(shù)，即，在GPU計(jì)算一批彩虹鏈的同時(shí)，CPU并非出于空閑狀態(tài)，而是進(jìn)行上一批鏈?zhǔn)祖溛埠喜?、寫文件工作，以及下一批鏈?zhǔn)椎纳伞亩s短整個(gè)過程消耗的時(shí)間，提高性能。

3 實(shí)驗(yàn)結(jié)果

目前，已有不少基于彩虹表技術(shù)的項(xiàng)目，例如 Rainbow Crack[4]、Ophcrack[5]、L0phtCrack[6]、Free Rainbow Tables[7]等。 我們利用OpenCL，在AMD GPU上實(shí)現(xiàn)了與經(jīng)典的Rainbow Crack彩虹表兼容的彩虹表生成程序。具體實(shí)驗(yàn)環(huán)境見下表:

表1 實(shí)驗(yàn)環(huán)境

我們分別實(shí)現(xiàn)了NTLM、MD5、SHA－1三種算法，并測(cè)試了彩虹表的性能。由于生產(chǎn)一張彩虹表的計(jì)算量近似于鏈長x鏈數(shù)次的F函數(shù)，這里以每秒計(jì)算F函數(shù)的次數(shù)作為主要的性能統(tǒng)計(jì)指標(biāo)。實(shí)驗(yàn)結(jié)果如下:

表2 基于GPU的彩虹表生成性能

實(shí)際生成彩虹表的時(shí)間測(cè)試中，CPU版本采用了rainbowcrack－1.6－win64中的rtgen.exe作為對(duì)比，具體結(jié)果下表所示:

表3 GPU/CPU彩虹表生成時(shí)間對(duì)比

經(jīng)過實(shí)驗(yàn)測(cè)試，可以發(fā)現(xiàn)基于GPU加速的彩虹表生成，相比于CPU能夠顯著縮短任務(wù)的運(yùn)行時(shí)間，取得了良好的效果。

另外，我們發(fā)現(xiàn)在彩虹表生成的過程中，Hash函數(shù)與Reduct函數(shù)在GPU與CPU上大不相同，CPU耗時(shí)主要在Hash函數(shù)上，而GPU耗時(shí)主要在Reduct函數(shù)上，如表4所示。

表4 Reduct函數(shù)計(jì)算時(shí)間占比

這主要是由GPU硬件特性所致。MD系列的哈希函數(shù)(包括MD4變種NTLM)以及由MD發(fā)展而來的SHA－1，SHA－2系列哈希函數(shù)，計(jì)算主要用到ARX指令，即整數(shù)加法、移位與異或，并且計(jì)算過程固定無分支，特別適合GPU計(jì)算實(shí)現(xiàn)。然而Reduct函數(shù)一方面是用到字節(jié)讀寫以拼接口令，并不適合32比特的GPU。另一方面Reduct函數(shù)還原出的口令長短不同，因而Reduct函數(shù)必在不同GPU線程之間產(chǎn)生分支?而GPU硬件特點(diǎn)就是強(qiáng)于計(jì)算而弱于分支控制，因此Reduct函數(shù)在GPU上實(shí)現(xiàn)的性能極其低下，以至于拖慢整體彩虹表生成的性能。

4 結(jié)語

在CUDA、OpenCL框架的帶動(dòng)下，GPU的通用計(jì)算逐步流行，并在各個(gè)行業(yè)得到應(yīng)用。本文利用GPU對(duì)彩虹表的生成進(jìn)行了加速，取得了良好的效果，大幅縮短彩虹表生成所需的時(shí)間。然而，我們同時(shí)也發(fā)現(xiàn)，由于硬件架構(gòu)的GPU原因，Reduct函數(shù)在GPU上實(shí)現(xiàn)的性能極低。因此，進(jìn)一步設(shè)計(jì)針對(duì)GPU的Reduct函數(shù)，替代rainbow crack中經(jīng)典的還原函數(shù)，能夠進(jìn)一步提高GPU計(jì)算彩虹表的性能。

[1] M.E.HELLMAN.A Cryptanalytic Time－Memory Trade－Off[J].Information Theory， IEEE Transactions on， 1980，26(4):401－406.

[2] Oechslin P.Making a Faster Cryptanalytic Time－Memory trade－off[M].Advances in Cryptology－CRYPTO 2003.Springer Berlin Heidelberg， 2003:617－630.

[3] Tarditi D，Puri S，Oglesby J.Accelerator:using data parallelism to program GPUs for general－purpose uses[C]//ACM SIGARCH Computer Architecture News.ACM，2006，34(5):325－335.

[4] S.Zhu.RainbowCrack Project[EB/OL].2014[2014－11－17].http://project－rainbowcrack.com/.

[5] Objectif Securite.Ophcrack[EB/OL].2014[2014－11－17].http://ophcrack.sourceforge.net/.

[6] L0phtCrack.L0phtCrack[EB/OL].2014[2014－11－17]http://www.l0phtcrack.com/.

[7] Free Rainbow Tables，Distributed Rainbow Table Project[EB/OL].2014[2014－11－17].https://www.freerainbowtables.com/.