基于映射的解密目標GPU快速比對法研究

謝鑫君，朱智慧，羅 順

(上海通用識別技術研究所，上海 201112)

基于映射的解密目標GPU快速比對法研究

謝鑫君，朱智慧，羅 順

(上海通用識別技術研究所，上海 201112)

GPU等加速設備在散列值暴力破解中有著廣泛的應用。在GPU上進行散列值暴力破解時，時常需要進行大量的目標散列值比較，因為GPU在邏輯判斷方面運算速度慢，使用二分比較法等經典算法存在一定的局限性。針對GPU的特點,提出了一種解密目標的快速比對方法。設計了一種目標映射關系，并基于這種映射關系實現了解密目標的快速比對，能降低比對復雜度，大幅提升解密效率。同時，實驗分別基于經典二分法和快速比對方法實現了基于GPU的MD5暴力破解算法。在實際實驗中，單目標情況下兩者速度基本相同。但使用二分法比對時,針對1萬個目標時的速度僅為單目標時的36%。相同的實驗環境下，基于映射的解密目標GPU快速比對算法效率有著明顯提升，針對1萬個目標時的速度為單目標時的95%，相比較速度提升了163%。

GPU設備；暴力破解；目標匹配；快速比對；MD5算法

0 引 言

散列算法在完整性校驗、數字簽名和安全身份認證等信息安全領域有著廣泛的應用[1]，因此，各類散列算法的快速破解對信息安全與取證有著重要的實際意義。由于散列算法的不可逆性，暴力破解成為主要的攻擊方式[2-3]。但同時由于密鑰空間的龐大性，使得暴力破解對破解系統計算能力有著更高的要求，通常需要使用分布式計算[4-5]，甚至使用GPU等硬件加速設備[6-10]。

在GPU上作散列值解密時，需要將計算出的每個散列值與大量的目標散列值進行比較。而對于MD5

等暴力破解口令嘗試次數較快的散列破解算法中，對每個猜測密鑰所生成的散列值與大量目標散列值的比較占據了相當比例的時間。文獻[11]中，將GPU生成的散列值傳送至CPU端再與目標散列值進行比較，該方法帶來了大量數據傳輸引起的時間消耗。文獻[2]直接在GPU端進行逐一比較，導致破解耗時與目標數量正相關，實際破解含1個、10個、100個MD5散列值的耗時分別為2 s、6.1 s和36 s。同時，由于GPU在邏輯判斷方面的運算速度慢，經典的二分比較法也存在一定的局限性。

文中著眼于基于GPU的解密目標比對方法研究。針對GPU的并行運算特點[12-14]，提出了基于目標映射的GPU解密目標快速比對方法，并分別實現了基于經典二分比較法和基于目標映射GPU快速比對法的MD5暴力破解程序，充分驗證了提出的GPU快速比對法對暴力破解效率的有效提升。

1 暴力破解算法原理及二分法比對

散列值暴力破解的基本原理是依照一定規律不斷嘗試不同口令進行哈希運算，然后將結果與目標哈希值進行對比，不相同則繼續嘗試其他口令，相同則表示破解成功，如圖1所示。由于對不同的嘗試密鑰，散列的實現互不相關，因此，散列的實現和比較是理想的并行運算模式。使用GPU等高速并行運算設備，可大幅提高相應破解效率。

圖1 暴力破解基本原理

在將結果與目標哈希值進行對比的過程中，最樸素的思路是逐一比對，即將運算結果與目標哈希值逐一進行比對。該方法實現簡單并且無需對目標哈希值做任何處理，但是目標哈希數量一旦增加，效率將嚴重降低[2]。

經典的比對方法是二分法比對。CPU端得到所有目標哈希值后，先將所有哈希值進行升序排列，而后在GPU中計算出當前嘗試口令對應的哈希值時，即可在進行二分法匹配。偽代碼如下：

//初始化區間下限a為0，區間上限b為hashcount-1；

for(i，a

c=ceil((a+b)/2) //取中間值

if(hash_out==HASH(c)) break;

else if(hash_out>HASH(c))a=c;continue;

elseb=c; continue;

end for

//其中hash_out表示利用猜測密鑰生成的散列值，HASH(c)表示經過升序排列后目標散列值中的第c個。

使用多哈希值二分法匹配，如對1 024個哈希值進行匹配，從最多1 024次降低至最多僅需10次。有效地提升了匹配速度，使得多哈希值并行暴力破解的口令嘗試速度在一定程度上接近于單哈希值破解情況下的速度。

值得注意的是，在使用經典二分法進行解密目標匹配時，需要提前對解密目標進行升序或者降序排序。

2 基于映射的GPU快速比對法

在GPU暴力破解中，解密目標比對方法的設計關系到如何有效地利用GPU硬件資源。文中設計了一種基于目標映射的GPU解密目標快速比對方法，在比對過程中充分考慮GPU運算的特點，減少邏輯判斷，提升暴力破解效率。并以MD5算法為例進行闡述，如需針對其他算法也可直接使用基于映射的GPU快速比對方法，僅需根據算法散列值長度對相關參數進行調整即可。

2.1基本原理

將N個MD5目標散列值通過一定的映射關系映射到特定內存空間，在GPU端計算出每個猜測口令對應的散列值時，僅需用同樣的映射關系計算并結合之前的映射空間，即可完成匹配。該方法的關鍵是設計一種良好的目標映射關系。為保證效率，設計的映射關系及匹配比對方法需要滿足如下條件：

(1)邏輯判斷盡量要少；

(2)需要進行分步判斷，并在初步判斷去除足夠數量的錯誤選項；

(3)確保結果無遺漏。

映射關系可簡單地描述為將目標散列值的某些bit位作為地址，而將某些bit位作為該地址下存儲的值。此時，對每一個猜測口令也遵循同樣的映射獲得地址，讀取內存空間該地址下的值是否匹配直接計算出來的值，來判斷口令的正確性。

2.2目標映射關系設計

將N個值映射到一塊內存空間中，映射方法如下:每個值以4字節(1個UINT)為單位，那么一個散列值由4個UINT組成，對每個UINT，將UINT的最低5個比特取出(其值計為a1)，再從UINT第6個bit開始往高取16位(其值計為b1)也取出，如圖2所示。當MD5值第一個UINT為0x6789ABCD時，a1=01101=13，b1=0100110101011110=19 806。

圖2 目標映射關系示意圖

創建一個大小為2的16次方，也就是長度為65 536的UINT數組M1[65 536]，并將M數組置0。接著就設定M[b1]|=(1?a1)，就是將M數組的第b個成員的值異或上(1左移a1位的值)。通過這樣的計算，將一個UINT中的21bit數據映射到一個數組中。如果這個UINT再映射一次，并且將b的位與第一次的選擇錯開。該例中使用從高位至低位取16個bit(其值計為b2)，那么就可以映射更多的位到數組中。對于1個UINT通過兩次計算即可以全部映射到2個數組中。

用這種方法，一個散列值的4個UINT最多通過8次計算就能全部映射到數組中。為了防止產生過多的沖突，考慮每次映射使用單獨的數組，也就是生成M1～M8共8個數組。產生8個數組的全部存儲空間需要65 536*4*8=2 MB空間。

該方法在設計過程中可調整的參數主要有3個，分別是a的長度、b的長度和數組的個數。a的長度取5 bit，即a的取值范圍為0～32，這將意味著數組M中的值恰好可以用UINT類型表示。b的長度決定了數組M的空間大小，b越大，則M所占用的內存空間越大，兩者呈指數關系。數組的個數則是由b的長度和目標散列值的長度來共同決定。

M[b]|=(1?a)中使用異或是因為，不同的散列值有可能存在同樣的b值而有著不同的a值，這就要求M[b]的值要體現不同的a值。使用異或可以完整保存所有相關的a值，即某bit為1代表存在相應的a值，以減少沖突。

2.3匹配比對

多哈希值并行破解會增加一些查詢與內存訪問開銷，但總的破解效率會得到極大提升。

首先，CPU需要將所有哈希值內容和哈希值個數傳遞至GPU。其次，GPU各線程根據口令自生成規則[10]產生的嘗試口令對進行MD5散列運算。最后，使用基于目標映射的GPU快速比對方法進行匹配，并將是否匹配成功等信息傳遞至CPU。

對于散列值A，將第一個UINT使用同樣的方法獲得a1和b1，然后計算c1=M1[b1]|=(1?a1)。如果c1為非0，那就意味著A可能命中；如果c1為0，意味著A肯定沒有命中。當c1為非0時，判斷A第二個UINT的情況，從第二個UINT獲得a2和b2,然后計算c2=M2[b2]&(1?a2)。如果c2為非0，那就意味著A可能命中；如果c2為0，意味著A肯定沒有命中。以此類推，如果c3～c8一直為非0，那就最終判斷出A可能命中了。但是大多數情況下，通過c1的概率約為200萬分之一(1/2的21次方)，通過c2的概率約為4萬億分之一，大部分散列值通過前幾次判斷就會被淘汰。

在GPU端判斷出A可能命中的情況下，需要進一步利用CPU相關程序進行驗證，確保解密結果無誤中。這是因為，在GPU端進行的目標映射并非一一對應，極小概率存在誤中。當然，這概率極小，對速度不存在影響，只是從邏輯上確保沒有誤中而增加CPU端的進一步判斷。

2.4速度與存儲空間的折衷

速度與占用空間的折衷也是設計映射關系要著重考慮的因素。

當目標數量大幅增加時，上述以16 bit為單位的映射方法將散列值的第一個UINT映射到了大小為65 536的空間中，當散列值的數量達到幾萬個時，可能會存在大量的沖突情況。如果繼續以16 bit為單位將目標映射到內存空間，會導致在各個步驟誤中的概率增加，從而增加整體的計算時間。

一種可行的提高效率的方法就是增加空間。方法是將b的位數(原先為16 bit)往上增加，比如當目標數量達到100萬個左右時，考慮將b的位數增加到20 bit。這樣雖然會產生一定的沖突，但是數量可控。當然增加位數后，占用的空間大小將從2 MB增加到32 MB。

3 實驗結果與分析

實驗中準備7個目標，依次為1個、10個、100個、1 000個、10 000個、10萬個、100萬個md5值，分別在GPU上使用二分法快速比對和文中比對方法進行暴力破解計算，結果如表1所示。兩個實驗中除了目標匹配的對比方法不同，其余均相同。

表1 不同比對法的MD5暴力破解速度對比

當目標個數為1時，兩者速度基本一致。而隨著目標數量的增加，使用二分法比對的效率逐漸降低，超過10 000個目標時，效率僅有單目標的36%。而相同的實驗環境下，使用文中的快速比對技術的MD5暴力破解算法，針對超過10 000個目標時效率有單目標的95%。可見提出的目標快速比對算法效率有著明顯提升，目標數量越多，提升效率越明顯。實驗中單目標情況下兩者速度基本相同，針對1萬個目標時，文中GPU快速比對方法比經典二分法提升了163%，而針對10萬個目標時，文中GPU快速比對方法比經典二分法提升了279%。具體如圖3所示。

圖3 文中方法與二分法針對不同 目標數量的效率提升幅度

這也和之前的預期是一致的，充分證明了提出方法的有效性和優越性。

4 結束語

GPU作為高速并行運算設備，在各類口令暴力破解中的作用日益凸顯。基于目標映射，設計了一種在GPU上進行的解密目標快速比對方法，使得暴力破解的效率顯著提升。同時，還實現了基于經典二分比對法和基于該方法的MD5暴力破解程序，充分驗證了提出的GPU快速比對法對暴力破解效率的有效提升。

實驗結果表明，使用二分法比對的MD5暴力破解算法，隨著解密目標數量的增加，效率逐漸降低。在相同的實驗環境下，使用文中的目標快速比對算法，效率提升明顯，且目標數量越多，提升效率越明顯。

文中方法可以應用于各種散列類型的解密程序中，針對不同目標類型僅需修改方法中部分參數即可，使用十分便捷。針對散列類型的暴力破解尤其是針對本身加密速度很快的散列類型有著極大的提升作用。

[1] Forouzan B A.密碼學與網絡安全[M].馬振晗，賈軍保，

譯.北京:清華大學出版社,2009.

[2] 翁 捷，吳 強，楊燦群.基于OpenCL的MD5破解算法[J].計算機工程，2011，37(4)：119-121.

[3] Chen R,Zhang Y,Zhang J,et al.Design and optimizations of the MD5 crypt cracking algorithm based on CUDA[C]//International conference on cloud computing.[s.l.]:Springer International Publishing,2015:155-164.

[4] 張麗麗，張玉清.基于分布式計算的暴力破解分組密碼算法[J].計算機工程,2008,34(13)：121-123.

[5] 石志才.異構平臺上協同計算的相關研究[D].長沙：國防科學技術大學,2011.

[6] Vu A D,Han J I,Nguyen H A,et al.A homogeneous parallel brute force cracking algorithm on the GPU[C]//International conference on ICT convergence.[s.l.]:IEEE,2011:561-564.

[7] Niewiadomska-Szynkiewicz E,Marks M,Jantura J,et al.Comparative study of massively parallel cryptalysis and cryptography on CPU-GPU cluster[C]//Military communications and information systems conference.[s.l.]:[s.n.],2013:1-8.

[8] 樂德廣，常晉義，劉祥南,等.基于GPU的MD5高速解密算法的實現[J].計算機工程,2010,36(11):154-155.

[9] Wang F,Yang C,Wu Q,et al.Constant memory optimizations in MD5 crypt cracking algorithm on GPU-accelerated supercomputer using CUDA[C]//International conference on computer science & education.[s.l.]:[s.n.],2012:638-642.

[10] 謝鑫君，羅 順，楊士華.基于口令自生成的GPU暴力破解優化技術[J].信息安全與通信保密,2013(3):82-84.

[11] 張 奇.基于CUDA架構的MD5并行破解算法設計與實現[D].成都：電子科技大學,2012.

[12] 陳 鋼，吳百鋒.面向OpenCL模型的GPU性能優化[J].計算機輔助設計與圖形學學報,2011,23(4):571-581.

[13] 張潤梅，王 霄.基于CUDA架構的MD5破解方法研究[J].計算機科學,2011,38(2):302-304.

[14] 于 飛,吉慶兵,羅 順,等.GPU計算及其在密碼分析中的應用[J].信息安全與通信保密,2012(12):98-100.

ResearchonQuickComparisonforCrackingofGPUBasedonMapping

XIE Xin-jun,ZHU Zhi-hui,LUO Shun

(Shanghai General Recognition Technology Institute，Shanghai 201112，China)

Acceleration equipment such as GPU is widely used in the brute-force cracking.It always has large number of hashes to compare when carrying through brute cracking on GPU.However,the use of classical algorithm such as dichotomy has certain limitation because of the poor computing ability of GPU in the logic judgment operation.A quick comparison method is proposed for cracking based on GPU and a kind of object mapping relation is designed to achieve the quick comparison for cracking,which can reduce the complexity of the target comparing and significantly enhance the efficiency.Meanwhile,the experiment uses classical dichotomy and quick comparison to crack MD5 hashes based on GPU.In the actual experiment,both speed under single target are substantially the same.But using dichotomy,the speed under 10 000 targets is 36% of that under single target.Under the same experimental environment,the speed with quick comparison algorithm under 10 000 targets is 95% of that under single target,which is lifting 163%.

GPU;brute-force cracking;target matching;quick comparison;MD5 algorithm

2016-09-19

2017-02-17 < class="emphasis_bold">網絡出版時間

時間：2017-08-01

國家科技支撐計劃(2014BAH41B03)

謝鑫君(1980-)，男，碩士，研究方向為信息安全。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170801.1549.016.html

TP301

A

1673-629X(2017)11-0119-04

10.3969/j.issn.1673-629X.2017.11.026