李明明,何 駿,郭建勝
(1.信息工程大學(xué),河南 鄭州 450001;2.鄭州信大捷安移動(dòng)信息安全關(guān)鍵技術(shù)國(guó)家地方聯(lián)合工程實(shí)驗(yàn)室,河南 鄭州 450004)
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ù)了全部主密鑰。
本節(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系列算法版本
首先,介紹徐洪等人給出的模整數(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所示。
本節(jié)首先詳細(xì)給出SPECK64/128算法的11輪不可能差分攻擊過程;其次,利用相同的方法簡(jiǎn)要給出SPECK96/144算法的10輪不可能差分分析結(jié)果以及SPECK128/256算法的11輪不可能差分分析結(jié)果。
利用圖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)。
證畢。
利用定理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)。
利用定理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)。
本文通過分析模加法差分的擴(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)行研究。