王明興

(中國電子信息產(chǎn)業(yè)集團有限公司第六研究所，北京 100083)

0 引言

立方攻擊是由DINUR I和SHAMIR A在2009年的歐密會上提出的[1]，作為一種新型的代數(shù)攻擊，其攻擊的思想是將密碼算法看成是一個未知的復雜的布爾多項式，輸入變量的明文或者初始向量稱為公開變量，密鑰比特稱為秘密變量。通過選擇一些公開變量，得到秘密變量的大量的簡單關系式，以此恢復密鑰比特。立方攻擊曾被用來分析過序列密碼，如Grain[2]、Trivium[3]等，結合側信道攻擊分析過分組密碼PRESENT[4]和SERPENT[5]，結合代數(shù)攻擊分析過79輪的KATAN32[6],結合條件差分攻擊分析過78輪的KATAN32[7]。

與此同時，立方攻擊的技術也有了新的發(fā)展，在2017年的美密會上，TODO Y等人[8]提出了一種新的計算工具，稱為可分性?？煞中缘膫鞑ヂ窂娇梢杂没旌险麛?shù)線性規(guī)劃(Mixed Integer Linear Programming,MILP)的方法計算，這個方法的優(yōu)點是立方可以任意選取，而且立方的維數(shù)可以達到任意大。這種新的技術可以攻擊到832輪的序列密碼Trivium。

本文使用這種立方攻擊的新技術，結合相關密鑰攻擊，得到了127輪的分組密碼KATAN32的部分密鑰信息，時間復雜度是274。與已有立方攻擊的結果比較，這是一個非常好的結果。

1 預備知識

1.1 多重集合的可分性

多重集合的可分性是TODO Y在2015年的歐密會上提出的[9]，是處理分組密碼的高階差分特征和積分特征的工具。TODO Y后來又提出了基于比特的可分性，定義如下：

定義2[11](可分路徑) 假設可分性質(zhì)的傳播為{k}K0→K1→…→Kr，進一步地，對任何向量必然存在一個向量使得可由可分性的傳播規(guī)則傳播到更進一步地，(k0,k1,…,kr)∈(K0×K1×…×K)，如果ki可以傳播到ki+1，i∈{0,1,…,r-1}，就把(k0,k1,…,kr)稱為一條r輪的可分路徑。

(1)

(2)

(3)

以這三種運算為基礎，就可以把整個密碼算法建模成MILP問題，使用Gurobi軟件可以很容易地計算出所有的可分路徑。

1.2 立方攻擊

立方攻擊是一種新型的代數(shù)攻擊[1]，它利用了高級差分的技術。任何布爾多項式都可以表示成一種類似于多元多項式的帶余除法的分解，而可以要求余式是不能包含除式的全部變量的一個多項式。

布爾多項式f(x0,x1,…,xt)的代數(shù)正規(guī)型為：

(4)

設I={i0,i1,…,il}是集合U={0,1,2,…,t-1}的一個子集，I中元素的個數(shù)記為|I|，I被稱為是一個立方索引，CI={xi0,xi1,…,xil}稱為一個立方(cube)，設

tI=i∈Ixi

(5)

于是，

f(x0,x1,…,xt-1)=tI·pS(I)⊕r(x0,x1,…,xt-1)

(6)

這里pS(I)是一個與tI沒有相同變量的多項式，它被稱為是立方的超級多項式；r(x0,x1,…,xt-1)中的每一項至少缺失tI中的一個變量，換句話說，r中沒有tI這一單項式。pS(I)的表達式可以如下計算：設XI={xi|i∈I}，當XI取遍所有的可能的值，其他變量不賦值；對式(6)的左端取連加號，得到pS(I)，即:

(7)

對于攻擊者而言，密碼算法是一個黑盒子，是一個關于秘密變量和公開變量的復雜的多元布爾多項式，表示為f(x0,x1,…,xn-1,v0,v1,…,vm-1)，其中xi是秘密變量，i=0,1,…,n-1，vi是公開變量，i=0,1,…,m-1。立方攻擊是把多元布爾多項式表示成一種類似于式(6)的分解式，除式是某些公開變量的乘積，商式是秘密變量的簡單的多項式。

攻擊過程分為兩個階段：離線階段和在線階段。離線階段時，攻擊者可以選擇秘密變量和公開變量，執(zhí)行密碼算法，探知密碼系統(tǒng)的結構，得到盡可能多的線性超級多項式；在線階段時，秘密變量是未知的，不允許選擇，敵手只能選擇公開變量，去訪問加密算法，得到輸出值；綜合兩個階段，恢復某些密鑰比特。詳細攻擊過程見文獻[2]。

1.3 基于可分路徑尋找超級多項式

從立方攻擊的過程可知，立方攻擊成功的關鍵在于找到超級多項式是簡單情形的立方，顯然，線性的超級多項式是最簡單的情形；文獻[2]進一步推廣了超級多項式的簡單情形，即超級多項式中的變量的個數(shù)少，同時又是平衡的。如果找到這樣的立方，那么就可以恢復出超級多項式的表達式，進而實施密鑰恢復攻擊。下面的性質(zhì)是利用可分路徑來判定一個變量xj是否在超級多項式中的準則。

性質(zhì)4[8]f(X,V)是一個多元多項式，X=(x0,x1,…,xn-1)是秘密變量，V=(v0,v1,…,vm-1)是公開變量，設一個立方索引I={i0,i1,…,i|I|-1},kI是一個m維的向量，使得VkI=TI=vi0vi1…vi|I|-1，即如果i∈I,則ki=1，否則ki=0；向量ej=(0,0,…,0,1,0,…,0)，即在第j的位置上取值為1，而其他位置是0；假設沒有可分路徑(ej,kI)→1，那么xj不是超級多項式中的變量。

表1 使用MILP方法計算秘密變量

2 KATAN32分組密碼描述

KATAN系列分組密碼是由DUNKELMAN O等人CHES 2009上提出的[12]。該分組密碼是面向硬件的輕量級分組密碼算法，硬件代價非常低。它包括三個算法，分別是KATAN32、KATAN48和KATAN64，其分組長度分別為32比特、48比特和64比特，在本文只介紹KATAN32。其密鑰長度是80比特，加密輪數(shù)是254輪；密鑰擴展算法是一個線性反饋移位寄存器；加密算法是由兩個非線性反饋移位寄存器設計的，而且使用二次反饋函數(shù)。

KATAN32輪函數(shù)的結構如圖1所示，在t+1輪時，加密算法更新關系式：

密鑰擴展算法的生成關系式為：

3 KATAN系列分組密碼算法立方攻擊的過程

從KATAN32的描述中不難發(fā)現(xiàn)，如果把明文看作是初始向量(IV)，把密文看作是密鑰流，分組密碼KATAN32可以看作是序列密碼，而且非常類似于序列密碼Trivium，可以對KATAN32抵抗立方攻擊的安全性進行分析。在算法加密r輪后，選擇非線性反饋移位寄存器L2的第13個位置輸出的序列作為密鑰流，因為敵手可以獲得密文(或者說密鑰流)，因此假設是合理的。

圖1 一輪KATAN32加密過程圖

3.1 MILP模型的算法實現(xiàn)

首先通過使用復制運算、異或運算和且運算，建立了KATAN32算法的可分路徑的MILP模型。然后編程實現(xiàn)算法去尋找超級多項式變量數(shù)量少的立方，進行立方攻擊。算法2～算法4如表2～表4所示。

表2 KATAN32算法的可分路徑的MILP模型

表3 計數(shù)器的值

3.2 初步攻擊結果

使用文獻[8]中類似的方法，隨機選擇立方索引I，尋找超級多項式。結果發(fā)現(xiàn)，I={0～25}。

在60輪時，超級多項式中有31個密鑰變量，分別是

k1,k2,k20,k21,k31,k32,k33,k37,

k39,k41,k43,k45,k47,k49,k51,k53，

k55,k57,k58,k59,k61,k62,k63,k65,

k66,k67,k68,k69,k71,k72,k75

時間復雜度為226+31=257。實驗計算表明，當輪數(shù)增加時，時間復雜度將大于280。換句話說，對于分組密碼KATAN32，原來的方法只能攻擊到較低的輪數(shù)。

表4 KATAN32算法的可分路徑的MILP模型(續(xù))

4 立方攻擊結合相關密鑰攻擊

在文獻[13]中，同時使用立方攻擊和相關密鑰攻擊，攻擊了72輪的KATAN48。本節(jié)使用立方攻擊和相關密鑰攻擊。

設密鑰為k=(k0,k1,k2,…,kl)，相關密鑰k⊕a=(k0⊕a0,k1⊕a1,…,kl⊕al)。

設布爾多項式f(k,v)=tI·pS(I)(k,v)⊕r(k,v)，

設D={a0,a1,…,al}，定義多元布爾多項式：

記為FD(k,v)=tIPS(I)⊕R(k⊕a,v)。

布爾多項式f(k,v)的復合布爾多項式f(k⊕a,v)的代數(shù)正規(guī)型的項中不可能同時出現(xiàn)ki和ai，i=0,1,2,…,l，于是PS(I)的項中也不會同時出現(xiàn)ki和ai，i=0,1,2,…,l。這說明這種差分定義得到的PS(I)中包含的變量的個數(shù)會減少，同時能攻擊的更高輪數(shù)的KATAN32。

對于127輪的分組密碼KATAN32，超級多項式中有5個密鑰變量，分別是k41,k60,k71,k72,k76，立方變量的集合CI={a0,a1,…,a39,v0,v1,…,v28}。

5 結論

分組密碼KANTAN32 結構非常簡單，它的兩個非線性反饋移位寄存器的反饋函數(shù)是2次的。但是，在單密鑰的情景下，使用帶有可分性的立方攻擊，得到的結果并不理想?？赡艿脑蚴荎ATAN32的擴散和混淆的速度并不慢。然后，在相關密鑰的情景下，得到了比較好的攻擊結果。這說明在密碼分析中，兩種或者三種攻擊的手段聯(lián)合使用得到的攻擊的效果比只用一個攻擊的手段要好。