基于現場可編程門陣列的Linux統一加密設置認證算法的流水線架構

楊文勇,黃 鷺,吳孔程,曹春暉,趙稟睿,李曉潮*

(1.廈門城市職業學院電子與信息工程系,福建 廈門 361008; 2.廈門大學信息科學與技術學院,福建 廈門 361005)

Linux統一加密設置(LUKS)是Linux系統的標準磁盤加密認證規范,適用于各種不同的Linux發行版本和Android操作系統.LUKS的認證算法采用兩層的密鑰結構,即用戶密鑰和主密鑰.主密鑰加密數據,用戶密鑰對主密鑰進行加密.LUKS首先通過基于密碼的密鑰派生函數(PBKDF2)來生成用戶密鑰,使用生成的用戶密鑰加密得到主密鑰后，采用數據分割在存儲前對主密鑰進行擴展和分割,以提高安全性.LUKS認證算法包含哈希算法、對稱加解密算法以及基于哈希消息驗證代碼(HMAC)導出的PBKDF2,其復雜度較高,所需要的硬件資源較多.

Malvoni等[1]提供了LUKS具體實現平臺選擇的依據,從在中央處理器(CPU)、圖像處理器(GPU)和現場可編程門陣列(FPGA)計算平臺上運行同一個認證機制所得到的能效比結果來看,FPGA的能效比最高.目前,在FPGA上實現認證算法的相關研究較少,如何在有限資源的FPGA中實現LUKS算法并獲得較高吞吐率是基于FPGA兌現工作的研究重點,需要兼顧吞吐率、占用資源大小、資源利用率和功耗等因素.

Lee等[2]通過對高級加密標準(AES)的優化和四級流水線架構的實現,使AES算法吞吐率達到了3.8 Gbit/s;Michail等[3]運用諸如循環展開、預計算、重定時等多種技術來實現安全散列算法(SHA)-1,其優化后的架構在Virtex-4器件(xc4vlx100-12FF1148)上實現了8.05 Gbit/s的吞吐率,占用的Slice數為2 390.可以看出,通過對AES和SHA-1進行優化能夠在有限資源的FPGA平臺上達到較高吞吐率.Li等[4]首次在FPGA平臺上采用PBKDF2-SHA1和AES-128算法,實現了生成用戶密鑰模塊的LUKS流水線架構,SHA-1的吞吐率達到了1 786 Mbit/s,使用1 033個Slice中的查找表(LUT)在實現平臺Picozed 7030上的密鑰恢復速度為20.6 s-1.由于Li等[4]僅在LUKS的較高層級采用了流水線架構,沒有對SHA-1等關鍵基礎模塊采用流水線,實驗數據表明這些模塊的吞吐率還有很大的提升空間.王文功等[5]在多片FPGA上實現了SHA-1的并行運算,但因為沒有對算法的底層實現進行流水線優化,吞吐率只有3.2 Gbit/s.劉恒等[6]將MD5、SHA-1、SHA-2等7種哈希算法設計為一個可重構IP,實現了一種高效可配的哈希算法硬件架構,但其中SHA-1的吞吐率較低,只有640 Mbit/s.龔向東等[7]采用了流水線架構優化AES的關鍵路徑-密鑰擴展,占用資源1 139 個Slice、308個塊隨機存取存儲器(BRAM)時吞吐率達到了56.83 Gbit/s；但如果考慮BRAM資源,其實際的單位Slice資源吞吐率權為1.40 Mbit/s.

基于以上分析,本研究設計了一種基于FPGA的高吞吐率LUKS認證算法片上系統:1) 對關鍵的PBKDF2-HMAC-SHA-1.算法采用流水線結構,并且基于預計算和回路展開等技術實現了SHA-1流水線結構；2) 充分利用FPGA內部的BRAM資源實現基于S盒和T盒(ST-box)映射表的AES算法,節省片內Slice資源給其他的流水線結構,并提升AES算法所對應電路的工作頻率；3) 對主要模塊進行合理分割,平衡了各模塊之間的運算時鐘數,以提高整體架構的工作頻率.

1 LUKS算法概述

LUKS認證算法流程如圖1所示.由圖1可知，雖然LUKS加密的最后階段對主密鑰進行了銷毀,但是可以在被加密硬盤上的密鑰數據區獲取到與主密鑰有關的數據,進而完成解密.PBKDF2所需的主密鑰鹽值和迭代次數,加密LUKS盤所使用的哈希算法和對稱加解密算法的類型都能夠從LUKS加密卷的卷頭(PHDR)上獲得[8].

圖1 LUKS認證算法的密碼驗證過程Fig.1 Password verification process of LUKS authentication algorithm

2 LUKS架構設計與實現

2.1 整體架構設計

本設計的整體架構分為兩個部分，即主控處理器部分和LUKS硬件協處理器部分,分別基于FPGA的硬件處理器(PS)和可編程邏輯(PL)資源實現.兩者之間采用先進可擴展接口(AXI)進行通信,主控處理器通過AXI與片內BRAM和LUKS電路模塊相連,輸入數據并獲得LUKS協處理器的運算結果.在BRAM中,儲存有主密鑰的相關數據,作為AES解密模塊的輸入.其他LUKS模塊所需要的數據可以從AXI相關的寄存器中獲取.

表1 流水線結構LUKS中IP核各模塊的時延

Tab.1 Amount of delayed for each module of IP core in LUKS pipeline architecture

模塊時延/clock 密碼生成器 16 PBKDF2第一級3 600 960 PBKDF2第二級3 600 960 PBKDF2第三級3 601 048 PBKDF2第四級3 601 048 AES AF-Merge1 631 672 PBKDF2校驗哈希值生成3 619 000 哈希值比較1

圖2 LUKS硬件協處理器架構Fig.2 Hardware coprocessor architecture of LUKS

基于以上各模塊運算時鐘數的分析，本研究設計了如圖2所示的硬件協處理器架構,包括1個密碼產生模塊、5個PBKDF2模塊、1個AES AF-Merge模塊、1個主密鑰校驗哈希值比較模塊和1個頂層AXI控制模塊,模塊之間通過緩存進行連接.接到主控處理器給出的控制指令后,開始認證算法的密鑰驗證過程：1) 由密碼產生模塊生成用戶密鑰并輸入到密鑰緩沖區;2) 第1～4級流水線的PBKDF2模塊從前一級緩沖區中取得輸入并將處理后的數據輸入到后一級的緩沖區;3) AES AF-Merge模塊用前面生成的用戶密鑰去解密和重新組合保存在BRAM中被分割加密的主密鑰數據,恢復出主密鑰并將其存入主密鑰緩沖區中;4) PBKDF2模塊利用輸入的主密鑰生成校驗哈希值并存入哈希值緩沖區;5) 哈希值比較模塊對比哈希值緩沖區中待校驗哈希值與輸入的主密鑰校驗哈希值,兩者相等則向控制模塊返回認證通過的信號,不相等則繼續密碼認證過程.

2.2 SHA-1流水線設計與實現

SHA-1算法以512 bit為單位進行處理,并輸出長度為160 bit的散列值.計算過程中,用寄存器A、B、C、D、E分別存儲一輪運算的中間結果，即5個狀態變量HA、HB、HC、HD、HE.第1組分組數據為SHA-1算法規定的初始常量值H0～H5,在其余分組計算中,HA～HE為上一分組計算出的摘要值.每個狀態變量的大小為32 bit,以容納160 bit的數據[10].圖3(a)給出了SHA-1其中一輪操作的示意圖.圖中:Ki是常量,fi是非線性函數,具體的取值根據80輪中的輪數i有所不同;Wi為由輸入數據分組計算所得的變量[10],RotLx表示將數據循環左移x位.

如果使用最基礎的SHA-1硬件，一個clock使用SHA-1的1輪運算，那么執行整個SHA-1算法就需要80個clock，這樣的設計性能不佳．因此，本文中對SHA-1的運算進行組合,使用了2輪展開,將80輪運算的每2輪運算合并在一起變為1輪運算,新的1輪運算能夠在一個clock內完成[11].同時還采用了預計算的手段,提前計算出下1輪所要用到的值,并寫入R1～R4這4個寄存器中,等待下1輪使用.由于每輪的中間運算結果HA(i),HB(i),HC(i),HD(i),HE(i),可以由HR1(i-1),HR2(i-1),HR3(i-1),HR4(i-1),HA(i-1),HB(i-1)和HC(i-1)得出,所以在一輪計算的過程中,中間值HD(i)和HE(i)無需用寄存器存儲,只在最后一輪才需要引出,因此在中間運算電路實現時,將寄存器D和E移除,以進一步節省資源,如圖3(b)所示.在首輪中對R1,R2,R3,R4這4個寄存器初始化公式如下.

圖3 SHA-1輪操作示意圖Fig.3 Round operation implementation of SHA-1

圖4 4級流水線SHA-1Fig.4 Four-stage pipeline SHA-1

(2)

其中,K0和K1分別為SHA-1中的常量.即便如此,SHA-1的1輪操作也需要花費大量的時間.因此將SHA-1的模塊設計為4級流水線結構,每級流水線完成20輪的計算,如圖4所示.SHA-1的4個核分別處理4級流水線的4個階段.因為第一輪需要預計算,因此第一個核需要經過11個clock才能夠計算出結果,至于其他核,則分別只需要10個clock.每2個核間的寄存器用于存放前一個核的輸出(即10輪運算結束后的狀態變量值),而這些值將作為下一個核的狀態變量輸入.在最后一個核中,還需要將運算結果與前一分組數據塊的摘要值HA、HB、HC、HD、HE相加,以得到最后的摘要值.

表2列出了本研究與其他文獻數據的吞吐率對比,吞吐率TP的計算公式如下:

(3)

其中,P代表流水線的級數,B表示進入一級流水線的數據塊的長度,f表示系統所能達到的最大工作頻率，L表示一個數據塊從輸入到計算完畢總共需要經過的時延.對比文獻[12]和[13],本研究的設計有著較大的工作頻率、吞吐率和TPS,并且所使用的資源較少.由表2可知，采用基于28 nm工藝的Zynq系列7030 FPGA可以實現比基于40 nm工藝的Virtex 6更高的吞吐率和單位資源吞吐率.本研究設計的工作頻率達到了301 MHz,TPS達到了17.52 Mbit/s.

2.3 流水線PBKDF2設計與實現

本研究的流水線PBKDF2的導出密鑰值

DK=PBKDF2(PRF,P,salt,iteration,dklen).

(4)

表2 4級流水線的SHA-1實現結果比較

Tab. 2 Result comparison of four-stage pipelined SHA-1 implementation

器件時延/clockSlicesf/MHzTP/(Mbit·s -1)TPS/(Mbit·s-1) 參考文獻Virtext-6411 230172.3208 607.66.99 [12]Virtext-641113.5605 672.4[13]Virtext-6411 221196.7449 827.68.05 本研究Zynq 703041858301.00415 035.517.52本研究

圖5 算法流程Fig.5 Flow of algorithm

注：TPS是單位Slices資源的吞吐率,下同.其中:PRF表示偽隨機函數,本研究選用HMAC-SHA-1;P代表密碼；salt是隨機生成的鹽值,長度為32 bit；iteration表示偽隨機函數循環的次數;dklen是導出密鑰DK的長度.導出密鑰被分為多個塊計算,每一塊的結果值Tn由PRF函數經過循環迭代計算得出,最后得到的DK由T1…Tn連接而成.

PBKDF2及其HMAC的底層函數框圖如圖5所示,圖中ipad和opad表示兩個固定常量,int(n)表示整數n的4字節十六進制數.圖5(b)給出了HMAC-SHA-1函數所進行的具體計算步驟,其中的H函數表示SHA-1運算,K0與圖5(a)中的P相對應,M則表示圖5(a)中的Salt‖int(n)(第n次迭代)或者是上一個PRF函數的輸出.HMAC函數中的摘要h0和h1會分別被計算iteration次，考慮到HMAC函數的輸入不變,每次h0和h1的計算結果均不變，故只需計算一次h0和h1，并存于寄存器中,即可將PBKDF2中SHA-1的執行次數從4×iteration次下降到2+2×iteration次.

考慮到在LUKS認證算法中需要大量的PBKDF2算法迭代,在此采用流水線架構來實現[14],其架構如圖6所示.每個PBKDF2中包含2個SHA-1的模塊,而每個SHA-1模塊采用4級流水線架構,所以整個PBKDF2-HMAC-SHA-1采用8級流水線的架構,需要82個clock完成一次迭代.其中寄存器1～8存放8個不同的h1值,而寄存器9～16存放8個不同的h0值.HMAC摘要寄存器用于累計每次HMAC-SHA-1函數的輸出摘要h3,經iteration次迭代后,該寄存器內的值即為PBKDF2函數的輸出密鑰.

圖6 PBKDF2-HMAC-SHA-1架構Fig.6 PBKDF2-HMAC-SHA-1 architecture

表3 PBKDF2占用資源及其性能對比

Tab. 3 Resource utilization and performance in PBKDF2

實現架構器件Slice時延/clockf/MHzTP/(Mbit·s-1)TPS/(Mbit·s-1) 8級流水線(本研究)Virtex-53 800881506 9821.84 20級流水線[15]Virtex-56 3813841504 6800.74

將本研究流水線架構實現的和文獻[15]中恢復WiFi保護訪問(WPA)/WPA2密鑰的PBKDF2-HMAC-SHA-1性能進行比較,如表3所示.本研究的8級流水線PBKDF架構僅使用3 800個Slice資源,而文獻[15]的20級流水線結構使用了6 381個Slice資源.并且本研究的PBKDF2構架完成8級流水只需88個clock,而文獻[15]完成20級流水需要384個clock,可見本研究的構架在完成每級流水平均所需的clock數上占優勢.在相同時鐘頻率的條件下,本研究的吞吐率高達6 982 Mbit/s,而文獻[15]的吞吐率為4 680 Mbit/s,可見本研究的8級流水線架構比20級流水架構的吞吐率還要高出許多.從資源利用率的角度看,本研究的TPS參數為1.84 Mbit/s,而文獻[15]中僅為0.74 Mbit/s.

2.4 AES-128的設計與實現

由于SHA-1和PBKDF2算法實現中采用流水線結構,占用了較多的LUT資源,因此在實現AES算法時,采用ST-box映射表的架構,并利用FPGA片內BRAM資源來實現.通過對AES輪運算(前9輪)的變換,可以得出以下公式:

(5)

根據式(5)，本設計將AES-128解密算法的一輪操作分為3個部分:前端行移位部分、中部ST-box表部分和后端輪密鑰加密部分.AES-128解密算法的輸入為16 B的數據,分別對應于式(5)中狀態矩陣ai,j,存放在16個寄存器中.將這些寄存器依據行移位規則連接到中部ST-box表部分的BRAM上,寄存器中的值就可以作為BRAM的地址,BRAM的輸出端則輸出對應地址的內容，完成式(5)中的行移位和逆T-box的代換.最后,再將狀態矩陣中的1列所需的4個逆T-box代換的值與該列對應的輪密鑰一同進行異或操作,就可以得到新的狀態矩陣中所對應的列.

表4列出了本研究設計的AES架構的數據與其他文獻的對比.文獻[16]和[17]在時延(每處理一個數據塊所需clock數)方面與本研究相同,但是本研究的AES架構在各平臺都能達到較高的工作頻率,在Virtex-7平臺中，本研究的工作頻率接近文獻[16]中的2倍，且獲得了最高的吞吐率8.346 Gbit/s.另外,本研究架構在7030平臺上實現所需Slice數最少.在各種平臺下,文獻[16]和[17]分別使用了2和4個BRAM資源,而本研究使用了8個BRAM,可以節約Slice資源,不搶占PBKDF2模塊的Slice資源,并且工作頻率高,整體的LUKS認證算法電路的頻率并不會因AES模塊受到限制.綜上所述,8個 BRAM的AES架構兼顧了時序和資源的需求,適合本研究的LUKS認證算法設計.

表4 AES算法不同實現之間的數據對比

Tab. 4 Comparison between different implementations of the AES algorithm

器件SlicesBRAM時延/clockf/MHzTP/(Gbit·s-1) 文獻Virtex-52032103334.262[16]Virtex-71392103574.569 [16]Virtex-51934103504.480 [17]Virtex-62104103003.840 [17]Virtex-73324102513.218 [17]Virtex-51318105166.605 本研究Virtex-61638105416.925 本研究Virtex-71318106528.346 本研究Picozed 70301008106398.179本研究

3 實驗結果與分析

本研究的LUKS認證系統基于Xilinx的Picozed開發板,該開發板搭載的主芯片為ZYNQ 7030,使用的軟件開發環境為Xilinx Vivado 2014.4,測試程序基于FreeRTOS操作系統,通過板級支持包來驅動LUKS協處理器完成認證計算和測試.板級支持包中包含有LUKS IP核的驅動、BRAM的驅動、串口驅動和以太網驅動等.本研究的設計占用了78.3%的Slice LUT資源,62.45%的Slice寄存器資源和15.47%的BRAM資源,如圖7所示.此處沒有列出用于連接不同模塊和組成AXI總線控制器的Slice LUT和Slice寄存器資源的利用率,但是它們已經被計入整個設計的利用率.用來生成用戶密鑰的PBKDF2算法使用了整個芯片約一半的資源(55.3%).此外,還有12.08%的BRAM資源用于保存密鑰數據區(這部分資源沒有列入圖7中).

1～4表示PBKDF2第1～4級,5表示AES AF-Merge，6表示PBKDF2檢驗哈希值生成，7表示整個設計.圖7 流水線結構各模塊資源占用率Fig.7 Resource utilization rate of each module in Pipeline architecture

表5 各平臺LUKS密碼恢復速度和功耗對比(AES-128-ECB)

Tab.5 LUKS password recovery speed and power consumption of each platform(AES-128-ECB)

器件密碼遍歷速度/s-1功耗/W每密碼所需能量/J 文獻 Intel(R) Core(TM) i7-6500U(2核4線程)522.254.450本研究 Intel Core i7 920(4核8線程)732.184.597 本研究 Nvidia GeForce GTX 48031762.520.200 本研究 Picozed 7030 (迭代)1786.130.034 本研究 Picozed 7030 (流水線)3425.270.015 本研究 Picozed 703020.62.440.118[4]

注:在用戶密鑰迭代次數163 682,校驗哈希值迭代次數41 125的條件下測試得到.

表5給出了針對密碼組合AES-128-ECB和SHA-1在各平臺中LUKS密碼恢復速度和功耗的對比.此處功耗為運行LUKS認證算法的動態功耗,即運行時功耗減去待機時功耗的結果.從表5中可以看出,基于Picozed 7030平臺，本研究的密碼恢復速度是迭代結構LUKS算法的2倍,因此密碼恢復不僅占用了較少的資源,而且得到較高的密碼遍歷速度,達342 s-1；而迭代結構的LUKS算法即使耗費了更多的資源,但是密碼遍歷速度僅為178 s-1.另外,本研究的流水線架構所實現的密碼遍歷速度是文獻[4]的16.6倍且已經超過了Nvidia GeForce GTX 480平臺的LUKS密碼遍歷速度.

在功耗方面,基于迭代結構的設計在恢復一個密碼時所要消耗的能量是0.034 J,而流水線架構僅需0.015 J,不到迭代結構的一半.在CPU和GPU平臺上,恢復一個密鑰所需要的能量則遠遠大于FPGA平臺.在Nvidia GeForce GTX 480平臺上,每個密鑰所需能量為0.200 J,是流水線方法的13.3倍,而在Intel Core i7 920(4核8線程)平臺上,每個密鑰所需能量(4.597 J)是流水線方法的306.5倍.本研究實現的功耗僅為文獻[4]中功耗的12.7%.因此,流水線架構的實現在密碼恢復速度,資源利用和能效比方面都優于迭代結構的設計.

4 結 論

本研究基于FPGA研究和實現了一種LUKS認證算法的流水線架構,為了充分利用FPGA的有限資源,分析了整體架構以及所涉及的密碼算法,進行了優化設計,并且采用流水線和查表的實現方式來達到吞吐率和資源利用率的平衡.通過對總體結構設計和底層算法的優化,系統的整體吞吐率、資源利用率和功耗等指標都得到較大的改善，主要體現在:1) 對關鍵的PBKDF2-HMAC-SHA1算法采用8級流水線結構,通過優化降低了其迭代次數;并且基于預計算和回路展開實現了4級流水SHA-1結構,并在具體實現時優化移除了部分寄存器.2) 考慮到PBKDF2的流水線結構占用了較多的LUT資源,因此在實現AES算法時采用基于ST-box結構的AES算法,充分利用FPGA內部的BRAM資源實現ST-box映射表,通過使用8個雙端口的BRAM資源,提升了AES算法部分的工作頻率.3) 對模塊進行合理分割,平衡了各級之間的運算clock數,以實現流水線結構的較高工作頻率;并基于Picozed 7030 FPGA開發板實現了LUKS認證片上系統,包括LUKS硬件協處理器、軟件驅動以及基于FreeRTOS操作系統的測試軟件開發.系統運行結果顯示本設計的密碼遍歷速度達到了342 s-1,而功耗只有5.27 W,每個密鑰所需能量為0.015 J.工作在195 MHz的系統口令恢復速度超過了工作頻率為700 MHz、流處理器數量為480的GTX 480 GPU,同時其能耗指標僅為GPU的1/13.