張金煜，張雨希，李 瑋

(東華大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 上海 201620)

隨著物聯(lián)網(wǎng)的迅速發(fā)展,越來越多的智慧車輛、智能家居以及移動(dòng)便攜式設(shè)備等具有數(shù)據(jù)交換功能的智能物理對(duì)象逐漸接入互聯(lián)網(wǎng),給人們的生活、學(xué)習(xí)和工作帶來了極大的便利。然而,物聯(lián)網(wǎng)安全仍是具有挑戰(zhàn)性的問題[1-2]?，F(xiàn)階段人們通常采用基于數(shù)學(xué)函數(shù)的密碼來處理并保護(hù)未經(jīng)授權(quán)的內(nèi)容。然而,傳統(tǒng)的密碼算法一般需要較多資源來執(zhí)行,難以有效在資源受限的物聯(lián)網(wǎng)設(shè)備中實(shí)現(xiàn)數(shù)據(jù)安全保護(hù)。為了能在物聯(lián)網(wǎng)設(shè)備上進(jìn)行加解密、認(rèn)證和完整性保護(hù)等,國(guó)內(nèi)外研究學(xué)者設(shè)計(jì)了一系列適合物聯(lián)網(wǎng)的輕量級(jí)密碼算法[3-6]。

常見的輕量級(jí)密碼結(jié)構(gòu)有代換置換網(wǎng)絡(luò)(substitution-permutation network,SPN)、Feistel、ARX等。與其他結(jié)構(gòu)不同,ARX結(jié)構(gòu)僅由模加、循環(huán)移位和異或3種運(yùn)算組成,通過線性與非線性操作的反復(fù)迭代,對(duì)差分分析、線性分析等密碼分析方法具有較強(qiáng)的抵抗能力,常見的ARX結(jié)構(gòu)密碼有LEA、SPECK等[5-6]。LEA輕量級(jí)密碼是2013年Hong等[6]提出的一種具有ARX結(jié)構(gòu)算法的密碼,目前它不僅是國(guó)際ISO/IEC 29192-2∶2019輕量級(jí)密碼標(biāo)準(zhǔn),也是韓國(guó)KS X 3246密碼標(biāo)準(zhǔn)。LEA密碼具有硬件吞吐量少、代碼量小等優(yōu)勢(shì),可以在物聯(lián)網(wǎng)等移動(dòng)設(shè)備上實(shí)現(xiàn)高速加密。當(dāng)前針對(duì)LEA密碼的分析包括差分分析、線性分析、截?cái)嗖罘址治觥w去來器分析和差分故障分析等[6-11]。

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

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

2013年Fuhr等[16]提出基于唯密文假設(shè)的故障分析,該方法僅利用任意錯(cuò)誤密文和故障注入,可以實(shí)現(xiàn)密碼算法的破譯。唯密文故障分析已有研究對(duì)象包括具有SPN結(jié)構(gòu)的AES密碼、LED密碼,以及具有Feistel結(jié)構(gòu)的Piccolo密碼等,未有ARX結(jié)構(gòu)密碼的相關(guān)分析結(jié)果。

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

1 相關(guān)工作

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

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

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

2 LEA密碼簡(jiǎn)介

2.1 符號(hào)說明

記r為總輪數(shù);

記K為原始密鑰,由4個(gè)32 bit數(shù)據(jù)塊組成,即K=K0‖K1‖K2‖K3;

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

2.2 算法描述

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

圖1 LEA密碼算法輪函數(shù)結(jié)構(gòu)圖Fig.1 Round function of LEA

本文采用128bit密鑰長(zhǎng)度的LEA密碼為分析對(duì)象。算法1給出了該版本的加密算法。解密算法以相反的子密鑰使用順序和模減操作實(shí)現(xiàn),與加密算法結(jié)構(gòu)類似。

算法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所示,其中,常數(shù)δ參照文獻(xiàn)[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 基本假設(shè)和故障模型

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

表3 經(jīng)故障注入后的單比特分布概率

3.2 攻擊過程

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

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

(δ0<<<3))

3.3 區(qū)分器

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

3.3.1 現(xiàn)有區(qū)分器

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

式中:n為導(dǎo)入的故障數(shù)量;Om為中間狀態(tài)值中值為m的個(gè)數(shù),m∈{0,1}。

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

式中:n為導(dǎo)入的故障數(shù)量;h(·)為漢明重量值的計(jì)算函數(shù);sν為第v個(gè)中間狀態(tài)值;Om為中間狀態(tài)值中值為m的個(gè)數(shù),m∈{0,1}。

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

式中:n為導(dǎo)入的故障數(shù)量;sv為第v個(gè)中間狀態(tài)值,Dsv為中間狀態(tài)值為sv的理論概率;Dm為中間狀態(tài)值為m的理論概率;Om為中間狀態(tài)值中值為m的個(gè)數(shù),m∈{0,1}。

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

式中:Om為中間狀態(tài)值中值為m的個(gè)數(shù);Rm為中間狀態(tài)值為m的理論個(gè)數(shù),m∈{0,1}。

3.3.2 新型區(qū)分器

(1)比例距離區(qū)分器。比例距離(ratio distance,RD)區(qū)分器統(tǒng)計(jì)單比特中間狀態(tài)為“0”的數(shù)量和為“1”的數(shù)量的比值,根據(jù)分布的不均勻性選擇與“1”距離最遠(yuǎn)的一組分布,即RD值最大的一組中間狀態(tài)對(duì)應(yīng)的候選密鑰即為正確密鑰。RD值可表示為

式中:O0、O1分別為中間狀態(tài)值中值為“0”和“1”的數(shù)量。

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

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

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

(3)比例距離-極大似然區(qū)分器。比例距離-極大似然(RD-ML)區(qū)分器結(jié)合了RD區(qū)分器和ML區(qū)分器的優(yōu)勢(shì),對(duì)一組中間狀態(tài)分別求出兩者的區(qū)分器值,再通過權(quán)重分配,計(jì)算合計(jì)的區(qū)分器值,最終最大的合計(jì)區(qū)分器值所對(duì)應(yīng)的候選密鑰即為正確密鑰。RD-ML值可表示為

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

4 試驗(yàn)分析

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

4.1 成功率

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

圖3 各區(qū)分器恢復(fù)LEA密碼的原始密鑰的成功率隨故障注入數(shù)量的變化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區(qū)分器均可達(dá)99%及以上的成功率恢復(fù)LEA密碼原始密鑰,且新型區(qū)分器RD-ML、RD-HW和RD的成功率率先達(dá)99%,SEI區(qū)分器無法對(duì)候選密鑰進(jìn)行有效分析。

4.2 故障數(shù)量

故障數(shù)量是衡量故障分析的主要指標(biāo),攻擊者所需的故障數(shù)越少,在實(shí)際物聯(lián)網(wǎng)環(huán)境下進(jìn)行分析時(shí)越具有優(yōu)勢(shì)。在恢復(fù)LEA密碼原始密鑰的成功率達(dá)99%及以上時(shí),各區(qū)分器所需的故障注入數(shù)量如表4所示。由表4可知,新型區(qū)分器RD、RD-HW和RD-ML所需故障數(shù)較少,其中,RD-ML區(qū)分器所需故障數(shù)最少。

表4 各區(qū)分器恢復(fù)LEA密碼密鑰所需的故障數(shù)量

4.3 耗時(shí)

耗時(shí)是密碼算法攻擊中的一個(gè)衡量指標(biāo)。在使用不同區(qū)分器恢復(fù)LEA密碼原始密鑰的過程中,攻擊者以99%及以上成功率恢復(fù)LEA密碼原始密鑰,耗時(shí)與注入故障數(shù)量的關(guān)系如圖4所示。

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

耗時(shí)主要由遍歷所有故障密文和候選密鑰、反向推導(dǎo)中間狀態(tài)值、統(tǒng)計(jì)中間狀態(tài)值的分布情況、利用區(qū)分器篩選正確的密鑰等所需的時(shí)間組成。試驗(yàn)結(jié)果表明,除SEI區(qū)分器外,其他區(qū)分器按耗時(shí)遞減依次排序?yàn)镽D-HW、RD-ML、ML、HW、GF和RD,所需的時(shí)間分別為0.771、0.745、0.174、0.142和0.139和0.133 ms,對(duì)應(yīng)的故障數(shù)量為400、396、468、456、480和452個(gè)。由圖4可知,單區(qū)分器的耗時(shí)少于雙重區(qū)分器,新型單區(qū)分器RD耗時(shí)最少。

5 結(jié) 語

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