SPECK型算法的積分分析和不可能差分分析*

方玉穎,徐 洪,2

1.數(shù)學工程與先進計算國家重點實驗室,鄭州450001

2.信息工程大學,鄭州450001

1 引言

不可能差分分析和積分分析是分組密碼兩類重要的分析方法.不可能差分分析是差分分析方法的變形,由Knudsen和Biham[1,2]分別獨立提出,其核心思想是利用分組密碼不可能出現(xiàn)的特定輸入輸出差分排除錯誤密鑰.不可能差分分析方法的關(guān)鍵是不可能差分特征的構(gòu)造,中間相錯是最主要的構(gòu)造方法.積分分析由Knudsen等[3]在Square攻擊、Saturation攻擊和Multiset攻擊基礎(chǔ)之上提出,其核心思想是通過選擇特定輸入明文集,分析經(jīng)多輪加密后某些比特是否具有特定的積分性質(zhì),比如平衡性,即對應(yīng)的狀態(tài)集求和為0的情形,再根據(jù)這些積分性質(zhì)排除錯誤密鑰.

積分攻擊的關(guān)鍵是尋找長的積分區(qū)分器,對于分組規(guī)模較大輪函數(shù)較復雜的算法尋找其積分區(qū)分器通常是比較困難的.2015年歐密會上,日本學者 Todo[4]在傳統(tǒng)積分的基礎(chǔ)上提出了可分性 (Division Property)的概念,并成功刻畫了可分性經(jīng)過異或,復制,S盒等基本運算的擴散規(guī)律,實現(xiàn)了對分組算法積分區(qū)分器的有效搜索.同年美密會,Todo[5]利用可分性的思想,結(jié)合 S盒自身的缺陷,成功構(gòu)造了MISTY1算法的 6輪積分區(qū)分器,首次實現(xiàn)了對 MISTY1算法理論上的全輪攻擊.FSE 2016會議上,Todo和Morii[6]在已有工作的基礎(chǔ)上,進一步給出了比特可分性(Bit-based Division Property)的定義,實現(xiàn)了對SIMON算法的積分區(qū)分器搜索.同年亞密會上,Xiang[7]等人將混合整數(shù)線性規(guī)劃(MILP)思想應(yīng)用到積分區(qū)分器的搜索中,先將分組密碼比特可分性的傳播過程轉(zhuǎn)化為相應(yīng)的MILP模型,再調(diào)用開源求解器Gurobi求解相應(yīng)的MILP問題,最終實現(xiàn)了包括SIMON 128在內(nèi)的多個分組密碼算法積分區(qū)分器的自動化搜索.Wang和Sun[8–10]等人進而研究了ARX型分組密碼的積分區(qū)分器的自動化搜索技術(shù),通過刻畫模加運算比特可分性的傳播規(guī)律,建立了相應(yīng)的MILP模型并實現(xiàn)了對HIGHT、TEA等多個分組算法積分區(qū)分器的搜索.

2013年,美國國家安全局 (簡稱 NSA)設(shè)計提出了兩類重要的 ARX型輕量分組密碼算法 SIMON和SPECK[11],其中SPECK算法整體采用變形的Feistel結(jié)構(gòu),算法輪函數(shù)由循環(huán)移位、模加和異或三部分組成.同時為了支持不同程度的信息安全,算法根據(jù)不同的分組長度和密鑰長度提供了多個版本,相應(yīng)的算法迭代輪數(shù)也有所不同.目前對SPECK算法主要的攻擊方法包括差分分析,線性分析,積分分析,零相關(guān)線性分析和不可能差分分析等[12–21].

作為輪函數(shù)中主要的線性擴散層,不同移位參數(shù)對應(yīng)的 SPECK算法的安全強度一般也不同.2016年FSE會議上,Biryukov等[17]在研究SPECK算法最優(yōu)差分路徑的搜索問題時,列出了分組長度為32,48,64比特的SPECK型算法的部分差分最優(yōu)移位參數(shù).本文在此基礎(chǔ)上針對不同分組長度,進一步分析了不同移位參數(shù)對應(yīng)的SPECK型算法的積分性質(zhì)和不可能差分性質(zhì),完善了對SPECK型算法安全性能的分析.

本文主要安排如下:第2節(jié)給出了文中要用到的一些符號,并簡要介紹了SPECK算法.第3節(jié)利用混合整數(shù)線性規(guī)劃方法,基于可分性搜索了SPECK型算法的積分區(qū)分器,并給出了不同移位參數(shù)對應(yīng)的積分區(qū)分器的輪數(shù).第4節(jié)利用中間相錯思想和模加差分的性質(zhì)搜索了SPECK型算法的不可能差分特征,并給出了不同移位參數(shù)對應(yīng)的不可能差分特征的輪數(shù).第5節(jié)為簡單的小結(jié),結(jié)合已有差分分析的結(jié)果,給出了能綜合抵抗多種攻擊的優(yōu)化移位參數(shù).

2 預備知識

2.1 符號說明

Lr: 第r輪左邊的輸入Rr: 第r輪右邊的輸入

kr: 第r輪的輪子密鑰⊕: 異或

∧: 按位與 +: 模2n加法

?α:循環(huán)左移α比特 ?β:循環(huán)右移β比特

:F2上n維向量空間a:F2上n維向量

a[i]: 向量a∈的第i個比特w(a):向量a∈的漢明重量

W(a):向量a=(a0,···,am?1)∈×···×的向量漢明重量,W(a)=(w(a0),···,w(am?1))

2.2 SPECK算法簡介

SPECK系列算法[11]采用變形的Feistel結(jié)構(gòu),輪函數(shù)由循環(huán)移位、模整數(shù)加法和異或運算組成,主要的非線性部件為模整數(shù)加法,具體結(jié)構(gòu)如圖1所示.

圖1 SPECK算法的輪函數(shù)Figure 1 Round function of SPECK

設(shè) SPECK 算法第r?1輪的輸入為 (Lr?1,Rr?1),輸出為 (Lr,Rr),輪子密鑰為kr?1,移位參數(shù)記為 (α,β),則經(jīng)過一輪迭代后的輸出為

Lr=(Lr?1>>>α)+Rr?1⊕kr?1

Rr=(Lr?1>>>α)+Rr?1⊕(Rr?1<<<β)⊕kr?1

以下簡記移位參數(shù)為 (α,β)的 SPECK 算法為 SPECK(α,β)算法. 原 SPECK32算法的移位參數(shù)(α,β)=(7,2),更長分組的 SPECK 算法的移位參數(shù) (α,β)=(8,3).

2016年FSE會議上,Biryukov等[17]在研究SPECK算法最優(yōu)差分路徑和線性路徑的搜索問題時,給出了不同移位參數(shù)下SPECK型算法的最優(yōu)差分路徑對應(yīng)的最大差分概率.在考慮減輪版本SPECK型算法的安全性時,他們發(fā)現(xiàn)在固定移位參數(shù)的情形下,移位參數(shù)(9,2)比原始參數(shù)(7,2)對應(yīng)的SPECK算法具有更好的差分性質(zhì),移位參數(shù)(4,3)、(5,3)、(7,3)、(13,3)的SPECK48算法比原始參數(shù)(8,3)對應(yīng)的差分性質(zhì)更好,而移位參數(shù) (2,3)、(4,3)、(5,3)、(7,3)、(9,3)、(10,3)、(11,3)、(12,3)、(15,3)的 SPECK64算法和原始參數(shù)(8,3)對應(yīng)的差分性質(zhì)相當,均達到最優(yōu).本文將在此基礎(chǔ)上進一步研究不同移位參數(shù)的SPECK型算法的積分性質(zhì)和不可能差分性質(zhì).

3 SPECK型算法的積分分析

本節(jié)先簡要回顧可分性的概念和可分性的傳播規(guī)律,建立相應(yīng)的MILP模型,再給出SPECK型算法積分區(qū)分器自動化搜索的步驟和結(jié)果.

3.1 可分性

可分性的概念由日本學者Todo[4]在2015年歐密會上提出,之后Todo,Xiang,Sun[6–10]等人又相繼研究了基于比特的可分性質(zhì),分析了可分性在基本運算上的擴散規(guī)律,并利用MILP,SAT等方法實現(xiàn)了多個分組算法積分區(qū)分器的搜索.下面簡要介紹可分性的定義以及一些基本運算的可分性傳播規(guī)律.

比特可分性經(jīng)過一些基本運算,如復制(COPY)、異或(XOR)、按位與(AND)的傳播規(guī)律如下:

性質(zhì) 1(復制)[6,7]設(shè)F是復制運算,輸入x∈F2,輸出可表示為(y0,y1)=(x,x).令X和Y分別為對應(yīng)的輸入和輸出集合,設(shè)X滿足可分性,Y滿足可分性,則傳播過程如下所示

注:設(shè)多重集X具有可分性,則集合X沒有積分性質(zhì)當且僅當K包含所有單位向量.

根據(jù)上面的分析,尋找分組算法的積分區(qū)分器時,可以從僅含一個非活躍比特(塊)的輸入集出發(fā),分析經(jīng)輪函數(shù)迭代后可分性的傳播規(guī)律.若r輪迭代后輸出集對應(yīng)的可分性K中首次包含所有單位向量,則存在相應(yīng)的(r?1)輪積分區(qū)分器.

3.2 MILP模型

Xiang等人在文獻[7]中利用混合整數(shù)線性規(guī)劃(MILP)思想,將分組密碼可分性的傳播過程轉(zhuǎn)化為不等式表示,并調(diào)用開源求解器Gurobi求解相應(yīng)MILP模型,實現(xiàn)了對多個輕量分組算法積分區(qū)分器的自動化搜索.Sun等人[8,9]進一步刻畫了模加運算可分性傳播的 MILP模型,實現(xiàn)了對一般ARX型分組密碼的積分區(qū)分器的搜索.他們建立的基于比特的復制、異或和與運算的MILP模型如下:

模型 1(復制)[8]設(shè)復制運算的比特可分性為(a)(b0,b1,···,bm),則有

模型 2(異或)[8]設(shè)異或運算的比特可分性為 (a0,a1,···,am)(b),則有

模型 3(按位與)[8]設(shè)按位與運算的比特可分性為(a0,a1)(b),則有

對于模加運算,Sun等[8,9]首先通過引入進位變量,給出了模加運算各分量的代數(shù)標準型.不妨設(shè)輸入和輸出分別為x=(x0,x1,···,xn?1),y=(y0,y1,···,yn?1),z=(z0,z1,···,zn?1),滿足z=x+y,則各分量間滿足如下關(guān)系

根據(jù)上式給出的各分量間的函數(shù)關(guān)系，可以將模加運算轉(zhuǎn)化為復制、異或、按位與等基本運算的復合,再結(jié)合模型1–3即可給出其可分性傳播的MILP形式.不妨以n比特數(shù)的模加運算為例,其可分性傳播的MILP模型可以如下構(gòu)造,各中間變量的分配表如表1所示.

設(shè)n比特模加運算輸入輸出可分性分別記為 (b0,b1,···,bn?1)、(d0,d1,···,dn?1) 和 (e0,e1,···,en?1),中間變量如上表所示,則模加運算可分性的傳播 (b0,b1,···,bn?1)+(d0,d1,···,dn?1)(e0,e1,···,en?1)可表示為如下形式

初始可分性和終止條件[7]記為一條 (r+1)輪可分路徑,L為刻畫該(r+1)輪算法可分性傳播規(guī)律的不等式形式.設(shè)算法的輸入和輸出可分性分別為,其中K0={k}={(k0,k1,···,k2n?1)}.為了構(gòu)造 (r+1)輪算法完整的 MILP 模型,我們首先需要對算法的初始可分性進行賦值,即將等式=ki(i=0,1,···,2n?1)作為約束條件添加到不等式組L中;其次,根據(jù)3.1節(jié)的說明,易知當輸出集的可分性中包含所有的單位向量,即說明此時集合不存在可分性,因此我們將目標函數(shù)設(shè)置為即第r+1輪輸出狀態(tài)集可分性各分量的求和.在調(diào)用開源求解器Gurobi求解后,若存在2n種輸出變量使得目標函數(shù)取值為1,即說明集合Kr+1包含所有2n個單位向量,則由可以得到一條r輪積分區(qū)分器.

表1 n比特模加中間變量分配Table 1 Allocation of intermediate variables for n-bit modular

3.3 積分區(qū)分器搜索

對于分組長度為2n比特的SPECK型算法,基于比特可分性,利用MILP方法自動化搜索積分區(qū)分器的具體流程如下:

步驟 1:選擇僅含一個非活躍比特的特定的輸入集 (A,···,C,···,A)相應(yīng)的比特可分性為其中C表示常量比特,A表示活躍比特,常量比特所在位置可以是任意的i∈{0,1,···,2n?1};

步驟 2:根據(jù) 3.2節(jié)中給出的 SPECK(α,β)算法的單輪可分性傳播模型,構(gòu)造完整 (r+1)輪SPECK(α,β)算法積分區(qū)分器搜索的MILP模型,并設(shè)置目標函數(shù)為

步驟3:調(diào)用開源求解器Gurobi求解MILP模型.若輸出集可分性中集合Kr+1包含所有2n個單位向量,則算法終止,由可以返回一條r輪積分區(qū)分器;

步驟4:若集合Kr+1不包含所有2n個單位向量,則繼續(xù)迭代1輪,重復步驟2和步驟3,直到程序返回一條有效的積分區(qū)分器.

圖2 SPECK32算法1輪差分路徑Figure 2 1-round of differential trail of SPECK32 algorithm

根據(jù)上述步驟,基于MILP方法我們對采用不同移位參數(shù)(α,β)的SPECK型算法的積分區(qū)分器進行了搜索.對于不同分組長度的 SPECK型算法,固定β為原算法的移位參數(shù),當移位參數(shù)α變化時,表2列出了不同參數(shù)下能夠找到的積分區(qū)分器的輪數(shù).

表2 SPECK型算法積分區(qū)分器的輪數(shù)(32/48/64比特分組)Table 2 Round of integral distinguishers of SPECK-like algorithm(32/48/64-bits block)

從表中數(shù)據(jù)可以看出,在減輪情形下,當固定β=2時,移位參數(shù)為(8,2),(9,2),(10,2)的SPECK32算法對應(yīng)的積分區(qū)分器的輪數(shù)比用原始參數(shù)(7,2)時少一輪,具有更強的抵抗積分分析的能力.同樣對于SPECK48算法,固定β=3時,移位參數(shù)為(11,3),(12,3),(13,3),(14,3),(15,3),(16,3)的 SPECK算法比原算法具有更強的抵抗積分分析的能力.而對于SPECK64算法,移位參數(shù)為(15,3),(16,3),(17,3),(18,3),(19,3),(20,3)的SPECK算法比原算法具有更強的抵抗積分分析的能力.

4 SPECK型算法的不可能差分分析

本節(jié)將利用中間相錯方法給出對SPECK型算法不可能差分分析的結(jié)果.文獻[21]刻畫了如下模加運算的差分擴散性質(zhì).

引理 1[21]設(shè)模加運算記為z=f(x,y)=x+ymod 2n,不妨設(shè)向量a=(a0,···,an?1),b=(b0,···,bn?1)為輸入差分,向量c=(c0,···,cn?1)為相應(yīng)的輸出差分. 另外記la=max{k|ak=1,ak+1=···=an?1=0},lb=max{k|bk=0,bk+1=···=bn?1=0},則有如下性質(zhì):

(1)若la=lb=l,則cl=···=cn?1=0,且對于 0≤i

(2)若la?=lb,設(shè)l=max(la,lb),則cl=1,cl+1=···=cn?1=0,且對于 0≤i

對于 SPECK 32算法,我們發(fā)現(xiàn)若該算法存在某r輪不可能差分特征,其輸出差分形如(00···0 10···0), 則可以自然拓展一輪, 得到輸出差分形如 (10···0 10···10) 的 (r+1) 輪不可能差分特征(參見圖2).采用大分組和其它移位參數(shù)(α,β)的SPECK型算法也有類似的性質(zhì).下面重點關(guān)注不同移位參數(shù)對應(yīng)的這類不可能差分特征的輪數(shù).

根據(jù)上面的分析,對于SPECK(α,β)算法,為了節(jié)約搜索時間,我們在搜索SPECK型算法的不可能差分特征時,限定輸入差分為單位向量,即滿足且輸出差分?Output0=(v0,···,v2n?1)滿足v0=vn=v2n?β=1,其余位置為 0.具體搜索流程如下:

步驟1:對選定的輸入差分?Input0進行加密,若第rin+1輪的輸出差分滿足所有位置取值均不確定,則記rin為加密最大輪數(shù);

步驟2:類似步驟1的方法,對于選定的輸出差分?Output0同樣可以得到解密最大輪數(shù),記為rout,同時記rtotal=rin+rout;

步驟3:對滿足r1+r2=rtotal的所有組合(r1,r2),判斷中間狀態(tài)的差分?Inputr1和?Outputr2是否存在某些位置比特相互矛盾,若存在則返回一條rtotal輪的不可能差分特征,否則rtotal=rtotal?1并重復步驟3;

步驟4:對所有的重復步驟1–3.

根據(jù)上述步驟,我們對采用不同移位參數(shù)(α,β)的SPECK型算法的不可能差分特征進行了搜索.對于不同分組長度的SPECK型算法,固定β為原算法的移位參數(shù),當移位參數(shù)α變化時,表3列出了不同參數(shù)下能夠找到的不可能差分特征的輪數(shù).

表3 SPECK型算法的不可能差分特征的輪數(shù)(32/48/64比特分組)Table 3 Round of impossible differentials of SPECK-like algorithm(32/48/64-bit block)

從表中數(shù)據(jù)可以看出,在減輪情形下,當固定β=2,移位參數(shù)為 (2,2),(3,2),(4,2),(9,2),(10,2),(11,2)的 SPECK 32算法的不可能差分特征的輪數(shù)比選用原始參數(shù) (7,2)時少一輪,具有更強的抵抗不可能差分分析的能力.同樣對于 SPECK 48算法,當固定β=3時,移位參數(shù)為 (3,3),(4,3),(5,3),(6,3),(14,3),(15,3),(16,3)的 SPECK算法比原算法具有更強的抵抗不可能差分分析的能力.而對于SPECK 64算法,移位參數(shù)為 (3,3),(4,3),(5,3),(6,3),(18,3),(19,3),(20,3)的 SPECK算法比原算法具有更強的抵抗不可能差分分析的能力.

5 總結(jié)

本文分析了當移位參數(shù)變化時,不同分組長度的 SPECK型算法抵抗積分分析和不可能差分分析的能力.基于MILP方法和中間相錯方法,我們給出了不同移位參數(shù)對應(yīng)的SPECK算法的積分區(qū)分器和不可能差分特征的輪數(shù).結(jié)合Biryukov等[17]關(guān)于SPECK型算法差分分析的結(jié)論,我們發(fā)現(xiàn)當考慮減輪版本的SPECK型算法的安全性能時,采用移位參數(shù) (9,2)的 SPECK32算法比原始算法具有更強的抵抗差分分析、積分分析和不可能差分分析的能力.當分組長度為48比特時,與原始參數(shù)(8,3)相比,采用移位參數(shù)(4,3)和(5,3)的SPECK算法在抵抗差分分析和不可能差分分析時有著較好的優(yōu)勢,而采用移位參數(shù)(13,3)的SPECK算法在抵抗差分分析和積分分析上的表現(xiàn)更好.當分組長度為64比特時,采用移位參數(shù) (18,3),(19,3),(20,3)的 SPECK算法比原始算法具有更好的抵抗積分分析和不可能差分分析能力,而采用移位參數(shù)(4,3),(5,3)的SPECK算法具有更好的抵抗差分分析和不可能差分分析能力,采用移位參數(shù)(15,3)的SPECK算法具有更好的抵抗差分分析和積分分析能力.