張 恒，趙榮彩，董本松

(1.中原工學(xué)院計(jì)算機(jī)學(xué)院，河南 鄭州 450007； 2.中原工學(xué)院前沿信息技術(shù)研究院，河南 鄭州 450007)

0 引 言

隨著個(gè)人對(duì)信息加密的重視，一般的弱密碼基本上不再使用，現(xiàn)在各大網(wǎng)站和手機(jī)軟件APP也要求用戶設(shè)置更復(fù)雜的密碼，并對(duì)密碼長(zhǎng)度也有了相應(yīng)要求。這給解密工作帶來(lái)極大的挑戰(zhàn)，導(dǎo)致需要更多的時(shí)間進(jìn)行解密。盡管MD5的解密算法運(yùn)行速度很快，但是由于密碼的復(fù)雜性，需要更多時(shí)間進(jìn)行破解，并且隨著密碼長(zhǎng)度的增加，所需要的時(shí)間更是以指數(shù)速度增長(zhǎng)，當(dāng)前一般的單核和多核處理器已經(jīng)逐漸滿足不了MD5解密的需要。

本文研究關(guān)于申威26010眾核處理器上的MD5解密算法優(yōu)化。申威26010處理器是我國(guó)自主研發(fā)的異構(gòu)眾核處理器[1]。主核和從核之間具有并行協(xié)作的特點(diǎn)，使其具有超高的并行計(jì)算能力，以及較好的靈活性，極大地滿足了解密算法對(duì)處理器計(jì)算能力的要求。

1 相關(guān)研究

1.1 研究現(xiàn)狀

文獻(xiàn)[2]指出可對(duì)MD5算法進(jìn)行重復(fù)性攻擊，采用循環(huán)展開(kāi)的技術(shù)可以提升MD5運(yùn)算速度。文獻(xiàn)[3]對(duì)MD5解密算法進(jìn)行了分析，在GPU上使用CUDA編程實(shí)現(xiàn)MD5解密算法，解密速度比CPU明顯提高。文獻(xiàn)[4]在FPGA上提出了一種新的全流水線架構(gòu)，使MD5運(yùn)算的吞吐量達(dá)到了設(shè)備的理論峰值。文獻(xiàn)[5]在FPGA上對(duì)MD5運(yùn)算的關(guān)鍵路徑中加法運(yùn)算進(jìn)行了優(yōu)化，縮短了B的運(yùn)算時(shí)間。文獻(xiàn)[6]在FPGA上對(duì)MD5解密算法進(jìn)行優(yōu)化，采用預(yù)計(jì)算和引入中間寄存器的方式縮短了關(guān)鍵路徑，進(jìn)一步優(yōu)化了運(yùn)算流程。文獻(xiàn)[7]提出了在FPGA上優(yōu)化MD5內(nèi)部算法，將串行數(shù)據(jù)進(jìn)行了并行處理，最后對(duì)設(shè)計(jì)的算法進(jìn)行了ModelSim仿真驗(yàn)證。文獻(xiàn)[8]在申威26010處理器上提出了字符空間展開(kāi)系統(tǒng)，在口令生成過(guò)程中使用了復(fù)雜正則表達(dá)式和碰撞變形2種生成規(guī)則，最后對(duì)MD5散列算法進(jìn)行了口令的正確性驗(yàn)證。

本文在申威26010眾核處理器上進(jìn)行MD5解密算法實(shí)現(xiàn)，對(duì)解密算法進(jìn)行優(yōu)化，并結(jié)合該處理器施行了多線程優(yōu)化方法，整體提高解密算法的運(yùn)算速度。

1.2 申威26010眾核處理器

如圖1所示，申威26010異構(gòu)眾核處理器是由4個(gè)互連的核組(Core Groups, CG)構(gòu)成[9]，每個(gè)核組都包括1個(gè)管理主核[10](Manage Processing Elements， MPE)和64個(gè)計(jì)算從核[11](Computing Processing Elements， CPE)構(gòu)成的從核簇[12]。64個(gè)從核在處理器中是以8×8的從核陣列形式存在，每個(gè)核組都可以通過(guò)眾核處理器的片上互聯(lián)網(wǎng)絡(luò)直接訪問(wèn)共享主存。

每個(gè)核組都有8 GB內(nèi)存，而從核局部存儲(chǔ)空間(LDM)為64 kB[14]。從核局存訪問(wèn)主存有2種方式，一種是直接訪問(wèn)主存，通過(guò)全局gld/gst指令進(jìn)行，另一種是由從核發(fā)起的DMA方式，DMA傳輸支持批量傳輸，傳輸效率更加高效，時(shí)間損耗更低。因?yàn)榫幾g器的限制，在編譯從核端的程序代碼時(shí)，如果未顯式指定DMA方式訪問(wèn)內(nèi)存數(shù)據(jù)，編譯器將會(huì)默認(rèn)生成全局gld/gst指令進(jìn)行訪問(wèn)，給算法運(yùn)行造成極大的訪存開(kāi)銷(xiāo)。因此，用戶在編程時(shí)需要認(rèn)真研究主從核數(shù)據(jù)傳輸方式，盡可能使用DMA方式在主存和從核上的局存之間傳輸數(shù)據(jù)，進(jìn)一步優(yōu)化程序。

2 MD5解密算法優(yōu)化

MD5屬于散列算法[15]，該算法主要包括4個(gè)步驟：1)消息補(bǔ)位[16]；2)初始的鏈接變量[17]；3)消息處理[18]；4)結(jié)果輸出[19]。通過(guò)上述4步將輸入的任意長(zhǎng)度消息轉(zhuǎn)換成128 bit固定長(zhǎng)度散列值[20]。因?yàn)镸D5算法加密是不可逆過(guò)程，無(wú)法通過(guò)散列值直接得到原文密碼，所以在破解時(shí)一般會(huì)選擇暴力破解方式[21]，通過(guò)窮舉攻擊密碼轉(zhuǎn)換成散列值進(jìn)行破解。本文根據(jù)解密實(shí)際情況，選擇破解56 bit長(zhǎng)度及以下的密碼。

2.1 MD5解密流程圖

對(duì)于傳統(tǒng)的MD5解密算法，解密流程是循環(huán)產(chǎn)生攻擊密碼進(jìn)行MD5加密運(yùn)算，之后再將散列值進(jìn)行匹配，直到得到正確的明文密碼。本文在傳統(tǒng)的MD5解密算法上進(jìn)行了3點(diǎn)改進(jìn)(如圖2所示)：

1)添加了目標(biāo)散列初始化，將從命令行上得到的目標(biāo)散列進(jìn)行預(yù)處理，將散列值從字符串賦值給數(shù)組。

2)對(duì)MD5加密運(yùn)算進(jìn)行優(yōu)化，對(duì)MD5中的64步循環(huán)進(jìn)行了循環(huán)展開(kāi)，去除了分支判斷語(yǔ)句。對(duì)64步運(yùn)算進(jìn)行了優(yōu)化，分別是鏈接變量?jī)?yōu)化、61步優(yōu)化和申請(qǐng)內(nèi)存優(yōu)化。

3)修改了解密成功的判斷條件，對(duì)于優(yōu)化后的解密算法，散列值在程序中已經(jīng)從字符串賦值給了數(shù)組，在進(jìn)行判斷時(shí)可以直接進(jìn)行對(duì)比，不需要將MD5運(yùn)算產(chǎn)生的值進(jìn)行拼接。

(a) 優(yōu)化前 (b) 優(yōu)化后圖2 MD5優(yōu)化前后解密流程圖

2.2 散列初始化

對(duì)于MD5加密算法，需通過(guò)64步運(yùn)算以及結(jié)果拼接才能生成MD5散列值，但是對(duì)于解密，散列生成過(guò)程中的結(jié)果拼接比較耗費(fèi)時(shí)間，所以對(duì)解密算法進(jìn)行了優(yōu)化。為了與最后的MD5算法64步運(yùn)算結(jié)果a、b、c、d相對(duì)應(yīng)，對(duì)目標(biāo)散列進(jìn)行了初始化，將散列分為4份賦值給數(shù)組。最后直接判斷a、b、c、d和數(shù)組對(duì)應(yīng)的值是否相同即可，無(wú)需進(jìn)行字符串的拼接。具體實(shí)現(xiàn)見(jiàn)算法1。

算法1 target hash initialization operation

輸入: argv, MD5

//argv:command line parameter

//MD5:initial Chaining Variable

輸出：md5_in

//md5_in: array of the hash

1 md5_input←argv[1]

2 forifrom 0 to 3

3 md5_in[i]←hex_to_u32 & md5_input[i×8]

//assigns the md5_input string to the array md5_in

4 md5_in[i]←byte_swap_32(md5_in[i])

//convert the big end to the small end

5 md5_in[i]←md5_in[i]-MD5[i]

//subtract the corresponding Chaining variable

6 end for

先將輸入的目標(biāo)散列argv[1]賦值給變量md5_input，再將該變量對(duì)應(yīng)位賦值給數(shù)組md5_in，將該數(shù)組的值從大端模式轉(zhuǎn)換成小端模式(申威處理器寄存器運(yùn)算采用小端模式)，數(shù)組中的值減去對(duì)應(yīng)初始鏈接變量，對(duì)解密做進(jìn)一步優(yōu)化運(yùn)算，該步在鏈接變量?jī)?yōu)化處說(shuō)明。

2.3 MD5運(yùn)算優(yōu)化

本節(jié)針對(duì)MD5循環(huán)64步運(yùn)算進(jìn)行優(yōu)化，每步運(yùn)算是由對(duì)應(yīng)壓縮函數(shù)完成。因?yàn)楸疚膶?duì)密碼長(zhǎng)度56 bit及以下進(jìn)行解密，所以采用循環(huán)展開(kāi)、鏈接變量?jī)?yōu)化、61步優(yōu)化、申請(qǐng)內(nèi)存優(yōu)化等方法對(duì)解密過(guò)程進(jìn)行優(yōu)化，減少了算法的冗余步驟，優(yōu)化了解密算法的性能，使破解速度進(jìn)一步加快。

2.3.1 循環(huán)展開(kāi)

循環(huán)展開(kāi)是循環(huán)中常用的優(yōu)化方法[22]。它將循環(huán)體中的代碼展開(kāi)，以減少循環(huán)分支給算法帶來(lái)的時(shí)間損耗，并提高算法的運(yùn)行速度。MD5的64步循環(huán)運(yùn)算一般分成4組循環(huán)體，根據(jù)當(dāng)前執(zhí)行次數(shù)進(jìn)行對(duì)應(yīng)循環(huán)操作，但是在每次進(jìn)行下一次的操作時(shí)都會(huì)進(jìn)行if的分支判斷，所以可以將MD5算法中的64步循環(huán)操作循環(huán)展開(kāi)，降低循環(huán)開(kāi)銷(xiāo)，從而提高算法解密效率。在循環(huán)中，數(shù)組的值也無(wú)法確定賦值，只能在執(zhí)行過(guò)程中根據(jù)循環(huán)次數(shù)進(jìn)行數(shù)組的對(duì)應(yīng)取值，這樣也會(huì)增加指令操作時(shí)間，進(jìn)行循環(huán)展開(kāi)后，壓縮函數(shù)的數(shù)組參數(shù)可以設(shè)置為常量，省去數(shù)組的取值操作。如圖3所示，圖中將第4個(gè)循環(huán)體展開(kāi)，減少了中間的賦值操作，消除了分支判斷語(yǔ)句，添加了61步優(yōu)化方法，提高了程序的性能。

圖3 循環(huán)展開(kāi)和61步優(yōu)化

2.3.2 循環(huán)優(yōu)化

循環(huán)優(yōu)化包括了鏈接變量?jī)?yōu)化、61步優(yōu)化、申請(qǐng)內(nèi)存優(yōu)化等優(yōu)化方法。

1)鏈接變量?jī)?yōu)化。

對(duì)于本文的MD5加密算法，最后的結(jié)果需要加上對(duì)應(yīng)鏈接變量，而對(duì)于解密，可以將該操作放到前面進(jìn)行，即將散列初始化后的值減去對(duì)應(yīng)鏈接變量，便會(huì)使程序在循環(huán)破解中省去4步加法運(yùn)算。

2)61步優(yōu)化。

MD5在加密時(shí)64步運(yùn)算是必要步驟，但在解密方面，為了更快地破解，可以對(duì)算法作進(jìn)一步優(yōu)化。經(jīng)過(guò)MD5運(yùn)算得到的a、b、c、d可以直接與散列初始化后的數(shù)組對(duì)應(yīng)值進(jìn)行匹配。但是經(jīng)過(guò)算法分析與實(shí)驗(yàn)得知，MD5算法在經(jīng)過(guò)單輪循環(huán)61步運(yùn)算之后a的值便不再改變，即從第61步到完成64步運(yùn)算，這期間a的值是不變的，所以可以進(jìn)一步優(yōu)化解密算法，提前對(duì)a的值進(jìn)行判斷。在實(shí)際破解中，若a與數(shù)組對(duì)應(yīng)值不相同，則解密算法可以省去之后的3步壓縮函數(shù)運(yùn)算，使解密速度進(jìn)一步加快。

3)申請(qǐng)內(nèi)存優(yōu)化。

MD5加密算法在消息進(jìn)行補(bǔ)位時(shí)需要定義指針變量申請(qǐng)內(nèi)存空間，通過(guò)malloc函數(shù)在程序運(yùn)行時(shí)向操作系統(tǒng)申請(qǐng)分配內(nèi)存，為動(dòng)態(tài)分配方式。本文的解密是針對(duì)56 bit及以下的密碼長(zhǎng)度進(jìn)行，所以該指針變量申請(qǐng)的內(nèi)存空間最終是一個(gè)固定大小內(nèi)存，即512 bit。因此在程序中可以將申請(qǐng)動(dòng)態(tài)內(nèi)存空間改寫(xiě)成數(shù)組定義，數(shù)組是在程序編譯時(shí)由編譯器分配內(nèi)存，在程序運(yùn)行前預(yù)先分配，為靜態(tài)分配方式。程序經(jīng)過(guò)改寫(xiě)之后，可以進(jìn)一步提高運(yùn)行速度。

3 基于申威26010眾核處理器的MD5解密并行算法設(shè)計(jì)與實(shí)現(xiàn)

申威26010眾核處理器大部分的計(jì)算性能都是由從核簇提供[23]，為了充分使用該眾核處理器的計(jì)算性能，通過(guò)申威系統(tǒng)提供的Athread線程庫(kù)對(duì)解密算法進(jìn)行改寫(xiě)，將計(jì)算任務(wù)放到從核簇上進(jìn)行，加快程序的整體運(yùn)行速度。

3.1 任務(wù)并行設(shè)計(jì)

因?yàn)樯傻墓裘艽a相互之間沒(méi)有依賴(lài)關(guān)系，所以MD5解密算法支持多線程并行執(zhí)行。對(duì)于申威26010眾核處理器，主核通過(guò)Athread線程庫(kù)調(diào)用64個(gè)從核并行進(jìn)行解密，64個(gè)從核序號(hào)是從0～63。

在主核上進(jìn)行散列初始化、鏈接變量?jī)?yōu)化、從核調(diào)用及任務(wù)更新等運(yùn)算，具體實(shí)現(xiàn)如算法2所示。

算法2 main core main program

輸入：current，NLOOP, is_find

//current: the current number of tasks

//NLOOP:number of tasks per run

//is_find:end mark bit

輸出：host_start

//host_start: transfer to the initial value of the slave kernel

1 target hash initialization operation

2 host_start←current

3 athread_init() //initializes the slave thread

4 while(is_find !=1)

//call the decryption calculation from the core

5 athread_spawn(func,0)

6 athread_join()

//tasks are updated and logged

7 current←current+NLOOP

8 host_start←current

9 athread_halt()

計(jì)算任務(wù)從主核放到從核時(shí)，需要對(duì)從核進(jìn)行任務(wù)分配，使每個(gè)從核任務(wù)負(fù)載均衡且任務(wù)不重復(fù)。每個(gè)從核同步進(jìn)行解密任務(wù)，依次生成攻擊密碼、MD5運(yùn)算和對(duì)比驗(yàn)證，破解成功后將結(jié)果傳輸?shù)街骱?，具體實(shí)現(xiàn)見(jiàn)算法3。

算法3 from the core main parallel program

輸入:count,host_start,md5_in,id,total

//count:the current number of tasks

//host_start:number of tasks per run

//md5_in:the array after the hash is initialized

//id:from the nuclear serial number

//total:the current number of tasks

輸出：password, is

//password: generated attack password

//is:crack the successful flag bit

//gets the task transferred from the main core

1 athread_get(PE_MODE,&md5_in[0],&digest[0],sizeof(u32)*4,&get_reply,0,0,0)

2 athread_get(PE_MODE,&host_start,&total,sizeof(int)*4,&get_reply,0,0,0)

3 athread_syn(ARRAY_SCOPE,0xffff)

//Synchronization between Core Groups

//from the nuclear task assignment

4 start←total+id*count

5 end←total+count*(id+1)

6 forifrom start to end

7 password←number_to_password(i)

//generate attack password

8 attack password is encrypted with MD5

9 if((a==md5_in[0]) && (b==md5_in[1])&&(c==md5_in[2])&&(d==md5_in[3]))

//judge the result of cracking

10 athread_put(PE_MODE,&is,&is_find,sizeof(int),&put_reply,0,0)

11 athread_put(PE_MODE,password,pass,sizeof(int),&put_reply,0,0)

12 end if

13 end for

3.2 訪存優(yōu)化

在開(kāi)始將計(jì)算任務(wù)放到從核上時(shí)采用的是直接訪問(wèn)主存方式，該方式訪存速度慢，并且從核程序運(yùn)行時(shí)會(huì)頻繁訪問(wèn)主存，導(dǎo)致解密速度整體變慢。針對(duì)訪存速度過(guò)慢，本文作了以下優(yōu)化：

1)在進(jìn)行從核的程序運(yùn)算時(shí)，本文將從核計(jì)算使用的數(shù)據(jù)存儲(chǔ)在從核LDM中。這些數(shù)據(jù)頻繁被從核調(diào)用，相比從核直接訪問(wèn)主存，從核訪問(wèn)LDM速度更快，所用時(shí)間更短。數(shù)據(jù)放到LDM中，則從核運(yùn)算時(shí)可以直接從LDM中取數(shù)據(jù)，而不用直接訪問(wèn)主存。MD5解密運(yùn)算數(shù)據(jù)需要的內(nèi)存空間較小，雖然從核的局存僅有64 kB，但基本滿足MD5的解密運(yùn)算需要。

2)計(jì)算任務(wù)放到從核上，每次從核運(yùn)行時(shí)會(huì)從主核獲取計(jì)算任務(wù)和目標(biāo)數(shù)組，之后循環(huán)生成攻擊密碼進(jìn)行MD5加密運(yùn)算，判斷是否破解成功。從核在破解成功之后將破解結(jié)果傳輸回主核。主從核之間的數(shù)據(jù)傳輸采用DMA傳輸方式，通過(guò)該傳輸方式可以加快從核訪問(wèn)主存的速度[24]。

4 實(shí)驗(yàn)結(jié)果與性能分析

4.1 實(shí)驗(yàn)平臺(tái)

本文的實(shí)驗(yàn)是在申威26010眾核處理器的一個(gè)核組上進(jìn)行，處理器具體參數(shù)如表1所示。

表1 申威26010眾核處理器基本參數(shù)

4.2 MD5解密算法優(yōu)化實(shí)驗(yàn)

本文在單主核上對(duì)MD5解密算法進(jìn)行了優(yōu)化，為了驗(yàn)證優(yōu)化效果，對(duì)MD5解密算法優(yōu)化前后進(jìn)行了不同密碼量破解的實(shí)驗(yàn)。

結(jié)果如圖4所示，每添加一個(gè)新的優(yōu)化方法都會(huì)縮短解密時(shí)間，加快破解速度，表明本文提出的優(yōu)化方法是有效的。圖5的加速比是根據(jù)圖4中5組實(shí)驗(yàn)結(jié)果進(jìn)行的平均取值。原算法進(jìn)行散列初始化之后，加速比達(dá)到了7.09倍，在散列初始化的基礎(chǔ)上加入循環(huán)展開(kāi)，加速比結(jié)果是8.90倍，加入鏈接變量?jī)?yōu)化后加速比是8.93倍，加入61步優(yōu)化后是9.17倍，最后添加申請(qǐng)空間變量?jī)?yōu)化后加速比達(dá)到了12.28倍。

圖4 加入不同優(yōu)化方法對(duì)解密時(shí)間的影響

圖5 加入不同優(yōu)化方法后的加速比

4.3 申威26010眾核處理器的多線程實(shí)驗(yàn)

將計(jì)算任務(wù)放到從核上運(yùn)行之后進(jìn)行了訪存優(yōu)化前后的測(cè)試，結(jié)果如圖6所示，為了更好的可觀性，實(shí)驗(yàn)數(shù)據(jù)均保留2位小數(shù)。

圖6 訪存優(yōu)化前后核組與主核運(yùn)行速度對(duì)比

由圖6可知，在將解密任務(wù)放到從核上之后，未進(jìn)行訪存優(yōu)化，程序運(yùn)行時(shí)會(huì)頻繁地訪問(wèn)主存，實(shí)際的運(yùn)行速度不及單主核，速度僅僅是單主核的30%左右。在將從核運(yùn)行的參數(shù)放到從核局存后，運(yùn)行速度明顯變快，充分發(fā)揮64個(gè)從核的計(jì)算優(yōu)勢(shì)，并且主從核傳輸也采用DMA方式，可以極大地發(fā)揮從核的強(qiáng)大算力，解密時(shí)間明顯縮短，優(yōu)化效果明顯。通過(guò)5組不同密碼量的時(shí)間對(duì)比，對(duì)比優(yōu)化后的單主核，核組的平均加速比為44.84倍。

5 結(jié)束語(yǔ)

本文首先對(duì)純C版本的MD5解密算法進(jìn)行了優(yōu)化，通過(guò)散列預(yù)處理使經(jīng)過(guò)MD5算法運(yùn)算得到的結(jié)果可以直接進(jìn)行匹配，省去了復(fù)雜的字符串拼接過(guò)程，優(yōu)化了解密流程；通過(guò)循環(huán)展開(kāi)減少了分支判斷語(yǔ)句以及數(shù)組取值操作指令，使程序運(yùn)行速度更快；進(jìn)行鏈接變量?jī)?yōu)化和61步優(yōu)化縮短了解密步驟，使解密速度進(jìn)一步變快，最后申請(qǐng)內(nèi)存優(yōu)化，優(yōu)化了算法性能。經(jīng)過(guò)上述的優(yōu)化方法，與原算法相比，平均加速比達(dá)到了12.28倍。本文結(jié)合申威26010眾核處理器的主從結(jié)構(gòu)，將解密算法中的計(jì)算任務(wù)放在64個(gè)從核上并行執(zhí)行，并在核組內(nèi)進(jìn)行了訪存優(yōu)化，將從核運(yùn)算需要的數(shù)據(jù)存放在從核局存中，減少了從核直接訪問(wèn)主存的次數(shù)，使破解速度更快。通過(guò)實(shí)驗(yàn)發(fā)現(xiàn)，相比單主核，核組的平均加速比達(dá)到了44.84倍。

在單核組上的實(shí)驗(yàn)表明，將計(jì)算任務(wù)放到64個(gè)從核上有很好的優(yōu)化效果，而申威26010眾核處理器有4個(gè)核組，為了充分使用該眾核處理器，下一步工作將進(jìn)行擴(kuò)展性實(shí)驗(yàn)，調(diào)用更多核組進(jìn)行解密任務(wù)。