輕量級密碼LEA的唯密文故障分析

張金煜，張雨希，李 瑋

(東華大學 計算機科學與技術學院, 上海 201620)

隨著物聯網的迅速發展,越來越多的智慧車輛、智能家居以及移動便攜式設備等具有數據交換功能的智能物理對象逐漸接入互聯網,給人們的生活、學習和工作帶來了極大的便利。然而,物聯網安全仍是具有挑戰性的問題[1-2]。現階段人們通常采用基于數學函數的密碼來處理并保護未經授權的內容。然而,傳統的密碼算法一般需要較多資源來執行,難以有效在資源受限的物聯網設備中實現數據安全保護。為了能在物聯網設備上進行加解密、認證和完整性保護等,國內外研究學者設計了一系列適合物聯網的輕量級密碼算法[3-6]。

常見的輕量級密碼結構有代換置換網絡(substitution-permutation network,SPN)、Feistel、ARX等。與其他結構不同,ARX結構僅由模加、循環移位和異或3種運算組成,通過線性與非線性操作的反復迭代,對差分分析、線性分析等密碼分析方法具有較強的抵抗能力,常見的ARX結構密碼有LEA、SPECK等[5-6]。LEA輕量級密碼是2013年Hong等[6]提出的一種具有ARX結構算法的密碼,目前它不僅是國際ISO/IEC 29192-2∶2019輕量級密碼標準,也是韓國KS X 3246密碼標準。LEA密碼具有硬件吞吐量少、代碼量小等優勢,可以在物聯網等移動設備上實現高速加密。當前針對LEA密碼的分析包括差分分析、線性分析、截斷差分分析、飛去來器分析和差分故障分析等[6-11]。

故障分析利用密碼設備泄露的錯誤信息攻擊密碼系統,由Boneh等[12]于1997年提出并應用于RSA密碼的破譯。故障分析通常采用電壓毛刺和激光脈沖等方式在設備運行密碼算法時向其注入故障,并利用獲得的錯誤信息攻擊密碼。故障分析在發展歷程中衍生出唯密文故障分析、差分故障分析、代數故障分析、中間相遇故障分析等方法,對現代密碼的安全實現提出了嚴峻的挑戰[12-16]。

密碼分析根據攻擊者掌握的信息分為唯密文、已知明文、選擇明文和選擇密文,其中,唯密文攻擊要求攻擊者獲取的設備泄露信息最少,更容易實施,因此密碼算法安全性的最低要求即是面對唯密文攻擊的安全性。目前,針對LEA密碼的分析均為傳統密碼分析和差分故障分析,攻擊假設為選擇明文和已知明文攻擊,未有唯密文假設的攻擊方法。

2013年Fuhr等[16]提出基于唯密文假設的故障分析,該方法僅利用任意錯誤密文和故障注入,可以實現密碼算法的破譯。唯密文故障分析已有研究對象包括具有SPN結構的AES密碼、LED密碼,以及具有Feistel結構的Piccolo密碼等,未有ARX結構密碼的相關分析結果。

本文針對具有ARX結構的LEA密碼算法進行安全性分析,不僅完成了唯密文故障分析方法的密碼破譯,而且提出了比例距離單重區分器和比例距離-漢明重量、比例距離-極大似然雙重區分器,降低了攻擊所需的故障數量和時間。研究結果可為其他ARX結構密碼的安全實現提供參考。

1 相關工作

近年來,國內外學者對LEA密碼進行了安全性研究。2014年,Park等[10]提出了針對LEA密碼的差分故障分析方法,使用300個故障恢復了算法的完整密鑰。2015年,Jap等[11]采用隨機比特翻轉模型對LEA密碼進行差分故障分析,降低了所需故障的數量。2016年,Song等[9]提出針對LEA密碼的自動差分分析方法,對14輪的LEA密碼進行了差分分析,提高了差分概率并降低了搜索時間。同年,Zhang等[7]評估了LEA密碼對抗零相關線性分析的能力,完成了對9輪LEA密碼的攻擊。2020年,李航等[8]實現了對10輪LEA密碼的積分攻擊,計算復雜度為2120次。表1列舉了針對LEA密碼的多種分析結果。

2013年,Fuhr等[16]提出基于唯密文攻擊假設的故障分析方法,將其應用于AES密碼,利用受故障影響的中間狀態的分布特性破解密鑰,并提出平方歐氏不平衡、漢明重量和極大似然區分器。2016年,Dobraunig等[17]實現了對基于AES密碼的認證加密算法的唯密文故障分析,并能夠在多種微型設備上利用激光和時鐘毛刺成功進行故障注入。此后,Li等[18]和李瑋等[19]結合LED、Piccolo等密碼提出了擬合優度、擬合優度-平方歐氏不平衡、擬合優度-極大似然和擬合優度-漢明重量等區分器,適用于SPN和Feistel結構密碼的安全性分析。針對密鑰長度為128 bit版本的AES、LED、Piccoco和LEA密碼的攻擊效果如表2所示。

表2 AES、LED、Piccolo和LEA密碼恢復原始密鑰所需故障數量的比較

2 LEA密碼簡介

2.1 符號說明

記r為總輪數;

記K為原始密鑰,由4個32 bit數據塊組成,即K=K0‖K1‖K2‖K3;

記∑為連加操作,Π為連乘操作。

2.2 算法描述

LEA密碼是ARX結構密碼,其分組長度為128 bit,密鑰長度為128、192和256 bit,輪數分別為24、28和32。加解密過程和密鑰編排方案僅采用模加、異或和移位操作,一輪結構圖如圖1所示。

圖1 LEA密碼算法輪函數結構圖Fig.1 Round function of LEA

本文采用128bit密鑰長度的LEA密碼為分析對象。算法1給出了該版本的加密算法。解密算法以相反的子密鑰使用順序和模減操作實現,與加密算法結構類似。

算法1LEA密碼加密算法

輸入:X,RK0,RK1,…,RKi-1,r;

輸出:Y。

①X0‖X1‖X2‖X3=X;

②U=X;

③U0‖U1‖U2‖U3=U;

④ fori= 0 tor-1 do

⑧V3=U0;

⑨V=V0‖V1‖V2‖V3;

⑩U=V;

2.3 密鑰編排方案

LEA密碼的密鑰編排方案如算法2所示,其中,常數δ參照文獻[6]。

算法2LEA密碼密鑰編排方案

輸入:K0‖K1‖K2‖K3=K,δ,r;

輸出:RK0,RK1,…,RKr-1。

①T0‖T1‖T2‖T3=K0‖K1‖K2‖K3;

② fori=0 tor-1 do

③T0=(T0(δimod4<<

④T1=(T1(δimod4<<<(i+1)))<<<3;

⑤T2=(T2(δimod4<<<(i+2)))<<<6;

⑥T3=(T3(δimod4<<<(i+3)))<<<11;

⑦RKi=T0‖T1‖T2‖T1‖T3‖T1;

⑧ end for

⑨ returnRK0,RK1,…,RKr-1。

3 LEA密碼的唯密文故障分析

3.1 基本假設和故障模型

本文采用隨機單字節的故障模型,并基于唯密文假設對LEA密碼進行分析。攻擊者能夠在加密過程中對設備注入單字節故障,以“與”運算的形式作用于中間狀態。此后,攻擊者僅能獲取加密產生的隨機密文。由于“與”運算的特點,所影響的中間狀態中每個比特的均勻性被打破,因此故障注入后,單比特變化的概率情況如表3所示,在破譯過程中利用了單比特分布的不均勻性質。

表3 經故障注入后的單比特分布概率

3.2 攻擊過程

LEA密碼的唯密文故障分析具體步驟如下:

圖2 在第23輪注入單字節故障后的故障傳播路徑Fig.2 Fault propagation path of an 8-bit fault in the 23rd round

(δ0<<<3))

3.3 區分器

本文使用7種區分器對LEA密碼進行唯密文故障分析,包括已有的平方歐氏不平衡、漢明重量、極大似然和擬合優度區分器,以及本文提出的比例距離、比例距離-漢明重量和比例距離-極大似然新型區分器。

3.3.1 現有區分器

(1)平方歐氏不平衡區分器。平方歐氏不平衡(square Euclidean imbalance,SEI)區分器用于衡量總體分布與均勻分布的差距[16]。由于注入故障后的比特服從的統計分布遠離均勻分布,故當候選密鑰的區分值最大時,該候選密鑰為正確密鑰的可能性也達到最大。SEI值可表示為

式中:n為導入的故障數量;Om為中間狀態值中值為m的個數,m∈{0,1}。

(2)漢明重量區分器。漢明重量(Hamming weight,HW)區分器用于統計總體分布與零的距離[16]。漢明重量區分器計算的是一組中間狀態值的平均漢明重量,由于理論分布中漢明重量與零的距離越近的值出現概率越大,故使得HW值最小的候選密鑰為正確密鑰的可能性最大。HW值可表示為

式中:n為導入的故障數量;h(·)為漢明重量值的計算函數;sν為第v個中間狀態值;Om為中間狀態值中值為m的個數,m∈{0,1}。

(3)極大似然區分器。極大似然(maximum likelihood,ML)區分器使用中間狀態值的聯合分布率作為候選密鑰的指標,ML值越大,該候選密鑰為正確密鑰的可能性越大[16]。ML值可表示為

式中:n為導入的故障數量;sv為第v個中間狀態值,Dsv為中間狀態值為sv的理論概率;Dm為中間狀態值為m的理論概率;Om為中間狀態值中值為m的個數,m∈{0,1}。

(4)擬合優度區分器。擬合優度(goodness of fit,GF)區分器能判斷已知樣本分布率與理論分布率的擬合程度,正確密鑰對應的樣本分布與理論分布擬合程度最大[18]。GF值可表示為

式中:Om為中間狀態值中值為m的個數;Rm為中間狀態值為m的理論個數,m∈{0,1}。

3.3.2 新型區分器

(1)比例距離區分器。比例距離(ratio distance,RD)區分器統計單比特中間狀態為“0”的數量和為“1”的數量的比值,根據分布的不均勻性選擇與“1”距離最遠的一組分布,即RD值最大的一組中間狀態對應的候選密鑰即為正確密鑰。RD值可表示為

式中:O0、O1分別為中間狀態值中值為“0”和“1”的數量。

(2)比例距離-漢明重量區分器。比例距離-漢明重量(RD-HW)區分器在RD區分器的基礎上進行了改進,使用HW區分器可進一步提高正確密鑰的篩選能力,通過賦予權重來計算兩個單區分器的合并值,從而篩選出最小合并值所對應的正確密鑰。RD-HW值可表示為

RD-HW值=w0·RD值+w1·HW值

式中:w0、w1分別為RD值和HW值的權重,w0+w1=1。

(3)比例距離-極大似然區分器。比例距離-極大似然(RD-ML)區分器結合了RD區分器和ML區分器的優勢,對一組中間狀態分別求出兩者的區分器值,再通過權重分配,計算合計的區分器值,最終最大的合計區分器值所對應的候選密鑰即為正確密鑰。RD-ML值可表示為

RD-ML值=w0·RD值+w1·ML值

4 試驗分析

本試驗部署并運行于云計算服務器(Intel Core Processor (Broadwell, no TSX, IBRS), Ubuntu 21.04, 2.4GHz),采用C++編程語言模擬試驗。攻擊者生成隨機單字節故障,使用“與”操作將故障注入在指定位置,使中間狀態值產生錯誤,并收集產生的故障密文。使用SEI、HW、ML、GF、RD、RD-HW和RD-ML區分器進行分析,并統計了恢復原始密鑰的成功率、故障數量和耗時。

4.1 成功率

成功率是指故障分析者成功恢復原始密鑰的概率。由于待統計的中間狀態信息僅為單比特,即只有“0”和“1”兩種情況,且所有操作均為模加、循環移位和異或操作,因此,多個密鑰候選值會對應至同一中間狀態,得到的候選密鑰非唯一。由SEI區分器的原理可知,交換中間狀態值中“0”與“1”的個數不改變SEI值大小,同時異或操作正是這種僅改變映射關系的變換,因此若最終的中間狀態值通過與候選密鑰塊直接異或所得,則SEI區分器將無法起到區分效果。本試驗成功率計入包括正確密鑰的候選密鑰集合,元素個數不超過8個。在不同區分器下恢復LEA密碼的128 bit原始密鑰的成功率隨故障注入數量的變化如圖3所示。

圖3 各區分器恢復LEA密碼的原始密鑰的成功率隨故障注入數量的變化Fig.3 The success rate of each distinguisher to recover the secret key of LEA with the number of faults injected

從圖3可以看出,HW、ML、GF、RD、RD-HW和RD-ML區分器均可達99%及以上的成功率恢復LEA密碼原始密鑰,且新型區分器RD-ML、RD-HW和RD的成功率率先達99%,SEI區分器無法對候選密鑰進行有效分析。

4.2 故障數量

故障數量是衡量故障分析的主要指標,攻擊者所需的故障數越少,在實際物聯網環境下進行分析時越具有優勢。在恢復LEA密碼原始密鑰的成功率達99%及以上時,各區分器所需的故障注入數量如表4所示。由表4可知,新型區分器RD、RD-HW和RD-ML所需故障數較少,其中,RD-ML區分器所需故障數最少。

表4 各區分器恢復LEA密碼密鑰所需的故障數量

4.3 耗時

耗時是密碼算法攻擊中的一個衡量指標。在使用不同區分器恢復LEA密碼原始密鑰的過程中,攻擊者以99%及以上成功率恢復LEA密碼原始密鑰,耗時與注入故障數量的關系如圖4所示。

圖4 各區分器恢復LEA密碼原始密鑰的耗時隨故障注入數量的變化Fig.4 The time of each distinguisher to recover the secret key ofLEA with the number of faults injected

耗時主要由遍歷所有故障密文和候選密鑰、反向推導中間狀態值、統計中間狀態值的分布情況、利用區分器篩選正確的密鑰等所需的時間組成。試驗結果表明,除SEI區分器外,其他區分器按耗時遞減依次排序為RD-HW、RD-ML、ML、HW、GF和RD,所需的時間分別為0.771、0.745、0.174、0.142和0.139和0.133 ms,對應的故障數量為400、396、468、456、480和452個。由圖4可知,單區分器的耗時少于雙重區分器,新型單區分器RD耗時最少。

5 結 語

本文提出了針對LEA輕量級分組密碼的唯密文故障分析方法,使用了比例距離、比例距離-漢明重量和比例距離-極大似然等新型區分器,在恢復LEA密碼原始密鑰的過程中攻擊者降低了所需故障數量。研究結果表明,LEA密碼無法抵御唯密文故障攻擊。因此,建議使用者在物聯網設備中使用該密碼算法時,對密碼設備進行必要的安全防護,以降低其遭受故障攻擊威脅的程度。