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

唐 鵬 袁 征，2

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

0 引 言

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

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

本文利用Biclique攻擊方法對輕量級分組密碼SKINNY- 64- 64進行分析，通過從明文方向尋找兩條不相交的差分路徑來構建Biclique結構，結合中間相遇攻擊的思路對SKINNY- 64- 64進行了全輪攻擊。

1 基礎知識

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

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

1.1.1 SKINNY- 64- 64的初始化

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

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

1.1.2 SKINNY- 64- 64的輪函數

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

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

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

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

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

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

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

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

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

圖1 分組密碼SKINNY- 64- 64的輪函數

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

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

1.2 Biclique攻擊方法的描述

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

1.2.1 明文方向的平衡型Biclique結構

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

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

圖3 d維平衡型Biclique結構

1.2.2 使用相關密鑰差分構造的獨立型Biclique結構

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

1.2.3 部分匹配及密鑰檢測

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

1.2.4Biclique攻擊的復雜度計算

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

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

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

2 對SKINNY- 64- 64的Biclique攻擊

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

圖4 中間狀態位置標記

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 從明文方向構造6輪4維的Biclique結構

圖和

圖8 由前項差分Δ和后向差分構造的 覆蓋1-6輪的Biclique結構

2.1.3 向后匹配26輪

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

2.1.4 攻擊復雜度的計算

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

3 結 語

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

表2 對SKINNY- 64- 64的攻擊復雜度比較