新的低輪Keccak線性結構設計

劉曉強,韋永壯,劉爭紅

(1.廣西密碼學與信息安全重點實驗室(桂林電子科技大學),廣西 桂林 541004;2.廣西無線寬帶通信與信號處理重點實驗室(桂林電子科技大學),廣西 桂林 541004; 3.廣西高校云計算與復雜系統重點實驗室(桂林電子科技大學),廣西 桂林 541004)(*通信作者電子郵箱walker_wyz@guet.edu.cn)

0 引言

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

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

研究表明,針對Keccak算法S盒層的線性分解方法[7-8, 10-13]是當前研究關鍵點之一,同時這種線性思想已經被應用到Keccak的幾個變體算法分析中[14-15]。文獻[13]中首次提出了線性結構的概念,并使用這種線性化思想,針對2輪順S盒層變換及1輪逆S盒層變換進行線性分解,進而設計出多個零和區分器。一方面,多輪S盒層線性分解的普遍方法都是順S盒方向進行分析,很少進行逆盒的分析,主要的原因是Keccak算法的S盒非線性部件χ的代數次數為2,而χ-1的代數次數為3,當迭代輪數多時,逆向分析似乎需要花銷更高的時間復雜度。如何針對多輪逆S盒層變換下,給出新的線性分解方法,并降低其復雜度是目前亟待解決的問題。另一方面,如何構建多種新型的零和區分器也值得進一步的探討。

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

1 Keccak算法

1.1 Keccak Sponge結構

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

圖1 海綿結構[4]18Fig.1 Sponge structure[4]18

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

如圖2(a)所示,當消息放入Keccak-f時,算法的內部狀態相當于的一個5×5×64的三維比特數組A[x,y,z],其二維比特數組A[x,y]的表示如圖2(b)所示,消息存放的對應關系為f[64(5y+x)+z]=A[x,y,z]。Keccak-f每輪迭代的輪函數R由5個部件構成,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表示一個64比特的輪常數;r(x,y)為ρ部件運算的一個常數,表示針對二維狀態A[x,y]的z軸進行移位操作,如圖3(a)所示。

圖2 數據狀態Fig. 2 Status of data

圖3 z軸循環位數Fig.3 z-axis cycle count

1.2 逆Keccak-f

逆Keccak-f指的是Keccak算法進行逆方向上的迭代操作,逆向迭代的輪函數R-1同樣由5個逆部件ι-1、χ-1、π-1、ρ-1和θ-1構成,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)是個常數,表示逆過程z軸所移位數,如圖3(b)所示。

通過簡單的邏輯計算,經過ι-1、χ-1、π-1、ρ-1等逆部件的每一比特值,都可以直接根據Keccak-f中ι、χ、π、ρ得到,故而本文沒有給出具體推導過程。在分析過程中發現:由于θ、θ-1部件都具有較強的擴散性,且每一比特輸出值都受到兩個列和比特值影響,這種列和比特狀態被稱為列奇偶核(Column Parity kernel, CP-kernel),簡稱CP核[17]。

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

已知θ部件:

(1)

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

則x=0時CP核的值為:

化簡得:

(2)

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

(3)

(4)

(5)

(6)

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

通過對θ、ρ、π、χ、ι共5個部件進行分析,研究發現ρ、π、ι及其逆部件均屬于線性運算,且其輸出結果均保持線性。θ部件屬于線性操作,但變量經過θ部件會擴散到周圍比特內;χ部件是一個類S盒部件,屬于非線性操作,變量經過χ部件會相互影響。因此,本文將著重分析θ部件和χ部件的特性,并研究其線性化的可能。

2.1 θ部件特性

在θ部件運行過程中,發現θ部件具有一定擴散性,變量經過θ部件會產生更多的變量比特,這種擴散會大幅增加經過χ部件的數據復雜度,不利于線性化操作。同時,研究發現CP核影響著θ部件的擴散強弱,下面將進一步分析一下CP核特性以及其對θ部件的影響:

推論1 若狀態A中每一個CP核P(A)=0,則列和影響最小,經過θ的狀態A一定差分不擴散。

推論2 若狀態A中每一個CP核P(A)=a,a為等于0或1的常數,則經過θ的狀態A一定線性,且變量不擴散。

2.2 χ部件特性

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

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

(7)

研究發現若對輸入的比特值進行部分約束,保證χ輸出值代數次數為1,那么非線性運算χ就可以轉換成線性運算。故當ai、ai+2為變量,ai+1、ai+3和ai+4為一個0或1的常數時,χ部件的輸出值代數次數為1。

引理1 若ai、ai+2為變量,ai+1=0,ai+3=1,ai+4=0時,χ運算的輸出比特具有線性關系。

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

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

2.3 χ-1部件特性

同理,χ-1部件是逆Keccak內非線性部件,這個部件的代數次數為3,故m輪的逆Keccak代數次數為3m。

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

(8)

同理χ部件,若對χ-1輸入的比特值進行部分約束時,并保證χ-1輸出值的代數次數為1,則非線性運算χ-1同樣可以轉換成線性運算。

引理2 若bi、bi+2為變量,bi+1=0,bi+3=0,bi+4=1時,χ-1運算的輸出比特具有線性關系。

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

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

引理3 若bi、bi+2為變量,bi+1=1,bi+3=0,bi+4=1時,χ-1運算的輸出值具有線性關系。

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

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

3 新的線性結構

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

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

由于ι和ι-1部件均只針對A00進行線性運算,即A00所表示的64比特數據異或一個輪常數RC。在新的線性結構中,設定A00為變量,當初始狀態嚴格按照引理1、引理2或引理3對變量之外的比特值進行特殊設定時,設定任意的RC值,其輸出比特一定線性,故本文約定RC=0。

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

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

圖4 逆1輪Keccak-f運算過程Fig.4 1-round backward of Keccak-f operation

初始狀態經過特殊設定后,滿足引理2,則經過χ-1部件的輸出比特具有線性關系,變量不會影響到其他比特位的值。

已知ι-1、ρ-1、π-1、θ-1部件均為線性部件,則經過ι-1、ρ-1、π-1、θ-1的輸出值仍保持線性關系,故新的線性結構在代數次數為1的情況下,可以進行1輪逆Keccak-f運算。

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

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

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

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

那么,初始狀態的逆2輪Keccak-f的輸出比特具有線性關系。

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

圖5 逆2輪Keccak-f運算過程Fig.5 2-rounds backward of Keccak-f operation

根據定理1,初始狀態進入χ-1、ι-1、ρ-1、π-1和θ-1運算后的輸出一定線性,但由于θ-1部件具有擴散性,其輸入的變量會擴散到周圍比特值。圖4中的A01、A02、A03、A10、A11、A14、A22、A23、A24、A30、A31、A32、A40、A43和A44等輸出值可能是活躍的。

根據推論2,為了保證經過θ-1后變量并不擴散到周圍比特值,要求所有列和值為一個0或1的常數,于是設定2×64比特的約束條件:

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

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

此時,經過部件θ-1的輸出會保持線性關系,且變量不進行擴散。因此,初始狀態經過1輪逆Keccak-f運算,其輸出比特仍保持線性關系,且變量不發生擴散。

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

值得注意的是:在新的線性結構演算過程中,研究發現經過2輪逆Keccak-f運算后,每一個輸出值都可能是活躍的,無法再通過加約束條件的方式來減少活躍比特個數,故新的線性結構只能保證初始狀態逆向2輪的輸出比特保持線性關系。

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

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

圖6 順1輪Keccak-f運算過程Fig.6 1-round forward of Keccak-f operation

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

在如圖6所示的順1輪Keccak-f運算過程中,χ部件的輸入比特值滿足引理1,則經過χ部件輸出的數據仍保持線性關系。同理,根據部件π、ρ、ι的特性,發現順1輪Keccak-f的運算結果最終保持線性關系。因此,新的線性結構在代數次數為1的情況下,可以進行1輪順Keccak-f運算。

因此,在新的線性結構中,結合定理1、定理3可以進行2輪的線性拓展,并對Keccak進行順1輪、逆1輪密碼分析;結合定理2、定理3可以進行3輪的線性拓展,并對Keccak進行順1輪、逆2輪密碼分析,其輸出值均保持線性關系。

4 零和區分器

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

Keccak-f的代數次數為2,逆Keccak-f的次數為3,零和區分器從Keccak中的某輪內部狀態開始,進行前向n輪、逆向m輪的操作,代數次數分別為2n、3m,則自由變量的總數為max(2n,3m),因此,構造零和區分器時間、數據復雜度至少為21+max(2n,3m)。

在新的線性結構中,本文通過代數的方式對初始狀態進行了線性擴展,構建了最佳的線性空間SM,使得初始狀態經過1輪或2輪的輸出代數次數恒為1。當線性空間SM的值滿足:SM≥21+max(2n,3m)時,就可以使用新的線性結構來構建新的零和區分器,對Keccak算法進行區分器攻擊。

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

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

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

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

5 區分器性能分析

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

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

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

6 結語

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