簡化版分組密碼KATAN32的相關(guān)密鑰立方攻擊

王明興

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

0 引言

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

與此同時，立方攻擊的技術(shù)也有了新的發(fā)展，在2017年的美密會上，TODO Y等人[8]提出了一種新的計算工具，稱為可分性。可分性的傳播路徑可以用混合整數(shù)線性規(guī)劃(Mixed Integer Linear Programming,MILP)的方法計算，這個方法的優(yōu)點是立方可以任意選取，而且立方的維數(shù)可以達(dá)到任意大。這種新的技術(shù)可以攻擊到832輪的序列密碼Trivium。

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

1 預(yù)備知識

1.1 多重集合的可分性

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

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

(1)

(2)

(3)

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

1.2 立方攻擊

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

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

(4)

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

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)的表達(dá)式可以如下計算：設(shè)XI={xi|i∈I}，當(dāng)XI取遍所有的可能的值，其他變量不賦值；對式(6)的左端取連加號，得到pS(I)，即:

(7)

對于攻擊者而言，密碼算法是一個黑盒子，是一個關(guān)于秘密變量和公開變量的復(fù)雜的多元布爾多項式，表示為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)的結(jié)構(gòu)，得到盡可能多的線性超級多項式；在線階段時，秘密變量是未知的，不允許選擇，敵手只能選擇公開變量，去訪問加密算法，得到輸出值；綜合兩個階段，恢復(fù)某些密鑰比特。詳細(xì)攻擊過程見文獻(xiàn)[2]。

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

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

性質(zhì)4[8]f(X,V)是一個多元多項式，X=(x0,x1,…,xn-1)是秘密變量，V=(v0,v1,…,vm-1)是公開變量，設(shè)一個立方索引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；假設(shè)沒有可分路徑(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è)計的，而且使用二次反饋函數(shù)。

KATAN32輪函數(shù)的結(jié)構(gòu)如圖1所示，在t+1輪時，加密算法更新關(guān)系式：

密鑰擴展算法的生成關(guān)系式為：

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

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

圖1 一輪KATAN32加密過程圖

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

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

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

表3 計數(shù)器的值

3.2 初步攻擊結(jié)果

使用文獻(xiàn)[8]中類似的方法，隨機選擇立方索引I，尋找超級多項式。結(jié)果發(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

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

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

4 立方攻擊結(jié)合相關(guān)密鑰攻擊

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

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

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

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

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

布爾多項式f(k,v)的復(fù)合布爾多項式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 結(jié)論

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