μ2算法的積分攻擊和不可能差分攻擊

胡 斌 張貴顯

(戰(zhàn)略支援部隊(duì)信息工程大學(xué) 鄭州 450001)

1 引言

積分攻擊是由Knudsen等人[1]在FSE 2002上提出的一種密碼分析方法。該攻擊方法是繼差分分析和線性分析之后，密碼學(xué)界公認(rèn)的最有效的分析方法之一。2015年歐密會上，Todo[2]提出了推廣的積分性質(zhì)--可分性(division property)，極大地改進(jìn)了積分區(qū)分器的搜索結(jié)果。2015年美密會上，Todo[3]將可分性應(yīng)用到MISTY1密碼算法上，攻破了全輪的MISTY1算法。然而，對于基于非S盒構(gòu)造的分組密碼算法，基于字可分性搜索得到的積分區(qū)分器與通過實(shí)驗(yàn)窮舉獲得的積分區(qū)分器之間仍有差距，這說明字可分性仍然不夠精確。2016年FSE會議上，Todo等人[4]提出二子集比特可分性和三子集比特可分性，可以找到更精確的積分區(qū)分器。但是當(dāng)密碼算法的分組規(guī)模n比較大時(shí)，刻畫中間狀態(tài)可分性的時(shí)間復(fù)雜度和存儲復(fù)雜度會變得十分大，這導(dǎo)致比特可分性無法應(yīng)用到分組規(guī)模較大的分組密碼算法上。2016年亞密會上，Xiang等人[5]將二子集可分性的刻畫問題轉(zhuǎn)化為混合整數(shù)線性規(guī)劃問題(Mixed Integral Linear Programming,MILP)，進(jìn)而用MILP求解器進(jìn)行求解，改進(jìn)了分組密碼積分區(qū)分器搜索結(jié)果。2019年CT-RSA會議上，Hu等人[6]提出了一種簡化的三子集可分性，并將他們轉(zhuǎn)化為SMT問題進(jìn)行求解，改進(jìn)了已有的積分區(qū)分器搜索結(jié)果。2019年亞密會上，Wang等人[7]通過提出“剪枝技術(shù)”來約簡冗余向量，有效解決了基于比特的三子集可分性的自動化刻畫問題，對基于比特的可分性的自動化刻畫問題進(jìn)行了理論完善。2020年亞密會上，Hu等人[8]從代數(shù)角度重新描述了可分性，進(jìn)一步詮釋了可分性的含義。

差分分析[9]由Biham和Shamir在1990年第1次提出。該攻擊方法是攻擊迭代型分組密碼最有效的方法之一，也是衡量分組密碼安全性的重要指標(biāo)。評估一個(gè)密碼算法抵抗差分密碼分析的能力主要有兩個(gè)方面：一是獲取差分活躍S盒數(shù)目的下界；二是搜索最大概率的差分特征。Mouha等人[10]和Wu等人[11]將計(jì)算差分活躍S盒的最小數(shù)目問題轉(zhuǎn)化為MILP問題。2014年亞密會上，Sun等人[12]改進(jìn)了基于MILP的評估分組密碼抵抗差分分析能力的算法，并提出一個(gè)啟發(fā)式算法去尋找差分特征。隨后，Sun等人[13]構(gòu)造了帶概率的MILP傳播模型來尋找最優(yōu)的差分特征。然而，隨著輪數(shù)的增加，MILP模型包含的不等式的數(shù)目急劇增加，導(dǎo)致模型的求解效率低下，以致到達(dá)一定輪數(shù)之后模型常常無法求解。為了提升搜索效率，2017年SecITC會議上，Sasaki等人[14]基于SageMath生成的不等式，提出了尋找刻畫S盒可分鏈和差分特征的最少不等式的方法。2019年FSE會議上，Zhou等人[15]結(jié)合“分而治之”的思想改進(jìn)了部分分組密碼抵抗差分/線性攻擊能力的評估結(jié)果。2020年FSE會議上，Boura等人[16]將SageMath生成的不等式進(jìn)行相加獲取更多候選不等式，然后再利用Sasaki等人的方法尋找最少的不等式，從而進(jìn)一步約簡了不等式。目前，基于MILP評估分組密碼抵抗差分攻擊能力已經(jīng)逐漸發(fā)展成為一種成熟的方法。

不可能差分分析由文獻(xiàn)[17]和文獻(xiàn)[18]分別獨(dú)立提出[17,18]，是差分分析的一個(gè)重要的變體之一。與差分分析利用高概率差分特征恢復(fù)密鑰相反，它利用的是概率為0的差分特征，其基本思想是排除那些使概率為0的差分特征成立的候選密鑰。對于不可能差分，當(dāng)用正確密鑰脫密密文對時(shí)，一定不會得到符合該路徑的差分；當(dāng)用錯(cuò)誤密鑰脫密密文對時(shí)，得到的差分會隨機(jī)分布，如果某個(gè)密鑰滿足該路徑的差分，那么該候選密鑰一定為錯(cuò)誤密鑰；那么篩去所有的錯(cuò)誤密鑰猜測值，剩下的就是正確密鑰。

μ2算法是由Yeoh等人[19]于2019年設(shè)計(jì)的一個(gè)分組長度為64 bit，密鑰長度為80 bit的輕量級分組密碼算法。該算法共15輪，采用TYPE-II廣義Feistel結(jié)構(gòu)，F(xiàn)函數(shù)采用重復(fù)4次的S-P結(jié)構(gòu)，其中S層為4個(gè)并置4 bit S盒，P層采用比特拉線，S盒與PRESENT算法中的S盒一致。μ2算法與已有的密碼算法相比有更高的吞吐率。設(shè)計(jì)者在設(shè)計(jì)文檔中對μ2算法抵抗差分分析、線性分析的能力進(jìn)行簡要介紹。然而，μ2算法抵抗積分攻擊和不可能差分分析的能力尚不清楚，因此本文對該算法進(jìn)行了積分攻擊和不可能差分分析，并對該算法抵抗差分分析的能力給出進(jìn)一步的評估。

本文具體貢獻(xiàn)如下：首先，為了評估μ2算法抵抗積分攻擊的能力，本文利用基于比特的可分性結(jié)合MILP搜索工具對μ2算法的積分區(qū)分器進(jìn)行搜索。為了提升搜索效率，本文結(jié)合Boura等人[16]的方法將描述S盒可分鏈的不等式的數(shù)目從11降到7，最終得到μ2算法的8輪和9輪積分區(qū)分器，并利用8輪積分區(qū)分器對9輪的μ2算法進(jìn)行積分攻擊，攻擊的時(shí)間復(fù)雜度為 276次9輪加密，數(shù)據(jù)復(fù)雜度為 248，存儲復(fù)雜度為 248。其次，為了評估μ2算法抵抗不可能差分攻擊的能力，本文采用中間相遇法得到了9輪的截?cái)嗖豢赡懿罘?，為了進(jìn)行更長輪數(shù)的密鑰恢復(fù)攻擊，在9輪不可能差分后面添加兩輪，可以對11輪μ2算法進(jìn)行攻擊，攻擊的時(shí)間復(fù)雜度為249次11輪加密，數(shù)據(jù)復(fù)雜度為 264個(gè)明文。最后，本文基于MILP對μ2算法抵抗差分攻擊能力給出進(jìn)一步的評估，并證明4輪μ2算法的差分特征的最大概率為 2-39，與設(shè)計(jì)報(bào)告指出的4輪差分特征的概率不超過2-36相比結(jié)果更為緊致。

本文的結(jié)構(gòu)安排如下：第2節(jié)主要對μ2算法進(jìn)行介紹；第3節(jié)給出μ2算法積分攻擊的具體過程和復(fù)雜度計(jì)算；第4節(jié)給出μ2算法的不可能差分分析的具體過程和復(fù)雜度計(jì)算；第5節(jié)對μ2算法抵抗差分分析能力進(jìn)一步評估，給出更緊致的安全界限；第6節(jié)總結(jié)全文。本文的程序均通過Python編程實(shí)現(xiàn)，在以下平臺上進(jìn)行：AMD R7-4800H CPU@2.9 GHz, 16 GB RAM；Python的運(yùn)行環(huán)境為VS2019；MILP模型求解器為Gurobi9.0.2；本文所有的程序和實(shí)驗(yàn)結(jié)果被放置在以下網(wǎng)站：https://github.com/zgxxgz111/integral-attack-andimpossible-difference。

2 μ2算法介紹

2.1 μ 2算法的加密過程

2.2 μ 2算法的密鑰擴(kuò)展方案

2.3 μ 2算法的F函數(shù)

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

3 對 μ2算法的積分攻擊

目前來說，自動化搜索積分區(qū)分器的方法主要有兩種：基于二子集比特可分性和基于三子集比特可分性。根據(jù)文獻(xiàn)[7]的結(jié)果得知，與二子集比特可分性相比，三子集比特可分性雖然可能會搜索得到更多的平衡比特，但是積分區(qū)分器的輪數(shù)往往不會有所突破。同時(shí)利用三子集比特可分性搜索積分區(qū)分器的時(shí)間復(fù)雜度較高，搜索效率較低。由于本文主要立足于進(jìn)行積分攻擊同時(shí)考慮到搜索效率，所以我們利用二子集可分性搜索積分區(qū)分器。

圖2 S-P結(jié)構(gòu)圖

圖3 F函數(shù)圖示

表1 S盒

3.1 比特可分性及其傳播規(guī)則

S盒的MILP模型 利用規(guī)則1得到S盒的47個(gè)可分鏈，然后通過SageMath數(shù)學(xué)軟件可以得到327個(gè)線性不等式來刻畫S盒可分鏈，并利用文獻(xiàn)[13]的貪婪算法來約簡不等式組，最終得到11個(gè)不等式。為了減少描述S盒可分鏈的不等式的數(shù)目從而提升搜索效率，本文采用文獻(xiàn)[16]中約簡刻畫S盒差分特征的不等式的方法。針對每一個(gè)可分鏈p=(x0,x1,x2,x3,y0,y1,y2,y3)，將SageMath生成的327個(gè)不等式中經(jīng)過可分鏈p=(x0,x1,x2,x3,y0,y1,y2,y3)的不等式兩兩相加，然后對這些不等式進(jìn)行檢測，如果這些不等式能移除不同的可分鏈集合，那么保留這個(gè)不等式。通過這種方法，獲得了1019個(gè)候選不等式。然后再利用Sasaki等人[14]的方法來尋找最小的不等式數(shù)目，最終得到7個(gè)不等式來刻畫S盒的可分鏈。

3.2 搜索積分區(qū)分器

3.3 9輪μ 2算法的積分攻擊

表2 積分區(qū)分器

4 對 μ2算法的不可能差分分析

4.1 μ 2算法的9輪不可能差分

定理1μ2算法存在形如(000α)?(000α)的9輪截?cái)嗖豢赡懿罘?，其?,α均 為16 bit向量且α/=0。

4.2 11輪μ 2算法的不可能差分分析

圖4 μ 2算法的9輪不可能差分

5 對 μ2算法的抗差分分析能力的評估

在設(shè)計(jì)文檔中，設(shè)計(jì)者對μ2算法抵抗差分分析的能力進(jìn)行了評估，本節(jié)基于MILP對μ2算法抵抗差分分析的能力進(jìn)一步評估。

5.1 針對基于比特設(shè)計(jì)的密碼算法的評估框架

圖5 μ 2算法的11輪不可能差分攻擊

5.2 μ 2算法抵抗差分分析的能力評估

本文將上述方法應(yīng)用到μ2算法，得到2輪μ2算法最優(yōu)差分特征的概率為 2-12， 3輪μ2算法最優(yōu)差分特征的概率為 2-24，這與設(shè)計(jì)報(bào)告的評估結(jié)果一致。然而本文搜索得到4輪μ2算法最優(yōu)差分特征的概率為 2-39，與設(shè)計(jì)報(bào)告指出的4輪差分特征的概率不超過 2-36相比更為緊致。計(jì)算復(fù)雜度的限制使我們無法搜索更高輪數(shù)最優(yōu)差分特征。然而μ2算法全輪共有15輪，我們相信有較大的安全空間抵抗差分密碼分析。關(guān)于4輪μ2算法最優(yōu)差分特征的結(jié)果如表3所示。

表3 4輪μ 2算法最優(yōu)差分特征

6 結(jié)束語

本文首次對μ2算法抵抗積分攻擊和不可能差分分析的能力進(jìn)行評估，分別得到了μ2算法的8輪和9輪積分區(qū)分器和9輪不可能差分，從而進(jìn)行了積分攻擊和不可能差分攻擊。結(jié)果顯示9輪μ2算法不能抵抗積分攻擊，11輪μ2算法不能抵抗不可能差分攻擊。另外，本文對μ2算法抵抗差分攻擊的能力進(jìn)一步評估，證明了μ2算法的4輪差分特征的最大概率為 2-39， 比設(shè)計(jì)報(bào)告中的2-36更為緊致。本文的結(jié)果完善了對μ2算法抵抗積分攻擊、差分攻擊和不可能差分攻擊能力的評估，結(jié)果顯示μ2算法對上述攻擊仍存在一定的安全冗余空間。如何考慮更多的設(shè)計(jì)細(xì)節(jié)從而給出更長的不可能差分以及如何利用已經(jīng)得到的區(qū)分器進(jìn)行更長輪數(shù)的攻擊是下一步工作的重點(diǎn)。