基于MILP 的輕量級(jí)密碼算法ACE 的差分分析

劉帥，關(guān)杰，胡斌，馬宿東

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

0 引言

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

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

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

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

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

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

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

1 背景知識(shí)

1.1 輕量級(jí)密碼算法ACE

ACE 是由Aagaard 等[24]提出的輕量級(jí)密碼算法，包括認(rèn)證加密算法ACE-AE-128 與哈希算法ACE-H-256。ACE 算法的設(shè)計(jì)采用基于ACE置換的雙工海綿結(jié)構(gòu)，ACE 置換是ACE 算法的主體部分，其規(guī)模為320 bit，第i步狀態(tài)表示為5 個(gè)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 個(gè)8 bit 的輪常數(shù)。

圖1 ACE-step

ACE置換的非線性環(huán)節(jié)SB-64是一個(gè)減輪的不帶密鑰的分組密碼Simeck[2]，其分組規(guī)模為64 bit，輪數(shù)為8，采用Feistel 結(jié)構(gòu)，輪函數(shù)如圖2 所示。

圖2 SB-64 輪函數(shù)

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

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

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

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

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

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

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

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

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

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

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

2 ACE 的MILP 差分模型

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

2.1 環(huán)形與門組合及其MILP 差分刻畫

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

圖5 環(huán)形與門組合的示意

其中，|表示邏輯或，對(duì)應(yīng)的目標(biāo)函數(shù)為

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

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

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

表1 單個(gè)與門的差分特性

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

最后，還需要考慮一種特殊情況，即輸入差為全1 的情況。定理1 給出了這種情況下不同輸出差對(duì)應(yīng)的差分轉(zhuǎn)移概率。

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

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

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

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

2.2 MILP 差分模型的快速求解

為了提高搜索差分/線性鏈的速度，Zhou 等[22]針對(duì)SPN 結(jié)構(gòu)與Feistel 結(jié)構(gòu)的分組密碼給出了MILP 模型的分而治之求解策略，其基本思想是縮減MILP 模型的可行域，這部分可行域由于活躍S盒的數(shù)量較多，不包含較好的差分/線性鏈。Zhou等[22]的方法并不適用于ACE 算法，由于ACE 算法的非線性環(huán)節(jié)（環(huán)形與門組合）規(guī)模較大，把環(huán)形與門組合當(dāng)作S 盒處理僅考慮其活躍性，會(huì)忽略很多細(xì)節(jié)。由于ACE 的狀態(tài)規(guī)模較大，且輪函數(shù)較為復(fù)雜，其MILP 差分模型很難求解，本節(jié)結(jié)合Gurobi 求解器及ACE 的特點(diǎn)，給出了提高M(jìn)ILP差分模型求解速度的方法。

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

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

2.2.1 MILP 差分模型下界的確定

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

2 種模型的區(qū)別僅在于模型 M1的目標(biāo)函數(shù)是使差分鏈的差分轉(zhuǎn)移概率重量達(dá)到最小，而模型M2的目標(biāo)函數(shù)是使差分鏈中活躍SB-64 的數(shù)量達(dá)到最小。由于目標(biāo)函數(shù)更加簡(jiǎn)單，后者的求解變得非常容易。對(duì)于一個(gè)活躍的SB-64，其差分轉(zhuǎn)移概率的重量最小值為18[31]，由此容易得到定理2。

定理 2對(duì)于R步 ACE-step，假設(shè)其活躍SB-64 的最小數(shù)量為v，則其差分轉(zhuǎn)移概率的重量下界為18v。

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

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

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

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

ACE 中唯一的非線性操作是環(huán)形與門組合，根據(jù)2.1 節(jié)的分析直觀地得出一個(gè)結(jié)論：環(huán)形與門組合的輸入差分重量越小，差分轉(zhuǎn)移概率越大。定理3具體分析了環(huán)形與門組合的差分轉(zhuǎn)移概率與輸入差分重量之間的關(guān)系。

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

證畢。

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

根據(jù)前面的分析，Gurobi 求解器會(huì)實(shí)時(shí)返回當(dāng)前最優(yōu)解CB，且利用2.2.1 節(jié)中的方法可以確定最優(yōu)解的下界LB，令SUM 表示MILP 模型中所有24R個(gè)環(huán)形與門組合的輸入差分變量的和，設(shè)定當(dāng)Gurobi 求解器長時(shí)間沒有返回更優(yōu)的解時(shí)，根據(jù)當(dāng)前的最優(yōu)解CB 以及最優(yōu)解的下界LB 加入以下限制條件。

根據(jù)推論1，條件1 刪除了MILP 模型的部分解，這部分解對(duì)應(yīng)的目標(biāo)函數(shù)不小于CB，所以必然不包括更優(yōu)的解；條件2 刪除了MILP 模型中變量的部分取值，這部分取值必然不構(gòu)成一個(gè)有效解，假設(shè)其構(gòu)成一個(gè)有效解，那么該解對(duì)應(yīng)的目標(biāo)函數(shù)小于LB，產(chǎn)生了矛盾。條件1 縮減了MILP模型的可行域，條件2 縮減了MILP 模型中變量的取值范圍，這些限制條件使MILP 模型的求解速度大幅提升。

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

3 ACE 的差分分析

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

3.1 文獻(xiàn)[24]的差分分析結(jié)果

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

3.2 本文的差分分析結(jié)果

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

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

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

本文搜索了ACE 置換的步數(shù)為1～6 時(shí)的差分鏈，表4 給出了最優(yōu)搜索結(jié)果，當(dāng)步數(shù)為1、2 時(shí)，沒有滿足條件的差分鏈。

表4 ACE 置換差分鏈最優(yōu)搜索結(jié)果

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

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

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

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

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

4 結(jié)束語

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

本文的工作為利用自動(dòng)化分析工具研究基于與門設(shè)計(jì)的密碼算法的差分性質(zhì)提供了理論參考與技術(shù)基礎(chǔ)，下一步考慮將環(huán)形與門組合的MILP差分刻畫進(jìn)行擴(kuò)展并應(yīng)用到更多相關(guān)算法的差分分析中，嘗試給出改進(jìn)的差分分析結(jié)果。