約減輪數(shù)分組密碼LEA的差分分析

李艷俊 李寅霜 劉 健 王 克

①(中國電子科技集團(tuán)公司第十五研究所信息產(chǎn)業(yè)信息安全測評中心 北京 100083)

②(北京電子科技學(xué)院 北京 100070)

1 引言

LEA算法[1]是2013年由韓國電子通信研究院(E lectronics and Telecomm unications Research Institu te,ETRI)提出的一個(gè)面向軟件的輕量級分組密碼，設(shè)計(jì)目標(biāo)是在通用軟件平臺(tái)上提供快速加密。2017年，LEA被遞交給國際標(biāo)準(zhǔn)化組織/國際電工委員會(huì)(International Organization for Standardization/International Electrotechnical Comm ission,ISO/IEC)作為輕量分組密碼的候選標(biāo)準(zhǔn)，并且于2019年11月成為ISO/IEC國際標(biāo)準(zhǔn)輕量級加密算法。LEA的加密算法和密鑰擴(kuò)展算法中的模加、循環(huán)移位、逐位異或(m odu lar A dd ition,R otation,bitw ise XOR,ARX)操作可以有效并行實(shí)現(xiàn)，LEA不僅能夠快速軟件加密，而且代碼量小。和高級加密標(biāo)準(zhǔn)(Advanced Encryption Standard,AES)等分組密碼不同，LEA最后一輪的輪變換和其他輪一樣，易于加密算法的軟件和硬件實(shí)現(xiàn)。設(shè)計(jì)者認(rèn)為有許多工作模式僅調(diào)用分組密碼的加密算法，因此LEA不考慮加解密相似性，只強(qiáng)調(diào)加密算法的實(shí)現(xiàn)性能。LEA算法設(shè)計(jì)重點(diǎn)是循環(huán)移位數(shù)的選取，加密算法中3個(gè)移位數(shù)的選取策略使得擴(kuò)散性和差分特征達(dá)到最優(yōu)。LEA采用簡單的密鑰擴(kuò)展算法，密鑰字之間沒有混合，只是對密鑰字模加常數(shù)和循環(huán)移位，易于軟件和硬件實(shí)現(xiàn)。

LEA算法基于ARX結(jié)構(gòu)設(shè)計(jì)，該結(jié)構(gòu)是對稱密碼設(shè)計(jì)中常用的一種設(shè)計(jì)方法，通過綜合使用模加A(modular Addition)、循環(huán)移位R(Rotation)以及逐位異或X(Bitw ise XOR)3個(gè)操作來實(shí)現(xiàn)算法的非線性部件，進(jìn)而達(dá)到混淆和擴(kuò)散的作用，可以用來替換非線性部件S盒?；贏RX結(jié)構(gòu)設(shè)計(jì)的分組密碼有SPECK,HIGHT和Shadow[2–4]等。LEA是面向32 bit字的ARX類算法，分組長度為128 bit，密鑰長度為128,192和256 bit，分別記為LEA-128,LEA-192和LEA-256，迭代輪數(shù)分別為24,28和32。

針對ARX結(jié)構(gòu)分組密碼的常用安全評估方法有差分分析[5,6]、差分線性密碼分析[7,8]、積分分析、零相關(guān)線性密碼分析等。文獻(xiàn)[1]提出LEA算法的同時(shí)，也利用了多種分析方式對LEA的安全性進(jìn)行了相關(guān)評估。2016年，文獻(xiàn)[9]對LEA-128/192/256算法的零相關(guān)線性密碼分析攻擊提升到了9/13/14輪；同年文獻(xiàn)[10]給出了數(shù)據(jù)復(fù)雜度為 296的7輪積分區(qū)分器；2018年，文獻(xiàn)[11]利用混合整數(shù)線性規(guī)劃(M ixed Integer Linear Program,M ILP)搜索給出了LEA-128的10輪零相關(guān)線性路線、10輪不可能差分路徑；2019年，文獻(xiàn)[12]利用M ILP和布爾可滿足性問題(SATisfiability,SAT)方法分別得到了LEA-128的7/8輪積分區(qū)分器；2020年，文獻(xiàn)[13]使用中間相錯(cuò)技術(shù)將LEA-128/192/256算法的積分分析攻擊提升到了10/11/11輪；2022年，文獻(xiàn)[14]對LEA算法進(jìn)行差分與線性建模，通過拼接的方式得到了12 輪概率為2–107的差分線性特征。有關(guān)LEA-128的攻擊分析結(jié)果比較如表1所示。

表1 LEA-128攻擊分析結(jié)果比較

利用M ILP[15,16]工具可以找到LEA算法的12輪和13輪差分特征，從而計(jì)算出其對應(yīng)的差分概率?；诖瞬罘痔卣?，結(jié)合提前拋棄技術(shù)，本文首次給出了LEA算法的13輪和14輪的密鑰恢復(fù)攻擊，其中13輪攻擊的數(shù)據(jù)復(fù)雜度和時(shí)間復(fù)雜度分別是298個(gè)選擇明文和285.7次13輪解密；14輪攻擊的數(shù)據(jù)復(fù)雜度和時(shí)間復(fù)雜度分別是2118個(gè)選擇明文和2110.6次14輪解密。

2 LEA算法簡介

2.1 LEA的加密算法

加密算法由r輪迭代運(yùn)算組成，輪變換如圖1所示。其中X i[j]表 示32 b it的字，R Ki[j]是輪密鑰，+表示模 232加，R ORi表示循環(huán)右移ibit，R OLi表示循環(huán)左移ibit。

圖1 LEA的輪變換

記128 bit的明文P=X0[0]‖X0[1]‖X0[2]‖X0[3]，加密過程如下：

對i=0,1,...,r-1計(jì)算

X r[0]‖X r[1]‖X r[2]‖X r[3]=C為128 bit密文。

2.2 LEA的密鑰擴(kuò)展算法

LEA的密鑰擴(kuò)展算法需要8個(gè)32 bit常數(shù)，具體為

當(dāng)密鑰長度為128 bit時(shí)，K=K[0]‖K[1]‖K[2]‖K[3]，令T[j]=K[j],0≤j ≤3。對i=0,1,...,23，輪密鑰RKi=RKi[0]‖RKi[1]‖...‖RKi[5]如式(3)生成

當(dāng)密鑰長度為192 bit或256 bit時(shí)，具體的密鑰擴(kuò)展算法可詳見文獻(xiàn)[1]。

3 基于M ILP的ARX結(jié)構(gòu)差分建模

在安全性評估方面，差分分析和線性分析仍然是最有效的分析方法，然而對于ARX結(jié)構(gòu)的分析也不同于傳統(tǒng)具有S盒的分組密碼的分析。對基于字節(jié)或半字節(jié)設(shè)計(jì)的算法，通過搜索活躍S盒個(gè)數(shù)的下界可以給出差分特征估計(jì)；對基于比特設(shè)計(jì)的算法，文獻(xiàn)[17]通過SAGE工具來產(chǎn)生刻畫S盒差分分布特性的線性不等式集合，并用這些不等式來構(gòu)建了搜索差分特征的M ILP模型；由于搜索程序是啟發(fā)式的，得到的結(jié)果不一定為最優(yōu)，為了克服這一問題，文獻(xiàn)[18]提出了一種貪心算法，將啟發(fā)式的搜索算法轉(zhuǎn)變?yōu)闇?zhǔn)確且可以實(shí)際應(yīng)用的搜索方法；對ARX結(jié)構(gòu)算法，Lipmaa等人[19]基于M ILP工具給出了模加操作的差分特征刻畫，并構(gòu)建了自動(dòng)化搜索模型，具體如下描述。

定義1模 2n加法輸入差分為α,β，輸出差分為γ，那么異或差分概率如式(4)計(jì)算

Lipm aa等人[19]提出先驗(yàn)證差分特征是否存在，再計(jì)算對應(yīng)的差分特征概率，如下兩個(gè)定理所示：

定理1模2n加法差分特征(α,β →γ)概率不為0當(dāng)且僅當(dāng)以下兩個(gè)條件成立：

進(jìn)一步，這5 個(gè)不等式等價(jià)于1 個(gè)等式：α[0]⊕β[0]⊕γ[0]=2d⊕，其中，d⊕是一個(gè)增加的比特變量。

下 面 用 向 量(α[i],β[i],γ[i],α[i+1],β[i+1],γ[i+1])刻 畫第ibit與第i+1 bit差分之間的關(guān)系。文獻(xiàn)[20]觀察到根據(jù)定理1，這個(gè)向量只有56種可能的模式，加上變量?eq(α[i],β[i],γ[i])形成7維向量，如圖2所示。

圖2 存在的差分向量模式

結(jié)合SAGE求解器和貪心算法[18]，這56個(gè)向量可以由13個(gè)不等式來刻畫，如圖3所示。

對于兩個(gè)輸入變量和1個(gè)輸出變量都為nb it的模加運(yùn)算，共需要13×(n-1)+1個(gè)線性不等式來刻畫，最后可以計(jì)算得到差分概率p=

4 差分概率與特征概率

為了精確評估分組密碼在差分分析下的安全性，Lai等人[21]首先引入了馬爾可夫密碼理論，并對差分特征和差分進(jìn)行了區(qū)分。在差分密碼分析中，對于一個(gè)給定的輸入輸出差分值，可能存在許多潛在的具有相同輸入輸出差分的特征，它們對差分概率的大小都有貢獻(xiàn)，這種效應(yīng)被稱作強(qiáng)差分效應(yīng)[21]，所以為了更加準(zhǔn)確地計(jì)算差分概率，應(yīng)當(dāng)統(tǒng)計(jì)更多具有相同輸入輸出差分的特征。

4.1 計(jì)算差分概率

算法1 最優(yōu)特征的差分概率

下面首先引入概率多項(xiàng)式的概念，它是差分概率的一種緊湊而簡潔的表示形式，并給出了相應(yīng)的特征。給定輸入輸出差分值的某一特定差分的概率多項(xiàng)式定義為：p(x)=p0x d+p1x d+1+p2x d+2+...，其中2-d是給定輸入輸出差分中概率最大的特征概率值，p i是具有概率為2-(d+i)的不同特征的數(shù)量，i=0,1,...，顯然，通過計(jì)算x=時(shí)p(x)的具體值可以得到其對應(yīng)特征的概率。特別地，可以考慮截?cái)喟娴膒(x)，只包含前N個(gè)單項(xiàng)，即：

算法1顯示了通過給定的原始M ILP模型如何構(gòu)造最優(yōu)特征的截?cái)喔怕识囗?xiàng)式。盡管在第(1)行中，M ILP求解器被配置為返回最優(yōu)解以及變量的值，但在第(7)行中，它應(yīng)該被配置為返回最優(yōu)解的數(shù)量。

4.2 次優(yōu)的解決方案

M ILP問題本質(zhì)上是NP完全問題。因此，對于差分密碼分析所對應(yīng)的具有大量變量和約束的復(fù)雜的M ILP模型，M ILP求解器實(shí)際上是無法求得最優(yōu)解的，所以一個(gè)次最優(yōu)解就足夠了。

為了找到次最優(yōu)解，可以將r輪密碼分成兩個(gè)r1和r2輪子密碼(r=r1+r2)，分別獨(dú)立求解。如果第1個(gè)和第2個(gè)子密碼問題的最優(yōu)值分別為d1和d2，則該密碼問題的次最優(yōu)值為d=d1+d2。通過算法1可以構(gòu)造兩個(gè)子密碼問題的概率多項(xiàng)式p1(x)和p2(x)。為了推導(dǎo)r輪密碼的概率多項(xiàng)式，需要結(jié)合r1和r2輪的每一個(gè)特征，考慮所有可能的r輪特征。這個(gè)過程完全等價(jià)于將兩個(gè)子密碼的概率多項(xiàng)式相乘。所以r 輪差分的概率多項(xiàng)式是p(x)=p1(x)p2(x)。

一般來說，實(shí)際的問題可能十分復(fù)雜，以至于把r輪密碼分成兩個(gè)子密碼是不夠的。因此，將r輪密碼用概率多項(xiàng)式pi(x)，i=1,2,...,k分成k個(gè)子密碼。顯然，第i個(gè)子密碼問題的輸出差分等于第i+1個(gè)子密碼問題的輸入差分。

最后，r輪密碼的概率多項(xiàng)式可以表示為p(x)=，其中差分概率表示為

4.3 基于M ILP的差分概率

根據(jù)第3節(jié)描述的針對ARX結(jié)構(gòu)差分分析的M ILP模型，可以構(gòu)造一個(gè)針對任意輪的LEA密碼的M ILP模型。但如果沒有任何額外的約束來搜索r 輪LEA，當(dāng)r ≥ 4時(shí)，M ILP模型將變得過于復(fù)雜而無法求解。因此，根據(jù)4.2節(jié)的分析，可以采用兩個(gè)短的特征來構(gòu)造一個(gè)長特征的方法。針對LEA-128，文獻(xiàn)[22]給出了12輪和13輪的差分特征及計(jì)算其對應(yīng)差分概率的方法。

4.3.1 12輪LEA差分分析

首先對12輪LEA進(jìn)行分析，將其分為兩個(gè)6輪的子密碼問題，并且第1個(gè)子密碼問題的輸出差分與第2個(gè)子密碼問題的輸入差分相同。將這兩個(gè)問題獨(dú)立求解，找到d=d1+d2最小的特征，此時(shí)12輪內(nèi)部的差分特征=(0x00000000,0x00000000,0x00000000,0x00020000)。在這種情況下，d1=70,d2=37。因此，對應(yīng)的次最優(yōu)12輪特征為d=107。這個(gè)特征的詳細(xì)信息如表2所示。

表2 LEA算法的12輪差分特征及概率

為了求次優(yōu)特征對應(yīng)的差分概率，首先根據(jù)算法1找到概率多項(xiàng)式p1(x)和p2(x)

可以計(jì)算出12輪差分的概率多項(xiàng)式如式(9)最后通過計(jì)算x=時(shí)的p(x)值，可以求得LEA 的12輪差分概率為

4.3.2 13輪LEA差分分析

由于7輪的M ILP問題不能較好地進(jìn)行求解，所以將密碼分成了3個(gè)子密碼，前兩個(gè)子密碼是之前發(fā)現(xiàn)的兩個(gè)6輪子密碼，第3個(gè)子密碼是1輪子密碼，它的輸入差分等于第2個(gè)子密碼問題的輸出差分，即=(0x80222188,0x22200400,0x81001400,0x00401110)。表3顯示了特征的詳細(xì)信息。

表3 LEA算法的13輪差分特征及概率

最后通過計(jì)算x=時(shí)p(x)的值，可以求得LEA的13輪差分概率為

5 密鑰恢復(fù)攻擊

5.1 13輪密鑰恢復(fù)攻擊

在以上12輪差分路徑后加1輪，形成13輪如圖4所示，為了更方便地描述解密過程，令X13[1]⊕RK13[1]=Y13[1], (X13[0]⊕RK13[0])?Y13[1]=Z13[1]。

圖4 13輪密鑰恢復(fù)攻擊

步驟1構(gòu)造 2N個(gè)明文對，加密13輪，根據(jù)12輪輸出差分特征，顯然有ΔZ13[1]的低4位為1 000，ΔZ13[2]的 低11位全為0，ΔZ13[3]的低5位為10 000，由此可確定密文差分ΔX14[0]中有1 bit為1，3 bit為0； ΔX14[1]中有1 1 b i t 為0；ΔX14[2]中有1 bit為1，4 bit為0；并且ΔX13[0]=ΔX14[3]，篩選后得到2N-4-11-5-32個(gè)密文對；

步驟2 猜測R K13[0]的 32 bit，解密得到ΔY13[1]，其低4 bit差分值與RK13[0]的相應(yīng)比特?zé)o關(guān)，所以過濾得到2N-52-28個(gè)對；

步驟3猜測 RK13[1]⊕RK13[2]的32 bit，解密得到ΔY13[2]，其低11 bit差分值與RK13[1]⊕RK13[2]的相應(yīng)比特?zé)o關(guān)，過濾得到2N-80-21個(gè)對；

步驟4猜測 RK13[3]⊕RK13[4]的32 bit，其低5 b it差分值與RK13[3]⊕RK13[4]的相應(yīng)比特?zé)o關(guān)，過濾得到2N-101-27個(gè)密文對。

令N =97，對于猜測正確的96 bit密鑰，平均剩下2個(gè)對；對于猜測錯(cuò)誤的密鑰，平均剩下2-31個(gè)對。

復(fù)雜度：第1步需要加密 298個(gè)明文，第2步進(jìn)行232×245次1/3輪解密；第3步進(jìn)行232×232×217次1/3輪解密；第4步進(jìn)行232×232×232×2-4次1/3輪解密。所以數(shù)據(jù)復(fù)雜度為298個(gè)明文，時(shí)間復(fù)雜度為次13輪解密。

5.2 14輪密鑰恢復(fù)攻擊

在以上13輪差分路徑后加1輪，形成14輪如圖5所示，為了更方便地描述解密過程，令X14[1]⊕RK14[1]=Y14[1], (X14[0]⊕RK14[0])?Y14[1]=Z14[1]。

圖5 14輪密鑰恢復(fù)攻擊

步驟1構(gòu)造 2N個(gè)明文對，加密14輪，根據(jù)13輪輸出差分特征，顯然有ΔZ14[1]的低3 b it為100，ΔZ14[2]和 ΔZ13[3]的最低位都為1，由此可確定密文差分ΔX15[0]中 有1 bit為1，2 bit為0；ΔX15[1]中有1 bit為1；ΔX15[2]中 有1 bit為1；并且ΔX14[0]=ΔX15[3]，篩選后得到2N-3-1-1-32個(gè)密文對；

步驟2猜測R K14[0]的 32 bit，解密得到ΔY14[1]，其低3 bit差分值與RK14[0]的相應(yīng)比特?zé)o關(guān)，所以過濾得到2N-37-29個(gè)對；

步驟3猜測 RK14[1]⊕RK14[2]的32 bit，解密得到ΔY14[2]，其最低位比特的差分值與RK14[1]⊕RK14[2]的相應(yīng)比特?zé)o關(guān)，過濾得到2N-66-31個(gè)對；

步驟4猜測 RK14[3]⊕RK14[4]的32 bit，其最低位比特的差分值與R K14[3]⊕RK14[4]的相應(yīng)比特?zé)o關(guān)，過濾得到2N-97-31個(gè)密文對。

令N =117，對于猜測正確的96 bit密鑰，平均剩下2個(gè)對；對于猜測錯(cuò)誤的密鑰，平均剩下2-11個(gè)對。

復(fù)雜度：第1步需要加密2118個(gè)明文，第2步進(jìn)行 232×280次1/3輪解密；第3步進(jìn)行232×232×251次1/3輪解密；第4步進(jìn)行232×232×232×220次1/3輪解密。所以數(shù)據(jù)復(fù)雜度為2118個(gè)明文，時(shí)間復(fù)雜度為次14輪解密。

6 結(jié)束語

本文對LEA算法的抵抗差分分析能力進(jìn)行了安全性評估，針對LEA-128算法，本文首次進(jìn)行了13輪和14輪的密鑰恢復(fù)攻擊。為了減少攻擊的計(jì)算復(fù)雜度和選擇明文量，選擇差分特征中概率最大的一條并計(jì)算其對應(yīng)的差分概率，改進(jìn)了文獻(xiàn)[1]中的差分分析結(jié)果。攻擊過程運(yùn)用加密算法的部分特性，采用了提前拋棄技術(shù)，從而減少了密鑰的猜測量，降低了計(jì)算復(fù)雜度，最終使得13輪密鑰恢復(fù)攻擊的數(shù)據(jù)復(fù)雜度為 298個(gè)明文，時(shí)間復(fù)雜度為286.7次13輪解密，使得14輪密鑰恢復(fù)攻擊的數(shù)據(jù)復(fù)雜度為2118個(gè)明文，時(shí)間復(fù)雜度為2110.6次14輪解密。

然而，如何優(yōu)化建模實(shí)現(xiàn)對LEA-128概率更大的差分路徑進(jìn)行搜索，并采用合適的方法對其進(jìn)行密鑰恢復(fù)攻擊則是本文下一步的工作。