李明明，何 駿，郭建勝

(1.信息工程大學(xué)，河南 鄭州 450001；2.鄭州信大捷安移動(dòng)信息安全關(guān)鍵技術(shù)國(guó)家地方聯(lián)合工程實(shí)驗(yàn)室，河南 鄭州 450004)

0 引言

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

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

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

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

1 SPECK算法介紹

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

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

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

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

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

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

Ki：第i輪子密鑰;

+：模2n加;

*：不確定的比特差分。

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

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

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

密鑰擴(kuò)展算法記算法主密鑰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。擴(kuò)展算法為：

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

表1 SPECK系列算法版本

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

首先，介紹徐洪等人給出的模整數(shù)加法的差分?jǐn)U散性質(zhì)，如性質(zhì)1所示。

性質(zhì)1[14]z=x+y(mod2n)為n比特?cái)?shù)的模加法運(yùn)算，令Δ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的差分，設(shè)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，而當(dāng)l+1≤i≤n-1時(shí)，Δz[i]=*。

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

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

(1)

(2)

(3)

(4)

但徐洪等人給出的模整數(shù)加法差分?jǐn)U散性質(zhì)是一個(gè)必要不充分命題，Li Mingming等[16]進(jìn)一步給出模整數(shù)加法差分?jǐn)U散的補(bǔ)充性質(zhì)，如性質(zhì)2所示。

證明設(shè)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])，進(jìn)位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]。

證畢。

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

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

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

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

證畢。

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

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

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

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

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

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

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

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

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

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

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

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

證畢。

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

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

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

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

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

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

4 結(jié)論

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