李 斌，周清雷，斯雪明，馮 峰

(1.鄭州大學(xué)信息工程學(xué)院，河南 鄭州 450001;2.數(shù)學(xué)工程與先進(jìn)計(jì)算國(guó)家重點(diǎn)實(shí)驗(yàn)室，河南 鄭州 450001)

1 引言

數(shù)據(jù)加密是信息安全的重要手段，密碼技術(shù)是網(wǎng)絡(luò)安全與保密的核心和關(guān)鍵。DES(Data Encryption Standard)作為最有代表性的分組加密算法，包括DES Crypt和3DES，對(duì)系統(tǒng)性能要求低，易于軟硬件加速實(shí)現(xiàn)，被應(yīng)用于各種保密通信之中[1,2]，如網(wǎng)絡(luò)協(xié)議、數(shù)據(jù)加密、智能卡加密、系統(tǒng)加密等。為有效恢復(fù)出以DES為核心加密的數(shù)據(jù)，提供電子取證，并測(cè)試DES的各種破譯攻擊，提供安全性研究，對(duì)DES算法的計(jì)算加速和恢復(fù)策略，顯得至關(guān)重要。在國(guó)外，對(duì)DES算法的恢復(fù)定制了專用的crack.sh平臺(tái)和設(shè)備(https:∥crack.sh;https:∥www.sciengines.com)，Hashcat(https:∥hashcat.net/hashcat)提供了各種DES密碼算法的恢復(fù)計(jì)算。在國(guó)內(nèi)，也出現(xiàn)了各種DES專用恢復(fù)設(shè)備，其以ASIC實(shí)現(xiàn)的方式(http:∥www.jn-ljjx.com)極大提高了DES的性能。其次，針對(duì)DES算法的高速并行攻擊，利用FPGA可靈活實(shí)現(xiàn)多種結(jié)構(gòu)，兼顧性能和功耗[3 - 5]，具有明顯優(yōu)勢(shì)。最后，為了提高安全性，DES經(jīng)常與RSA、Hash函數(shù)等聯(lián)合使用，包括含有鹽值Salt的DES Crypt和3DES算法，這也給為恢復(fù)加密數(shù)據(jù)帶來(lái)了一定困難。

顯然，對(duì)于DES的計(jì)算，CPU和GPU只能依靠多核心和頻率的提升來(lái)加速，且GPU功耗較高。而ASIC僅能支持單個(gè)DES應(yīng)用的恢復(fù)，缺失了一定靈活性。其次，DES算法應(yīng)用眾多，需要靈活的架構(gòu)和不同恢復(fù)策略支持，以提高恢復(fù)效率。最后，對(duì)于聯(lián)合使用多種密碼算法的DES加密機(jī)制，是否可繞過(guò)部分過(guò)程，直接對(duì)DES進(jìn)行破解，并據(jù)此恢復(fù)其他數(shù)據(jù)，也亟待研究。

擬態(tài)計(jì)算依托可重構(gòu)技術(shù)，通過(guò)剖析應(yīng)用的計(jì)算特征，依據(jù)盡可能高效的原則，構(gòu)建出合適的處理結(jié)構(gòu)，并隨著處理負(fù)荷的變化，主動(dòng)進(jìn)行結(jié)構(gòu)變更，以達(dá)到“應(yīng)用決定結(jié)構(gòu)，結(jié)構(gòu)決定效能”的目的。為進(jìn)一步提高DES的性能和可擴(kuò)展性，結(jié)合擬態(tài)計(jì)算的思想，本文提出了一種混合可重構(gòu)的DES算核高效能口令恢復(fù)方案。通過(guò)對(duì)DES算法的深入剖析，形成可重構(gòu)的算核[6]，并以全局異步局部同步GALS(Global Asynchronous Local Synchronous)架構(gòu)對(duì)算核進(jìn)行互連，建立混合結(jié)構(gòu)，提高了計(jì)算速度、能效比和靈活性。其次，優(yōu)化并設(shè)計(jì)了高速口令生成算法，以匹配DES的高速口令輸入需求，并針對(duì)不同應(yīng)用提出了各種恢復(fù)策略，提高了恢復(fù)效率。最后，通過(guò)實(shí)驗(yàn)對(duì)比了不同計(jì)算部件DES算法的性能，并驗(yàn)證了本文方案的有效性。

2 DES應(yīng)用及算法分析

2.1 DES應(yīng)用場(chǎng)景

(1)網(wǎng)絡(luò)協(xié)議。目前大多數(shù)網(wǎng)絡(luò)協(xié)議中仍以DES為核心加密算法，如LM、NTLM v1、Kerberos 5[7]、VPN、IPSec、FTD等協(xié)議。以VPN為例，目前仍有60%以上的VPN使用PPTP隧道協(xié)議[8]，以DES進(jìn)行通信加密傳輸。但是，國(guó)內(nèi)出現(xiàn)了大量的“翻墻”軟件，有自由門、極速安全VPN、蝙蝠VPN等。不法之徒利用這些網(wǎng)絡(luò)協(xié)議，通過(guò)私自架設(shè)服務(wù)器，在國(guó)內(nèi)傳播不良信息，并將重要數(shù)據(jù)備份在國(guó)外服務(wù)器上，給電子取證和犯罪審查造成了巨大的阻礙。

(2)數(shù)據(jù)恢復(fù)。對(duì)于DES分組加密算法，有ECB、CBC、CFB、OFB這4種常用加密模式。其中，由于ECB加密模式簡(jiǎn)單，且利用并行化處理，目前被廣泛使用。作為DES解密數(shù)據(jù)的突破口，ECB加密模式也是本文研究的重點(diǎn)。當(dāng)獲取到DES密文后，可以采用并行逆向計(jì)算的方式[9]，嘗試用各種不同的口令恢復(fù)同一數(shù)據(jù)段，并以解析到明文輸出為判斷條件，直到找到唯一正確的密鑰。顯然，這對(duì)DES加密數(shù)據(jù)的安全性及其變種改進(jìn)算法的抗攻擊性測(cè)試具有重要意義。

(3)系統(tǒng)恢復(fù)。DES算法在智能卡[10]、芯片[11]和操作系統(tǒng)[12]等領(lǐng)域仍被廣泛應(yīng)用著，以此來(lái)實(shí)現(xiàn)關(guān)鍵數(shù)據(jù)的保密，如IC卡與POS間的雙向認(rèn)證、金融交易系統(tǒng)和Linux/Unix系統(tǒng)登錄認(rèn)證。通過(guò)調(diào)試跟蹤工具，如OllyDBG、DDMS等，可以跟蹤軟件的內(nèi)存讀寫和程序執(zhí)行狀態(tài)，進(jìn)而獲取有用信息，為恢復(fù)加密數(shù)據(jù)提供支持。對(duì)于智能卡和芯片，目前則更多是依賴差分功耗分析DPA(Differential Power Analysis)[13]進(jìn)行破解。但是，DPA也需要輸入n次口令，并對(duì)每次產(chǎn)生的功耗進(jìn)行分析，所以DES的計(jì)算性能至關(guān)重要。

2.2 DES算法分析

DES算法是一種單密鑰分組密碼算法，以64 bit的密鑰對(duì)64 bit的數(shù)據(jù)分組進(jìn)行加密，輸出64 bit的密文。明文數(shù)據(jù)塊首先經(jīng)過(guò)初始置換IP，再使用16個(gè)擴(kuò)展后的子密鑰進(jìn)行16輪迭代編碼，最后經(jīng)過(guò)一個(gè)逆初始置換IP-1，輸出密文，可表述如下：DESm=IP(m)→Round(K0),Round(K1),…,Round(K15)→IP-1。DES解密過(guò)程與加密類似，只需要對(duì)迭代過(guò)程逆序使用子密鑰即可，第1輪使用K15，第2輪使用K14，依次類推，即有：DES-1m=IP(m)→Round(K15),Round(K14),…,Round(K0)→IP-1。DES加/解密流程如圖1所示。

Figure 1 DES encryption/decryption process圖1 DES加/解密流程

DES加密的核心是16輪迭代循環(huán)，64 bit明文在經(jīng)過(guò)初始置換后，被分為L(zhǎng)0和R0共2個(gè)32 bit的數(shù)據(jù)塊；然后R0與子密鑰K0進(jìn)行乘積變換，得到F(R0,K0)；再與L0異或得到L0⊕F(R0,K0)，隨后使用Ln=Rn-1,Rn=Ln-1⊕F(Rn-1,Kn-1)重復(fù)迭代過(guò)程。其中，F(xiàn)包括：擴(kuò)展函數(shù)E、按位異或、S盒運(yùn)算和置換函數(shù)P這4個(gè)功能模塊。對(duì)于密鑰擴(kuò)展，56 bit的密鑰被分成2個(gè)28 bit的半密鑰，每個(gè)半密鑰經(jīng)過(guò)循環(huán)左移處理，并通過(guò)選擇置換，產(chǎn)生48 bit的子密鑰。DES單輪加密流程如圖2所示。Rn-1先由擴(kuò)展函數(shù)E擴(kuò)展到48 bit，然后再與擴(kuò)展后的48 bit的子密鑰Kn-1按位異或，得到8組6 bit的數(shù)據(jù)。這8組數(shù)據(jù)再進(jìn)入6 bit輸入4 bit輸出的S盒S1,S2,…,S8，得到32 bit的數(shù)據(jù)。最后經(jīng)過(guò)置換函數(shù)P，得到32 bit的輸出。

Figure 2 Single round encryption process圖2 單輪加密流程

由以上分析可以看出，DES算法具有如下特點(diǎn)：(1)數(shù)據(jù)通路簡(jiǎn)單，都是位級(jí)的線性變換；(2)16輪核心迭代完全相同，且每輪迭代均為線性變換；(3)DES是分組密碼算法，參與運(yùn)算的數(shù)據(jù)塊前后沒(méi)有相關(guān)性[14]，因而可以將循環(huán)展開，形成流水線；(4)DES每輪參與運(yùn)算的子密鑰可以提前生成。

雖然基于FPGA對(duì)DES算法有了眾多優(yōu)化[15-17]，但其僅優(yōu)化了算法本身，并未對(duì)算法在各種應(yīng)用場(chǎng)景中的使用進(jìn)行分析。為進(jìn)一步提高DES算法的應(yīng)用靈活性和可擴(kuò)展性，本文結(jié)合擬態(tài)計(jì)算算核的設(shè)計(jì)思想，以有限規(guī)模的硬件解決DES算法多領(lǐng)域應(yīng)用，并采用全局異步局部同步GALS的架構(gòu)，實(shí)現(xiàn)芯片級(jí)的多維可重構(gòu)，進(jìn)而高效地實(shí)現(xiàn)DES各種應(yīng)用的口令恢復(fù)。

3 方案優(yōu)化與設(shè)計(jì)

3.1 算核模型

擬態(tài)計(jì)算以算核為基本功能單元，其規(guī)模受解算目標(biāo)的應(yīng)用驅(qū)動(dòng)，可按應(yīng)用所需重構(gòu)成不同數(shù)量、粒度和功能的算核，進(jìn)而可獲得更高的單元利用率，兼顧高效計(jì)算和靈活性。因此，算核是一種計(jì)算粒度可變的計(jì)算結(jié)構(gòu)，對(duì)于提高計(jì)算系統(tǒng)的效能和資源利用率具有重要意義。

算核的計(jì)算模型可表示為：CK=(VE,ED,PR,ME,CO,GR)，其中VE={ve1,ve2,…,ven}，表示算核的集合；ED={edij|edij=vei,vej,vei,vej∈VE,1≤i,j≤n}，稱為有向邊集，表示算核之間數(shù)據(jù)依賴先后關(guān)系及串并行關(guān)系；PR={pr1,pr2,…,prn}，代表算核的串行計(jì)算量；ME={me1,me2,…,men}，代表算核所需內(nèi)存容量或硬件寄存器資源；CO={co1,co2,…,con}，代表每條邊eij上的通信量；GR={gr1,gr2,…,grn}，表示計(jì)算粒度，粒度大小受輸入輸出數(shù)據(jù)和串、并行實(shí)現(xiàn)方式影響。

圖3所示為算核重構(gòu)的示意圖。其中I1～I(xiàn)5為輸入算核，A1～A4、D1～D4、F1～F4為中間算核，O1～O5為輸出算核。通過(guò)每條路徑上算核的重構(gòu)連接得到了一定的運(yùn)算功能。那么，針對(duì)DES口令恢復(fù)算法，以片內(nèi)邏輯塊、IP核、功能函數(shù)、算法等形成算核，利用FPGA細(xì)粒度可重構(gòu)器件，通過(guò)觸發(fā)器FF(Flip Flop)和查找表LUT(Look Up Table)等實(shí)現(xiàn)串并混合的計(jì)算結(jié)構(gòu)，可獲取更好的可擴(kuò)展性和執(zhí)行效率。

Figure 3 Reconstruction of the computing kernel圖3 算核重構(gòu)

3.2 整體架構(gòu)

DES口令恢復(fù)算法主要由口令生成、DES算核和對(duì)比邏輯構(gòu)成，并由主控模塊與上位機(jī)通信，完成任務(wù)的初始化與配置。其中DES算核支持動(dòng)態(tài)可重構(gòu)，可根據(jù)用戶配置信息，重構(gòu)成不同功能和結(jié)構(gòu)的算核。同時(shí)，采用GALS架構(gòu)放置多個(gè)算子模塊，各個(gè)算子獨(dú)立執(zhí)行，可支持同一掩碼多個(gè)任務(wù)或不同掩碼同一任務(wù)等多種恢復(fù)模式。當(dāng)某個(gè)算子找到正確口令時(shí)，由多路復(fù)用器MUX(MUltipleXer)進(jìn)行仲裁輸出，并傳遞給上位機(jī)，其整體框架如圖4所示。

Figure 4 Password recovery overall framework of DES computing kernel圖4 DES算核口令恢復(fù)整體框架

基于算核模型，采用粗細(xì)粒度的混合結(jié)構(gòu)，以重構(gòu)IP置換、密鑰拓展、輪運(yùn)算等模塊，形成串行、并行、流水線等多種執(zhí)行方式，以及加密、解密等多種不同的DES算核。同時(shí)，配以不同的口令生成策略和對(duì)比模塊，滿足不同應(yīng)用的計(jì)算需求。基于擬態(tài)計(jì)算的DES口令恢復(fù)，其流程如算法1所示。

算法1DES口令恢復(fù)算法

輸入：FPGA配置信息、任務(wù)信息和口令策略。

輸出：正確密鑰key。

1.由FPGA配置信息，載入對(duì)應(yīng)的比特流文件，并完成任務(wù)和口令的配置。

2.While(HasNextKey)do

3.key=GenerateNextKey(口令策略)；

4.d=DES(key)；

5.If( 對(duì)比驗(yàn)證通過(guò) )

6.Returnkey；

7.EndIf

8.EndWhile

從算法1中可以看出，以DES為核心算法的口令驗(yàn)證流程較為簡(jiǎn)明。通過(guò)口令生成模塊產(chǎn)生key，并代入DES算核逐一驗(yàn)證，如果計(jì)算出的結(jié)果和驗(yàn)證串相同，即找到了對(duì)應(yīng)的正確key。

3.3 DES算核優(yōu)化

為滿足不同應(yīng)用的需求，這里對(duì)DES算核的串行實(shí)現(xiàn)進(jìn)行了優(yōu)化，以減少資源占用，提高布線成功率。同時(shí)，使用全流水架構(gòu)實(shí)現(xiàn)DES的高速并行計(jì)算，以空間換取時(shí)間，最大化算法的吞吐量和性能。

3.3.1 串行結(jié)構(gòu)

由于DES解密是加密的逆過(guò)程，只有密鑰使用的順序相反，中間操作完全相同。因此，為實(shí)現(xiàn)統(tǒng)一的DES加/解密算法，在密鑰擴(kuò)展時(shí)，只并行計(jì)算一次，并得到16組Key。然后，通過(guò)狀態(tài)機(jī)控制，根據(jù)當(dāng)前迭代的輪數(shù)，選擇對(duì)應(yīng)的Key。這樣不僅節(jié)省了資源，還簡(jiǎn)化了設(shè)計(jì)。圖5所示為DES串行加/解密的結(jié)構(gòu)圖。

Figure 5 DES serial structure圖5 DES串行結(jié)構(gòu)圖

圖5中，密鑰拓展采用assign連續(xù)直接賦值，并由16個(gè)寄存器數(shù)組保存，可在1個(gè)時(shí)鐘周期內(nèi)執(zhí)行完成。單輪計(jì)算也采用assign賦值，可在1個(gè)時(shí)鐘周期內(nèi)完成，并將結(jié)果保存在寄存器中，由狀態(tài)機(jī)控制，向下傳遞。整個(gè)DES加/解密串行需要17個(gè)時(shí)鐘周期，其中數(shù)據(jù)輸入占用1個(gè)時(shí)鐘，計(jì)算過(guò)程占用16個(gè)時(shí)鐘，并在最后一次計(jì)算完成后，直接輸出結(jié)果。

3.3.2 全流水架構(gòu)

在使用FPGA以全流水架構(gòu)實(shí)現(xiàn)DES算法時(shí)，需要將單輪計(jì)算實(shí)例化16次，并使用寄存器數(shù)組存儲(chǔ)每輪的計(jì)算結(jié)果，然后順次傳遞。由于參與運(yùn)算的數(shù)據(jù)和密鑰是連續(xù)的，因此在密鑰擴(kuò)展時(shí)，需要在1個(gè)時(shí)鐘周期內(nèi)生成16組數(shù)據(jù)對(duì)應(yīng)的密鑰，并參與16輪計(jì)算。如圖6所示，采用位寬為48 bit的寄存器數(shù)組Key_r[0:15]存儲(chǔ)擴(kuò)展后的密鑰，數(shù)據(jù)在經(jīng)過(guò)初始化后，由寄存器數(shù)組L_r[0:15]和R_r[0:15]依次進(jìn)行存儲(chǔ)。

Figure 6 DES pipeline architecture圖6 DES流水線架構(gòu)

當(dāng)流水線開始工作時(shí)，在第1個(gè)時(shí)鐘周期對(duì)第1組數(shù)據(jù)進(jìn)行初始化和密鑰擴(kuò)展，生成Key_r[0]，然后參與第1輪運(yùn)算，產(chǎn)生結(jié)果L_r[1]和R_r[1]。在第2個(gè)時(shí)鐘周期，Key_r[0]會(huì)進(jìn)行密鑰擴(kuò)展生成Key_r[1]，并和L_r[1]、R_r[1]參與第2輪計(jì)算，產(chǎn)生結(jié)果L_r[2]和R_r[2]。同時(shí)，第2組數(shù)據(jù)會(huì)進(jìn)行初始化和密鑰擴(kuò)展操作，生成新的Key_r[0]，并參與第1輪計(jì)算，產(chǎn)生新的L_r[1]和R_r[1]。以此類推，直至16輪迭代計(jì)算完成，然后依次輸出16組數(shù)據(jù)的加密結(jié)果。顯然，每組數(shù)據(jù)都要經(jīng)過(guò)16個(gè)時(shí)鐘周期才能計(jì)算出結(jié)果。但是，當(dāng)流水線滿負(fù)荷工作時(shí)，每個(gè)時(shí)鐘周期都會(huì)產(chǎn)生輸出，相比于串行DES算法，其處理速度提高了16倍，具有很高的計(jì)算性能。

由于FPGA屬于位級(jí)計(jì)算部件，非常適合與或非、異或、移位等操作。而DES運(yùn)算中，正好含有大量的位級(jí)運(yùn)算，但在每輪運(yùn)算中需要8個(gè)S盒參與運(yùn)算，S盒的優(yōu)化顯得十分重要。S盒是一個(gè)十分復(fù)雜的非線性函數(shù)，可以使用多重case，以LUT和MUX進(jìn)行實(shí)現(xiàn)；還可以使用卡諾圖進(jìn)行適當(dāng)化簡(jiǎn)，得到邏輯表達(dá)式，然后使用硬件語(yǔ)言描述；或者直接使用BRAM(Block Random Access Memory)進(jìn)行S盒存儲(chǔ)。前2種方法規(guī)模較小，適宜特定硬件平臺(tái)。第3種方法隨著硬件工藝的提升，對(duì)擁有豐富BRAM資源的FPGA非常適用。

本文采用第3種方法，以BRAM存儲(chǔ)S盒，不僅可以充分利用FPGA資源，還可平衡LUT、寄存器和BRAM的使用，有利于FPGA布局布線。優(yōu)化后的DES單輪結(jié)構(gòu)如圖7所示。

Figure 7 DES single round structure圖7 DES單輪結(jié)構(gòu)

3.4 高速口令生成算法

文獻(xiàn)[18]通過(guò)對(duì)大量真實(shí)口令集的統(tǒng)計(jì)分析，指出口令的頻率分布符合Zipf分布，為評(píng)估口令猜測(cè)攻擊模型提供了理論基礎(chǔ)。由于DES破解速度十分快，結(jié)合口令的Zipf分布，只需采用窮舉策略，即可滿足恢復(fù)的要求。如果采用字典進(jìn)行破解，傳輸帶寬將成為計(jì)算瓶頸。同時(shí)，由于字典通常只包括常見的弱口令，且無(wú)法涵蓋所有口令，必然存在口令遺漏的情況。本文方案優(yōu)化并實(shí)現(xiàn)了掩碼攻擊和奇偶概率攻擊，縮短了計(jì)算時(shí)間。

3.4.1 掩碼攻擊

對(duì)于DES算法，其口令長(zhǎng)度固定為8 B，因此采用全空間的掩碼攻擊。相比于暴力窮舉攻擊，掩碼攻擊可對(duì)口令的每一位進(jìn)行配置，使攻擊更加有效。為充分發(fā)揮FPGA計(jì)算效率，使多個(gè)算子并行計(jì)算，將掩碼口令劃分為2部分，其中一部分用來(lái)產(chǎn)生口令前綴，另一部分用來(lái)窮舉余下的口令。這樣，就可將不同的口令前綴分配到多個(gè)算子，并將口令前綴和余下窮舉的口令組合形成完整的口令輸入DES進(jìn)行計(jì)算。其過(guò)程如算法2所示。

算法2掩碼口令生成算法

輸入：口令配置信息pwd_config[7:0][0:7],pwd_fix[0:7]。

輸出：候選口令password[7:0][0:7]。

1.Fori= 0 to 7do

2.password[i] = Null；

3.index[i] = 0；

4.Endfor

5.While(True)do

6.Fori= 0 to 7do

7.If(pwd_fix[i] == 1)∥該位為已知明文

8.password[i] =pwd_config[i]；

9.Else∥全空間窮舉

10.password[i] =AllCharSet(index[i])；

11.EndIf

12. 判斷第i位索引index[i]是否需要進(jìn)位或歸0

13.Endfor

14. 輸出password；

15. 如果index[0,…,7]全為0，跳出While循環(huán);

16.EndWhile

顯然，算法2可以以流水線的方式實(shí)現(xiàn)，在算法中的第1～4行可在1個(gè)時(shí)鐘周期內(nèi)完成初始化，第6～13行可使用8個(gè)模塊并行計(jì)算，并將口令第i(0≤i≤7)位對(duì)應(yīng)的字符同時(shí)輸出，然后在1個(gè)時(shí)鐘周期內(nèi)完成拼接并輸出，如圖8所示。

Figure 8 Mask password generation pipeline 圖8 掩碼口令生成流水線

此外，口令生成的速度在某些情況下會(huì)成為計(jì)算的瓶頸，需要進(jìn)行深度優(yōu)化。本文采用2級(jí)流水線的方法，將原流水線隔斷為2個(gè)獨(dú)立的流水線，1個(gè)模塊工作在低頻，另1個(gè)模塊工作在高頻，并將低頻流水線生成的口令，通過(guò)異步FIFO傳輸給高頻模塊，高頻模塊再對(duì)低頻模塊生成的口令進(jìn)行補(bǔ)位擴(kuò)充操作，并產(chǎn)生最終的口令。經(jīng)該方法優(yōu)化后，掩碼攻擊最高每秒可產(chǎn)生400M個(gè)口令。

3.4.2 奇偶概率攻擊

對(duì)于DES算法的64 bit密鑰，其中8 bit是奇偶校驗(yàn)位，只有56 bit參與計(jì)算。因此，只需從0到256-1窮盡56 bit所有密鑰，即可達(dá)到百分之百破解率。進(jìn)一步，結(jié)合統(tǒng)計(jì)學(xué)分析，采取先窮舉偶數(shù)，再窮舉奇數(shù)的規(guī)則，以優(yōu)先恢復(fù)出其中的部分口令，達(dá)到事半功倍的效果。同時(shí)，放置多個(gè)算子并行計(jì)算，每個(gè)算子分配不同的密鑰前綴，以提高攻擊性能。奇偶概率攻擊口令生成算法如算法3所示。

算法3奇偶概率口令生成算法

輸入：口令配置key_config[17:0]。

輸出：候選口令key[55:0]。

1.key_high[17:0] =key_config[17:0]；

2.key_low[37:0] = 0；

3.While(True)do

4.If(key_low== 38’hFFFFFFFFE)

5.key_low= 1；

6.Else

7.key_low=key_low+2；

8.EndIf

9.If(key_low== 38’hFFFFFFFFF)

10.Break；

11.EndIf

12.key= {key_high,key_low}?！纹唇由蒶ey

13.EndWhile

3.5 恢復(fù)策略

3.5.1 協(xié)議密鑰恢復(fù)

網(wǎng)絡(luò)協(xié)議授權(quán)過(guò)程中，Hash+DES的方式仍被廣泛應(yīng)用著，它以用戶口令輸入Hash函數(shù)，并將產(chǎn)生的結(jié)果經(jīng)過(guò)處理作為DES加密的密鑰，以此保護(hù)用戶數(shù)據(jù)安全。如圖9所示，詳細(xì)給出了VPN PPTP使用微軟Ms CHAP v2身份認(rèn)證的過(guò)程。

Figure 9 Ms CHAP v2 authentication process圖9 Ms CHAP v2認(rèn)證過(guò)程

客戶端和服務(wù)端會(huì)分別由Ms CHAP v2身份認(rèn)證過(guò)程產(chǎn)生各自的NtResponse，并在服務(wù)端進(jìn)行對(duì)比驗(yàn)證，如果2個(gè)NtResponse一致，則驗(yàn)證成功，否則驗(yàn)證失敗。從圖9中的流程可以看出，在截獲協(xié)議交互信息后，可以通過(guò)窮舉用戶口令產(chǎn)生NtResponse，并與截獲的NtResponse進(jìn)行對(duì)比，如果一致，則找到了正確的口令。進(jìn)一步，由于用戶口令范圍極廣，16 bit的全字符空間約有PwdNum=9516個(gè)口令，而DES密鑰空間為KeyNum=256，顯然，PwdNum要遠(yuǎn)大于KeyNum，采用奇偶概率攻擊是十分有效的方法，且對(duì)DES密鑰空間搜索可以達(dá)到100%的破解率。由此，還可直接對(duì)3個(gè)DES進(jìn)行密鑰奇偶概率攻擊，還原MD4哈希值，并據(jù)此恢復(fù)其他加密數(shù)據(jù)。最后，對(duì)諸如此類的網(wǎng)絡(luò)協(xié)議，如LM、NTLM v1、Ms CHAP v1、Kerberos 5等，都可以用類似方法進(jìn)行密鑰恢復(fù)。

3.5.2 數(shù)據(jù)密鑰恢復(fù)

對(duì)于使用DES加密數(shù)據(jù)的恢復(fù)，在得到足夠多密文的情況下，可以用口令逐一嘗試，并以輸出明文為判斷條件，當(dāng)連續(xù)得到np組明文時(shí)，即找到了唯一的正確口令。對(duì)于DES ECB模式的口令恢復(fù)如圖10所示。

Figure 10 DES ECB decryption diagram圖10 DES ECB解密示意圖

由于ASCII碼表中有256個(gè)字符，其中95個(gè)為可顯示字符，則DES解密全為明文的概率為q=(95/256)8≈3.60×10-4。全口令空間大小為488(去除奇偶校驗(yàn)位重復(fù)的字符)，只有一個(gè)正確口令的概率為p=1/(488)≈3.55×10-14。如果連續(xù)解密成功4組數(shù)據(jù)，有q4≈1.67×10-14，且q4

3.5.3 系統(tǒng)口令恢復(fù)

在服務(wù)器領(lǐng)域，Linux/Unix系統(tǒng)由于其開放性、公開性和可移植性等優(yōu)勢(shì)，被絕大多數(shù)用戶使用。但是，其帶來(lái)諸多便利的同時(shí)，安全問(wèn)題也隨之而來(lái)。其中DES Crypt作為用戶身份認(rèn)證加密算法仍被使用著。DES Crypt算法使用鹽值Salt作為參數(shù)，完成對(duì)用戶口令的加密。例如，特征串“s2JQ85JElCMeU”，其中“s2”為Salt值，“JQ85JElCMeU”為加密后的驗(yàn)證信息。整個(gè)過(guò)程需要25次DES迭代，如圖11所示。

Figure 11 Linux/Unix user password verification process圖11 Linux/Unix用戶口令驗(yàn)證過(guò)程

由于DES口令輸入為8個(gè)字符，因此用戶口令空間為958，可以使用掩碼進(jìn)行全空間搜索，以達(dá)到100%的破解率。進(jìn)一步，對(duì)循環(huán)迭代使用DES或DES Crypt算法的其他軟件、密碼機(jī)或系統(tǒng)都可進(jìn)行類似的口令恢復(fù)。

3.6 DES算核的重構(gòu)

對(duì)于以DES為核心的口令恢復(fù)算法，可以用四元組表示PWRC={PWD,CORE(DES),CMP,SRP}，其中，PWD表示口令，可以是掩碼攻擊、奇偶攻擊或字典攻擊產(chǎn)生的口令；CORE(DES)表示以DES為核心的算法，可以是DES的變形算法或其他算法的組合，如DES Crypt、Hash+DES、2次DES迭代組合等；CMP表示結(jié)果對(duì)比；SRP表示存儲(chǔ)正確口令。

為了有效支持各種應(yīng)用場(chǎng)景的DES恢復(fù)，對(duì)PWRC進(jìn)行可重構(gòu)設(shè)計(jì)，如圖12所示。圖12中深灰色表示粗粒度可重構(gòu)模塊[19]，各模塊間由FIFO互連。采用基于算核的映射方式，在PWD、CORE(DES)、CMP各階段選擇不同的算核進(jìn)行靈活重構(gòu)，形成應(yīng)用。其次，改變FIFO位寬和深度銜接各個(gè)模塊，完成異步時(shí)鐘域的同步和數(shù)據(jù)傳輸。最后，以參數(shù)配置的形式實(shí)例化多個(gè)算子，適配多種FPGA并提高了資源利用率。針對(duì)網(wǎng)絡(luò)協(xié)議、數(shù)據(jù)和系統(tǒng)的口令恢復(fù)，給出如下幾種重構(gòu)結(jié)構(gòu)，如表1所示。

Table 1 Reconstruction structure description of each application表1 各應(yīng)用重構(gòu)結(jié)構(gòu)說(shuō)明

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

本文實(shí)驗(yàn)的硬件平臺(tái)是4核FPGA集成加速卡，芯片型號(hào)為XILINX公司的xcku060，其查找表LUT資源為331 680，F(xiàn)F寄存器資源為663 360。軟件平臺(tái)為集設(shè)計(jì)、仿真、綜合、布線、生成于一體的Vivado軟件。實(shí)驗(yàn)通過(guò)對(duì)DES口令恢復(fù)算法的各模塊進(jìn)行深度優(yōu)化，給出了資源占用及各種重構(gòu)方案，使最終算法在吞吐量、運(yùn)行速度、資源利用率等方面有了較大的提升。其次，與CPU、GPU和其他方案進(jìn)行了性能對(duì)比分析。最后，給出了各種應(yīng)用及口令策略的恢復(fù)效率分析。

4.1 各模塊實(shí)現(xiàn)

表2所示為DES口令恢復(fù)算法主要算核的資源占用情況。從表2中可以看出，各模塊占用資源較少，完全滿足算核的設(shè)計(jì)要求，可重構(gòu)成各種結(jié)構(gòu)，并布局多個(gè)模塊并行計(jì)算，滿足不同應(yīng)用的需求。表3所示為4種典型應(yīng)用的DES算核重構(gòu)方案及實(shí)現(xiàn)情況。從表3中可以看出，每個(gè)應(yīng)用不僅充分利用了FPGA資源，工作頻率還均在360～400 MHz，具有非常高的性能。

Table 2 Implementation of each module表2 各模塊實(shí)現(xiàn)情況

Table 3 Typical application of DES computing kernel reconstruction and implementation表3 典型應(yīng)用DES算核重構(gòu)及實(shí)現(xiàn)情況

4.2 性能對(duì)比分析

首先，給出了本文DES實(shí)現(xiàn)方案與其他方案的對(duì)比，如表4所示，其中吞吐量的計(jì)算公式為：吞吐量=輸入位寬×頻率。從表4中可以看出，本文實(shí)現(xiàn)的17級(jí)流水線DES方案較其他方案具有更高的吞吐量。

Table 4 Comparison of the scheme in this paper with other schemes表4 本文方案與其他方案對(duì)比

其次，以VPN DES為例，使用FPGA加速卡與使用CPU、使用GPU在性能、功耗和能效比方面進(jìn)行了對(duì)比，結(jié)果如表5所示。其中CPU型號(hào)為NVIDIA Intel i5-7500(4核，3.40 GHz)，GPU為GTX 1080(2 560核，1 860 MHz)，軟件測(cè)試平臺(tái)為hashcat v3.60。能效比計(jì)算公式為：能效比=性能/功耗，顯然能效比越高越好。

Table 5 Performance comparison among platforms FPGA,CPU and GPU 表5 FPGA、CPU和GPU平臺(tái)上性能對(duì)比

從表5中可以看出，使用FPGA的速度分別是使用CPU和GPU的2 353.14倍和14.19倍，使用GPU的速度是使用CPU的165.81倍。使用FPGA的能效比分別是使用CPU和使用GPU的584.96倍和11.02倍，使用GPU是使用CPU的53.08倍。無(wú)論是從速度還是能效比，使用FPGA都要優(yōu)于使用CPU和GPU。一方面由于DES算法主要為邏輯運(yùn)算，非常適合FPGA實(shí)現(xiàn)。另一方面，基于算核的設(shè)計(jì)方法充分利用了FPGA資源，提高了FPGA計(jì)算頻率，具有明顯的優(yōu)勢(shì)。

最后，給出了單個(gè)FPGA隨DES算核個(gè)數(shù)增加及加速卡隨FPGA個(gè)數(shù)增加的功耗變化情況，如圖13和圖14所示。從圖13和圖14中可以看出，板卡空載功耗約為64.48 W，每個(gè)算核的功耗約為0.3 W，整個(gè)加速卡的功耗約為276.32 W。顯然，基于算核的實(shí)現(xiàn)方式，在保證了DES性能的同時(shí)具有較低的功耗，適合大規(guī)模使用。

Figure 13 FPGA power consumption changes with the increasement of DES computing kernels圖13 FPGA隨DES算核增加的功耗變化

Figure 14 Accelerator card power consumption changes with the increasesment of FPGAs圖14 加速卡隨FPGA個(gè)數(shù)增加的功耗變化

4.3 口令攻擊分析

4.3.1 掩碼模式攻擊

針對(duì)DES ECB加密模式，使用掩碼模式攻擊，對(duì)數(shù)據(jù)進(jìn)行恢復(fù)。當(dāng)連續(xù)np組解密后的數(shù)據(jù)都為明文時(shí)，即可判斷解密成功。表6給出了各種口令組合使用單個(gè)加速卡掩碼攻擊的恢復(fù)時(shí)間。

Table 6 DES ECB mask attack recovery time表6 DES ECB掩碼攻擊恢復(fù)時(shí)間

從表6中可以看出，對(duì)于常用的數(shù)字+字母組合口令，使用加速卡進(jìn)行恢復(fù)，僅需要8.88 s的時(shí)間，對(duì)數(shù)字+字母+特殊字符的組合口令，最長(zhǎng)也僅需要177.90 s。顯然，對(duì)于DES ECB加密模式數(shù)據(jù)的恢復(fù)，本文方案基本可以做到實(shí)時(shí)恢復(fù)，效率十分可觀。

對(duì)于Linux/Unix系統(tǒng)口令的恢復(fù)，每次初始化計(jì)算時(shí)會(huì)先將口令左移1 bit，但參與DES Crypt計(jì)算的仍為56 bit有效密鑰。這樣，可以統(tǒng)計(jì)分析移位后的字符，并直接使用移位后的字符作為新的字符表，再去除其中重復(fù)的字符，以此來(lái)減少口令空間。同時(shí)，由于DES Crypt需要循環(huán)迭代25次，使用掩碼攻擊，其恢復(fù)時(shí)間會(huì)增加25倍。

4.3.2 奇偶概率攻擊

搭建服務(wù)器集群，每個(gè)服務(wù)器配有8個(gè)加速卡，以VPN PPTP為恢復(fù)對(duì)象，采用奇偶概率攻擊，窮舉0～256-1所有56 bit密鑰，表7所示為隨著服務(wù)器個(gè)數(shù)的增加，其恢復(fù)時(shí)間的變化。

Table 7 Password recovery time on server cluster 表7 服務(wù)器集群上口令恢復(fù)時(shí)間

從表7中可以看出，當(dāng)服務(wù)器集群規(guī)模為16時(shí)，加速卡可在0.58 h內(nèi)窮盡56 bit全部密鑰空間，達(dá)到100%的恢復(fù)效率。而crack.sh系統(tǒng)含有48塊 XILINX Virtex-6 LX240T FPGA，需要26 h才能窮盡56 bit密鑰空間，文獻(xiàn)[4]在120塊XC7S100 FPGA規(guī)模下，也需要19 h。對(duì)大量VPN的恢復(fù)任務(wù)，本文服務(wù)器集群可保證短時(shí)間內(nèi)的有效恢復(fù)，為電子取證提供了強(qiáng)力支撐。

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

本文提出的混合可重構(gòu)的DES算核多應(yīng)用口令恢復(fù)方案，以DES算核為研究對(duì)象，設(shè)計(jì)并優(yōu)化了串行、全流水結(jié)構(gòu)的DES算核。然后，基于統(tǒng)計(jì)學(xué)原理，給出了掩碼攻擊和奇偶概率攻擊，提高了應(yīng)用口令恢復(fù)效率，并給出了不同應(yīng)用場(chǎng)景下的恢復(fù)策略。最后，通過(guò)深入剖析各應(yīng)用的特征，以DES算核的變結(jié)構(gòu)組合，適配各種應(yīng)用。實(shí)驗(yàn)結(jié)果表明，該方案可重構(gòu)出的DES算法在性能、資源、功耗等方面具有明顯優(yōu)勢(shì)，較使用CPU和GPU有10倍以上的提升。同時(shí)，結(jié)合口令恢復(fù)策略，可在較短時(shí)間內(nèi)恢復(fù)出原始口令。

進(jìn)一步，基于算核的設(shè)計(jì)思想，為定制ASIC芯片提供了理論基礎(chǔ)和技術(shù)支持?？蓪⒖诹钌?、密鑰擴(kuò)展、串行DES、流水線DES、對(duì)比模塊等算核在ASIC芯片內(nèi)部規(guī)劃布局，通過(guò)配置信息完成相應(yīng)算法的切換，并獲取更高的計(jì)算性能。基于算核可重構(gòu)的ASIC DES算法實(shí)現(xiàn)，也是下一步的研究方向。