ANU，ANU-II和LiCi算法的積分區(qū)分器搜索

王紅艷，韋永壯，劉文芬

1(桂林電子科技大學(xué) 廣西密碼學(xué)與信息安全重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004) 2(桂林電子科技大學(xué) 廣西高校云計(jì)算與復(fù)雜系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004) 3(桂林電子科技大學(xué) 廣西無線寬帶通信與信號處理重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004)

1 引 言

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

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

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

2 算法介紹

2.1 符號說明

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

K：80比特主密鑰

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

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

⊕：按位異或操作(XOR)

<<<α：左循環(huán)左移α比特

>>>β：右循環(huán)右移β比特

‖：二進(jìn)制連接符

2.2 ANU和ANU-II算法簡介

2.2.1 ANU算法

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

圖2 ANU算法的P置換

ANU算法的輪函數(shù)F由密鑰加、異或運(yùn)算、字節(jié)替換和循環(huán)移位等四種基本運(yùn)算構(gòu)成.設(shè)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基礎(chǔ)上進(jìn)行優(yōu)化，并舍去P置換線性操作.其分組長度為64比特，密鑰長度為128比特，共迭代25輪.ANU-II算法結(jié)構(gòu)如圖3所示.

圖3 ANU-II算法結(jié)構(gòu)

關(guān)于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算法的比特積分攻擊不需要考慮密鑰編排算法，所以這里不再作詳細(xì)介紹，具體可參見文獻(xiàn)[1,2].

2.3 LiCi算法簡介

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

如圖5是LiCi算法的等價(jià)結(jié)構(gòu)，可看作該算法的一輪加密運(yùn)算由兩個簡單的Feistel結(jié)構(gòu)相接而成.關(guān)于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算法結(jié)構(gòu)

Fig.4 Structure of LiCi

圖5 LiCi算法的等價(jià)結(jié)構(gòu)

Fig.5 Equivalent structure of LiCi

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

3 可分性分析

3.1 可分性和可分性路徑

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

3.2 可分性的傳播規(guī)則

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

3.3 混合整數(shù)線性規(guī)劃(MILP)

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

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

3.4 SAGE中的不等式生成函數(shù)

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

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

Triangle=Polyhedron(vertices = Points)

for l in triangle.inequality_generator()：

print l

4 可分性MILP模型的構(gòu)建

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

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

2)利用1中基本運(yùn)算的可分性質(zhì)，根據(jù)三個算法本身的結(jié)構(gòu)特性來構(gòu)建經(jīng)過輪函數(shù)的可分性路徑的MILP模型，包括非線性層和置換層.

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

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

圖6 ANU的MILP模型變量之間的關(guān)系

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

算法1.對ANU算法XOR函數(shù)的MILP模型

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

end for

算法2.對ANU算法COPY函數(shù)的MILP模型

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

end for

4.1 ANU算法的MILP模型

4.1.1 模型化S盒

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

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

4.1.2 模型化置換層

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

4.2 ANU-II算法的MILP模型

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

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

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

4.3 LiCi算法的MILP模型

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

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

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

4.4 目標(biāo)函數(shù)

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

5 實(shí)驗(yàn)分析結(jié)果

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

1)ANU算法的積分區(qū)分器：

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

3)LiCi算法的積分區(qū)分器：

表4 ANU，ANU-II和LiCi攻擊結(jié)果對比

上述結(jié)果表明，本文對以上三個算法所得到的區(qū)分器優(yōu)于目前其他分析方法，如差分線性、不可能差分、零相關(guān)線性等.對比結(jié)果如表4所示.

6 結(jié)束語

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

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