李 瑋 吳益鑫 谷大武 曹 珊 廖林峰 孫 莉 劉 亞 劉志強

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

隨著信息技術(shù)與計算機技術(shù)的不斷發(fā)展，物聯(lián)網(wǎng)正在逐漸深入到人們各個領域中.物聯(lián)網(wǎng)將所有物品通過射頻識別和紅外感應器等信息傳感設備與互聯(lián)網(wǎng)連接起來，將人、數(shù)據(jù)與實體相聯(lián)系，實現(xiàn)了人與物、物與物之間的信息交換與通信，以實現(xiàn)遍及智慧城市、智能家居、環(huán)境保護、智能交通和個人健康的智能化識別與管理[1-3].如圖1所示.輕量級分組密碼作為實現(xiàn)消息保密、數(shù)據(jù)完整性保護和實體認證的核心體制，其設計、分析與實現(xiàn)方法一直是密碼學研究的主流，在物聯(lián)網(wǎng)的安全領域發(fā)揮著重要的應用[4].

Fig. 1 The IoT scenario圖1 物聯(lián)網(wǎng)概況圖

LBlock算法是一種Feistel結(jié)構(gòu)的輕量級分組密碼算法，具有優(yōu)良的軟硬件實現(xiàn)效率，以及在處理器應用上具有良好的實現(xiàn)性能[5-6]，因而可應用于RFID標簽和其他低資源設備以保護物聯(lián)網(wǎng)的安全.前人針對LBlock算法的安全性分析主要致力于傳統(tǒng)密碼分析，包括不可能差分分析、相關密鑰不可能差分分析、截斷差分分析、零相關線性分析、積分分析、Biclique分析和側(cè)信道立方分析等多種密碼分析方法[7-9].然而，在物聯(lián)網(wǎng)環(huán)境中，單純從LBlock算法的算法結(jié)構(gòu)研究安全性已經(jīng)遠遠不夠，攻擊者不僅可以進行傳統(tǒng)密碼分析，而且可以通過電路剖析和軟件逆向分析等方式獲取密碼算法的硬件結(jié)構(gòu)和內(nèi)部編碼方法，借助異常時鐘、異常電流、微波輻射、激光照射、渦流磁場等方式干預密碼變換的正常過程使其出錯，并有可能實現(xiàn)比傳統(tǒng)密碼分析更有效地破譯，從而實現(xiàn)密碼算法內(nèi)數(shù)據(jù)的復制、篡改或偽造.人們通常把這種攻擊稱為“故障分析”[10-19].由于其成功的攻擊效果和潛在的發(fā)展前景，已經(jīng)引起了國內(nèi)外從事密碼學和微電子領域的研究學者的極大關注，并成為密碼工程和密碼分析領域發(fā)展最為迅速的方向之一.

故障分析在其自身的發(fā)展中，逐步衍生出多種攻擊方法.1997年，由Biham和Shamir提出的差分故障分析是目前分析范圍最廣、威脅最大且發(fā)展最迅速的一種攻擊技術(shù)，被廣泛應用于密碼算法的安全性分析中[20].后來，無效故障分析、碰撞故障分析、不可能故障分析、代數(shù)故障分析、中間相遇故障分析、線性故障分析以及唯密文故障攻擊等應運而生.它們充分結(jié)合了傳統(tǒng)密碼分析技術(shù)以及軟硬件實現(xiàn)，具備獨特的分析優(yōu)勢，不僅擴大了攻擊面，而且提升了威脅性，在面向現(xiàn)實的運行環(huán)境下具有更加靈活的應用前景.

在故障分析中，唯密文故障攻擊是目前唯一只需要知道錯誤密文就能進行攻擊的技術(shù)，在唯密文攻擊(ciphertext-only attack， COA)假設下，攻擊者通過導入故障得到錯誤密文，解密密文之后得到中間狀態(tài)，分析得到的中間狀態(tài)的特性，就能以低的時間復雜度和數(shù)據(jù)復雜度推導出正確的密鑰.目前，國內(nèi)外的主要研究是基于代換置換網(wǎng)絡(substitution permutation network, SPN)結(jié)構(gòu)的唯密文故障分析方法.那么，具有Feistel結(jié)構(gòu)的典型密碼算法是否能夠抵抗唯密文故障分析，已引起國內(nèi)外研究學者的廣泛關注.由此，本文提出了一種針對LBlock算法的新型唯密文故障分析方法，在較短時間內(nèi)以較少故障就能夠恢復主密鑰，為物聯(lián)網(wǎng)的安全提供了保障.

1 相關工作

Boneh等學者于1997年利用隨機故障成功破譯RSA算法，此后故障分析在評測密碼體制安全性的方法中占據(jù)了重要的位置[21].國內(nèi)外研究學者自2012年起針對LBlock算法相繼提出了故障分析方法.2012年，Zhao等學者首次使用差分故障攻擊(differential fault analysis， DFA)對LBlock算法進行攻擊，在隨機單比特故障模型下，通過在加密算法第25～31輪導入7次故障，成功恢復倒數(shù)3輪的子密鑰，進而恢復了主密鑰[22].2013年，Jeong等學者對無線傳感網(wǎng)絡環(huán)境下的LBlock算法提出了改進的差分故障攻擊方法，在隨機半字節(jié)故障模型下，通過在算法的第30輪導入7次故障成功恢復了主密鑰，同時在算法的第29輪導入5次故障也成功恢復主密鑰，進一步減少了導入故障數(shù)[23].2018年，Wei等學者對LBlock算法提出了改進的差分故障攻擊方法，在隨機半字節(jié)故障模型下，通過在算法的第27～29輪導入13.3次故障，成功恢復主密鑰，擴展了該方法的攻擊輪數(shù)[24].2013年，Chen等學者針對LBlock算法提出了積分故障分析(integral fault attack， IFA)，在隨機半字節(jié)故障模型下，通過在算法的第24輪結(jié)束時導入120次故障成功恢復了主密鑰，同時也提出了在半隨機的半字節(jié)故障模型下，通過在加密的第23輪結(jié)束時在算法的右分支導入32次故障成功恢復了主密鑰.該方法成功實現(xiàn)了對算法更深輪數(shù)進行攻擊，且能夠確定故障導入的具體位置[25].上述方法均屬于選擇明文攻擊(chosen-plaintext attack， CPA)，而本文針對LBlock提出的唯密文故障攻擊(Ciphertext-only Fault Analysis，CFA)是唯一一種在只知道錯誤密文的情況下就能對算法進行攻擊的方法.表1列出了現(xiàn)有的針對LBlock算法的故障分析方法的對比.

2013年，F(xiàn)uhr等學者基于全零字節(jié)模型、半字節(jié)模型和隨機字節(jié)模型，針對AES算法首次提出了唯密文故障攻擊方法[26].該方法在算法運行時導入隨機故障，使算法執(zhí)行某些錯誤的操作，并產(chǎn)生錯誤的密文，解密密文得到中間狀態(tài)，利用統(tǒng)計學的知識統(tǒng)計中間狀態(tài)的分布律，從而恢復最后一輪子密鑰.重復上述過程，即可恢復更多的子密鑰，直至破譯原始密鑰.針對AES算法，在隨機字節(jié)故障模型下，將故障導入在倒數(shù)第2輪的指定位置并用平方歐式距離SEI和極大似然估計MLE作為區(qū)分器，分別以320個故障和224個故障且99%的成功概率恢復出了AES算法的主密鑰.2017年，Li等學者針對LED算法提出了新型的唯密文故障分析，除了Fuhr等人提出的SEI區(qū)分器之外，還提出了擬合優(yōu)度檢驗GF作為新型區(qū)分器，又構(gòu)建了GF-SEI雙重區(qū)分器，以更少的故障數(shù)成功求得了LED的密鑰，提高了故障攻擊的效率[27].目前發(fā)表的唯密文故障分析都是針對SPN結(jié)構(gòu)的加密算法.因而，F(xiàn)eistel結(jié)構(gòu)密碼算法的安全性是目前唯密文故障分析研究的熱點.

Table 1 Comparison of Fault Analysis on LBlock表1 針對LBlock算法的故障分析對比

本文首次提出了針對Feistel結(jié)構(gòu)的LBlock算法的新型唯密文故障分析，并且以更深輪數(shù)對算法進行攻擊，實現(xiàn)了故障導入在倒數(shù)第4輪，在原有SEI區(qū)分器、GF區(qū)分器、MLE區(qū)分器和GF-SEI雙重區(qū)分器的基礎上，提出了GF-MLE雙重區(qū)分器和MLE-SEI雙重區(qū)分器統(tǒng)計分析中間狀態(tài)的分布律，以更少的故障數(shù)且99%的成功率恢復了LBlock算法80比特的密鑰，提高了故障攻擊的效率并減少了故障攻擊數(shù).表2為統(tǒng)計故障分析AES算法、LED算法和LBlock算法的唯密文攻擊結(jié)果對比.其中，Byte和Nibble分別表示字節(jié)和半字節(jié)故障模型，r表示算法的總輪數(shù).攻擊結(jié)果總結(jié)如下：

Table 2 Comparison of Ciphertext-Only Fault Attacks on a Subkey of AES,LED and LBlock表2 LBlock,LED和AES算法唯密文故障分析部分子密鑰結(jié)果對比

1) 唯密文攻擊不僅適用于SPN結(jié)構(gòu)的密碼算法，對于Feistel結(jié)構(gòu)的密碼算法同樣可以進行攻擊.

2) GF-MLE雙重區(qū)分器與MLE-SEI雙重區(qū)分器減少了故障數(shù)，提高了攻擊效率.

3) 使用這6種區(qū)分器進行攻擊的輪數(shù)在倒數(shù)第4輪.

本文首先對唯密文故障攻擊的研究現(xiàn)狀進行了探討，接著詳細介紹了LBlock算法，然后給出了故障模型與假設，詳述唯密文故障攻擊過程，最后分析攻擊的實驗結(jié)果并對本文進行總結(jié)，附錄給出了實驗的全部數(shù)據(jù).

2 LBlock算法

2.1 術(shù)語說明

記F為輪算法，SL和DL分別表示S盒混淆層和P擴散層.SL-1和DL-1分別表示S盒混淆層的逆運算和P置換的逆運算.

2.2 LBlock密碼算法

LBlock密碼算法是一種具有Feistel結(jié)構(gòu)的迭代型分組密碼，分組長度為64 b，主密鑰長度為80 b.迭代輪數(shù)為32輪.在加密算法中將消息明文分為32 b等長的左右2個分支.

該算法由3部分組成，分別為加密、解密和密鑰編排方案.其中，解密過程是加密過程的逆.下面介紹算法的加密過程.算法結(jié)構(gòu)如圖2所示.

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

LBlock算法前31輪都是左右交換操作，最后一輪不包含左右分支交換操作，每一輪變換之后的狀態(tài)表示為

Xi=F(Xi-1,eki-1)⊕(Xi-2<<<8)，

其中，2≤i≤33.在F輪函數(shù)中，首先將左分支與輪密鑰進行異或運算.其次將左分支的每半個字節(jié)經(jīng)過8個S盒進行置換變成另外一個半字節(jié).之后將經(jīng)過S混淆層之后的狀態(tài)按照特定的交換規(guī)則，變換到不同的位置.最后密文輸出為C=X32‖X33.

2.3 密鑰編排方案

密鑰編排由3個步驟組成：

1) 選取80 b的主密鑰K(ek79,ek78,…,ek0)的左側(cè)32 b密鑰(ek79ek78…ek47ek46)作為第1輪加密的輪密鑰ek0.

2) 對80 b的主密鑰進行循環(huán)左移29 b操作，將得到的80 b作為新的主密鑰.

3) 部分密鑰位更新，更新規(guī)則如下：

[ek79ek78ek77ek76]=s9[ek79ek78ek77ek76]，
[ek75ek74ek73ek72]=s8[ek75ek74ek73ek72]，
[ek50ek49ek48ek47ek46]=
[ek50ek49ek48ek47ek46]⊕[i]2，

其中，s8,s9均為4位S盒.

3 唯密文故障分析

3.1 故障模型和基本步驟

本文采用的唯密文故障分析的基本假設為：對隨機明文采用同一個密鑰進行加密，分析人員可以獲得的是密碼算法的任意錯誤密文.

LBlock算法中采用的S盒輸入與輸出均為4 b，因此本文采用隨機半字節(jié)故障模型，誘發(fā)某一輪的存儲單元發(fā)生4 b的隨機錯誤.在本節(jié)中，導入故障輪數(shù)為倒數(shù)第4輪.

唯密文故障分析的基本步驟如下：

1) 選擇隨機明文并使用同一個密鑰對其進行加密.當LBlock算法的加密過程運行到倒數(shù)第4輪時，導入隨機故障，從而獲得一組錯誤的密文.其中，故障導入既可以通過控制硬件實現(xiàn)中的異常時鐘、異常電流、微波輻射、激光照射、渦流磁場等手段對真實的密碼硬件實現(xiàn)來實現(xiàn)，也可以通過修改程序等軟件模擬技術(shù)的方式來實現(xiàn).

2) 解密錯誤密文得到中間狀態(tài).找到中間狀態(tài)、子密鑰和錯誤密文之間的關系，用關系式正確表達出來.

3) 利用構(gòu)造的區(qū)分器統(tǒng)計中間狀態(tài)值的分布律.從而恢復倒數(shù)3輪的子密鑰中的部分位.因為在故障導入之后，加密過程中的某些中間狀態(tài)值會呈現(xiàn)非均勻分布.

4) 重復上述過程，可以恢復倒數(shù)3輪的子密鑰的全部位，最后結(jié)合密鑰編排方案直至破譯原始密鑰.

3.2 具體過程

本文首次提出了用唯密文故障分析的方法對Feistel結(jié)構(gòu)算法進行破譯.針對LBlock算法，本文在前人提出的SEI區(qū)分器、MLE區(qū)分器、GF區(qū)分器和GF-SEI雙重區(qū)分器的基礎上又提出了2種新型區(qū)分器用于唯密文故障分析.具體過程如下：

1) 使用同一個密鑰對隨機明文進行加密，在運算過程中的某一輪中導入隨機半字節(jié)故障，故障導入的位置在倒數(shù)第4輪的左分支上8個半字節(jié)中的任意半個字節(jié)，根據(jù)故障導入的位置不同，則擴散路徑也各不同，從而根據(jù)不同的故障擴散路徑求得子密鑰的不同的比特值.如圖3所示，故障可以導入在X29的任意半個字節(jié)，圖中陰影表示受故障影響的半字節(jié).圖3表示故障導入在X29的第1個半字節(jié)后的故障擴散路徑.

Fig. 3 Fault diffusion path in the fifth countdown round圖3 故障導入在倒數(shù)第4輪后的擴散路徑

2) 在運算過程中，中間狀態(tài)X29的每個半字節(jié)都能用子密鑰ek31的2個半字節(jié)、ek30的1個半字節(jié)、ek29的1個半字節(jié)和錯誤密文的4個半字節(jié)來表示：

3) 通過區(qū)分器對中間狀態(tài)進行分析，計算出ek29的1個半字節(jié)、ek30的1個半字節(jié)、ek31的2個半字節(jié).對于每一個子密鑰的候選值，根據(jù)導入的故障數(shù)都能求出一組中間狀態(tài)值.選擇一個區(qū)分器，以這組數(shù)據(jù)為樣本，計算出每個密鑰候選值所對應的區(qū)分器的值，經(jīng)過比較，區(qū)分器值最大或最小所對應的候選值，即為正確子密鑰.

4) 將上述過程重復4次，即可恢復出子密鑰ek31的8個半字節(jié)、ek30的4個半字節(jié)、ek29的4個半字節(jié).上述過程重復8次，即可恢復出子密鑰ek29、ek30和ek31的全部位，之后可通過密鑰編排方案求出主密鑰.

3.3 區(qū)分器介紹

在3.2節(jié)的步驟3中所使用的區(qū)分器一共有6種，前4種是以前學者所提出的，后2種是本文所提出的新型區(qū)分器.

1) 平方歐氏距離(square euclidean imbalance， SEI)區(qū)分器

SEI區(qū)分器用于計算未知分布到均勻分布的距離，其中越不服從均勻分布的那一組樣本值所對應的密鑰候選值，即為所求的子密鑰的部分位的解.表達式為

其中，M表示半個字節(jié)的所有可能值的個數(shù)，因此M=16.γ[m]表示實際得到的中間狀態(tài)半字節(jié)值為m的樣本個數(shù)；N為導入的故障數(shù)；每個密鑰候選值都可以通過中間狀態(tài)呈現(xiàn)的不同的分布律求出對應的SEI值.計算故障導入之后實際得到中間狀態(tài)半字節(jié)值的分布與理論半字節(jié)值均勻分布的距離，即為當前樣本的SEI值.當?shù)玫降腟EI數(shù)值越大，表示這組樣本越不服從均勻分布.因此，攻擊者可以計算SEI的最大值來求出正確的候選值.

2) 擬合優(yōu)度(goodness of fit， GF)區(qū)分器

GF區(qū)分器的使用條件為已知樣本的分布律.攻擊者通過比較得到的樣本分布律是否滿足所討論模型下的理論分布律.若滿足，則可求出子密鑰的部分位.其中，4 b故障以按位與方式導入后，分布律如圖4所示，并在GF區(qū)分器中使用該分布律.區(qū)分器表達式為

其中，M表示半個字節(jié)的所有可能值的個數(shù)；Om表示實際得到的值為m的樣本個數(shù)；Hm表示在樣本總數(shù)相同的情況下，值為m中的理論個數(shù).通過區(qū)分器表達式可求出樣本分布律是否滿足理論分布律.其中，M=16，GF所求出的值越小越滿足分布，即正確候選值.

3) GF-SEI雙重區(qū)分器

GF-SEI雙重區(qū)分器結(jié)合了GF區(qū)分器與SEI區(qū)分器的優(yōu)點，先用擬合優(yōu)度檢驗篩選出滿足分布的樣本.再用SEI區(qū)分器從中尋找最優(yōu)樣本，從而恢復一定的密鑰比特.該方法進一步減少了故障數(shù)，提高了故障攻擊的效率.

4) 極大似然估計(maximum likelihood estimate， MLE)區(qū)分器

MLE區(qū)分器作為唯密文故障分析的區(qū)分器之一適用于已知樣本滿足某種概率分布的情況下，攻擊者計算得到樣本出現(xiàn)的概率，當概率最大時，即為所求的子密鑰:

5) GF-MLE區(qū)分器

為了減少故障，本文將GF區(qū)分器與MLE區(qū)分器相結(jié)合，構(gòu)建了一個GF-MLE雙重區(qū)分器，先用擬合優(yōu)度檢驗篩選出符合中間狀態(tài)值分布的所有樣本組.再用MLE區(qū)分器從中選出更優(yōu)樣本，即為正確子密鑰:

其中，k′表示GF區(qū)分器篩選之后的候選值，MLE(k′)表示每組樣本對應的MLE值；RK表示正確的候選值.從中選取MLE區(qū)分器最大的值，就是正確的子密鑰.

6) MLE-SEI區(qū)分器

為了更進一步減少故障數(shù)，本文構(gòu)建了一個MLE-SEI雙重區(qū)分器，將MLE區(qū)分器與SEI區(qū)分器結(jié)合，先用MLE區(qū)分器篩選出符合中間狀態(tài)值分布的一部分樣本，再用SEI區(qū)分器選出更優(yōu)樣本:

其中，m表示每個k″所對應的所有中間狀態(tài)值，SEI(k″)表示部分樣本分別對應的SEI值；從中選取SEI區(qū)分器最大的值，就是正確的子密鑰.

4 實驗分析

Fig. 5 The probability of recovering a partial subkey using different faults圖5 不同故障數(shù)對應恢復出部分子密鑰的概率

本實驗在普通PC機器(CPU為Inter Core I7-7700K，4.2 GHz 內(nèi)存16 GB)上使用Java語言編程進行算法的加解密實現(xiàn)和攻擊操作，利用計算機軟件來模擬故障的產(chǎn)生，從而得到錯誤密文，用編程實現(xiàn)從故障導入到唯密文攻擊再到最后得到主密鑰的全部過程.本文一共進行了1 000次實驗，記錄了恢復ek31,ek30和ek29部分比特的SEI區(qū)分器、GF區(qū)分器、MLE區(qū)分器、GF-SEI和GF-MLE雙重區(qū)分器所需的故障數(shù)和耗費時間.圖5表示不同區(qū)分器導入不同的故障數(shù)所恢復正確密鑰部分位的成功概率.其中，橫坐標軸表示導入的故障數(shù)，縱坐標軸表示恢復出正確子密鑰的成功率.圖5中有6種不同線段，分別表示使用SEI區(qū)分器、GF區(qū)分器、GF-SEI雙重區(qū)分器、MLE區(qū)分器、GF-MLE雙重區(qū)分器和MLE-SEI雙重區(qū)分器進行唯密文攻擊的結(jié)果.從實驗結(jié)果可知，在半字節(jié)隨機故障模型下，當以99%的概率恢復出過程3中的子密鑰時，SEI區(qū)分器、GF區(qū)分器、GF-SEI雙重區(qū)分器、MLE區(qū)分器、GF-MLE雙重區(qū)分器和MLE-SEI雙重區(qū)分器分別需要51,47,36,29,28和22個故障數(shù).由此分析，本文所提出的2種新型區(qū)分器可以減少攻擊時使用的故障數(shù)，并且使用MLE-SEI雙重區(qū)分器時故障數(shù)減少明顯.

圖6表示分別使用SEI區(qū)分器、GF區(qū)分器、GF-SEI雙重區(qū)分器、MLE區(qū)分器、GF-MLE雙重區(qū)分器和MLE-SEI雙重區(qū)分器破譯密鑰時間消耗圖.其中縱坐標軸表示消耗時間，以秒為單位，橫坐標表示導入故障數(shù).從實驗結(jié)果可知，在半字節(jié)的隨機故障模型下，6個區(qū)分器以99%的成功率破譯密鑰所需時間分別為130.4 s,87.4 s,50.0 s,43.2 s,37.0 s和28.4 s.不同的區(qū)分器所需時間相差較大，其中消耗時間最多的GF區(qū)分器，消耗時間是MLE-SEI消耗時間的5倍多.從結(jié)果可知，本文中所提出的雙重區(qū)分器并不會增加消耗的時間，反而減少了消耗時間.

Fig. 6 The time shown with stacked charts of using different faults圖6 不同故障數(shù)對應消耗時間的堆積柱形圖

由圖5和圖6可得，從各個區(qū)分器對算法的破譯情況進一步分析，GF區(qū)分器的攻擊效果比SEI區(qū)分器更佳，而GF-SEI雙重區(qū)分器的攻擊效果比GF和SEI區(qū)分器效果更佳，本文中所提出的2種新型區(qū)分器的攻擊效果都比之前的4種區(qū)分器的攻擊效果更佳.MLE-SEI雙重區(qū)分器所需要的導入故障數(shù)和耗費的時間比前面5種區(qū)分器均明顯減少.

5 結(jié)束語

本文提出并討論了LBock密碼算法抗唯密文故障攻擊的安全性.研究結(jié)果表明：在面向半字節(jié)的故障模型中，與原有的4種區(qū)分器相比，本文所提出的2種新型區(qū)分器所需故障數(shù)更少，故障攻擊效率更高；以LBlock為代表的Feistel結(jié)構(gòu)的密碼算法易受到統(tǒng)計故障分析的威脅，此方法有助于優(yōu)化唯密文故障攻擊方法的攻擊性能，提高故障攻擊的效率和實用性.在下一步工作中，我們將進一步深入分析雙重區(qū)分器的效率以及注入故障的分布律.