基于GPU的高性能彩虹表生成?

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

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

0 引言

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

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

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

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

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

1 彩虹表算法

1.1 時間空間折中

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

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

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

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

1.2 彩虹表生成

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

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

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

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

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

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

1.2 彩虹表查找

由于彩虹表存儲的僅僅是彩虹鏈的鏈首與鏈尾，不是簡單的哈希/口令鍵值對，因此無法通過簡單的二分查找法直接，直接搜索哈希值，得到明文口令。

參考圖1，哈希值在彩虹鏈中出現(xiàn)的位置總是在前后兩個口令之間的第i列，0≤i≤l－1，因此，在查找時，分別假設(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條鏈鏈首計算鏈直至pc，i，驗證 Hash(pc，i)＝ ＝H。若是，則得到正確口令pc，i，查找成功，查找結(jié)束?否則判定為誤報，跳轉(zhuǎn)步驟2?

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

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

2 基于GPU的彩虹表生成

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

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

2.1 GPU通用計算與OpenCL

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

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

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

2.2 基于GPU的彩虹表生成

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

利用CPU進行彩虹表生成時，CPU需要生成鏈首，逐次串行地計算每一條彩虹鏈得到鏈尾，然后將鏈首與鏈尾寫入文件。

利用GPU加速彩虹表生成時，鏈首的生成依然靠CPU進行控制維護。鏈首的生成策略選擇線性遞增而非隨機選擇，這樣僅需向GPU傳入一個初始鏈首，GPU的線程可以通過各自線程ID計算得到不同的鏈首，減少了輸入的數(shù)據(jù)傳輸量。每個GPU線程分別負責一條彩虹鏈的計算，得到線程的鏈首后進行多次Hash與Reduct直至算至鏈尾并輸出。GPU計算完成后，通過PCI－E總線將鏈尾傳輸至內(nèi)存，CPU繼續(xù)負責將鏈首與鏈尾對應(yīng)并寫入文件。其基本流程可見下圖:

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

由于GPU的計算與鏈尾數(shù)據(jù)傳輸、寫文件等是相對獨立的過程，因此可以采用流水線技術(shù)，即，在GPU計算一批彩虹鏈的同時，CPU并非出于空閑狀態(tài)，而是進行上一批鏈首鏈尾合并、寫文件工作，以及下一批鏈首的生成。從而縮短整個過程消耗的時間，提高性能。

3 實驗結(jié)果

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

表1 實驗環(huán)境

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

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

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

表3 GPU/CPU彩虹表生成時間對比

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

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

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

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

4 結(jié)語

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

[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/.