基于獨立分量技術的類GIFT算法S盒逆向分析

馬向亮 李 冰 習 偉 陳 華 陳財森

1(中國科學院軟件研究所可信計算與信息保障實驗室 北京 100190)2(中國科學院大學 北京 100049)3(國家信息技術安全研究中心 北京 100084)4(南方電網科學研究院 廣州 510663)5(陸軍裝甲兵學院演訓中心 北京 100072)

盡管目前密碼學的一個基本安全假設為,密碼算法的安全性依賴于密鑰及密鑰的長度,而不是算法本身的保密性.然而在很多時候,政府或國防軍隊為了加強安全級別,或企業為了商業應用,對一些密碼算法、部件進行保密或修改.在此情況下,對帶有未知算法實現的密碼系統或模塊進行安全性評估至關重要,其中逆向分析是進行安全性評估的前提.逆向分析將直接影響到密碼算法實現測評的力度.

目前,已存在的逆向分析方法主要有數學逆向分析[1]、基于故障注入技術的逆向分析[2]和基于側信道技術的逆向分析[3]等.和數學分析方法相比,基于側信道和故障注入等旁路技術的逆向分析具有代價低、通用性強等優勢.另外,芯片解剖逆向[4]也是一種逆向分析方式,通過還原電路進行邏輯判斷、分析,然而由于周期長、代價高、可行性低等原因,該方法不適宜現在工藝發達、高度集成的加密電路芯片.

1) 數學逆向分析

在歐洲密碼年會(EUROCRYPT2001)上,文獻[1]提出了一種結構分析方法,目的是在減少輪上進行SPN機構的逆向分析.考慮到分析的高復雜度,為了建立未知操作輸入和輸出之間的關系,利用該方法通過線性和非線性操作發現多重集的特征.在2011年文獻[5]使用這種方法實現了類PRESENT算法的逆向S盒分析.

2) 基于故障注入技術的逆向分析

基于差分故障技術的逆向分析模型[6]是1997年由Biham等人最初提出的,即錯誤發生位置可以控制,但錯誤的結果未知.他們提出在一個封閉的防篡改設備(如智能卡)中可以逆向恢復未知S盒結構.2014年Clavier等人基于無效故障模型對類AES算法進行了逆向分析[7].在該模型下,即使敵手在不知道密鑰,對未保護的或帶有常用布爾掩碼和亂序防護措施的算法軟實現,依然能夠完全逆向恢復所有未知參數.

3) 基于側信道逆向分析

① 傳統側信道逆向分析

2008年文獻[8]提出基于硬件設計的未知Feistel結構的逆向分析方案,使用選擇明文攻擊的側信道攻擊可以逆向分析恢復.2010年文獻[9] 提出2種攻擊方法,一種是攻擊線性反饋寄存器結構算法的未知線性部件;另一種是恢復未知的非線性函數如S盒.2011年文獻[10]使用故障注入同時對2個常用的DES和AES算法逆向恢復未知S盒.2016年文獻[11]提出了基于線性回歸攻擊的新型側信道逆向分析方法,與之前的側信道逆向分析相比,該方法使用更少的先驗知識,并能給出更多的密碼實例.

② 基于獨立分量攻擊(ICA)的逆向分析

2017年文獻[12]提出了一種新型的側信道分析技術,即基于獨立分量技術[13](independent com-ponent analysis, ICA)的側信道分析方法.盲源分離問題是指在原始信號被混合輸出后,如何從一組被觀測的混合信號中分離出沒有被觀測到的原始信號.獨立分量技術可將側信道泄露轉化為有效的獨立分量觀測,并直接從泄露的曲線中恢復出中間輪的某個中間狀態.與傳統的側信道分析策略不同,該方法沒有采取“先猜測后確定”,而是采用了直接恢復的分析策略.該方法可用于未知密碼算法的逆向分析中.相比于已有方法,該方法對算法類型和實現條件的限制較少,攻擊復雜度較低,適用性好.文獻[12]同時給出了一個針對DES實現的攻擊實例,結果顯示該方法恢復出S盒的等價形式僅需幾百條能量跡.

綜合以上相關工作,側信道在逆向分析中具有很大的優勢,在一定程度上降低了逆向分析的復雜度,可行性較強.進一步,獨立分量技術在側信道逆向分析中的應用使得側信道逆向分析攻擊的適用性更強、復雜度更低.鑒于獨立分量技術的特點,在側信道逆向分析中,特別適用于密碼算法具有比特打亂或比特置換部件.

GIFT算法[14]是在密碼硬件與嵌入式系統會議(CHES 2017)上提出的一種輕量級分組密碼算法.自該算法提出后,已出現一些針對它的分析結果,但尚沒有針對它抵抗逆向分析的安全性評估.

本文提出了一種基于獨立分量攻擊技術的類GIFT算法S盒逆向分析方法.我們針對GIFT算法中P置換的比特置換特點,構造了有效的獨立分量觀測值,并從得到的功耗曲線中直接恢復出了第一輪P置換輸出值.因此在明文已知的情況下,S盒的內容可以恢復出來.另外我們也進行了GIFT算法的逆向分析實驗,實驗結果驗證了本方法是可行的.最后,我們針對獨立分量技術的攻擊特點給出了相關防御建議.

1 預備知識

1.1 ICA介紹

1.1.1 ICA定義

ICA是信號處理中解決盲源分離[12](blind source separation, BSS)問題的一種常用技術.利用該技術實現了雞尾酒會假設的問題,即在酒會上多人在一起講話,房間的多個麥克風將大家的聲音混合在一起經信號轉換后進行記錄,如何由記錄的混合信號還原回原始的各個獨立的信號.

ICA模型假設觀察到的混合信號變量Y=(y1,y2,…,ym)T,這些變量是由n個獨立未知源信號S=(s1,s2,…,sn)線性混合而成.因此混合信號yj和源信號S之間存在關系yj=aj,1s1+aj,2s2+…+aj,nsn,其中ai,j是未知的混合系數.混合信號也可以使用向量表示為Y=AS,A為未知混合系數矩陣.在實際信號處理過程中,通常會考慮噪聲的干擾,ICA模型修正為Y=AS+N,N為未知的不可預測噪聲,符合正態高斯分布.ICA的作用是僅僅通過觀察Y來恢復源信號S和混合系數矩陣A.

1.1.2 ICA約束與不確定性

由ICA定義可知,在混合系數矩陣A未知情況下,由Y直接恢復S是非常有挑戰性的.使用ICA方法解決這個難題,需要滿足以下3個條件：

1) 觀測信號相互獨立;

2) 觀測信號必須非高斯分布;

3) 觀察個數大于等于源信號個數 (m≥n).

由于源信號S和混合系數矩陣A未知,基于ICA模型恢復必然帶來了一些不確定結果,不確定性主要有以下2個方面：

1) 無法確定源信號的次序.這個是顯而易見的,選擇一個可逆矩陣P,由Y=AS,則Y=AP-1PS,若A和S是解,則AP-1和PS也是解.

2) 無法確定源信號的維度.任何一個源信號都可以通過乘一個標量然后在矩陣A中對應的列中除以該標量抵消掉.

1.1.3 ICA算法

ICA自從提出開始已有大量的研究成果,不同的處理算法相繼提出.按步驟分類為以下3種：

1) 批處理算法.成對數據旋轉法(Jacobi)、特征矩陣的聯合近似對角法(JADE)等;

2) 自適應算法.串行矩陣更新及其自適應算法、擴展的Infomax法等;

3) 探查性投影追蹤法.梯度算法、固定點算法(Fast ICA)等.

以上算法中Fast ICA類最常用,本文使用該算法進行實驗.

1.2 GIFT算法介紹

GIFT算法是Banik等人在CHES2017年會議上提出的SPN結構輕量級算法,是PRESENT算法的升級版,修正了PRESENT算法已知的缺點.該算法有2個版本,密鑰都是128 b,明文分組有區別分別為64 b和128 b.本文實驗使用的是64 b版本,以64 b為例介紹,但是64 b和128 b攻擊效果是一樣的.

GIFT算法一共28輪運算,每輪運算由3個步驟組成：S盒替換、比特P置換和與密鑰異或運算.

1.2.1 初始化

將加密的64位明文bn-1bn-2…b0作為一個密碼狀態S,其中b0是最低有效位.也可以將S表示為4位半字節排列,即S=ws-1‖ws-2‖…‖w0,其中s=16.密鑰128位可以表示為16位的字排列,即K=k7‖k6‖…‖k0.

1.2.2 S盒替換

S盒是GIFT算法中唯一的非線性部件,將狀態S中的每半個字節經查表替換為相應的值.wi←GS(wi),?i∈{0,…,s-1}.S盒GS如表1所示,表1中的數據使用十六進制.

1.2.3 比特置換

比特置換用來打亂原來的位順序,將第i位的狀態置換為第P(i)位,即bP(i)←bi,?i∈{0,…,n-1}.P置換表如表2所示.

1.2.4 密鑰異或

32位的輪密鑰被分為2個16位字排列,即RK=U‖V=us-1…u0‖vs-1…v0.U和V分別和密碼狀態b4i+1和b4i進行異或運算.即b4i+1←b4i+1⊕ui,b4i←b4i⊕vi,?i∈{0,…,15}.

Table 1 GIFT S Box GS表1 GIFT算法的S盒GS

Table 2 GIFT Bit Permutation表2 GIFT算法P置換表

與輪密鑰異或運算完的密碼狀態的第63,23,19,15,11,7和3位分別與1和6位輪常數進行異或運算.輪常數為C=c5c4c3c2c1c0,即

bn-1←bn-1⊕1,b23←b23⊕c5,
b19←b19⊕c4,b15←b15⊕c3,
b11←b11⊕c2,b7←b7⊕c1,b3←b3⊕c0.

1.2.5 密鑰編排和輪常數

輪密鑰RK32位由2個16位字排列組合而成,即RK=U‖V.U←k1,V←k0.密鑰每輪更新一次,k7‖k6‖…‖k0←k1>>>2‖k0>>>12‖…‖k3‖k2.其中,>>>i指的是16位字循環右移i位.輪常數使用6位線性反饋寄存器進行更新,6位初始值為0,需要先更新才能使用,更新函數為(c5,c4,c3,c2,c1,c0)←(c4,c3,c2,c1,c0,c5⊕c4⊕1).每輪常數如表3所示：

Table 3 Rounds constants表3 輪常數

2 ICA逆向分析

2.1 ICA逆向分析模型及算法

在本節中,我們詳細介紹如何將ICA用于側信道逆向恢復.依賴數據側信道泄露模型以及數據之間的獨立與非高斯性,通過深入研究算法的特定結構,構造符合ICA攻擊條件,將側信道中需要恢復的中間值數據問題轉換為ICA問題.

側信道常用的數據依賴映射模型為漢明重量模型.對于中間值數據n位的能量泄露值可以表示為

L(x)=a1x1+a2x2+…+anxn,αi∈{0,1},

其中，xi表示中間值x的二進制表示.能量泄露值的漢明重量模型滿足ICA線性混合條件.在側信道環境中,xi是比特信號,取值0或者1,服從伯努利分布,天然滿足非高斯和獨立性.在此基礎上,構造符合ICA觀測成為ICA在側信道逆向分析的關鍵,由于該問題需要結合特定算法結構進行分析解決,針對本文的GIFT算法觀測將在3節介紹.

通過結合算法結構和側信道相關理論,使得ICA算法在側信道環境中適用于逆向分析,通過觀察T個中間狀態x=(x(1),x(2),…,x(T)).由比特置換可知,每個比特之間互相獨立,可表示為xi=(xi(1),xi(2),…,xi(T)).相對應的觀測為Y=(y1,y2,…,ym)T,而每比特觀測為yi=(yi(1),yi(2),…,yi(T)).如算法1所示.

算法1. 用于側信道逆向的ICA算法[15].

輸入：T條能量跡;

① 收集m個觀測Y=(y1,y2,…,ym)T.

② 利用Fast ICA算法,得到原觀測的n個實值獨立分量(IC1,IC2,…,ICn).

while ΔL>thresholddo

E-Step:用當前的參數θ(j),計算對數似然期 望函數L(θ(j))；

M-Step:計算最大化對數似然期望函數L的 參數(θ(j+1))；

end while

電子噪聲在能量曲線采集中不可避免,噪聲會改變能量跡中的能量值,從而對逆向分析帶來了難度.一個簡單直接的辦法就是改善采集硬件條件盡可能降低電子噪聲和轉換噪聲,另外就是通過多次采集求均值、濾波技術、奇異譜分析技術等預處理技術,減少噪聲的干擾.S盒是分組密碼算法的關鍵非線性部件,它是逆向分析研究的主要分析對象.在針對S盒的逆向分析中,利用算法的特殊結構,ICA可以從能量跡上的能量值直接恢復S盒的輸出,本文提出基于ICA的逆向分析模型如圖1所示：

Fig. 1 ICA model for SCARE圖1 ICA側信道逆向分析模型

由圖1該模型下逆向分析S盒的步驟如下:

1) 選擇隨機明文,經加密算法M次加密運算,得到M條能量跡,也就得到一組M長的源信號觀測,而且相互之間是獨立的;

2) 選取S盒輸出的能量跡上的相應值觀測作為能量值.能量值依據示波器的采用率和分辨率,而且和采樣時間長短有關.需要從能量跡上識別出所需的點;

3) 使用Fast ICA算法對能量值進行攻擊,恢復出S盒輸出二進制序列;

4) 將二進制轉化為16進制數據,作為算法S盒輸出;

5) 由于S盒輸入已知,由輸入和輸出逆向分析出S盒結果.

2.2 ICA逆向分析成功率

其中,

由于ICA方法直接恢復密碼算法的某個中間值,可以使用正確信號(Xc)與ICA計算恢復信號(Xr)之間的最小距離來判斷恢復結果的有效性.隨著能量跡的增多,D(Xr,Xc)將變大,因此ICA逆向分析成功率可定義為

由D(Xr,Xc)定義可知,ICA逆向恢復成功率最小為0.5;若成功率比較大，遠遠大于0.5,則說明ICA成功恢復出S盒中間值;若成功率和0.5差不多,則說明ICA計算返回的中間值不可信.

3 GIFT算法逆向分析

本節將詳細介紹GIFT算法利用ICA技術進行逆向分析.GIFT算法主要由3部分組成,S盒置換、P置換和與輪密鑰、常數異或.因此在GIFT算法ICA觀測中,選擇比特置換作為觀測源,滿足ICA觀測需求,如圖2所示.

Fig. 2 Observations GIFT圖2 GIFT算法觀測圖

在這里我們將分析第1輪S盒輸出(它同時也是第1輪P置換的輸入)的能量泄露,由于P置換是逐比特進行的,比特之間相互獨立,這種方法特別適用于構造ICA觀測.xi=(xi(1),xi(2),…,xi(T)).相對應的觀測為Y=(y1,y2,…,ym)T,而每比特觀測為yi=(yi(1),yi(2),…,yi(T)).通過調用ICA算法,可以直接恢復出S盒的輸出值.

隨機選擇2 000組明文數據,使用GIFT算法對該數據進行加密,得到2 000條能量跡.由上面觀測圖2和先驗知識可知,第1個S 盒輸出比特置換位分別為0,17,34和51,這4個比特之間相互獨立滿足ICA觀測要求,因此能量跡上存在4個點產生的能量值作為觀測值.以這種觀測方式,得到2 000組中間值觀測,其他S盒執行類似觀測.

Fig. 3 GIFT trace with SNR=0.01圖3 信噪比為0.01的GIFT能量跡

將2 000組觀測值作為ICA逆向分析算法輸入數據進行計算.算法計算完成返回一個2 000行4列二進制數據0或1矩陣.將矩陣中每行4列二進制數據按照相應權重計算為一個16進制數據,由此得到一個2 000行向量,每個值對應為S盒輸出數據.由于2 000個明文已知,對應的S盒輸出數據已由ICA算法計算獲得,從而完成GIFT算法S盒逆向恢復.

Fig. 4 GIFT trace with SNR=0.04圖4 信噪比為0.04的GIFT能量跡

Fig. 5 GIFT trace with SNR=1圖5 信噪比為1的GIFT能量跡

由圖3和圖5能量跡可以直觀得出,噪聲對側信道分析的影響也可以從能量跡上直觀的看到,信噪比小的能量跡波動很大.信噪比為1的能量跡波動明顯小于信噪比為0.01的能量跡波動.利用比特置換P為觀測源,通過選取能量跡上4個點能量值作為ICA觀測值,通過ICA算法對上述仿真的7組不同信噪比能量跡進行逆向分析的成功率如表4所示.

Table 4 Success Rates Based on ICA for Recovering S Box with Different SNR

Fig. 6 Success rates based on ICA for recovering GIFT S box圖6 ICA逆向分析GIFT算法S盒成功率

圖6給出了GIFT算法首輪第一個S盒ICA逆向恢復結果.實驗中,沒有噪聲的觀測值恢復很快,無疑正確的恢復出了結果;信噪比在接近1以及大于1時的成功率都為1;可以看出信噪比為0.04的逆向成功率為0.757 5,效果也比較理想;但在信噪比為0.01時的成功率較低,僅有0.627 5.

實驗中,統一使用的能量跡2 000條,成功率為1的逆向分析實際上用不了2 000條.成功率小于1的隨著能量跡條數的增多,成功率會逐漸增大,但是信噪比較低的,成功率不會有大的改善.另外,本實驗沒有使用任何降噪技術,如果能量跡進行降噪預處理后再進行觀測,那么效果會得到改善,可以預計的是攻擊條數會有相應減少,信噪比太低的,成功率仍然不會有很大提高,這是由于有用信息已被噪聲淹沒掉.

4 結 論

對帶有未知算法實現的密碼系統或模塊進行逆向分析具有重要意義,側信道方法具有一定的優勢,在一定程度上降低了逆向分析的復雜度,而且可行性強.與傳統的側信道逆向分析相比,本文提出的一種基于獨立分量攻擊技術的類GIFT算法S盒逆向分析方法,不需要進行猜測和確定.我們針對該算法中P置換的比特置換特點,構造了有效的獨立分量觀測值,并從仿真得到的能量跡中直接恢復出了第一輪P置換輸出值,從而成功進行逆向分析.

本文提出的基于ICA的逆向分析方法和模型,基于P置換的比特置換特點.對于某些算法結構中,并不存在比特置換特點如國密SM4算法,相互之間不獨立,因此無法進行有效觀測.如何構建符合ICA攻擊的獨立觀測是一個難點,可以嘗試選擇特定明文或使明文與一個常數異或,使得該算法在第二輪加密時達到某些觀測值之間相互獨立.

如果算法工程采用軟實現方式,針對本文提出的基于獨立分量技術的逆向分析,使用大噪聲干擾是一種方案,該方法在一定程度上增加了該攻擊難度，如果噪聲足夠大，則信號將淹沒，信噪比很低，無法恢復出有用信號.對于硬實現,暫時沒有找到合適的線性模型,觀測值之間相互不獨立,分離信號有一定的難度,是目前該方法的局限性,因此硬實現是一種比較理想的防護方案.最后統籌考慮安全因素和性能代價，選擇沒有比特置換特點的算法,使得攻擊者無法構建符合ICA攻擊的獨立觀測.盡管該方法不夠完美,有一定的局限性,但本方法為密碼分析者和測評機構提供了一種新的思路和評估手段,對于其他未知算法的逆向分析也具有參考意義.