Piccolo 算法的相關密鑰-不可能差分攻擊?

徐林宏, 郭建勝, 崔競一, 李明明

(信息工程大學,河南 鄭州 450001)

隨著物聯網技術的不斷發展,人們對其安全性的要求也越來越高,適用于這些資源受限環境的密碼算法即輕量級密碼算法成為密碼學研究的一個熱點,大量輕量級密碼算法被設計出來,如 PRESENT[1],LBlock[2],PRINCE[3],SIMON[4]等算法.

Piccolo 算法是由日本密碼學家Shibutani 等人[5]于CHES 2011 上提出的一種適用于資源受限環境的輕量級分組密碼算法,其算法結構為廣義Feistel 結構,硬件實現效率較高.該算法一經提出,就受到學界的廣泛關注.

不可能差分分析是由Knudsen[6]和Biham[7]兩人獨自提出的單密鑰條件下的密碼分析方法,Knudsen 在分析高級加密標準的候選算法DEAL 的安全性時,提出了輪函數為雙射的Feistel 結構存在5 輪的不可能差分路徑;Biham 等人在FSE’99 上介紹了基于中間相錯的思想構造不可能差分的方法.此后,不可能差分在研究很多標準密碼算法的安全性時得到了廣泛應用,如AES[8],CLEFIA[9]等.

相關密鑰攻擊同樣是由Biham[10]和Knudsen[11]各自獨立提出的,其主要思想是:基于密碼算法密鑰擴展方式對算法安全性的影響,利用密鑰擴展算法的一些弱點,通過分析相關密鑰與原有密鑰之間的關系對加密結果造成的影響恢復出原有密鑰.該攻擊方法對于具有簡單密鑰擴展方式的密碼算法尤其有效.當前,主流應用是在此攻擊方法假設條件下,與其他密碼分析方法相結合,如差分分析、不可能差分分析、矩陣攻擊等,對算法進行安全性分析.因此,本文結合上述兩種攻擊方法,對Piccolo 算法進行了相關密鑰-不可能差分分析.

· 相關工作

現有的對于Piccolo 算法的安全性分析結果較多,這里主要介紹差分類分析結果.其中,利用Biclique 分析方法可得到對于全輪Piccolo-80 和Piccolo-128 算法低于窮舉復雜度的攻擊結果[12?14].在單密鑰條件下,Azimi 等人[15]于2014 年利用不可能差分分析方法,對含前向白化密鑰12 輪Piccolo-80 算法、不含白化密鑰的13 輪Piccolo-80 算法和含后向白化密鑰的15 輪Piccolo-128 算法進行了安全性分析;2015 年,Tolba 等人[16]給出了14輪Piccolo-80 不含白化密鑰和17 輪Piccolo-128 含后向白化密鑰的中間相遇攻擊結果;2017 年,Liu 等人[17]在文獻[16]基礎上進行改進,利用中間相遇攻擊方法,給出了不含白化密鑰的14 輪Piccolo-80 和含后向白化密鑰的的18 輪Piccolo-128 的安全性分析結果.在相關密鑰條件下,Minier[18]在2013 年結合相關密鑰攻擊和不可能差分分析,實現了對均不含白化密鑰的14 輪Piccolo-80 和21 輪Piccolo-128 的攻擊,但攻擊所需的數據量超過算法的分組規模264.2016 年,Zheng 等人[19]利用U-method 分別給出了Piccolo-80 和Piccolo-128 算法11 輪和17輪的相關密鑰-不可能差分區分器,但未能給出具體的安全性分析結果.

· 本文工作

本文主要使用相關密鑰-不可能差分分析方法評估了Piccolo 算法的安全性:首先,基于中間相錯思想和密鑰擴展的性質,尋找到所有可能的最長相關密鑰-不可能差分區分器;而后,利用輪函數等效結構減少攻擊所需選擇明(密)文量,給出了15 輪Piccolo-80 和21 輪Piccolo-128 算法的攻擊結果,所需數據復雜度和計算復雜度均低于窮舉分析.在不考慮Biclique 分析結果的情況下,均優于現有分析結果.本文攻擊結果見表1.

Table 1 Comparison of attack results on Piccolo表1 Piccolo 算法的攻擊結果對比

· 文章結構安排

本文首先介紹研究背景.第1 節主要介紹Piccolo 算法的相關知識.第2 節給出Piccolo-80 的相關密鑰-不可能差分分析結果.Piccolo-128 算法的相關密鑰-不可能差分分析主要在第3 節中給出.最后對全文進行總結.

1 相關知識

本節中,首先給出下文中一些常用符號說明,而后給出Piccolo 算法具體描述.

1.1 符號說明

· (P,P′):輸入明文狀態.

· (C,C′):輸出密文狀態.

·WKt:第t個白化密鑰,t∈{0,1,2,3}.

· (rk2r,rk2r+1):第r輪輪密鑰.

1.2 Piccolo算法簡介

Piccolo 算法的分組規模為64bits,根據密鑰規模不同,可分為Piccolo-80 和Piccolo-128 兩種,對應輪數分別為25(0～24)輪和31(0～30)輪.其加密環節主要由密鑰白化、F函數和字節置換操作組成.密鑰白化操作僅在第1輪和最后一輪存在,保證加脫密結構的一致性.輪變換包括F函數和字節置換,具體的Piccolo 算法輪函數各環節的結構示意圖詳見文獻[5]的圖1～圖4.輪函數各個環節和密鑰擴展算法的介紹如下給出.

·F函數

每一個F函數包含了8 個相同的4bits 雙射S盒和一個列混合矩陣M,通過對16bits 數據進行作用,實現算法的混亂和擴散.即有(x0(4),x1(4),x2(4),x3(4))t=M?(x0(4),x1(4),x2(4),x3(4))t,其中,列混合矩陣M的運算定義在由不可約多項式x4+x+1 生成的GF(24)上.

· 字節置換RP

該環節主要實現各字節的移位替換,即

· 密鑰擴展算法

Piccolo 算法的密鑰擴展有80bits 和128bits 密鑰兩種.其中,對于Piccolo-80,將80bits 主密鑰劃分為5 個部分,每個部分包括2 字節,即K=K0||K1||K2||K3||K4,其中,根據F函數中采用的是4bits的S盒,可對每一字節密鑰進行再劃分,即

白化密鑰WKj(j∈{0,1,2,3})由主密鑰直接生成,其中,

輪密鑰(rk2r,rk2r+1)由主密鑰與固定常數異或所得,r∈{0,…,24}.在Piccolo-128 中,增加了6 個字節的主密鑰,有K=K0||K1||K2||K3||K4||K5||K6||K7,相應的白化密鑰也有所變化,即

表2 和表3 分別給出了兩個版本Piccolo 算法輪子密鑰和主密鑰的對應關系.

Table 2 Correspondence between the master key and the round keys of Piccolo-80表2 Piccolo-80 算法的主密鑰與輪密鑰之間的對應關系

Table 3 Correspondence between the master key and the round keys of Piccolo-128表3 Piccolo-128 算法的主密鑰與輪密鑰之間的對應關系

2 15 輪Piccolo-80 算法的相關密鑰-不可能差分攻擊

本節中首先介紹了Piccolo 算法具有的3 點性質,而后基于中間相錯思想,分析了Piccolo-80 算法在狀態值和主密鑰值均僅有單比特塊差分活動的情況下,其能夠具有的所有最長11 輪相關密鑰-不可能差分區分器.通過選擇合適的區分器,向上向下各拓展兩輪,得到了15 輪Piccolo-80 含前向白化密鑰的安全性分析結果.

2.1 Piccolo算法性質

性質1(密鑰擴展算法性質).主要有以下3 個方面.

(1) 對于Piccolo 兩種密鑰規模的算法,除白化密鑰外,其每一主密鑰字Ki在各輪密鑰中分布的位置均與其第1 次出現的位置相同.具體來說,若主密鑰Ki第1 次出現在輪密鑰的左(右)半部分,則后續的均出現在輪密鑰的左(右)半部分.

(2) 在不考慮輪常數的影響時,對于Piccolo-80,其輪密鑰(除白化密鑰外)是由主密鑰構成的一個周期為5的循環.

(3) 對于Piccolo-128 算法,在不考慮輪常數的影響下,自第0 輪開始,其輪密鑰左半部分是按(K2,K4,K6,K2,K6,K0,K4,K6,K4,K2,K0,K4,K0,K6,K2,K0)排列的一個16 輪循環,右半部分是按(K3,K5,K7,K1,K7,K3,K5,K1,K5,K7,K3,K1)排列的一個12 輪循環.

證明:分別觀察表2、表3 中Piccolo-80 和Piccolo-128 主密鑰與輪密鑰間的對應關系,可得上述結論.□

性質2.根據算法結構中的F函數采用的是4bits 的S盒,且在字節置換操作中,實現的是對字節整體的移位操作,未改變各個字節內部每一比特的狀態,因此在引入明文差分時,可在與密鑰進行差分抵消的位置選取4bits 或8bits 差分,相應地選擇4bits 或8bits 的相關密鑰差分實現差分抵消.當選取明文差分為4bits 時,攻擊所需的相關密鑰量約為24,較差分選為8bits 時有所減少,具體應用見第2.3 節和第3.2 節.

性質3(輪函數等效結構)[12].改變Piccolo 算法中輪密鑰加的順序,不影響算法加解密效果,且根據輪密鑰加變換順序的不同有兩種算法輪函數的等效結構,具體結構如圖1 所示.

Fig.1 Equivalent structure of round function圖1 輪函數等效結構

在下文給出的攻擊過程中,利用性質3,通過在數據收集階段采用算法等效結構,可以有助于減少攻擊過程中的選擇明(密)文量,降低攻擊所需數據復雜度.這里僅以Piccolo-80 算法為例進行具體說明,對于Piccolo-128算法具有同樣的效果.

例1:對于Piccolo-80 算法,由圖2 的攻擊路徑可得:在數據收集階段使用算法等效結構,使得第14 輪不含密鑰加運算的作用,進而可由預計算直接得到滿足第14 輪的輸入狀態差分為(α,0,0,0,0,β,γ,0)的密文對.也就是說,對于2n個明文結構,所需的選擇密文量為2n+24.而若未使用算法等效結構,則根據密文差分中有6 個活動差分字節,攻擊所需的選擇密文量2n+48.進一步的,在攻擊計算復雜度相同的條件下,顯然,未使用等效結構所需的數據復雜度更高.

2.2 11輪相關密鑰-不可能差分區分器

根據算法輪函數結構,在不含相關密鑰差分,輸入狀態僅存在1 個差分活動比特塊時,算法達到完全性有兩種情況.

(1) 活動比特塊位于F函數的輸入,經過3 輪變換后,算法達到完全.

(2) 活動比特塊位于密鑰加操作的輸入,經過4 輪變換后,算法達到完全.

引入相關密鑰差分,一般用于實現與輸入狀態差分的相互抵消,得到更長的區分器,提升密鑰恢復攻擊時的輪數,所以說,密鑰差分選取的位置也十分關鍵.一般情況下,針對Piccolo 算法,所能構造區分器的最長輪數由同一主密鑰字在輪密鑰中連續出現5 次的相距輪數決定.但并不是說,所能構造的區分器輪數就一定達到相距輪數,還需受到算法達到完全性的輪數限制.此外,直觀地可以發現:若引入的密鑰差分和輸入狀態差分活動比特塊越多,算法達到完全所需的輪數越少.

綜合上述考慮,利用中間相錯思想,在主密鑰差分和輸入狀態差分均僅有1 個活動比特塊時構造區分器.特別地,當輪密鑰為(K4,K4)時,若在K4中引入一個差分活動塊,則為了實現差分抵消,需要在狀態差分中有2 個差分活動比特塊,此種情況的區分器也在本節考慮范圍內.由此,利用性質1,尤其是Piccolo-80 密鑰擴展中輪密鑰具有的5 輪循環性,能夠構造得到的Piccolo-80 的最長11 輪相關密鑰-不可能差分區分器主要有3 種情形,見表4.其中,密鑰差分選取在K0中與選取在K1中,所得的區分器情形基本一致,且根據差分選取的左右位置不同,共有12 種情況;密鑰差分選取在K2中與選取在K3中,所得的區分器情形一致,且與情形1 類似,也有12 種情況;密鑰差分選取在K4中時,根據差分選取的左右位置不同,共有6 種情況.綜上,能夠找到30 條11 輪Piccolo-80 的相關密鑰-不可能差分區分器.附錄A、附錄B 給出了3 種情形區分器的示例.

Table 4 11-round related-key impossible differential distinguishers of Piccolo-80表4 11 輪Piccolo-80 算法的相關密鑰-不可能差分區分器

由于本文攻擊中考慮前向白化密鑰對算法安全性的影響,因此密鑰差分選取在K0和K1中的區分器不適合用于攻擊環節.而為了使攻擊輪數盡可能長,且攻擊復雜度盡可能低,考慮選用輸入差分活動塊較少的區分器,故在下文的攻擊中,選用的區分器為情形2 中的區分器,且區分器的位置取為第2 輪～第12 輪,具體路徑見附錄A 中表A 的左半部分.特別指出:文獻[19]給出的Piccolo-80 區分器也是情形2 中的一種,且情形2 中的位于第12 輪～第22 輪的區分器也可用來分析15 輪Piccolo-80 算法僅含后向白化密鑰的安全性,具體攻擊過程和復雜度估計與下文給出的攻擊算法1、算法2 類似.

2.3 15輪密鑰恢復攻擊

根據上述構造所得區分器,向上解密2 輪,向下加密2 輪,基于分割攻擊思想,可對15 輪Piccolo-80 算法進行密鑰恢復,攻擊總共分為兩個階段:一為數據收集階段,二為密鑰猜測階段.本小節中根據選取密鑰差分的比特塊規模不同,給出了兩種攻擊算法,可以恢復出Piccolo-80 算法的全部80bits 主密鑰,具體的攻擊步驟基本類似,但在所需復雜度方面有一定差異,下面具體介紹這兩種攻擊算法.具體攻擊路徑如圖2 所示,其中,黑色表示差分活動比特塊,灰色標識差分值為γ的比特塊,差分不活動比特塊用白色標識.

Fig.2 15-round related-key impossible differential cryptanalysis of Piccolo-80圖2 15 輪Piccolo-80 算法相關密鑰-不可能差分分析

2.3.1 攻擊算法1

· Step 1.數據收集.

基于性質3,對于密文(C,C′),選擇其在第14 輪的輸入差分為(α,0,0,0,0,β,γ,0),其中,α,β,γ表示差分活動比特塊,且每一比特塊表示一個字節.則顯然:對于一個結構,需要選擇224個選擇密文,則得到247個密文對.當選定γ的一個非零取值時,因為有28?1 種可能,所以對應的密文對數量239個.此時選擇相應的密鑰差分篩選明文差分為(*,0,*,*,0,*,*,*)的密文對,予以保留,則平均剩余的密文對個數為239×2?16=223.構造2n個結構,當γ選定一個非零值時,可得到2n+23個平均剩余密文對.

· Step 2.密鑰猜測.

第2 步中具體介紹密鑰猜測階段的攻擊步驟,其中,Step 2.1～Step 2.4 是基于γ取定的情況,γ≠0.

? Step 2.1.對于選定的一個γ,根據已得到的密文對,猜測密鑰,篩選使得的密文對,予以保留,則平均剩余密文對個數為2n+23×2?16=2n+7.

? Step 2.3.猜測密鑰WK0,也就是,進行第0 輪的左半部分加密,篩選使得的密文對,予以保留,則平均剩余密文對的個數為2n?9×2?16=2n?25.

? Step 2.5.遍歷所有可能的γ值,重復進行上述步驟2.1～步驟2.4,將均不滿足第2.4 步驗證條件的密鑰可作為最終正確密鑰的候選密鑰.對于任一γ值,存在滿足驗證條件的密鑰作為錯誤密鑰篩除.上述攻擊步驟已對48bits 密鑰進行了猜測,將篩選后得到的候選密鑰與未猜測32bits 密鑰進行窮舉,得到最終正確密鑰.

攻擊所需的各項復雜度由定理1 給出.

定理1.根據攻擊算法1,可恢復出Piccolo-80 算法的全部主密鑰,攻擊所需數據復雜度為258.6,計算復雜度為278,存儲復雜度為260.6.

證明:攻擊所需數據復雜度主要由選擇密文量決定.由攻擊步驟1 可知,對于每一個結構,選擇密文的數目為224,選取2n個這樣的結構,得到攻擊所需的選擇密文量為2n+24,也就是數據復雜度為2n+24個選擇密文.本文中所有攻擊所需計算復雜度均采用的是文獻[20]中的方法進行估計,即總的計算復雜度由構造明文結構、密鑰猜測篩選階段以及窮舉剩余密鑰這3 部分的計算復雜度組成.由于Piccolo 算法中F函數采用的是SDS 結構,在一輪運算中,與計算其他環節操作相比,計算F函數所需的復雜度要高出很多,因此攻擊的計算復雜度可依所需計算的F函數的個數進行近似估計,下面進行具體分析.

1.由于攻擊所需選擇密文量為2n+24,因此構造明密文對所需的計算復雜度為TN=2n+24×2=2n+25.

2.Step 2.1 中,選定γ的一個值,猜測密鑰共有216種可能,根據已得的密文對,進行輪Piccolo-80 算法解密操作,篩選的密文對,因此,攻擊所需的計算復雜度為

4.Step 2.3 中,與前兩步類似,猜測密鑰WK0,有216種取值,篩選符合條件的密文對,則該步驟的計算復雜度為

6.Step 2.5 中,對γ所有可能的28?1 值進行遍歷,進行密鑰篩選.也就是重復上述攻擊步驟2.1～步驟2.4,所以密鑰猜測階段總的計算復雜度體現在該步驟中,也就是需要再進行約28?2 次步驟2.1～步驟2.4,因此密鑰猜測階段總的計算復雜度為

存儲復雜度主要用于存儲密文結構以及錯誤密鑰,共需約為260.6個字節.

綜上,攻擊所需數據復雜度為258.6個選擇密文,計算復雜度為278次15 輪Piccolo-80 算法加密,存儲復雜度為260.6個字節.□

2.3.2 攻擊算法2

根據Piccolo 算法F函數組成部分中的S盒為4bits,我們可以將算法每一輪的輸入按半字節進行劃分,密鑰同樣如此,為簡化表示,每一輪的一個輸入狀態將每一個主密鑰定義為Ki=相應的輪密鑰也依此表示.通過簡化密鑰選取的條件,給出如下具體攻擊算法.

· 攻擊條件:選擇第14 輪的輸入差分為(α,0,0,0,0,β,(γ||0),0),密鑰差分為.其中,α,β各表示一個差分活動字節,γ表示一個差分活動半字節.

· 攻擊步驟:除數據收集階段采用上述攻擊條件,使得與算法1 的步驟1 略有不同外,其余步驟與攻擊算法1 基本類似.

定理2 給出了攻擊算法2 的各項復雜度分析結果.

定理2.根據攻擊算法2,可恢復出Piccolo-80 算法的全部主密鑰,攻擊所需數據復雜度為262.6,計算復雜度為277.93,存儲復雜度為264.6.

證明:顯然對于2n個結構,需要2n+20個選擇密文,相應的密鑰猜測階段所需的計算復雜度與攻擊算法1 也有所不同,具體各個環節所需的計算復雜度見表5.

Table 5 Computation complexity analysis of attack Algorithm 2表5 攻擊算法2 的計算復雜度分析

經過驗證可得,選取n=42.6,此攻擊所需的數據復雜度約為262.6個選擇密文,計算復雜度為277.93次15 輪Piccolo-80 算法加密,存儲復雜度為264.6個字節.□

3 21 輪Piccolo-128 算法的相關密鑰-不可能差分攻擊

與第2 節類似,本節首先分析Piccolo-128 算法在輸入狀態差分和主密鑰差分均僅有1 個活動比特塊的限制條件下能夠具有的最長17 輪相關密鑰-不可能差分區分器,在此基礎上,得到適用于攻擊21 輪含前向白化密鑰的Piccolo-28 算法的16 輪相關密鑰-不可能差分區分器,并給出相應的安全性分析結果.

3.1 17輪相關密鑰-不可能差分區分器

結合性質1,考慮Piccolo-28 主密鑰的各個部分在各輪密鑰中出現的分布情況,通過選取合適位置的密鑰差分,實現與輸入輸出差分狀態的抵消,能夠構造得到的最長相關密鑰-不可能差分區分器主要有4 種情形,見表6.

Table 6 17-round related-key impossible differential distinguishers of Piccolo-128表6 17 輪Piccolo-128 算法的相關密鑰-不可能差分區分器

觀察表6 可得,區分器的密鑰差分選取均位于輪密鑰的左半部分.這是因為每輪輪密鑰的右半部分采用的是主密鑰(K1,K3,K5,K7)中的任意一個,而由性質1,Piccolo-128 的輪密鑰的右半部分是按(K3,K5,K7,K1,K7,K3,K5,K1,K5,K7,K3,K1)排列的一個12 輪循環.其中,K3,K5在輪密鑰中連續出現5 次的相距輪數為18,K7在輪密鑰中的相距輪數為17,但該三者中間輪均已達到算法達到完全性的輪數要求,在截斷差分條件下不能得到矛盾.K1在輪密鑰中的相距輪數為15<17,因此當密鑰差分位于輪密鑰的右半部分時,所能構造的區分器輪數定不超過17 輪,所以未予考慮.

由此,我們可得Piccolo-128 算法的8 條17 輪相關密鑰-不可能差分區分器,且需要強調,情形1 中包含了文獻[19]給出的Piccolo-128 算法的相關密鑰-不可能差分區分器.

由于本文的攻擊考慮前向白化密鑰對算法安全性的影響,因此我們僅選取情形1 中的區分器用于實施攻擊.為了能夠利用多相關密鑰以及輪函數的等效結構實現攻擊,我們對所得區分器進行改進,將區分器的第一輪置于密鑰恢復攻擊環節,也就是說改進后的區分器僅為第2 輪～第17 輪,表7 給出了此16 輪區分器的具體構造.而后,借助所得區分器向上向下分別拓展2 輪和3 輪,給出了21 輪含前向白化密鑰Piccolo-128 算法的安全性分析結果.此外,情形4 中的區分器也可用來分析21 輪Piccolo-128 算法僅含后向白化密鑰的安全性,具體攻擊過程和復雜度估計與下文給出的攻擊算法3、算法4 基本一致.

Table 7 16-round related-key impossible differential distinguisher of Piccolo-128 with ΔK4=(α||0)表7 Piccolo-128 在密鑰差分分別選為ΔK4=(α||0)時的16 輪區分器

3.2 21輪密鑰恢復攻擊

根據第3.1 節所得的16 輪區分器,向上解密2 輪,向下加密3 輪,得到對于Piccolo-128 的21 輪攻擊路徑,且與對Piccolo-80 算法的攻擊相同,對于Piccolo-128 的攻擊過程也由兩個階段組成:一為數據收集階段,二為密鑰猜測階段.下文中給出兩個攻擊算法,其中,攻擊算法3 選取的密鑰差分規模為8bits,攻擊算法4 中密鑰差分規模為4bits.下面對算法3 進行詳細介紹,算法4 由于步驟基本與算法3 相似,在本節僅進行簡單介紹.圖3 給出具體攻擊路徑,其中,黑色和白色標識與圖2 相同,灰色表示差分值為α的比特塊.

Fig.3 21-round related-key impossible differential cryptanalysis of Piccolo-128圖3 21 輪Piccolo-128 算法的相關密鑰-不可能差分分析

3.2.1 攻擊算法3

· Step 1.數據收集.

選擇明文(P,P′)的輸入差分為(0,0,0,0,α,0,β,γ),同樣,α,β,γ表示差分活動字節.對于一個明文結構,需要選擇224個明文,則得到247個明文對.當α選定一個非零的取值時,因為有28?1 種可能,所以對應的明文對數量239個.此時選擇相應的密鑰差分基于性質3 輪函數的等效結構,篩選滿足在第20 輪的輸入差分有其余字節差分活動的明文對予以保留,構造2n個結構,當α選定一個非零值時,可得到2n+23個平均剩余明文對.第2 步中具體介紹密鑰猜測階段的攻擊步驟,其中,步驟2.1～步驟2.4 是基于α的值取定的情況,α≠0.

· Step 2.密鑰猜測.

? Step 2.1.猜測密鑰WK1,對于選定的一個α,根據已得到的明文對,篩選使得的明文對,予以保留,則平均剩余明文對個數為2n+23×2?16=2n+7.

? Step 2.5.遍歷所有可能的α值,重復進行上述Step 2.1～Step 2.4,則對于所有可能的α值,均不通過Step 2.4 檢驗的密鑰可作為最終正確密鑰的候選密鑰.對于任一非零α值,存在滿足第2.4 步驗證條件的密鑰作為錯誤密鑰篩除.上述攻擊步驟已對56bits 密鑰進行了猜測,將篩選后得到的候選密鑰與未猜測72bits 密鑰進行窮舉,得到最終正確密鑰.

攻擊所需的復雜度由定理3 給出.

定理3.根據攻擊算法3,可恢復出Piccolo-128 算法的全部主密鑰,攻擊所需數據復雜度為262.3,計算復雜度為282.5,存儲復雜度為264.3.

證明:攻擊所需數據復雜度主要由選擇明文量決定.由步驟1 可得:對于每一個結構,選擇明文數量為224,選取2n個這樣的結構,得到攻擊所需的選擇明文量為2n+24,也就是數據復雜度為2n+24個選擇明文.各步驟具體的計算復雜度情況如下.

由于攻擊所需選擇明文為2n+24,因此構造明文對所需的計算復雜度為TN=2n+25.在Step 2.1 中,攻擊所需的計算復雜度為Step 2.2 所需的計算復雜度為Step 2.3 所需的計算復雜度為Step 2.4 中,猜測密鑰,驗證是否成立,進行密鑰篩選,則該步驟的計算復雜度為Step 3 中,對α所有可能的28?1 值進行遍歷,進行密鑰篩選.也就是重復上述攻擊步驟2.1～步驟2.4,因此在密鑰猜測階段,總的計算復雜度約為

存儲復雜度主要用于存儲明文結構以及錯誤密鑰,共需約為264.3個字節.

綜上,攻擊所需數據復雜度為262.3個選擇明文,計算復雜度為282.5次21 輪Piccolo-128 算法加密,存儲復雜度為264.3個字節.□

3.2.2 攻擊算法4

· 攻擊條件:與攻擊算法2 類似,對各輪輸入輸出狀態和密鑰比特塊按半字節進行劃分.選擇明文差分為(0,0,0,0,(α||0),0,β,γ),密鑰差分為其中,α表示一個差分活動半字節,β,γ各表示一個差分活動字節.

· 攻擊步驟:除數據收集階段略異于攻擊算法3,其余步驟基本類似.

攻擊算法4 的復雜度分析結果由定理4 給出.

定理4.根據攻擊算法4,恢復Piccolo-128 算法的全部主密鑰所需數據復雜度為262.3,計算復雜度為2124.45,存儲復雜度為264.3.

證明:選取n=42.3,則該攻擊所需的數據復雜度約為262.3個選擇明文,計算復雜度為2124.45次21 輪Piccolo-128 算法加密,存儲復雜度為264.3個字節.主要證明過程與定理2.3 類似,此處不再贅述.□

4 結束語

本文中利用相關密鑰-不可能差分分析方法,結合算法密鑰擴展方面的弱點,基于算法的等效結構,給出了除Biclique 分析外,攻擊輪數最長的縮減輪Piccolo 算法的差分類分析結果.其中,對于Piccolo-80 算法,找到所有30 條11 輪相關密鑰-不可能差分區分器,并基于情形1 的區分器,得到了15 輪含前向白化密鑰的攻擊結果;對于Piccolo-128 算法,找到所有8 條17 輪區分器,并基于改進后的16 輪區分器,攻擊了21 輪含前向白化密鑰的Piccolo-128 算法.且根據所選取的密鑰差分規模不同,對Piccolo-80 和Piccolo-128 分別給出了兩個不同的攻擊算法,攻擊所需的復雜度均低于窮舉分析,優于已有攻擊結果.分析結果表明,15 輪Piccolo-80 算法和21 輪Piccolo-128 算法在不含后向密鑰的條件下均不能抵抗相關密鑰-不可能差分攻擊.能否在不增加算法實現代價的前提下,通過改進Piccolo 算法的密鑰擴展方式使得算法的安全性進一步提高,是下一步研究的方向.

作者注 本文于2018 年5 月22 日投稿至《軟件學報》“面向自主安全可控的可信計算”專題,并于2018 年12月13 日被錄用,于2019 年正式發表.本文第一作者徐林宏的碩士學位論文于2018 年12 月底完成答辯,后提交至學位論文庫.該碩士學位論文的部分章節內容基于本文工作成果,特此說明.

附錄A

Table A 11-round distinguisher of Piccolo-80 with ΔK2=(γ||0) or ΔK1=(0||γ)表A Piccolo-80 在密鑰差分分別選為ΔK2=(γ||0)和ΔK1=(0||γ)時的11 輪區分器

附錄B

Table B 11-round distinguisher of Piccolo-80 with ΔK4=(γ||0)表B Piccolo-80 在密鑰差分選為ΔK4=(γ||0)時的11 輪區分器