ANU，ANU-II和LiCi算法的積分區分器搜索

王紅艷，韋永壯，劉文芬

1(桂林電子科技大學 廣西密碼學與信息安全重點實驗室，廣西 桂林 541004) 2(桂林電子科技大學 廣西高校云計算與復雜系統重點實驗室，廣西 桂林 541004) 3(桂林電子科技大學 廣西無線寬帶通信與信號處理重點實驗室，廣西 桂林 541004)

1 引 言

隨著物聯網IOT(Internet of Things)技術的飛速發展，嵌入式系統、無線通信和智能卡等已普及到人們生活的方方面面.由于輕量級分組密碼算法具有低功耗、結構輕便和占用面積小等特點，所以較適用于資源受限的環境中.ANU[1]，ANU-II[2]和LiCi算法[3]是新提出的基于比特來設計的三個超輕量級密碼算法.它們的設計理念都是通過盡可能低的輪數來獲取最大數目的活躍S盒個數.并且ANU-II是Dahiphale等人在ANU基礎上改進的輕量級密碼算法，該算法舍去ANU算法的P置換后，相應在算法結構上進行新的變換，使得算法在實現效率和安全性方面都有進一步提升.目前，對于三個算法的最新攻擊進展如下：2016年印度學者Bansod等人針對ANU算法分別給出8輪的零相關線性區分器和4輪的不可能差分區分器[1]；2017年Patil等人給出LiCi算法6輪的零相關線性區分器[3]；2019年Xin等人給出LiCi算法的12輪積分區分器，活躍比特為263個選擇明文1,[11]；2019年Wei等人利用S盒的特殊性質，給出LiCi算法10輪的不可能差分區分器[10].

近年來，自動搜索技術對密碼算法的安全性分析起到很大的推進作用.與傳統手動運算相比，其具有操作簡易、精確性高和效率高等優點.積分攻擊[4]是2002年Knudsen等人在Square攻擊基礎上提出一種選擇明文的密碼分析方法.通常使用積分性質的傳播特性和評估代數次數兩種方法來構造區分器.在EUROCRYPT2015上Todo等人提出了可分性質[5]，它是在積分攻擊基礎上進行推廣的一種新分析方法.利用可分性質，介于“BALANCE”和“ALL”之間的隱含關系可以更明確的表達出來.相比傳統積分攻擊，可分性對密碼算法要求局限性更小，更適用于非雙射、低代數次數、比特級等分組密碼算法中.2015年Todo等人利用可分性質以及S盒的特殊性質成功分析了全輪的MISTY1算法[6]；2016年Xiang等人利用基于比特可分性和MILP相結合的思想，實現了對6個密碼算法的區分器搜索[7]；2019年Hu等人利用三子集可分性質提出一個自動搜索模型-STP，該模型具有不限制算法分組大小的優點[8]；2019年Hao Y和Todo等人提出超級多項式的代數性質應用到基于比特可分性的立方攻擊中[9].由于傳統比特級可分性限制了對分組較長算法的應用，Xiang等人提出利用線性不等式來刻畫比特可分性的傳播特性，并構建相關MILP模型.注意到，對于ANU，ANU-II和LiCi算法是否能抵御比特可分性質的積分分析這一問題仍有待解決.

此外，在密碼算法攻擊中，區分器輪數的高低更能準確的衡量密碼算法的安全性.本文首次對ANU和ANU-II算法進行比特積分分析，構建其新的可分性MILP模型，給出了針對ANU和ANU-II算法9輪和8輪的積分區分器自動搜索方法.并利用LiCi算法變形的等價結構，構建新的MILP模型，給出了12輪積分區分器.對于以上三個算法，這是目前最優的區分器攻擊結果.

2 算法介紹

2.1 符號說明

P，C：64比特明文和密文

K：80比特主密鑰

RKi：第i輪的32比特輪密鑰

Li，Ri：第i輪左分支(右分支)32比特輸入

⊕：按位異或操作(XOR)

<<<α：左循環左移α比特

>>>β：右循環右移β比特

‖：二進制連接符

2.2 ANU和ANU-II算法簡介

2.2.1 ANU算法

ANU算法[1]是2016年印度學者Bansod等人提出的一種基于Feistel結構的超輕量級分組密碼算法.該算法采用基于比特的置換形式，分組長度為64比特，密鑰長度支持80和128比特兩個版本，迭代輪數為25輪.ANU算法結構如圖1所示.

圖2 ANU算法的P置換

ANU算法的輪函數F由密鑰加、異或運算、字節替換和循環移位等四種基本運算構成.設PT為輸入，CT為輸出，則ANU算法加密流程如下：

PT=Li‖Ri，0≤i<25

Ri+1=P(Li)，Li+1=S(Li<<<3)⊕Ri，

Li+1=P[(S(Li>>>8)⊕Li+1)⊕RKi].

CT=Li+1‖Ri+1

2.2.2 ANU-II算法

ANU-II算法[2]是Dahiphale等人在BID2017上提出的一種輕量級分組密碼算法.該算法是在ANU基礎上進行優化，并舍去P置換線性操作.其分組長度為64比特，密鑰長度為128比特，共迭代25輪.ANU-II算法結構如圖3所示.

圖3 ANU-II算法結構

關于ANU-II的加密流程：

PT=Li‖Ri，0≤i<25

Ri+1=[S(Li)]⊕(Ri>>>3)⊕RKi1，

Li+1=[(Ri+1)<<<10]⊕Ri⊕RKi2.

CT=Li+1‖Ri+1

由于對ANU和ANU-II算法的比特積分攻擊不需要考慮密鑰編排算法，所以這里不再作詳細介紹，具體可參見文獻[1,2].

2.3 LiCi算法簡介

LiCi算法[3]是Patil等人在ICET2017上提出的一種超輕量級分組密碼算法.該算法分組長度為64比特，密鑰長度為128比特，共迭代31輪.LiCi算法的結構(等價結構)如圖4、圖5)所示.

如圖5是LiCi算法的等價結構，可看作該算法的一輪加密運算由兩個簡單的Feistel結構相接而成.關于LiCi算法的加密流程如下：

PT=Li‖Ri，0≤i<31

Li+1=(S(Li)⊕RKi1⊕Ri)<<<3，

Ri+1=(S(Li)⊕RKi2⊕Li+1)>>>7.

CT=Li+1‖Ri+1

圖4 LiCi算法結構

Fig.4 Structure of LiCi

圖5 LiCi算法的等價結構

Fig.5 Equivalent structure of LiCi

由于對LiCi算法的比特積分攻擊同樣不考慮密鑰編排，具體可參見文獻[3].

3 可分性分析

3.1 可分性和可分性路徑

其中(k0，k1，…，kr)∈K0×K1×…Kr，對于所有i∈{1，2，…，r}都有ki-1傳播到ki，那么記r輪可分性路徑為(k0，k1，…，kr).最后集合Kr之間的關系用來判斷是否存在有效積分區分器.

3.2 可分性的傳播規則

2015年Todo等人給出了傳統可分性質的傳播規則[5].但基于比特可分性質，這里只用到Copy和XOR兩種基本操作，具體的傳播規則這里不再多加贅述，詳細可參考文獻[5,6,12].下面用線性不等式組對COPY、XOR和AND操作的可分性傳播進行模型化，如下所示：

3.3 混合整數線性規劃(MILP)

MILP問題是一種優化求解問題，即在約束條件下取目標函數的最優解(即最大最小值問題).構建一個MILP模型M，需要包括變量a，b，c，限制條件M.con和目標函數M.obj，并且其中的變量僅限于整數.下面舉例1來說明：

然而，MILP求解器僅用來評估該模型是否具有可行性，也就是說如果沒有目標函數和可行解決方案，則此模型不可行.所以本實驗根據搜索算法的具體特征，使用Gurobi優化器來求解該模型.

3.4 SAGE中的不等式生成函數

通過Sage軟件中的Inequality_generator()函數，把經過S盒的可分性路徑用一系列不等式來表示，核心代碼如下：

Points=[[0，0，0，0]，[0，0，1，0]，…]

Triangle=Polyhedron(vertices = Points)

for l in triangle.inequality_generator()：

print l

4 可分性MILP模型的構建

ANU，ANU-II和LiCi算法總體都采用廣義Feistel結構.我們利用文獻[7]的思想，針對以上三個算法結構的本身特性，給出了構建基于比特可分性的新MILP模型來搜索積分區分器的自動化搜索方法，可分為以下3個步驟：

1)給出初始比特可分性，即給定具體的活躍bit和常量值.然后將密碼算法輪函數分解為Copy、AND和XOR等基本運算.

2)利用1中基本運算的可分性質，根據三個算法本身的結構特性來構建經過輪函數的可分性路徑的MILP模型，包括非線性層和置換層.

3)選擇合適的目標函數，即搜索終止條件.重復r次可得到r輪輪函數的可分性MILP模型M.

由于密碼算法中密鑰加、輪常數異或等運算不影響可分性質，所以這里不作考慮.

圖6 ANU的MILP模型變量之間的關系

下面以ANU算法為例，針對密碼算法的輪函數分解為XOR和COPY等基本運算，構建其MILP模型.同理ANU-II和LiCi算法與之思想類似，就不再詳細介紹.如圖6所示.

算法1.對ANU算法XOR函數的MILP模型

forn= 0；n<25 ;n++ do

end for

算法2.對ANU算法COPY函數的MILP模型

forn=0；n<25；n++ do

end for

4.1 ANU算法的MILP模型

4.1.1 模型化S盒

ANU算法由兩個相同4*4的S盒構成，計算可得到經過S盒的輸入輸出可分性的48條可分性路徑{D，C}，具體如表1所示.

表1 ANU算法S盒的可分性路徑

4.1.2 模型化置換層

對于一些置換層較為復雜的算法，可通過引入一些中間變量來描述置換層分解為COPY和XOR后的操作，從而來構建相關MILP模型.ANU算法的置換層由基于比特的P置換構成，運用簡單拉線變換，即得到一條經過置換層的輸入輸出可分性的可分性路徑.

4.2 ANU-II算法的MILP模型

ANU-II算法不含有置換層，所以僅對S盒來構建相關比特可分性的新MILP模型.經過計算可得到經過S盒的輸入輸出可分性的48條可分性路徑{D，C}，具體如表2所示.

表2 ANU-II算法S盒的可分性路徑

其次，通過Sage軟件中的不等式生成函數(參考3.4節)，利用貪婪算法對生成198個線性不等式進行約減到11個，則約減不等式{Ine}如下.

4.3 LiCi算法的MILP模型

由于LiCi算法不含有置換層，所以僅對其4×4的S盒，來構建比特可分性的新MILP模型.計算可得到經過S盒輸入輸出可分性的48條可分路徑{D，C}，具體如表3所示.

表3 LiCi算法S盒的可分性路徑

其次，通過Sage軟件中的不等式生成函數(參考3.4節)，利用貪婪算法的思想對生成187個線性不等式進行約減到15個，則約減不等式{Ine}表示如下：

4.4 目標函數

由定義2可知，搜索是否存在r輪的積分區分器，只需檢測是否存在零和性質.即判斷Kr是否包含所有的單位向量e，步驟如下所示：

5 實驗分析結果

本文采用的實驗研究平臺：采用Intel(R)Core(TM)i5-3230M CPU @ 2.60Hz，RAM-4GB，x64 Windows 10.首先根據第3節可分性性質相關定義，其次結合ANU，ANU-II和LiCi三個密碼算法的本身結構特性，構建新的MILP模型(算法1、算法2).最后選擇合適的目標函數、終止條件和限制條件，利用Gurobi優化器來求解該模型，搜索是否存在可用的積分區分器.設Ci為i個常量比特，Ai為i個活躍比特，Bi為i個平衡比特和Ui為i個未知比特，輸入比特→輸出比特.對以上三個算法搜索的區分器結果如下：

1)ANU算法的積分區分器：

2)ANU-II算法的積分區分器：

3)LiCi算法的積分區分器：

表4 ANU，ANU-II和LiCi攻擊結果對比

上述結果表明，本文對以上三個算法所得到的區分器優于目前其他分析方法，如差分線性、不可能差分、零相關線性等.對比結果如表4所示.

6 結束語

目前對ANU，ANU-II和LiCi算法的分析有：差分/線性、零相關分析以及不可能差分等分析方法.注意到，對于以上三個算法是否能抵御基于比特積分攻擊的這一問題仍有待解決.此外，在密碼算法攻擊中，所攻擊的區分器輪數高低優劣更能準確的衡量密碼算法的安全性，也更具有參考價值.

本文針對ANU，ANU-II和LiCi算法的結構特性，構建新的比特可分性MILP模型，給出了三個算法的9輪、8輪和12輪的積分區分器自動化搜索方法.相比其他已知的分析方法，本文所得到三個算法的區分器輪數和選擇明文量都是最優的，利用這些區分器可以得到更高輪的積分攻擊.同時針對LiCi算法的結構進行變形，提出一種新的LiCi算法的等價結構.由于目前比特積分攻擊沒有考慮到密鑰編排算法.我們可考慮對以上三個算法利用密鑰間的特殊性質與可分性質相結合的思想，如立方攻擊等方法來進一步提高密碼算法的分析輪數.