Saturnin-Short轻量级认证加密算法的统计无效故障分析

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

通信学报 ›› 2023, Vol. 44 ›› Issue (4): 167-175.doi: 10.11959/j.issn.1000-436x.2023084

Saturnin-Short轻量级认证加密算法的统计无效故障分析

李玮¹^,²^,³^,⁴, 刘春¹, 谷大武², 孙文倩¹, 高建宁¹, 秦梦洋¹

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

修回日期:2023-03-29 出版日期:2023-04-25 发布日期:2023-04-01
作者简介:李玮（1980- ），女，安徽寿县人，博士，东华大学教授、博士生导师，主要研究方向为对称密码的设计与分析
刘春（2000- ），女，江西萍乡人，东华大学硕士生，主要研究方向为轻量级密码的安全性分析
谷大武（1970- ），男，河南漯河人，博士，上海交通大学教授、博士生导师，主要研究方向为密码学和计算机安全
孙文倩（2000- ），女，安徽铜陵人，东华大学硕士生，主要研究方向为对称密码的故障分析
高建宁（1999- ），男，宁夏西吉人，东华大学硕士生，主要研究方向为对称密码的安全性分析
秦梦洋（2000- ），男，河南许昌人，东华大学硕士生，主要研究方向为轻量级密码的故障分析
基金资助:
国家自然科学基金资助项目(61772129);国家自然科学基金资助项目(61932014);国家自然科学基金资助项目(62102077);国家密码发展基金资助项目(MMJJ20180101);信息安全国家重点实验室开放课题资助项目(2021-MS-05);上海市扬帆计划基金资助项目(21YF1401200);上海市扬帆计划基金资助项目(23YF1401000);中央高校基本科研业务费专项资金资助项目(2232022D-25)

Statistical ineffective fault analysis of the lightweight authenticated cipher algorithm Saturnin-Short

Wei LI¹^,²^,³^,⁴, Chun LIU¹, Dawu GU², Wenqian SUN¹, Jianning GAO¹, Mengyang QIN¹

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

Revised:2023-03-29 Online:2023-04-25 Published:2023-04-01
Supported by:
The National Natural Science Foundation of China(61772129);The National Natural Science Foundation of China(61932014);The National Natural Science Foundation of China(62102077);The National Cryptography Development Foundation of China(MMJJ20180101);The Open Fund Program for State Key Laboratory of In-formation Security of China(2021-MS-05);Shanghai Sailing Program(21YF1401200);Shanghai Sailing Program(23YF1401000);The Fundamental Research Funds for the Central Universities(2232022D-25)

摘要/Abstract

摘要：

面向随机单字节故障模型和唯密文攻击假设，提出了一种针对 Saturnin-Short 算法的统计无效故障分析方法。该方法基于统计分布和无效状态分析，通过结合故障注入前后中间状态的变化，设计并采用了概率对称卡方-极大似然估计和调和中项-汉明重量新型区分器，最少仅需 1 097 个无效故障并以不低于 99%的成功率恢复Saturnin-Short算法的256 bit原始密钥。实验分析表明，所提区分器不仅降低了故障注入数，而且减少了攻击时间和复杂度。因此，Saturnin-Short算法不能抵抗统计无效故障分析的攻击。研究结果为其他轻量级认证加密算法的安全性分析提供了重要参考。

关键词: Saturnin-Short, 认证加密, 统计无效故障分析, 密码分析

Abstract:

On the random single byte-oriented fault model and the assumption of ciphertext-only attack, a statistical ineffective fault analysis of the Saturnin-Short cipher was proposed.The analysis combined the statistical distribution with the ineffective analysis, and discussed the difference between intermediate states before and after fault injections.A variety of dual distinguishers was designed, such as the probabilistic symmetric Chi-square-maximum likelihood estimate, and harmonic mean-Hamming weight.It only required at least 1 097 ineffective faults to recover the 256 bit secret key with a success rate of at least 99%.The experimental results show that the proposed distinguishers can not only decrease fault injections, but also reduce the attacking time and complexities.Therefore, the Saturnin-Short cipher cannot resist against the statistical ineffective fault analysis.It provides an important reference for the security analysis of other lightweight authenticated ciphers.

Key words: Saturnin-Short, authenticated cipher, statistical ineffective fault analysis, cryptanalysis

中图分类号:

TP309.7

李玮, 刘春, 谷大武, 孙文倩, 高建宁, 秦梦洋. Saturnin-Short轻量级认证加密算法的统计无效故障分析[J]. 通信学报, 2023, 44(4): 167-175.

Wei LI, Chun LIU, Dawu GU, Wenqian SUN, Jianning GAO, Mengyang QIN. Statistical ineffective fault analysis of the lightweight authenticated cipher algorithm Saturnin-Short[J]. Journal on Communications, 2023, 44(4): 167-175.

图/表 15

表1

表2

表3

符号说明"

符号	说明
X、 $\overset{⌢}{X}$ 、 $\bar{X}$ 、Y、N、 $\bar{N}$	明文、填充明文、待认证明文、密文、Nonce和待认证Nonce
K、K_rot、R、C₀、Cr	原始密钥、旋转密钥、加（解）密轮数、初始常数和第 r 轮的轮常数，其中，1≤r≤R， 10≤R≤31
${Saturnin}_{R}$ 、 ${Saturnin}_{R}^{- 1}$ 、Padding	加密过程、解密过程和填充过程
SC、MC、SR_slice、SR_sheet	S盒变换、列混淆、纵切片行移位和横切片行移位
SC^-1、MC^-1、 ${SR}_{slice}^{- 1}$ 、 ${SR}_{sheet}^{- 1}$	SC、MC、SR_slice 和 SR_sheet的逆操作
AK、AK_rot、IC、LFSR	密钥加、旋转密钥加、初始化轮常数和线性反馈移位
$T 、 T^{l} 、 K^{l} 、 K_{rot}^{l}$	第R-1轮AK_rot运算后输出的中间状态值及T、K和K_rot的第 $l$ 字节， $0 \leq l \leq 63$
$\oplus 、 mod 、 \| \| 、 \emptyset$	异或、模、连接和空集

表3

图1

图2

图3

表4

图4

表5

图5

表6

图6

图7

表7

表8

参考文献 29

[1]	CHEHAB M , MOURAD A . LP-SBA-XACML:lightweight semantics based scheme enabling intelligent behavior-aware privacy for IoT[J]. IEEE Transactions on Dependable and Secure Computing, 2022,19(1): 161-175.
[2]	ALRAWI O , LEVER C , ANTONAKAKIS M ,et al. SoK:security evaluation of home-based IoT deployments[C]// Proceedings of 2019 IEEE Symposium on Security and Privacy. Piscataway:IEEE Press, 2019: 1362-1380.
[3]	BANIK S , ISOBE T , LIU F K ,et al. Orthros:a low-latency PRF[J]. IACR Transactions on Symmetric Cryptology, 2021(1): 37-77.
[4]	BEIERLE C , LEANDER G , MORADI A ,et al. CRAFT:lightweight tweakable block cipher with efficient protection against DFA attacks[J]. IACR Transactions on Symmetric Cryptology, 2019(1): 5-45.
[5]	NAITO Y , MATSUI M , SUGAWARA T ,et al. SAEB:a lightweight blockcipher-based AEAD mode of operation[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2018(2): 192-217.
[6]	NAITO Y , SASAKI Y , SUGAWARA T . Lightweight authenticated encryption mode suitable for threshold implementation[C]// Annual International Conference on the Theory and Applications of Cryptographic Techniques. Berlin:Springer, 2020: 705-735.
[7]	CANTEAUT A , DUVAL S , LEURENT G ,et al. Saturnin:a suite of lightweight symmetric algorithms for post-quantum security[J]. IACR Transactions on Symmetric Cryptology, 2020(1): 160-207.
[8]	BONEH D , DEMILLO R A , LIPTON R J . On the importance of checking cryptographic protocols for faults[C]// Advances in Cryptology - EUROCRYPT ’97. Berlin:Springer, 1997: 37-51.
[9]	FUHR T , JAULMES E , LOMNé V ,et al. Fault attacks on AES with faulty ciphertexts only[C]// Proceedings of 2013 Workshop on Fault Diagnosis and Tolerance in Cryptography. Piscataway:IEEE Press, 2013: 108-118.
[10]	CLAVIER C , . Secret external encodings do not prevent transient fault analysis[C]// International Workshop on Cryptographic Hardware and Embedded Systems. Berlin:Springer, 2007: 181-194.
[11]	BIHAM E , SHAMIR A . Differential fault analysis of secret key cryptosystems[C]// Advances in Cryptology - CRYPTO’97. Berlin:Springer, 1997: 513-525.
[12]	COURTOIS N , WARE D A , JACKSON K . Fault-algebraic attacks on inner rounds of DES[C]// Strategies Telecom and Multimedia. Montreuil:Computer Science, 2010: 22-24.
[13]	DERBEZ P , FOUQUE P A , LERESTEUX D . Meet-in-the-middle and impossible differential fault analysis on AES[C]// International Workshop on Cryptographic Hardware and Embedded Systems. Berlin:Springer, 2011: 274-291.
[14]	ZHANG F , LOU X X , ZHAO X J ,et al. Persistent fault analysis on block ciphers[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2018(3): 150-172.
[15]	JANA A , PAUL G . Differential fault attack on PHOTON-beetle[C]// Proceedings of the 2022 Workshop on Attacks and Solutions in Hardware Security. New York:ACM Press, 2022: 25-34.
[16]	ZHANG F , FENG T X , LI Z Q ,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.
[17]	王永娟, 樊昊鹏, 代政一 ,等. 侧信道攻击与防御技术研究进展[J]. 计算机学报, 2023,46(1): 202-228.
	WANG Y J , FAN H P , DAI Z Y ,et al. Research progress of side channel attack and defense technology[J]. Chinese Journal of Computers, 2023,46(1): 202-228.
[18]	DOBRAUNIG C , EICHLSEDER M , KORAK T ,et al. Statistical fault attacks on nonce-based authenticated encryption schemes[C]// International Conference on the Theory and Application of Cryptology and Information Security. Berlin:Springer, 2016: 369-395.
[19]	李玮, 汪梦林, 谷大武 ,等. 轻量级密码算法TWINE的唯密文故障分析[J]. 通信学报, 2021,42(3): 135-149.
	LI W , WANG M L , GU D W ,et al. Ciphertext-only fault analysis of the TWINE lightweight cryptogram algorithm[J]. Journal on Communications, 2021,42(3): 135-149.
[20]	SUGAWARA T , SHOJI N , SAKIYAMA K ,et al. Exploiting bitflip detector for non-invasive probing and its application to ineffective fault analysis[C]// Proceedings of 2017 Workshop on Fault Diagnosis and Tolerance in Cryptograph. Piscataway:IEEE Press, 2017: 49-56.
[21]	CLAVIER C , WURCKER A . Reverse engineering of a secret AES-like cipher by ineffective fault analysis[C]// Proceedings of 2013 Workshop on Fault Diagnosis and Tolerance in Cryptography. Piscataway:IEEE Press, 2013: 119-128.
[22]	DOBRAUNIG C , EICHLSEDER M , KORAK T ,et al. SIFA:exploiting ineffective fault inductions on symmetric cryptography[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2018(3): 547-572.
[23]	BAGHERI N , SADEGHI S , RAVI P ,et al. SIPFA:statistical ineffective persistent faults analysis on Feistel ciphers[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2022(3): 367-390.
[24]	VAFAEI N , ZAREI S , BAGHERI N ,et al. Statistical effective fault attacks:the other side of the coin[J]. IEEE Transactions on Information Forensics and Security, 2022,17: 1855-1867.
[25]	DOBRAUNIG C , EICHLSEDER M , GROSS H ,et al. Statistical ineffective fault attacks on masked AES with fault countermeasures[C]// International Conference on the Theory and Application of Cryptology and Information Security. Berlin:Springer, 2018: 315-342.
[26]	GRUBER M , PROBST M , TEMPELMEIER M . Statistical ineffective fault analysis of GIMLI[C]// Proceedings of 2020 IEEE International Symposium on Hardware Oriented Security and Trust. Piscataway:IEEE Press, 2020: 252-261.
[27]	FISHER R A . On the mathematical foundations of theoretical statistics[J]. Philosophical Transactions of the Royal Society of London, 1922,222(594): 309-368.
[28]	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.
[29]	CHA S H . Comprehensive survey on distance/similarity measures between probability density functions[J]. International Journal of Mathematical Models ＆ Methods in Applied Sciences, 2007,1(4): 300-307.

分析类型	基本假设	攻击最高轮数/轮	方法
线性分析	已知明文攻击	8	文献[7]
差分分析	选择明文攻击	8	文献[7]
不可能差分分析	选择明文攻击	7	文献[7]
中间相遇分析	选择明文攻击	7.5	文献[7]
统计无效故障分析	唯密文攻击	31	本文方法

区分器	无效故障数/个	总故障数/个	耗时/s	成功率	时间复杂度	数据复杂度存储复杂度
平方欧氏距离（SEI）	∞	∞	∞	—	∞	∞∞
极大似然估计（MLE）	1 485	14 861	8.152	≥99%	2 ^14.64	2 ^18.542 ^18.55
汉明重量（HW）	1 454	14 542	7.787	≥99%	2 ^14.61	2 ^18.512 ^18.52
概率对称卡方-极大似然估计（PSC-MLE）	1 228	12 296	5.821	≥99%	2 ^14.37	2 ^18.262 ^18.28
调和中项-汉明重量（HM-HW）	1 097	10 981	4.532	≥99%	2 ^14.21	2 ^18.102 ^18.12

区分器	取值范围	筛选过程
SEI	最大值	评估实际分布和均匀分布之间的距离，选出距离相差最大的统计样本
MLE	最大值	评估中间状态的出现概率，选出概率最大的统计样本
HW	最小值	评估中间状态的汉明重量，选出汉明重量最小的统计样本
PSC-MLE	PSC 最小值和MLE最大值	先后使用PSC和MLE，选出距离程度最小且出现概率最大的统计样本
HM-HW	HM 最大值和HW最小值	先后使用 HM 和 HW，选出调和平均数最大且汉明重量最小的统计样本

区分器	无效故障数/个	总故障数/个	成功率
SEI	∞	∞	—
MLE	46	464	≥99%
HW	45	455	≥99%
PSC-MLE	38	384	≥99%
HM-HW	34	343	≥99%

区分器			耗时/s
区分器	300个	600个	900个	1 200个	1 500个
SEI	0.48	1.696	3.68	6.208	9.504
MLE	0.479	1.692	3.64	6.194	—
HW	0.472	1.669	3.59	6.191	—
PSC-MLE	0.47	1.662	3.575	6.084	—
HM-HW	0.465	1.643	3.534	—	—

Saturnin-Short轻量级认证加密算法的统计无效故障分析

Statistical ineffective fault analysis of the lightweight authenticated cipher algorithm Saturnin-Short

在线阅读

PDF下载

可视化

摘要/Abstract

引用本文

使用本文

图/表 15

参考文献 29

相关文章 15

Metrics

推荐阅读 0

输入	偶数索引	奇数索引
0	0	0
1	6	9
2	14	13
3	1	2
4	15	15
5	4	1
6	7	11
7	13	7
8	9	6
9	8	4
10	12	5
11	5	3
12	2	8
13	10	12
14	3	10
15	11	14

区分器	时间复杂度	数据复杂度	存储复杂度
SEI	∞	∞	∞
MLE	2 ^19.98	2 ^18.23	2 ^13.95
HW	2 ^19.96	2 ^18.19	2 ^13.93
PSC-MLE	2 ^19.71	2 ^17.95	2 ^13.75
HM-HW	2 ^19.55	2 ^17.79	2 ^13.64

[1]	杜小妮, 王香玉, 梁丽芳, 李锴彬. 轻量级分组密码Piccolo的量子密码分析[J]. 通信学报, 2023, 44(6): 175-182.
[2]	杜少宇. 积分攻击改进——随机线性区分与密钥恢复攻击[J]. 通信学报, 2023, 44(4): 145-153.
[3]	刘正斌, 李永强, 朱朝熹. 分组密码最小活跃S盒个数快速搜索算法[J]. 通信学报, 2023, 44(1): 118-128.
[4]	王念平, 殷勍. 类Piccolo结构的差分安全性评估[J]. 通信学报, 2022, 43(2): 55-64.
[5]	王念平, 郭祉成. 动态密码结构抵抗差分密码分析能力评估[J]. 通信学报, 2021, 42(8): 70-79.
[6]	张国双,陈晓,林东岱,刘凤梅. 基于Nonce重用的ACORN v3状态恢复攻击[J]. 通信学报, 2020, 41(8): 11-21.
[7]	沈煜,李玮,谷大武,吴益鑫,曹珊,刘亚,刘志强,周志洪. ARIA密码的积分故障分析[J]. 通信学报, 2019, 40(2): 164-173.
[8]	李荣佳,金晨辉. FOX算法的中间相遇攻击[J]. 通信学报, 2016, 37(8): 185-190.
[9]	郭建胜,崔竞一,潘志舒,刘翼鹏. HIGHT算法的积分攻击[J]. 通信学报, 2016, 37(7): 71-78.
[10]	马猛,赵亚群. 简化版Trivium算法的线性逼近研究[J]. 通信学报, 2016, 37(6): 185-191.
[11]	刘庆聪,赵亚群,马猛,刘凤梅. MIBS密码的零相关—积分攻击[J]. 通信学报, 2016, 37(11): 189-195.
[12]	潘志舒,郭建胜,曹进克,罗伟. MIBS算法的积分攻击[J]. 通信学报, 2014, 35(7): 157-163.
[13]	潘志舒，郭建胜，曹进克，罗伟. MIBS算法的积分攻击[J]. 通信学报, 2014, 35(7): 19-163.
[14]	古春生. 破解新型的轻量级数字签名方案[J]. 通信学报, 2013, 34(7): 154-158.
[15]	古春生1,2,3. 破解新型的轻量级数字签名方案[J]. 通信学报, 2013, 34(7): 17-158.