轻量级密码MANTIS的唯密文故障分析

doi:10.12263/DZXB.20211026

电子学报 ›› 2022, Vol. 50 ›› Issue (4): 967-976.DOI: 10.12263/DZXB.20211026

轻量级密码MANTIS的唯密文故障分析

李玮¹^,²^,³^,⁴, 张雨希¹, 谷大武², 张金煜¹, 朱晓铭¹, 刘春¹, 蔡天培¹, 李嘉耀¹

^1.东华大学计算机科学与技术学院，上海 201620
^2.上海交通大学计算机科学与工程系，上海 200240
^3.上海市可扩展计算机与系统重点实验室（上海交通大学），上海 200240
^4.上海市信息安全综合管理技术研究重点实验室（上海交通大学），上海 220240

收稿日期:2021-08-01 修回日期:2022-01-17 出版日期:2022-04-25
- 作者简介:
- 李玮女，1980年8月出生，安徽寿县人.现为东华大学教授，博士生导师.主要研究方向为对称密码的设计与分析.E-mail: liwei.cs.cn@gmail.com
  张雨希女，1998年8月出生，黑龙江哈尔滨人.现为东华大学硕士研究生.主要研究方向为轻量级密码的安全分析.
  谷大武男，1970年10月出生，河南漯河人.现为上海交通大学教授，博士生导师.主要研究方向为密码学和计算机安全.
  张金煜男，1998年2月出生，浙江嘉兴人.现为东华大学硕士研究生.主要研究方向为轻量级密码的故障分析.
  朱晓铭男，1998年1月出生，河北邯郸人.现为东华大学硕士研究生.主要研究方向为轻量级密码的安全分析.
  刘春女，2000年3月出生，江西萍乡人.现为东华大学硕士研究生.主要研究方向为轻量级密码的安全分析.
  蔡天培男，1996年12月出生，浙江温州人.现为东华大学硕士研究生.主要研究方向为对称密码的安全性分析.
  李嘉耀男，1996年4月出生，广东广州人.现为东华大学博士研究生.主要研究方向为对称密码的故障分析.
- 基金资助:
- 国家自然科学基金 (61772129); 国家密码发展基金 (MMJJ20180101); 上海市自然科学基金 (19ZR14 02000); 上海市可扩展计算与系统重点实验室开放课题; 上海市信息安全综合管理技术研究重点实验室开放课题; 中央高校基本科研业务费专项资金

Ciphertext-Only Fault Analysis on the MANTIS Lightweight Cipher

LI Wei¹^,²^,³^,⁴, ZHANG Yu-xi¹, GU Da-wu², ZHANG Jin-yu¹, ZHU Xiao-ming¹, LIU Chun¹, CAI Tian-pei¹, LI Jia-yao¹

^1.School of Computer Science and Technology, Donghua University, Shanghai 201620, China
^2.Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai 200240, China
^3.Department of Shanghai Key Laboratory of Scalable Computing and Systems （Shanghai Jiao Tong University）, Shanghai 200240, China
^4.Shanghai Key Laboratory of Integrate Administration Technologies for Information Security （Shanghai Jiao Tong University）, Shanghai 200240, China

Received:2021-08-01 Revised:2022-01-17 Online:2022-04-25 Published:2022-04-25
- Supported by:
- National Natural Science Foundation of China (61772129); National Cryptography Development Fund (MMJJ20180101); National Natural Science Foundation of Shanghai Municipality, China (19ZR14 02000); Open project of Shanghai Key Laboratory of Scalable Computing and System; Shanghai Key Laboratory of Information Security Integrated Management Technology Research Program; Fundamental Research Funds for the Central Universities

摘要/Abstract

摘要：

MANTIS密码是于2016年美密会上提出的一种轻量级可调分组密码，它的设计采用FX结构和TWEAKEY框架，适用于物联网环境中具有低延迟、高实时安全需求的受限设备中.本文基于半字节随机故障模型以及唯密文攻击，提出并讨论一种针对MANTIS密码的新型唯密文故障分析.该分析结合公开调柄，利用故障注入后中间状态的不均匀性，可以破译MANTIS的全部版本.实验结果表明，提出的新型双重区分器狄利克雷分布-汉明重量以及狄利克雷分布-极大似然最少分别需要392和396个故障，以99%及以上的成功率破译MANTIS各版本的128 bit原始密钥，不仅减少了故障注入数，而且提高了攻击效率，因此，MANTIS密码不能抵抗唯密文故障分析的攻击.该结果为其他轻量级可调分组密码的安全性分析和防护提供了重要参考.

关键词: 故障分析, 轻量级密码, MANTIS, 唯密文分析, 物联网

Abstract:

The lightweight tweakable block cipher MANTIS was published at the international Cryptology conference in 2016. It adopts the FX construction and the TWEAKEY framework, and can be applicable to the devices with the security requirements of low latency and high real time in the Internet of Things. The novel ciphertext-only fault analysis on MANTIS is proposed and discussed on the basis of the random nibble-oriented fault model and the assumption of ciphertext-only attack. On the public tweaks, the attackers can take advantage of the non-uniform property of the nibbles after fault injections, and recover the secret keys of all versions of MANTIS. The experimental results show that the new double distinguishers of Dirichlet distribution-Hamming weight and Dirichlet distribution-maximum likelihood can recover the 128-bit secret key with 392 and 396 faults, respectively. And the probability of success is no less than 99%. The proposed ciphertext-only fault analysis can not only decrease the faults, but improve the attacking efficiency. Thus, MANTIS cannot resist against the ciphertext-only fault analysis. It is vital for the security analysis and protection of other lightweight tweakable block ciphers.

Key words: fault analysis, lightweight cipher, MANTIS, ciphertext-only attack, Internet of Things

中图分类号:

TP309.7

李玮, 张雨希, 谷大武, 等. 轻量级密码MANTIS的唯密文故障分析[J]. 电子学报, 2022, 50(4): 967-976.

Wei LI, Yu-xi ZHANG, Da-wu GU, et al. Ciphertext-Only Fault Analysis on the MANTIS Lightweight Cipher[J]. Acta Electronica Sinica, 2022, 50(4): 967-976.

图/表 12

表1 针对MANTIS密码的安全性分析汇总

分析类型	基本假设	$M A N T I S r$ 版本	文献
截断差分分析	选择明文	$r = 5$	［13］
半截断差分分析	选择明文	$r = 6$	［14］
多差分分析	选择明文	$r = 6 / 7$	［15］
零相关分析	选择明文	$r = 8$	［16］
积分分析	选择明文/文本	$r = 4$	［17］
唯密文故障分析	唯密文	$r ≥ 3$	本文

表1 针对MANTIS密码的安全性分析汇总

分析类型	基本假设	$M A N T I S r$ 版本	文献
截断差分分析	选择明文	$r = 5$	［13］
半截断差分分析	选择明文	$r = 6$	［14］
多差分分析	选择明文	$r = 6 / 7$	［15］
零相关分析	选择明文	$r = 8$	［16］
积分分析	选择明文/文本	$r = 4$	［17］
唯密文故障分析	唯密文	$r ≥ 3$	本文

表2 AES密码、LED密码、LBlock密码、SIMON密码及MANTIS密码的唯密文故障分析结果比较

区分器故障数算法	AES-128^［22］	LED-128^［24］	LBlock-80^［25］	SIMON-64/128^［26］	MANTIS-128
平方欧氏距离（SEI）	320	560	124	∞	∞
汉明重量（HW）	288	312	-	-	440
极大似然（ML）	224	320	92	264	424
拟合优度（GF）	-	480	114	408	736
拟合优度-平方欧式距离（GF-SEI）	-	424	70	376	528
拟合优度-极大似然（GF-ML）	-	-	90	288	436
拟合优度-汉明重量（GF-HW）	-	-	-	248	428
狄利克雷分布-极大似然（DD-ML）	-	-	-	-	396
狄利克雷分布-汉明重量（DD-HW）	-	-	-	-	392

图1 MANTIS密码结构和轮函数

表3 信元代替表

x	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
$S C (x)$	12	10	13	3	14	11	15	7	8	9	1	5	0	2	4	6

表3 信元代替表

x	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
$S C (x)$	12	10	13	3	14	11	15	7	8	9	1	5	0	2	4	6

表4 逆信元置换表

x	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
$S C (x)$	0	5	15	10	13	8	2	7	11	14	4	1	6	3	9	12

表4 逆信元置换表

x	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
$S C (x)$	0	5	15	10	13	8	2	7	11	14	4	1	6	3	9	12

图2 半字节经故障注入后的分布律

图3 故障导入在倒数第二轮后的扩散路径

图4 故障导入在倒数第三轮后的扩散路径

表5 各区分器对比

区分器	原理	取值	文献
平方欧式距离（SEI）	衡量总体分布与均匀分布的差距，筛选最不符合均匀分布的样本分布	SEI最大值	［22］
汉明重量（HW）	计算样本分布与零的距离，筛选汉明重量值与零距离最远的样本分布	HW最小值	［22］
极大似然（ML）	计算中间状态分布概率的乘积，筛选似然函数最大的样本分布	ML最大值	［22］
拟合优度（GF）	判断已知样本分布与理论分布的拟合程度，筛选拟合程度最大的样本分布	GF最小值	［24］
拟合优度-平方欧氏距离（GF-SEI）	先用GF筛选与理论分布拟合程度最优的一组样本分布，再用SEI筛选最不均匀的样本分布	GF最小值 SEI最大值	［24］
拟合优度-极大似然（GF-ML）	先用GF筛选与理论分布拟合程度最优的一组样本分布，再用ML筛选似然函数最大的样本分布	GF最小值 ML最大值	［25］
拟合优度-汉明重量（GF-HW）	先用GF筛选与理论分布拟合程度最优的一组样本分布，再用HW筛选汉明重量最小的样本分布	GF最小值 HW最小值	［26］
狄利克雷分布-极大似然（DD-ML）	先用DD筛选中间状态对应的概率最大的一组样本分布，再用ML筛选似然函数最大的样本分布	DD最大值 ML最大值	本文
狄利克雷分布-汉明重量（DD-HW）	先用DD筛选中间状态对应的概率最大的一组样本分布，再用HW筛选汉明重量最小的样本分布	DD最大值 HW最小值	本文

图5 各区分器恢复16 bit密钥的成功率

图6 各区分器恢复16 bit密钥的耗时

表6 各区分器恢复完整密钥所需故障数、时间复杂度和数据复杂度

区分器	故障数	时间复杂度	数据复杂度
平方欧氏距离（SEI）	∞	∞	∞
汉明重量（HW）	440	2^30.61	2^24.78
极大似然（ML）	424	2^30.51	2^24.75
拟合优度（GF）	736	2^31.99	2^25.52
拟合优度-平方欧氏距离（GF-SEI）	528	2^31.20	2^25.15
拟合优度-极大似然（GF-ML）	436	2^30.87	2^24.77
拟合优度-汉明重量（GF-HW）	428	2^30.78	2^24.74
狄利克雷分布-极大似然（DD-ML）	396	2^30.50	2^24.63
狄利克雷分布-汉明重量（DD-HW）	392	2^30.49	2^24.61

参考文献 26

1	ZAINUDDINN, DAUDM, AHMADS, et al. A study on privacy issues in Internet of Things(IoT)[C]//Proceedings of the 5th International Conference on Cryptography, Security and Privacy. New York: IEEE, 2021: 96-100.
2	SHAIKHE, MOHIUDDINI, MANZOORA. Internet of Things(IoT): Security and privacy threats[C]//Proceedings of the 2nd International Conference on Computer Applications & Information Security. New York: IEEE, 2019: 1-6.
3	GUOJ, PEYRINT, POSCHMANNA, et al. The LED block cipher[C]// PRENEEL B, TAKAGI T. Proceedings of the 13th International Workshop on Cryptographic Hardware and Embedded Systems. Berlin: Springer, 2011: 326-341.
4	WUW, ZHANGL. LBlock: a lightweight block cipher[C]//LOPEZ J, TSUDIK G. Proceedings of the 9th International Conference on Applied Cryptography and Network Security. Berlin: Springer, 2011: 327-344.
5	BORGHOFFJ, CANTEAUTA, GÜNEYSUT, et al. PRINCE-a low-latency block cipher for pervasive computing applications[C]//WANG X, SAKO K. Proceedings of the 18th International Conference on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2012: 208-225.
6	BANIKS, BOGDANOVA, ISOBET, et al. Midori: A block cipher for low energy[C]//IWATA T, CHEON J. Proceedings of the 21st International Conference on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2015: 411-436.
7	BEIERLEC, LEANDERG, MORADIA, et al. CRAFT: lightweight tweakable block cipher with efficient protection against DFA attacks[J]. IACR Transactions on Symmetric Cryptology, 2019, 2019(1): 5-45.
8	KIMH, JEONY, KIMG, et al. PIPO: A lightweight block cipher with efficient higher-order masking software implementations[C]//HONG D. Proceedings of the 23rd Information Security and Cryptology. Berlin: Springer, 2020: 99-122.
9	BEIERLEC, JEANJ, KÖLBLS, et al. The SKINNY family of block ciphers and its low-latency variant MANTIS[C]//ROBSHAW M, KATZ J. Proceedings of the 36th International Cryptology Conference. Berlin: Springer, 2016: 123-153.
10	KILIANJ, ROGAWAYP. How to protect DES against exhaustive key search[J]. Lecture Notes in Computer Science, 1996, 1109: 252-267.
11	LISKOVM, RIVESTR L, WAGNERD. Tweakable block ciphers[J]. Journal of Cryptology, 2002, 2442: 531-46.
12	JEANJ, NIKOLIĆI, PEYRINT. Tweaks and keys for block ciphers: The TWEAKEY framework[C]//SARKAR P, IWATA T. Proceedings of the 20th International Conference on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2014: 274-288.
13	DOBRAUNIGC, EICHLSEDERM, KALESD, et al. Practical key-recovery attack on MANTIS₅[J]. IACR Transactions on Symmetric Cryptology, 2016, 2016(2): 248-260.
14	EICHLSEDERM, KALESD. Clustering related-tweak characteristics: application to MANTIS-6[J]. IACR Transactions on Symmetric Cryptology, 2018, 2018(2): 111-132.
15	CHENS Y, LIUR, CUIT T, et al. Automatic search method for multiple differentials and its application on MANTIS[J]. Science China Information Sciences, 2019, 62(3): 145-159.
16	ANKELER, DOBRAUNIGC, GUOJ, et al. Zero-correlation attacks on tweakable block ciphers with linear tweakey expansion[J]. IACR Transactions on Symmetric Cryptology, 2019, 2019(1): 192-235.
17	BEYNET. Block cipher invariants as eigenvectors of correlation matrices[J]. Journal of Cryptology, 2020, 33(3): 1156-1183.
18	BONEHD, DEMILLOR, LIPTONR. On the importance of checking cryptographic protocols for faults[C]//FUMY W. Proceedings of the International Conference on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 1997: 37-51.
19	BIHAME, SHAMIRA. Differential fault analysis of secret key cryptosystems[C]//KALISKI B S. Proceedings of the 17th International Cryptology Conference. Berlin: Springer, 1997: 513-525.
20	COURTOISN T, WARED, JACKSONK. Fault-algebraic attacks on inner rounds of DES[C]//Proceedings of the European Smart Card Security Conference. Montreuil: Computer Science, 2010: 22-24.
21	DERBEZP, FOUQUEP A, LERESTEUXD. Meet-in-the-middle and impossible differential fault analysis on AES[C]//PRENEEL B, TAKAGI T. Proceedings of the 13th International Workshop on Cryptographic Hardware and Embedded Systems. Berlin: Springer, 2011: 274-291.
22	FUHRT, JAULMESE, LOMNÉV, et al. Fault attacks on AES with faulty ciphertexts only[C]//Proceedings of the Workshop on Fault Diagnosis and Tolerance in Cryptography. New York: IEEE, 2013: 108-118.
23	DOBRAUNIGC, EICHLSEDERM, KORAKT, et al. Statistical fault attacks on nonce-based authenticated encryption schemes[C]//CHEON J, TAKAGI T. Proceedings of the 22nd International Conference on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2016: 369-395.
24	LIW, LIAOL F, GUD W, 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	李玮, 吴益鑫, 谷大武, 等. LBlock轻量级密码算法的唯密文故障分析[J]. 计算机研究与发展, 2018, 55(10): 2174-2184.
	LIW, WUY X, GUD W, et al. Ciphertext-only fault analysis of the LBlock lightweight cipher[J]. Journal of Computer Research and Development, 2018, 55(10): 2174-2184. (in Chinese)
26	李玮, 吴益鑫, 谷大武, 等. SIMON轻量级密码算法的唯密文故障分析[J]. 通信学报, 2019, 40(11): 122-137.
	LIW, WUY X, GUD W, et al. Ciphertext-only fault analysis of the SIMON lightweight cipher[J]. Journal on Communications, 2019, 40(11): 122-137. (in Chinese)

[1]	陈书仪, 刘亚丽, 林昌露, 李涛, 董永权. 面向物联网的轻量级可验证群组认证方案[J]. 电子学报, 2022, 50(4): 990-1001.
[2]	孟超, 周倩, 郭林, 王攀, 孙知信. 基于相关性传输模型的无线链路质量估计方法及路由优化算法[J]. 电子学报, 2022, 50(10): 2409-2424.
[3]	陈亮, 李峰, 任保全, 杨建喜. 软件定义物联网研究综述[J]. 电子学报, 2021, 49(5): 1019-1032.
[4]	焦贤龙, 郭松涛, 黎勇, 李艳涛, 向朝参. 基于相继干扰消除和跨层并发传输的物联网数据聚合调度[J]. 电子学报, 2021, 49(10): 1982-1992.
[5]	黄美根, 郁滨. 软件定义WSN规则一致更新研究[J]. 电子学报, 2019, 47(9): 1965-1971.
[6]	徐诚, 何杰, 张晓彤, 姚翠, 段世红, 齐悦. IMU/TOA融合人体运动追踪性能评估方法[J]. 电子学报, 2019, 47(8): 1748-1754.
[7]	王巍, 彭力, 赵继军, 常存喜, 黄晓丹, 田立勤. 移动物联网非完整约束中继的协同任务规划[J]. 电子学报, 2019, 47(6): 1251-1259.
[8]	李森森, 黄一才, 郁滨, 鲍博武. 基于PUF的低开销物联网安全通信方案[J]. 电子学报, 2019, 47(4): 812-817.
[9]	唐晓庆, 谢桂辉, 佘亚军, 俞杨. 基于MCU的无源Wi-Fi散射通信方法[J]. 电子学报, 2019, 47(10): 2069-2075.
[10]	杨晓东, 陈益强, 于汉超, 张迎伟, 钟习, 胡子昂, 刘弘. 面向帕金森病的多模态异构协同感知方法[J]. 电子学报, 2018, 46(3): 659-664.
[11]	王巍, 赵继军, 彭力, 黄晓丹, 李林茂, 魏丁丁. 基于UAV的移动物联网远距离通信节能策略研究[J]. 电子学报, 2018, 46(12): 2914-2922.
[12]	张德干, 葛辉, 刘晓欢, 张晓丹, 李文斌. 一种基于Q-Learning策略的自适应移动物联网路由新算法[J]. 电子学报, 2018, 46(10): 2325-2332.
[13]	李浪, 李肯立, 贺位位, 邹祎, 刘波涛. Magpie:一种高安全的轻量级分组密码算法[J]. 电子学报, 2017, 45(10): 2521-2527.
[14]	李勐, 王晓峰, 崔莉. 一种物联网设备自动描述方法[J]. 电子学报, 2016, 44(5): 1055-1063.
[15]	田野, 袁博, 李廷力. 物联网海量异构数据存储与共享策略研究[J]. 电子学报, 2016, 44(2): 247-257.

轻量级密码MANTIS的唯密文故障分析

Ciphertext-Only Fault Analysis on the MANTIS Lightweight Cipher

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 12

参考文献 26

相关文章 15

编辑推荐

Metrics