新的低輪Keccak線性結(jié)構(gòu)設(shè)計(jì)

劉曉強(qiáng),韋永壯,劉爭(zhēng)紅

(1.廣西密碼學(xué)與信息安全重點(diǎn)實(shí)驗(yàn)室(桂林電子科技大學(xué)),廣西 桂林 541004;2.廣西無(wú)線寬帶通信與信號(hào)處理重點(diǎn)實(shí)驗(yàn)室(桂林電子科技大學(xué)),廣西 桂林 541004; 3.廣西高校云計(jì)算與復(fù)雜系統(tǒng)重點(diǎn)實(shí)驗(yàn)室(桂林電子科技大學(xué)),廣西 桂林 541004)(*通信作者電子郵箱walker_wyz@guet.edu.cn)

0 引言

鑒于MD5(Message-Digest Algorithm 5)及SHA-1(Secure Hash Algorithm 1)等主流Hash算法被成功攻破[1],2007年美國(guó)國(guó)家標(biāo)準(zhǔn)與技術(shù)研究院(National Institute of Standards and Technology, NIST)開(kāi)展了SHA-3標(biāo)準(zhǔn)的征集活動(dòng)[2]。經(jīng)歷三輪的篩選,NIST最終在2012年10月2日宣布SHA-3競(jìng)賽的獲勝算法是Keccak算法[3],并于2015年8月將標(biāo)準(zhǔn)化的Keccak作為SHA-3標(biāo)準(zhǔn)[4]1-2。Keccak算法由比利時(shí)密碼研究組Bertoni 等[5]領(lǐng)銜設(shè)計(jì),該算法基于新穎的海綿結(jié)構(gòu),具有有效抵抗碰撞攻擊、原像攻擊和第二原像攻擊等能力,同時(shí)兼顧快速軟、硬件實(shí)現(xiàn)的優(yōu)勢(shì)[6]。

自2007年起,由于Keccak算法全球應(yīng)用的廣泛性和重要性,針對(duì)Keccak的多種攻擊方法被相繼提出和研究:文獻(xiàn)[7]中針對(duì)Keccak-224、Keccak-256提出了4輪實(shí)際碰撞;文獻(xiàn)[8]中針對(duì)SHAKE128(Secure Hash Algorithm Keccak 128)[4]20-21和兩個(gè)Keccak挑戰(zhàn)[9](Keccak[r=1 440]、Keccak[r=640])給出了5輪的實(shí)際碰撞攻擊;文獻(xiàn)[10]針對(duì)Keccak-224給出了5輪的實(shí)際碰撞，針對(duì)Keccak挑戰(zhàn)Keccak[r=1 440] 給出了6輪的實(shí)際碰撞攻擊；文獻(xiàn)[11]中對(duì)Keccak進(jìn)行了8輪實(shí)際區(qū)分攻擊;文獻(xiàn)[12]中對(duì)Keccak進(jìn)行了9輪實(shí)際區(qū)分攻擊;文獻(xiàn)[13]中對(duì)Keccak-224/256/384/512進(jìn)行了15輪理論區(qū)分攻擊、11輪實(shí)際區(qū)分攻擊,并針對(duì)Keccak-224/256、SHAKE128和Keccak挑戰(zhàn)Keccak[r=1 440]進(jìn)行了4輪實(shí)際原像攻擊。

研究表明,針對(duì)Keccak算法S盒層的線性分解方法[7-8, 10-13]是當(dāng)前研究關(guān)鍵點(diǎn)之一,同時(shí)這種線性思想已經(jīng)被應(yīng)用到Keccak的幾個(gè)變體算法分析中[14-15]。文獻(xiàn)[13]中首次提出了線性結(jié)構(gòu)的概念,并使用這種線性化思想,針對(duì)2輪順S盒層變換及1輪逆S盒層變換進(jìn)行線性分解,進(jìn)而設(shè)計(jì)出多個(gè)零和區(qū)分器。一方面,多輪S盒層線性分解的普遍方法都是順S盒方向進(jìn)行分析,很少進(jìn)行逆盒的分析,主要的原因是Keccak算法的S盒非線性部件χ的代數(shù)次數(shù)為2,而χ-1的代數(shù)次數(shù)為3,當(dāng)?shù)啍?shù)多時(shí),逆向分析似乎需要花銷(xiāo)更高的時(shí)間復(fù)雜度。如何針對(duì)多輪逆S盒層變換下,給出新的線性分解方法,并降低其復(fù)雜度是目前亟待解決的問(wèn)題。另一方面,如何構(gòu)建多種新型的零和區(qū)分器也值得進(jìn)一步的探討。

本文利用Keccak算法的S盒代數(shù)性質(zhì),針對(duì)多輪逆S盒層變換,設(shè)計(jì)了一種新的線性結(jié)構(gòu)。在S盒層輸入比特固定約束條件下,確保狀態(tài)數(shù)據(jù)經(jīng)過(guò)線性結(jié)構(gòu)的輸出值仍具有線性關(guān)系。通過(guò)這種線性分解的方法,結(jié)合中間相遇攻擊的思想[16],從Keccak算法的某個(gè)中間狀態(tài)作為攻擊點(diǎn)(以概率為1),構(gòu)造了新的零和區(qū)分器,并給出新的零和區(qū)分器的性能分析。

1 Keccak算法

1.1 Keccak Sponge結(jié)構(gòu)

如圖1所示,Keccak的整體結(jié)構(gòu)是海綿結(jié)構(gòu)。其中：N表示任意長(zhǎng)度的消息；Z表示算法的輸出；Keccak-f為算法的置換函數(shù)；b=r+c為置換寬度；r為比特率,表示外部狀態(tài),和輸入消息塊的長(zhǎng)度一致；c為容量,表示內(nèi)部狀態(tài)。被選為SHA-3標(biāo)準(zhǔn)的Keccak算法b=1 600比特,有24輪的置換操作,包含4種輸出長(zhǎng)度,Z∈{224,256,384,512}。

圖1 海綿結(jié)構(gòu)[4]18Fig.1 Sponge structure[4]18

海綿結(jié)構(gòu)分為兩個(gè)階段:吸收階段和擠壓階段。在吸收階段,輸入的消息N需要經(jīng)過(guò)特殊的填充,將消息N分為長(zhǎng)度均為r的消息塊p0、p1、…、pn-1。填充的方式為在消息N末尾添加1、0、…、0、1,使得填充后的消息N的長(zhǎng)度是r的整數(shù)倍。之后,每一個(gè)消息塊都異或前一輪經(jīng)過(guò)Keccak-f的輸出值,c內(nèi)部的值不變,這個(gè)整體作為下一輪置換的輸入。在擠壓階段,可根據(jù)Keccak版本的選擇,從置換的輸出值提取一個(gè)固長(zhǎng)Z的Hash值。

如圖2(a)所示,當(dāng)消息放入Keccak-f時(shí),算法的內(nèi)部狀態(tài)相當(dāng)于的一個(gè)5×5×64的三維比特?cái)?shù)組A[x,y,z],其二維比特?cái)?shù)組A[x,y]的表示如圖2(b)所示,消息存放的對(duì)應(yīng)關(guān)系為f[64(5y+x)+z]=A[x,y,z]。Keccak-f每輪迭代的輪函數(shù)R由5個(gè)部件構(gòu)成,R=θ°ρ°π°χ°ι，其中:

ρ:A′[x,y,z]=A[x,y]<<

π:A′[y,2x+3y]=A[x,y]

χ:A′[x,y]=A[x,y]?((A[x+1,y]?1)·

A[x+2,y])

ι:A′[0,0]=A[0,0]?RC

其中:RC表示一個(gè)64比特的輪常數(shù);r(x,y)為ρ部件運(yùn)算的一個(gè)常數(shù),表示針對(duì)二維狀態(tài)A[x,y]的z軸進(jìn)行移位操作,如圖3(a)所示。

圖2 數(shù)據(jù)狀態(tài)Fig. 2 Status of data

圖3 z軸循環(huán)位數(shù)Fig.3 z-axis cycle count

1.2 逆Keccak-f

逆Keccak-f指的是Keccak算法進(jìn)行逆方向上的迭代操作,逆向迭代的輪函數(shù)R-1同樣由5個(gè)逆部件ι-1、χ-1、π-1、ρ-1和θ-1構(gòu)成,R-1=ι-1°χ-1°π-1°ρ-1°θ-1。其中:

ι-1:A[0,0]=A′[0,0]?RC

χ-1:A[x,y]=(A[x+2,y]?(A[x+2,y]?1)·

A[x+3,y])·(A[x+1,y]?1)?A′[x,y]

π-1:A[x,y]=A′[y,2x+3y]

ρ-1:A[x,y,z]=A′[x,y]<<

其中:r-1(x,y)是個(gè)常數(shù),表示逆過(guò)程z軸所移位數(shù),如圖3(b)所示。

通過(guò)簡(jiǎn)單的邏輯計(jì)算,經(jīng)過(guò)ι-1、χ-1、π-1、ρ-1等逆部件的每一比特值,都可以直接根據(jù)Keccak-f中ι、χ、π、ρ得到,故而本文沒(méi)有給出具體推導(dǎo)過(guò)程。在分析過(guò)程中發(fā)現(xiàn):由于θ、θ-1部件都具有較強(qiáng)的擴(kuò)散性,且每一比特輸出值都受到兩個(gè)列和比特值影響,這種列和比特狀態(tài)被稱(chēng)為列奇偶核(Column Parity kernel, CP-kernel),簡(jiǎn)稱(chēng)CP核[17]。

利用CP核的概念,本文通過(guò)解線性方程組的方式求解θ-1的輸出比特,下面給出具體的推導(dǎo)過(guò)程:

已知θ部件:

(1)

若已知A00、A01、A02、A03和A04,根據(jù)式(1),可求解其經(jīng)過(guò)θ的輸出值:

則x=0時(shí)CP核的值為:

化簡(jiǎn)得:

(2)

同理，x=1,2,3,4的列和輸出值為:

(3)

(4)

(5)

(6)

2 θ部件和χ部件特性分析

通過(guò)對(duì)θ、ρ、π、χ、ι共5個(gè)部件進(jìn)行分析,研究發(fā)現(xiàn)ρ、π、ι及其逆部件均屬于線性運(yùn)算,且其輸出結(jié)果均保持線性。θ部件屬于線性操作,但變量經(jīng)過(guò)θ部件會(huì)擴(kuò)散到周?chē)忍貎?nèi);χ部件是一個(gè)類(lèi)S盒部件,屬于非線性操作,變量經(jīng)過(guò)χ部件會(huì)相互影響。因此,本文將著重分析θ部件和χ部件的特性,并研究其線性化的可能。

2.1 θ部件特性

在θ部件運(yùn)行過(guò)程中,發(fā)現(xiàn)θ部件具有一定擴(kuò)散性,變量經(jīng)過(guò)θ部件會(huì)產(chǎn)生更多的變量比特,這種擴(kuò)散會(huì)大幅增加經(jīng)過(guò)χ部件的數(shù)據(jù)復(fù)雜度,不利于線性化操作。同時(shí),研究發(fā)現(xiàn)CP核影響著θ部件的擴(kuò)散強(qiáng)弱,下面將進(jìn)一步分析一下CP核特性以及其對(duì)θ部件的影響:

推論1 若狀態(tài)A中每一個(gè)CP核P(A)=0,則列和影響最小,經(jīng)過(guò)θ的狀態(tài)A一定差分不擴(kuò)散。

推論2 若狀態(tài)A中每一個(gè)CP核P(A)=a,a為等于0或1的常數(shù),則經(jīng)過(guò)θ的狀態(tài)A一定線性,且變量不擴(kuò)散。

2.2 χ部件特性

χ部件是Keccak內(nèi)唯一的非線性部件 (相當(dāng)于一個(gè)非線性S盒),該部件的代數(shù)次數(shù)為2,故順n輪的Keccak算法的代數(shù)次數(shù)為2n。

若χ部件的輸入為ai(i=0,1,2,3,4),其輸出bi為:

(7)

研究發(fā)現(xiàn)若對(duì)輸入的比特值進(jìn)行部分約束,保證χ輸出值代數(shù)次數(shù)為1,那么非線性運(yùn)算χ就可以轉(zhuǎn)換成線性運(yùn)算。故當(dāng)ai、ai+2為變量,ai+1、ai+3和ai+4為一個(gè)0或1的常數(shù)時(shí),χ部件的輸出值代數(shù)次數(shù)為1。

引理1 若ai、ai+2為變量,ai+1=0,ai+3=1,ai+4=0時(shí),χ運(yùn)算的輸出比特具有線性關(guān)系。

證明 根據(jù)式(7),已知a0、a2為變量,a1=0,a3=1,a4=0,則此時(shí)輸出比特值bi為:

輸出比特bi的代數(shù)次數(shù)為1,故ai、ai+2為變量,ai+1=0,ai+3=1,ai+4=0時(shí),χ運(yùn)算的輸出比特一定線性。

2.3 χ-1部件特性

同理,χ-1部件是逆Keccak內(nèi)非線性部件,這個(gè)部件的代數(shù)次數(shù)為3,故m輪的逆Keccak代數(shù)次數(shù)為3m。

若χ-1部件的輸入為bi(i=0,1,2,3,4),其輸出ai為:

(8)

同理χ部件,若對(duì)χ-1輸入的比特值進(jìn)行部分約束時(shí),并保證χ-1輸出值的代數(shù)次數(shù)為1,則非線性運(yùn)算χ-1同樣可以轉(zhuǎn)換成線性運(yùn)算。

引理2 若bi、bi+2為變量,bi+1=0,bi+3=0,bi+4=1時(shí),χ-1運(yùn)算的輸出比特具有線性關(guān)系。

證明 根據(jù)式(8),已知b0、b2為變量,b1=0,b3=0,b4=1,此時(shí)輸出比特值ai為:

輸出比特ai的代數(shù)次數(shù)為1,故設(shè)定bi、bi+2為變量,bi+1=0,bi+3=0,bi+4=1時(shí),χ-1運(yùn)算的輸出比特一定線性。

引理3 若bi、bi+2為變量,bi+1=1,bi+3=0,bi+4=1時(shí),χ-1運(yùn)算的輸出值具有線性關(guān)系。

證明 根據(jù)式(8),已知b0、b2為變量,b1=1,b3=0,b4=1,此時(shí)輸出比特值ai為:

輸出比特ai的代數(shù)次數(shù)為1,故設(shè)定bi、bi+2為變量,bi+1=1,bi+3=0,bi+4=1時(shí),χ-1運(yùn)算的輸出比特一定線性。

3 新的線性結(jié)構(gòu)

線性結(jié)構(gòu)是2016年Guo等[13]首次定義的。線性結(jié)構(gòu)是指攻擊者在選定某一中間狀態(tài)作為初始狀態(tài),通過(guò)代數(shù)的方式對(duì)初始位置進(jìn)行線性擴(kuò)展,在不增加復(fù)雜度的同時(shí),完成了前向n輪和逆向m輪的線性分析。文獻(xiàn)[13]在概率為1、不增加復(fù)雜度的情況下,構(gòu)建的線性結(jié)構(gòu)使得某中間狀態(tài)前向2輪、逆向1輪的輸出比特都具有線性關(guān)系。不同的是,新的線性結(jié)構(gòu)考慮的是初始狀態(tài)逆向2輪、前向1輪的輸出比特之間的線性關(guān)系。

新的線性結(jié)構(gòu)中約定：淺灰色塊表示該位置比特值是活躍的，白色塊表示該位置比特值為定值0，深灰色塊表示該位置比特值為定值1。

由于ι和ι-1部件均只針對(duì)A00進(jìn)行線性運(yùn)算,即A00所表示的64比特?cái)?shù)據(jù)異或一個(gè)輪常數(shù)RC。在新的線性結(jié)構(gòu)中,設(shè)定A00為變量,當(dāng)初始狀態(tài)嚴(yán)格按照引理1、引理2或引理3對(duì)變量之外的比特值進(jìn)行特殊設(shè)定時(shí),設(shè)定任意的RC值,其輸出比特一定線性,故本文約定RC=0。

定理1 若初始狀態(tài)A00、A04、A12、A13、A20、A21、A33、A34、A41和A42位置的比特值為變量;初始狀態(tài)A03、A11、A24、A32和A40位置的比特值為常數(shù)1;初始狀態(tài)余下比特值為常數(shù)0,那么,初始狀態(tài)的逆1輪Keccak-f的輸出比特具有線性關(guān)系。

證明 如圖4所示,設(shè)定A00、A04、A12、A13、A20、A21、A33、A34、A41和A42為變量;設(shè)A03、A11、A24、A32和A40為定值1;余下比特值設(shè)定為定值0。

圖4 逆1輪Keccak-f運(yùn)算過(guò)程Fig.4 1-round backward of Keccak-f operation

初始狀態(tài)經(jīng)過(guò)特殊設(shè)定后,滿足引理2,則經(jīng)過(guò)χ-1部件的輸出比特具有線性關(guān)系,變量不會(huì)影響到其他比特位的值。

已知ι-1、ρ-1、π-1、θ-1部件均為線性部件,則經(jīng)過(guò)ι-1、ρ-1、π-1、θ-1的輸出值仍保持線性關(guān)系,故新的線性結(jié)構(gòu)在代數(shù)次數(shù)為1的情況下,可以進(jìn)行1輪逆Keccak-f運(yùn)算。

其中:盡管θ-1部件是線性部件,但由于不確定CP核的奇偶性,圖4中的輸出值A(chǔ)01、A02、A03、A10、A11、A14、A22、A23、A24、A30、A31、A32、A40、A43和A44可能是活躍的。

定理2 若初始狀態(tài)A00、A04、A12、A13、A20、A21、A33、A34、A41和A42位置的比特值為變量;初始狀態(tài)A03、A11、A24、A32和A40位置的比特值為常數(shù)1;初始狀態(tài)余下比特值為常數(shù)0,且滿足約束條件:

A00<<<0⊕A13<<<28⊕A21<<<61⊕A34<<<23⊕A42<<<46=0

A04<<<2⊕A12<<<58⊕A20<<<21⊕A33<<<49⊕A41<<<3=1

那么,初始狀態(tài)的逆2輪Keccak-f的輸出比特具有線性關(guān)系。

證明 如圖5所示,設(shè)定A00、A04、A12、A13、A20、A21、A33、A34、A41和A42為變量;設(shè)A03、A11、A24、A32和A40等位置為定值1;余下比特值設(shè)定為定值0。

圖5 逆2輪Keccak-f運(yùn)算過(guò)程Fig.5 2-rounds backward of Keccak-f operation

根據(jù)定理1,初始狀態(tài)進(jìn)入χ-1、ι-1、ρ-1、π-1和θ-1運(yùn)算后的輸出一定線性,但由于θ-1部件具有擴(kuò)散性,其輸入的變量會(huì)擴(kuò)散到周?chē)忍刂怠D4中的A01、A02、A03、A10、A11、A14、A22、A23、A24、A30、A31、A32、A40、A43和A44等輸出值可能是活躍的。

根據(jù)推論2,為了保證經(jīng)過(guò)θ-1后變量并不擴(kuò)散到周?chē)忍刂?要求所有列和值為一個(gè)0或1的常數(shù),于是設(shè)定2×64比特的約束條件:

A00<<<0⊕A13<<<28⊕A21<<<61⊕A34<<<23⊕A42<<<46=0

A04<<<2⊕A12<<<58⊕A20<<<21⊕A33<<<49⊕A41<<<3=1

此時(shí),經(jīng)過(guò)部件θ-1的輸出會(huì)保持線性關(guān)系,且變量不進(jìn)行擴(kuò)散。因此,初始狀態(tài)經(jīng)過(guò)1輪逆Keccak-f運(yùn)算,其輸出比特仍保持線性關(guān)系,且變量不發(fā)生擴(kuò)散。

在如圖5所示的第2個(gè)逆Keccak-f運(yùn)算中,χ-1部件的輸入數(shù)據(jù)比特值滿足引理3,故經(jīng)過(guò)χ-1部件輸出的數(shù)據(jù)依舊是線性的。同理,根據(jù)部件π-1、ρ-1、θ-1的特性,發(fā)現(xiàn)逆2輪的運(yùn)算結(jié)果仍保持線性關(guān)系。因此,新的線性結(jié)構(gòu)在代數(shù)次數(shù)為1的情況下,可以進(jìn)行2輪逆Keccak-f運(yùn)算。同理,由于不確定逆2輪CP核的奇偶性,經(jīng)過(guò)第2輪θ-1部件的A01、A02、A03、A10、A11、A14、A22、A23、A24、A30、A31、A32、A40、A43和A44等輸出值可能是活躍的。

值得注意的是:在新的線性結(jié)構(gòu)演算過(guò)程中,研究發(fā)現(xiàn)經(jīng)過(guò)2輪逆Keccak-f運(yùn)算后,每一個(gè)輸出值都可能是活躍的,無(wú)法再通過(guò)加約束條件的方式來(lái)減少活躍比特個(gè)數(shù),故新的線性結(jié)構(gòu)只能保證初始狀態(tài)逆向2輪的輸出比特保持線性關(guān)系。

定理3 若初始狀態(tài)A00、A04、A12、A13、A20、A21、A33、A34、A41和A42等位置的比特值為變量;初始狀態(tài)A03、A11、A24、A32和A40等位置比特值為常數(shù)1;初始狀態(tài)余下比特值為常數(shù)0,且滿足約束條件:A00=A04,A12=A13,A20=A21,A41=A42,A33=A34。那么,初始狀態(tài)的順1輪Keccak-f的輸出比特具有線性關(guān)系。

證明 如圖6所示,設(shè)定A00、A04、A12、A13、A20、A21、A33、A34、A41和A42為變量;設(shè)A03、A11、A24、A32和A40為定值1;余下比特值設(shè)定為定值0。

圖6 順1輪Keccak-f運(yùn)算過(guò)程Fig.6 1-round forward of Keccak-f operation

根據(jù)推論1,為了保證經(jīng)過(guò)θ部件后,變量不進(jìn)行擴(kuò)散,要求所有列和值為0,于是設(shè)定5×64比特的約束條件:A00=A04,A12=A13,A20=A21,A41=A42,A33=A34。

在如圖6所示的順1輪Keccak-f運(yùn)算過(guò)程中,χ部件的輸入比特值滿足引理1,則經(jīng)過(guò)χ部件輸出的數(shù)據(jù)仍保持線性關(guān)系。同理,根據(jù)部件π、ρ、ι的特性,發(fā)現(xiàn)順1輪Keccak-f的運(yùn)算結(jié)果最終保持線性關(guān)系。因此,新的線性結(jié)構(gòu)在代數(shù)次數(shù)為1的情況下,可以進(jìn)行1輪順Keccak-f運(yùn)算。

因此,在新的線性結(jié)構(gòu)中,結(jié)合定理1、定理3可以進(jìn)行2輪的線性拓展,并對(duì)Keccak進(jìn)行順1輪、逆1輪密碼分析;結(jié)合定理2、定理3可以進(jìn)行3輪的線性拓展,并對(duì)Keccak進(jìn)行順1輪、逆2輪密碼分析,其輸出值均保持線性關(guān)系。

4 零和區(qū)分器

2009年,Aumasson等[12]首次提出了零和區(qū)分器的概念,并使用這種零和區(qū)分器分別對(duì)Keccak和逆Keccak進(jìn)行了區(qū)分攻擊,其結(jié)果如表1所示。

Keccak-f的代數(shù)次數(shù)為2,逆Keccak-f的次數(shù)為3,零和區(qū)分器從Keccak中的某輪內(nèi)部狀態(tài)開(kāi)始,進(jìn)行前向n輪、逆向m輪的操作,代數(shù)次數(shù)分別為2n、3m,則自由變量的總數(shù)為max(2n,3m),因此,構(gòu)造零和區(qū)分器時(shí)間、數(shù)據(jù)復(fù)雜度至少為21+max(2n,3m)。

在新的線性結(jié)構(gòu)中,本文通過(guò)代數(shù)的方式對(duì)初始狀態(tài)進(jìn)行了線性擴(kuò)展,構(gòu)建了最佳的線性空間SM,使得初始狀態(tài)經(jīng)過(guò)1輪或2輪的輸出代數(shù)次數(shù)恒為1。當(dāng)線性空間SM的值滿足:SM≥21+max(2n,3m)時(shí),就可以使用新的線性結(jié)構(gòu)來(lái)構(gòu)建新的零和區(qū)分器,對(duì)Keccak算法進(jìn)行區(qū)分器攻擊。

根據(jù)定理1和定理3,可以構(gòu)建一個(gè)新的順1輪、逆1輪的零和區(qū)分器,新的零和區(qū)分器在不增加復(fù)雜度的同時(shí),可以多進(jìn)行順1輪、逆1輪的運(yùn)算。故當(dāng)復(fù)雜度同樣為21+max(2n,3m)時(shí),新的零和區(qū)分器可以進(jìn)行順n+1輪、逆m+1的區(qū)分攻擊,自由變量個(gè)數(shù)為max(2n+1,3m+1),做到Keccak的(n+m+2)輪,其攻擊情況如表1所示。

新的順1輪、逆1輪的零和區(qū)分器中,當(dāng)n=5、m=8時(shí),自由變量為729比特,復(fù)雜度為2257。結(jié)合定理1和定理3,設(shè)定初始變量為10×64比特,存在5×64比特的約束條件,實(shí)際使用2320比特的自由變量,線性空間SM為2320(?2257),故新的零和區(qū)分器可以對(duì)Keccak進(jìn)行15輪的區(qū)分攻擊。

同理,在新的線性結(jié)構(gòu)中,根據(jù)定理2和定理3,可以構(gòu)建新的順1輪、逆2輪零和區(qū)分器,使用新的線性結(jié)構(gòu)所構(gòu)建的零和區(qū)分器在不增加復(fù)雜度的同時(shí),可以多進(jìn)行順1輪、逆2輪的運(yùn)算。故當(dāng)復(fù)雜度同樣為21+max(2n,3m)時(shí),新的零和區(qū)分器進(jìn)行順n+1輪、逆m+2的區(qū)分攻擊,自由變量個(gè)數(shù)為max(2n+1,3m+2),做到Keccak的(n+m+3)輪,其攻擊情況如表1所示。

新的順1輪、逆2輪的零和區(qū)分器中,當(dāng)n=7、m=4時(shí),自由變量為729比特,復(fù)雜度為2129。結(jié)合定理2和定理3,設(shè)定初始變量為10×64比特,存在7×64比特的約束條件,實(shí)際使用192比特的自由變量,線性空間SM為2192(?2129),故新的零和區(qū)分器可以對(duì)Keccak進(jìn)行14輪的區(qū)分攻擊。

5 區(qū)分器性能分析

新的順1輪、逆1輪零和區(qū)分器與文獻(xiàn)[12]區(qū)分器相比,可以做到目前最好的理論15輪攻擊。如表1所示,對(duì)Keccak算法進(jìn)行前向9輪、逆向6輪的區(qū)分攻擊時(shí),文獻(xiàn)[12]區(qū)分器的復(fù)雜度為2511.68,本文區(qū)分器的復(fù)雜度為2257。注意到,當(dāng)攻擊輪數(shù)相同時(shí),兩種區(qū)分器的自由變量數(shù)量相同,但這種線性化思想與過(guò)去的區(qū)分攻擊相比,極大程度上降低了數(shù)據(jù)復(fù)雜度。

如表1所示,對(duì)Keccak算法進(jìn)行14輪區(qū)分攻擊時(shí),文獻(xiàn)[13]提供了前向9輪、逆向5輪的區(qū)分器組合方式,自由變量個(gè)數(shù)為512,而本文提供的區(qū)分器組合方式是前向8輪、逆向6輪,自由變量個(gè)數(shù)為729。新的順1輪、逆2輪零和區(qū)分器與文獻(xiàn)[13]區(qū)分器相比,新的零和區(qū)分器攻擊Keccak算法的輪數(shù)并沒(méi)有提高,但新的零和區(qū)分器具有更多的自由變量,同時(shí)提供了更豐富的區(qū)分器組合方式。

表1 新的零和區(qū)分器性能Tab. 1 Performance of new zero-sum distinguishers

6 結(jié)語(yǔ)

本文基于Keccak算法S盒的代數(shù)性質(zhì),針對(duì)多輪逆S盒層變換,通過(guò)線性化的思想,給出了一種新的線性結(jié)構(gòu)構(gòu)造方法,并利用該線性結(jié)構(gòu),進(jìn)一步提供了新的零和區(qū)分器的構(gòu)造方式。研究結(jié)果表明:使用線性化的思想可以有效降低區(qū)分攻擊的攻擊復(fù)雜度;在時(shí)間、數(shù)據(jù)復(fù)雜度相同的情況下,新的零和區(qū)分器具有自由變量更多、區(qū)分攻擊的組合方式更豐富等優(yōu)勢(shì)。然而為了防止算法過(guò)程中變量的增值、擴(kuò)散,必須要設(shè)定一些約束條件,這種操作會(huì)損失一定比特的自由變量,導(dǎo)致時(shí)間、數(shù)據(jù)的復(fù)雜度依舊很高,同時(shí)也不能再進(jìn)行更多輪數(shù)的線性化操作。如何更精準(zhǔn)地設(shè)定約束條件,并提高輪數(shù)的線性化操作是下一步的研究方向。