混合可重構(gòu)的DES算核高效能口令恢復(fù)方案

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

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

1 引言

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

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

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

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

2.1 DES應(yī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)行通信加密傳輸。但是，國內(nèi)出現(xiàn)了大量的“翻墻”軟件，有自由門、極速安全VPN、蝙蝠VPN等。不法之徒利用這些網(wǎng)絡(luò)協(xié)議，通過私自架設(shè)服務(wù)器，在國內(nèi)傳播不良信息，并將重要數(shù)據(jù)備份在國外服務(wù)器上，給電子取證和犯罪審查造成了巨大的阻礙。

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

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

2.2 DES算法分析

DES算法是一種單密鑰分組密碼算法，以64 bit的密鑰對64 bit的數(shù)據(jù)分組進(jìn)行加密，輸出64 bit的密文。明文數(shù)據(jù)塊首先經(jīng)過初始置換IP，再使用16個擴(kuò)展后的子密鑰進(jìn)行16輪迭代編碼，最后經(jīng)過一個逆初始置換IP-1，輸出密文，可表述如下：DESm=IP(m)→Round(K0),Round(K1),…,Round(K15)→IP-1。DES解密過程與加密類似，只需要對迭代過程逆序使用子密鑰即可，第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)過初始置換后，被分為L0和R0共2個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ù)迭代過程。其中，F(xiàn)包括：擴(kuò)展函數(shù)E、按位異或、S盒運算和置換函數(shù)P這4個功能模塊。對于密鑰擴(kuò)展，56 bit的密鑰被分成2個28 bit的半密鑰，每個半密鑰經(jīng)過循環(huán)左移處理，并通過選擇置換，產(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)過置換函數(shù)P，得到32 bit的輸出。

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

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

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

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

3.1 算核模型

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

算核的計算模型可表示為：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}，代表算核的串行計算量；ME={me1,me2,…,men}，代表算核所需內(nèi)存容量或硬件寄存器資源；CO={co1,co2,…,con}，代表每條邊eij上的通信量；GR={gr1,gr2,…,grn}，表示計算粒度，粒度大小受輸入輸出數(shù)據(jù)和串、并行實現(xiàn)方式影響。

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

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

3.2 整體架構(gòu)

DES口令恢復(fù)算法主要由口令生成、DES算核和對比邏輯構(gòu)成，并由主控模塊與上位機(jī)通信，完成任務(wù)的初始化與配置。其中DES算核支持動態(tài)可重構(gòu)，可根據(jù)用戶配置信息，重構(gòu)成不同功能和結(jié)構(gòu)的算核。同時，采用GALS架構(gòu)放置多個算子模塊，各個算子獨立執(zhí)行，可支持同一掩碼多個任務(wù)或不同掩碼同一任務(wù)等多種恢復(fù)模式。當(dāng)某個算子找到正確口令時，由多路復(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置換、密鑰拓展、輪運算等模塊，形成串行、并行、流水線等多種執(zhí)行方式，以及加密、解密等多種不同的DES算核。同時，配以不同的口令生成策略和對比模塊，滿足不同應(yīng)用的計算需求。基于擬態(tài)計算的DES口令恢復(fù)，其流程如算法1所示。

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

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

輸出：正確密鑰key。

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

2.While(HasNextKey)do

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

4.d=DES(key)；

5.If( 對比驗證通過 )

6.Returnkey；

7.EndIf

8.EndWhile

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

3.3 DES算核優(yōu)化

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

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

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

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

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

3.3.2 全流水架構(gòu)

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

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

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

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

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

3.4.1 掩碼攻擊

對于DES算法，其口令長度固定為8 B，因此采用全空間的掩碼攻擊。相比于暴力窮舉攻擊，掩碼攻擊可對口令的每一位進(jìn)行配置，使攻擊更加有效。為充分發(fā)揮FPGA計算效率，使多個算子并行計算，將掩碼口令劃分為2部分，其中一部分用來產(chǎn)生口令前綴，另一部分用來窮舉余下的口令。這樣，就可將不同的口令前綴分配到多個算子，并將口令前綴和余下窮舉的口令組合形成完整的口令輸入DES進(jìn)行計算。其過程如算法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可以以流水線的方式實現(xiàn)，在算法中的第1～4行可在1個時鐘周期內(nèi)完成初始化，第6～13行可使用8個模塊并行計算，并將口令第i(0≤i≤7)位對應(yīng)的字符同時輸出，然后在1個時鐘周期內(nèi)完成拼接并輸出，如圖8所示。

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

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

3.4.2 奇偶概率攻擊

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

13.EndWhile

3.5 恢復(fù)策略

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

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

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

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

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

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

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

由于ASCII碼表中有256個字符，其中95個為可顯示字符，則DES解密全為明文的概率為q=(95/256)8≈3.60×10-4。全口令空間大小為488(去除奇偶校驗位重復(fù)的字符)，只有一個正確口令的概率為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ù)用戶使用。但是，其帶來諸多便利的同時，安全問題也隨之而來。其中DES Crypt作為用戶身份認(rèn)證加密算法仍被使用著。DES Crypt算法使用鹽值Salt作為參數(shù)，完成對用戶口令的加密。例如，特征串“s2JQ85JElCMeU”，其中“s2”為Salt值，“JQ85JElCMeU”為加密后的驗證信息。整個過程需要25次DES迭代，如圖11所示。

Figure 11 Linux/Unix user password verification process圖11 Linux/Unix用戶口令驗證過程

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

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

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

為了有效支持各種應(yīng)用場景的DES恢復(fù)，對PWRC進(jìn)行可重構(gòu)設(shè)計，如圖12所示。圖12中深灰色表示粗粒度可重構(gòu)模塊[19]，各模塊間由FIFO互連。采用基于算核的映射方式，在PWD、CORE(DES)、CMP各階段選擇不同的算核進(jìn)行靈活重構(gòu)，形成應(yīng)用。其次，改變FIFO位寬和深度銜接各個模塊，完成異步時鐘域的同步和數(shù)據(jù)傳輸。最后，以參數(shù)配置的形式實例化多個算子，適配多種FPGA并提高了資源利用率。針對網(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)說明

4 實驗結(jié)果與分析

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

4.1 各模塊實現(xiàn)

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

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

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

4.2 性能對比分析

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

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

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

Table 5 Performance comparison among platforms FPGA,CPU and GPU 表5 FPGA、CPU和GPU平臺上性能對比

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

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

4.3 口令攻擊分析

4.3.1 掩碼模式攻擊

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

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

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

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

4.3.2 奇偶概率攻擊

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

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

從表7中可以看出，當(dāng)服務(wù)器集群規(guī)模為16時，加速卡可在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。對大量VPN的恢復(fù)任務(wù)，本文服務(wù)器集群可保證短時間內(nèi)的有效恢復(fù)，為電子取證提供了強(qiáng)力支撐。

5 結(jié)束語

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

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