基于可分性改進分組密碼SM4 和FOX 的積分區分器*

毛永霞, 吳文玲

1.中國科學院 軟件研究所 可信計算與信息保障實驗室, 北京100190

2.中國科學院大學, 北京100049

3.河南師范大學 數學與信息科學學院, 新鄉453000

1 引言

積分分析是由Knudsen 等人[1]在FSE 2002 上提出來的.由于它首先被應用于分組密碼Square[2],因此也被稱為Square 攻擊.它是當前評估分組密碼算法安全性的基礎分析方法之一, 已經在許多分組密碼算法上得到了較好的攻擊結果, 例如AES[3]等.可分性是積分分析的推廣, 在EUROCRYPT 2015 上被Todo[4]首次提出.Todo 結合密碼算法非線性部件的代數次數, 優化了積分性質, 使得積分特征能夠用一種更精確的方式推導.一個顯著的應用是第一次在理論上對全輪的MISTY1 進行了積分攻擊[5].后來, Todo 等人[6]在FSE 2016 上又提出了更精細的比特級可分性(bit-based division property, BDP).在ASIACRYPT 2016 上, Xiang 等人[7]將基于混合整數線性規劃(mixed integer linear programming,MILP) 建模的方法引入比特級可分性, 進一步提高了積分區分器可自動化搜索的密碼算法的規模.2017年, Todo 等人[8]對上述MILP 模型進行了補充, 并將其應用于多個流密碼算法的立方攻擊, 得到了幾個流密碼當時最好的密鑰恢復攻擊.近幾年, 對分組密碼算法的積分區分器搜索的改進主要圍繞改進非線性層[9,10]和線性層[11–15]的可分性傳播模型來進行.

SM4[16]是由國家密碼管理局于2006 年1 月發布的分組密碼, 專為無線局域網標準設計, 2016 年被采納為國家標準, 2021 年被納入ISO/IEC 國際標準, 自發布以來一直是許多密碼分析者攻擊的目標.在積分分析方面, 2007 年, Liu 等人[17]利用特定的差分對和S 盒性質, 構造了SM4 的8 輪積分區分器.2012 年, Zhang 等人[18]對高階積分分析的概念進行擴展, 并提出了一種由內而外搜索高階積分區分器的方法, 構造了256 個Gen-SM4 結構的10 輪區分器.2015 年, Sun 等人[19]利用在特定條件下零相關線性殼與積分區分器的存在性之間具有某種關系, 構造了SM4 的12 輪積分區分器.2018 年, Eskandari 等人[20]利用可分性構造了12 輪的積分區分器.后來, 胡西超[21]提高了12 輪積分區分器的數據復雜度.

FOX[22]是一個分組密碼算法族, 應MediaCrypt AG 公司的要求而設計, 在各種平臺上使用時具有高靈活性和高實現性能的特點.它包含FOX64 和FOX128 兩個密碼算法, 分別具有64 比特和128 比特的分組長度: 每一個分組密碼又支持不同的密鑰長度, 具有不同的輪數.FOX 的整體結構是Lai-Massey結構, 輪函數是SPS 結構, 設計者證明了它對線性和差分分析是免疫的.2015 年, Qiao 等人[23]結合MILP 技術給出了更緊的差分活躍S 盒個數的下界.同年, 伊文壇等人[24]給出了FOX 的多維零相關線性分析.由于FOX 整體結構比較復雜, 目前已有的最長積分區分器是設計文檔給出的三個FOX64 的3輪積分性質.設計文檔聲稱4 輪FOX64/64、5 輪FOX64/128、6 輪FOX64/192、7 輪FOX64/256、5輪FOX128 對積分攻擊免疫, 但是Wu 等人[25,26]結合碰撞技術和積分攻擊改進了對FOX 的積分攻擊結果, 發現4 輪FOX64/64、5 輪FOX64/128、6 輪FOX64/192、7 輪FOX64/256、5 輪FOX128/256對積分攻擊均不免疫.

本文的貢獻如下.分支異或壓縮結構和非比特置換的線性變換是分組密碼的兩個基本部件.本文通過分析可分性在這兩個部件上傳播的特點, 分別提出了兩個建模策略.策略一通過增加約束條件維持部分輸入可分性經過首輪傳播的狀態, 使得這部分可分性在后續傳播中更有優勢; 策略二通過增加約束條件提高可分性經過線性變換傳播時的模型精度, 提高可分性傳播的效率.將兩個建模策略分別應用于分組密碼SM4 和FOX, 可以構造SM4 的13 輪積分區分器、FOX64 的3 輪積分區分器、FOX128 的3 輪積分區分器(表1 展示了與已有積分區分器的結果對比).這些區分器都優于相應密碼算法已知的最好積分區分器.

表1 SM4 和FOX 已有積分區分器的結果對比Table 1 Integral distinguisher results for SM4 and FOX

本文剩余的內容安排如下: 第2 節為預備知識, 主要介紹符號約定、可分性相關定義和建模規則;第3 節介紹針對兩種密碼部件提出的自動化方法的建模策略; 第4 節介紹兩個策略在分組密碼SM4 和FOX 上的應用; 第5 節是本文總結.

2 預備知識

2.1 符號和定義

對于一個分組密碼, 用下面的符號表示明文半字節和密文半字節的積分性質:

-C: 明文半字節的每一個比特都是常數;

-A: 明文半字節的每一個比特都是活躍的;

-B: 密文半字節的每個比特都是平衡的;

-U: 密文半字節的狀態是未知的.

2.2 可分性和可分跡

定義1 (比特級可分性[6]) 設X 是一個取值于Fm2的多重集,k ∈Fm2.當多重集X 有可分性D1,mK時, 滿足下面的條件:

2.3 結合自動化建模技術與比特級可分性搜索積分區分器

自動化搜索技術已經成為構造分組密碼區分器的主要方法, 借助數學工具提高搜索能力和效果是目前最流行的方法之一.利用SAT (satisfiability modulo theories)、MILP (mixed integer linear programming) 等數學工具搜索可分性在分組密碼上的傳播是目前構造積分區分器最常用的方法.這兩種數學工具的建模方式相似, 都是通過刻畫可分性在密碼基本部件上的傳播, 設置合理的目標函數, 將可分性傳播的搜索問題轉化為一個SAT 或MILP 問題.然后借助合適的求解器如Cryptominisat 或Gurobi 對模型進行求解, 最后根據求解結果和可分性判斷條件判斷是否存在積分區分器.下面簡要介紹基于MILP 的建模過程.

(1) 二元運算的建模規則

在基于比特的可分性傳播中, 文獻[4] 證明了可分性在5 種密碼基本部件上的傳播規則.本節介紹其中的兩種, 即可分性傳播在COPY 函數和XOR 函數(如圖1–2) 上的MILP 建模規則.

圖1 COPY 函數Figure 1 COPY

圖2 XOR 函數Figure 2 XOR

(2) S 盒的建模規則

例1 設S 是一個3 比特S 盒, 如表2 所示, (u,v) 表示可分跡uS?→v, 可求得如下17條可分跡: (0,0,0,0,0,0), (0,0,1,0,0,1), (0,0,1,0,1,0), (0,0,1,1,0,0), (0,1,0,0,0,1), (0,1,0,0,1,0),(0,1,0,1,0,0), (0,1,1,0,1,1), (0,1,1,1,0,0), (1,0,0,0,0,1), (1,0,0,0,1,0), (1,0,0,1,0,0), (1,0,1,0,1,0),(1,0,1,1,0,1), (1,1,0,0,0,1), (1,1,0,1,1,0), (1,1,1,1,1,1).

表2 一個3 比特S 盒Table 2 A 3-bit S-box

Step 1 寫出S 盒可分跡對應的真值表, 并將其導入Logic Friday;

Step 2 生成描述S 盒所有不可能可分跡對應點的析取范式并進行約簡;

Step 3 轉化成合取范式f=(u1+(v1+1)+(v0+1))(u0+(v1+1)+(v0+1))···;

Step 4 合取范式包含18 個因式,f為真當且僅當所有因式為真.因此每一個因式對應一個不等式.例如, 因式u1+(v1+1)+(v0+1) 對應不等式u1+(v1+1)+(v0+1)≥1.以此類推, 寫出所有不等式.這18 個不等式就刻畫了比特級可分性在S 盒上的傳播.

3 自動化分析方法的兩種有效建模策略

輔助數學工具的自動化分析方法的建模策略非常重要, 它會直接影響模型的中間狀態和求解空間, 也決定著模型的精度, 因此經常會影響可分性的搜索結果.目前, 盡管基于自動化建模方法描述可分性傳播的技術已經非常成熟, 但實際中往往會產生誤報, 即輸出可分性為單位向量的可分跡的存在性并不能確保該輸出位置的積分區分器不存在.正如Derbez 等人所說[28], 可分性的核心是追蹤單項式通過迭代函數的傳播, 而誤報是因為在追蹤過程中沒有恰當地處理異或操作導致的.例如, 設p和q是兩個包含變量x的多項式,p=xp1⊕p2,q=xq1⊕q2.盡管p和q都依賴變量x, 但是p ⊕q是不清楚的.為了保持建模過程簡單, 通常假設p ⊕q在定義1 的可分性下仍舊依賴變量x.顯然, 這種假設有時候并不正確.在分組密碼的輪函數中, 非比特置換的線性層部分通常包含最多的異或運算.為了降低異或運算因為建模方式帶來的誤差, 提高可分性傳播模型的精度, 許多密碼學者提出了針對線性層建模的改進方法[11–15].本節針對兩種包含異或操作的密碼部件: 分支異或壓縮結構和非比特置換的線性變換, 分別提出了基于模型的中間狀態和基于模型的精度進行改進的建模策略.

3.1 策略一: 針對分支異或壓縮結構的建模

Feistel 結構一輪的擴散速度通常沒有SP 結構一輪的擴散速度快, 因此需要更多的輪數保證相同水平的安全強度.為此, 密碼設計者有時候將整體采用Feistel 結構的分組密碼的輸入分支經過異或壓縮處理,例如Gen-SM4 結構(圖3).類似地, 安全強度看起來更高的Lai-Massey 結構也包含分支異或壓縮部件(例如圖4).在傳統構造積分區分器的方法中, 密碼分析者通常將參與異或壓縮的分支選擇相同的明文結構, 從而確保經過一輪迭代之后, 壓縮輸出的分支是非活躍狀態, 進而使得初始輸入狀態可以傳播得更遠,最終達到獲得更優積分區分器的目的.受此啟發, 我們對具有這類密碼部件的分組密碼建立可分性傳播模型時, 采用深度優先的建模策略, 即為異或壓縮的參與分支的輸入可分性添加約束條件, 舍棄一部分有效可分跡, 只保留經過該結構之后輸出活躍位置最少的可分性狀態, 從而達到可分性具有更優傳播效果的目的, 具體過程如策略一所述.

圖3 SM4 的一輪變換Figure 3 Round function of SM4

圖4 FOX64 的一輪變換Figure 4 Round Function of FOX64

圖5 FOX128 的一輪變換Figure 5 Round Function of FOX128

策略一: 設密碼算法的輪函數包含t個輸入分支參與異或壓縮, 每個分支長度為n比特, 異或壓縮函數F⊕: (Fn2)t →Fn2描述為(X1,X2,···,Xt)⊕?→Y.這t個分支第i比特對應的可分跡記為(a1i,a2i,···,ati)→bi, 0≤i ≤n ?1.那么在第一輪的可分性傳播模型中添加如下約束條件

基于自動化建模方法搜索積分區分器時, 需要對初始輸入狀態的活躍情況進行遍歷, 以期找到可分性傳播最優的情況.受到計算復雜度的制約, 這在實際中往往是不可行的.根據可分性的傳播特點, 初始輸入可分性漢明重量越大, 一般傳播得也越遠.為此, 許多攻擊者通常將初始可分性設置為一比特是常數,其余比特均活躍, 以此尋找最長的積分區分器.例如, 文獻[29] 提出了優化的積分區分器搜索算法: 先判斷一比特常數下積分區分器的存在性, 再降低活躍比特數, 找到最優的積分區分器.對于包含分支異或壓縮的密碼結構來說, 這種策略或許并不是最優的(4.1 節證實了這種猜測).策略一根據密碼算法的結構特點, 對初始輸入可分性進行限制, 即異或壓縮的輸入分支之間的可分性是相互制約的, 它們滿足關系a1i+a2i+···+ati= 0.并且, 這一約束條件保證了壓縮輸出的分支是不活躍的, 因為它對應的可分性bi= 0.換言之, 通過策略一刪除經過異或壓縮結構的部分可分跡, 使得被保留的可分跡滿足條件: 當異或壓縮輸出分支作為中間狀態的輸入時, 中間狀態可分性的漢明重量不會因為異或壓縮結構而降低.

3.2 策略二: 針對非比特置換線性變換的建模

分組密碼輪函數包含的非比特置換線性變換可以寫成一個二元線性變換矩陣.那么, 利用COPY/XOR 函數建模規則可以對任意維數的線性變換矩陣直接建立可分性傳播的約束模型.正如文獻[30] 指出, 由于非獨立活躍比特的影響, 這種建模方式得到的約束會產生冗余可分跡, 進而導致可分性傳播提前終止.文獻[30] 提出了一種減少冗余可分跡、提高模型精度的建模方法.該方法的核心思想是通過處理線性變換矩陣消除非獨立活躍比特.

文獻[30] 中的算法1 和算法2 描述了對矩陣建模的過程.其中, 算法1 對矩陣的行之間進行兩兩配對, 找到兩行之間非獨立可分性傳播比特(輸出結果記為result), 算法2 對矩陣M涉及的非獨立可分性傳播進行處理: 通過引入新的中間變量TN, 將矩陣拆分為獨立建模的COPY 矩陣和XOR 矩陣.經過觀察發現,TN在建模過程中作為一個整體參與COPY/XOR 運算, 因此沒必要再拆分開單獨建立約束, 只需要整體進行約束即可.為此, 我們給出文獻[30] 中關于TN的等價約束條件, 即策略二.

根據傳統COPY 函數和XOR 函數的建模規則, 策略二中非獨立可分性傳播部分建立的可分性約束條件為:

結合COPY 約束條件, 這與不等式(1)顯然是等價的.

設j1,j2∈result, 根據文獻[30] 中的算法2, 將這條非獨立可分性傳播轉化為獨立可分性傳播需要在MILP 模型中添加對應如下約束的不等式條件

這意味著, 若TN在bj1的可分性取1, 那么在bj2必定取0; 若TN在bj1的可分性取0, 那么在bj2必定取1.這與不等式(1)顯然也是等價的.

此外, 策略二的另一個優點是: 無需對矩陣M提前進行行配對, 以期找到最多的公共變量個數(文獻[30] 的算法1), 只需要對任意包含非獨立可分性傳播的兩行添加如不等式(1)的約束條件即可, 需要添加的不等式個數上界為m(m ?1)/2.算法1 描述了利用策略二對M建模的過程.其中, 3–6 行對矩陣M涉及的非獨立可分性傳播進行處理, 第5 行的a=(a1,a2,···,an) 代表可分性向量.

算法1.構建線性變換的BDP 傳播的新MILP 模型Input: 線性變換矩陣M Output: M 對應的BDP 傳播模型M 1 建立空的MILP 模型M;2 生成輸入/輸出/中間變量M.var ←ai,bi,ui;3 for i ?= j,(i,j) ∈(0,m)×(0,m),t ∈(0,n) do 4 l =(l0i ∧l0j,l1i ∧l1j,··· ,lni ∧lnj);5 M.con ←〈a,l〉 ≤1;6 end 7 for j ∈(0,n),i ∈(0,m) do 8 M.con ←aj = ∑n?1 k=0 uk ·M [i][j];9 end 10 for i ∈(0,m),j ∈(0,n) do 11 M.con ←bi = ∑n?1 k=0 uk ·M [i][j];12 end 13 return M.

4 應用于SM4 和FOX

4.1 應用于SM4

SM4 整體采用廣義Feistel 結構, 分組長度和密鑰長度均為128 比特, 加密輪數為32 輪.SM4 的一輪變換如圖3 所示, 第i輪輪函數F定義為F(Xi,Xi+1,Xi+2,Xi+3,RKi) =Xi ⊕T(Xi+1⊕Xi+2⊕Xi+3⊕RKi), 0≤i ≤31.其中, 合成置換T是一個32 維的可逆變換, 由非線性變換τ和線性變換L復合而成, 即T(.)=L(τ(.)).非線性變換τ由4 個并置的8 比特S 盒構成, 線性變換L表示如下:

其中,B ∈Z322是輸入,C ∈Z322是輸出.明文經過32 輪加密之后, 最后再經過一個反序變換R輸出密文.設Y0,Y1,Y2,Y3為輸出, 那么(Y0,Y1,Y2,Y3)=R(X32,X33,X34,X35)=(X35,X34,X33,X32).

不考慮最后一個反序變換, 利用MILP 方法建模, 搜索SM4 的積分區分器.首先, 根據第2 節S 盒的建模規則, 利用Logic Friday 軟件, 共得到191 個約束不等式描述可分性在SM4 的8 比特S 盒上的傳播.由于線性變換比較簡單, 可以根據二元運算的建模規則直接對其建立約束條件.然后, 設置初始輸入的一比特為常數, 其余比特全活躍.最后, 借助Gurobi 求解器對模型進行求解.遍歷輸入的常數位置, 得到如下結果: 輸入最低32 位任一位為常數, 其余位置全活躍, 12 輪傳播之后存在32 個平衡比特(最高32位), 而13 輪之后無平衡位置.采用3.1 節的策略一, 增加首輪關于分支異或壓縮結構的約束條件:

其中,a1i,a2i,a3i分別表示輸入分支X1,X2,X3第i比特的可分性.這可以構造13 輪的積分區分器: 選擇初始輸入最低32 位任一位為常數, 其余位置全活躍, 13 輪傳播之后存在32 個平衡比特.例如, 選取最后一比特為常數, 那么可以構建如下13 輪SM4 的積分區分器:

4.2 應用于FOX

FOX 支持兩種分組長度: 64 比特和128 比特, 密鑰k的長度滿足0≤k ≤256, 且是8 的倍數, 輪數r隨著密鑰長度的改變而不同.FOX64 和FOX128 的一輪變換如圖4–5 所示.下面介紹FOX64 的輪函數f32、FOX128 的輪函數f64、以及or 函數.

(1) 輪函數f32f32 是FOX64 的核心函數, 輸入輸出都為32 比特, 包含三個部分: 替換部分sigma4、擴散部分mu4 和輪密鑰加部分,如圖6 所示.設f32 的輸入輸出分別為X(32)和Y(32),64 比特的輪密鑰為RK(64)=RK0(32)||RK1(32), 那么Y(32)=sigma4(mu4(sigma4(X(32)⊕RK0(32)))⊕RK1(32))⊕RK0(32).非線性變換sigma4 由4 個并置的8 比特S 盒組成, 線性變換mu4 可以寫成GF(28)上的一個4×4 的變換矩陣.

圖6 f32Figure 6 f32

(2) 輪函數f64f64 是FOX128 的核心函數, 類似于f32, 輸入輸出都為64 比特, 也包含三個部分: 替換部分sigma8、擴散部分mu8 和輪密鑰加部分, 如圖7 所示.設f64 的輸入輸出分別為X(64)和Y(64),128 比特的輪密鑰為RK(128)= RK0(64)||RK1(64), 那么Y(64)= sigma8(mu8(sigma8(X(64)⊕RK0(64)))⊕RK1(64))⊕RK0(64).非線性變換sigma8 由8 個并置的8 比特S 盒組成(S 盒與f32 相同), 線性變換mu8 可以寫成GF(28) 上的一個8×8 的變換矩陣.

圖7 f64Figure 7 f64

(3) or 函數or 函數是一輪Feistel 變換, 輸入輸出均為32 比特.設輸入為X(32)=X0(16)||X1(16), 那么輸出Y(32)=Y0(16)||Y1(16)=X1(16)||(X0(16)⊕X1(16)).FOX64 和FOX128 的最后一輪都不包含or函數, 即, 最后一輪的or 變換相當于一個恒等變換.

根據第2 節S 盒的建模規則, 利用Logic Friday 軟件, 共得到614 個約束不等式描述可分性在FOX的8 比特S 盒上的傳播.針對FOX64, 采用3.1 節的策略一, 增加首輪關于分支異或壓縮的約束條件:

5 總結

本文針對分組密碼的分支異或壓縮結構和非比特置換的線性變換, 提出了兩種自動化建模策略: 策略一對初始輸入可分性進行約束, 從而保證經過首輪分支異或壓縮結構的輸出可分性為0, 使得可分性傳播更有優勢; 策略二通過對線性變換中的非獨立可分性傳播比特進行約束, 減少冗余可分跡, 提高模型的精度; 并且, 將兩種策略分別應用于分組密碼SM4 和FOX, 改進了二者關于積分區分器搜索的結果.因為這兩種策略都是基于分組密碼的結構提出的, 因此本文的建模策略不僅適用于基于MILP 技術搜索可分性, 也適用于基于SAT/SMT 等技術搜索可分性.