物聯(lián)網(wǎng)中MIBS輕量級密碼的唯密文故障分析

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

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

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

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

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

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

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

1 相關(guān)工作

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

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

Table 1 Classical Cryptanalysis of MIBS表1 針對MIBS密碼的傳統(tǒng)密碼分析

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

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

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

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

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

2 MIBS算法介紹

2.1 符號說明

Fig. 1 The structure of MIBS圖1 MIBS算法的結(jié)構(gòu)

2.2 MIBS密碼簡介

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

輪函數(shù)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 半字節(jié)被影響后的分布律

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 基本假設(shè)和故障模型

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

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

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

3.2 攻擊步驟

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

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

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

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

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

3.3 區(qū)分器介紹

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

1) 平方歐氏距離區(qū)分器

2) 擬合優(yōu)度區(qū)分器

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

3) 漢明重量區(qū)分器

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

4) 極大似然估計區(qū)分器

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

5) 擬合優(yōu)度——平方歐氏距離區(qū)分器

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

6) 擬合優(yōu)度—極大似然估計區(qū)分器

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

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

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

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

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

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

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

然后，結(jié)合漢明重量區(qū)分器進一步篩選：

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

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

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

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

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

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

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

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

5 結(jié)束語

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