對分組密碼SKINNY- 64- 64的Biclique攻擊

唐 鵬 袁 征，2

1(西安電子科技大學(xué) 陜西 西安 710071) 2(北京電子科技學(xué)院 北京 100071)

0 引 言

Biclique密碼分析方法是一種較為新穎的密碼分析技術(shù)。它由Khovratovich等在文獻[1]中被提出，后來在FSE 2012中被收錄。Biclique是一種完全二分圖，一個集合中的每個元素的初始狀態(tài)都和另一個集合中的結(jié)束狀態(tài)相聯(lián)系。在密碼分析過程中，在這種二分圖中的每一條路徑代表一個初始原語在一個唯一密鑰下經(jīng)過若干步驟后加密后的密文狀態(tài)。如果這些路徑不共享活躍的非線性部件，那么一個Biclique結(jié)構(gòu)就允許攻擊者可以高效地檢測候選密鑰的集合。這種Biclique結(jié)構(gòu)可以用來降低中間相遇攻擊的時間復(fù)雜度。起初Biclique被用于分析哈希函數(shù)，后來發(fā)現(xiàn)Biclique也適用于分組密碼的安全性分析。Bogdanov等在文獻[2]中采用Biclique對AES算法進行了攻擊。他們的成果得到了高度關(guān)注，因為他們利用Biclique攻擊首次實現(xiàn)了對AES單密鑰模式下的全輪攻擊。從那以后，基于Biclique的密鑰恢復(fù)攻擊開始被廣泛應(yīng)用于分組密碼的分析中。

分組密碼SKINNY由文獻[3]提出，它是SP結(jié)構(gòu)的分組密碼。SKINNY是一種可調(diào)分組密碼，分組長度和密鑰長度有多種版本。SKINNY- 64- 64是SKINNY分組密碼的64比特分組長度、64比特密鑰長度的版本。多種分組、密鑰長度版本使SKINNY能更好地適應(yīng)不同的應(yīng)用環(huán)境，它的軟硬件實現(xiàn)均有較好的性能。因此，對它的安全性進行分析有著極為重要的實際意義。

本文利用Biclique攻擊方法對輕量級分組密碼SKINNY- 64- 64進行分析，通過從明文方向?qū)ふ覂蓷l不相交的差分路徑來構(gòu)建Biclique結(jié)構(gòu)，結(jié)合中間相遇攻擊的思路對SKINNY- 64- 64進行了全輪攻擊。

1 基礎(chǔ)知識

1.1 輕量級分組密碼SKINNY- 64- 64的描述

輕量級分組密碼SKINNY，是在CRYPTO 2016上提出的一種新型分組密碼。SKINNY- 64- 64是SKINNY密碼中64比特分組長度、64比特密鑰長度的版本。本節(jié)將介紹SKINNY- 64- 64的加密算法和密鑰擴展算法。

1.1.1 SKINNY- 64- 64的初始化

以m表示SKINNY- 64- 64的64比特明文，m=m0‖m1‖…‖m14‖m15，mi為4比特狀態(tài)單位。以IS表示中間狀態(tài)，以矩陣形式給出，其中ISi=mi，0≤i≤15。

以tk表示64比特初始密鑰，tk=tk0‖tk1‖…‖tk14‖tk15，tki為4比特密鑰狀態(tài)單位。以TK表示輪密鑰，以矩陣形式給出，其中TKi=tki，0≤i≤15。

1.1.2 SKINNY- 64- 64的輪函數(shù)

SKINNY- 64- 64的加密輪數(shù)為32輪，分組長度為64比特，密鑰長度為64比特。

SKINNY- 64- 64的輪函數(shù)由以下5種操作組成：

1) 狀態(tài)單位替換(SubCells)：SKINNY- 64- 64使用的S盒，與PICCOLO密碼[4]所使用的S盒非常接近。SKINNY- 64- 64的中間狀態(tài)以4比特為單位通過4×4的S盒進行非線性變換。SKINNY- 64- 64所使用的4×4的S盒見表1。

表1 分組密碼SKINNY- 64- 64的S盒

2) 輪常量加(AddConstants)：輪常量與64比特中間狀態(tài)相加。

3) 輪密鑰加(AddRoundTweakey)：經(jīng)過密鑰編排算法得到的輪密鑰的前32比特，與64比特的中間狀態(tài)的前32比特對應(yīng)相加。

4) 行移位(ShiftRows)：中間狀態(tài)的每一行依次循環(huán)右移0、1、2、3個單位(4比特)。

5) 列混合(MixColumns)：64比特中間狀態(tài)矩陣與矩陣M相乘。矩陣M如下：

分組密碼SKINNY- 64- 64的輪函數(shù)如圖1所示。

圖1 分組密碼SKINNY- 64- 64的輪函數(shù)

1.1.3 SKINNY- 64- 64的密鑰編排算法

圖2 SKINNY- 64- 64的密鑰編排過程

1.2 Biclique攻擊方法的描述

Biclique攻擊的基本思路是通過構(gòu)造Biclique結(jié)構(gòu)來降低中間相遇攻擊的復(fù)雜度。在所構(gòu)造的Biclique結(jié)構(gòu)的基礎(chǔ)上，通過密鑰劃分、部分匹配、重新檢測候選密鑰等步驟來確定密鑰恢復(fù)的時間復(fù)雜度。Biclique結(jié)構(gòu)決定了攻擊的數(shù)據(jù)復(fù)雜度，部分匹配過程決定了攻擊的時間復(fù)雜度。

1.2.1 明文方向的平衡型Biclique結(jié)構(gòu)

Biclique結(jié)構(gòu)可以從明文方向構(gòu)造，也可以從密文方向構(gòu)造。這取決于密碼算法的結(jié)構(gòu)，以及對降低攻擊數(shù)據(jù)復(fù)雜度的綜合權(quán)衡。Biclique結(jié)構(gòu)分為平衡型和非平衡型(星型)兩種，本文使用平衡型Biclique結(jié)構(gòu)進行攻擊，非平衡型Biclique結(jié)構(gòu)的詳細(xì)介紹可以參考文獻[5]。本文對SKINNY- 64- 64的攻擊將從明文方向構(gòu)造Biclique結(jié)構(gòu)。從密文方向構(gòu)建Biclique結(jié)構(gòu)的過程與從明文方向構(gòu)建的過程類似，在此不再贅述，詳情可以參考文獻[2]。

明文P在函數(shù)f的作用下映射為中間狀態(tài)S：fK(P)=S。如果對2d個明文Pi、2d個中間狀態(tài)Sj以及2d個密鑰K[i,j]滿足關(guān)系Sj=fK[i,j](Pi)，則三元組[{Pi},{Sj},{K[i,j]}]稱為一個d維的平衡型Biclique結(jié)構(gòu)(見圖3 )。密鑰集合K[i,j]如下：

圖3 d維平衡型Biclique結(jié)構(gòu)

1.2.2 使用相關(guān)密鑰差分構(gòu)造的獨立型Biclique結(jié)構(gòu)

構(gòu)造獨立型的Biclique結(jié)構(gòu)，需要找到兩條不相交的密鑰差分路徑，通過這兩條密鑰差分路徑再構(gòu)造兩條不相交的差分路徑。因為這兩條差分路徑不相交(不共享任何活躍的非線性部件)，所以它們之間相互獨立，這兩條路徑就可以直接合并起來構(gòu)成獨立的Biclique結(jié)構(gòu)。下面來詳細(xì)介紹從明文方向用相關(guān)密鑰差分構(gòu)造獨立型Biclique結(jié)構(gòu)的過程。

1.2.3 部分匹配及密鑰檢測

最后對密鑰集中剩余的密鑰再次進行檢測，直到正確的密鑰找到為止。

1.2.4Biclique攻擊的復(fù)雜度計算

Biclique攻擊的密鑰恢復(fù)時間復(fù)雜度按如下公式計算：

Ctotal=2n-2d[Cbiclique+Cmatch+Crecheck]

式中：n為密鑰長度，d為Biclique結(jié)構(gòu)的維度。Cbiclique為構(gòu)造Biclique結(jié)構(gòu)的復(fù)雜度。Cmatch為部分匹配過程的復(fù)雜度，Cmatch等于前向匹配與后向匹配的復(fù)雜度之和，Cmatch=Cfoward+Cbackward。Crecheck為密鑰檢測復(fù)雜度。Biclique攻擊的存儲復(fù)雜度為2d。由于本文從明文方向構(gòu)造Biclique結(jié)構(gòu)，所以攻擊屬于選擇明文攻擊，攻擊的數(shù)據(jù)復(fù)雜度取決于所構(gòu)造的具體的Biclique結(jié)構(gòu)。

2 對SKINNY- 64- 64的Biclique攻擊

本節(jié)我們將利用Biclique攻擊方法對SKINNY- 64- 64進行攻擊。在進行Biclique攻擊過程中，SKINNY- 64加密的中間狀態(tài)和經(jīng)過密鑰編排算法后的子密鑰長度都是64比特。64比特的加密中間狀態(tài)和子密鑰均按圖4的位置順序來標(biāo)記每個半字節(jié)，圖中的每一格代表一個半字節(jié)(4比特)。

圖4 中間狀態(tài)位置標(biāo)記

2.1.1 密鑰劃分

對第1輪密鑰空間進行劃分。將基密鑰K[0,0]的第1、第12兩個個位置固定為0 ( 如圖5所示)，其他位置取遍所有可能的值，這樣基密鑰K[0,0]有214×4=256種可能的取值，也就是說第1輪密鑰被劃分為256個密鑰集合。{K[i,j]}表示在K[0,0]上取遍所有i和j可能的值(如圖6所示)，它有28個可能的取值，也就是說每個密鑰集合中有28個密鑰。這樣第1輪的密鑰空間就完成了完備劃分。

圖5 基密鑰K[0,0] 圖6 差分i和j

2.1.2 從明文方向構(gòu)造6輪4維的Biclique結(jié)構(gòu)

圖和

圖8 由前項差分Δ和后向差分構(gòu)造的 覆蓋1-6輪的Biclique結(jié)構(gòu)

2.1.3 向后匹配26輪

(a) (b) 圖9 SKINNY- 64- 64的前向匹配和后向匹配

2.1.4 攻擊復(fù)雜度的計算

我們將密鑰空間分為256個集合，每個集合中有密鑰28個，所以攻擊的存儲復(fù)雜度不超過28。

3 結(jié) 語

本文首先對輕量級分組密碼SKINNY- 64- 64進行了描述，然后介紹了Biclique攻擊方法。通過相關(guān)密鑰差分從明文方向構(gòu)造了獨立型Biclique結(jié)構(gòu)，在此結(jié)構(gòu)的基礎(chǔ)上對SKINNY- 64- 64進行了全輪攻擊，攻擊的時間復(fù)雜度為262.908，數(shù)據(jù)復(fù)雜度為248個選擇明文，時間復(fù)雜度優(yōu)于文獻[3]。這是目前使用平衡型Biclique結(jié)構(gòu)對SKINNY- 64- 64進行全輪攻擊的最優(yōu)攻擊結(jié)果。本文對SKINNY- 64- 64的攻擊結(jié)果與文獻[3]的攻擊結(jié)果的比較見表2。

表2 對SKINNY- 64- 64的攻擊復(fù)雜度比較