約減輪數分組密碼LEA的差分分析

李艷俊 李寅霜 劉 健 王 克

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

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

1 引言

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

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

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

表1 LEA-128攻擊分析結果比較

利用M ILP[15,16]工具可以找到LEA算法的12輪和13輪差分特征，從而計算出其對應的差分概率。基于此差分特征，結合提前拋棄技術，本文首次給出了LEA算法的13輪和14輪的密鑰恢復攻擊，其中13輪攻擊的數據復雜度和時間復雜度分別是298個選擇明文和285.7次13輪解密；14輪攻擊的數據復雜度和時間復雜度分別是2118個選擇明文和2110.6次14輪解密。

2 LEA算法簡介

2.1 LEA的加密算法

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

圖1 LEA的輪變換

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

對i=0,1,...,r-1計算

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

2.2 LEA的密鑰擴展算法

LEA的密鑰擴展算法需要8個32 bit常數，具體為

當密鑰長度為128 bit時，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)生成

當密鑰長度為192 bit或256 bit時，具體的密鑰擴展算法可詳見文獻[1]。

3 基于M ILP的ARX結構差分建模

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

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

Lipm aa等人[19]提出先驗證差分特征是否存在，再計算對應的差分特征概率，如下兩個定理所示：

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

進一步，這5 個不等式等價于1 個等式：α[0]⊕β[0]⊕γ[0]=2d⊕，其中，d⊕是一個增加的比特變量。

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

圖2 存在的差分向量模式

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

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

4 差分概率與特征概率

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

4.1 計算差分概率

算法1 最優特征的差分概率

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

算法1顯示了通過給定的原始M ILP模型如何構造最優特征的截斷概率多項式。盡管在第(1)行中，M ILP求解器被配置為返回最優解以及變量的值，但在第(7)行中，它應該被配置為返回最優解的數量。

4.2 次優的解決方案

M ILP問題本質上是NP完全問題。因此，對于差分密碼分析所對應的具有大量變量和約束的復雜的M ILP模型，M ILP求解器實際上是無法求得最優解的，所以一個次最優解就足夠了。

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

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

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

4.3 基于M ILP的差分概率

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

4.3.1 12輪LEA差分分析

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

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

為了求次優特征對應的差分概率，首先根據算法1找到概率多項式p1(x)和p2(x)

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

4.3.2 13輪LEA差分分析

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

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

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

5 密鑰恢復攻擊

5.1 13輪密鑰恢復攻擊

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

圖4 13輪密鑰恢復攻擊

步驟1構造 2N個明文對，加密13輪，根據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個密文對；

步驟2 猜測R K13[0]的 32 bit，解密得到ΔY13[1]，其低4 bit差分值與RK13[0]的相應比特無關，所以過濾得到2N-52-28個對；

步驟3猜測 RK13[1]⊕RK13[2]的32 bit，解密得到ΔY13[2]，其低11 bit差分值與RK13[1]⊕RK13[2]的相應比特無關，過濾得到2N-80-21個對；

步驟4猜測 RK13[3]⊕RK13[4]的32 bit，其低5 b it差分值與RK13[3]⊕RK13[4]的相應比特無關，過濾得到2N-101-27個密文對。

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

復雜度：第1步需要加密 298個明文，第2步進行232×245次1/3輪解密；第3步進行232×232×217次1/3輪解密；第4步進行232×232×232×2-4次1/3輪解密。所以數據復雜度為298個明文，時間復雜度為次13輪解密。

5.2 14輪密鑰恢復攻擊

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

圖5 14輪密鑰恢復攻擊

步驟1構造 2N個明文對，加密14輪，根據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個密文對；

步驟2猜測R K14[0]的 32 bit，解密得到ΔY14[1]，其低3 bit差分值與RK14[0]的相應比特無關，所以過濾得到2N-37-29個對；

步驟3猜測 RK14[1]⊕RK14[2]的32 bit，解密得到ΔY14[2]，其最低位比特的差分值與RK14[1]⊕RK14[2]的相應比特無關，過濾得到2N-66-31個對；

步驟4猜測 RK14[3]⊕RK14[4]的32 bit，其最低位比特的差分值與R K14[3]⊕RK14[4]的相應比特無關，過濾得到2N-97-31個密文對。

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

復雜度：第1步需要加密2118個明文，第2步進行 232×280次1/3輪解密；第3步進行232×232×251次1/3輪解密；第4步進行232×232×232×220次1/3輪解密。所以數據復雜度為2118個明文，時間復雜度為次14輪解密。

6 結束語

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

然而，如何優化建模實現對LEA-128概率更大的差分路徑進行搜索，并采用合適的方法對其進行密鑰恢復攻擊則是本文下一步的工作。