CRAFT算法基于比特可分性的積分區(qū)分器搜索

劉宗甫 袁 征,2 段曉慶 朱 亮

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

0 引 言

隨著RFID技術(shù)的廣泛應(yīng)用和物聯(lián)網(wǎng)的快速發(fā)展，輕量級分組密碼在過去十年中一直是一個非常熱門的研究領(lǐng)域。近年來，輕量級分組密碼因其分組長度相對較短、算法結(jié)構(gòu)簡單、加密速度快，在確保數(shù)據(jù)安全的同時降低了資源消耗和實(shí)施成本而被廣泛使用，因此分析其安全性也變得至關(guān)重要。現(xiàn)有的輕量級分組密碼有PRESENT[1]、PRINCE[2]、Midori[3]、MIBS[4]、SKINNY[5]等，其中許多已經(jīng)被定義為ISO標(biāo)準(zhǔn)，被廣泛應(yīng)用于各個領(lǐng)域。

CRAFT是一種新型SPN結(jié)構(gòu)的類AES型輕量級可調(diào)分組密碼，由Christof Beierle等在FSE 2019上提出。它主要的設(shè)計標(biāo)準(zhǔn)之一是有效地抵抗差分故障攻擊，在相關(guān)可調(diào)模型中有著更強(qiáng)的安全界。考慮到基于輪函數(shù)硬件實(shí)現(xiàn)的引腳面積，CRAFT在相同狀態(tài)和密鑰大小下優(yōu)于其他輕量級密碼。算法設(shè)計者在文獻(xiàn)[6]中對CRAFT的安全性進(jìn)行了詳細(xì)介紹，該算法可以用許多方法進(jìn)行分析，其中包括線性攻擊、差分攻擊、積分攻擊、中間相遇攻擊和零相關(guān)攻擊等。

積分攻擊[7]是目前對于CRAFT算法的有效攻擊之一，是Knudsen等在總結(jié)Square攻擊、Multiset攻擊和Saturation攻擊的基礎(chǔ)上提出的一種密碼分析方法。2015年，Todo[8]將積分性質(zhì)進(jìn)行了推廣，準(zhǔn)確地描述位于傳統(tǒng)ALL和BALANCE之間的隱含特征。通過將可分性考量在區(qū)分器的搜索過程中，即使分組密碼具有非雙射函數(shù)、基于比特的結(jié)構(gòu)和低代數(shù)次數(shù)的函數(shù)，積分區(qū)分器也能夠被構(gòu)造。同年Todo[9]將可分性與非線性組件布爾函數(shù)的代數(shù)次數(shù)相結(jié)合，對MISTY1進(jìn)行全輪攻擊。Xiang等[10]將比特可分性的追蹤轉(zhuǎn)化為MILP問題，而后借助一些開源的求解器實(shí)現(xiàn)積分區(qū)分器的自動化搜索，并將這種方法有效地應(yīng)用到一些輕量級分組密碼上。該方法不僅提升了原有的積分分析結(jié)果，而且使比特可分性的復(fù)雜度急劇下降，設(shè)計者和分析者的工作量也明顯減少。基于MILP的方法在很多以比特置換為線性層的積分區(qū)分器搜索中取得了很大的進(jìn)展，但對于具有非比特置換的線性層的適用性還尚不清楚。Sun等[11]將復(fù)制和異或模型進(jìn)行了推廣，使其適用于刻畫多輸出分支的復(fù)制和異或操作。不管線性層的運(yùn)算多么復(fù)雜，總能轉(zhuǎn)化成本源表示的形式，對非零元素的位置通過引入中間變量，使用復(fù)制和異或模型生成刻畫線性層的線性不等式組。由此，利用MILP方法自動化搜索積分區(qū)分器的適用性將更加趨于完善。

本文利用基于比特可分性的思想結(jié)合MILP方法對CRAFT算法進(jìn)行積分區(qū)分器的搜索，通過Python編程實(shí)現(xiàn)以較少的變量與約束不等式搜索到多條12輪積分區(qū)分器，這是目前為止利用自動化搜索得到的最長的積分區(qū)分器，同時還搜索到了一條輸出平衡比特數(shù)最多的9輪積分區(qū)分器和一條11輪積分區(qū)分器。

1 CRAFT算法

1.1 算法描述

輕量級分組密碼CRAFT的分組長度為64比特，密鑰長度為128比特，其內(nèi)部狀態(tài)值可用一個4×4的半字節(jié)方陣表示，使用符號Ii,j來表示位于狀態(tài)的第i行、第j列的半字節(jié)。假設(shè)以m表示CRAFT的64比特明文，m=m0‖m1‖…‖m14‖m15，以S表示中間狀態(tài)，其中Si=mi,0≤i≤15。

(1)

CRAFT是一個可調(diào)密鑰系統(tǒng)，以T表示64比特可調(diào)密鑰，同時將128比特初始密鑰K分為K0和K1兩個64比特密鑰。利用T、K0和K1可推導(dǎo)出4個64比特輪密鑰TK0、TK1、TK2、TK3，其中每一個輪密鑰也被看作一個4×4的半字節(jié)方陣。

圖1 CRAFT算法的全輪加密結(jié)構(gòu)

圖2 CRAFT的輪函數(shù)

1.2 CRAFT的輪函數(shù)

CRAFT的輪函數(shù)的5個操作如下：

1) SubBox(SB):CRAFT算法使用的S盒和Midori算法[3]使用的S盒是相同的。該4 bit的S盒被并置應(yīng)用16次，并且作用于中間狀態(tài)的每個半字節(jié)。所使用的S盒如表1所示。

表1 CRAFT中應(yīng)用的4 bit S盒

2) MixColumn(MC):基于有限域GF(24)的半字節(jié)中間狀態(tài)矩陣與固定矩陣M進(jìn)行相乘運(yùn)算，矩陣M如下所示:

(2)

3) PermuteNibbles(PN):置換P被應(yīng)用到中間狀態(tài)矩陣的每一個半字節(jié)位置上，對于所有0≤i≤15，輸入為Ii,輸出為IP(i)。其中:

P=[15,12,13,14,10,9,8,11,6,5,4,7,1,2,3,0]

4) AddConstantsi(ARCi):輪常量是由一個4 bit的LFSR和一個3 bit的LFSR生成，分別用狀態(tài)a=(a3,a2,a1,a0)和b=(b3,b2,b1)來表示，兩個LFSRs的初始值分別為(0001)和(001)。在每一輪，中間狀態(tài)I4和I5分別與(a3,a2,a1,a0)和(0,b3,b2,b1)異或，隨后兩個LFSRs同步更新以便下一輪使用。表2展示了所有輪常量的16進(jìn)制表示。

表2 CRAFT的輪常量

(a3,a2,a1,a0)→(a1⊕a0,a3,a2,a1)

(3)

(b2,b1,b0)→(b1⊕b0,b2,b1)

(4)

5) AddTweakeyi(ATKi):在給定的可調(diào)密鑰T的半字節(jié)上使用置換Q，Q=[12,10,15,5,14,8,9,2,11,3,7,4,6,0,1,13]。用TQ(i)來替換Ti,此處0≤i≤15。利用可調(diào)密鑰T和初始密鑰(K0‖K1)，根據(jù)式(5)-式(8)可推導(dǎo)出4個64 bit輪密鑰TK0、TK1、TK2、TK3。在每一輪中，沒有任何輪密鑰更新,用輪密鑰TKi mod 4與中間狀態(tài)對應(yīng)相加。

TK0=K0⊕T

(5)

TK1=K1⊕T

(6)

TK2=K0⊕Q(T)

(7)

TK3=K1⊕Q(T)

(8)

根據(jù)上述五種操作，輪函數(shù)Ri，i∈{0,1,…,30}被定義如下：

Ri=SB°PN°ATKi°ARCi°MC

(9)

(10)

1.3 S盒的代數(shù)表達(dá)式

設(shè)x=(x3,x2,x1,x0)和y=(y3,y2,y1,y0)分別為S盒的輸入和輸出，則S盒的代數(shù)規(guī)范式(ANF)為：

2 相關(guān)知識

2.1 符號說明

(11)

式中：x[i]1=x[i]；x[i]0=1。

(12)

2.2 基于比特的可分性

(13)

{k}K0→K1→…→Kr

2.3 基于比特可分性的傳遞規(guī)則

Todo[9]證明了傳統(tǒng)可分性的一些傳播規(guī)則，并將這些規(guī)則總結(jié)為5條，分別為置換、復(fù)制、異或、分支和集聯(lián)。而在這五條規(guī)則中，對于該算法僅僅用到復(fù)制和異或操作。

可分路徑為(0)→(0,0),(1)→(0,1),(1)→(1,0)。

可分路徑為(0，0)→0,(0，1)→1,(1，0)→1。

注意：(1,1)→(2)應(yīng)該被丟棄，因?yàn)??F2。

2.4 構(gòu)建基本操作的MILP模型

基于MILP自動化搜索比特可分性的核心思想在于將可分性的傳遞規(guī)則轉(zhuǎn)化為一系列線性不等式。下面構(gòu)造MILP模型來刻畫復(fù)制、異或和S盒的傳遞規(guī)則。

模型1復(fù)制。用(a)→(b0,b1)來表示復(fù)制操作的一條可分路徑，分離傳遞規(guī)則可描述為：

(14)

模型2異或。用(a0,a1)→(b)來表示異或操作的一條可分路徑，分離傳遞規(guī)則可描述為：

(15)

對S盒的刻畫。為了得到S盒的線性不等式組，首先利用Xiang等[10]中算法得到一個可分路徑的完整列表，接下來調(diào)用SageMath軟件的不等式產(chǎn)生器inequality_generator()生成刻畫S盒的線性不等式集合。通常這個集合規(guī)模很大，包含非常多的線性不等式。倘若將這些線性不等式全部添加所有到模型中，將會使得MILP問題在計算上不可解。為了解決這一個問題，Sun等[12]提出了貪心算法來約減不等式的數(shù)量，這使得計算的復(fù)雜度顯著降低。

對于基于復(fù)制、異或基本操作和S盒的算法，能夠構(gòu)建線性不等式集合來刻畫一輪可分性的傳遞規(guī)律。把這種過程迭代r次，我們將得到一個線性不等式系統(tǒng)來描述r輪可分性質(zhì)，該系統(tǒng)的所有可行解對應(yīng)所有r輪可分路徑。

2.5 初始條件和終止規(guī)則以及目標(biāo)函數(shù)的設(shè)置

通過應(yīng)用可分性的定義，任何漢明重量大于2的向量存在都表明著該狀態(tài)下的所有比特滿足零和性質(zhì)。如果單位向量在輸出可分性質(zhì)中出現(xiàn)，那么說明該單位向量中非零元素對應(yīng)的比特位置不遵循零和性質(zhì)。因此目標(biāo)函數(shù)被設(shè)置為：

3 CRAFT算法應(yīng)用

CRAFT算法采用了類AES結(jié)構(gòu)，輪函數(shù)由五部分組成，看上去結(jié)構(gòu)比較復(fù)雜，但總體上仍是由S層和線性層組成。輪密鑰加和輪常量加操作并不影響可分性質(zhì)的傳遞，因此本文不將其考量在內(nèi)。

3.1 S層的線性不等式

表3 CRAFT的S盒可分路徑

續(xù)表3

CRAFT的S盒包含48條可分路徑，這48條可分路徑形成了一個點(diǎn)集P，將這些點(diǎn)集輸入到Sage軟件中的inequality_generator()中，將返回52個線性不等式集合。再通過調(diào)用貪婪算法，將冗余的不等式刪掉，最終不等式的個數(shù)被縮減為5個。

3.2 線性層的線性不等式描述

利用MILP模型處理更加復(fù)雜的線性層是一個遺留的問題，Sun等[11]將復(fù)制和異或模型進(jìn)行了推廣，使其適用于刻畫多輸出分支的復(fù)制和異或操作。不管線性層的運(yùn)算多么復(fù)雜，總能轉(zhuǎn)化成本源表示的形式，對非零元素的位置通過引入中間變量，使用復(fù)制和異或模型生成刻畫線性層的線性不等式組。

分布在同一列的元素用來描述輸入比特的復(fù)制操作，即:

另一方面，同一行的變量將追蹤同一個輸出比特的異或運(yùn)算，所以有：

4 CRAFT算法積分區(qū)分器搜索結(jié)果

本節(jié)給出了CRAFT算法利用MILP工具搜索得到的積分區(qū)分器。通過建立CRAFT算法的自動化MILP模型，并將模型進(jìn)行Python編程實(shí)現(xiàn)，設(shè)定初始的分離特性，通過MILP模型算法就可以判定CRAFT存在幾輪的積分區(qū)分器，而且還可以確定區(qū)分器末端的哪些比特位置具有零和性質(zhì)。目前搜索到的CRAFT算法輪數(shù)最長的積分區(qū)分器為12輪，這也是已知CRAFT算法最長的積分區(qū)分器。其中輸入60個活躍比特數(shù)，輸出12比特平衡。但12輪區(qū)分器的平衡比特數(shù)較少，區(qū)分優(yōu)勢不夠明顯。為了取得更好的攻擊效果，本文同時還搜索到了一條擁有平衡比特數(shù)最多的9輪積分區(qū)分器和一條擁有輸出40比特平衡的11輪積分區(qū)分器。

表4 積分區(qū)分器搜索結(jié)果

本文假設(shè)“a”表示活躍，“b”表示平衡，“c”表示常數(shù)，“？”表示未知。

4.1 12輪積分區(qū)分器

積分區(qū)分器1，第32、33、34、35位為常量輸入。

輸入：(aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaccccaaaaaaaaaaaaaaaaaaaaaaaaaaaa)

輸出：(????????????????????bbbbbbbbbbbb????????????????????????????????)

積分區(qū)分器2，第36、37、38、39位為常量輸入。

輸入：(aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaccccaaaaaaaaaaaaaaaaaaaaaaaa)

輸出：(????????????????bbbb????bbbbbbbb????????????????????????????????)

積分區(qū)分器3，第40、41、42、43位為常量輸入。

輸入：(aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaccccaaaaaaaaaaaaaaaaaaaa)

輸出：(????????????????bbbbbbbb????bbbb????????????????????????????????)

積分區(qū)分器4，第44、45、46、47位為常量輸入。

輸入：(aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaccccaaaaaaaaaaaaaaaa)

輸出：(????????????????bbbbbbbbbbbb????????????????????????????????????)

4.2 11輪積分區(qū)分器

由于以上4個12輪區(qū)分器平衡比特數(shù)較少，區(qū)分優(yōu)勢不夠明顯。本文還搜索到了一條11輪積分區(qū)分器，其活躍比特數(shù)為60比特，平衡比特數(shù)為40比特。當(dāng)?shù)?0、41、42、43位為常量輸入時：

輸入：(aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaccccaaaaaaaaaaaaaaaaaaaa)

輸出：(bbbbbbbbbbbb?bbbbbbbbbbbbbbbb?bbbbbbbbbbbb?)

4.3 9輪積分區(qū)分器

基于MILP搜索得到的平衡比特數(shù)最多，輪數(shù)最長的積分區(qū)分器，輸入60比特活躍，輸出64比特平衡的9輪積分區(qū)分器，當(dāng)?shù)?2、33、34、35位為常量輸入時：

輸入：(aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaccccaaaaaaaaaaaaaaaaaaaaaaaaaaaa)

輸出：(bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb)

5 結(jié) 語

CRAFT算法的設(shè)計文檔對CRAFT算法抵抗積分攻擊的能力進(jìn)行了介紹，并提及基于比特可分性及結(jié)合MILP方法搜索的積分區(qū)分器是存在的，但沒有給出搜索到的具體積分區(qū)分器的輪數(shù)以及實(shí)現(xiàn)過程。本文利用該方法，得到了輪數(shù)最長為12輪的積分區(qū)分器，也證實(shí)了此方法無法找到超過13輪的積分區(qū)分器的結(jié)論。同時本文也找到了一個平衡比特數(shù)最多的9輪積分區(qū)分器和擁有40比特平衡的11輪積分區(qū)分器。可以利用搜索得到的區(qū)分器，根據(jù)相關(guān)密鑰恢復(fù)的方法進(jìn)行密鑰恢復(fù)攻擊，從而獲取部分密鑰信息。

相比傳統(tǒng)積分區(qū)分器尋找的方法，基于比特可分性結(jié)合MILP方法自動化搜索積分區(qū)分器已經(jīng)成為積分分析中一個強(qiáng)有力的工具[13-14]。本文實(shí)現(xiàn)自動化搜索的過程主要是把可分性在整個算法中的傳遞規(guī)則及其最終不具有積分特性的這個命題轉(zhuǎn)化成相應(yīng)的數(shù)學(xué)模型，調(diào)用數(shù)學(xué)工具來進(jìn)行自動化搜索，并且能在較短的時間里得到比傳統(tǒng)方法性質(zhì)更好的積分區(qū)分器，極大地提高了搜索的效率。但該方法仍舊有一定的局限性，比如每個S盒的約束數(shù)量和S盒的大小呈指數(shù)關(guān)系，對于一個8進(jìn)8出的S盒，采用文獻(xiàn)[10]中的方法產(chǎn)生的不等式不足以約束該S盒。解決S盒算法的適用性問題將是未來研究的主要方向。