基于混合整數線性規劃的八陣圖不可能差分分析

杜小妮 梁麗芳 賈美純 李鍇彬

①(西北師范大學數學與統計學院 蘭州 730070)

②(西北師范大學計算機科學與工程學院 蘭州 730070)

③(西北師范大學密碼技術與數據分析重點實驗室 蘭州 730070)

④(甘肅省數學與統計學基礎學科研究中心 蘭州 730070)

1 引言

近年來，伴隨無線傳感器網絡以及射頻識別技術的發展和廣泛應用，需要輕量級分組密碼對資源受限的設備進行數據加密。這類算法具有效率高、功耗低、占用資源少等優點，且易于在軟硬件上實現。目前提出了許多輕量級分組密碼算法[1-5]，比較經典的算法有PRESENT, LBlock, WARP等。

ESF算法是2013年Liu等人[6]基于LBlock改進的輕量級分組密碼算法，適用于傳感器網絡等資源有限的環境。該算法置換層采用了PRESENT中比特置換的設計思想，在提高軟硬件實現效率的同時，使得硬件面積相比LBlock減少20個等效行。針對ESF算法的安全性分析主要是不可能差分密碼分析[7,8]，該分析的思想來源于差分密碼分析，利用中間相錯[9]的原理推導出概率為零的差分路徑，從而排除錯誤密鑰。當所有錯誤密鑰均被排除時，攻擊者就可確定正確密鑰。近些年，針對ESF算法的分析結果較多。2013年，劉宣等人[10]首次給出了ESF算法的8輪不可能差分區分器，在此區分器基礎上，通過前面加2輪后面加1輪的方法，實現了對該算法的11輪攻擊；2016年，陳玉磊等人采用文獻[11]中的區分器，通過向前添加1輪，向后添加2輪的擴展方式實現了相同輪數的攻擊，與文獻[10]相比，時間復雜度和數據復雜度均有效降低；2017年，高紅杰等人[12]同樣采用文獻[10]中的區分器，通過向前向后各添加2輪的擴展方式，實現了對ESF算法12輪攻擊，與文獻[11]相比，攻擊輪數提高了一輪，數據復雜度仍保持不變；2018年，謝敏等人[13]首次對ESF進行了相關密鑰不可能差分分析，結合算法特點構造了兩條10輪相關密鑰不可能差分路徑，對ESF分別進行了13輪和14輪不可能差分分析；2019年，李明明等人[14]基于8輪截斷不可能差分區分器，對ESF進行了13輪不可能差分分析，與文獻[10-12]相比，實現了更多輪數的攻擊；2021年，Li等人[15]利用自動化搜索方法，對ESF算法進行了基于比特可分性質的積分分析，給出了ESF算法9輪積分區分器的自動搜索方法；同年，Wu等人[16]同樣采用自動化搜索方法搜索到9輪不可能差分區分器，并對其進行驗證，且從中選取一條區分器，通過向前向后各添加3輪的擴展方式實現了15輪攻擊，相比現有結果，攻擊輪數明顯提高。

受文獻[17]的啟發，本文的主要貢獻包括兩個方面：

(1) 利用ESF算法的結構特性，研究得到了S盒的差分傳播規律，構建了基于MILP的ESF差分搜索模型，并利用中間相遇的原理，得到了 ESF算法輪數更長的不可能差分區分器。

(2) 基于9輪不可能差分區分器，通過向前添加2輪和向后添加4輪的擴展方式，給出了15輪的擴展路徑，并成功實現了15輪單密鑰不可能差分攻擊。攻擊過程的數據復雜度和時間復雜度分別為260.16和 267.44。與文獻[16]相比，數據復雜度和時間復雜度均明顯降低。

本文第2節簡要描述ESF算法；第3節給出ESF算法基于MILP的有效差分路徑的搜索算法；第4節給出ESF算法的不可能差分分析；第5節總結全文。

2 算法描述

為了便于算法描述，下面給出符號說明：

X: 64 bit明文

Y: 64 bit密文

Li: 第i輪輸出的左 32 bit

Ri: 第i輪輸出的右 32 bit

K: 80 bit的主密鑰

Ki: 第i輪的 32 bit子密鑰

Ki,j:Ki的第j個半Byte

Kih,j:Ki,j的第hbit

Si: 4×4 的 第i個S盒

P: 比特置換

[i]2: 常數i的二進制表示

2.1 算法加密過程

ESF是一種輕量級分組密碼算法，整體結構采用LBlock的設計準則和 PRESENT 線性層按比特置換的思想，以實現更快的擴散。ESF算法采用廣義Feistel結構，算法的分組長度為64 bit，密鑰長度為80 bit，迭代輪數為32輪。一輪算法加密流程如圖1所示。

圖1 ESF 算法結構

加密流程如下：

(1) 輸入 64 bit的明文

i=1,2,...,31

(2) 當 時，

(3) 當i=32時，

(4) 輸出密文

ESF算法的輪函數為SPN結構，如圖2所示，由混淆層和置換層構成，其中混淆層是一個 4×4的非線性替換，由8個并行的S盒構成，S盒如表1所示；置換P將3 2 b i t 的b31||b30||...||b0映射為c31||c30||...||c0，即

表1 ESF的S盒

圖2 ESF 算法輪函數

2.2 密鑰擴展算法

ESF算法主密鑰長度為80 bit，經過更新，每輪產生32 bit的輪子密鑰。首先將K=(k79k78...k1k0)存儲在寄存器中，取最左端的32 bit密鑰作為K1，對于i=1,2,...,31輪密鑰更新如下：

3 基于MILP的有效差分路徑搜索

3.1 ESF算法 S 盒的差分傳播特性

定義1 (S盒差分分布表[17]) 設m,n ∈N，從到的非線性映射(稱S盒)記為S:→，給定∈,β ∈，定義

其中NS(α,β) 表 示第α行 第β列的取值。由式(6)可構造ESF算法S盒的差分分布表(此處以S0為例)，如表2所示。

表2 ESF 的S0盒差分分布表

定理1[18]若給定S盒的輸入差分值，那么對應S盒的輸出差分值至少有1 bit的概率為1，且稱概率為1的bit為未受干擾比特。

分析表2可知，給定S0盒的輸入差分值，其輸出差分存在一定的規律。例，當α=0010，β的取值分別為1 001,1010,1100,1101,1110,1111，觀察發現輸出差分的第3 bit取值為1，其余3 bit的取值可為1或0，輸出差分可記為 1***(* 表示未知比特)。同理，根據ESF算法 8個S盒的差分分布表，給定 S 盒的輸入差分值，輸出差分值存在的傳播特性如表3所示。

表3 ESF的S盒差分傳播特性

輸入差分為某些值時，其輸出差分存在相應的概率，如表4所示。

表4 ESF的S盒差分概率傳播特性

3.2 基于MILP的有效差分路徑搜索算法

利用邏輯狀態模型和凸閉包計算，將3.1節中S盒的差分傳播特性用不等式表示，由此來移除不可能差分路徑，使得可行域的集合逼近ESF算法的有效差分路徑。搜索ESF算法加密方向有效路徑見算法1。

4 ESF算法的不可能差分分析

4.1 不可能差分分析

不可能差分分析由差分分析演變而來，近年來成為分組密碼安全性分析的常用方法之一。其基本思想是利用概率為0的差分路徑來構建區分器，通過該區分器排除導致概率為0的差分出現的候選密鑰，將篩選后剩下的密鑰作為正確密鑰。不可能差分的定義如下。

定義2 對于一個迭代分組密碼算法，設明文對(X,X*)的 差分值為 ΔX=α，第r輪 輸出對(Y,Y*)的差分值為 ΔY=β，若P(ΔY=β|ΔX=α)=0，則稱 (α?β) 為一條r輪不可能差分。

基于一條r-1 輪不可能差分區分器 (α?β)，r輪不可能差分分析流程如下：

(1) 選擇明文對 (X,X*) 滿足輸入差分α，加密得到相應的密文對 (Y,Y*)；

(2) 猜測第r輪的輪密鑰Kr，解密密文對，得到相應的中間值 (D,D*) ，判斷D ⊕D*=β是否成立。若成立，則對應的猜測值為錯誤密鑰。

(3) 重復以上步驟，直到密鑰唯一確定。

假設通過上述攻擊可以得到 |K| bit密鑰，且每個明密文對可以淘汰 2-t的密鑰量，要保證正確密鑰被唯一確定，所需明密文對n必須滿足

4.2 ESF算法的不可能差分攻擊

基于3.2節中的算法1，從加解密方向各找一條概率為1的差分路徑，利用中間相遇的思想，將其拼接并篩選出一條概率為0的最優差分路徑，搜索輪數最長的不可能差分區分器流程見算法2。將此思想應用于不可能差分分析中，可獲得輪數更長的不可能差分區分器。

ESF算法的分組長度為64 bit，遍歷所有可能差分的復雜度過高，故只對漢明重量為1的輸入/輸出差分進行搜索?；谒惴?，搜索并選取其中一條9區分器(0100 0000 0000 0000)?(1000 0000 0000 0000)，在此區分器基礎上通過向前擴展2輪向后擴展4輪實現了對ESF算法進行15輪不可能差分攻擊。具體路徑如圖3 所示，其中“ *”取任意值。

圖3 ESF的15輪不可能差分攻擊

定理2 利用9輪不可能差分區分器對ESF算法進行15輪不可能差分分析，攻擊過程明文量為 260.16，時間復雜度為 267.44。

依據 4.1 節中的攻擊原理，不可能差分攻擊過程如下。

(1) 選擇明文結構：輸入差分選擇滿足如式(8)形式的明文對

該結構由220個明文生成，共有 220×220×1/2=230個明文對。若選擇 2n個明文結構，則構成 2n+39個明密文對。

(2) 密文篩選：輸出差分選擇滿足如式 (9) 的密文對

經此步驟過濾大約剩余 2n+39×2-16= 2n+23個數據對。

(3) 猜測密鑰：

(a) 猜測K15，共32 bit。在K中對應的位置為K57-54,K53-50,K49-46,K45-42,K41-38,K37-34,K33-30,K29-26。對剩余密文對進行解密運算，由L14＜＜＜7=P ·S(R14⊕K15)⊕R15可知，排除不滿 足 ΔL14=(0000 000* 0000 000* 0000 000*0000 000*) 的 數據對，則剩余數據對個數為2n+23×2-28=2n-5。此步驟的時間復雜度為

算法2 尋找最長不可能差分區分器輪數

(b) 猜測K14,6,K14,4,K14,2,K14,0。它們在K中對應的位置為K66-63,K58-55,K48-45,K40-37，由于K57-55,K48-45,K40-37在(a)中已被猜測，故只需猜測剩余5 bit。對剩余數據對進行一輪解密運算，依次驗證式(10)

是否成立，經排除不滿足式(10)的數據對后，剩余數據對個數為 2n-5×2-16=2n-21。此步驟的時間復雜度為

4.3 結果對比

對ESF算法分析的常用方法是不可能差分分析。本文根據ESF算法的結構特性和S盒的差分傳播特性，實現了對ESF的15輪不可能差分攻擊。與文獻[16]相比，在攻擊輪數相同的條件下，時間復雜度和數據復雜度均得到有效降低。對比結果如表5所示。

5 結束語

本文利用ESF算法的S盒差分傳播特性，基于中間相遇思想，構建基于MILP的自動化搜索模型，搜索ESF的不可能差分區分器。選取了其中一條區分器，利用S盒的輸入輸出差分特征，分別向前添加2輪向后添加4輪，對ESF算法進行15輪不可能差分攻擊，且攻擊的時間復雜度低于窮舉攻擊的復雜度，與現有結果相比，攻擊效果也有較大的提升。在后續工作中，將考慮將多種分析方法結合，并優化搜索算法，找到更好的不可能差分區分器，進一步提高不可能差分攻擊的輪數。