PRIDE轻量级密码的不可能统计故障分析

doi:10.11959/j.issn.1000-436x.2024019

通信学报 ›› 2024, Vol. 45 ›› Issue (1): 141-151.doi: 10.11959/j.issn.1000-436x.2024019

• 学术论文 • 上一篇

PRIDE轻量级密码的不可能统计故障分析

李玮¹^,²^,³^,⁴, 孙文倩¹, 谷大武², 张爱琳¹, 温云华¹

¹ 东华大学计算机科学与技术学院，上海 201620
² 上海交通大学计算机科学与工程系，上海 200240
³ 上海市可扩展计算与系统重点实验室，上海 200240
⁴ 上海市信息安全综合管理技术研究重点实验室，上海 200240

修回日期:2023-12-08 出版日期:2024-01-01 发布日期:2024-01-01
作者简介:李玮（1980- ），女，安徽寿县人，博士，东华大学教授、博士生导师，主要研究方向为对称密码的设计与分析
孙文倩（2000- ），女，安徽铜陵人，东华大学硕士生，主要研究方向为对称密码的故障分析
谷大武（1970- ），男，河南漯河人，博士，上海交通大学教授、博士生导师，主要研究方向为密码学和计算机安全
张爱琳（2001- ），女，吉林四平人，东华大学硕士生，主要研究方向为轻量级分组密码的故障分析
温云华（1990- ），女，山东临清人，博士，东华大学讲师、硕士生导师，主要研究方向为密码学
基金资助:
国家自然科学基金资助项目(61772129);国家自然科学基金资助项目(62172395);国家自然科学基金资助项目(62102077);国家密码发展基金资助项目(MMJJ20180101);信息安全国家重点实验室开放课题基金资助项目(2021-MS-05);上海市扬帆计划基金资助项目(21YF1401200);上海市扬帆计划基金资助项目(23YF1401000);中央高校基本科研业务费专项资金资助项目(223202D-25)

Impossible statistical fault analysis of the PRIDE lightweight cryptosystem

Wei LI¹^,²^,³^,⁴, Wenqian SUN¹, Dawu GU², Ailin ZHANG¹, Yunhua WEN¹

¹ School of Computer Science and Technology, Donghua University, Shanghai 201620, China
² Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai 200240, China
³ Shanghai Key Laboratory of Scalable Computing and System, Shanghai 200240, China
⁴ Shanghai Key Laboratory of Integrate Administration Technologies for Information Security, Shanghai 200240, China

Revised:2023-12-08 Online:2024-01-01 Published:2024-01-01
Supported by:
The National Natural Science Foundation of China(61772129);The National Natural Science Foundation of China(62172395);The National Natural Science Foundation of China(62102077);The National Cryptography Development Fund(MMJJ20180101);State Key Laboratory of Information Security(2021-MS-05);Shanghai Sailing Plan(21YF1401200);Shanghai Sailing Plan(23YF1401000);The Fundamental Research Funds for the Central Universities(223202D-25)

摘要/Abstract

摘要：

针对2014年美密会上提出的PRIDE轻量级密码的实现安全，提出了面向唯密文攻击假设的新型不可能统计故障分析方法，设计了卡方拟合优度-汉明重量区分器、卡方拟合优度-极大似然估计区分器等新型区分器。所提方法基于随机半字节故障模型，结合统计分布状态和不可能关系分析，围绕导入故障前后中间状态的变化，最少仅需432个故障即可恢复出PRIDE算法的128 bit原始密钥，且成功率达99%及以上。实验分析表明，所提方法不仅能减少故障数和耗时，而且进一步提升了准确率。该结果对轻量级密码的实现安全性提供了重要参考。

关键词: 侧信道分析, 不可能统计故障分析, 轻量级密码, PRIDE, 智能无人系统

Abstract:

To analyze the implementation security of the PRIDE lightweight cryptosystem proposed at CRYPTO in 2014, a novel method of impossible statistical fault analysis on the ciphertext-only attack assumption was proposed.Furthermore, new distinguishers were designed, such as the Chi-square goodness-of-fit test-Hamming weight, and Chi-square goodness-of-fit test-maximum likelihood estimation.The proposed method had a random nibble-oriented fault model, and combined the statistical distribution states with the impossible relationship.On the difference among the intermediate states before and after the fault injections, at least 432 faults were required to recover the 128 bit secret key of PRIDE with a reliability of at least 99%.The experimental analysis demonstrates that the proposed method can not only reduce injected faults and latency, but also increase the accuracy.The results provide a vital reference for exploring the implementation security of lightweight cryptosystems.

Key words: side-channel analysis, impossible statistical fault analysis, lightweight cryptosystem, PRIDE, intelligent unmanned system

中图分类号:

TP309.7

李玮, 孙文倩, 谷大武, 张爱琳, 温云华. PRIDE轻量级密码的不可能统计故障分析[J]. 通信学报, 2024, 45(1): 141-151.

Wei LI, Wenqian SUN, Dawu GU, Ailin ZHANG, Yunhua WEN. Impossible statistical fault analysis of the PRIDE lightweight cryptosystem[J]. Journal on Communications, 2024, 45(1): 141-151.

图/表 13

图1

表1

图2

图3

图4

图5

图6

表2

表3

图7

表4

图8

表5

参考文献 39

[1]	SINGH R , BHUSHAN B . Evolving intelligent system for trajectory tracking of unmanned aerial vehicles[J]. IEEE Transactions on Automation Science and Engineering, 2022,19(3): 1971-1984.
[2]	ALRAWI O , LEVER C , ANTONAKAKIS M ,et al. SoK:security evaluation of home-based IoT deployments[C]// Proceedings of IEEE Symposium on Security and Privacy. Piscataway:IEEE Press, 2019: 1362-1380.
[3]	吴武飞, 李仁发, 曾刚 ,等. 智能网联车网络安全研究综述[J]. 通信学报, 2020,41(6): 161-174.
	WU W F , LI R F , ZENG G ,et al. Survey of the intelligent and connected vehicle cybersecurity[J]. Journal on Communications, 2020,41(6): 161-174.
[4]	王圣宝, 周鑫, 文康 ,等. 适用于智能电网的三方认证密钥交换协议[J]. 通信学报, 2023,44(02): 210-218.
	WANG S B , ZHOU X , WEN K ,et al. Tripartite authenticated key exchange protocol for smart grid[J]. Journal on Communications, 2023,44(2): 210-218.
[5]	NAITO Y , SASAKI Y , SUGAWARA T . Lightweight authenticated encryption mode suitable for threshold implementation[C]// Proceedings of Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 2020: 705-735.
[6]	CHENG J , GUO S , HE J . An extended type-1 generalized Feistel networks:lightweight block cipher for IoT[J]. IEEE Internet of Things Journal, 2022,9(13): 11408-11421.
[7]	CHENG H , GROSSSCH?DL J , MARSHALL B ,et al. RISC-V instruction set extensions for lightweight symmetric cryptography[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2022(1): 193-237.
[8]	ZHU D , ZHANG R , OU L ,et al. Low-latency design and implementation of the squaring in class groups for verifiable delay function using redundant representation[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2022(1): 438-462.
[9]	ALBRECHT M R , DRIESSEN B , KAVUN E B ,et al. Block ciphers –focus on the linear layer (feat.PRIDE)[C]// Proceedings of Advances in Cryptology. Berlin:Springer, 2014: 57-76.
[10]	伊文坛, 田亚, 陈少真 . 减缩轮PRIDE算法的线性分析[J]. 电子学报, 2017,45(2): 468-476.
	YIN W T , TIAN Y , CHEN S Z . Linear cryptanalysis of reduced-round PRIDE block cipher[J]. Chinese Journal of Electronics, 2017,45(2): 468-276.
[11]	LALLEMAND V , RASOOLZADEH S . Differential cryptanalysis of 18-round PRIDE[C]// Proceedings of International Conference on Cryptology in India. Berlin:Springer, 2017: 126-146.
[12]	PAL D , MANDAL U , DAS A ,et al. Deep learning based differential classifier of PRIDE and RC5[C]// Proceedings of International Conference on Applicat ions and Techniques in Information Security. Berlin:Springer, 2023: 46-58.
[13]	YANG Q , HU L , SUN S ,et al. Improved differential analysis of block cipher PRIDE[C]// Proceedings of International Conference on Information Security Practice and Experience. Berlin:Springer, 2015: 209-219.
[14]	BONEH D , DEMILLO R A , LIPTON R J . On the importance of checking cryptographic protocols for faults[C]// Proceedings of International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 1997: 37-51.
[15]	FUHR T , JAULMES E , LOMNE V ,et al. Fault attacks on AES with faulty ciphertexts only[C]// Proceedings of Workshop on Fault Diagnosis and Toler ance in Cryptography. Piscataway:IEEE Press, 2013: 108-118.
[16]	CLAVIER C . Secret external encodings do not prevent transient fault analysis[C]// Proceedings of International Workshop on Cryptographic Hardware and Embedded Systems. Berlin:Springer, 2007: 181-194.
[17]	BIHAM E , SHAMIR A . Differential fault analysis of secret key cryptosystems[C]// Proceedings of Annual International Cryptology Conference. Berlin:Springer, 1997: 513-525.
[18]	DERBEZ P , FOUQUE P A , LERESTEUX D . Meet-in-the-middle and impossible differential fault analysis on AES[C]// Proceedings of International Workshop on Cryptographic Hardware and Embedded Systems. Berlin:Springer, 2011: 274-291.
[19]	ZHANG F , LOU X , ZHAO X ,et al. Persistent fault analysis on block ciphers[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2018(3): 150-172.
[20]	JANA A , PAUL G . Differential fault attack on PHOTON-Beetle[C]// Proceedings of Workshop on Attacks and Solutions in Hardware Security. New York:ACM Press, 2022: 25-34.
[21]	ZHANG F , FENG T , LI Z ,et al. Free fault leakages for deep exploitation:algebraic persistent fault analysis on lightweight block ciphers[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2022(2): 289-311.
[22]	王永娟, 樊昊鹏, 代政一 ,等. 侧信道攻击与防御技术研究进展[J]. 计算机学报, 2023,46(1): 202-228.
	WANG Y J , FAN H P , DAI Z Y ,et al. Advances in side channel attacks and countermeasures[J]. Chinese Journal of Computers, 2023,46(1): 202-228.
[23]	李玮, 刘春, 谷大武 ,等. Saturnin-Short 轻量级认证加密算法的统计无效故障分析[J]. 通信学报, 2023,44(4): 167-175.
	LI W , LIU C , GU D W ,et al. Statistical ineffective fault analysis of the lightweight authenticated cipher algorithm Saturnin-Short[J]. Journal on Communications, 2023,44(4): 167-175.
[24]	LI W , LIAO L , GU D ,et al. Ciphertext-only fault analysis on the LED lightweight cryptosystem in the Internet of things[J]. IEEE Transactions on Dependable and Secure Computing, 2019,16(3): 454-461.
[25]	LI W , LI J , GU D ,et al. Statistical fault analysis of the Simeck lightweight cipher in the ubiquitous sensor networks[J]. IEEE Transactions on Information Forensics and Security, 2021,16: 4224-4233.
[26]	BIHAM E , BIRYUKOV A , SHAMIR A . Miss in the middle attacks on IDEA and Khufu[C]// Proceedings of International Workshop on Fast Software Encryption. Berlin:Springer, 1999: 124-138.
[27]	BIHAM E , BIRYUKOV A , SHAMIR A . Cryptanalysis of Skipjack reduced to 31 rounds using impossible differentials[J]. Journal of Cryptology, 2005,18(4): 291-311.
[28]	MOON D , HWANG K , LEE W ,et al. Impossible differential cryptanalysis of reduced round XTEA and TEA[C]// Proceedings of International Workshop on Fast Software Encryption. Berlin:Springer, 2002: 49-60.
[29]	CHEN J , HU Y , ZHANG Y . Impossible differential cryptanalysis of advanced encryption standard[J]. Science China Information Sciences, 2007,50(3): 342-350.
[30]	WU W , ZHANG L , ZHANG W . Improved impossible differential cryptanalysis of reduced-round Camellia[C]// Proceedings of International Workshop on Selected Areas in Cryptography. Berlin:Springer, 2009: 442-456.
[31]	BOURA C , NAYA-PLASENCIA M , SUDER V . Scrutinizing and improving impossible differential attacks:applications to CLEFIA,Camellia,LBlock and Simon[C]// Proceedings of International Conference on the Theory and Application of Cryptology and Information Security. Berlin:Springer, 2014: 179-199.
[32]	LIU Y , SHI Y , GU D ,et al. Improved impossible differential cryptanalysis of large-block Rijndael[J]. Science China Information Sciences, 2019,62(3): 1-14.
[33]	DU J , WANG W , LI M ,et al. Related-tweakey impossible differential attack on QARMA-128[J]. Science China Information Sciences, 2019,62(3): 15-26.
[34]	ZHANG L , WU W , MAO Y . Impossible differential cryptanalysis on reduced-round PRINCEcore[C]// Proceedings of International Conference on Inform ation Security and Cryptology. Berlin:Springer, 2023: 61-77.
[35]	BIHAM E , GRANBOULAN L , NGUY?N P Q . Impossible fault analysis of RC4 and differential fault analysis of RC4[C]// Proceedings of Internation al Workshop on Fast Software Encryption. Berlin:Springer, 2005: 359-367.
[36]	LI W , RIJMEN V , TAO Z ,et al. Impossible meet-in-the-middle fault analysis on the LED lightweight cipher in VANETs[J]. Science China Information Sciences, 2018,61(3): 032110.
[37]	REED I . A class of multiple-error-correcting codes and the decoding scheme[J]. Transactions of the IRE Professional Group on Information Theory, 1954,4(4): 38-49.
[38]	WILKS S S . The large-sample distribution of the likelihood ratio for testing composite hypotheses[J]. The Annals of Mathematical Statistics, 1938,9(1): 60-62.
[39]	PEARSON K X . On the criterion that a given system of deviations from the probable in the case of a correlated system of variables is such that it can be reasonably supposed to have arisen from random sampling[J]. The London,Edinburgh,and Dublin Philosophical Magazine and Journal of Science, 1900,50(302): 157-175.

分析类型	基本假设	最高攻击轮数/轮	文献
线性分析	已知明文攻击	18	文献[10]
差分分析	选择明文攻击	18	文献[11]
基于深度学习差分分析	选择明文攻击	18	文献[12]
高阶差分分析	选择明文攻击	19	文献[13]
统计故障分析	唯密文攻击	20	本文
不可能统计故障分析	唯密文攻击	20	本文

区分器	取值范围	筛选过程
HW	最小值	评估中间状态的汉明重量，选择值最小的统计样本
MLE	最大值	评估中间状态的出现概率，选择概率最大的统计样本
CS-HW	HW最小值、CS最小值	先使用 HW 区分器选择值最小的统计样本，再使用CS区分器选择值最小的统计样本
CS-MLE	MLE最大值、CS最小值	先使用MLE区分器选择出概率最大的统计样本，再使用CS区分器选择值最小的统计样本

区分器	统计故障分析			不可能统计故障分析
区分器	时间复杂度	数据复杂度	空间复杂度	时间复杂度	数据复杂度	空间复杂度
HW	2 ^21.45	2 ^17.36	2 ^23.36	2 ^21.30	2 ^17.21	2 ^23.21
MLE	2 ^21.37	2 ^17.29	2 ^23.29	2 ^21.22	2 ^17.13	2 ^23.13
CS-HW	2 ^22.34	2 ^17.25	2 ^23.25	2 ^21.89	2 ^16.81	2 ^22.81
CS-MLE	2 ^22.22	2 ^17.13	2 ^23.13	2 ^21.84	2 ^16.75	2 ^22.75

PRIDE轻量级密码的不可能统计故障分析

Impossible statistical fault analysis of the PRIDE lightweight cryptosystem

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 13

参考文献 39

相关文章 5

Metrics

推荐阅读 0

[1]	刘帅, 关杰, 胡斌, 马宿东. 基于MILP的轻量级密码算法ACE的差分分析[J]. 通信学报, 2023, 44(1): 39-48.
[2]	李玮, 汪梦林, 谷大武, 李嘉耀, 蔡天培, 徐光伟. 轻量级密码算法TWINE的唯密文故障分析[J]. 通信学报, 2021, 42(3): 135-149.
[3]	李玮,吴益鑫,谷大武,李嘉耀,曹珊,汪梦林,蔡天培,丁祥武,刘志强. SIMON轻量级密码算法的唯密文故障分析[J]. 通信学报, 2019, 40(11): 122-137.
[4]	罗鹏,李慧云,王鲲鹏,王亚伟. 对ECC算法实现的选择明文攻击方法[J]. 通信学报, 2014, 35(5): 79-87.
[5]	罗鹏1,2，李慧云3，王鲲鹏4，王亚伟5. 对ECC算法实现的选择明文攻击方法[J]. 通信学报, 2014, 35(5): 11-87.

区分器	统计故障分析		不可能统计故障分析
区分器	故障数/个	成功率	故障数/个	成功率
HW	656	99%	592	99%
MLE	624	99%	560	99%
CS-HW	608	99%	448	99%
CS-MLE	560	99%	432	99%

区分器	统计故障分析		不可能统计故障分析
区分器	耗时/s	成功率	耗时/s	成功率
HW	2.07	99%	1.90	99%
MLE	1.99	99%	1.81	99%
CS-HW	1.92	99%	1.43	99%
CS-MLE	1.80	99%	1.40	99%