Piccolo算法的Biclique分析*

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

信息工程大學,鄭州 450001

1 引言

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

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

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

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

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

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

2 相關知識

2.1 符號說明

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

Pi:Biclique 結構明文狀態(tài)

Ci:Biclique 結構密文狀態(tài)

Sj:Biclique 結構中間狀態(tài)

Vi,j:匹配向量位置

wkt:第t個白化密鑰

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

2.2 Piccolo 算法

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

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

圖1 Piccolo算法結構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ù)的具體構造.

表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ù)異或所得,具體對應關系見表3.對于Piccolo-128,與Piccolo-80 主要區(qū)別在于主密鑰增加了6 個字節(jié),得到K=K0||K1||K2||K3||K4||K5||K6||K7,相應的白化密鑰也有所變化,即輪密鑰r∈{0,···,30},具體對應關系見表4.Piccolo 算法的具體構造詳見文獻[7].

2.3 Biclique攻擊方法介紹

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

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

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

2.3.1 Biclique結構構造

簡單來說,一個Biclique 結構就是一個二分圖,一般通過三元組的形式表示.令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 結構.當d1=d2=d0 時,將其稱為平衡Biclique 結構,當d1=0,d2=d0時稱為Stars 結構,d1d2且均不為0 時為非平衡Biclique 結構.下面詳細介紹非平衡Biclique 結構的構造方法,圖4 為一般的Biclique 結構示意圖.

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

圖4 Biclique 結構示意圖Figure 4 Biclique structure

2.3.2 Biclique 攻擊流程

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

其中f表示構造Biclique 結構的子算法,進而可將Biclique 攻擊分為以下四步.

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

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

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

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

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

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

3 Piccolo-80算法的Biclique分析

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

性質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 次.進而想要使得攻擊效果更好,在構造Biclique 結構時,應盡量選擇在K4上進行密鑰劃分.同樣的,對于Piccolo-128 算法的密鑰擴展算法中的每一Ki,i∈{0,1,···,8},除白化密鑰外,K0、K1出現(xiàn)的次數(shù)均為7 次,其余均為8 次.因此選擇在這兩個密鑰位置進行密鑰劃分能使得攻擊結果更優(yōu).

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

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

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

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

密鑰劃分借助性質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 結構構造首先依據(jù)劃分的密鑰空間,利用對應的輪密鑰構造相關密鑰差分路徑?i、?j1、?j2,如圖5 所示.顯然(?i,?j1)和(?i,?j2)中沒有重合的F函數(shù),因此構造得到了兩個密文方向的6輪(4,4)平衡Biclique 結構.然后利用文獻[18]中的構造方法,將這兩個平衡Biclique 結構進行組合,就得到了一個6 輪(4,8)非平衡Biclique 結構({Sj1,j2},{Ci},K[i,j1,j2]).

狀態(tài)匹配根據(jù)構造得到的一個6 輪(4,8)非平衡Biclique 結構,得到24個狀態(tài)Ci,通過正確密鑰解密得到對應的24個明文狀態(tài)Pi.選擇與文獻[17]相同的匹配向量,即第10 輪的第6 個字節(jié)為匹配向量,也就是由Pi向下加密10 輪,定義為前向匹配過程,Sj1,j2向上解密9 輪,定義為后向匹配過程.結合引理1,在前向匹配時只需對圖中2.75 個F函數(shù)進行預計算,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)表示兩者結合,在前向匹配過程中需要重計算的活動比特情況.(d)表示后向匹配過程中重計算的活動比特情況.后向匹配過程需要對圖中2.75 個F函數(shù)進行預計算,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 攻擊所需的復雜度.

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

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

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

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

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

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

3.2 Piccolo-80算法的Stars攻擊

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

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

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

圖7 Piccolo-80 算法的4 輪8 維Stars 結構Figure 7 4 rounds of 8-dimensional Stars structure of Piccolo-80

狀態(tài)匹配與3.1 節(jié)介紹的狀態(tài)匹配過程類似,根據(jù)構造得到的8 維Stars 結構,在第10 輪進行匹配,選取匹配向量的位置為.由圖8 可得,前向匹配中需對2.75 個F函數(shù)進行預計算,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 攻擊所需復雜度由定理2 給出.

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

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

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

4 Piccolo-128算法的Biclique分析

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

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

基于密鑰擴展算法的影響,我們從明文方向直接構造Biclique 結構,攻擊步驟與第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 結構構造基于劃分的密鑰空間,利用對應的輪密鑰構造相關密鑰差分路徑?i、?j,顯然(?i,?j)中沒有重合的活動F函數(shù),因此構造得到了一個明文方向的5 輪(4,8)非平衡Biclique 結構({Pi},{Sj},K[i,j]),i∈{0,1}4,j∈{0,1}8.具體結構詳見圖9(a).

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

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

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

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

4.2 Piccolo-128算法的Stars攻擊

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

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

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

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

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

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

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

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

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

5 結束語

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

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