基于MILP 的輕量級密碼算法ACE 的差分分析

劉帥，關杰，胡斌，馬宿東

（信息工程大學密碼工程學院，河南 鄭州 450001）

0 引言

隨著物聯網的發展，如何利用有限的資源保證數據的安全成為當前的重要研究課題，輕量級密碼算法（LWCA,lightweight cipher algorithm）[1]應運而生。近年來，涌現出了大量輕量級密碼算法[2-5]，其設計與分析得到了研究者的廣泛關注[6-8]。2016年，美國國家標準與技術研究院發起了輕量級密碼算法征集活動[9]，要求提交的算法兼具認證與加密功能，這一類算法也被稱為認證加密算法[10]。

認證加密算法輸入密鑰K、NonceN、相關數據A、明文M，輸出密文C、認證碼T，即(C,T) =E (K,N,A,M)；相應地，解密階段輸入密鑰K、NonceN、相關數據A、密文C、認證碼T，隨后生成認證碼T′，如果T=T′則認證通過，輸出明 文M，否則認證失敗輸出⊥，即D(K,N,A,C,T) ∈{M,⊥}。

隨著多種多樣的輕量級密碼算法被提出，其安全性分析也經歷著不斷的革新，過去的安全分析往往依賴手工推導，1994 年，Matsui[11]提出了一種強有力的自動化分析工具，利用分支定界搜索算法來搜索最優差分/線性鏈，從此自動化分析在諸多場景下取代了手工推導[12-15]。2014 年，Sun 等[16]給出了密碼算法的混合整數線性規劃（MILP,mixed-integer linear programming）差分/線性刻畫方法，建立并求解了MILP 模型來搜索最優差分/線性鏈，拉開了利用MILP 自動化搜索技術分析密碼算法的序幕[17-21]。MILP 自動化搜索的關鍵在于MILP 模型的刻畫與快速求解，為了提高求解速度，研究者需要根據密碼算法的特點，給出快速求解MILP 模型的方法，如Zhou 等[22]針對代換-置換網絡（SPN）結構的分組密碼算法提出了分而治之策略；劉帥等[23]針對MORUS 算法的結構特點根據 ΔI V的重量將MILP模型劃分為多個子模型，根據MORUS 算法差分狀態的循環等價性省略部分子模型的求解。

LWCA 第二輪的候選算法ACE 由Aagaard 等[24]提出，是基于ACE 置換設計的雙工海綿結構輕量級密碼算法，包括認證加密算法ACE-AE-128 和哈希算法ACE-H-256。研究者在設計報告中做出了較粗略的差分分析，利用最小活動SB-64 的數量給出了ACE 置換抗差分分析的安全邊界。

2020 年，Liu 等[25]提出了ACE 置換不可能差分的自動化搜索算法，證明了ACE 置換不存在9 步以上的不可能差分，并給出了8 步不可能差分。2021 年，葉濤等[26]針對ACE 算法給出了12 步ACE 置換的積分區分器，相比于研究者給出的區分器提高了4 步，取得了較大的改進。2022 年，Chang 等[27]給出了ACE 算法的偽造攻擊。對于差分分析，仍沒有第三方給出較精確的分析結果。

差分分析是研究密碼算法安全性強有力的分析方法，近幾年，針對輕量級密碼算法的差分分析得到了廣泛的研究。2022 年，蔣梓龍等[28]針對Saturnin 算法給出了5.5 輪不可能差分攻擊。同年，Dunkelman 等[29]給出了相關密鑰下全輪TinyJUMBU-192/256 的差分偽造攻擊。

本文基于自動化分析工具MILP對ACE算法的差分性質進行研究。利用MILP 搜索差分鏈，首先給出算法中非線性操作差分性質的MILP 刻畫，給出的刻畫越精確，就能更大程度地確保搜索得到的差分鏈的概率最大。ACE 算法中的唯一非線性操作為與門，對于ACE 置換，SB-64 輪函數中的32 個與門的輸入之間存在緊密的關系，如何充分考慮與門之間的相互關系是要解決的首要問題，本文將這32 個與門轉化為環形與門組合，給出了環形與門組合差分性質精確的MILP 刻畫。為了提高MILP 差分模型的求解速度，本文采用了如下方法：1) 利用最小活躍SB-64 的數量給出目標函數的下界；2) 利用環形與門組合輸入差分重量與差分轉移概率之間的關系，增加約束條件，縮減MILP 模型的可行域與變量的取值范圍。最后給出了ACE 置換的高概率差分鏈，為了提高差分鏈的概率，搜索了具有相同輸入、輸出差分的差分鏈。利用搜索到的差分鏈，給出了對ACE 算法的攻擊方法：ACE 置換為3 步的簡化版ACE-AE-128 的差分偽造攻擊，以及簡化版ACE-H-256 的差分碰撞攻擊。

1 背景知識

1.1 輕量級密碼算法ACE

ACE 是由Aagaard 等[24]提出的輕量級密碼算法，包括認證加密算法ACE-AE-128 與哈希算法ACE-H-256。ACE 算法的設計采用基于ACE置換的雙工海綿結構，ACE 置換是ACE 算法的主體部分，其規模為320 bit，第i步狀態表示為5 個64 bit(Ai,B i,C i,D i,E i)(i= 0,1,2,…,16)，ACE置換由ACE-step 迭代16 次，圖1 展示了ACE-step。其中，第i步ACE-step中使用了6 個8 bit 的輪常數。

圖1 ACE-step

ACE置換的非線性環節SB-64是一個減輪的不帶密鑰的分組密碼Simeck[2]，其分組規模為64 bit，輪數為8，采用Feistel 結構，輪函數如圖2 所示。

圖2 SB-64 輪函數

對于認證加密算法ACE-AE-128 與哈希算法ACE-H-256，其狀態大小均為320 bit，狀態S中有r=64 bit 進行數據的輸入與輸出，稱為比率部分，記為Sr。比率部分由320 bit 狀態S=A||B||C||D||E中的8 個字節組成，分別為A[ 7]、A[ 6]、A[ 5]、A[ 4]、C[ 7]、C[6]、C[ 5]、C[ 4]，其中，A[j]、C[j]分別表示A、C的第j個字節。對于算法ACE-AE-128 與ACE-H-256 的具體結構，這里不再贅述，可參照其設計報告[24]。

1.2 差分偽造攻擊與差分碰撞攻擊

對于認證加密算法，偽造攻擊的基本思想是如果攻擊者能夠構造出未經詢問的合法消息密文對則偽造成功，按照構造認證碼的方式不同，將其分為差分偽造攻擊和直接偽造攻擊。差分偽造攻擊是指攻擊者在已掌握消息密文對的情況下，利用差分分析方法，構造出另一對消息密文對且能夠通過驗證。

哈希算法要求對于不同的消息，必定得到不同的哈希值。差分碰撞攻擊的思想是利用高概率差分對應找到一對不同的消息，其對應的哈希值相同，這樣哈希算法便是不安全的。

令SΔ表示320 bit 狀態差分，其比率部分差分為Δ ≠ 0，其余比特差分為0，尋找ACE 置換一條高概率的差分鏈，其差分轉移概率為P，根據該差分鏈，可以構造認證加密算法ACE-AE-128 的差分偽造攻擊以及哈希算法ACE-H-256 的差分碰撞攻擊。

1) 認證加密算法ACE-AE-128 的差分偽造攻擊

已知 Nonce、相關數據、明文組(N,A0⊕Δ1||A1⊕Δ2,M)，詢問ACE-AE-128 加密機得到認證碼T，則認證碼T對 (N,A0||A1,M)以概率P有效。同樣地，也可以在明文處理階段加入差分構造攻擊。圖3 給出了ACE-AE-128 的差分偽造攻擊示意。

圖3 ACE-AE-128 的差分偽造攻擊示意

2) 哈希算法ACE-H-256 的差分碰撞攻擊

已知初始變量、明文對 (IV,M0⊕Δ1||M1⊕Δ2)，詢問ACE-H-256 加密機得到哈希值H，則初始變量、明文對 (IV,M0||M1)的哈希值與H以概率P產生碰撞。圖4 給出了ACE-H-256 的差分碰撞攻擊示意。

圖4 ACE-H-256 的差分碰撞攻擊示意

2 ACE 的MILP 差分模型

本節給出了ACE 的MILP 差分模型，主要研究了其非線性環節差分特性的MILP 刻畫。由于ACE的狀態較大，每一步迭代多輪Simeck 輪函數，MILP模型很難求解，本文利用ACE 算法中非線性環節差分轉移概率與輸入差分重量之間的關系給出了MILP 差分模型的快速求解方法。

2.1 環形與門組合及其MILP 差分刻畫

從圖5 可以看出，ACE 中的非線性操作實際是一個32 維環形與門組合，上述轉換本質上是將SB-64同一輪的32 個與門利用線性變換進行移位，更直觀地展示了32 個與門之間的相互關系，使2 個相鄰的與門具有一個共同的輸入，便于利用數學化的推導進行下一步分析。此外，將ACE 中的非線性操作歸納為n維環形與門組合，對環形與門組合進行研究，使研究結果可以應用于更多的場景，比如SIMON 算法輪函數中的與門同樣可以轉化為多維環形與門組合，其維數取決于分組的規模。本節將給出n維環形與門組合的MILP 差分刻畫，值得一提的是，Saha 等[21]在分析認證加密算法TinyJUMBU 時，給出了函數f(x0,x1,…,xn-1)=(x0x1,x1x2,…,x n-2xn-1)的MILP 差分刻畫，稱其為鏈形與門組合。與鏈形與門組合不同的是，n維環形與門組合在鏈形與門組合的基礎上增加了一個與門，即最后一個輸入xn-1與第一個輸入x0經過一個與門輸出yn-1，這使n個與門之間的相互關系更加復雜，下面給出具體的分析及刻畫。

圖5 環形與門組合的示意

其中，|表示邏輯或，對應的目標函數為

式(1)并沒有考慮n個與門之間的相關性，實際上，不同與門的輸入之間是相互關聯的，所以這種簡單的刻畫顯然不準確，為了給出精確的刻畫，需要分析環形與門組合中n個與門之間的相關性。參考文獻[21]，觀察 2 個相鄰與門xi xi+1,xi+1xi+2的情況，上述刻畫認為這2 個與門相互獨立，其差分特性滿足

但實際上，式(2)并不一直成立。表2 給出了輸入差取遍所有值時式(2)的成立情況。

由表2 可知，只有當相鄰2 個與門的輸入差為(1,0,1)時，2 個與門的差分傳遞概率之間存在相關性，這容易從單個與門的差分特性進行解釋，當輸入差為(1,0,1)，根據表1，輸出差為 Δxi xi+1=Δxi+1xi+2=xi+1，據此，在g(x0,x1,…,xn-1)的MILP 差分刻畫中增加如下限制條件，其中，i=0,1,2,…,n-1。

表1 單個與門的差分特性

表2 輸入差取遍所有值時式(2)的成立情況

最后，還需要考慮一種特殊情況，即輸入差為全1 的情況。定理1 給出了這種情況下不同輸出差對應的差分轉移概率。

對于n維環形與門組合g(x0,x1,…,xn-1)，當輸入差為全1 時，輸出差中1 的個數與n具有相同的奇偶性，為此加入如下限制條件

其中，dummy 是一個輔助變量。當且僅當所有i∈ { 0,1,…,n- 1}，滿足idi=1時，λ=1（即輸入差為全1），此時，第二個等式使輸出差中1 的個數與n具有相同的奇偶性；其他情況下，第二個等式不起任何作用。在輸入差為全1 的情況下，最后一個與門與前n-1個與門具有相關性，因此目標函數應該減去λ。λ= id0id1…i dn-1與線性表達式等價。

綜上，式(1)、式(3)和式(4)給出了n維環形與門組合g(x0,x1,…,xn-1)完全精確的MILP 差分刻畫，目標函數為。

式(1)、式(3)和式(4)共包含5n+2個線性表達式、一個二次表達式以及n個邏輯或表達式。如果單純把n維環形與門組合g當作一個大規模的S 盒處理，由于規模過大，利用之前關于S盒的MILP刻畫技術[30]很難對函數g進行有效刻畫，本文僅利用O(n) 個表達式精確刻畫了n維環形與門組合g的差分特性，并驗證了以上刻畫是完全精確的。

2.2 MILP 差分模型的快速求解

為了提高搜索差分/線性鏈的速度，Zhou 等[22]針對SPN 結構與Feistel 結構的分組密碼給出了MILP 模型的分而治之求解策略，其基本思想是縮減MILP 模型的可行域，這部分可行域由于活躍S盒的數量較多，不包含較好的差分/線性鏈。Zhou等[22]的方法并不適用于ACE 算法，由于ACE 算法的非線性環節（環形與門組合）規模較大，把環形與門組合當作S 盒處理僅考慮其活躍性，會忽略很多細節。由于ACE 的狀態規模較大，且輪函數較為復雜，其MILP 差分模型很難求解，本節結合Gurobi 求解器及ACE 的特點，給出了提高MILP差分模型求解速度的方法。

對于一條差分鏈，假設其差分轉移概率為P≠ 0，稱 -lbP為差分轉移概率的重量。求解差分鏈的最大差分轉移概率即求解差分轉移概率重量的最小值，這與2.1 節中給出的目標函數一致。按照2.1 節的刻畫方法給出R步ACE-step 的MILP差分模型，記該模型為 M1，并利用Gurobi 求解器求解該MILP 差分模型，Gurobi 求解器實時返回當前的最優解CB 以及最優解的下界LB，當CB=LB 時，Gurobi 確定CB 為該模型最優解B并返回該解，據此可以將Gurobi 求解過程分為2 個主要部分：1) 求解當前最優解CB，直到得到全局最優解B；2) 計算更緊致的下界LB，直到LB=B。

根據經驗，在Gurobi 的求解過程中，往往能夠較快地給出全局最優解B，而絕大部分時間都被用來收緊下界LB，使LB 的數值逐漸增加，逼近數值B。根據Gurobi求解過程的特點，給出2種方式來提高MILP差分模型 M1的求解速度：1) 建立一個粗略的MILP差分模型 M2，給出模型 M1目標函數的緊致下界，以提高求解過程第二部分的速度；2) 通過分析環形與門組合的差分轉移概率與輸入差之間的關系，加入一些限制條件縮減MILP 差分模型 M1的可行域或者縮小變量的取值范圍，從而提高求解過程第一部分的速度。

2.2.1 MILP 差分模型下界的確定

本節建立了一個MILP差分模型 M2，對于R步ACE-step，ACi,j∈{ 0,1}表示第i(i=0,1,…,R-1)步ACE-step 中第j(j= 0,1,2)個SB-64 的活躍性，當且僅當該SB-64 的輸入差不為0 時，ACi,j=1，否則ACi,j=0，目標函數為。

2 種模型的區別僅在于模型 M1的目標函數是使差分鏈的差分轉移概率重量達到最小，而模型M2的目標函數是使差分鏈中活躍SB-64 的數量達到最小。由于目標函數更加簡單，后者的求解變得非常容易。對于一個活躍的SB-64，其差分轉移概率的重量最小值為18[31]，由此容易得到定理2。

定理 2對于R步 ACE-step，假設其活躍SB-64 的最小數量為v，則其差分轉移概率的重量下界為18v。

證明對于R步ACE-step 的任意一條概率為P= 2-p≠ 0的差分鏈，其活躍SB-64 的數量為w，設第i(i= 0,1,…,w- 1)個活躍SB-64 的差分轉移概率重量為pi，則，所以差分轉移概率的重量下界為18v。證畢。

定理2 給出了一種確定MILP 差分模型 M1目標函數下界的方法，由于Gurobi 求解過程第二步花費的時間遠大于第一步，這種方法大大提升了模型M1的求解速度。表3 給出了不同步數ACE 置換活躍SB-64 的最小數量及其搜索時間。

表3 不同步數ACE置換活躍SB-64的最小數量及其搜索時間

2.2.2 增加MILP 差分模型的限制條件

ACE 中唯一的非線性操作是環形與門組合，根據2.1 節的分析直觀地得出一個結論：環形與門組合的輸入差分重量越小，差分轉移概率越大。定理3具體分析了環形與門組合的差分轉移概率與輸入差分重量之間的關系。

定理3假設n維環形與門組合的輸入差分為id= (id0,id1,…,idn-1)，id 的重量為，對于任意輸出差分，滿足差分轉移概率P≠ 0，則概率P具有P= 2-p的形式，其中p為非負整數，且有

證畢。

本文的MILP 差分模型刻畫了R步ACE-step（R是一個正整數），每一步ACE-step 包含24 個環形與門組合，則R步共包含24R個環形與門組合，假設這些環形與門組合之間是相互獨立的，對于R步ACE-step 的一條差分鏈，根據定理3 容易得到差分鏈的差分轉移概率與環形與門組合的輸入差分重量之間的關系，即推論1。

根據前面的分析，Gurobi 求解器會實時返回當前最優解CB，且利用2.2.1 節中的方法可以確定最優解的下界LB，令SUM 表示MILP 模型中所有24R個環形與門組合的輸入差分變量的和，設定當Gurobi 求解器長時間沒有返回更優的解時，根據當前的最優解CB 以及最優解的下界LB 加入以下限制條件。

根據推論1，條件1 刪除了MILP 模型的部分解，這部分解對應的目標函數不小于CB，所以必然不包括更優的解；條件2 刪除了MILP 模型中變量的部分取值，這部分取值必然不構成一個有效解，假設其構成一個有效解，那么該解對應的目標函數小于LB，產生了矛盾。條件1 縮減了MILP模型的可行域，條件2 縮減了MILP 模型中變量的取值范圍，這些限制條件使MILP 模型的求解速度大幅提升。

通過以上加速方法，經過實驗驗證，3 步ACE 置換MILP 差分模型求解時間由3 700 s 降低到1 900 s，4 步ACE 置換MILP 差分模型求解時間由24 200 s降低到10 600 s，而對于5 步ACE 置換，加速前的模型無法在有限時間內完成求解過程，而加速后的模型求解大約花費了2 天時間。

3 ACE 的差分分析

ACE 算法中的ACE 置換包含16 步ACE-step，本文主要分析了R步ACE-step 的ACE 置換的差分特征，在本文的分析中，限制ACE 置換輸入差與輸出差中64 bit 比率部分非0，其余比特為0。本節首先給出了文獻[24]的差分分析結果，然后給出了本文的分析結果。

3.1 文獻[24]的差分分析結果

文獻[24]中給出了ACE的差分分析結果，目前，對于ACE 算法，尚沒有進一步的差分分析結果，文獻[24]利用MILP 自動搜索技術，求解出16 步ACE-step 中活躍SB-64 數量的最小值為21，其中SB-64 的差分轉移概率上界為 2-15.8，由此得到了16步 ACE-step 的最大差分轉移概率的上界2-15.8×21= 2-331.8＜ 2-320，這樣16 步ACE-step 保證了ACE 置換達到差分安全邊界 2-320，使ACE 狀態與隨機320 bit 狀態不可區分。

3.2 本文的差分分析結果

本文對ACE 置換建立MILP 差分模型，從而搜索其高概率差分鏈，ACE 置換中的線性操作包括異或、移位，其中，移位操作只需要改變差分值的位置，不需要進行額外的刻畫。

對于比特異或a⊕b=c，可以用等式Δa+Δb+Δc= 2dummy 刻畫其差分性質，這里需要引入一個整數變量dummy。

2.1 節將ACE 置換中的非線性操作轉化為32 維環形與門組合，并給出了其差分性質精確的MILP刻畫，綜上，可對ACE 置換的差分性質利用MILP進行全面的刻畫，并通過Gurobi 求解器進行求解。

本文搜索了ACE 置換的步數為1～6 時的差分鏈，表4 給出了最優搜索結果，當步數為1、2 時，沒有滿足條件的差分鏈。

表4 ACE 置換差分鏈最優搜索結果

對于表4 給出的差分鏈，搜索具有相同輸入差、輸出差的多條差分鏈，從而得到更大、更精確的差分傳遞概率。例如，當步數為3 時，找到一條概率為 2-98的差分鏈，表5 給出了這條差分鏈，固定其輸入差 ΔS0以及輸出差 ΔS3，搜索得到多條大概率的 差 分 鏈，計 算其概率之和為 2-98× 6+2-99× 13+2-100× 183+2-101× 627+2-102× 671 ≈ 2-90.52。

表5 3 步ACE 置換概率為 2-98的差分鏈

對表4 中3～6 步的差分鏈均做此處理，表6 給出了多條差分鏈的概率之和。

表6 多條差分鏈的概率之和

根據以上搜索結果，本文給出了減輪認證加密算法ACE-AE-128 的差分偽造攻擊和減輪哈希函數ACE-H-256 的差分碰撞攻擊，當ACE 置換的步數為3 時，差分偽造攻擊的成功概率為 2-90.52，差分碰撞攻擊的成功概率為 2-90.52。文獻[24]指出，ACE-AE-128 的認證安全目標為 128 bit，ACE-H-256 的碰撞安全目標為128 bit。從表6 可以看出，4 步 ACE 置換可以保證認證加密算法ACE-AE-128 抗差分偽造攻擊，哈希算法ACE-H-256 抗差分碰撞攻擊。

4 結束語

輕量級密碼算法ACE 是LWCA 征集活動中第二輪的候選算法，文獻[24]給出了較粗略的差分分析結果，為了給出進一步的結果，本文利用自動化分析工具MILP 對ACE 算法的差分性質進行研究，首先給出了ACE 算法非線性操作差分性質精確的MILP 刻畫，實際上，該部分工作可以直接應用到SIMON、Simeck 等密碼算法的分析中；然后給出了ACE 置換的高概率差分鏈，并利用多差分技術提高差分鏈的概率，分別給出了ACE-AE-128 的差分偽造攻擊與哈希函數ACE-H-256 的差分碰撞攻擊。

本文的工作為利用自動化分析工具研究基于與門設計的密碼算法的差分性質提供了理論參考與技術基礎，下一步考慮將環形與門組合的MILP差分刻畫進行擴展并應用到更多相關算法的差分分析中，嘗試給出改進的差分分析結果。