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

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

1 引言

物聯(lián)網(wǎng)的興起帶來了微型設(shè)備的大量應(yīng)用,像智慧交通、智能物流等,給人們的生活帶來了很大的方便,但終端資源非常有限,其中的安全問題是一個急需解決的問題,主要是未授權(quán)用戶對數(shù)據(jù)的生成、訪問和篡改,所以輕量級密碼算法[1–3]和協(xié)議[4–6]就成了密碼學(xué)術(shù)界關(guān)注的焦點.

Piccolo 算法是由日本密碼學(xué)家Shibutani 等人[7]于CHES 2011 上提出的一種基于廣義Feistel 結(jié)構(gòu)設(shè)計的輕量級分組密碼算法,適用于資源受限的環(huán)境,有較高的硬件實現(xiàn)效率.該算法分組規(guī)模為64 bits,根據(jù)密鑰規(guī)模的不同,可分為Piccolo-80 和Piccolo-128 兩類.

Biclique 分析方法由Bogdanov 等人[8]在AsiaCrypt 2011 上提出,是對分組密碼以及Hash 函數(shù)的一種新型攻擊方法,初始用于對全輪AES 算法進行攻擊,并使得攻擊復(fù)雜度低于窮舉攻擊.同樣的,Biclique 對于其他的分組密碼算法,尤其是輕量級分組密碼算法這類具有簡單密鑰調(diào)度設(shè)計的算法也有較好的攻擊效果,例如對CLEFIA[9]、LBlock[10]、PRESENT[11,12]、PRINCE[13]等算法的安全性分析.

現(xiàn)有的對于Piccolo 算法的安全性分析結(jié)果較多,其中,在單密鑰條件下利用統(tǒng)計類的分析方法(差分、線性、積分分析等)以低于窮舉復(fù)雜度對Piccolo 算法的最優(yōu)攻擊輪數(shù)[14]分別為Piccolo-80 算法14輪、Piccolo-128 算法18 輪.而基于Biclique 分析能夠攻擊全輪分組密碼算法的特性,可對全輪的Piccolo算法進行安全性評估.在已有的對于Piccolo 算法的Biclique 攻擊結(jié)果中,大多是通過構(gòu)造平衡Biclique結(jié)構(gòu)實施攻擊.2012年,Wang 等人[15]最先給出了全輪Piccolo-80 算法和縮減輪的Piccolo-128 算法在不考慮白化密鑰條件下的Biclique 分析結(jié)果;2013年,Jeong 等人[11]利用Biclique 分析方法給出了全輪PRESENT、Piccolo 和LED 算法的攻擊結(jié)果;2017年,Han 等人[16]通過改進Jeong 等人的工作,降低了對全輪Piccolo 算法Biclique 攻擊的復(fù)雜度;利用非平衡Biclique 結(jié)構(gòu)對Piccolo 算法進行攻擊體現(xiàn)在2014年Ahmadi 等人[17]的工作中.

本文主要使用非平衡Biclique 攻擊的方法對Piccolo 算法進行安全性分析,利用文獻[8,18]中構(gòu)造Biclique 結(jié)構(gòu)的方法,通過建立非平衡Biclique 結(jié)構(gòu)以及Stars 結(jié)構(gòu),分別給出了Piccolo-80 和Piccolo-128 算法的非平衡Biclique 攻擊和Stars 攻擊結(jié)果,增加考慮存儲方面的復(fù)雜度.與現(xiàn)有攻擊結(jié)果相比,分別在數(shù)據(jù)復(fù)雜度和計算復(fù)雜度方面有所優(yōu)化.本文攻擊結(jié)果如表1 所示.

第1 節(jié)介紹本文研究背景,第2 節(jié)主要介紹Piccolo 算法和Biclique 攻擊的相關(guān)知識,對Piccolo-80和Piccolo-128 算法的非平衡Biclique 分析和Stars 攻擊主要在第3 節(jié)和第4 節(jié)中給出,第5 節(jié)總結(jié)全文.

2 相關(guān)知識

2.1 符號說明

:第r輪算法的第i個分塊,i∈{0,1,···,7}

Pi:Biclique 結(jié)構(gòu)明文狀態(tài)

Ci:Biclique 結(jié)構(gòu)密文狀態(tài)

Sj:Biclique 結(jié)構(gòu)中間狀態(tài)

Vi,j:匹配向量位置

wkt:第t個白化密鑰

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

2.2 Piccolo 算法

Piccolo 算法采用廣義Feistel 結(jié)構(gòu),其密鑰規(guī)模有80 bits 和128 bits 兩種,分組規(guī)模均為64 bits,從而可分為Piccolo-80 和Piccolo-128 兩個版本,加密輪數(shù)分別為25 輪和31 輪.它的加密環(huán)節(jié)包括密鑰白化、F函數(shù)和字節(jié)置換操作.密鑰白化操作僅在第一輪和最后一輪存在,保證加脫密結(jié)構(gòu)的一致性.輪變換主要由F函數(shù)和字節(jié)代替組成,下面具體介紹輪變換的各個環(huán)節(jié)和密鑰擴展算法,完整的Piccolo 加密變換如圖1 所示,其中r表示加密輪數(shù).

表1 Piccolo算法的Biclique 分析結(jié)果對比Table 1 Comparison of Biclique analysis results of Piccolo

圖1 Piccolo算法結(jié)構(gòu)Figure 1 Structure of Piccolo

F 函數(shù)該變換對16 bits 數(shù)據(jù)進行操作,其主要由8 個相同的4 比特雙射S 盒和一個列混合矩陣M組成,用來實現(xiàn)算法的混亂和擴散.列混合矩陣M的運算定義在由不可約多項式x4+x+1 生成的GF(24)上,具體形式如下.

表2 給出了雙射S 盒,圖2 給出了F函數(shù)的具體構(gòu)造.

表2 4比特雙射S 盒Table 2 4 bits S-Box with bijection

輪置換RP初始將明文數(shù)據(jù)分成四部分,每部分由兩個字節(jié)組成,也就是圖1 中的P0到P3,則在進行輪置換時,以字節(jié)為單位進行置換操作.在本文中,為了便于攻擊,根據(jù)F函數(shù)中的S 盒為4 比特,可將每一字節(jié)分割成兩個半字節(jié)進行操作,即每一輪的輸入狀態(tài)表示為左右兩個半字節(jié)具體如圖3 所示.

圖2 F函數(shù)Figure 2 F function

圖3 輪置換RPFigure 3 Round permutation

密鑰擴展算法Piccolo 算法的密鑰擴展根據(jù)密鑰規(guī)模不同,同樣分為80 bits 和128 bits 密鑰兩種.對于Piccolo-80,將80 bits 主密鑰劃分為5 個部分,每個部分包括兩字節(jié),即K=K0||K1||K2||K3||K4,其中,由于F函數(shù)中采用的是4 比特S 盒,因此,在這里,我們可以將主密鑰繼續(xù)作劃分,對每一字節(jié)密鑰再劃分,即白化密鑰wkj,j∈(0,1,2,3)由主密鑰直接生成,也就輪密鑰(rk2r,rk2r+1),r∈{0,···,24} 由主密鑰與固定常數(shù)異或所得,具體對應(yīng)關(guān)系見表3.對于Piccolo-128,與Piccolo-80 主要區(qū)別在于主密鑰增加了6 個字節(jié),得到K=K0||K1||K2||K3||K4||K5||K6||K7,相應(yīng)的白化密鑰也有所變化,即輪密鑰r∈{0,···,30},具體對應(yīng)關(guān)系見表4.Piccolo 算法的具體構(gòu)造詳見文獻[7].

2.3 Biclique攻擊方法介紹

Biclique 攻擊本質(zhì)上是基于中間相遇思想,借助算法密鑰擴展的弱點給出密鑰恢復(fù)方案的一種攻擊方法.在文獻[8]中,作者提出了兩種構(gòu)造Biclique 結(jié)構(gòu)的方法,分別為獨立Biclique 結(jié)構(gòu)和長Biclique結(jié)構(gòu).由于獨立Biclique 結(jié)構(gòu)更易構(gòu)造,所以后續(xù)的攻擊一般采用此結(jié)構(gòu)對密碼算法進行Biclique 分析,本文中亦如此.2017年崔競一等人[18]運用獨立Biclique 結(jié)構(gòu)提出了一種廣義Biclique 自動攻擊框架,在進行具體攻擊時,根據(jù)構(gòu)造所得結(jié)構(gòu)維數(shù)不同,可分為平衡Biclique 攻擊、Stars 攻擊[19]和非平衡Biclique 攻擊.本文基于文獻[18]的分類方法,主要研究Piccolo 算法在非平衡Biclique 攻擊和Stars 攻擊下的安全性,有效利用預(yù)計算技術(shù)降低攻擊所需計算復(fù)雜度.下面對一般情形下Biclique 結(jié)構(gòu)的構(gòu)造和攻擊流程以及預(yù)計算匹配技術(shù)進行介紹.

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

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

2.3.1 Biclique結(jié)構(gòu)構(gòu)造

簡單來說,一個Biclique 結(jié)構(gòu)就是一個二分圖,一般通過三元組的形式表示.令l輪子算法f在密鑰K[i,j]作用下將密文狀態(tài)C中的2d1個元素Ci映射到中間狀態(tài)S中的2d2個元素Sj,也就是其中?i∈{0,1,···,2d1?1},?j∈{0,1,···,2d2?1}.將這樣的三元組({Ci},{Sj},K[i,j])記為(d1,d2)維Biclique 結(jié)構(gòu).當d1=d2=d0 時,將其稱為平衡Biclique 結(jié)構(gòu),當d1=0,d2=d0時稱為Stars 結(jié)構(gòu),d1d2且均不為0 時為非平衡Biclique 結(jié)構(gòu).下面詳細介紹非平衡Biclique 結(jié)構(gòu)的構(gòu)造方法,圖4 為一般的Biclique 結(jié)構(gòu)示意圖.

基于文獻[8]的方法,選擇一個上述三元組(C0,S0,K[0,0])滿足在此基礎(chǔ)上,選取兩組相關(guān)密鑰差分和得到兩條獨立的差分路徑?j和?i,構(gòu)造得到一個映射關(guān)系,滿足對于2d1 個元素Ci在密鑰K[i,j]作用下映射到2d2個元素Sj,即S0⊕?jC0⊕?i.令Ci=C0⊕?i,Sj=S0⊕?j,K[i,j]=K[0,0]⊕⊕則三元組({Ci},{Sj},K[i,j])即所構(gòu)造得到的一個Biclique 結(jié)構(gòu),其中i∈{0,1,···,2d1?1},j∈{0,1,···,2d2?1},當d1=d2=d0 時,則構(gòu)造所得為一個平衡Biclique 結(jié)構(gòu).對于非平衡Biclique 結(jié)構(gòu)的構(gòu)造,可利用文獻[18]的方法,將密鑰差分相互獨立的多個平衡Biclique 結(jié)構(gòu)進行組合得到,如下文中3.1 節(jié);也可以通過選取兩組不平衡的密鑰差分直接利用上述方法構(gòu)造得到,如4.1 節(jié).此外,在結(jié)構(gòu)構(gòu)造中,為了使得攻擊效果更好,根據(jù)算法實際,還可選擇有明文方向或密文方向兩種構(gòu)造方式.

圖4 Biclique 結(jié)構(gòu)示意圖Figure 4 Biclique structure

2.3.2 Biclique 攻擊流程

將一個分組密碼e看成多個子算法的結(jié)合,即使得由密文狀態(tài)C映射到明文狀態(tài)P有如下表示:

其中f表示構(gòu)造Biclique 結(jié)構(gòu)的子算法,進而可將Biclique 攻擊分為以下四步.

1.密鑰劃分.敵手將分組密碼e上的主密鑰2n分割成不同的2n?d1?d2個密鑰空間,每一個密鑰空間內(nèi)有2d1+d2個候選密鑰K[i,j],i∈{0,1,···,2d1?1},j∈{0,1,···,2d2?1}.

2.構(gòu)造Biclique 結(jié)構(gòu).敵手依據(jù)劃分所得的每個密鑰空間K[i,j],在子算法f上構(gòu)造Biclique 結(jié)構(gòu).

3.匹配階段.敵手通過子算法f上的Biclique 結(jié)構(gòu)得到2d1個狀態(tài)Ci,在正確密鑰解密下得到對應(yīng)的密文Pi,而后從Pi由子算法前向計算得到對應(yīng)的2d1個匹配狀態(tài)Vi,0,即相應(yīng)的,從2d2個狀態(tài)Sj后向計算得到2d2個匹配狀態(tài)V0,j,即V0,j在此基礎(chǔ)上,進行狀態(tài)匹配,保留滿足的K[i,j]作為正確的候選密鑰予以保留,其余的篩除.

4.密鑰篩選.對候選密鑰集進行窮舉,得到正確密鑰.

這里僅以密文方向的Biclique 分析為例進行了介紹,明文方向的攻擊過程與密文方向基本一致.攻擊復(fù)雜度主要包括數(shù)據(jù)復(fù)雜度、存儲復(fù)雜度和計算復(fù)雜度.數(shù)據(jù)復(fù)雜度由構(gòu)造Biclique 結(jié)構(gòu)所需的選擇明(密)文數(shù)量決定,存儲復(fù)雜度由構(gòu)造得到的Biclique 結(jié)構(gòu)的維度以及預(yù)計算過程中的非線性環(huán)節(jié)數(shù)量決定.計算復(fù)雜度主要包括三個部分,分別是Biclique 結(jié)構(gòu)構(gòu)造、狀態(tài)匹配階段以及密鑰篩選階段的計算復(fù)雜度,即C=CBiclique+Cmatch+Cfalse.

引理1(預(yù)計算匹配技術(shù))[8]根據(jù)2.3.2 節(jié)中介紹的攻擊中的狀態(tài)匹配過程,攻擊者通過檢驗前向和后向匹配過程得到的匹配向量值是否一致,篩選錯誤密鑰.考慮可以發(fā)現(xiàn),當固定i,對于兩個不同的j,在前向匹配階段,即中有部分狀態(tài)值一直保持不變,因此我們在攻擊時對這些部分僅需計算一次.同樣的,在后向匹配階段,固定j,對于密鑰差分i和0,即V0,j和中那些狀態(tài)值不變的部分僅需計算一次.基于此特點,在匹配階段,選定匹配向量,預(yù)計算那些在不同的密鑰差分條件下仍保持不變的狀態(tài)值,并進行存儲,只對狀態(tài)值發(fā)生改變的部分進行重計算,再進行狀態(tài)匹配,能夠有效降低攻擊所需計算復(fù)雜度.

3 Piccolo-80算法的Biclique分析

首先,給出Piccolo 算法的幾點性質(zhì),有助于下一步實施Blicique 攻擊.

性質(zhì)1通過統(tǒng)計Piccolo-80 算法的密鑰擴展算法中主密鑰的每一Ki,i∈{0,1,···,5} 出現(xiàn)的次數(shù)可得,除白化密鑰外,輪密鑰中(K0,K1)與(K2,K3)組合出現(xiàn)的概率均為10 次,(K4,K4)出現(xiàn)的概率為5 次.進而想要使得攻擊效果更好,在構(gòu)造Biclique 結(jié)構(gòu)時,應(yīng)盡量選擇在K4上進行密鑰劃分.同樣的,對于Piccolo-128 算法的密鑰擴展算法中的每一Ki,i∈{0,1,···,8},除白化密鑰外,K0、K1出現(xiàn)的次數(shù)均為7 次,其余均為8 次.因此選擇在這兩個密鑰位置進行密鑰劃分能使得攻擊結(jié)果更優(yōu).

性質(zhì)2[14]Piccolo 算法的非線性環(huán)節(jié)—F函數(shù)采用是SDS 結(jié)構(gòu),如圖2 所示.由于對于單個F函數(shù)進行計算所需的復(fù)雜度遠大于其他環(huán)節(jié)操作例如異或操作,因此,在本文的攻擊中,計算復(fù)雜度均以所需計算的F函數(shù)的個數(shù)作為衡量指標.在狀態(tài)匹配階段,當F函數(shù)輸入比特全部活動,輸出比特僅有一半活動時,也就是需計算4 個輸入S 盒和2 個輸出S 盒,則所需的計算復(fù)雜度約為個F函數(shù),同樣的僅在輸入有一半比特不活動,所需計算復(fù)雜度也為個F函數(shù);僅在輸入或輸出一側(cè)有比特活動時,另一側(cè)比特全部活動時,所需計算復(fù)雜度約為個F函數(shù).

下面依據(jù)上述性質(zhì),介紹對于Piccolo 算法的非平衡Biclique 攻擊和Stars 攻擊.

3.1 Piccolo-80算法的(4,8)非平衡Biclique分析

在該部分,利用文獻[18]中構(gòu)造Biclique 結(jié)構(gòu)的方法,通過兩個低維的(4,4)平衡Biclique 結(jié)構(gòu)結(jié)合得到一個(4,8)非平衡Biclique 結(jié)構(gòu),并依此對Piccolo-80 算法進行了Biclique 分析.根據(jù)密鑰擴展算法,為了得到更好的攻擊效果,選擇從密文方向進行Biclique 結(jié)構(gòu)構(gòu)造.

密鑰劃分借助性質(zhì)1,選取為活動比特位,令K[0,0,0]為上述三個位置密鑰為0,其余比特遍歷的主密鑰.劃分80 bits 主密鑰為268個集合,每一子密鑰集合包含212個密鑰K[i,j1,j2],(i,j1,j2∈{0,1}4).K[i,j1,j2]定義為由K[0,0,0]與三個密鑰差分組成,其中

Biclique 結(jié)構(gòu)構(gòu)造首先依據(jù)劃分的密鑰空間,利用對應(yīng)的輪密鑰構(gòu)造相關(guān)密鑰差分路徑?i、?j1、?j2,如圖5 所示.顯然(?i,?j1)和(?i,?j2)中沒有重合的F函數(shù),因此構(gòu)造得到了兩個密文方向的6輪(4,4)平衡Biclique 結(jié)構(gòu).然后利用文獻[18]中的構(gòu)造方法,將這兩個平衡Biclique 結(jié)構(gòu)進行組合,就得到了一個6 輪(4,8)非平衡Biclique 結(jié)構(gòu)({Sj1,j2},{Ci},K[i,j1,j2]).

狀態(tài)匹配根據(jù)構(gòu)造得到的一個6 輪(4,8)非平衡Biclique 結(jié)構(gòu),得到24個狀態(tài)Ci,通過正確密鑰解密得到對應(yīng)的24個明文狀態(tài)Pi.選擇與文獻[17]相同的匹配向量,即第10 輪的第6 個字節(jié)為匹配向量,也就是由Pi向下加密10 輪,定義為前向匹配過程,Sj1,j2向上解密9 輪,定義為后向匹配過程.結(jié)合引理1,在前向匹配時只需對圖中2.75 個F函數(shù)進行預(yù)計算,2.25 個F函數(shù)進行24次重計算,11.25 個F函數(shù)進行28次重計算,即可完成匹配,如圖6(c)所示.圖6 中(a)表示前向匹配過程中使用K[i,j1,j2]和K[i,0,j2]進行加密時的差分活動情況,(b)表示前向匹配過程中使用K[i,j1,j2]和K[i,j1,0]進行加密時的差分活動情況,(c)表示兩者結(jié)合,在前向匹配過程中需要重計算的活動比特情況.(d)表示后向匹配過程中重計算的活動比特情況.后向匹配過程需要對圖中2.75 個F函數(shù)進行預(yù)計算,13.5 個F函數(shù)進行24次重計算即可完成匹配.圖6 中黑色標識需28次重計算的活動比特塊,灰色標識需24次重計算的活動比特塊,白色表示非活動比特塊,下文中的圖中標識均與此相同.

圖6 Piccolo-80 算法的非平衡Biclique 攻擊匹配階段Figure 6 Matching phase of unbalanced Biclique attack for Piccolo-80

密鑰篩選由于使用的匹配向量共28個可能值,因此平均一個錯誤密鑰通過篩選的概率為2?8.又由每個密鑰子集合中含有212個密鑰,所以每個密鑰子集合平均有212×2?8=24個密鑰通過篩選,即得到了24個候選密鑰.最后,每次攻擊均對剩余的24個候選密鑰進行全輪加密,檢驗得到初始的正確密鑰.定理1 給出了上述Piccolo-80 算法非平衡Biclique 攻擊所需的復(fù)雜度.

定理1利用6 輪(4,8)非平衡Biclique 結(jié)構(gòu)對Piccolo-80 算法進行攻擊,可恢復(fù)全輪Piccolo-80 算法的主密鑰,其數(shù)據(jù)復(fù)雜度為236,存儲復(fù)雜度為211.12,計算復(fù)雜度為279.03.

證明:數(shù)據(jù)復(fù)雜度主要由構(gòu)造Biclique 結(jié)構(gòu)所需的明密文量決定,由圖5 可得,對每一個Biclique結(jié)構(gòu),需要固定密文C0,,差分不活動,其余位置遍歷所有可能值,因此攻擊所需的數(shù)據(jù)復(fù)雜度為236個選擇密文.

存儲復(fù)雜度由存儲Biclique 結(jié)構(gòu)以及利用預(yù)計算匹配技術(shù),存儲預(yù)計算的F函數(shù)這兩部分構(gòu)成.對于Biclique 結(jié)構(gòu)的存儲,實際上就是對密文狀態(tài)和中間狀態(tài)之間的對應(yīng)關(guān)系進行存儲,也就是需要順序存儲24個密文和28個中間狀態(tài)的對應(yīng)關(guān)系,每個狀態(tài)為8 字節(jié),共需存儲(24+28)×8 字節(jié).另外,由于在匹配階段使用了預(yù)計算匹配技術(shù),需要對攻擊中不受活動比特影響的F函數(shù)進行預(yù)計算并存儲,共有2.75+2.75 個F函數(shù),每個F函數(shù)狀態(tài)均為8 字節(jié),因此需要存儲(2.75+2.75)×8 個字節(jié).綜上,上述攻擊所需存儲復(fù)雜度為211.12個字節(jié).

攻擊所需的計算復(fù)雜度主要由三部分構(gòu)成.一是構(gòu)造Biclique 結(jié)構(gòu)所需的復(fù)雜度,本節(jié)中利用文獻[18]的非平衡Biclique 結(jié)構(gòu)構(gòu)造方法,能夠有效降低結(jié)構(gòu)構(gòu)造所需的計算復(fù)雜度.由圖5 可知,構(gòu)造過程所需的計算復(fù)雜度約為

次全輪Piccolo-80 加密.二是匹配階段的計算復(fù)雜度,主要包含前向匹配和后向匹配兩個部分.根據(jù)上述攻擊過程可得,前向匹配階段需2.75 個F函數(shù)進行預(yù)計算,2.25 個F函數(shù)進行24次重計算,11.25個F函數(shù)進行28次重計算,后向匹配需要對2.75 個F函數(shù)進行預(yù)計算,13.5 個F函數(shù)進行24次重計算.即匹配階段所需的計算復(fù)雜度總計為:Cmatch=29.87+210.13≈211.01次全輪Piccolo-80 加密.三是密鑰篩選階段的計算復(fù)雜度,由每一密鑰子集合剩余24候選密鑰,則Cfalse=24.因此上述攻擊所需的計算復(fù)雜度總計為C=268×(24.07+211.01+24)≈279.03次全輪Piccolo-80 加密.

綜上,對于Piccolo-80 算法的(4,8)非平衡Biclique 攻擊所需的數(shù)據(jù)復(fù)雜度為236個選擇密文,存儲復(fù)雜度為211.12個字節(jié),計算復(fù)雜度為279.03次全輪Piccolo-80 加密.

3.2 Piccolo-80算法的Stars攻擊

Stars 攻擊是由Bogdanov 等人[19]在ICISC 2014 上提出的一種Biclique 攻擊方法,最先用于AES算法.其本質(zhì)上與非平衡Biclique 攻擊相似,攻擊過程也基本一致,但所需數(shù)據(jù)復(fù)雜度很少,一般為2–3個已知明文,相應(yīng)的攻擊所需計算復(fù)雜度就有所增加.本小節(jié)中就運用此方法對Piccolo-80 算法進行了安全性分析,給出了對于Piccolo-80 算法最低數(shù)據(jù)復(fù)雜度的攻擊結(jié)果.

密鑰劃分選取()為活動比特位,劃分80 bits 主密鑰為272個集合,每一子密鑰集合包含28個密鑰K[i,j],(i,j ∈{0,1}4).

Stars 結(jié)構(gòu)構(gòu)造首先依據(jù)劃分的密鑰空間,利用對應(yīng)的輪密鑰構(gòu)造相關(guān)密鑰差分路徑?i、?j,該兩條差分中沒有重合的F函數(shù),因此構(gòu)造得到了一個明文方向的4 輪8 維的Stars 結(jié)構(gòu).具體結(jié)構(gòu)見圖7.

圖7 Piccolo-80 算法的4 輪8 維Stars 結(jié)構(gòu)Figure 7 4 rounds of 8-dimensional Stars structure of Piccolo-80

狀態(tài)匹配與3.1 節(jié)介紹的狀態(tài)匹配過程類似,根據(jù)構(gòu)造得到的8 維Stars 結(jié)構(gòu),在第10 輪進行匹配,選取匹配向量的位置為.由圖8 可得,前向匹配中需對2.75 個F函數(shù)進行預(yù)計算,2.25 個F函數(shù)進行24次重計算,11.25 個F函數(shù)進行28次重計算,后向匹配中完成匹配需要對1 個F函數(shù)進行24次重計算,19.25 個F函數(shù)進行28次重計算.

圖8 Piccolo-80 算法的Stars 攻擊匹配階段Figure 8 Matching phase of Stars attack for Piccolo-80

密鑰篩選由于使用的匹配向量共28個可能值,因此平均一個錯誤密鑰通過篩選的概率為2?8.又由每個密鑰子集合中含有28個密鑰,則平均得到了1 個候選密鑰.最后,對每一密鑰子集合進行一次全輪加密,檢驗得到初始的正確密鑰.對于Piccolo-80 算法的Stars 攻擊所需復(fù)雜度由定理2 給出.

定理2利用4 輪8 維Stars 結(jié)構(gòu)對Piccolo-80 算法進行攻擊,能夠以最低的數(shù)據(jù)復(fù)雜度恢復(fù)出主密鑰,其數(shù)據(jù)復(fù)雜度為2,存儲復(fù)雜度為28.12,計算復(fù)雜度為279.31.

證明:存儲復(fù)雜度包括Stars 結(jié)構(gòu)以及預(yù)計算的F函數(shù)這兩部分.對于Stars 結(jié)構(gòu),共需存儲(24+24)×8=28個字節(jié),F函數(shù)需存儲2.75×8 個字節(jié),即上述攻擊所需存儲復(fù)雜度為28.12個字節(jié).

攻擊所需的計算復(fù)雜度包括構(gòu)造Stars 結(jié)構(gòu)、攻擊匹配階段以及密鑰篩選階段三部分.其中,結(jié)構(gòu)構(gòu)造所需的計算復(fù)雜度為CStars=匹配階段所需的計算復(fù)雜度總計為Cmatch=次全輪Piccolo-80 加密,密鑰篩選階段的計算復(fù)雜度為Cfalse=1.因此上述攻擊所需的計算復(fù)雜度總計為C=272×(2?0.9+27.30+1)≈279.31次全輪Piccolo-80 加密.數(shù)據(jù)復(fù)雜度方面,使用2 個明密文對,使得攻擊成功率為1.

4 Piccolo-128算法的Biclique分析

本節(jié)中主要介紹對Piccolo-128 算法的非平衡Biclique 攻擊和Stars 攻擊.在進行非平衡Biclique攻擊時,由于Piccolo-128 算法的密鑰擴展方式的約束,我們不采用第3 節(jié)中Biclique 結(jié)構(gòu)的構(gòu)造方法,而是通過選取特定的密鑰差分,基于文獻[8]的方法直接構(gòu)造(4,8)非平衡Biclique 結(jié)構(gòu).雖然使得構(gòu)造結(jié)構(gòu)所需的計算復(fù)雜度增加,但相應(yīng)的降低了匹配階段的計算復(fù)雜度,使得整體攻擊所需復(fù)雜度有所優(yōu)化.下面對具體攻擊進行介紹.

4.1 Piccolo-128算法的(4,8)非平衡Biclique分析

基于密鑰擴展算法的影響,我們從明文方向直接構(gòu)造Biclique 結(jié)構(gòu),攻擊步驟與第3.1 節(jié)對Piccolo-80算法的攻擊相同.

密鑰劃分選取()為活動比特位,令K[0,0]為上述兩個位置密鑰為0,其余比特遍歷的主密鑰.劃分128 bits 主密鑰為2116個集合,每一子密鑰集合包含212個密鑰K[i,j](i∈{0,1}4,j∈{0,1}8).K[i,j]定義為由K[0,0]與兩個密鑰差分、組成,其中

Biclique 結(jié)構(gòu)構(gòu)造基于劃分的密鑰空間,利用對應(yīng)的輪密鑰構(gòu)造相關(guān)密鑰差分路徑?i、?j,顯然(?i,?j)中沒有重合的活動F函數(shù),因此構(gòu)造得到了一個明文方向的5 輪(4,8)非平衡Biclique 結(jié)構(gòu)({Pi},{Sj},K[i,j]),i∈{0,1}4,j∈{0,1}8.具體結(jié)構(gòu)詳見圖9(a).

狀態(tài)匹配基于上述構(gòu)造得到的一個5 輪(4,8)非平衡Biclique 結(jié)構(gòu),得到24個狀態(tài)Pi,在選擇明文條件下,得到對應(yīng)的24個密文狀態(tài)Ci.選擇第17 輪的第6 個字節(jié)的左半部分為匹配向量,即,前向匹配過程為由Sj向下加密12 輪,后向匹配過程Ci向上解密9 輪.結(jié)合引理1,在前向匹配時只需對圖中5.875 個F函數(shù)進行預(yù)計算,14.375 個F函數(shù)進行24次重計算,即可完成匹配,完成后向匹配需要對圖中9.75 個F函數(shù)進行預(yù)計算,16.5 個F函數(shù)進行28次重計算.匹配過程如圖9(b)所示.

密鑰篩選由于使用的匹配向量共28個可能值,因此平均一個錯誤密鑰通過篩選的概率為2?8,即得到了24個候選密鑰.最后,每次攻擊均對剩余的24個候選密鑰進行全輪加密,檢驗得到初始的正確密鑰.上述對于Piccolo-128 算法非平衡Biclique 攻擊所需的復(fù)雜度由定理3 給出.

定理3基于5 輪(4,8)非平衡Biclique 結(jié)構(gòu)對Piccolo-128 算法進行攻擊,可恢復(fù)全輪Piccolo-128算法的主密鑰,其數(shù)據(jù)復(fù)雜度為220,存儲復(fù)雜度為211.17,計算復(fù)雜度為2127.05.

證明:由圖9 可得,對每一個Biclique 結(jié)構(gòu),需要固定明文(P0,P1,,)差分不活動,其余位置遍歷所有可能值,因此攻擊所需的數(shù)據(jù)復(fù)雜度為220個選擇明文.攻擊中需順序存儲24個明文和28個中間狀態(tài)的對應(yīng)關(guān)系以及匹配階段預(yù)計算的(5.875+9.75)個F函數(shù),因此存儲復(fù)雜度為(24+28+5.875+9.75)×8 ≈211.17個字節(jié).計算復(fù)雜度方面,在Biclique 結(jié)構(gòu)構(gòu)造時,需要預(yù)計算10 個F函數(shù),0.625 個F函數(shù)進行24次重計算,8.25 個F函數(shù)進行28次重計算,即次全輪Piccolo-128 加密.匹配階段的計算復(fù)雜度為29.93+210.10≈211.01,又由Cfalse=24,因此,計算復(fù)雜度總計為C=2116×(25.10+211.01+24)≈2127.05次全輪Piccolo-128 加密.

4.2 Piccolo-128算法的Stars攻擊

該部分的攻擊過程與Piccolo-80 算法的Stars 攻擊相似,這里就進行簡要介紹.

密鑰劃分利用性質(zhì)1,選取()為活動比特位,劃分128 bits 主密鑰為2120個集合,每一子密鑰集合包含28個密鑰K[i,j],(i,j∈{0,1}4).

Stars 結(jié)構(gòu)構(gòu)造首先依據(jù)劃分的密鑰空間,利用對應(yīng)的輪密鑰構(gòu)造相關(guān)密鑰差分路徑?i、?j,該兩條差分中沒有重合的F函數(shù),因此構(gòu)造得到了一個明文方向的4 輪8 維的Stars 結(jié)構(gòu).

狀態(tài)匹配根據(jù)構(gòu)造得到的8 維Stars 結(jié)構(gòu),在第16 輪進行匹配,選取匹配向量的位置為.則前向匹配過程中需對1 個F函數(shù)進行24次重計算,19.25 個F函數(shù)進行28次重計算,后向匹配中完成匹配需要對4.75 個F函數(shù)進行預(yù)計算,2.25 個F函數(shù)進行24次重計算,21.25 個F函數(shù)進行28次重計算.

密鑰篩選由于使用的匹配向量共28個可能值,因此平均一個錯誤密鑰通過篩選的概率為2?8.因此可平均得到了1 個候選密鑰.最后,對每一密鑰子集合進行一次全輪加密,檢驗得到初始的正確密鑰.

圖9 Piccolo-128算法的非平衡Biclique 結(jié)構(gòu)和攻擊匹配階段Figure 9 Structure and matching phase of unbalanced Biclique attack for Piccolo-128

Piccolo-128 算法的Stars 攻擊結(jié)構(gòu)和匹配過程見圖10,圖10 中(a)表示4 輪8 維Stars 結(jié)構(gòu),(b)表示Stars 攻擊狀態(tài)匹配過程.定理4 給出了該攻擊的各類指標,證明過程與定理2 類似.

定理4利用4 輪8 維Stars 結(jié)構(gòu)對Piccolo-128 算法進行攻擊,能夠以最低數(shù)據(jù)復(fù)雜度恢復(fù)主密鑰,其數(shù)據(jù)復(fù)雜度為2,存儲復(fù)雜度為28.19,計算復(fù)雜度為2127.40.

圖10 Piccolo-128 算法的Stars 攻擊結(jié)構(gòu)和匹配階段示意圖Figure 10 Structure and matching phase of Stars attack for Piccolo-128

5 結(jié)束語

本文利用Biclique 攻擊方法對Piccolo 算法在非平衡Biclique 攻擊和Stars 攻擊下的安全性進行了評估,結(jié)合Piccolo-80 與Piccolo-128 算法的密鑰擴展的相關(guān)性質(zhì),分別給出了目前對于該兩種算法最低數(shù)據(jù)復(fù)雜度和最優(yōu)計算復(fù)雜度的Biclique 攻擊結(jié)果.分析表明,對于同一分組密碼算法,使用非平衡Biclique 攻擊方法所需的計算復(fù)雜度較平衡Biclique 攻擊更低,使用Stars 攻擊方法能夠以最低的數(shù)據(jù)復(fù)雜度恢復(fù)出算法主密鑰.而這三類Biclique 攻擊之所以均能以低于窮舉攻擊的復(fù)雜度實現(xiàn),主要在于密碼算法具有簡單的密鑰擴展,并且算法本身擴散性弱,存在多條獨立的差分路徑,從而能夠有效降低攻擊復(fù)雜度.

根據(jù)輕量級密碼算法擴散性強弱的不同,利用多種Biclique 攻擊方法所得的攻擊效果也不同,因此能否利用本文的方法,對更多的輕量級分組密碼算法,特別是SPN 結(jié)構(gòu)類、ARX 結(jié)構(gòu)類等算法有較好的攻擊效果是下一步研究的方向.