物聯網中MIBS輕量級密碼的唯密文故障分析

李 瑋 曹 珊 谷大武 李嘉耀 汪夢林 蔡天培 石秀金

1(東華大學計算機科學與技術學院 上海 201620) 2(上海交通大學計算機科學與工程系 上海 200240) 3(上海市可擴展計算與系統重點實驗室(上海交通大學) 上海 200240) 4(上海市信息安全綜合管理技術研究重點實驗室(上海交通大學) 上海 200240)

物聯網是物物相連的網絡，它通過信息傳感設備，按照某種協議把任何物品接入互聯網，進行信息交換和通信，以實現對物品的智能化識別、定位、跟蹤、監控和管理，廣泛應用于智能家居、食品安全、智能電網、智慧醫療、智能交通、精準農業、智能環保、智慧物流、智能零售和公共安全等領域中[1-5].物聯網的普及為人們的工作、學習和生活帶來了極大的便利，但是，與傳統的網絡相比，它遭受到更大的安全風險.原因在于物聯網中使用的終端設備存儲和計算能力有限，不能有效地使用傳統的密碼算法實現信息的保密性、完整性和認證性.為了保護物聯網中的數據免遭截獲、篡改和偽造等威脅，國內外學者設計了具有一系列功耗低、吞吐量小、執行效率高和安全性能佳的輕量級密碼，包括MIBS密碼、LBlock密碼、Simon密碼和Simeck密碼等[6-9].

2009年Lzadi等學者[6]于密碼學和網絡安全(CANS)會議上提出了MIBS輕量級分組密碼，該密碼具有典型的Feistel結構，分組長度為64 b，密鑰長度分為64 b和80 b，具有功耗低、存儲占用小等優點，適合在資源受限的RFID設備上使用.MIBS算法可以進行抵抗差分攻擊、線性攻擊、不可能差分攻擊、積分攻擊、中間相遇攻擊和碰撞攻擊等分析[10-15].

在物聯網環境中，RFID等設備易受到故障分析(fault analysis, FA)的攻擊.1996年Boneh等學者[16-18]針對RSA密碼系統首次提出故障分析，以較低的攻擊代價破譯了密鑰，引起了國內外研究學者的廣泛關注.1997年Biham等學者[18]提出了差分故障分析(differential fault analysis, DFA)，并成功破譯了DES密碼.攻擊者通過利用強磁場、電源電壓毛刺、時鐘毛刺、激光干擾、外界溫度變化等方式對密碼模塊執行過程中的中間狀態進行擾亂，從而獲得錯誤的密文，并結合其他有效信息來破譯主密鑰.在物聯網環境中，RFID等設備易受到這種攻擊.

在故障攻擊的實現中，基本假設至關重要，分為選擇明文攻擊(chosen plaintext attack， CPA)和唯密文攻擊(ciphertext-only attack， COA).例如差分故障攻擊、線性故障攻擊、積分故障攻擊、不可能差分故障攻擊等的基本假設均為選擇明文攻擊，即攻擊者可以選擇獲取任意明文的密文及相對應的錯誤密文.而僅有唯密文故障攻擊的基本假設為唯密文攻擊，即攻擊者可以獲得任意密文或錯誤密文.在唯密文攻擊假設下，攻擊者的能力最弱，一旦獲得成功，將對密碼系統的安全造成巨大威脅.因此，分析輕量級密碼算法能否抵抗唯密文攻擊假設下的故障攻擊，對于物聯網安全具有十分重要的意義.

目前，國內外還未有公開發表關于MIBS輕量級密碼算法是否抵抗唯密文故障攻擊方法的結果.本文深度剖析了MIBS密碼的內部結構和運算，使用唯密文故障攻擊對其進行了安全性分析，不僅實現了已有的“與”故障模型下的平方歐氏距離等7種區分器，而且提出了新型的雙重“與”故障模型、新型Parzen-HW雙重區分器和Parzen-HW-MLE三重區分器.結果表明，使用新型故障模型和區分器不僅提高了故障攻擊效率，而且降低了故障攻擊需要的故障注入數.該方法的提出，對于保護物聯網等環境中的數據傳輸安全、增強密碼系統的自主開發和分析能力，無疑都具有重要的現實意義和價值.

1 相關工作

自MIBS輕量級密碼提出后，國內外研究學者相繼使用差分攻擊、線性攻擊、不可能差分攻擊、積分攻擊、中間相遇攻擊和碰撞攻擊等傳統密碼分析方法對其安全性進行了分析.如表1所示，這些結果檢測了MIBS密碼縮減輪的安全性.

在故障攻擊分析MIBS密碼方面，研究學者通常使用選擇明文假設下的差分故障攻擊，完成破譯MIBS密碼全部輪.2011年王素貞等學者[19]在加密部分的最后2輪分別注入32 b故障，將密鑰搜索空間降低到221.7.2018年王永娟等學者[20]基于S盒差分傳播特性，在加密部分的最后一輪注入4 b故障，進而恢復最后一輪密鑰的47 b，所需要的時間復雜度為217.2019年Gao等學者[21]通過計算S盒的差分分布的統計規律，在最后3輪中分別注入4 b故障，恢復主密鑰的時間復雜度僅為22.本文分析了在唯密文攻擊假設下，MIBS密碼抵抗唯密文故障攻擊的安全性.表2給出了針對MIBS算法的故障分析對比.

Table 1 Classical Cryptanalysis of MIBS表1 針對MIBS密碼的傳統密碼分析

Table 2 Comparison of Fault Analysis of MIBS表2 針對MIBS算法的故障分析對比

2013年Fuhr等學者[22]首次針對AES密碼提出了唯密文故障攻擊方法，結合平方歐氏距離、漢明重量和極大似然估計等區分器，僅需要320,288和224個故障注入，可以恢復最后一輪密鑰.2017年李瑋等學者[23]將唯密文故障攻擊應用在LED密碼上，并新增了擬合優度區分器和擬合優度—平方歐氏距離雙重區分器，用于降低所需的故障注入數.以上2種分析方法都是針對SPN結構的密碼.2018年李瑋等學者針對Feistel結構的LBlock輕量級密碼，新增了雙重區分器，提高了故障攻擊的效率[24].從目前的研究可以看出，改進的唯密文故障攻擊的方法均是通過優化選擇單區分器和雙重區分器來降低故障注入數.結合物聯網環境和MIBS密碼的設計特點，本文提出的唯密文故障攻擊不僅增加了新型的雙重區分器和三重區分器，而且構建了新型的雙重“與”故障模型，進一步提高了故障導入效率，減少了故障注入數.表3總結了AES算法、LBlock算法和MIBS算法的唯密文故障攻擊所需故障注入的結果對比.

Table 3Comparison of Fault Injections to Decrypting theLast Subkey of AES, LBlock and MIBS

表3 破譯AES，LBlock和MIBS密碼最后一輪子密鑰所需故障數對比

DistinguisherAESLBlockMIBSANDANDANDDouble ANDSEI32012410846GF11411038HW2887428MLE224927028GF-SEI708636GF-MLE909234MLE-SEI589234Parzen-HW6826Parzen-HW-MLE6424

2 MIBS算法介紹

2.1 符號說明

Fig. 1 The structure of MIBS圖1 MIBS算法的結構

2.2 MIBS密碼簡介

MIBS密碼的分組長度為64 b，MIBS-64版本和MIBS-80版本分別對應密鑰長度為64 b,80 b，其迭代輪數均為32輪.算法由加密、解密和密鑰編排3部分組成.解密與加密相同，所使用的子密鑰順序相反.結構如圖1所示：

輪函數F由子密鑰加、非線性層和線性層組成，表示為

Ll+1=F(Ll,kl)⊕Rl=
PL(ML(SL(Ll⊕kl)))⊕Rl，
Rl+1=Ll，

其中，SL為非線性層，ML和PL分別為線性層的混淆變換和置換.ML表達式為

Fig. 2 The distribution of a nibble after fault injections圖2 半字節被影響后的分布律

MIBS的加密部分如算法1所示.

算法1.MIBS密碼的加密算法.

輸入：明文X、密鑰K；

輸出：密文Y.

①L1‖R1=X;

② forl=1 to 32

③kl=Keyschedule(K);

④ end for

⑤ forl=1 to 32

⑥Ll+1=PL(ML(SL(Ll⊕kl)))⊕Rl;

⑦Rl+1=Ll;

⑧ end for

3 唯密文故障分析

3.1 基本假設和故障模型

本文使用的基本假設為唯密文攻擊，即攻擊者可以利用同一個密鑰對多組隨機明文進行加密，并在加密過程中導入任意故障，從而獲得多組相對應的錯誤密文.

唯密文故障攻擊中常使用的是“與”故障模型，在此基礎上，本文構建了雙重“與”故障模型，即

圖2統計了上述故障模型的半字節分布，圖2(b)雙重“與”模型中的半字節分布比圖2(a)“與”模型中的半字節分布差異更大.

3.2 攻擊步驟

針對MIBS算法，本文驗證了前人提出的SEI,HW,ML,GF,GF-SEI,GF-MLE和MLE-SEI等區分器,并提出了2種新型區分器Parzen-HW和Parzen-HW-MLE用于唯密文故障分析，均可以破譯MIBS算法，具體有3個步驟.

Fig. 3 Faulty diffusion path in the last three rounds圖3 最后3輪的故障擴散路徑

素琴即無弦琴，該典與陶淵明相關，《晉書·隱逸傳·陶潛》說陶潛：“性不解音，而畜素琴一張，弦徽不具，每朋酒之會，則撫而和之曰：‘但識琴中趣，何勞弦上聲’”[4]。陸游認為彈琴能夠悅性靈、養心、排悶，“舉酒和神氣，彈琴悅性靈”[3]831，“琴調養心安澹泊，爐香挽夢上青冥” [3]262，“援琴排遣悶，合藥破除閑”[3]730。

通過中間狀態、子密鑰和錯誤密文之間的關系式可以求出k32的第1，2，4，5，6個半字節的值，由此可推出R32與k32的20位相關，依次可以求解k32的20個位.同步驟1，在第7個半字節導入故障，即可求得k32剩余12個位.

步驟3. 與步驟2類似，可以推出最后3輪所有子密鑰，通過密鑰編排方案即可恢復出主密鑰.

3.3 區分器介紹

本文使用了9種區分器對MIBS密碼進行分析，其中最后2種是本文所提出的新型區分器.

1) 平方歐氏距離區分器

2) 擬合優度區分器

擬合優度(goodness of fit， GF)區分器[23]是在已知樣本分布率的情況下，通過計算一組樣本與給定分布的擬合程度，從而找出正確的子密鑰.圖2給出了“與”、雙重“與”故障模型下的理論分布.樣本與已知分布率的擬合相似度越大，即誤差越小，所對應的密鑰候選值為正確子密鑰的可能性越大，因此當GF取值最小時，所對應的密鑰猜測值為正確子密鑰：

3) 漢明重量區分器

漢明重量(Hamming weight， HW)區分器[22]是計算中間狀態和等長非零字符串的漢明距離，導入故障后會打破中間狀態0,1的平衡，

4) 極大似然估計區分器

極大似然估計(maximum likelihood estimate， MLE)區分器[22]是通過利用觀察到的樣本信息，反推最具有可能出現此樣本結果的模型參數值.通過建立似然函數，計算每一組中間狀態理論應該出現概率的乘積：

5) 擬合優度——平方歐氏距離區分器

擬合優度——平方歐氏距離(GF-SEI)區分器[23]先利用擬合優度算法過濾一部分明顯不符合理論分布的樣本所對應的密鑰候選值，再利用平方歐氏距離進一步計算選擇出最優的樣本.該區分器的使用可以提高攻擊效率，減少需要的故障注入數：

6) 擬合優度—極大似然估計區分器

擬合優度—極大似然估計(GF-MLE)區分器[24]先利用GF區分器挑選出與理論分布最接近的部分密鑰候選值，再使用MLE區分器計算挑選出來的樣本對應的概率，達到減少故障注入數和提高攻擊效率的目的：

7) 極大似然估計—平方歐氏距離區分器

極大似然估計—平方歐氏距離(MLE-SEI)區分器[24]先利用MLE區分器篩選出密鑰候選值，再計算出這些值對應樣本的平方歐氏距離，從而達到減少故障注入數：

8) 窗估計—漢明重量區分器

窗估計—漢明重量(Parzen-HW)區分器是本文提出的一種新型雙重復合區分器.Parzen窗估計是一種無參估計，由于Parzen區分器不需要假設數據分布，所以具有通用性的優點，但是要準確地估計窗函數需要大量的樣本，因此使用Parzen區分器理論上需要更多的故障注入.通過結合HW區分器可以有效地避免上述問題，具體方法為先利用Parzen方法過濾大部分密鑰候選值，然后再使用HW方法作精確篩選：

9) 窗估計—漢明重量—極大似然估計區分器

現有的區分器均為單區分器和雙重區分器，本文提出的窗估計—漢明重量—極大似然估計(Parzen-HW-MLE)區分器是一種新型的三重區分器，有效地發揮了3種單區分器的優點，進一步提高了攻擊效率，減少故障注入數.首先，攻擊者構造窗函數，使用Parzen過濾大量密鑰候選值

然后，結合漢明重量區分器進一步篩選：

4 唯密文故障破譯MIBS密碼的實驗分析

實驗使用的PC配置為Intel Core I5-4200M，實驗平臺為Eclipse.使用Java編程語言軟件模擬攻擊環境.本文共進行了1 000次實驗，均以超過 99%的成功概率破譯MIBS-64版本和MIBS-80版本的密鑰.附錄A列出了實驗所有數據.

圖4(a)(b)表示在“與”、雙重“與”故障模型下，所有區分器恢復子密鑰的20 b所需要的成功概率和所需故障注入數的關系，其中橫坐標表示故障注入數，縱坐標表示攻擊成功率.不同顏色表示SEI,GF,HW,MLE,GF-SEI,GF-MLE,MLE-SEI,Parzen-HW和Parzen-HW-MLE等區分器的變化趨勢.最終每一種區分器恢復子密鑰的成功概率不小于99%.因而，在“與”、雙重“與”故障模型下，攻擊者恢復出最后一輪子密鑰最少需要的故障注入為64個、24個，破譯主密鑰最少需要的故障注入為192個、72個.由表3可知，新型區分器Parzen-HW和Parzen-HW-MLE所需的故障注入數均較少.

圖5(a)(b)表示在“與”、雙重“與”故障模型下，使用所有區分器恢復子密鑰20 b需要消耗的時間堆積圖和故障注入數的關系.其中，橫坐標表示故障注入數，縱坐標表示需要消耗的時間堆積，不同顏色線條分別代表各區分器.圖6表示在相同區分器中，“與”、雙重“與”故障模型下恢復出子密鑰的平均時間對比圖.其中，橫坐標表示區分器，縱坐標表示時間，不同色塊分別代表各故障模型.由圖5和圖6可知，SEI區分器和GF區分器所耗時間最多.和原有的“與”故障模型相比，雙重“與”故障模型下各區分器需要的時間都大幅度減少.

Fig. 4 Comparison of success probability of recovering 20 b in two fault models圖4 2種故障模型下恢復出20 b的成功率對比

Fig. 5 Comparison of time of recovering 20 b using two fault models圖5 2種不同故障模型下恢復20 b所需的時間對比

Fig. 6 Comparison of average time of recovering 20 b圖6 恢復20 b所需的平均時間對比

在雙重“與”故障模型中，所有區分器可以以較短時間和較少故障注入破譯子密鑰.并且，雙重區分器Parzen-HW和三重區分器Parzen-HW-MLE在故障注入和時間消耗上均少于原有的區分器，因而，使用新型故障模型和新型區分器有效地提升了提高了故障攻擊的效率，降低故障注入數和攻擊時間.

5 結束語

本文提出并討論了MIBS密碼算法抵抗唯密文故障攻擊的安全性.仿真結果表明：以MIBS密碼為代表的Feistel結構密碼算法易受到唯密文故障分析的威脅，在新型雙重“與”故障模型下，新型Parzen-HW二重區分器和Parzen-HW-MLE三重區分器可以以較少的故障注入數、較低的時間花費破譯MIBS密碼，該方法的提出優化了唯密文故障攻擊方法的效率和性能，為物聯網中輕量級密碼算法的安全性分析提供了參考.