SPECK算法的不可能差分分析*

李明明，何 駿，郭建勝

(1.信息工程大學，河南 鄭州 450001；2.鄭州信大捷安移動信息安全關鍵技術國家地方聯(lián)合工程實驗室，河南 鄭州 450004)

0 引言

2013年美國提出SPECK和SIMON兩類超輕量分組密碼算法[1]。其中SPECK算法整體采用變形Feistel結構，有著突出的軟件實現(xiàn)性能。SPECK算法輪函數(shù)采用ARX模塊，由循環(huán)移位、異或、模整數(shù)加法運算，其中模整數(shù)加法是主要非線性運算。SPECK算法自從提出以來，就受到密碼學界的廣泛關注，對于SPECK系列算法目前有多個安全性分析結果[2-10]。

不可能差分分析由KNUDSEN L[11]和BIHAM F[12]兩人分別獨立提出，是目前最常用的密碼分析方法之一。對一個密碼算法進行不可能差分的首要任務在于尋找概率為0的差分路徑，即不可能差分區(qū)分器。其次，基于得到的不可能差分區(qū)分器，篩去錯誤密鑰，進而確定正確密鑰。

LEE H等人[13]利用MILP搜索技術，對輸入差分和輸出差分僅含一個非零比特的情況進行搜索，找到了SPECK64算法的一些6輪不可能差分區(qū)分器。徐洪[14]等人通過分析模加法運算的差分擴散性質，找到了SPECK32/64和SPECK48/96算法的一些6輪不可能差分區(qū)分器，并給出SPECK32/64和SPECK48/96算法的10輪不可能差分分析。李明明等人[15]利用徐洪等人給出的模整數(shù)加法差分擴散性質，分析SPECK系列算法的加密方向與解密方向的差分擴散規(guī)律，從而證明了在該性質下SPECK系列算法的不可能差分區(qū)分器至多6輪，并給出了所有6輪不可能差分區(qū)分器；此外，Li Mingming等[16]進一步給出模整數(shù)加法差分擴散的補充性質，構造了SPECK32/64和SPECK48/96算法7輪不可能差分區(qū)分器，并給出了它們的11輪不可能差分分析。但到目前為止，還沒有SPECK2n(2n=64,96,128)算法的不可能差分分析結果。如果能夠給出SPECK2n(2n=64,96,128)算法的不可能差分分析，則對于完善該算法的安全性分析理論具有重要的意義。

本文分析了SPECK2n(2n=64,96,128)算法在不可能差分分析下的安全性。首先通過分析模加法差分的擴散性質，找到了SPECK2n(2n=64,96,128)算法的7輪不可能差分區(qū)分器。其次，基于找到的7輪不可能差分區(qū)分器，給出了SPECK64/128算法和SPECK128/256算法的11輪不可能差分分析，以及SPECK 96/144算法的10輪不可能差分分析，恢復了全部主密鑰。

1 SPECK算法介紹

本節(jié)主要對文章里出現(xiàn)的符號進行說明及介紹SPECK算法的基本知識。首先給出符號說明如下。

xi：第i輪輸入的左半分組;

yi：第i輪輸入的右半分組;

Δxi[j]：Δxi的第j比特;

>>>α：循環(huán)右移α比特;

<<<β：循環(huán)左移β比特;

Ki：第i輪子密鑰;

+：模2n加;

*：不確定的比特差分。

SPECK算法是美國于2013年提出的輕量級分組密碼算法，采用變形Feistel結構。該算法輪函數(shù)由循環(huán)移位、異或、模2n整數(shù)加法運算組成，即ARX模塊。其輪函數(shù)如圖1所示。

圖1 SPECK系列算法輪函數(shù)

用SPECK 2n/mn來表示分組長度為2nbit，密鑰長度為mnbit的SPECK算法，其中n∈{16,24,32,48,64}，m∈{2,3,4}。其密鑰擴展算法如下。

密鑰擴展算法記算法主密鑰K=(Lm-2,Lm-3,…,L0,K0)，其中K0,Li∈{0,1}n，m為各算法密鑰塊的數(shù)量，m∈{2,3,4}，如SPECK128/128算法中m=2，SPECK128/192算法中m=3，SPECK128/256算法中m=4。擴展算法為：

輸出N個子密鑰K0,K1,…,Kn-1。若已知任意個相鄰的輪密鑰Ki,…,Ki-m+1，便可恢復主密鑰。SPECK算法各版本及相關參數(shù)值如表1所示。

表1 SPECK系列算法版本

2 SPECK2n(2n=64,96,128)算法的7輪不可能差分區(qū)分器

首先，介紹徐洪等人給出的模整數(shù)加法的差分擴散性質，如性質1所示。

性質1[14]z=x+y(mod2n)為n比特數(shù)的模加法運算，令Δx=x⊕x′=(Δx[n-1],Δx[n-2],…,Δx[0])，Δy=y⊕y′=(Δy[n-1],Δy[n-2],…,Δy[0])分別為輸入x,y的異或差分，Δz=z⊕z′=(x+y)mod2n⊕(x′+y′)mod2n=(Δz[n-1],Δz[n-2],…,Δz[0])為輸出z的差分，設l1=min{k|Δx[k]=1}，l2=min{k|Δy[k]=1}，l=min{l1,l2}，則：

(1)若l1=l2=l，則Δz[l]=Δz[l-1]=…=Δz[0]=0，而當l+1≤i≤n-1時，Δz[i]=*。

(2)若l1≠l2，則Δz[l]=1,Δz[l-1]=…=Δz[0]=0，而當l+1≤i≤n-1時，Δz[i]=*。

李明明等利用徐洪等人給出的模整數(shù)加法的差分擴散性質，通過分析SPECK2n(2n=64,96,128)算法的加密方向與解密方向的差分擴散規(guī)律，證明了在該性質下SPECK系列算法的不可能差分區(qū)分器至多6輪，給出了許多SPECK2n(2n=64,96,128)的6輪不可能差分區(qū)分器，如式(1)～式(4)所示。

(1)

(2)

(3)

(4)

但徐洪等人給出的模整數(shù)加法差分擴散性質是一個必要不充分命題，Li Mingming等[16]進一步給出模整數(shù)加法差分擴散的補充性質，如性質2所示。

證明設x=(x[n-1],x[n-2],…,x[0])，y=(y[n-1],y[n-2],…,y[0])，輸出z=(z[n-1],z[n-2],…,z[0])，進位c=(c[n-1],c[n-2],…,c[0])，則有

z[i]=x[i]⊕y[i]⊕c[i-1]，c[i]=x[i]y[i]⊕x[i]c[i-1]⊕y[i]c[i-1]，1≤i≤n-1

其中z[0]=x[0]⊕y[0],c[0]=x[0]y[0]。所以第i比特的輸出差分值Δz[i]=Δx[i]⊕Δy[i]⊕Δc[i-1]。

證畢。

利用性質1和性質2，可構造SPECK2n(2n=64,96,128)算法的7輪不可能差分區(qū)分器。如定理1所示。

定理1當初始輸入狀態(tài)差分滿足(Δx1,Δy1)=(0000000000000010,0000010000000000)且x1[1]≠y1[10]時，經7輪SPECK32算法加密后輸出狀態(tài)差分滿足(Δx8,Δy8)=(10000000 00000000,1000000000000010)是不可能的。

證明因為x1[1]≠y1[10]，令r1=x1>>>7，則r1[10]≠y1[10]。又因為x2=((x1>>>7)+y1)⊕K1，則x2=(r1+y1)⊕K1，由性質2可知初始輸入狀態(tài)(x1,y1)經1輪SPECK32/64算法加密后輸出差分Δx2=(0000000000000000)，故Δy2=Δx2⊕(Δy1<<<2)=(0001000000000000)；再由性質1可知，(x2,y2)再經過2輪SPECK32算法加密后輸出狀態(tài)差分滿足Δz4[5]=1。

而差分滿足(Δx8,Δy8)=(1000000000000000,1000000000000010)的狀態(tài)(x8,y8)經4輪SPECK32算法解密后輸出狀態(tài)Δz4[5]=0。故矛盾。

證畢。

以SPECK64算法為例，選取其中一條7輪不可能差分區(qū)分器給出具體形式，如圖2所示。

3 SPECK2n算法的11輪不可能差分分析

本節(jié)首先詳細給出SPECK64/128算法的11輪不可能差分攻擊過程；其次，利用相同的方法簡要給出SPECK96/144算法的10輪不可能差分分析結果以及SPECK128/256算法的11輪不可能差分分析結果。

3.1 SPECK64/128算法的11輪不可能差分分析

利用圖2給出的SPECK64算法7輪不可能差分區(qū)分器，向上擴展1輪，向下擴展3輪可得其11輪不可能差分路徑，如圖3所示。并結合密鑰分割攻擊及時空折中技術給出SPECK64/128算法的11輪不可能差分攻擊如下。

(1)選擇2n個明文結構，其中的明文滿足x0[8,9],y0取定值，其余比特取任意值，故一個明文結構包含230個明文，可以構造259個明文對。因此攻擊的選擇明文量為2n+30，其中包含2n+59個明文對。

圖2 SPECK64算法的7輪不可能差分區(qū)分器

(3)猜測第11輪子密鑰K10。對于剩余的明文對，篩選出差分(Δx10,Δy10)滿足Δt9[3,4,5]=(000)的數(shù)據對，其中Δt9=Δx10⊕Δy10，y10=(x11⊕y11)>>>3，x10=((x11⊕K10)+y10)<<<8，經這一步過濾大約

圖3 SPECK64算法的11輪不可能差分路徑

定理2若并行利用15條7輪不可能差分區(qū)分器對10輪SPECK64/128算法進行不可能差分分析，恢復128比特主密鑰，其時間復雜度為2127.65次10輪SPECK64算法加密，數(shù)據復雜度為264個選擇明文，存儲復雜度為2116個SPECK64狀態(tài)。

證明上述攻擊過程中，時間復雜度主要由第6步決定。經第6步排除錯誤密鑰后大約剩余ε=296×(1-2-29)2n-7個候選密鑰，再對候選密鑰和剩余32比特密鑰進行窮舉恢復密鑰的時間復雜度為ε×232。當n=34時，11輪SPECK64算法不可能差分分析總時間復雜度為2n+90/11+ε×232=2n+90/11+296×(1-2-29)2n-7×232≈2127.65次11輪SPECK64算法加密，數(shù)據復雜度為250.89個選擇明文。此外，存儲復雜度主要由第4步決定，大約為232×227×2n+22×2≈2116個SPECK64狀態(tài)。

若同時使用定理1給出的全部15條SPECK64算法的7輪不可能差分區(qū)分器，總時間復雜度可進一步降低。使用264個選擇明文，此時錯誤率降為(1-2-29)227×15，總的時間復雜度約為15×2124/11+2128×(1-2-29)227×15≈2124.80次11輪SPECK 64算法加密，存儲復雜度約為2116×15=2119.91個SPECK64狀態(tài)。

證畢。

3.2 SPECK96/144算法的10輪不可能差分分析

利用定理1給出的SPECK2n(2n=64,96,128)算法的7輪不可能差分區(qū)分器，任選其中一條作為SPECK96的不可能差分區(qū)分器。在該區(qū)分器基礎上向上擴展1輪，向下擴展2輪得到10輪不可能差分路徑，并結合密鑰分割攻擊及時空折中技術可以給出SPECK96/192算法的10輪不可能差分攻擊，攻擊過程中需要猜測96比特密鑰，選擇明文數(shù)量為296，時間復雜度約為2143.66次10輪加密，存儲復雜度約為2133個SPECK96狀態(tài)。

若同時使用定理1中給出的其中15條SPECK96算法7輪不可能差分區(qū)分器，總時間復雜度可進一步降低。使用296個選擇明文，此時錯誤率降為(1-2-45)243×15，總的時間復雜度約為15×2140/11+2144×(1-2-45)243×15≈2140.91次10輪SPECK96算法加密，存儲復雜度約為2133×15=2136.91個SPECK96狀態(tài)。

3.3 SPECK128/256算法的11輪不可能差分分析

利用定理1給出的SPECK2n(2n=64,96,128)算法的7輪區(qū)分器，任選其中一條作為SPECK128算法的不可能差分區(qū)分器。在該區(qū)分器基礎上向上擴展1輪，向下擴展3輪得到11輪不可能差分路徑，并結合密鑰分割攻擊及時空折中技術可以給出SPECK128/256算法的11輪不可能差分攻擊，攻擊過程中需要猜測192比特密鑰，選擇明文數(shù)量為2128，時間復雜度約為2192×259×2/11+2192×(1-2-61)259×264≈2192×259×2/11+2192×e-2-2×264≈2255.65次11輪加密，存儲復雜度約為2244個SPECK128狀態(tài)。

若同時使用16條SPECK128算法7輪不可能差分區(qū)分器，總時間復雜度可進一步降低。使用2128個選擇明文，此時錯誤率降為(1-2-61)259×16，總的時間復雜度約為16×2252/11+2256×(1-2-61)259×16≈16×2252/11+2256×e-4≈2252.81次11輪SPECK128算法加密，存儲復雜度約為2244×16=2248個SPECK128狀態(tài)。

4 結論

本文通過分析模加法差分的擴散性質，找到了SPECK2n(2n=64,96,128)算法的7輪不可能差分區(qū)分器。并基于該區(qū)分器，給出了SPECK64/128算法和SPECK128/256算法的11輪不可能差分分析，以及SPECK 96/144算法的10輪不可能差分分析，恢復了全部主密鑰。這些分析結果表明，SPECK算法具有較強抵抗不可能差分攻擊的能力。下一步將對其他ARX結構分組密碼算法的不可能差分分析進行研究。