Related-key Differential Cryptanalysis of Full-round PFP Ultra-lightweight Block Cipher

YAN Zhiguang; WEI Yongzhuang; YE Tao

doi:10.11999/JEIT240782

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2025 >

YAN Zhiguang, WEI Yongzhuang, YE Tao. Related-key Differential Cryptanalysis of Full-round PFP Ultra-lightweight Block Cipher[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT240782

Citation:

YAN Zhiguang, WEI Yongzhuang, YE Tao. Related-key Differential Cryptanalysis of Full-round PFP Ultra-lightweight Block Cipher[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT240782

Citation:

PDF( 0 KB)

Related-key Differential Cryptanalysis of Full-round PFP Ultra-lightweight Block Cipher

doi: 10.11999/JEIT240782

Guangxi Key Laboratory of Cryptography and information Security, Guilin University of Electronic Technology, Guilin 541004, China

Funds: The National Natural Science Foundation of China (62162016, 62402132)

Received Date: 2024-09-11
Rev Recd Date: 2025-01-07

Available Online: 2025-01-11

Abstract

Abstract

Objective In 2017, the PFP algorithm was introduced as an ultra-lightweight block cipher to address the demand for efficient cryptographic solutions in constrained environments, such as the Internet of Things (IoT). With a hardware footprint of approximately 1355 GE and low power consumption, PFP has attracted attention for its ability to deliver high-speed encryption with minimal resource usage. Its encryption and decryption speeds outperform those of the internationally recognized PRESENT cipher by a factor of 1.5, making it highly suitable for real-time applications in embedded systems. While the original design documentation asserts that PFP resists various traditional cryptographic attacks, including differential, linear, and impossible differential attacks, the possibility of undiscovered vulnerabilities remains unexplored. This study evaluates the algorithm’s resistance to related-key differential attacks, a critical cryptanalysis method for lightweight ciphers, to determine the actual security level of the PFP algorithm using formal cryptanalysis techniques. Methods To evaluate the security of the PFP algorithm, Satisfiability Modulo Theories (SMT) is used to model the cipher’s round function and automate the search for distinguishers indicating potential design weaknesses. SMT, a formal method increasingly applied in cryptanalysis, facilitates automated attack generation and the detection of cryptographic flaws. The methodology involved constructing mathematical models of the cipher’s rounds, which are tested for differential characteristics under various key assumptions. Two distinguisher models are developed: one based on single-key differentials and the other on related-key differentials, the latter being the focus of this analysis. These models automated the search for weak key differentials that could enable efficient key recovery attacks. The analysis leveraged the nonlinear substitution-permutation structure of the PFP round function to systematically identify vulnerabilities. The results are examined to estimate the probability of key recovery under different attack scenarios and assess the effectiveness of related-key differential cryptanalysis against the full-round PFP cipher. Results and Discussions The SMT-based analysis revealed a critical vulnerability in the PFP algorithm. A related-key differential characteristic with a probability of 2^-62 is identified, persisting through 32 encryption rounds. This characteristic indicates a predictable pattern in the cipher’s behavior under related-key conditions, which can be exploited to recover the secret key. Such differentials are particularly concerning as they expose a significant weakness in the cipher’s resistance to related-key attacks, a critical threat in IoT applications where keys may be reused or related across multiple devices or sessions.Based on this finding, a key recovery attack is developed, requiring only 2⁶³ chosen plaintexts and 2⁴⁸ full-round encryptions to retrieve the 80-bit master key. The efficiency of this attack demonstrates the vulnerability of the PFP cipher to practical cryptanalysis, even with limited computational resources. The attack’s relatively low complexity suggests that PFP may be unsuitable for applications demanding high security, particularly in environments where adversaries can exploit related-key differential characteristics. Moreover, these results indicate that the existing resistance claims for the PFP cipher are insufficient, as they do not account for the effectiveness of related-key differential cryptanalysis. This challenges the assertion that the PFP algorithm is secure against all known cryptographic attacks, emphasizing the need for thorough cryptanalysis before lightweight ciphers are deployed in real-world scenarios.(Fig. 1: Related-key differential characteristic with probability 2^-62 in 32 rounds; Table 1: Attack complexity and resource requirements for related-key recovery.) Conclusions In conclusion, this paper presents a cryptographic analysis of the PFP lightweight block cipher, revealing its vulnerability to related-key differential attacks. The proposed key recovery attack demonstrates that, despite its efficiency in hardware and speed, PFP fails to resist attacks exploiting related-key differential characteristics. This weakness is particularly concerning for IoT applications, where key reuse or related keys across devices is common. These findings highlight the need for further refinement in lightweight cipher design to ensure robust resistance against advanced cryptanalysis techniques. As lightweight ciphers continue to be deployed in security-critical systems, it is essential that designers consider all potential attack vectors, including related-key differentials, to strengthen security guarantees. Future work should focus on enhancing the cipher’s security by exploring alternative key-schedule designs or increasing the number of rounds to mitigate the identified vulnerabilities. Additionally, this study emphasizes the effectiveness of SMT-based formal methods in cryptographic analysis, providing a systematic approach for identifying previously overlooked weaknesses in cipher designs.
- Lightweight block cipher algorithm,
- Differential cryptanalysis,
- Key recovery attack,
- Satisfiability Modulo Theories (SMT)

FullText(HTML)

References(30)

References

[1]	National Institute of Standards and Technology, DWORKIN M J, BARKER E, et al. Advanced encryption standard[R]. 197, 2001. doi: 10.6028/NIST.FIPS.197.
[2]	WU Wenling and ZHANG Lei. LBlock: A lightweight block cipher[C]. Proceedings of the 9th International Conference on Applied Cryptography and Network Security, Nerja, Spain, 2011: 327–344. doi: 10.1007/978-3-642-21554-4_19.
[3]	GUO Jian, PEYRIN T, POSCHMANN A, et al. The LED block cipher[C]. Proceedings of the 13th International Workshop on Cryptographic Hardware and Embedded Systems, Nara, Japan, 2011: 326–341. doi: 10.1007/978-3-642-23951-9_22.
[4]	BANIK S, PANDEY S K, PEYRIN T, et al. GIFT: A small present: Towards reaching the limit of lightweight encryption[C]. Proceedings of the 19th International Conference on Cryptographic Hardware and Embedded Systems, Taipei, China, 2017: 321–345. doi: 10.1007/978-3-319-66787-4_16.
[5]	BEAULIEU R, TREATMAN-CLARK S, SHORS D, et al. The SIMON and SPECK lightweight block ciphers[C]. Proceedings of the 52nd ACM/EDAC/IEEE Design Automation Conference, San Francisco, USA, 2015: 1–6. doi: 10.1145/2744769.2747946.
[6]	BOGDANOV A, KNUDSEN L R, LEANDER G, et al. PRESENT: An ultra-lightweight block cipher[C]. Proceedings of the 9th International Workshop, Vienna, Austria, 2007: 450–466. doi: 10.1007/978-3-540-74735-2_31.
[7]	黄玉划, 代学俊, 时阳阳, 等. 基于Feistel结构的超轻量级分组密码算法(PFP)[J]. 计算机科学, 2017, 44(3): 163–167. doi: 10.11896/j.issn.1002-137X.2017.03.036. HUANG Yuhua, DAI Xuejun, SHI Yangyang, et al. Ultra-lightweight block cipher algorithm (PFP) based on Feistel structure[J]. Computer Science, 2017, 44(3): 163–167. doi: 10.11896/j.issn.1002-137X.2017.03.036.
[8]	BIHAM E and SHAMIR A. Differential cryptanalysis of DES-like cryptosystems[J]. Journal of Cryptology, 1991, 4(1): 3–72. doi: 10.1007/BF00630563.
[9]	MATSUI M. Linear cryptanalysis method for DES cipher[C]. Proceedings of the Workshop on the Theory and Application of Cryptographic Techniques on Advances in Cryptology (EUROCRYPT'93), Lofthus, Norway, 1993: 386–397. doi: 10.1007/3-540-48285-7_33.
[10]	HADIPOUR H, SADEGHI S and EICHLSEDER M. Finding the impossible: Automated search for full impossible-differential, zero-correlation, and integral attacks[C]. Proceedings of the 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology (EUROCRYPT 2023), Lyon, France, 2023: 128–157. doi: 10.1007/978-3-031-30634-1_5.
[11]	HADIPOUR H, GERHALTER S, SADEGHI S, et al. Improved search for integral, impossible differential and zero-correlation attacks[J]. IACR Transactions on Symmetric Cryptology, 2024, 2024(1): 234–325. doi: 10.46586/tosc.v2024.i1.234-325.
[12]	LAI Xuejia. Higher order derivatives and differential cryptanalysis[M]. BLAHUT R E, COSTELLO D J, MAURER U, et al. Communications and Cryptography: Two Sides of One Tapestry. Boston: Springer, 1994: 227–233. doi: 10.1007/978-1-4615-2694-0_23.
[13]	AHMADIAN Z, KHALESI A, M’FOUKH D, et al. Truncated differential cryptanalysis: New insights and application to QARMAv1-n and QARMAv2–64[J]. Designs, Codes and Cryptography, 2024, 92(12): 4549–4591. doi: 10.1007/s10623-024-01486-8.
[14]	BIHAM E. New types of cryptanalytic attacks using related keys[J]. Journal of Cryptology, 1994, 7(4): 229–246. doi: 10.1007/BF00203965.
[15]	ROHIT R and SARKAR S. Reconstructing s-boxes from cryptographic tables with MILP[J]. IACR Transactions on Symmetric Cryptology, 2024, 2024(3): 200–237. doi: 10.46586/tosc.v2024.i3.200-237.
[16]	CHAKRABORTY D, HADIPOUR H, NGUYEN P H, et al. Finding complete impossible differential attacks on AndRX ciphers and efficient distinguishers for ARX designs[J]. IACR Transactions on Symmetric Cryptology, 2024, 2024(3): 84–176. doi: 10.46586/tosc.v2024.i3.84-176.
[17]	WANG Dachao, WANG Baocang, and SUN Siwei. SAT-aided automatic search of boomerang distinguishers for ARX ciphers[J]. IACR Transactions on Symmetric Cryptology, 2023, 2023(1): 152–191. doi: 10.46586/tosc.v2023.i1.152-191.
[18]	ERLACHER J, MENDEL F, and EICHLSEDER M. Bounds for the security of ascon against differential and linear cryptanalysis[J]. IACR Transactions on Symmetric Cryptology, 2022, 2022(1): 64–87. doi: 10.46586/tosc.v2022.i1.64-87.
[19]	沈璇, 王欣玫, 何俊, 等. PFP算法改进的不可能差分分析[J]. 计算机科学, 2020, 47(7): 263–267. doi: 10.11896/jsjkx.200200034. SHEN Xuan, WANG Xinmei, HE Jun, et al. Revised impossible differential cryptanalysis of PFP block cipher[J]. Computer Science, 2020, 47(7): 263–267. doi: 10.11896/jsjkx.200200034.
[20]	赵光耀, 沈璇, 余波, 等. 缩减轮的超轻量级分组密码算法PFP的不可能差分分析[J]. 计算机应用, 2023, 43(9): 2784–2788. doi: 10.11772/j.issn.1001-9081.2022091395. ZHAO Guangyao, SHEN Xuan, YU Bo, et al. Impossible differential cryptanalysis of reduced-round ultra-lightweight block cipher PFP[J]. Journal of Computer Applications, 2023, 43(9): 2784–2788. doi: 10.11772/j.issn.1001-9081.2022091395.
[21]	刘道瞳, 袁征, 魏锦鹏, 等. 轻量级分组密码算法PFP和SLIM的积分分析[J]. 密码学报, 2023, 10(3): 609–621. doi: 10.13868/j.cnki.jcr.000617. LIU Daotong, YUAN Zheng, WEI Jinpeng, et al. Integral cryptanalysis of lightweight block cipher PFP and SLIM[J]. Journal of Cryptologic Research, 2023, 10(3): 609–621. doi: 10.13868/j.cnki.jcr.000617.
[22]	李艳俊, 李寅霜, 杨明华, 等. 轻量级PFP算法的差分攻击[J]. 计算机工程与应用, 2023, 59(21): 296–302. doi: 10.3778/j.issn.1002-8331.2305-0193. LI Yanjun, LI Yinshuang, YANG Minghua, et al. Differential attack on lightweight PFP algorithm[J]. Computer Engineering and Applications, 2023, 59(21): 296–302. doi: 10.3778/j.issn.1002-8331.2305-0193.
[23]	COOK S A. The complexity of theorem-proving procedures[C]. Proceedings of the Third Annual ACM Symposium on Theory of Computing (STOC '71), Shaker Heights, USA, 1971: 151–158. doi: 10.1145/800157.805047.
[24]	DE MOURA L and BJØRNER N. Z3: An efficient SMT solver[C]. Proceedings of the 14th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2008), Budapest, Hungary, 2008: 337–340. doi: 10.1007/978-3-540-78800-3_24.
[25]	BARRETT C, CONWAY C L, DETERS M, et al. CVC4[C]. Proceedings of the 23rd International Conference on Computer aided verification (CAV 2011), Snowbird, USA, 2011: 171–177.
[26]	CIMATTI A, GRIGGIO A, SCHAAFSMA B J, et al. The MathSAT5 SMT solver[C]. Proceedings of the 19th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2013), Rome, Italy, 2013: 93–107. doi: 10.1007/978-3-642-36742-7_7.
[27]	BRUMMAYER R and BIERE A. Boolector: An efficient SMT solver for bit-vectors and arrays[C]. Proceedings of the 15th International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS 2009), York, UK, 2009: 174–177. doi: 10.1007/978-3-642-00768-2_16.
[28]	GANESH V and DILL D L. A decision procedure for bit-vectors and arrays[C]. Proceedings of the 19th International Conference on Computer Aided Verification (CAV 2007), Berlin, Germany, 2007: 519–531. doi: 10.1007/978-3-540-73368-3_52.
[29]	STUMP A, BARRETT C W, and DILL D L. CVC: A cooperating validity checker[C]. Proceedings of the 14th International Conference on Computer Aided Verification (CAV 2002), Copenhagen, Denmark, 2002: 500–504. doi: 10.1007/3-540-45657-0_40.
[30]	SELÇUK A A. On probability of success in linear and differential cryptanalysis[J]. Journal of Cryptology, 2008, 21(1): 131–147. doi: 10.1007/s00145-007-9013-7.