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

胡 斌 張貴顯

(戰略支援部隊信息工程大學 鄭州 450001)

1 引言

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

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

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

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

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

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

2 μ2算法介紹

2.1 μ 2算法的加密過程

2.2 μ 2算法的密鑰擴展方案

2.3 μ 2算法的F函數

圖1 μ 2算法結構圖

3 對 μ2算法的積分攻擊

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

圖2 S-P結構圖

圖3 F函數圖示

表1 S盒

3.1 比特可分性及其傳播規則

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

3.2 搜索積分區分器

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

表2 積分區分器

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

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

定理1μ2算法存在形如(000α)?(000α)的9輪截斷不可能差分，其中0,α均 為16 bit向量且α/=0。

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

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

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

在設計文檔中，設計者對μ2算法抵抗差分分析的能力進行了評估，本節基于MILP對μ2算法抵抗差分分析的能力進一步評估。

5.1 針對基于比特設計的密碼算法的評估框架

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

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

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

表3 4輪μ 2算法最優差分特征

6 結束語

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