国产日韩欧美一区二区三区三州_亚洲少妇熟女av_久久久久亚洲av国产精品_波多野结衣网站一区二区_亚洲欧美色片在线91_国产亚洲精品精品国产优播av_日本一区二区三区波多野结衣 _久久国产av不卡

?

Piccolo 算法的相關(guān)密鑰-不可能差分攻擊?

2019-10-28 11:21徐林宏郭建勝崔競一李明明
軟件學(xué)報(bào) 2019年8期
關(guān)鍵詞:明文白化密文

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

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

隨著物聯(lián)網(wǎng)技術(shù)的不斷發(fā)展,人們對(duì)其安全性的要求也越來越高,適用于這些資源受限環(huán)境的密碼算法即輕量級(jí)密碼算法成為密碼學(xué)研究的一個(gè)熱點(diǎn),大量輕量級(jí)密碼算法被設(shè)計(jì)出來,如 PRESENT[1],LBlock[2],PRINCE[3],SIMON[4]等算法.

Piccolo 算法是由日本密碼學(xué)家Shibutani 等人[5]于CHES 2011 上提出的一種適用于資源受限環(huán)境的輕量級(jí)分組密碼算法,其算法結(jié)構(gòu)為廣義Feistel 結(jié)構(gòu),硬件實(shí)現(xiàn)效率較高.該算法一經(jīng)提出,就受到學(xué)界的廣泛關(guān)注.

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

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

· 相關(guān)工作

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

· 本文工作

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

Table 1 Comparison of attack results on Piccolo表1 Piccolo 算法的攻擊結(jié)果對(duì)比

· 文章結(jié)構(gòu)安排

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

1 相關(guān)知識(shí)

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

1.1 符號(hào)說明

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

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

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

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

1.2 Piccolo算法簡介

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

·F函數(shù)

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

· 字節(jié)置換RP

該環(huán)節(jié)主要實(shí)現(xiàn)各字節(jié)的移位替換,即

· 密鑰擴(kuò)展算法

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

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

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

表2 和表3 分別給出了兩個(gè)版本Piccolo 算法輪子密鑰和主密鑰的對(duì)應(yīng)關(guān)系.

Table 2 Correspondence between the master key and the round keys of Piccolo-80表2 Piccolo-80 算法的主密鑰與輪密鑰之間的對(duì)應(yīng)關(guān)系

Table 3 Correspondence between the master key and the round keys of Piccolo-128表3 Piccolo-128 算法的主密鑰與輪密鑰之間的對(duì)應(yīng)關(guān)系

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

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

2.1 Piccolo算法性質(zhì)

性質(zhì)1(密鑰擴(kuò)展算法性質(zhì)).主要有以下3 個(gè)方面.

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

(2) 在不考慮輪常數(shù)的影響時(shí),對(duì)于Piccolo-80,其輪密鑰(除白化密鑰外)是由主密鑰構(gòu)成的一個(gè)周期為5的循環(huán).

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

證明:分別觀察表2、表3 中Piccolo-80 和Piccolo-128 主密鑰與輪密鑰間的對(duì)應(yīng)關(guān)系,可得上述結(jié)論.□

性質(zhì)2.根據(jù)算法結(jié)構(gòu)中的F函數(shù)采用的是4bits 的S盒,且在字節(jié)置換操作中,實(shí)現(xiàn)的是對(duì)字節(jié)整體的移位操作,未改變各個(gè)字節(jié)內(nèi)部每一比特的狀態(tài),因此在引入明文差分時(shí),可在與密鑰進(jìn)行差分抵消的位置選取4bits 或8bits 差分,相應(yīng)地選擇4bits 或8bits 的相關(guān)密鑰差分實(shí)現(xiàn)差分抵消.當(dāng)選取明文差分為4bits 時(shí),攻擊所需的相關(guān)密鑰量約為24,較差分選為8bits 時(shí)有所減少,具體應(yīng)用見第2.3 節(jié)和第3.2 節(jié).

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

Fig.1 Equivalent structure of round function圖1 輪函數(shù)等效結(jié)構(gòu)

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

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

2.2 11輪相關(guān)密鑰-不可能差分區(qū)分器

根據(jù)算法輪函數(shù)結(jié)構(gòu),在不含相關(guān)密鑰差分,輸入狀態(tài)僅存在1 個(gè)差分活動(dòng)比特塊時(shí),算法達(dá)到完全性有兩種情況.

(1) 活動(dòng)比特塊位于F函數(shù)的輸入,經(jīng)過3 輪變換后,算法達(dá)到完全.

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

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

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

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

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

2.3 15輪密鑰恢復(fù)攻擊

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

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

2.3.1 攻擊算法1

· Step 1.數(shù)據(jù)收集.

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

· Step 2.密鑰猜測.

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

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

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

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

攻擊所需的各項(xiàng)復(fù)雜度由定理1 給出.

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

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

1.由于攻擊所需選擇密文量為2n+24,因此構(gòu)造明密文對(duì)所需的計(jì)算復(fù)雜度為TN=2n+24×2=2n+25.

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

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

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

存儲(chǔ)復(fù)雜度主要用于存儲(chǔ)密文結(jié)構(gòu)以及錯(cuò)誤密鑰,共需約為260.6個(gè)字節(jié).

綜上,攻擊所需數(shù)據(jù)復(fù)雜度為258.6個(gè)選擇密文,計(jì)算復(fù)雜度為278次15 輪Piccolo-80 算法加密,存儲(chǔ)復(fù)雜度為260.6個(gè)字節(jié).□

2.3.2 攻擊算法2

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

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

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

定理2 給出了攻擊算法2 的各項(xiàng)復(fù)雜度分析結(jié)果.

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

證明:顯然對(duì)于2n個(gè)結(jié)構(gòu),需要2n+20個(gè)選擇密文,相應(yīng)的密鑰猜測階段所需的計(jì)算復(fù)雜度與攻擊算法1 也有所不同,具體各個(gè)環(huán)節(jié)所需的計(jì)算復(fù)雜度見表5.

Table 5 Computation complexity analysis of attack Algorithm 2表5 攻擊算法2 的計(jì)算復(fù)雜度分析

經(jīng)過驗(yàn)證可得,選取n=42.6,此攻擊所需的數(shù)據(jù)復(fù)雜度約為262.6個(gè)選擇密文,計(jì)算復(fù)雜度為277.93次15 輪Piccolo-80 算法加密,存儲(chǔ)復(fù)雜度為264.6個(gè)字節(jié).□

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

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

3.1 17輪相關(guān)密鑰-不可能差分區(qū)分器

結(jié)合性質(zhì)1,考慮Piccolo-28 主密鑰的各個(gè)部分在各輪密鑰中出現(xiàn)的分布情況,通過選取合適位置的密鑰差分,實(shí)現(xiàn)與輸入輸出差分狀態(tài)的抵消,能夠構(gòu)造得到的最長相關(guān)密鑰-不可能差分區(qū)分器主要有4 種情形,見表6.

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

觀察表6 可得,區(qū)分器的密鑰差分選取均位于輪密鑰的左半部分.這是因?yàn)槊枯嗇喢荑€的右半部分采用的是主密鑰(K1,K3,K5,K7)中的任意一個(gè),而由性質(zhì)1,Piccolo-128 的輪密鑰的右半部分是按(K3,K5,K7,K1,K7,K3,K5,K1,K5,K7,K3,K1)排列的一個(gè)12 輪循環(huán).其中,K3,K5在輪密鑰中連續(xù)出現(xiàn)5 次的相距輪數(shù)為18,K7在輪密鑰中的相距輪數(shù)為17,但該三者中間輪均已達(dá)到算法達(dá)到完全性的輪數(shù)要求,在截?cái)嗖罘謼l件下不能得到矛盾.K1在輪密鑰中的相距輪數(shù)為15<17,因此當(dāng)密鑰差分位于輪密鑰的右半部分時(shí),所能構(gòu)造的區(qū)分器輪數(shù)定不超過17 輪,所以未予考慮.

由此,我們可得Piccolo-128 算法的8 條17 輪相關(guān)密鑰-不可能差分區(qū)分器,且需要強(qiáng)調(diào),情形1 中包含了文獻(xiàn)[19]給出的Piccolo-128 算法的相關(guān)密鑰-不可能差分區(qū)分器.

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

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

3.2 21輪密鑰恢復(fù)攻擊

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

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

3.2.1 攻擊算法3

· Step 1.數(shù)據(jù)收集.

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

· Step 2.密鑰猜測.

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

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

攻擊所需的復(fù)雜度由定理3 給出.

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

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

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

存儲(chǔ)復(fù)雜度主要用于存儲(chǔ)明文結(jié)構(gòu)以及錯(cuò)誤密鑰,共需約為264.3個(gè)字節(jié).

綜上,攻擊所需數(shù)據(jù)復(fù)雜度為262.3個(gè)選擇明文,計(jì)算復(fù)雜度為282.5次21 輪Piccolo-128 算法加密,存儲(chǔ)復(fù)雜度為264.3個(gè)字節(jié).□

3.2.2 攻擊算法4

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

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

攻擊算法4 的復(fù)雜度分析結(jié)果由定理4 給出.

定理4.根據(jù)攻擊算法4,恢復(fù)Piccolo-128 算法的全部主密鑰所需數(shù)據(jù)復(fù)雜度為262.3,計(jì)算復(fù)雜度為2124.45,存儲(chǔ)復(fù)雜度為264.3.

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

4 結(jié)束語

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

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

附錄A

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

附錄B

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

猜你喜歡
明文白化密文
一種支持動(dòng)態(tài)更新的可排名密文搜索方案
群智感知網(wǎng)絡(luò)環(huán)境下的一種高效安全數(shù)據(jù)聚合方案*
基于模糊數(shù)學(xué)的通信網(wǎng)絡(luò)密文信息差錯(cuò)恢復(fù)
支持多跳的多策略屬性基全同態(tài)短密文加密方案
運(yùn)用紅外相機(jī)技術(shù)首次記錄白化小麂
白化黃喉擬水龜人工培育研究①
基于Surfer的瞬變電磁法扇形超前探測白化文件的精確快速生成方法
奇怪的處罰
奇怪的處罰
老河口市| 湘西| 华蓥市| 吕梁市| 谢通门县| 洱源县| 历史| 天全县| 芜湖市| 平罗县| 平和县| 商水县| 楚雄市| 凤翔县| 昔阳县| 靖江市| 潼关县| 保德县| 襄汾县| 辉南县| 万全县| 和林格尔县| 济南市| 乳山市| 井冈山市| 确山县| 乌海市| 互助| 黔西县| 即墨市| 三都| 全州县| 宜丰县| 广平县| 静宁县| 柘城县| 甘肃省| 萝北县| 洞口县| 中山市| 大方县|