武小年，李迎新，韋永壯，孫亞平

（1.桂林電子科技大學(xué)廣西密碼學(xué)與信息安全重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004；2.保密通信重點(diǎn)實(shí)驗(yàn)室，四川 成都 610041；3.廣西高校云計(jì)算與復(fù)雜系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004）

1 引言

近年來，伴隨著電子信息技術(shù)的迅速發(fā)展，射頻識(shí)別、傳感器網(wǎng)絡(luò)和智能卡等微型計(jì)算設(shè)備應(yīng)用需求不斷增大。注意到，這些微型計(jì)算設(shè)備的存儲(chǔ)空間小、計(jì)算能力弱、功耗小等資源受限特點(diǎn)使常規(guī)的對(duì)稱密碼算法并不適用。如何設(shè)計(jì)新型的輕量級(jí)密碼算法，以滿足各種資源受限環(huán)境下的使用，成為目前的研究熱點(diǎn)。過去的10 年里，多個(gè)輕量級(jí)算法被相繼提出，比如LBlock、GIFT、Midori、PRESENT、MIBS、LED、SPECK等密碼算法。另一方面，輕量級(jí)分組密碼的安全性至關(guān)重要，常見的密碼分析方法包括差分密碼分析[1]、線性密碼分析[2]、不可能差分分析[3-4]、積分分析[5]等。

不可能差分分析是對(duì)差分分析的擴(kuò)展，由Knudsen[3]和Biham 等[4]提出。不可能差分分析的關(guān)鍵在于構(gòu)造不可能差分區(qū)分器，以進(jìn)行密鑰篩選。由于該攻擊方法簡單、有效，因此廣泛應(yīng)用到分組密碼攻擊中[6-8]。為了能夠快速高效地尋找高輪數(shù)的不可能差分區(qū)分器，多種自動(dòng)化搜索方法被先后提出。2012 年，Wu 等[9]提出一個(gè)較通用的不可能差分區(qū)分器的自動(dòng)化搜索方法，其將r輪分組密碼結(jié)構(gòu)視為一個(gè)方程組，描述了內(nèi)部基元中差分的傳播行為，尤其是分組密碼結(jié)構(gòu)的S 盒置換或分支交換。2017 年，Luo 等[10]改進(jìn)Wu 等[9]提出的自動(dòng)化搜索方法，并測試該方法是否存在解，其主要簡化了最耗時(shí)的矩陣運(yùn)算，在更短的時(shí)間內(nèi)找到了更多不可能的差分，提高了搜索效率。同年，Sasaki 等[11]針對(duì)分組密碼算法，提出了基于MILP 模型的比特級(jí)的不可能差分自動(dòng)化捜索方法，并給出了Midori-128 算法的7 輪不可能差分區(qū)分器。2018 年，韓亞等[12]通過學(xué)習(xí)基于比特的可分性質(zhì)，利用三子集傳播方程，提出一種基于SAT/SMT 求解器自動(dòng)化搜索ARX 結(jié)構(gòu)分組密碼積分區(qū)分器的方法。張仕偉等[13]利用SIMON 中AND 組件的差分傳播特性，構(gòu)造2 條約束條件，結(jié)合SAT 求解器提出了自動(dòng)化搜索算法，搜索出多條11 輪不可能差分區(qū)分器，該算法可以準(zhǔn)確地判斷SIMON 算法的任意差分對(duì)能否構(gòu)成一條不可能差分區(qū)分器。Zhang 等[14]提出了“Modes operation”方法，用于對(duì)ARX 類型的密碼算法進(jìn)行不可能差分區(qū)分器的自動(dòng)化搜索。

2018 年，Bansod 等提出了2 種輕量級(jí)分組密碼算法——GRANULE[15]和MANTRA[16]。這2 種算法均使用了典型的Feistel 結(jié)構(gòu)，并采用了輕量級(jí)S 盒和簡單的位操作，使其能夠在較少的輪數(shù)中完成最大擴(kuò)散效果。他們對(duì)GRANULE 和MANTRA算法分別進(jìn)行了安全性分析，表明2 種算法均能有效地抵抗差分分析、線性分析、Biclique 攻擊、零相關(guān)分析等。2019 年，石淑英等[17]針對(duì)GRANULE算法構(gòu)造了9 個(gè)5 輪不可能差分區(qū)分器，但是該方法在構(gòu)造不可能差分區(qū)分器中并未考慮算法內(nèi)部核心部件代數(shù)性質(zhì)。如何針對(duì)這些新算法構(gòu)建更高輪數(shù)的不可能差分區(qū)分器有待深入解決。

本文基于GRANULE 和MANTRA 算法結(jié)構(gòu)，利用密碼S 盒差分分布表新性質(zhì)，結(jié)合中間相遇思想，提出了一種不可能差分區(qū)分器的新自動(dòng)化搜索方法?；谠撍阉鞣椒ǎ疚陌l(fā)現(xiàn)GRANULE/MANTRA 算法有144/52 個(gè)不同的7/9 輪的不可能差分區(qū)分器。

2 算法介紹

2.1 GRANULE 算法簡介

GRANULE 算法是一種基于Feistel 結(jié)構(gòu)的輕量級(jí)分組密碼算法，分組長度為64 bit，支持80 bit和128 bit 這2 種密鑰長度，迭代輪數(shù)為32 輪。該算法中的輪函數(shù)F包括置換層、S 盒、循環(huán)移位、密鑰加和異或運(yùn)算。GRANULE 算法結(jié)構(gòu)如圖1所示。

圖1 GRANULE 算法結(jié)構(gòu)

設(shè)GRANULE 算法第i輪輸入是Ci，輸出是Ci+1，該算法的左分支和右分支分別記為Li和Ri(i=0,1,2,…,31)，則從(Li,Ri)更新至(Li+1,Ri+1)，更新過程為

GRANULE 算法采用一個(gè)4 bit 的S 盒，即{0,1}4→{0,1}4。S 盒具體數(shù)值以十六進(jìn)制的形式給出，如表1 所示。

表1 GRANULE 算法S 盒

2.2 MANTRA 算法簡介

MANTRA 算法是一種基于Feistel 結(jié)構(gòu)的輕量級(jí)分組密碼算法，分組長度為64 bit，支持80 bit和128 bit 這2 種密鑰長度，迭代輪數(shù)為32 輪。該算法中的輪函數(shù)F是由2 輪的Feistel 結(jié)構(gòu)拼接而成，這2 個(gè)Feistel 結(jié)構(gòu)都包含了S 盒、密鑰加、循環(huán)移位和異或運(yùn)算4 個(gè)基本操作。MANTRA 算法結(jié)構(gòu)如圖2 所示。

圖2 MANTRA 算法結(jié)構(gòu)

設(shè)MANTRA 算法的第i輪輸入是Ci，輸出是Ci+1，該算法的左分支和右分支分別記為Li和Ri(i=0,1,2,…,31)，則從(Li,Ri)更新至(Li+1,Ri+1)，更新過程為

MANTRA 算法中使用的是一個(gè)4 bit 的S 盒，即{0,1}4→{0,1}4。S 盒具體數(shù)值以十六進(jìn)制的形式給出，如表2 所示。

表2 MANTRA 算法S 盒

3 2 種算法的不可能差分區(qū)分器構(gòu)造

2014 年，Tezcan[18]提出一種針對(duì)S 盒評(píng)估以及S 盒差分傳播的新標(biāo)準(zhǔn)。當(dāng)給定S 盒的差分輸入值時(shí)，對(duì)應(yīng)S 盒的輸出差分中至少有1 bit 的概率為1，即可以確定該輸出差分中的1 bit 的差分值。被確定概率為1 的比特被稱為未受干擾比特?；谠撍枷耄瑢?duì)密碼算法中S 盒的差分分布表進(jìn)行分析，通過分析輸入/輸出差分值，找到未受干擾比特。將該方法應(yīng)用于不可能差分分析中，可獲得更長的不可能差分區(qū)分器。

針對(duì)GRANULE 和MANTRA 算法的不可能差分區(qū)分器自動(dòng)搜索方法，主要是通過分析2 種算法S 盒的差分分布表，得到2 種算法對(duì)應(yīng)的S 盒差分特征，再利用中間相遇思想，對(duì)2 種算法分別從加/解密方向得到的差分路徑進(jìn)行遍歷，篩選出概率為0 的最優(yōu)差分路徑，即不可能差分區(qū)分器。

3.1 S 盒的差分特征

Biham 等[1]對(duì)DES 算法進(jìn)行差分密碼分析的關(guān)鍵在于觀察到S 盒差分分布不均勻特性，并給出了S 盒差分分布表的概念，這個(gè)概念完全刻畫了S 盒的差分傳播特征，實(shí)際上也是滿足特定差分的隨機(jī)輸入對(duì)經(jīng)過S 盒作用后輸出差分的分布特征?；谖墨I(xiàn)[18]中使用的方法，對(duì)差分分布表輸入/輸出差分進(jìn)行分析總結(jié)，得到S 盒的輸入/輸出差分特征，將該特征應(yīng)用到不可能差分區(qū)分器的推導(dǎo)過程中，可有效提高不可能差分區(qū)分器的長度。

定義1S 盒差分分布表。設(shè)i,j∈N，給定m∈，n∈，從到的非線性映射（也稱為S 盒）定義為

構(gòu)造2i×2j的表格如下：以m為行指標(biāo)遍歷，n為列指標(biāo)遍歷，行列交錯(cuò)處的取值NS(m,n)。稱m為S 盒的輸入差分，n為S 盒的輸出差分。三元數(shù)組(m,n,NS(m,n))按上述方式構(gòu)成的表即為S 盒的差分分布表。

3.1.1 GRANULE 算法S 盒的差分特征

根據(jù)定義1，構(gòu)造GRANULE 算法S 盒的差分分布表，GRANULE 算法S 盒的差分分布表如表3 所示。

當(dāng)S 盒的輸入/輸出差分為某些定值時(shí)，其輸入/輸出差分會(huì)存在一定的規(guī)律性。如輸入差分為0001時(shí)，輸出差分可能為1000，1001，1010，1011，1100，1101，1110，1111。而這些輸出差分的第3 比特均為1，另外3 個(gè)比特的差分未知，簡記為1***（其中“*”表示未知差分）。根據(jù)該方法，對(duì)表3 進(jìn)行總結(jié)可得到性質(zhì)1。

性質(zhì)1GRANULE 算法S 盒的差分分布表輸入/輸出差分不均勻的特征表明，當(dāng)S 盒的輸入差分為某些定值時(shí)，其輸出差分存在相應(yīng)的特征，其輸出差分存在的傳播特性如表4 所示。

表3 GRANULE 算法S 盒的差分分布表

表4 GRANULE 算法S 盒輸入/輸出差分特征

表4 中，“*”表示差分未知，“0”表示差分為0，“1”表示差分為1。將表4 中GRANULE 算法S盒的差分特征應(yīng)用于該算法的加/解密過程中，可有效拓展不可能差分區(qū)分器的長度。

3.1.2 MANTRA 算法S 盒的差分特征

根據(jù)定義1，構(gòu)造MANTRA 算法S 盒的差分分布表，然后利用3.1.1 節(jié)中的方法對(duì)S 盒的差分分布表進(jìn)行分析可得到性質(zhì)2。

性質(zhì)2MANTRA算法S盒的差分分布表輸入/輸出差分不均勻的特征表明，當(dāng)S 盒的輸入差分為某些定值時(shí)，其輸出差分存在相應(yīng)的特征，其輸出差分存在的傳播特性如表5 所示。

表5 MANTRA 算法S 盒的輸入/輸出差分特征

將表5 中MANTRA 算法S 盒的差分特征應(yīng)用于該算法的加/解密過程中，可有效拓展不可能差分區(qū)分器的長度。

3.2 GRANULE 算法不可能差分區(qū)分器自動(dòng)搜索方法

從GRANULE 算法S 盒差分分布表的輸入/輸出差分中找到S 盒的輸入/輸出差分傳播特征，在此基礎(chǔ)上，基于中間相遇思想，先從加密方向找到一條概率為1 的有效差分路徑，然后從解密方向找到一條概率為1 的有效差分路徑；再在上述的加密方向的路徑集合和解密方向的路徑集合中進(jìn)行遍歷，并將其拼接，篩選出一條概率為0 的最優(yōu)差分路徑，即不可能差分區(qū)分器。在搜索篩選概率為0的最優(yōu)差分路徑過程中，采用自動(dòng)化搜索的方式進(jìn)行遍歷。

中間相遇思想是構(gòu)造不可能差分區(qū)分器的常用方法，將一個(gè)密碼算法T分成兩部分：T=T0T1，T0存在概率為1 的差分ΔE→ΔF，T1存在概率為1的差分ΔG→ΔH；如果ΔF和ΔH不相等，那么對(duì)于T就存在概率為0 的差分ΔE→ΔG，即ΔE→ΔG稱為“不可能差分區(qū)分器”，如圖3 所示。

圖3 不可能差分區(qū)分器原理

3.2.1 GRANULE 算法有效差分路徑

對(duì)GRANULE 算法有效差分路徑的搜索，首先是在算法的加密方向，利用中間相遇思想找到一條概率為1 的差分路徑，具體地，當(dāng)輸入差分在經(jīng)過輪函數(shù)中S 盒時(shí)，利用性質(zhì)1 中S 盒的差分特征進(jìn)行差分傳播，輸出較為準(zhǔn)確的差分，直到輸出差分全為未知差分時(shí)，則停止搜索加密方向的差分路徑，并輸出差分路徑集合。其次，在算法的解密方向，按照同樣的方式，從相反的解密方向進(jìn)行搜索，最終輸出解密方向的差分路徑集合。

GRANULE 算法加密方向搜索概率為1 的差分路徑過程如算法1 所示。

算法1GRANULE 算法加密方向有效差分路徑自動(dòng)搜索

輸入64 bit 差分明文M，其左右分支分別記為Li和Ri(i=0,1,2,…,31)

輸出輸出每輪經(jīng)過輪函數(shù)的輸出差分集合List

3.2.2 GRANULE 算法不可能差分區(qū)分器

基于上述GRANULE 算法加/解密方向自動(dòng)搜索的概率為1 的差分路徑集合，利用中間相遇思想，對(duì)算法1 得到的加密方向的差分路徑集合和解密方向的差分路徑集合進(jìn)行遍歷拼接，搜索一條概率為0 的最優(yōu)差分路徑，即不可能差分區(qū)分器。

GRANULE 算法搜索不可能差分區(qū)分器過程如算法2 所示。

算法2GRANULE 算法不可能差分區(qū)分器自動(dòng)搜索

輸入加密方向差分路徑集合List_en，解密方向差分路徑集合List_de

輸出輸出最優(yōu)不可能差分區(qū)分器輪數(shù)

算法2 通過遍歷算法1 中得到的加密方向差分路徑集合和解密方向差分路徑集合，每次分別從加密方向和解密方向路徑中選取一條數(shù)據(jù)，利用contradiction 函數(shù)進(jìn)行矛盾點(diǎn)的檢測。通過遍歷和檢測，最終輸出最優(yōu)不可能差分區(qū)分器輪數(shù)。

由于GRANULE 算法的分組長度為64 bit，遍歷所有可能差分的復(fù)雜度太高，因此本文只對(duì)具有1 bit 活躍的輸入/輸出差分對(duì)進(jìn)行搜索。利用上述自動(dòng)搜索方法進(jìn)行搜索，搜索到了144 個(gè)不同的7 輪不可能差分區(qū)分器，圖4 給出了其中一條不可能差分區(qū)分器的具體形式。

表6 列出了所搜索出的GRANULE 算法部分7 輪不可能差分區(qū)分器，其中，vi(0≤i≤7)表示第ibit 的差分為1，其余比特差分為0，0 表示該字節(jié)的差分為0。

圖4 GRANULE 算法不可能差分區(qū)分器示意

表6 GRANULE 算法不可能差分區(qū)分器

3.3 MANTRA 算法不可能差分區(qū)分器自動(dòng)搜索方法

MANTRA 算法不可能差分區(qū)分器的搜索方法與GRANULE 算法不可能差分區(qū)分器的搜索方法類似，是根據(jù)MANTRA 算法的差分特征，再采用中間相遇思想，分別從加/解密方向各找到一條概率為1 的有效差分路徑；再對(duì)加/解密方向的路徑集合進(jìn)行遍歷和拼接，篩選出一條概率為0 的最優(yōu)差分路徑，即不可能差分區(qū)分器。2 種算法搜索方法不同的地方在于2 種算法S 盒的差分特征不同，因此MANTRA 算法在搜索加/解密方向的有效差分路徑時(shí)，需要根據(jù)其自身算法S 盒的差分特征進(jìn)行傳播，從而輸出對(duì)應(yīng)的差分路徑。

由3.2 節(jié)中提出的不可能差分區(qū)分器自動(dòng)化搜索方法，利用性質(zhì)2 中的MANTRA 算法S 盒的輸入/輸出差分特征，只對(duì)具有1 bit 活躍的輸入/輸出差分對(duì)進(jìn)行自動(dòng)化搜索，可搜索到52 個(gè)不同的9輪不可能差分區(qū)分器，表7 列出了所搜索出的MANTRA 算法部分9 輪不可能差分區(qū)分器，其中，vi(0≤i≤7)表示第ibit 的差分為1，其余比特差分為0，0 表示該字節(jié)的差分為0。

表7 MANTRA 算法不可能差分區(qū)分器

4 分析結(jié)果對(duì)比

為加強(qiáng)對(duì)GRANULE 算法和MANTRA 算法的安全性分析，并給出本文不可能差分區(qū)分器對(duì)這2種算法的分析結(jié)果，采用Java 語言實(shí)現(xiàn)了本文提出的搜索方法，并在處理器為Intel i5-8500，內(nèi)存為8 GB的Windows10 家庭版系統(tǒng)環(huán)境下運(yùn)行，算法的時(shí)間復(fù)雜度為O(n4)，其中，n表示輸入的明文長度。針對(duì)GRANULE 算法和MANTRA 算法，遍歷1 bit活躍的輸入輸出差分對(duì)，測試所使用的時(shí)間分別為392 ms 和274 ms。

為進(jìn)一步歸納對(duì)這2 種算法的現(xiàn)有方法安全性分析結(jié)果，將本文分析結(jié)果與現(xiàn)有文獻(xiàn)進(jìn)行了對(duì)比。針對(duì)GRANULE 算法的安全性分析，將本文結(jié)果與文獻(xiàn)[10,17]中提出的自動(dòng)化搜索方法，以及文獻(xiàn)[15]采用的零相關(guān)線性分析進(jìn)行對(duì)比。零相關(guān)線性分析由Bogdanov 等[19]提出，該分析方法是尋找密碼算法概率為，即相關(guān)性為0 的線性逼近作為零相關(guān)線性分析的區(qū)分器，進(jìn)而區(qū)分出正確密鑰和錯(cuò)誤密鑰。零相關(guān)線性分析作為不可能差分分析的對(duì)偶方法，存在與不可能差分區(qū)分器對(duì)比的合理性。針對(duì)MANTRA 算法的安全性分析，將本文結(jié)果與文獻(xiàn)[10]中提出的自動(dòng)化搜索方法，以及文獻(xiàn)[16]中的零相關(guān)線性分析進(jìn)行了對(duì)比。對(duì) GRANULE 算法和MANTRA 算法的分析結(jié)果如表8 所示。

表8 對(duì)GRANULE 算法和MANTRA 算法的分析結(jié)果

文獻(xiàn)[15]在提出GRANULE 算法時(shí)，使用零相關(guān)線性分析的分析方法對(duì)其進(jìn)行安全性分析，構(gòu)造出 6 輪的零相關(guān)線性區(qū)分器。文獻(xiàn)[17]針對(duì)GRANULE 算法給出了9 條5 輪不可能差分區(qū)分器中，其S 盒的輸入/輸出差分僅考慮“0”與“非0”這2 種情況，即輸入差分為“0”時(shí)，輸出差分也為“0”；輸入差分為“非0”時(shí)，輸出差分為“****”。文獻(xiàn)[10]對(duì)GRANULE 算法的自動(dòng)化搜索，得到38 個(gè)6 輪不可能差分區(qū)分器，其采用線性運(yùn)算，以半字節(jié)進(jìn)行搜索，搜索時(shí)間為76 ms。本文通過對(duì)GRANULE 算法中S 盒的差分分布表的輸入/輸出差分進(jìn)行總結(jié)，得到性質(zhì)1 所示的S 盒差分特征，其能夠獲得輸入/輸出差分的傳播規(guī)律，如在非0 情況下，若輸入差分為“0001”其輸出差分為“1***”；將該性質(zhì)與中間相遇思想結(jié)合，采用自動(dòng)化搜索方法，以比特進(jìn)行搜索，搜索時(shí)間較文獻(xiàn)[10]更長，但獲得的不可能差分區(qū)分器的輪數(shù)也更長。

文獻(xiàn)[16]在提出MANTRA 算法時(shí)，使用零相關(guān)線性分析的分析方法對(duì)其進(jìn)行安全性分析，構(gòu)造出8輪的零相關(guān)線性區(qū)分器。文獻(xiàn)[10]對(duì)MANTRA 算法的自動(dòng)化搜索，得到52 個(gè)6 輪不可能差分區(qū)分器，其采用線性運(yùn)算，以半字節(jié)進(jìn)行搜索，其搜索時(shí)間為51 ms。本文通過對(duì)MANTRA 算法S 盒的差分分布表的輸入/輸出差分進(jìn)行總結(jié)，得到性質(zhì)2 所示的S盒差分特征，通過結(jié)合中間相遇思想，并采用自動(dòng)化搜索方法，以比特進(jìn)行搜索，搜索時(shí)間較文獻(xiàn)[10]更長，但獲得的不可能差分區(qū)分器的輪數(shù)也更長。

綜上所述，通過分析密碼算法S 盒的差分分布表的輸入/輸出差分特征，并采用自動(dòng)化搜索方法，結(jié)合中間相遇思想，可以提高算法的不可能差分區(qū)分器長度。

5 結(jié)束語

本文針對(duì)GRANULE和MANTRA算法的結(jié)構(gòu)特性，通過分析其S 盒差分分布表獲得對(duì)應(yīng)的差分特征性質(zhì)，結(jié)合中間相遇思想，采用自動(dòng)化搜索的方式，在加/解密方向分別找到一條概率為1 的有效差分路徑；再在上述的加/解密方向的路徑集合中進(jìn)行遍歷，找到一條概率為0 的最優(yōu)差分路徑。研究結(jié)果發(fā)現(xiàn)，GRANULE/MANTRA 算法有144/52 個(gè)不同的7/9 輪的不可能差分區(qū)分器。在后續(xù)工作中，將充分地考慮密碼核心部件的代數(shù)性質(zhì)，以獲得更高輪數(shù)的區(qū)分器。