GRANULE 和MANTRA 算法的不可能差分區(qū)分器分析

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

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

1 引言

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

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

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

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

2 算法介紹

2.1 GRANULE 算法簡介

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

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

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

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

表1 GRANULE 算法S 盒

2.2 MANTRA 算法簡介

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

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

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

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

表2 MANTRA 算法S 盒

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

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

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

3.1 S 盒的差分特征

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

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

構(gòu)造2i×2j的表格如下：以m為行指標遍歷，n為列指標遍歷，行列交錯處的取值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 所示。

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

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

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

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

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

3.1.2 MANTRA 算法S 盒的差分特征

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

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

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

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

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

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

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

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

3.2.1 GRANULE 算法有效差分路徑

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

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

算法1GRANULE 算法加密方向有效差分路徑自動搜索

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

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

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

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

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

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

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

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

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

由于GRANULE 算法的分組長度為64 bit，遍歷所有可能差分的復雜度太高，因此本文只對具有1 bit 活躍的輸入/輸出差分對進行搜索。利用上述自動搜索方法進行搜索，搜索到了144 個不同的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ū)分器自動搜索方法

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

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

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

4 分析結(jié)果對比

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

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

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

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

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

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

5 結(jié)束語

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