基于多核FPGA的HMAC-SHA1口令恢復(fù)

馮 峰，周清雷，李 斌

(鄭州大學(xué)信息工程學(xué)院，河南 鄭州 450001)

1 引言

消息認(rèn)證碼MAC(Message Authentication Code)是一種使用密鑰對(duì)通信消息進(jìn)行認(rèn)證的機(jī)制，在開放的、通用的網(wǎng)絡(luò)上常利用該機(jī)制來保證通信消息的機(jī)密性、完整性和有效性?；贖ash算法(如MD5、SHA系列、SM3等)的消息認(rèn)證碼是目前廣泛使用的消息認(rèn)證碼，即HMAC(keyed-Hash Message Authentication Code)，它是美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)研究院NIST(National Institute of Standards and Technology)指定的標(biāo)準(zhǔn)[1,2],且被要求在IPsec協(xié)議族和其他如SSL的Internet協(xié)議中實(shí)現(xiàn)?？梢杂肏MAC認(rèn)證的消息種類有很多，本文中HMAC-SHA1(Hash-based Message Authentication Code-secure Hash Algorithm 1)針對(duì)的應(yīng)用場(chǎng)景是基于SHA1算法對(duì)用戶密碼進(jìn)行認(rèn)證，以確認(rèn)密碼的正確性。正因?yàn)镠MAC具有較高的安全性，所以也經(jīng)常被不法分子所利用，以傳播危害公共安全的數(shù)據(jù)信息，這給信息安全監(jiān)管和計(jì)算機(jī)取證工作帶來了很大困難。因此，HMAC口令認(rèn)證碼的快速口令恢復(fù)對(duì)信息安全具有很重要的意義。

對(duì)于口令的恢復(fù)，僅依靠暴力窮舉是不可行的。有研究表明，用戶密碼服從Zipf分布[3]，這樣就可以利用“口令猜測(cè)算法”和“口令猜測(cè)模型”并結(jié)合社會(huì)工程學(xué)等方法[4 - 6]獲得對(duì)某一用戶有針對(duì)性的信息，從而分析出對(duì)應(yīng)高概率口令的特征并生成字典，最后采用字典+窮舉結(jié)合的方法猜出口令。但是，隨著口令長(zhǎng)度的增加，口令的驗(yàn)證速度依然是最亟待解決的問題。口令恢復(fù)加速的研究與具體算法具有強(qiáng)依賴性。因此，從計(jì)算平臺(tái)的角度來看，目前口令恢復(fù)加速的研究現(xiàn)狀主要是基于CPU的通用平臺(tái)以及基于OpenCL和CUDA架構(gòu)的GPU平臺(tái)。前者破解效率較低，后者有功耗高且因受到訪存限制而影響性能提升的問題。現(xiàn)場(chǎng)可編程門陣列FPGA(Field Programmable Gate Array)目前已廣泛應(yīng)用在各個(gè)領(lǐng)域[7 - 9]，利用FPGA硬件并行的優(yōu)勢(shì)并采用邏輯上的流水線工作模式，可使每個(gè)時(shí)鐘周期能夠完成更多的處理任務(wù)且具有相當(dāng)?shù)偷哪芎腫10,11]，再構(gòu)建多核FPGA硬件平臺(tái)則可完成多流水線的并行計(jì)算。因此，基于FPGA硬件平臺(tái)的口令恢復(fù)更具有優(yōu)勢(shì)。

本文實(shí)現(xiàn)了基于多核FPGA的高速HMAC-SHA1口令恢復(fù)，通過深入分析HMAC-SHA1算法，使用可重構(gòu)硬件FPGA和流水線技術(shù)，以展開結(jié)構(gòu)和引入保留進(jìn)位加法器CSA(Carry Save Adder)優(yōu)化SHA1算核，同時(shí)實(shí)現(xiàn)了全流水線和狀態(tài)機(jī)模式的HMAC-SHA1算子，最后設(shè)計(jì)并實(shí)現(xiàn)了字典+窮舉模式的口令恢復(fù)架構(gòu)。

2 算法分析

2.1 SHA1

SHA是著名的密碼散列算法家族，這些算法具有單向性、抗沖突性等特性，SHA1是其中之一。SHA1能對(duì)輸入的消息產(chǎn)生160 bit固定長(zhǎng)度的消息摘要。SHA1的內(nèi)容如下所示：

(1)消息填充與分塊。

在輸入消息的后面加1位1，再向后用0填充，直到總位長(zhǎng)對(duì)512取模時(shí)的結(jié)果為448，最后繼續(xù)填充64位，用于保存初始輸入消息的長(zhǎng)度。填充后的消息位長(zhǎng)為512的整數(shù)倍，按每512位進(jìn)行分塊。

(2)單個(gè)消息塊的計(jì)算過程。

各個(gè)消息塊按分塊順序執(zhí)行本過程。本過程總共4輪，每輪20步。設(shè)t為本過程的步數(shù)，則0≤t≤79。本過程的計(jì)算如式(1)所示：

(1)

其中,參量Hi,i=0,1,…,4在消息塊為首塊時(shí)是固定的5個(gè)常數(shù)，為非首塊時(shí)是前一個(gè)消息塊的計(jì)算結(jié)果；參量Kt和ft()分別是輪常數(shù)和輪函數(shù)，它們?cè)?輪上均不相同；參量Wt是明文分組，設(shè)消息塊(512 bit)按每32 bit進(jìn)行分割后的順序表示為{M0,M1,…,M15}，則它的取值如式(2)所示：

(2)

最后在本過程結(jié)束時(shí)，將求得的Hi與它們?cè)诒具^程剛開始時(shí)的初始值分別相加作為結(jié)果輸出。

2.2 HMAC-SHA1口令處理算法

HMAC-SHA1口令處理算法的過程如下所示：

設(shè)pwd為密鑰,salt為鹽值。若pwd的長(zhǎng)度大于512 bit則用SHA1處理pwd并將結(jié)果作為新的pwd；salt的長(zhǎng)度小于448 bit。

(1)對(duì)pwd補(bǔ)0至512位，然后與一個(gè)512位且每8位重復(fù)出現(xiàn)十六進(jìn)制36的值進(jìn)行異或得到消息塊Message，此Message和SHA1初始H輸入SHA1進(jìn)行運(yùn)算，結(jié)果H記為IPAD。

(2)對(duì)pwd補(bǔ)0至512位，然后與一個(gè)512位且每8位重復(fù)出現(xiàn)十六進(jìn)制5c的值進(jìn)行異或得到消息塊Message，此Message和SHA1初始H輸入SHA1進(jìn)行運(yùn)算，結(jié)果H記為OPAD。

(3)對(duì)salt進(jìn)行SHA1規(guī)則的消息填充，其中長(zhǎng)度部分要算上產(chǎn)生IPAD時(shí)Message所占的64 B，即512 bit，填充后得到本次消息塊Message。此Message和IPAD輸入SHA1進(jìn)行運(yùn)算，結(jié)果H向下繼續(xù)傳遞。

(4)對(duì)上次的結(jié)果H進(jìn)行SHA1規(guī)則的消息填充，其中長(zhǎng)度部分要算上產(chǎn)生OPAD時(shí)Message所占的64 B，即512 bit，填充后得到本次消息塊Message。此Message和OPAD輸入SHA1進(jìn)行運(yùn)算，結(jié)果H為RESULT。

HMAC-SHA1口令處理算法的過程[1]如圖1所示。

Figure 1 Process of HMAC-SHA1 password processing algorithm圖1 HMAC-SHA1口令處理算法的過程

2.3 HMAC-SHA1口令恢復(fù)

由于Hash算法的單向性，HMAC-SHA1口令恢復(fù)的主要思路就是不斷嘗試HMAC-SHA1口令認(rèn)證，直到碰撞出目標(biāo)口令認(rèn)證碼所代表的正確密鑰。本文將目標(biāo)口令認(rèn)證碼稱為HashValue，HashValue和salt的組合稱為特征串。

HMAC-SHA1口令恢復(fù)的過程如下所示：

(1)根據(jù)給定的特征串解析出HashValue和salt。

(2)采用字典+窮舉結(jié)合的方法來生成試探密鑰。

(3)若試探密鑰已全部枚舉完則就此結(jié)束口令恢復(fù)，口令恢復(fù)失敗，否則繼續(xù)。

(4)以試探密鑰和salt進(jìn)行HMAC-SHA1口令處理，處理結(jié)果記為digest。

(5)若digest與HashValue一致,則digest對(duì)應(yīng)的試探密鑰即為正確密鑰，口令恢復(fù)成功，否則重新從(2)開始。

HMAC-SHA1口令恢復(fù)的過程如圖2所示。

Figure 2 Password recovery process of HMAC-SHA1圖2 HMAC-SHA1口令恢復(fù)的過程

至此，本文對(duì)HMAC-SHA1口令進(jìn)行恢復(fù)的相關(guān)算法已介紹完畢。由前述算法分析可知，對(duì)HMAC-SHA1口令進(jìn)行恢復(fù)的主要運(yùn)算量在于SHA1算核的運(yùn)算，在具體實(shí)現(xiàn)中，SHA1算核的運(yùn)算速度將成為整個(gè)HMAC-SHA1口令恢復(fù)速度的瓶頸。因?yàn)镾HA1算核需要經(jīng)歷80步運(yùn)算，每一步運(yùn)算中包含與、或、異或、移位等子運(yùn)算，站在FPGA硬件設(shè)計(jì)的角度，可以針對(duì)這些步驟、子運(yùn)算等結(jié)合時(shí)鐘周期因素產(chǎn)生許多設(shè)計(jì)思路，但是不同的思路將最終得到不同的SHA1計(jì)算速度。比如，SHA1的串行實(shí)現(xiàn)設(shè)計(jì)難度小，但是最終工作的時(shí)鐘頻率卻很低，這無(wú)疑成為了速度瓶頸。

為了后續(xù)描述方便，本文將“對(duì)單個(gè)消息塊進(jìn)行SHA1運(yùn)算”稱為“一次SHA1”。由于整個(gè)HMAC-SHA1口令處理過程中只包含4個(gè)消息塊，因此，每進(jìn)行一次HMAC-SHA1口令處理實(shí)際需要進(jìn)行4次SHA1。

3 HMAC-SHA1高速口令恢復(fù)實(shí)現(xiàn)與優(yōu)化

3.1 SHA1實(shí)現(xiàn)與優(yōu)化

(1)流水線。

對(duì)于FPGA的設(shè)計(jì)，用硬連線的方式實(shí)現(xiàn)復(fù)雜的運(yùn)算是不可取的。首先，復(fù)雜的硬連線會(huì)占用大量的資源。其次，復(fù)雜的硬連線會(huì)加大時(shí)鐘延遲進(jìn)而目標(biāo)邏輯不能工作在高頻時(shí)序，如果時(shí)鐘頻率降低，則吞吐量也會(huì)降低，對(duì)應(yīng)的運(yùn)算速度也隨之降低，強(qiáng)行設(shè)置較高的時(shí)鐘頻率將會(huì)導(dǎo)致布線失敗。最后，硬連線不可緩存數(shù)據(jù)，需要通過寄存器進(jìn)行緩存，且寄存器的讀寫需要占用一個(gè)時(shí)鐘周期。因此，需在此基礎(chǔ)上考慮SHA1的實(shí)現(xiàn)。

根據(jù)一次SHA1運(yùn)算的過程可知，一次SHA1運(yùn)算需要80步，每一步的輸入、輸出僅與相鄰的步具有依賴關(guān)系，因此可將SHA1算法通過流水線技術(shù)實(shí)現(xiàn)為并行模式，從而降低時(shí)間復(fù)雜度。在本文實(shí)現(xiàn)中，為了算法整體的銜接所加入的輸入緩存和輸出緩存各占用一個(gè)時(shí)鐘周期，因此，本文對(duì)一次SHA1的實(shí)現(xiàn)為82級(jí)流水線模式，本文后續(xù)將該實(shí)現(xiàn)稱為流水線SHA1算核。FPGA中的流水線是以空間、可編程邏輯資源來?yè)Q取運(yùn)算速度的技術(shù)，流水線SHA1算核在滿負(fù)荷工作時(shí)，每一個(gè)時(shí)鐘周期都可得出一次SHA1運(yùn)算的結(jié)果。

由前述算法分析可知，一次SHA1運(yùn)算中的Wt參量在80步中各不相同且需要由之前已有的Wt計(jì)算得出。因此，Wt的計(jì)算和流水線傳遞是流水線SHA1算核的一個(gè)較大部分，以下是對(duì)Wt在具體實(shí)現(xiàn)中的邏輯描述，包括了緩存、計(jì)算和傳遞3個(gè)方面：

①緩存。

Wt的緩存需要依靠比較多的寄存器。在流水線SHA1中，不僅要求能夠提供每一步運(yùn)算所需的Wt，還要保證新的Wt能夠同時(shí)被算出，而需要計(jì)算得到的Wt總共是64個(gè)，實(shí)際上在流水線SHA1中，輸入緩存時(shí)鐘時(shí)就可以開始Wt的計(jì)算了。因此，流水線SHA1的前63步在提供當(dāng)前步驟Wt的同時(shí)還在計(jì)算后續(xù)的Wt，至于最后17步則只用輸出已經(jīng)算好的Wt即可。這樣來看，首先需要一個(gè)長(zhǎng)度為64的寄存器數(shù)組來保存通過計(jì)算得到的Wt值；然后需要80個(gè)寄存器數(shù)組分別對(duì)應(yīng)SHA1的80步，其中，前64個(gè)寄存器數(shù)組的長(zhǎng)度均是16，后16個(gè)寄存器數(shù)組的長(zhǎng)度從16開始依次遞減。

②計(jì)算。

流水線SHA1對(duì)Wt計(jì)算最大的優(yōu)勢(shì)是高度的并行性。在某一時(shí)鐘周期內(nèi)，前述緩存方式能夠同時(shí)對(duì)應(yīng)82個(gè)獨(dú)立的SHA1運(yùn)算，邏輯上的每一步都有對(duì)應(yīng)的寄存器數(shù)組配合完成Wt的計(jì)算。例如流水線SHA1的第63步中，進(jìn)行第80個(gè)Wt的計(jì)算，這將通過存儲(chǔ)了該Wt所需前16個(gè)值的寄存器數(shù)組來輔助完成，其余步驟下均是如此。

③傳遞。

流水線SHA1對(duì)Wt的傳遞是為了在每一步中順利輸出該步驟所需的Wt值。具體做法是80個(gè)對(duì)應(yīng)每一步的寄存器數(shù)組之間進(jìn)行錯(cuò)位賦值，即舍棄數(shù)組中首個(gè)寄存器內(nèi)的值，并將后續(xù)寄存器內(nèi)的值依次傳遞到下個(gè)數(shù)組編號(hào)減1的寄存器中去，最后把新計(jì)算得到的Wt值追加到下個(gè)數(shù)組的最后一個(gè)寄存器。這些在寄存器數(shù)組間的賦值同樣是完全并行的。

Wt計(jì)算和傳遞的邏輯如圖3所示。

Figure 3 Logical sketch of calculation and transfer of Wt圖3 Wt計(jì)算和傳遞的邏輯示意

在流水線SHA1算核中，對(duì)Wt的維護(hù)是隊(duì)列式緩存邏輯。從邏輯上看，在隊(duì)首元素參與運(yùn)算的同時(shí)計(jì)算隊(duì)尾元素，在隊(duì)首元素出隊(duì)的同時(shí)將新的隊(duì)尾元素入隊(duì)。流水線模式使得上述邏輯按流水線級(jí)數(shù)并行，在一個(gè)時(shí)鐘周期內(nèi)每一級(jí)處理都對(duì)應(yīng)著互不相關(guān)的SHA1運(yùn)算，并隨著時(shí)鐘周期以流水線的方式將這種對(duì)應(yīng)關(guān)系通過寄存器數(shù)組向下傳遞。

(2)展開結(jié)構(gòu)。

通過分析SHA1算法可知，SHA1的每一步運(yùn)算中，對(duì)第1個(gè)緩存H0的計(jì)算最為復(fù)雜。對(duì)于FPGA硬件來說，無(wú)緩存式運(yùn)算參與的器件參數(shù)越多，則布線的空間距離越大，即運(yùn)算的關(guān)鍵路徑越長(zhǎng)，這會(huì)使得延遲增大進(jìn)而拉低最大工作頻率。因此，可通過展開結(jié)構(gòu)的方式做進(jìn)一步優(yōu)化。

基于前述流水線的實(shí)現(xiàn)方式，本文對(duì)緩存H0的計(jì)算進(jìn)行拆分，以優(yōu)化上述問題。因?yàn)檩斎刖彺娴拇嬖谑筍HA1運(yùn)算推后了一個(gè)時(shí)鐘周期，所以計(jì)算緩存H0所需的E+Wt+Kt部分可預(yù)先計(jì)算完成。因此，對(duì)緩存H0的計(jì)算被分成2個(gè)時(shí)鐘周期來完成，第1個(gè)時(shí)鐘周期進(jìn)行預(yù)計(jì)算，這樣做使得單次參與緩存H0計(jì)算的參數(shù)個(gè)數(shù)減少了。對(duì)計(jì)算緩存H0的結(jié)構(gòu)展開前后對(duì)比，如圖4所示，圖4a為展開前，圖4b為展開后。

Figure 4 Comparison of calculation structure of H0 before and after expansion 圖4 對(duì)計(jì)算緩存H0的結(jié)構(gòu)展開前后對(duì)比

(3)使用保留進(jìn)位加法器。

在對(duì)計(jì)算緩存H0進(jìn)行實(shí)現(xiàn)時(shí)，本文對(duì)其中的加法運(yùn)算進(jìn)行了優(yōu)化。FPGA編程面向的是底層硬件，因此FPGA適合進(jìn)行位運(yùn)算，加法運(yùn)算的延遲要比位運(yùn)算高。保留進(jìn)位加法器CSA能夠通過增加位運(yùn)算來減少加法運(yùn)算，從而降低計(jì)算延遲，保證流水線的吞吐率[12]。CSA運(yùn)算如下所示：

其中，S(a,b,c)為和輸出，Ca(a,b,c)為進(jìn)位輸出，并且a、b、c的二進(jìn)制位數(shù)一致。

3.2 HMAC-SHA1口令處理實(shí)現(xiàn)

前文已指出HMAC-SHA1口令處理需要進(jìn)行4次SHA1。為了描述方便，本文對(duì)這4次SHA1進(jìn)行命名，并根據(jù)前文算法描述的邏輯過程排列命名的順序：

其中，ipad_sha1+salt_sha1實(shí)際是SHA1對(duì)第1次消息輸入進(jìn)行處理，opad_sha1+hmac_sha1實(shí)際是SHA1對(duì)第2次消息輸入進(jìn)行處理。通過分析可知：

ipad_sha1與opad_sha1沒有運(yùn)算上的依賴順序，兩者可同時(shí)進(jìn)行運(yùn)算；salt_sha1與opad_sha1沒有運(yùn)算上的依賴順序，兩者可同時(shí)進(jìn)行運(yùn)算；其他任何組合都具有運(yùn)算上的依賴順序，運(yùn)算順序與上述命名順序相同。

HMAC-SHA1口令處理需要進(jìn)行的SHA1次數(shù)在邏輯上是固定的，但用FPGA進(jìn)行具體實(shí)現(xiàn)時(shí)，前述流水線SHA1算核的物理個(gè)數(shù)是可以進(jìn)行設(shè)計(jì)的。本文后續(xù)把對(duì)HMAC-SHA1口令處理的實(shí)現(xiàn)稱為HMAC-SHA1口令處理算子。

對(duì)于HMAC-SHA1口令處理本文進(jìn)行了以下2種實(shí)現(xiàn)：

(1)HMAC-SHA1口令處理全流水線算子。

本算子將流水線SHA1算核實(shí)例化了4份，即物理空間上存在4份算核電路。在工作邏輯上，本算子采用ipad_sha1與opad_sha1并行工作且兩者與salt_sha1、hmac_sha1按命名順序串行工作的工作邏輯。在算子滿負(fù)荷運(yùn)行時(shí)，該工作邏輯在擁有4份算核電路的算子中以全流水線的方式推進(jìn)。算子實(shí)現(xiàn)時(shí)，opad_sha1產(chǎn)生的階段結(jié)果經(jīng)由FIFO進(jìn)行了82級(jí)緩存，為的是在邏輯上延遲至hmac_sha1開始。該FIFO通過一個(gè)雙端口Block RAM實(shí)現(xiàn)的IP核來配置。本算子的工作邏輯如圖5所示。

Figure 5 Full pipeline operator working logic of HMAC-SHA1 password processing 圖5 HMAC-SHA1口令處理全流水線算子工作邏輯

本算子的資源占用主要是4份流水線SHA1算核電路，滿負(fù)荷工作時(shí)，每82×4個(gè)時(shí)鐘周期可產(chǎn)生82×4個(gè)口令處理結(jié)果。

(2)HMAC-SHA1口令處理狀態(tài)機(jī)算子。

本算子將流水線SHA1算核實(shí)例化了一份，即物理空間上存在一份算核電路。在工作邏輯上，本算子采用ipad_sha1、opad_sha1、salt_sha1、hmac_sha1按命名順序串行工作的工作邏輯。在算子滿負(fù)荷運(yùn)行時(shí)，該工作邏輯在擁有一份算核電路的算子當(dāng)中以狀態(tài)機(jī)流水線的方式推進(jìn)，狀態(tài)機(jī)決定算核當(dāng)前狀態(tài)是在進(jìn)行哪一次SHA1運(yùn)算且算核以流水線模式工作。算子實(shí)現(xiàn)當(dāng)中，共需要2個(gè)FIFO來進(jìn)行緩存，opad_sha1所需的512 bit消息塊經(jīng)由第1個(gè)FIFO進(jìn)行了82級(jí)緩存，為的是在邏輯上延遲至opad_sha1開始，ipad_sha1和opad_sha1產(chǎn)生的階段結(jié)果經(jīng)由第2個(gè)FIFO進(jìn)行了82級(jí)緩存，為的是在邏輯上延遲至salt_sha1和hmac_sha1開始。以上2個(gè)FIFO均通過一個(gè)雙端口Block RAM實(shí)現(xiàn)的IP核來配置。本算子的工作邏輯如圖6所示。

Figure 6 State machine operator working logic of HMAC-SHA1 password processing 圖6 HMAC-SHA1口令處理狀態(tài)機(jī)算子工作邏輯

本算子的資源占用主要是一份流水線SHA1算核電路，滿負(fù)荷工作時(shí)，每82×4個(gè)時(shí)鐘周期可產(chǎn)生82個(gè)口令處理結(jié)果。

最后，對(duì)比2種實(shí)現(xiàn)方式。綜合了資源占用和運(yùn)算速度后，在同等工作頻率下，理論上兩者的總體性能相當(dāng)，但狀態(tài)機(jī)方式能夠更好地支持?jǐn)U展改進(jìn)，具有更大的實(shí)際應(yīng)用價(jià)值，而全流水線方式與算法本身具有強(qiáng)耦合性，不利于擴(kuò)展改進(jìn)。HMAC具有很多的應(yīng)用場(chǎng)景或迭代使用，比如“PBKDF2-HMAC”對(duì)HMAC迭代了1 000次，此時(shí)全流水線的實(shí)現(xiàn)方式將不再適用。

3.3 口令恢復(fù)架構(gòu)與實(shí)現(xiàn)

前述工作中，本文實(shí)現(xiàn)了能夠高速進(jìn)行HMAC-SHA1口令處理的算子，這是進(jìn)行HMAC-SHA1口令恢復(fù)的核心工作模塊。圍繞它實(shí)現(xiàn)HMAC-SHA1口令恢復(fù)，本文設(shè)計(jì)了如圖7所示的架構(gòu)，本文將該架構(gòu)以外的部分稱為“外部”。

Figure 7 Password recovery architecture圖7 口令恢復(fù)架構(gòu)

從圖7中可以看出，頂層模塊封裝了整個(gè)架構(gòu)，口令恢復(fù)任務(wù)所需的相關(guān)數(shù)據(jù)從外部緩存到接口模塊中的FIFO，然后在內(nèi)部時(shí)鐘頻率下被讀取到解析模塊進(jìn)行解析處理，解析后的口令恢復(fù)任務(wù)被分配到對(duì)應(yīng)的口令恢復(fù)模塊進(jìn)行計(jì)算，所有的計(jì)算結(jié)果都將匯總到選擇模塊進(jìn)行處理，若口令恢復(fù)成功，則相關(guān)信息再經(jīng)過接口模塊輸出到外部。其中，口令恢復(fù)模塊接到任務(wù)后通過口令生成模塊來產(chǎn)生口令，口令經(jīng)過口令處理模塊計(jì)算后，結(jié)果交給匹配模塊來進(jìn)行檢查。以下是對(duì)各個(gè)模塊的介紹，其中所用到的FIFO均通過一個(gè)雙端口Block RAM實(shí)現(xiàn)的IP核來配置。

(1)TOP頂層模塊。作用是實(shí)例化INTERFACE、ANALYSIS、OPERATOR和SELECT模塊，并依照各模塊的功能正確連通它們的接口。

(2)INTERFACE接口模塊。作用是承擔(dān)與外部的交互工作，外部通過頂層TOP模塊連入INTERFACE模塊。外部與TOP模塊內(nèi)部處在不同的時(shí)鐘域，因?yàn)門OP模塊內(nèi)部需要完成計(jì)算任務(wù)，所以TOP模塊內(nèi)部時(shí)鐘頻率要比外部時(shí)鐘頻率高很多。因此，INTERFACE模塊需要通過FIFO來緩存外部傳入的口令恢復(fù)配置信息，以此來隔離時(shí)鐘域。

(3)ANALYSIS解析模塊。作用是解析口令恢復(fù)配置信息并下發(fā)口令恢復(fù)任務(wù)，這些信息包括算例編號(hào)、字典規(guī)則、特征串等。

(4)OPERATOR口令恢復(fù)模塊。本文將該模塊的實(shí)例稱為口令恢復(fù)算例。該模塊包含ENUM、HMAC-SHA1和MATCH子模塊，作用是依照各子模塊的功能正確連通它們的接口。各子模塊具體如下所示：

①ENUM口令生成模塊。作用是根據(jù)本算例的口令恢復(fù)任務(wù)依照字典規(guī)則生成口令。因?yàn)榭诹钐幚硇枰?jīng)過復(fù)雜的計(jì)算過程，所以被處理的口令還需要通過FIFO進(jìn)行緩存，以便與口令處理結(jié)果同步對(duì)應(yīng)。

此處對(duì)本文中的可窮舉字典規(guī)則進(jìn)行簡(jiǎn)要說明。對(duì)于一條口令字典規(guī)則，它能表示的最大口令長(zhǎng)度為32 bit可打印字符位置，一個(gè)口令字符位置可以是明文也可以是掩碼，掩碼有4種，分別是數(shù)字、小寫字母、大寫字母、標(biāo)點(diǎn)符號(hào)。例如“#1#2#3?d?l?u?s”表示一個(gè)7位密碼，其中，#1、#2、#3表示1、2、3這3個(gè)明文字符，?d表示數(shù)字0～9的掩碼，?l表示小寫字母a～z的掩碼，?u表示大寫字母A～Z的掩碼，?s表示標(biāo)點(diǎn)符號(hào)掩碼。

②HMAC-SHA1口令處理模塊。該模塊就是前文實(shí)現(xiàn)的HMAC-SHA1口令處理算子。

③MATCH匹配模塊。作用是檢查口令恢復(fù)是否成功。

(5)SELECT選擇模塊。作用是選擇口令恢復(fù)成功的算例，并將其口令恢復(fù)結(jié)果發(fā)送給INTERFACE模塊。

在以上架構(gòu)的實(shí)現(xiàn)中，根據(jù)板卡上FPGA芯片的資源量和所選內(nèi)部時(shí)鐘頻率，應(yīng)盡可能多地實(shí)例化口令恢復(fù)算例并完成綜合以及布線，這樣能最大化單塊FPGA芯片的口令恢復(fù)速度。

3.4 多核FPGA口令恢復(fù)設(shè)計(jì)與管理

本文中所謂多核FPGA就是一塊PCIe外設(shè)板卡上同時(shí)搭載多個(gè)獨(dú)立的FPGA芯片，該板卡的具體構(gòu)成以及FPGA芯片型號(hào)將在后續(xù)實(shí)驗(yàn)部分進(jìn)行闡述。

對(duì)于基于多核FPGA的口令恢復(fù)，本文構(gòu)建了對(duì)應(yīng)的口令恢復(fù)系統(tǒng)并采用樹狀結(jié)構(gòu)設(shè)計(jì)其管理方式。在整套系統(tǒng)中，F(xiàn)PGA板卡的宿主機(jī)將擔(dān)任口令恢復(fù)任務(wù)分配管理的重要角色。具體做法是，用戶機(jī)統(tǒng)一管理所有計(jì)算節(jié)點(diǎn)，一臺(tái)宿主機(jī)及其上所包含的若干前述板卡整體被定義為一個(gè)計(jì)算節(jié)點(diǎn)；單個(gè)計(jì)算節(jié)點(diǎn)上的宿主機(jī)管理其上所有可利用算例，這其中的關(guān)系是，宿主機(jī)包含若干板卡，一塊板卡搭載多個(gè)FPGA核，一個(gè)FPGA上實(shí)例化了多個(gè)算例。綜上，整個(gè)口令恢復(fù)任務(wù)通過分配可窮舉字典規(guī)則的方式進(jìn)行逐級(jí)下放，使得最終所有算例根據(jù)所分得的字典規(guī)則能夠并行完成各自的任務(wù)，整個(gè)系統(tǒng)具有極高的效率。該結(jié)構(gòu)如圖8所示。

Figure 8 Structure of password recovery system based on multi-core FPGA圖8 基于多核FPGA的口令恢復(fù)系統(tǒng)結(jié)構(gòu)示意

從圖8中可以看出，該結(jié)構(gòu)能夠通過增加計(jì)算節(jié)點(diǎn)的數(shù)量來動(dòng)態(tài)擴(kuò)展整個(gè)口令恢復(fù)任務(wù)的算力配置，具有很高的靈活性。

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

本文實(shí)驗(yàn)涉及的硬件平臺(tái)如下所示：

(1)FPGA加速卡。該加速卡集成了4個(gè)FPGA芯片，每個(gè)芯片的型號(hào)均為XILINX公司的XCKU060，板卡通過PCIe接口與上位機(jī)通信和上電。圖9所示為該加速卡的簡(jiǎn)要構(gòu)成。

Figure 9 Brief composition of FPGA acceleration card圖9 FPGA加速卡簡(jiǎn)要構(gòu)成示意

(2)對(duì)比平臺(tái)。CPU，Intel Core i5-8500 @ 3.00 GHz 6核；GPU，NVIDIA GeForce GTX 1080 (8 GB/EVGA)。

輔助軟件有：

(1)Vivado。針對(duì)XILINX的FPGA芯片進(jìn)行開發(fā)需要用到Vivado，它是XILINX公司提供給開發(fā)者的集成開發(fā)環(huán)境，能夠在FPGA開發(fā)的整個(gè)生命周期內(nèi)提供支持。Vivado不僅功能強(qiáng)大，還能根據(jù)所配置的相關(guān)策略自動(dòng)對(duì)開發(fā)者的FPGA工程進(jìn)行底層優(yōu)化。

(2)hashcat。hashcat是一款開源的口令破解軟件，其中包括眾多被優(yōu)化后的口令恢復(fù)算法，且這些口令恢復(fù)算法是通過OpenCL實(shí)現(xiàn)的，所以hashcat能夠同時(shí)在CPU和GPU上進(jìn)行口令恢復(fù)。hashcat因?yàn)槠鋸?qiáng)大的口令恢復(fù)功能和跨平臺(tái)支持而得到了廣泛使用。因此，本文實(shí)驗(yàn)通過hashcat軟件來獲取在CPU和GPU平臺(tái)上HMAC-SHA1口令恢復(fù)的速度。

本文實(shí)驗(yàn)進(jìn)行的第1項(xiàng)對(duì)比是對(duì)SHA1算核實(shí)現(xiàn)與優(yōu)化的各個(gè)階段的資源占用與最大工作頻率的對(duì)比，結(jié)果如表1所示。其中，階段1是僅采用流水線；階段2是采用流水線并展開結(jié)構(gòu)；階段3是采用流水線并展開結(jié)構(gòu)，同時(shí)引入保留進(jìn)位加法器，即最終實(shí)現(xiàn)。

Table 1 Resource occupancy and maximum frequency in different stages表1 不同階段的資源占用和最大頻率

從表1中可以看出，在階段3中本文實(shí)現(xiàn)的SHA1算核最高工作頻率達(dá)到了最大，而3個(gè)階段所占用的資源卻相差不大。

本文實(shí)驗(yàn)進(jìn)行的第2項(xiàng)對(duì)比是本文實(shí)現(xiàn)且優(yōu)化后的流水線SHA1算核與其他文獻(xiàn)中SHA1性能的對(duì)比，結(jié)果如表2所示。

Table 2 Comparison of SHA1 implementation performance in different references表2 不同文獻(xiàn)SHA1實(shí)現(xiàn)性能對(duì)比

通過對(duì)比可知，本文實(shí)現(xiàn)且優(yōu)化后的流水線架構(gòu)SHA1算核在頻率上達(dá)到了480 MHz，吞吐量達(dá)到了245.76 Gbps。在吞吐量上，本文的實(shí)現(xiàn)是文獻(xiàn)[17]的33倍，比除本文外最高的文獻(xiàn)[10]的高出90 Gbps，性能提升顯著。在此需要說明，流水線SHA1算核僅是HMAC-SHA1口令恢復(fù)工程中的核心運(yùn)算單元，整個(gè)工程還包括前文所述的許多模塊，并且最終需要滿載算例。對(duì)于FPGA工程來說，工程越復(fù)雜則越難提高工作頻率，因此，最終HMAC-SHA1口令恢復(fù)工程中的內(nèi)部時(shí)鐘工作頻率為200 MHz。

本文實(shí)驗(yàn)進(jìn)行的第3項(xiàng)對(duì)比是HMAC-SHA1口令處理全流水線算子和狀態(tài)機(jī)算子在吞吐量和資源占用量上的對(duì)比，結(jié)果如表3所示。

Table 3 Comparison between full pipeline operator and state machine operator表3 全流水線算子和狀態(tài)機(jī)算子對(duì)比

根據(jù)表3可知，單個(gè)HMAC-SHA1口令處理全流水線算子的吞吐量和資源占用量均是狀態(tài)機(jī)算子的4倍左右。因此，每4個(gè)HMAC-SHA1口令處理狀態(tài)機(jī)算子與單個(gè)全流水線算子在吞吐量和資源占用量上相當(dāng)。需要說明的是，當(dāng)LUT等資源的使用超出85%后，本文實(shí)驗(yàn)所用的XCKU060芯片在200 MHz的時(shí)序約束下將無(wú)法通過布線。因此，根據(jù)實(shí)際測(cè)試，在本文實(shí)驗(yàn)中的單個(gè)FPGA芯片上最多能搭載4個(gè)全流水線算子或16個(gè)狀態(tài)機(jī)算子。在滿配全流水線算子后整套系統(tǒng)的資源利用率是LUT消耗194 866(58.75%)、FF消耗505 770(76.24%)；在滿配狀態(tài)機(jī)算子后整套系統(tǒng)的資源利用率是LUT消耗273 620(82.50%)、FF消耗555 630(83.76%)。

本文實(shí)驗(yàn)最后用基于滿載上述規(guī)模算子的4核FPGA加速卡與基于hashcat的CPU、GPU平臺(tái)對(duì)HMAC-SHA1口令恢復(fù)速度進(jìn)行了對(duì)比，結(jié)果如表4所示。

Table 4 Comparison of speed on different platforms表4 不同平臺(tái)上的速度對(duì)比

根據(jù)表4可知，本文對(duì)HMAC-SHA1口令恢復(fù)的速度達(dá)到了CPU平臺(tái)上的72倍，GPU平臺(tái)上的2.6倍。這只是單塊板卡的速度對(duì)比，而單臺(tái)上位機(jī)可配置多塊參與口令恢復(fù)的板卡，最后若再以集群形式進(jìn)行口令恢復(fù)，則口令恢復(fù)的速度也會(huì)成倍增長(zhǎng)。因此，基于FPGA進(jìn)行HMAC-SHA1口令恢復(fù)還具有橫向可擴(kuò)展的優(yōu)點(diǎn)。

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

本文實(shí)現(xiàn)了基于多核FPGA的高速HMAC-SHA1口令恢復(fù)。首先，對(duì)HMAC-SHA1口令處理的相關(guān)算法進(jìn)行了深入分析。其次，先后實(shí)現(xiàn)和優(yōu)化了SHA1算核，完成了基于全流水線和狀態(tài)機(jī)的HMAC-SHA1口令處理算子，設(shè)計(jì)并實(shí)現(xiàn)了HMAC-SHA1口令恢復(fù)架構(gòu)。最后，通過實(shí)驗(yàn)測(cè)試了本文SHA1算核的性能，測(cè)試結(jié)果表明，相比于其它文獻(xiàn)，本文SHA1算核的性能要高出很多，緊接著根據(jù)基于全流水線和狀態(tài)機(jī)的算子吞吐量、資源占用量進(jìn)行了單塊板卡滿配算子的速度測(cè)試，在與其他平臺(tái)進(jìn)行對(duì)比后得出，本文對(duì)HMAC-SHA1口令恢復(fù)的速度達(dá)到了CPU平臺(tái)上的72倍，GPU平臺(tái)上的2.6倍，充分利用了FPGA的硬件優(yōu)勢(shì)。