Differential Attack on Lightweight PFP Algorithm

doi:10.3778/j.issn.1002-8331.2305-0193

Abstract

Abstract: The PFP algorithm is a lightweight block cipher algorithm proposed in 2017 based on the design idea of the international standard PRESENT algorithm, designed based on the Feistel-SP structure with bit substitution, which has higher efficiency of hardware and software implementation compared to the PRESENT algorithm. In order to perform a new evaluation of the ability of algorithm to resist differential analysis, the S-box and the overall structure are first modeled based on the mixed integer linear programming（MILP） method, and a 4-round iterative differential path with probability 2?11 is searched for the PFP algorithm, and a 22-round differential distinguisher with probability 2?59 is constructed; further, 2 rounds are added before and after the distinguisher to obtain 26 rounds, and by studying the characteristics of the added 4-round key arrangement, the guessing sequence of the key bits is optimized, and at the same time, the 26-round key recovery of the PFP algorithm is performed for the first time by using the early abort technique. The data complexity required for the whole differential attack process is 260 plaintexts, and the time complexity is 254.3 times 26 rounds of encryption, which still has sufficient security redundancy compared with the overall 34-round PFP algorithm.

Key words: block cipher, differential attack, key recovery attack, early abort technique

摘要： PFP算法借鉴国际标准PRESENT算法的设计思想，在2017年提出的一种轻量级分组密码算法，基于Feistel-SP结构设计，采用比特置换，相比PRESENT算法有着更高的软硬件实现效率。为了对该算法的抗差分分析的能力进行新的评估，基于混合整数线性规划（MILP）方法对S盒和整体结构进行建模，针对PFP算法搜索到了概率为2?11的4轮迭代差分路径，构造了概率为2?59的22轮差分区分器；进一步，在区分器前后各增加2轮，得到26轮，通过研究增加的4轮轮密钥编排特点，对密钥比特的猜测顺序进行了优化，同时采用提前抛弃技术，首次对PFP算法进行了26轮的密钥恢复。整个差分攻击过程需要的数据复杂度为260个明文，时间复杂度为254.3次26轮加密，与整体34轮PFP算法相比，仍然具有足够的安全冗余。

关键词: 分组密码, 差分攻击, 密钥恢复攻击, 提前抛弃技术

LI Yanjun, LI Yinshuang, YANG Minghua, ZHANG Lixian, LIU Jian. Differential Attack on Lightweight PFP Algorithm[J]. Computer Engineering and Applications, 2023, 59(21): 296-302.

李艳俊, 李寅霜, 杨明华, 张黎仙, 刘健. 轻量级PFP算法的差分攻击[J]. 计算机工程与应用, 2023, 59(21): 296-302.

References

[1] 梁广俊，辛建芳，王群，等.物联网取证综述[J].计算机工程与应用，2022，58（8）：12-32.
LIANG G J，XIN J F，WANG Q，et al.Survey of IoT forensics[J].Computer Engineering and Applications，2022，58（8）：12-32.
[2] DOBRAUNIG C，EICHLSEDER M，MENDEL F，et al.Ascon v1.2：lightweight authenticated encryption and hashing[J].Journal of Cryptology，2021，34：1-42.
[3] WU W，ZHANG L.LBlock：a lightweight block cipher[C]//9th International Conference on Applied Cryptography and Network Security，Nerja，Spain，June 7-10，2011：327-344.
[4] BOGDANOV A，KNUDSEN L R，LEANDER G，et al.PRESENT：an ultra-lightweight block cipher[C]//9th International Workshop on Cryptographic Hardware and Embedded Systems，Vienna，Austria，September 10-13，2007：450-466.
[5] BANIK S，BOGDANOV A，ISOBE T，et al.Midori：a block cipher for low energy[C]//21st International Conference on the Theory and Application of Cryptology and Information Security，Auckland，New Zealand，November 29-December 3，2015：411-436.
[6] GUO J，PEYRIN T，POSCHMANN A，et al.The LED block cipher[C]//13th International Workshop on Cryptographic Hardware and Embedded Systems，Nara，Japan，September 28-October 1，2011：326-341.
[7] GERARD B，GROSSO V，NAYA-PLASENCIA M，et al.Block ciphers that are easier to mask：how far can we go?[C]//15th International Workshop on Cryptographic Hardware and Embedded Systems，Santa Barbara，CA，USA，August 20-23，2013：383-399.
[8] 黄玉划，代学俊，时阳阳，等.基于Feistel结构的超轻量级分组密码算法（PFP）[J].计算机科学，2017，44（3）：163-167.
HUANG Y H，DAI X J，SHI Y Y，et al.Ultra-lightweight block cipher algorithm（PFP） based on feistel structure[J].Computer Science，2017，44（3）：163-167.
[9] BEYNE T，RIJMEN V.Differential cryptanalysis in the fixed-key model[C]//42nd Annual International Cryptology Conference，Santa Barbara，CA，USA，August 15-18，2022：687-716.
[10] 沈璇，王欣玫，何俊，等.Robin算法改进的6轮不可能差分攻击[J].计算机工程与应用，2021，57（5）：95-99.
SHEN X，WANG X M，HE J，et al.Revised impossible differential attack on reduced 6-round robin[J].Computer Engineering and Applications，2021，57（5）：95-99.
[11] 王建华，怀进鹏.多重线性密码分析中线性逼近方程的构造[J].计算机工程与应用，2007，43（8）：118-120.
WANG J H，HUAI J P.Construction of linear approximation equations in multiple linear cryptanalysis[J].Computer Engineering and Applications，2007，43（8）：118-120.
[12] BIHAM E，SHAMIR A.Differential cryptanalysis of DES-like cryptosystems[J].Journal of Cryptology，1991，4（1）：3-72.
[13] SUN S W，HU L，WANG P，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]//International Conference on the Theory and Application of Cryptology and Information Security，Taiwan，China，2014：158-178.
[14] SUN S W，HU L，WANG M Q，et al.Towards finding the best characteristics of some bit-oriented block ciphers and automatic enumeration of（related-key） differential and linear characteristics with predefined properties[J].Cryptology ePrint Archive，2014：747.
[15] 沈璇，王欣玫，何俊，等.PFP算法改进的不可能差分分析[J].计算机科学，2020，47（7）：263-267.
SHEN X，WANG X M，HE J，et al.Revised impossible differential cryptanalysis of PFP block cipher[J].Computer Science，2020，47（7）：263-267.
[16] 黄思佳，欧海文，孙启龙.基于MILP模型的PFP算法的不可能差分分析[J].北京电子科技学院学报，2022，30（3）：64-70.
HUANG S J，OU H W，SUN Q L.Impossible differential analysis of PFP algorithm based on MILP model[J].Journal of Beijing Electronic Science and Technology Institute，2022，30（3）：64-70.