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

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

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

0 引 言

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

CRAFT是一種新型SPN結構的類AES型輕量級可調分組密碼，由Christof Beierle等在FSE 2019上提出。它主要的設計標準之一是有效地抵抗差分故障攻擊，在相關可調模型中有著更強的安全界。考慮到基于輪函數硬件實現的引腳面積，CRAFT在相同狀態和密鑰大小下優于其他輕量級密碼。算法設計者在文獻[6]中對CRAFT的安全性進行了詳細介紹，該算法可以用許多方法進行分析，其中包括線性攻擊、差分攻擊、積分攻擊、中間相遇攻擊和零相關攻擊等。

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

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

1 CRAFT算法

1.1 算法描述

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

(1)

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

圖1 CRAFT算法的全輪加密結構

圖2 CRAFT的輪函數

1.2 CRAFT的輪函數

CRAFT的輪函數的5個操作如下：

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

表1 CRAFT中應用的4 bit S盒

2) MixColumn(MC):基于有限域GF(24)的半字節中間狀態矩陣與固定矩陣M進行相乘運算，矩陣M如下所示:

(2)

3) PermuteNibbles(PN):置換P被應用到中間狀態矩陣的每一個半字節位置上，對于所有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生成，分別用狀態a=(a3,a2,a1,a0)和b=(b3,b2,b1)來表示，兩個LFSRs的初始值分別為(0001)和(001)。在每一輪，中間狀態I4和I5分別與(a3,a2,a1,a0)和(0,b3,b2,b1)異或，隨后兩個LFSRs同步更新以便下一輪使用。表2展示了所有輪常量的16進制表示。

表2 CRAFT的輪常量

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

(3)

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

(4)

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

TK0=K0⊕T

(5)

TK1=K1⊕T

(6)

TK2=K0⊕Q(T)

(7)

TK3=K1⊕Q(T)

(8)

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

Ri=SB°PN°ATKi°ARCi°MC

(9)

(10)

1.3 S盒的代數表達式

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

2 相關知識

2.1 符號說明

(11)

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

(12)

2.2 基于比特的可分性

(13)

{k}K0→K1→…→Kr

2.3 基于比特可分性的傳遞規則

Todo[9]證明了傳統可分性的一些傳播規則，并將這些規則總結為5條，分別為置換、復制、異或、分支和集聯。而在這五條規則中，對于該算法僅僅用到復制和異或操作。

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

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

注意：(1,1)→(2)應該被丟棄，因為2?F2。

2.4 構建基本操作的MILP模型

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

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

(14)

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

(15)

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

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

2.5 初始條件和終止規則以及目標函數的設置

通過應用可分性的定義，任何漢明重量大于2的向量存在都表明著該狀態下的所有比特滿足零和性質。如果單位向量在輸出可分性質中出現，那么說明該單位向量中非零元素對應的比特位置不遵循零和性質。因此目標函數被設置為：

3 CRAFT算法應用

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

3.1 S層的線性不等式

表3 CRAFT的S盒可分路徑

續表3

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

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

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

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

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

4 CRAFT算法積分區分器搜索結果

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

表4 積分區分器搜索結果

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

4.1 12輪積分區分器

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

輸入：(aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaccccaaaaaaaaaaaaaaaaaaaaaaaaaaaa)

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

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

輸入：(aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaccccaaaaaaaaaaaaaaaaaaaaaaaa)

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

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

輸入：(aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaccccaaaaaaaaaaaaaaaaaaaa)

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

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

輸入：(aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaccccaaaaaaaaaaaaaaaa)

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

4.2 11輪積分區分器

由于以上4個12輪區分器平衡比特數較少，區分優勢不夠明顯。本文還搜索到了一條11輪積分區分器，其活躍比特數為60比特，平衡比特數為40比特。當第40、41、42、43位為常量輸入時：

輸入：(aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaccccaaaaaaaaaaaaaaaaaaaa)

輸出：(bbbbbbbbbbbb?bbbbbbbbbbbbbbbb?bbbbbbbbbbbb?)

4.3 9輪積分區分器

基于MILP搜索得到的平衡比特數最多，輪數最長的積分區分器，輸入60比特活躍，輸出64比特平衡的9輪積分區分器，當第32、33、34、35位為常量輸入時：

輸入：(aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaccccaaaaaaaaaaaaaaaaaaaaaaaaaaaa)

輸出：(bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb)

5 結 語

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

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