基于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.