基于MILP的MGFN全輪差分分析及改進

李艷俊 畢鑫杰 項勇 林怡平

摘 要：

研究了輕量級分組密碼MGFN算法的抗差分分析能力并提出了改進方法。首先，基于MILP工具對MGFN算法建模，搜索迭代差分并構造了全輪差分路徑，整體差分概率為2－40，遠遠大于隨機置換的差分概率。然后，給出S盒的差分分支數概念并將其作為衡量差分安全性的指標，以新S盒替代原MGFN算法的S盒，并修改了密鑰擴展算法，提出新的MGFN-P算法。最后，通過差分路徑搜索和分析比較，說明了MGFN-P算法比原MGFN算法更安全、高效。

關鍵詞：MGFN；輕量級分組密碼；MILP；差分分析；分支數

中圖分類號：TP391.9?? 文獻標志碼：A??? 文章編號：1001-3695（2024）03-040-0911-05doi： 10.19734/j.issn.1001-3695.2023.07.0300

Differential analysis and improvement of full-round MGFN based on MILP

Li Yanjun1，2a， Bi Xinjie2a， Xiang Yong1， Lin Yiping2b

（1.Information Industry Information Security Evaluation Center，The 15th Research Institute of China Electronics Technology Group Corporation， Beijing 100083， China; 2.a. Dept. of Cryptologic Science & Technology， b. Dept. of Cyberspace Security， Beijing Institute of Electronic Science & Technology， Beijing 100070， China）

Abstract：

This article investigated the MGFN algorithms ability to resist differential analysis and proposed improved methods. First of all， it modeled this algorithm based on the MILP， and then got a 6-round iterative differential and a full round differential path with a total probability of 2－40， which was much larger than the differential probability of random permutation. Secondly， it gave the branch number of the S-box as an indicator to measure its differential safety. This paper also replaced the S-box of MGFN algorithm with a new S-box and proposed a new MGFN-P algorithm by modifying the key extension algorithm. Finally， differential path search and analysis show that MGFN-P algorithm is more secure and efficient than the original algorithm.

Key words：MGFN; lightweight block cipher; MILP; differential analysis; branch number

0 引言

隨著物聯網的發展，無線傳感器網絡 （wireless sensor networks， WSN）和無線射頻技術（radio frequency identification devices， RFID）等微型計算的應用越來越廣泛，更多的可穿戴技術、智能家居設計等設備不斷涌現，使人們的生活更加便利。但由于WSN和RFID是基于無線網絡傳輸信息，并且設備計算資源受到限制，一方面，如果不使用加密技術，那么傳輸數據容易被攻擊者干擾甚至破壞；另一方面，如果使用傳統加密算法進行數據處理，則會占用更多的計算資源，而且速度慢。所以，為了保證重要數據傳輸和存儲的安全性，既有效率又能保證安全性的輕量級分組密碼算法應運而生。

輕量級分組密碼通常由不同的代換組件通過迭代結構組合而成，目前比較主流的結構有Feistel結構、SP結構等。隨著分組密碼設計與分析的發展，關于整體結構設計的研究越來越精細化，比如Feistel-SP組合結構、ARX結構，以及近幾年基于邏輯門設計的電路結構等［1～3］，其中基于Feistel結構的算法加密和解密過程基本相同，這樣大大減少了算法實現需要的電路面積，非常適用于資源受限環境。它的推廣形式稱為廣義Feistel網絡（generalized feistel network，GFN），采用更多的分支和不同的分支之間的操作進行設計。在1989年美密會上，Zheng等人［4］將廣義Feistel網絡總結為三種，即Type-1、Type-2和Type-3型。廣義Feistel結構可以利用更簡單的輪函數來設計大狀態分組的密碼算法，這對于輕量級密碼算法的設計大有裨益。基于廣義Feistel網絡設計的輕量級分組密碼有LBlock［5］、TWINE［6］、CLEFIA［7］等。

伴隨輕量級分組密碼算法的不斷提出和改進，安全性分析和證明也有了豐富的成果［8～10］。混合整數線性規劃（mixed integer linear programming，MILP）是一種在決策分析、優化問題等領域內廣泛應用的數學模型和算法，它將線性規劃與整數規劃相結合應用于多種決策分析和優化問題，同時MILP已是密碼領域中引領密碼分析的一種有效方法，被廣泛應用到了差分分析、線性分析、積分攻擊［11］、立方攻擊［12］、飛來去器攻擊［13］、中間相遇攻擊［14］等密碼分析方法中，給出諸如GIFT［15，16］、SIMON［17，18］、LED［19］、Midori［20］等大量輕量級分組密碼算法的新的分析結果。為了確定密碼算法抵抗差分分析的能力，密碼分析者需要推導或者測試密碼算法中差分活躍S盒個數的下界，以獲取高概率差分特征。2011年，Mouha等人［21］將計算差分活躍S盒個數下界轉換為了MILP問題，并進行了不可能差分特征和線性特征的搜索。2014年，Sun等人［22］利用數學凸包問題，結合應用SageMath數學工具，實現了對S盒的精確不等式刻畫，完善了MILP分析模型關于S盒的建模過程，給出了基于比特運算的密碼算法的差分特征搜索工具，使得MILP推廣應用到了線性層基于比特變換的SPN結構密碼算法。2016年，Fu等人［23］提出了一種基于MILP的針對模加操作的建模方法，不再將模加操作視為分塊S盒進行建模。2019年，Elsheikh等人［24］改進了Fu等人提出的模加操作建模方法，考慮了模加操作之間的關系，使得MILP工具更廣泛地應用到了ARX型結構密碼的自動化分析。對于大規模S盒的差分建模，Abdelkhalek等人［25］在2017年提出了一種描述8 bit密碼S盒的差分特征的方法，并應用此方法完成了對SKINNY-128的高概率差分特征搜索；2019年，Li等人［26］提出了一種新的從小狀態S盒建模延伸到大狀態S盒完成MILP建模的方法。同年，Zhou等人［27］基于分治法將全部差分特征構成的集合分割成了多個小的子集，通過在子集中搜索最優的差分軌跡，提高了差分特征的搜索效率。

MGFN算法是2023年Mohammad等人［28］提出來的基于改進GFN結構設計的一個輕量級分組密碼算法，輪函數F包含非線性部件S盒和線性部件比特置換，其中比特置換包含循環移位和比特拉線，類似的輕量級分組密碼算法有PFP［29］、SLIM［30］等。如果S盒實現占用的電路面積足夠小，那么該結構的算法通常比較節約資源，因為比特置換幾乎不占用電路資源。缺點是安全性分析目前還沒有可證明理論，只能結合算法特點進行建模和搜索，若設計不好很容易造成安全隱患。

本文研究了MGFN算法的抗差分分析能力，基于MILP工具對該算法進行了建模，搜索得到6輪迭代差分，活躍S盒只有4個，差分概率為2－10。基于這樣的迭代差分構造了全輪差分路徑，總概率為2－40，遠遠小于隨機置換的差分概率，由此證明了MGFN不能抵抗差分分析。進一步，對S盒討論了分支數，用來衡量其差分安全性能，并以PRESENT算法的S盒為例進行替代盒測試，提出新的MGFN-P算法，使其抵抗差分分析的能力得到了加強。

1 MGFN算法

MGFN算法的明文分組長度64 bit，密鑰長度128 bit，基于改進的GFN結構設計，迭代24輪后輸出密文。

1.1 加密變換

將64 bit明文分成4個16 bit字（X0，0，X0，1，X0，2，X0，3），經過24輪GFN結構進行變換，輸出64 bit密文（X24，0，X24，1，X24，2，X24，3）。對于0≤i≤23，第i輪的輪函數輸入記為（Xi，0，Xi，1，Xi，2，Xi，3），輸出記為（Xi+1，0，Xi+1，1，Xi+1，2，Xi+1，3），加密輪結構如圖1所示。

在第i輪的輪結構中，F函數輸入為32 bit（Xi，0，Xi，1），輸出為32 bit（Yi，0，Yi，1），如圖2所示。

一方面，從理論角度進行安全性比較。對于11輪MGFN算法，得到差分活躍S盒個數為7個，對應輸入輸出差分概率為2－18，全部24輪的差分概率理論估計為2－42，遠遠高于隨機置換的概率；迭代36輪的差分概率理論估計為2－63，所以安全輪數至少大于36輪。對于11輪MGFN-P算法，得到差分活躍S盒個數為11個，對應輸入輸出差分概率為2－34，全部24輪的差分概率最小理論估計為2－72，遠遠低于隨機置換的概率。由此可見，理論上改進后的算法MGFN-P在抵抗差分分析方面更為安全。

另一方面，進行實際迭代差分搜索。如3.2節所示，MGFN算法存在全輪差分路徑，差分概率為2－40，無法抵抗差分分析。對于替換S盒之后的MGFN-P算法，搜索得到4輪迭代差分路徑，活躍S盒個數為4個，最大差分特征概率為2－10， 24輪的差分特征概率為2－60，如圖6所示，雖然大于隨機置換的概率，但明顯低于替換S盒之前MGFN算法的差分概率2－40。由此可見，相同輪數下使用分支數大的S盒在相同輪數會得到更多的活躍S盒，相應的差分路徑概率更小。

綜上所述，28輪MGFN-P算法的最大差分特征概率為2－70，遠遠小于隨機置換的差分概率。MGFN-P的密鑰擴展算法的全擴散輪數為4，那么28輪前后各加4輪安全冗余以防止密鑰恢復攻擊，整體36輪能保證MGFN-P算法具有抵抗差分分析的能力。

由于S盒分支數影響了密碼算法抵抗差分分析的能力，所以對改進后算法與原算法進行如表6所示的比較。表中Min-S/R表示每輪平均最少活躍S盒個數，具體數值由表5中大于6輪之后的活躍S盒個數計算得到。Sec-R表示根據迭代差分搜索得到的最少安全輪數，例如對于MGFN-P算法，4輪迭代差分概率為2－10，則26輪約為2－65，小于隨機置換差分概率，所以對應的Sec-R值為26；同理可得MGFN算法對應的Sec-R值為36+3=39。WR表示算法整體設計的輪數，容易看出MGFN算法遠遠沒有達到安全輪數，而MGFN-P算法存在8輪安全冗余。所以MGFN-P算法比原算法更安全、更有效。

5 結束語

本文對MGFN算法進行了差分建模，并基于MILP工具搜索得到6輪迭代差分，概率為2－10，基于這樣的迭代差分構造了全輪差分，對應差分概率為2－40，遠遠小于隨機置換的差分概率，證明了MGFN不能夠抵抗差分分析。進一步，使用分支數較大的PRESENT算法S盒為例進行替代，改進了MGFN算法，使其抗差分分析能力得到了加強。

針對基于比特設計的SP結構分組密碼算法，S盒的分支數可以有效衡量活躍S盒個數，進而進行分組密碼的抗差分分析安全性證明。然而，對于基于Feistel結構的分組密碼設計，由于存在差分異或抵消，目前常用的方法還是基于MILP等數學工具進行搜索，這種搜索方法隨著分組長度或者S盒規模的增加，效率會大大降低。因此，如何評估Feistel結構的活躍S盒個數下界，并給出相關安全性證明仍然是筆者下一步研究的主要方向。

參考文獻：

［1］張文濤，卿斯漢，吳文玲. 嵌套 Feistel 結構的 SP 型分組密碼的可證明安全性 ［J］. 計算機研究與發展，2004，41（8）： 1389-1397.（Zhang Wentao，Qin Sihan，Wu Wenling. Provable security for SPN block ciphers containing Feistel structure ［J］ Journal of Computer Research and Development，2004，41（8）： 1389-1397.）

［2］Wheeler D J，Needham R M. TEA，a tiny encryption algorithm ［C］// Proc of International Conference on Fast Software Encryption. Berlin： Springer，1995： 363-366.

［3］Tiri K，Akmal M，Verbauwhede I. A dynamic and differential CMOS logic with signal independent power consumption to withstand differential power analysis on smart cards ［C］// Proc of the 28th European Solid-State Circuits Conference. Piscataway，NJ： IEEE Press，2002： 403-406.

［4］Zheng Yuliang，Matsumoto T，Imai H. On the construction of block ciphers provably secure and not relying on any unproved hypotheses ［C］// Advances in Cryptology. Berlin： Springer，1989： 461-480.

［5］Wu Wenling，Zhang Lei. LBlock： a lightweight block cipher ［C］// Proc of International Conference on Applied Cryptography and Network Security. Berlin： Springer，2011： 327-344.

［6］Suzaki T，Minematsu K，Morioka S，et al. TWINE： a lightweight，versatile block cipher ［C］// Proc of ECRYPT Workshop on Lightweight Cryptography. 2011.

［7］Shirai T，Shibutani K，Akishita T，et al. The 128-bit block cipher CLEFIA ［C］// Proc of International Conference on Fast Software Encryption. Berlin： Springer，2007： 181-195.

［8］Zhang Lei，Wu Wenling，Mao Yongxia. Impossible differential cryptanalysis on reduced-round PRINCE ［C］// Proc of International Conference on Information Security and Cryptology. Berlin： Springer，2022： 61-77.

［9］Zheng Yafei，Wu Wenling. Security of Khudra against meet-in-the-middle-type cryptanalysis［J］. Chinese Journal of Electronics，2019，28（3）： 482-488.

［10］劉亞，唐偉明，沈致遠，等.輕量級分組密碼Pyjamask的不可能差分分析 ［J］. 計算機應用研究，2021，38（11）：3428-3432.（Liu Ya，Tang Weiming，Shen Zhiyuan，et al. Impossible differential cryptanalysis of lightweight block cipher Pyjamask ［J］. Application Research of Computers，2021，38（11） ：3428-3432.）

［11］Xiang Zejun，Zhang Wentao，Bao Zhenzhen，et al. Applying MILP method to searching integral distinguishers based on division property for 6 lightweight block ciphers ［C］// Advances in Cryptology-ASIACRYPT. Berlin： Springer，2016： 648-678.

［12］Li Zheng，Bi Wenquan，Dong Xiaoyang，et al. Improved conditional cube attacks on Keccak keyed modes with MILP method ［C］// Advances in Cryptology. Berlin： Springer，2017： 99-127.

［13］Cid C，Huang T，Peyrin T，et al. A security analysis of Deoxys and its internal tweakable block ciphers［J］. IACR Trans on Symmetric Cryptology，2017，2017（3）： 73-107.

［14］Shi Danping，Sun Siwei，Derbez P，et al. Programming the Demirci-Sel?uk meet-in-the-middle attack with constraints ［C］// Advances in Cryptology. Berlin： Springer，2018： 3-34.

［15］Zhu Baoyu，Dong Xiaoyang，Yu Hongbo. MILP-based differential attack on round-reduced GIFT ［C］// Proc of International Conference on Topics in Cryptology. Berlin： Springer，2019： 372-390.

［16］Cui Yaxin，Xu Hong，Tan Lin. Improved related-key rectangle attack on GIFT ［C］// Proc of the 7th International Conference on Computer and Communication Systems. Piscataway，NJ： IEEE Press，2022： 403-409.

［17］Wang Xuzi，Wu Baofeng，Hou Lin，et al. Automatic search for related-key differential trails in SIMON-like block ciphers based on MILP ［C］//Proc of International Conference on Information Security. Berlin： Springer，2018： 116-131.

［18］Zhang Yingjie，Lyu Lijun，Qiao Kexin，et al. Automatic key recovery of Feistel ciphers： application to SIMON and SIMECK ［C］// Proc of the 16th International Conference on Information Security Practice and Experience. Berlin： Springer，2021： 147-167.

［19］劉波濤，彭長根，吳睿雪，等.基于MILP方法的LED密碼安全性分析［J］. 計算機應用研究，2020，37（2）：505-509，517. （Liu Botao，Peng Changgen，Wu Ruixue，et al. Based on MILP method for security analysis of LED［J］. Application Research of Computers，2020，37（2） ：505-509，517.）

［20］Zhao Hongluan，Han Guoyong，Wang Letian，et al. MILP-based diffe-rential cryptanalysis on round-reduced Midori64［J］. IEEE Access，2020，8： 95888-95896.

［21］Mouha N，Wang Qingju，Gu Dawu，et al. Differential and linear cryptanalysis using mixed-integer linear programming ［C］// Proc of? International Conference on Information Security and Cryptology. Berlin： Springer， 2012： 57-76.

［22］Sun Siwei，Hu Lei，Wang Peng，et al. Automatic security evaluation and （related-key） differential characteristic search： application to SIMON，PRESENT，LBlock，DES （L） and other bit-oriented block ciphers［C］// Advances in Cryptology.Berlin：Springer，2014：158-178.

［23］Fu Kai，Wang Meiqin，Guo Yinghua，et al. MILP-based automatic search algorithms for differential and linear trails for speck ［C］// Proc of? International Conference on Fast Software Encryption. Berlin： Springer， 2016： 268-288.

［24］ElSheikh M，Abdelkhalek A，Youssef A M. On MILP-based automatic search for differential trails through modular additions with application to Bel-T ［C］// Proc of International Conference on Cryptology in Africa. Berlin： Springer，2019： 273-296.

［25］Abdelkhalek A，Sasaki Y，Todo Y，et al. MILP modeling for （large） S-boxes to optimize probability of differential characteristics［J］. IACR Trans on Symmetric Cryptology，2017，2017（4）： 99-129.

［26］Li Linchen，Wu Wenling，Zhang Lei，et al. New method to describe the differential distribution table for large S-boxes in MILP and its application［J］. IET Information Security，2019，13（5）： 479-485.

［27］Zhou Chunning，Zhang Wentao，Ding Tianyou，et al. Improving the MILP-based security evaluation algorithm against differential/linear cryptanalysis using a divide-and-conquer approach［EB/OL］. （2019）. https：//eprint.iacr.org/2019/019.

［28］Mohammad S I N，Ismail E S，Samat F，et al. Modified generalized Feistel network block cipher for the Internet of Things［J］. Symmetry，2023，15（4）： 900.

［29］黃玉劃，代學俊，時陽陽，等.基于Feistel結構的超輕量級分組密碼算法［J］.計算機科學，2017，44（3）： 163-168. （Huang Yuhua，Dai Xuejun，Shi Yangyang，et al. Ultra-light weight block cipher algorithm （PFP） based on Feistel structure［J］. Computer Science，2017，44（3）：163-168.）

［30］Aboushosha B，Ramadan R A，Dwivedi A D，et al. SLIM： a lightweight block cipher for Internet of health things［J］. IEEE Access，2020，8： 203747-203757.