RAIN:一種面向軟硬件和門限實現的輕量分組密碼算法

曹梅春 張文英 陳彥琴 邢朝輝,3 吳 磊

1(山東師范大學信息科學與工程學院 濟南 250358) 2(三未信安科技股份有限公司 濟南 250014) 3(山東交通學院理學院 濟南 250357)

分組密碼算法作為對稱密碼的一個重要分支，在計算機通信和信息系統安全領域有著廣泛應用，同時也是構造認證加密算法、Hash函數和密碼協議的底層算法.分組密碼的典型結構主要包括Feistel結構、SPN(substitution permutation network)結構和Lai-Massey結構.Feistel結構代表有數據加密標準(data encryption standard, DES)算法[1]和NSA(National Security Agency)設計的SIMON算法[2]等；SPN結構的算法有高級加密標準(advanced encryption standard, AES)[3]、輕量級分組密碼算法Midori[4]和SKINNY[5]等；Lai-Massey結構的算法有國際數據加密算法IDEA[6].Feistel結構加解密采用相同的結構，加解密算法同時實現可以節省資源，但是由于其混淆擴散速度慢，一般輪數比較多，加解密效率相對低一些.而Lai-Massey結構的混淆擴散速度較快，加解密一致，且軟件實現速度快.但是輪函數較為復雜，每輪的硬件實現面積較大.SPN結構混淆擴散速度快，算法輪數一般較少，算法實現時吞吐量較大.一般情況下加密和解密的部件是不同的，解密是加密運算的逆.一些SPN結構加密算法實現解密的開銷通過使用對合運算作為組成部分來進行優化.在SPN結構中，有一類是基于S盒和乘矩陣的AES類結構，該類結構算法有利于對抗差分和線性分析，并進行安全性證明.

輕量級分組密碼是一種特殊的分組密碼體制，對輕量級分組密碼進行研究的動機是某些特定應用需要比AES面積低、功耗低且安全強度相當的加密算法.輕量級密碼算法硬件實現和運行時所占用的系統資源的開銷較少，例如硬件實現面積、運行時所占內存空間大小和能耗等.這類分組密碼算法主要被用于資源受限的計算環境中，例如電子標簽射頻識別(radio frequency identification, RFID)以及一些電池驅動的設備.隨著物聯網的快速發展，物聯網終端傳感器部件廣泛部署,對輕量級密碼體制的需求也越來越大[7].由于輕量級分組密碼具有較低的實現成本和較低的能耗，在物聯網終端和衛星通信網絡中大量部署輕量級密碼算法可以帶來顯著的社會經濟效益.第1代輕量級密碼，例如PRESENT[8]和KATAN[9]僅關注芯片面積，并使用非常簡單的輪函數作為算法的主要組成部分.近年來，具有各類特色的新輕量分組密碼如雨后春筍般涌現.例如短代碼型PRIDE[10]和SPECK[2]，低延遲型PRINCE[11]，MANTIS[5]，QARMA[12]，能抵抗側信道攻擊型LS-Designs[13]和PICARO[14]，以及低能耗型Midori和GIFT[15].

小型加密設備適用于物聯網中，輕量級加密算法的側信道保護實現是一個非常重要的方面，防止側信道攻擊的一種額外保護措施是使用防泄漏設計，尤其是通過對密碼進行額外的調柄(Tweak)輸入.輕量級可調分組密碼通過附加的公開輸入Tweak進行擴展.這樣的算法允許更好的加密模式和認證加密方案的有效構造[16].這類算法包括SKINNY[5]，CRAFT[17]，Deoxys-BC[18]，QARMA[12]，Joltik[19]，以及作為一般設計原則的TWEAKEY框架[20].

安全是密碼算法得以應用的前提.近年來，分組密碼的安全性評估己取得長足的進步.特別是，基于混合整數線性規劃(mixed integer linear programming， MILP)方法的提出和應用[21-23]，使得分組密碼算法安全分析朝著自動化、精細化、標準化、可證明方向發展.

1 RAIN分組密碼

RAIN是一族可調分組密碼算法，分組長度支持64 b和128 b，根據分組長度的不同記為RAIN-64和RAIN-128.兩個版本調柄的長度等于密鑰長度分別為64 b和128 b，它們的迭代輪數分別為30輪和36輪.

1.1 符號說明

符號說明如表1所示：

Table 1 Symbols and Descriptions表1 所用符號及說明

1.2 RAIN算法描述

算法的輪函數由4種運算組成：列混合、字替換、行移位和輪可調密鑰加.圖1和圖2分別展示了RAIN算法的輪函數結構和算法的整體結構.令n比特向量(w0,w1,…,wn-2,wn-1)表示一個密碼內部狀態ST，最左比特w0代表最高有效位，若將內部狀態從左至右每n/16比特劃分為一個單元，則密碼內部狀態ST可表示為(st0,st1,…,st15)，其矩陣形式為

其中，st0表示內部狀態的最左單元，st15表示內部狀態最右單元，每個單元st中最左比特代表最高有效位.

Fig. 1 The round function of theRAIN algorithm圖1 RAIN算法的輪函數結構

Fig. 2 The overall structure of the RAIN algorithm圖2 RAIN算法的整體結構

RAIN算法的具體加密流程：

1) 初始白化(Whitening).將明文P與密鑰K按單元進行異或運算.

2) 列混合(MixColumns, MC).密碼內部狀態矩陣的每一列乘以下二元矩陣：

3) 字節替換(SubCells, SC).將s×s的S盒并行應用于密碼內部狀態的每個單元，當分組長度為64 b時s=4，當分組長度為128 b時s=8.表2給出了RAIN算法所用S盒S4的十六進制表示形式：

Table 2 The Truth Table of RAIN S -box S4表2 S盒S4的真值表

當s=8時所用8 b的S盒S8是經過與SKINNY所用8 b的S盒相似的變換而來，即通過并行放置2個4 b的S盒S4來構造如圖3所示8 b的S盒S8.

Fig. 3 The 8 b S -box S8圖3 8 b的S盒S8

4) 行移位(ShiftRow, SR).采用與AES相同的行移位變換，密碼狀態的第2～4行分別向左循環移動1，2，3個單元.

5) 輪可調密鑰加(AddTweakey, ATK).將輪可調密鑰RTKi與步驟4)的輸出進行異或運算.

輪可調密鑰編排流程：

① 密鑰加(AddKey, AK).令輪可調密鑰經過密鑰加之后的狀態為TAK，則首輪可調密鑰更新中密鑰加計算記為TAK=T?K.隨后的第i輪中TAK=RTKi-1?K，2≤i≤30或36.

② 行移位(SR).對密鑰加(AK)運算的輸出狀態使用與輪函數相同的位置變換.

Table 3 The Round Constant RC of RAIN-64表3 RAIN-64版本的輪常數RC

Table 4 The RoundConstant of RAIN-128表4 RAIN-128版本的輪常數

④ 比特加(AddBit, AB).令輪可調密鑰編排過程中輪常數加運算的輸出狀態為TAC，則比特加運算可描述為：提取狀態TAC中每個單元的第1比特，將提取的16個比特進行異或運算得到1 b的輸出，即：

TAC[0][0]+TAC[1][0]+…+TAC[15][0],

運算結果用于替代狀態TAC中每個單元的第1位即為比特加運算的輸出RTK.

加密過程和解密過程偽代碼見算法1和算法2所示.實現RAIN算法的代碼可通過https://github.com/CaoMeichun/RAIN.git獲取.RAIN算法的測試向量見附錄A.

算法1.加密算法.

輸入:P,K,T;

輸出:C.

①stateWhitening=P?K;

② for 1≤i≤Nrdo

③stateMC=M·stateWhitening;

④ for 0≤j≤15 do

⑤stateSC[j]=Ss(stateMC[j]),s=4,8;

⑥ end for

⑦ for 1≤j≤15 do

⑧stateSR[j]=SR(stateSC[j]);

⑨ end for

⑩stateATK=stateSR?RTKi;

算法2.解密算法.

輸入:C,K,T;

輸出:P.

①stateMC_inv←C;

② forNr≥i≥1 do

③stateRTK_inv=stateMC_inv?RTKi;

④ for 0≤j≤15 do

⑤stateSR_inv[j]=SR-1(stateMC_inv[j]);

⑥ end for

⑦ for 1≤j≤15 do

⑧stateSC_inv[j]=Ss-1(stateSR_inv[j]),s=4或8;

⑨ end for

⑩stateMC_inv=M·stateSC_inv;

2 算法輪函數的設計

我們的設計遵循強安全性、高效的軟硬件實現、簡單的結構以及強靈活性等宗旨.RAIN的整體結構為SPN結構，S盒的選擇是密碼設計中的關鍵，對于4 b的S盒，我們將S盒的差分均勻度設為4，并將線性度設為8.當2個條件都滿足時，我們篩選出具有安全性的S盒.擴散層的設計既要為算法獲取良好的安全邊界也要考慮到軟硬件實現的性能，另一個重要標準是使得加密過程中密鑰盡可能快地影響密碼內部狀態.輪常數的選取需遵循3個原則：1)區分不同的輪并避免對稱性;2)使子空間密碼分析復雜化;3)避免利用S盒中的固定點進行攻擊.

2.1 RAIN算法的S盒設計

本算法采用4×4安全輕量S盒以及基于此S盒構造的8 b輸入輸出S盒.S盒的選擇不僅考慮了如差分密碼分析和線性密碼分析等常規的安全性，還考慮了S盒的門限實現方案以達到抵御側信道攻擊的目的.

RAIN算法2個版本均采用4 b的S盒，一個原因是4 b的S盒可以用單指令多數據流擴展(streaming SIMD extensions, SSE)等指令集快速實現，另一個原因是硬件實現代價的考慮.和8 b的S盒相比，4 b的S盒具有明顯的硬件優勢，不僅硬件實現代價小，而且延遲能耗等方面都有明顯優勢.采用由2個并行處理的4 b的S盒組成8 b的S盒，以最小化基于輪的實現中的路徑延時.該結構采用4 b的S盒構造非線性變換層，相較于AES等算法采用的8 b的S盒，更易于硬件實現，延遲、面積、能耗等指標更優.其次，4 b的S盒在各種平臺的軟件實現靈活，可以采用查表方式，也可以采用比特切片的實現方式.

(1)

(2)

其中s的值為4.

對于任意雙射4 b的S盒，均有Diff(S)≥4且Lin(S)≥8，當這2個值都達到最小時,可以稱該S盒為最優S盒.

RAIN算法使用的S盒的差分均勻度、非線性度以及線性度為別為4，4，8，該S盒的密碼學性質達到了最優.且此S盒代數次數為3，同時兼顧了S盒高代數次數的要求.

2.2 S盒的門限實現

S盒門限實現[26-28]為加密算法的實現提供了可證明的安全性，用來抵抗側信道攻擊.本文S盒S4的布爾表達式為

(3)

其中，(x0,x1,x2,x3)表示S4的4 b輸入變量，(y0,y1,y2,y3)表示S4的4 b輸出變量.S4的1個分量函數y0由1個立方項、2個二次項和2個一次項組成.為了降低硬件實現中的電路復雜性以及縮減電路開銷，將代數次數為3的分量函數轉換為代數次數為2的子函數的復合，然后對這些子函數進行門限實現.共享份額[29]為3的門限實現方案[30]見附錄B.

此門限方案中，秘密信息被隨機地分成了多個份額，即使其中某個份額的信息被泄露，也不會對此S盒造成威脅.

由于S4其余的3個分量函數可通過該分量函數y0中變量的循環移位獲得，其余的3個分量函數的門限實現方案與y0相同.在進行硬件實現時，它們的面積開銷與功耗也相似.

2.3 RAIN算法的擴散層設計

擴散層的設計是為了提供擴散，因此輸出的每一列依賴于輸入的某些列.在算法的擴散層結構上，我們希望擴散層便于解密過程的求逆，并且解密逆運算和加密正運算的性能是等價的.同時還考慮了擴散層和S盒產生強擴散的計算資源和實現效率，要求每個比特使用的異或數量不能超過3個.考慮到可逆性，我們利用對合矩陣M構造擴散層，使線性層的加密和解密可以使用相同的代碼塊來減少算法實現所需指令的數量.

分支數反映了線性擴散層的安全性能，擴散層的分支數越大，在進行差分密碼分析或者線性密碼分析時需要選擇(己知)明文數越多，密碼的安全性就越好.分組密碼的擴散層都可以表示為有限域上的線性變換操作，所以設計一種高擴散性的密碼算法就相當于設計一個具有最大分支數的線性變換.

(4)

(5)

其中，MT是矩陣M的轉置，W(X)表示向量X的漢明重量.

定義3.若一個m階矩陣的差分分支數和線性分支數均等于此矩陣的階數m，即BD(M)=BL(M)=m，則該矩陣M是幾乎最優極大距離可分碼(maximum distance separable, MDS)矩陣.

雖然許多加密算法使用MDS矩陣作為擴散層，但不可否認的是，MDS矩陣在提供了最優的擴散性能的同時，使算法效率下降，這將消耗更多的軟硬件資源，算法的實現需要更長的運行時間.我們使用線性分支數和差分分支數均等于4的幾乎最優MDS矩陣，從而在安全性和效率之間取得最佳平衡.幾乎最優MDS矩陣都具有次優的分支數，但是與MDS矩陣相比，它們的實現代價小，具有更高的硬件和軟件實現效率.幾乎最優MDS矩陣只需要簡單的異或運算，從而大大減少了硬件和軟件資源的消耗.

3 安全性分析

3.1 差分分析

差分分析是最初由Biham和Shamir[31]于1991年針對DES算法提出的一種密碼分析方法.該方法幾乎適用于所有的分組密碼體制，是對分組密碼算法威脅最大的分析方法之一[32-33].對于采用S盒作為核心部件的分組密碼算法，評估單條差分傳播路徑最大概率上界的最有效方法就是估算差分傳播路徑中活躍S盒的個數.2011年Mouha等人[21]利用混合整數線性規劃給出差分分析和線性分析中活躍S盒個數下界的評估方法.首先將差分分析和線性分析中活躍S盒傳播規律用線性不等式刻畫，目標函數為最小的活躍S盒個數，然后利用求解MILP問題的軟件進行求解，如Cplex，Gurobi等.該方法得到的下界精度較高，許多時候達到最優值，因此被廣泛用來作為評估分組密碼抵抗差分分析和線性分析能力的參考指標.

Table 5 The Minimum Number of Differential Active S -boxes Corresponding to the Different Number of Rounds表5 各迭代輪數對應的最少差分活躍S盒個數

我們將RAIN-64的最小活躍S盒與其他輕量級分組密碼在相同安全級別64 b分組128 b密鑰上進行比較，結果如表6所示(表6中所有加密都使用4 b的S盒，最大差分概率為2-2)：

Table 6 Comparison of the Minimum Number of Differential Active S -box Corresponding to the Different Number of Rounds Between RAIN-64 and Several Algorithms表6 RAIN-64與若干算法各輪最少差分活躍S盒的比較

3.2 不可能差分分析

不可能差分分析是利用概率為0的差分路徑進行密碼分析的分析方法[34].根據不可能差分密碼分析的研究現狀，一個分組密碼的最長不可能差分區分器的輪數接近于全擴散輪數的2倍.對于RAIN算法而言，當輸入差分漢明重量為1時，4輪可達到差分全擴散.

我們利用基于MILP的自動化搜索方法對RAIN的不可能差分路徑進行搜索.由己知的不可能差分分析結果來看，幾乎所有的不可能差分路徑的輸入和輸出差分模式分別只有一個活躍S盒，因此選定輸入輸出差分時，應滿足輸入、輸出只能使單個S盒活躍.搜索到RAIN算法的6輪不可能差分形式為

*000 0000 0000 0000|→*000 0000 0000 0000.

利用不可能差分區分器，可以給出縮減輪RAIN的不可能差分分析.考慮到RAIN算法的擴散性和迭代輪數，可以相信全輪RAIN針對不可能差分分析提供了足夠的安全冗余.

3.3 積分分析

積分分析可以看成是一種代數攻擊,主要構造關于若干輸入明文比特的零和區分器.可分性(division property)是目前分析對稱密碼算法積分性質最有力的工具[35-38]，同樣可以借助MILP方法方便準確的搜索算法的積分區分器.我們利用Xiang等人[36]以及Zhang等人[38]提出的生成S盒及線性層可分性不等式的方法構造了RAIN算法可分性傳播的MILP模型.文獻[36]中對S盒可分性傳播的不等式描述近乎完美.文獻[38]中利用線性層矩陣所描述的異或運算，通過構造線性不等式來建模可分性在線性擴散層中的傳播，使不等式的可行解精確地表示線性層的所有可分性傳播軌跡.因此，利用該方法描述是緊致的，得到的解是最優的，輪數是用可分性方法所得最多的.借助可分性可以搜索得到RAIN-64算法的7輪積分區分器，其中輸入63個活躍比特，輸出4個平衡比特.

7輪RAIN-64積分區分器的輸入為

0111 1111 1111 1111…1111 1111 1111 111，

其中“1”表示活躍比特位；

7輪RAIN-64積分區分器的輸出為

????BBBB????????…????????????????，

其中，“B”表示平衡比特，“?”表示未知狀態.

受限于計算能力，目前還無法斷定RAIN-64是否存在8輪積分區分器，但是我們構造出的積分區分器的輪數7和RAIN-64的總輪數30相差很大.因此我們相信RAIN-64具有足夠的抵抗積分密碼分析的安全性.

3.4 不變子空間分析

我們采用Guo等人[39]提出的不變子空間分析方法對算法S盒的不動點導致的弱密鑰存在性進行了分析.觀察算法的S盒發現有可能存在的弱密鑰空間為:{0,5,a,f}，{1,9}，{2,3}，{4,6}.

由此我們考察了算法各個部件的輸入輸出可能性.當明文、調柄和主密鑰都從以上某一個空間中取值時，密鑰編排中的密鑰加，行移位都不會改變輸出值的空間.例如明文、調柄和主密鑰都從{0,5,a,f}中取值，那么密鑰編排中密鑰加和行移位的輸出值仍在{0,5,a,f}這個空間中.比特加操作會使{0,5,a,f}，{2,3}，{4,6}這3個空間不成立，因為該操作會改變半字節的最高位.而算法所使用的輪常數使得密鑰編排經過輪常數加之后不能保持上述4個空間中的任何一個.雖然輪函數的每一步操作都使得輸入輸出空間一致，但是每一輪的密鑰都無法與明文保持在同一個空間中，所以以上4個可能的弱密鑰空間是不存在的.

4 軟硬件性能評估

4.1 軟件性能評估

RAIN算法便于軟件實現，算法可以采用基于字的基本邏輯運算實現.

RAIN算法使用的矩陣M每行有3個1，在計算輸出狀態矩陣列向量時，可以通過增加輔助變量t達到減少使用模加運算的目的.

令乘矩陣的輸入為(x0,x1,x2,x3)，輸出為(y0,y1,y2,y3)，輸出向量可由輸入向量計算得到：

(6)

若引入輔助變量t=x0?x1?x2?x3，則輸出向量可計算為

(7)

通過式(6)計算輸出列向量所需模加數量為7個，而式(7)計算輸出列向量所需模加數量為8個.

我們采用標準C實現RAIN算法,在64 b Windows(i7-7700 CPU@3.6 GHz；Win7操作系統；16 GB內存；x86_64環境；編譯器為visual studio2017 x64 release)和64 b ARM(TaiShan 200 MHz CPU@2.6 GHz；Cortex A73架構；編譯器gcc 9.1.0)環境下，對RAIN算法的加解密速率進行測試，測試結果如表7所示:

Table 7 Software Test Results of RAIN Algorithm表7 RAIN算法軟件測試結果

表7中對RAIN算法的軟件實現性能與其他提供相同安全級別的輕量級可調分組密碼SKINNY和CRAFT進行了對比，RAIN-64算法的加解密速率是較高的.

4.2 硬件性能評估

為了評估RAIN的硬件實現性能，我們針對可編程邏輯陣列(FPGA)實現平臺進行評估.使用Xilinx公司的Xilinx Kintex xc7k325tffg900-2平臺來評估RAIN在FPGA上的實現結果和性能.算法實現的加/解密運算用時包含密鑰編排運算用時.算法電路面積規模為包含加密、解密、密鑰編排運算的算法整體實現的含互連線面積.表8給出了RAIN在FPGA上的實現結果，并將RAIN算法的實現與SKINNY進行了比較，RAIN算法的加解密速率更優且面積較小.

Table 8 Performance of RAIN in FPGA表8 RAIN算法在FPGA平臺實現性能

5 結 論

本文設計了一個面向軟硬件和門限實現的輕量分組密碼算法，算法兼顧了安全性和軟硬件實現性能.RAIN算法對64 b的分組和128 b的分組，采用統一的結構都可以轉化為基于字的基本邏輯運算，這種實現方式在現代英特爾中央處理器架構下可以很方便地結合擴展指令SSE實現分組密碼的并行處理，同時對S盒的門限實現方案在抗側信道攻擊上具有優勢.