李 瑋,張雨希,谷大武,張金煜,朱曉銘,劉 春,蔡天培,李嘉耀
(1. 東華大學計算機科學與技術學院,上海 201620;2. 上海交通大學計算機科學與工程系,上海 200240;3. 上海市可擴展計算機與系統(tǒng)重點實驗室(上海交通大學),上海 200240;4. 上海市信息安全綜合管理技術研究重點實驗室(上海交通大學),上海 220240)
近年來,隨著5G 技術對物聯網普及的持續(xù)推動,智能家居、智能電網、智能交通等應用正給人們的工作、學習和生活帶來極大的便利. 然而,如何保護網絡中的數據免遭中斷、截獲、篡改和偽造等威脅,已成為物聯網面臨的重大安全挑戰(zhàn)[1,2]. 由于智能卡、射頻識別(Radio Frequency Identification,RFID)技術等存儲、計算能力方面的限制,物聯網中的數據難以直接采用傳統(tǒng)密碼兼顧安全性和高效性,因此,輕量級密碼一經提出,便受到國內外工業(yè)界和學術界的廣泛關注[3~9].
MANTIS 密碼是于2016 年美密會上由Beierle 等提出的一種輕量級可調分組密碼,具有低延遲、高靈活性等特點,適用于保護物聯網中的數據安全[9]. MANTIS密碼采用FX 結構和TWEAKEY 框架的設計,分組長度、調柄長度均為64 bit,密鑰長度為128 bit,用戶可以根據實際需求選擇不同的輪數及對應版本,其中輪數r≥3,對應版本記為MANTISr[9~12]. 密碼設計者Beierle等[9]分析了該密碼抵抗差分分析、線性分析、中間相遇分析、積分分析、滑動分析和不變子空間分析等的能力. 2016 年,Dobraunig 等[13]利用截斷差分的多條高概率差分特征,實現了對MANTIS5版本的截斷差分分析.2018 年,Eichlseder 等[14]提出尋找半截斷差分特征族并計算其概率的通用方法,并對MANTIS6版本進行了分析. 2019 年,Chen 等[15]提出聚類多個差分的通用自動搜索方法,給出了對MANTIS6和MANTIS7的分析結果. 同年,Ankele 等[16]提出了針對使用線性擴展可調密鑰的分組密碼的零相關攻擊,并將其應用于縮減輪的MANTIS8的分析. 2020 年,Beyne 等[17]將積分分析方法應用在MANTIS4版本密碼的安全性分析中.表1 列舉了針對MANTIS 密碼不同版本的多種密碼分析結果.
表1 針對MANTIS密碼的安全性分析匯總
與上述傳統(tǒng)密碼分析方法不同,故障分析對物聯網中密碼的實現安全進行分析.1997 年,Boneh 等[18]首次提出故障分析的概念,并將其應用于RSA 公鑰密碼的破譯. 攻擊者通??梢晕锢砩显L問運行中的設備,并在執(zhí)行算法加解密運算時,采用電壓毛刺、激光脈沖和異常溫度等方式向設備注入故障,干擾設備的工作狀態(tài),利用錯誤輸出破譯密鑰信息. 在故障分析的發(fā)展歷程中,逐漸衍生出差分故障分析、代數故障分析、線性故障分析、中間相遇故障分析以及唯密文故障分析等方法,對現代密碼的安全實現提出了嚴峻的挑戰(zhàn)[19~22].
在密碼分析中,根據攻擊者能力由弱到強將攻擊假設分成唯密文、已知明文、選擇明文和選擇密文等攻擊. 其中,唯密文攻擊對攻擊者控制使用算法設備的能力要求最弱、在實際中易實施,倘若在該假設下,攻擊者能夠成功破解密碼,則該密碼在其他攻擊假設下必將遭受更大的安全威脅. 唯密文故障分析是一種基于唯密文攻擊假設的故障分析方法,由Fuhr 等[22]于2013年提出并應用于AES 等密碼的分析中,攻擊者僅需獲取隨機故障密文,利用統(tǒng)計分析即可破譯出密鑰. 在AES 密碼的唯密文故障分析中,攻擊者可通過錯誤輸出來獲取密碼的中間狀態(tài)值,利用平方歐氏距離、漢明重量和極大似然等區(qū)分器,結合中間狀態(tài)的統(tǒng)計信息篩選出AES 密碼的原始密鑰. 2016 年,Dobraunig 等[23]提出了認證加密算法的統(tǒng)計故障分析,并在智能卡、微控制器等硬件上利用激光和時鐘毛刺實現了故障注入,成功破譯了基于AES密碼原語的認證加密算法. 近年來,李瑋等[24~26]結合LED 算法、LBlock 和SIMON 等算法提出了擬合優(yōu)度、擬合優(yōu)度-平方歐氏距離、擬合優(yōu)度-極大似然和擬合優(yōu)度-漢明重量等多種區(qū)分器,適用于代換置換網絡(SPN)結構和Feistel 結構密碼的安全性分析.
目前,國內外未有公開發(fā)表的基于TWEAKEY 框架的可調分組密碼算法的唯密文故障分析研究. 與常見的分組密碼相比,MANTIS 密碼的首尾輪具有白化密鑰,再根據密碼自身設計細節(jié)的分析,攻擊者只能通過密鑰之間的異或關系來確定密鑰的值,此外結合可調分組密碼中的調柄設計,無疑增加了密碼破譯的難度.本文針對MANTIS 密碼抵抗唯密文故障分析的安全性進行了分析,并構造了狄利克雷分布-漢明重量和狄利克雷分布-極大似然等新型區(qū)分器. 表2 總結了攻擊者使用不同區(qū)分器分析AES 密碼、LED 密碼、LBlock 密碼、SIMON密碼以及MANTIS密碼并恢復完整密鑰所需的故障數,可以看出狄利克雷分布-漢明重量和狄利克雷分布-極大似然等新型區(qū)分器,不僅能以99%及以上的成功率破譯MANTIS密碼所有版本的完整密鑰,而且降低了密鑰恢復所需注入的故障數,有效地提升了攻擊效率. 該結果為輕量級可調分組密碼的實現安全提供了有價值的參考.
表2 AES密碼、LED密碼、LBlock密碼、SIMON密碼及MANTIS密碼的唯密文故障分析結果比較
記X為明文,Y為密文,Y*為故障密文.
記K為原始密鑰,k0和k′0為白化密鑰,k1和為輪密鑰,其中,=k1⊕α,α為常數.
記r為輪數,2r為算法總輪數,其中,r∈[3,∞).
記T為原始調柄值,ti為第i輪調柄值,TKi=ti⊕k1,且其 中,r∈[3,∞),i∈[1,2r].
記RCi為 第i輪 輪 常 數,且RC2r+1-i=RCi,其 中,r∈[3,∞),i∈[1,2r].
記Ri為前向輪函數,R-1i為后向輪函數,R-1i是Ri的逆變換.
記SC,AC,ART,PC,MC,PC-1分別為信元代替、輪常數加、可調密鑰加、信元置換、列混合和逆信元置換操作.
記h為調柄的更新函數,h-1為h的逆運算.
記k1[j],[j],RC[j],ISi[j]分別為k1,,輪常 數和 第i輪ART 輸 出 的 第j個 半 字 節(jié),其 中,i∈[1,2r],j∈[0,15].
記⊕為異或操作,∥為連接操作,>>、>>>和<<<分別為右移、循環(huán)右移和循環(huán)左移操作.
輕量級可調分組密碼MANTIS 算法由Beierle 等學者在2016 年美密會上提出,采用FX 結構和TWEAKEY框架設計,分組長度和調柄長度均為64 bit,密鑰長度為128 bit. 根據輪數不同,該密碼分為不同版本,記為MANTISr,總輪數為2r輪,包括r輪前向輪和r輪后向輪,由一不帶密鑰的中間層連接,有首尾白化密鑰,如圖1所示.MANTISr的不同版本均使用相同的輪函數,64 bit數據結構采用4×4矩陣,其中,每個單元格為4 bit.
圖1 MANTIS密碼結構和輪函數
前向輪函數Ri包含如下5種基本運算.
(1)信元代替(SubCells,SC):使用以4 bit為單位的S盒進行替換,如表3所示.
表3 信元代替表
(2)輪常數加(AddConstant,AC):與輪常數進行異或操作.
(3)可調密鑰加(AddRoundTweakey,ART):與可調密鑰進行異或操作.
(4)信元置換(PermuteCells,PC):對16 個單元格進行移位.
(5)列混合(MixColumns,MC):與矩陣M相乘實現,其中,
后向輪函數中包含5 種運算:MC,PC-1,ART,AC和SC. 其中,逆信元置換表如表4所示,MANTISr的加密算法如算法1所示.
表4 逆信元置換表
算法1 MANTISr加密算法輸入:X,k0,k′0,TK,α,r輸出:Y 1:S=X⊕k0;2:S=S⊕TK0;3:FOR i=1 TO r DO 4: SubCells(S);5: AddConstant(S,i);6: AddRoundTweakey(S,TKi);7: PermuteCells(S);8: MixColumns(S);9:END FOR 10:SubCells(S);11:MixColumns(S);12:SubCells(S);13:FOR i=r TO 1 DO 14: MixColumns(S);15: InvPermuteCells(S);16: AddRoundTweakey(S,TKi,α);17: AddConstant(S,i);18: SubCells(S);19:END FOR 20:S=S⊕TK0⊕α;21:Y=S⊕k′0.
128 bit 原始密鑰K與64 bit 子密鑰k0,k1和k′0的關系如下:
其中,k0和k′0為白化密鑰,k1為輪密鑰.
本文采用半字節(jié)隨機故障模型,基本假設如下:
(1)攻擊者可在加密過程中注入隨機半字節(jié)故障,以“與”運算方式對原半字節(jié)進行注入;
(2)攻擊者能夠獲得由同一密鑰加密得到的故障密文.
圖2統(tǒng)計了半字節(jié)經隨機故障注入后的分布規(guī)律.由于比特之間的“與”運算會出現不均勻性,因此注入半字節(jié)故障后,結果會出現不均勻分布.
圖2 半字節(jié)經故障注入后的分布律
在可調分組密碼算法的設計中,調柄通常公開且已知,分為固定和不固定,分別表示每次加密時使用相同或不同的調柄值. 考慮普遍性,本文在調柄不固定時檢測MANTIS密碼各版本抵御唯密文故障分析的能力,該攻擊方法同樣適用于調柄固定時的所有情況. 攻擊過程主要包含如下3個步驟.
步驟1恢復k1的16 bit相關值和k1⊕k′0的48 bit.
攻擊者在倒數第二輪導入隨機半字節(jié)故障,并獲得故障密文. 重復上述操作,攻擊者能夠收集到一組故障密文用于分析. 攻擊者通過分析輪密鑰、白化密鑰、調柄和故障密文之間的關系,利用調柄、故障密文和猜測的子密鑰做解密運算,將故障密文恢復至導入故障時的中間狀態(tài). 對于候選密鑰比特,攻擊者逆推故障密文得到對應的中間狀態(tài)值,再利用區(qū)分器獲得最佳區(qū)分值,篩選出正確候選密鑰比特. 以注入位置在IS2r-1[0]為例,故障擴散路徑如圖3示,攻擊者利用部分候 選 子 密 鑰(k1⊕k′0)[5],(k1⊕k′0)[10],(k1⊕k′0)[15] 和k1[5]⊕k1[10]⊕k1[15],可用故障密文恢復出錯誤半字節(jié)IS2r-1[0],推導公式為
圖3 故障導入在倒數第二輪后的擴散路徑
通過遍歷IS2r-1[0]對應的216個密鑰候選值,將每個密鑰候選值對應的一組中間狀態(tài)值分別輸入到區(qū)分器中,獲取216個區(qū)分值,再將區(qū)分值進行比較,即可得出符合理論分布的一組中間狀態(tài),所對應的密鑰候選值即為正確密鑰候選值. 攻擊者通過改變故障注入位置,將故障注入在IS2r-1[1],IS2r-1[2]和IS2r-1[3]半字節(jié),可 得 到(k1⊕k′0)[1],(k1⊕k′0)[2],(k1⊕k′0)[3],(k1⊕k′0)[4],(k1⊕k′0)[7], (k1⊕k′0)[8], (k1⊕k′0)[9], (k1⊕k′0)[12],(k1⊕k′0)[14]以 及k1[1]⊕k1[4]⊕k1[14],k1[3]⊕k1[9]⊕k1[12]和k1[2]⊕k1[7]⊕k1[8]的值.
步驟2恢復k1的48 bit相關值和k1⊕k′0的16 bit.
攻擊者注入隨機半字節(jié)故障至倒數第三輪,得到故障密文. 以IS2r-2[3]作為注入位置為例,故障擴散路徑如圖4所示.
圖4 故障導入在倒數第三輪后的擴散路徑
利用已恢復的k1的相關比特值以及部分k1⊕k′0的值,攻擊者可將故障密文恢復至IS2r-2. 以IS2r-2[3]為例,用對應的待猜測子密鑰(k1⊕k′0)[0],(k1⊕k′0)[13],k1[2]⊕k1[8]⊕k1[13]和k1[0]⊕k1[10]⊕k1[15],將故障密文恢復至IS2r-2[3],推導公式可表示為
攻 擊 者 依 次 對IS2r-2[3],IS2r-2[4],IS2r-2[13]和IS2r-2[10]半字節(jié)進行故障注入,每次注入恢復的部分子密鑰用于后續(xù)的密鑰恢復. 重復上述攻擊步 驟,攻 擊 者 可 以 得 到(k1⊕k′0)[6],(k1⊕k′0)[11],k1[7]⊕k1[8]⊕k1[13],k1[0]⊕k1[5]⊕k1[15],k1[2]⊕k1[7]⊕k1[13],k1[3]⊕k1[6]⊕k1[12],k1[1]⊕k1[11]⊕k1[14],k1[3]⊕k1[6]⊕k1[9],k1[1]⊕k1[4]⊕k1[11],k1[0]⊕k1[5]⊕k1[10],k1[4]⊕k1[11]⊕k1[14]和k1[6]⊕k1[9]⊕k1[12]的值.
步驟3恢復原始密鑰K.
攻擊者利用步驟1、步驟2 可以恢復k1的64 bit相關值以及k1⊕k′0的16 個半字節(jié)值,可得到關于k1的16 個半字節(jié)的方程組和k1⊕k′0的值,具體如下:
其中,bu為已恢復的k1的相關值,u∈[0,15]. 攻擊者解出方程組獲得k1后,再與k1⊕k′0的值進行異或操作,可得到k′0的值,即k′0=k1⊕(k1⊕k′0).
最后,攻擊者通過密鑰編排方案恢復MANTIS各版本的原始密鑰,即
本節(jié)使用平方歐氏距離、漢明重量等7種現有區(qū)分器及2 種新型區(qū)分器對MANTIS 密碼進行唯密文故障分析.2013 年,Fuhr 等[22]首次提出平方歐式距離、漢明重量和極大似然區(qū)分器對AES 密碼進行唯密文故障分析. 近年來,李瑋等[24,26]針對LED等密碼提出了擬合優(yōu)度、擬合優(yōu)度-平方歐氏距離、擬合優(yōu)度-極大似然和擬合優(yōu)度-漢明重量等區(qū)分器,降低了故障注入數. 本節(jié)提出了狄利克雷分布-極大似然和狄利克雷分布-漢明重量新型區(qū)分器. 各區(qū)分器的原理及取值如表5所示.新型區(qū)分器原理如下所述.
表5 各區(qū)分器對比
(1)狄利克雷分布-極大似然區(qū)分器
狄利克雷分布(Dirichlet Distribution,DD)區(qū)分器通過計算在理論分布下中間狀態(tài)值得到的概率篩選出一組最符合理論分布的狀態(tài),概率值DD 越越大,候選密鑰為真實密鑰的可能性越大.DD值可表示為
狄利克雷分布-極大似然(Dirichlet Distribution-Maximum Likelihood,DD-ML)區(qū)分器是結合DD 區(qū)分器和ML 區(qū)分器的雙重區(qū)分器,攻擊者依次計算DD 值和ML 值,從DD 區(qū)分值較佳結果中取ML 的最大值,即為最可能的候選密鑰,ML計算式為
其中,n為導入故障數,ISv為第v個中間狀態(tài)值,O[m]表示中間狀態(tài)值中值為m的個數,D[m]表示中間狀態(tài)值為m的理論概率.
(2) 狄利克雷分布-漢明重量區(qū)分器
狄利克雷分布-漢明重量(Dirichlet Distribution-Hamming Weight,DD-HW)區(qū)分器首先計算在理論分布下中間狀態(tài)值得到的概率,得到較大概率對應的一組中間狀態(tài),然后在這一組中間狀態(tài)中進行進一步的篩選,以減少所需故障數.攻擊者首先利用DD 區(qū)分器篩選出一組高概率值的候選值,計算式為
然后利用HW區(qū)分器篩選出最小值,計算式為
其中,n為導入故障數,ISv為第v個中間狀態(tài)值,hw為漢明重量值的計算函數,O[m]表示中間狀態(tài)值中值為m的個數,D[m]表示中間狀態(tài)值為m的理論概率.
本實驗在Intel Core Processor(Broadwell,no TSX,IBRS),Ubuntu 21.04,2.4GHz計算機服務器上運行,采用C++編程語言實現對MANTIS 密碼的唯密文故障分析. 攻擊者采用計算機軟件生成半字節(jié)隨機故障并模擬故障注入,使用“與”運算的方式對原中間狀態(tài)的指定位置產生影響,再使用各區(qū)分器恢復原始密鑰. 由于MANTISr的不同版本僅有加密輪數的區(qū)別,輪函數和密鑰編排均相同,使得從故障密文倒推至注入故障的中間狀態(tài)的過程也相同,因此相同區(qū)分器恢復MANTIS密碼各版本原始密鑰的效果相同.
本實驗以MANTIS8為例,利用SEI,HW,ML,GF,GF-SEI,GF-ML 和GF-HW 區(qū)分器以及DD-ML,DD-HW 新型區(qū)分器進行統(tǒng)計分析. 在攻擊過程中,每次統(tǒng)計分析可恢復16 bit 子密鑰的信息,在倒數第二輪和倒數第三輪先后分別注入半字節(jié)故障,用于恢復128 bit原始密鑰. 圖5、圖6和表6展示了針對MANTIS8版本的攻擊結果,所有結果均為1000 次實驗后的統(tǒng)計結果.
圖6 各區(qū)分器恢復16 bit密鑰的耗時
在故障攻擊中,攻擊算法需要注入的故障數越少,在實際硬件實現時越具有優(yōu)勢. 表6 給出了恢復MANTIS8完整密鑰且成功率達到99%及以上時,各區(qū)分器所需的故障注入數. 本文提出的DD-HW 和DDML 雙重區(qū)分器分別需要392 個和396 個故障數,與現有區(qū)分器相比,所需故障數較少. 其中,SEI區(qū)分器對每一個中間狀態(tài)值統(tǒng)計所得的個數采用了相同的處理系數,故中間狀態(tài)值與統(tǒng)計所得個數間映射關系的改變不會影響區(qū)分值大小,同時,異或操作會導致這個映射關系發(fā)生變化. 因此,如果待分析的中間狀態(tài)值是通過故障密文與待猜測密鑰候選值直接異或所得的,那么SEI區(qū)分器無法起到區(qū)分效果.
表6 各區(qū)分器恢復完整密鑰所需故障數、時間復雜度和數據復雜度
成功率指成功恢復密鑰的次數占實驗次數的比例. 在故障分析中,若候選密鑰經區(qū)分器篩選后得到唯一候選密鑰且該候選密鑰與真實密鑰值相同,那么該次密鑰恢復實驗成功. 恢復完整密鑰需進行兩階段攻擊,依次在加密的倒數第二輪和倒數第三輪分別注入故障,由于注入故障輪數不同,故障對加密過程的影響不同,導致區(qū)分器恢復密鑰的成功率不同,因此圖5(a)和(b)分別展示在倒數第二輪和倒數第三輪注入故障時不同區(qū)分器的攻擊效果,即子密鑰恢復成功率與導入故障個數的關系,其中橫坐標為故障注入數,縱坐標為子密鑰恢復成功率. 為了減少第一階段攻擊對第二階段攻擊的實驗數據的影響,第二階段攻擊的實驗數據在第一階段攻擊待恢復子密鑰已知的基礎上進行統(tǒng)計. 從數據可以看出,HW,ML,GF,GF-SEI,GF-ML,GF-HW,DD-ML 和DD-HW 區(qū)分器均可以99%及以上的成功率恢復MANTIS密碼原始密鑰. 鑒于SEI 區(qū)分器成功率最高不超過20%,實際攻擊時不建議采用SEI區(qū)分器.
圖5 各區(qū)分器恢復16 bit密鑰的成功率
時間復雜度和數據復雜度是衡量密碼破譯的時間量和數據量的重要指標,其計算式分為
和
其中,f1和f2分別為兩階段攻擊中注入的故障數,ω為不同區(qū)分器對應的復雜度系數. 表6 給出了不同區(qū)分器以不小于99%的成功率恢復MANTIS8完整密鑰所需的時間復雜度和數據復雜度,新型雙重區(qū)分器DDML 和DD-HW 的時間復雜度以及數據復雜度均小于已有區(qū)分器.
在密碼算法的攻擊中,耗時越少則攻擊的時間成本越小. 圖6(a)和(b)分別表示在不同區(qū)分器下,在兩階段攻擊中恢復子密鑰的耗時與故障注入數的關系.其中橫坐標表示注入的故障個數;縱坐標表示耗時,具體為遍歷候選密鑰和故障密文、統(tǒng)計中間狀態(tài)的分布律、計算區(qū)分值并篩選正確密鑰的總時間. 實驗結果表明,除SEI 區(qū)分器外,使用HW,ML,GF,GF-SEI,GFML,GF-HW,DD-ML和DD-HW區(qū)分器以99%及以上的成功率恢復出完整密鑰消耗的最少時間分別483.6 ms,462.8 ms,756.0 ms,564.8 ms,577.6 ms,554.8 ms,500.4 ms,490.8 ms. 其中,DD-ML 和DD-HW 新型區(qū)分器恢復完整密鑰的耗時次于HW 和ML 單區(qū)分器,但在所有雙重區(qū)分器比較中,新型區(qū)分器耗時最少.
因此,結合圖5、圖6 和表6 的統(tǒng)計分析,新型區(qū)分器DD-ML 和DD-HW 恢復MANTIS 完整密鑰的成功率可達99%及以上,所需的故障數、時間復雜度、數據復雜度均達到最優(yōu),耗時低于現有雙重區(qū)分器.
本文提出了針對MANTIS密碼的唯密文故障分析方法,采用狄利克雷分布-漢明重量和狄利克雷分布—極大似然等新型區(qū)分器,不僅能以99%及以上的成功率破譯密碼,而且降低了故障注入數,提升了攻擊效率. 研究表明,MANTIS 密碼易受到唯密文故障攻擊的威脅,因此,在物聯網中的智能卡、RFID 等設備中使用該密碼算法時,建議實施必要的舉措對密碼最后若干輪加以防護,以減少受到該類分析的威脅. 下一步工作將結合MANTIS密碼的內部更深輪進行唯密文故障分析研究.