SM9加密算法的颠覆攻击与改进

doi:10.3969/j.issn.1671-1122.2024.06.002

摘要/Abstract

摘要：

我国自主研发的基于标识的SM9加密算法已成功入选ISO/IEC国际标准，但敌手可以颠覆密码算法的组件，从而破坏算法的安全性，而SM9加密算法在设计之初并未考虑到此类攻击的存在。针对该问题，文章首先提出了基于标识加密（Identity Based Encryption，IBE）的颠覆攻击模型，并定义了明文可恢复性和不可检测性两个性质；然后提出了针对SM9加密算法的颠覆攻击，并发现敌手通过连续两个密文就能恢复明文；最后提出了抗颠覆的SM9加密算法（Subversion Resilient-SM9，SR-SM9），并证明其不仅满足适应性选择身份和密文攻击下的密文不可区分性，还能够抵抗颠覆攻击。文章基于gmalg库和Python语言测试了SR-SM9，测试结果显示，SR-SM9相比于SM9加密算法只增加0.6%的计算成本且未增加通信成本。

关键词: SM9加密算法, 基于标识的密码学, 颠覆攻击, 抗颠覆性

Abstract:

China’s independently developed identity-based encryption algorithm SM9 has been successfully selected as an ISO/IEC international standard. However, adversary can tamper components of cryptographic algorithms to undermine their security. During the initial design of SM9 encryption algorithm, such subversion attacks were not considered. Whether SM9 encryption algorithm is vulnerable to subversion attacks and how to resist subversion attacks is still an unknown issue. To answer the above question, this paper introduced a subversion attack model for identity-based encryption(IBE) and defined two properties: plaintext recoverability and undetectability. In addition, this paper implemented a subversion attack on SM9 encryption algorithm and found that an adversary could recover a plaintext with only two successive ciphertexts. Moreover, this paper proposed a subversion-resilient SM9 encryption(SR-SM9), and proved SR-SM9 was not only secure under the adaptive chosen identity and ciphertext attack(ID-IND-CCA2) but also was subversion-resilient. Finally, this paper implemented SR-SM9 based on gmalg library and Python language. Compared with SM9, SR-SM9 only adds 0.6% computation cost with no additional communication cost.

Key words: SM9 encryption, identity-based cryptography, subversion attack, subversion- resilient

中图分类号:

TP309

欧阳梦迪, 孙钦硕, 李发根. SM9加密算法的颠覆攻击与改进[J]. 信息网络安全, 2024, 24(6): 831-842.

OUYANG Mengdi, SUN Qinshuo, LI Fagen. Subversion Attacks and Countermeasures of SM9 Encryption[J]. Netinfo Security, 2024, 24(6): 831-842.

图/表 6

表1

图1

表2

表3

图2

图3

参考文献 30

[1]	SCHNEIER B, FREDRIKSON M, KOHNO T, et al. Surreptitiously Weakening Cryptographic Systems[EB/OL]. (2015-09-07)[2024-04-12]. https://eprint.iacr.org/2015/097.
[2]	WALD G. U.S. British Intelligence Mining Data from Nine U. S. Internet Companies[N]. Washington Post 2013-06-06(1).
[3]	DAVIS D. US Global Monitoring Action Record[N]. Xinhuanet, 2014-05-26(1).
[4]	YOUNG A, YUNG M. The Dark Side of “Black-Box” Cryptography or: Should We Trust Capstone?[C]// Springer. Advances in Cryptology-CRYPTO 1996. Heidelberg:Springer, 1996: 89-103.
[5]	YOUNG A. Kleptography: Using Cryptography against Cryptography[C]// Springer. Advances in Cryptology-EUROCRYPT 1997. Heidelberg:Springer, 1997: 62-74.
[6]	BELLARE M, PATERSON K G, ROGAWAY P. Security of Symmetric Encryption against Mass Surveillance[C]// Springer. Advances in Cryptology-CRYPTO 2014. Heidelberg: Springer, 2014: 1-19.
[7]	CHEN Rongmao, HUANG Xinyi, YUNG M. Subvert Kem to Break Dem: Practical Algorithm-Substitution Attacks on Public-Key Encryption[C]// Springer. Advances in Cryptology-ASIACRYPT 2020. Heidelberg: Springer, 2020: 98-128.
[8]	CHAKRABORTY S, MAGRI B, NIELSEN J B, et al. Universally Composable Subversion-Resilient Cryptography[C]// Springer. Advances in Cryptology-EUROCRYPT 2022. Heidelberg: Springer, 2022: 272-302.
[9]	ATENIESE G, MAGRI B, VENTURI D. Subversion-Resilient Signature Schemes[C]// Springer. Advances in Cryptology-EUROCRYPT 2022. Heidelberg: Springer, 2022: 272-302.
[10]	ARMOUR M, POETTERING B. Substitution Attacks against Message Authentication[J]. IACR Transactions on Symmetric Cryptology, 2019, 1(1): 152-168.
[11]	SHAMIR A. Identity-Based Cryptosystems and Signature Schemes[C]// Springer. Advances in Cryptology-CRYPTO 1985. Heidelberg:Springer, 1985: 47-53.
[12]	SHANG Tao, ZHANG Feng, CHEN Xingyue, et al. Identity-Based Dynamic Data Auditing for Big Data Storage[J]. IEEE Transactions on Big Data, 2019, 7(6): 913-921.
[13]	LI Jiguo, HAO Yan, ZHANG Yichen. Efficient Identity-Based Provable Multi Copy Data Possession in Multi-Cloud Storage[J]. IEEE Transactions on Cloud Computing, 2019, 10(1): 356-365.
[14]	IEEE Std 1363.3-2013. Standard for Identity-Based Cryptographic Techniques Using Pairings[S]. New York: IEEE, 2013.
[15]	ISO/IEC 18033-5:2015. Information Technology-Security Techniques-Encryption Algorithms-Part 5: Identity-Based Ciphers[S]. New York: ISO/IEC, 2015.
[16]	GM/T0044-2016. SM9 Identity-Based Cryptographic Algorithm Part IV: Key Encapsulation Mechanism and Public Key Encryption Algorithm[S]. Beijing: Standards Press of China, 2016.
	GM/T0044.4-2016. SM9标识密码算法第4部分:密钥封装机制和公钥加密算法[S]. 北京: 中国标准出版社, 2016.
[17]	HUANG Xinyi, CHEN Rongmao, WANG Yi, et al. Key Exfiltration on SM2 Cryptographic Algorithms[J]. Journal of Cryptologic Research, 2021, 8(4): 684-698.
	黄欣沂, 陈荣茂, 王毅, 等. SM2密码算法密钥渗漏分析[J]. 密码学报, 2021, 8(4):684-698.
[18]	DEGABRIELE J P, FARSHIM P, POETTERING B. A More Cautious Approach to Security Against Mass Surveillance[C]// Springer. In Fast Software Encryption-FSE. Heidelberg: Springer, 2015: 579-598.
[19]	BELLARE M, JAEGER J, KANE D. Mass-Surveillance without the State: Strongly Undetectable Algorithm-Substitution Attacks[C]// ACM. The 22nd ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2015: 1431-1440.
[20]	RUSSELL A, TANG Qiang, YUNG M, et al. Cliptography: Clipping the Power of Kleptographic Attacks[C]// Springer. Advances in Cryptology-ASIACRYPT 2016. Heidelberg: Springer, 2016: 34-64.
[21]	ARMOUR M, POETTERING B. Algorithm Substitution Attacks against Receivers[J]. International Journal of Information Security, 2022, 21(5): 1027-1050.
[22]	MIRONOV I, STEPHENS-DAVIDOWITZ N. Cryptographic Reverse Firewalls[C]// Springer. Advances in Cryptology-EUROCRYPT 2015. Heidelberg: Springer, 2015: 657-686.
[23]	SIMMONS G J. The Prisoners’ Problem and the Subliminal Channel[C]// Springer. Advances in Cryptology-CRYPTO 1984. Heidelberg:Springer, 1984: 51-67.
[24]	BERNDT S, LISKIEWICZ M. Algorithm Substitution Attacks from a Steganographic Perspective[C]// ACM. The 2017 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2017: 1649-1660.
[25]	RUSSELL A, TANG Qiang, YUNG M, et al. Generic Semantic Security Against a Kleptographic Adversary[C]// ACM. The 2017 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2017: 907-922.
[26]	FISCHLIN M, MAZAHERI S. Self-Guarding Cryptographic Protocols Against Algorithm Substitution Attacks[C]// Springer. 2018 IEEE 31st Computer Security Foundations Symposium-CSF. Heidelberg: Springer, 2018: 76-90.
[27]	YAN Duli, YU Yong, LI Yannan, et al. Subversion Attack and Improvement of ECDSA Signature Scheme[J]. Journal of Software, 2023, 34(6): 2892-2905.
	严都力, 禹勇, 李艳楠, 等. ECDSA签名方案的颠覆攻击与改进[J]. 软件学报, 2023, 34(6):2892-2905.
[28]	CHEN Rongmao, WANG Yi, HUANG Xinyi. RCCA-Secure Public-Key Encryption Based on SM2[J]. Science China: Information Sciences, 2023, 53(2): 266-281.
	陈荣茂, 王毅, 黄欣沂. 国密SM2加密算法的RCCA安全设计[J]. 中国科学:信息科学, 2023, 53(2):266-281.
[29]	CHENG Zhaohui. Security Analysis of SM9 Key Agreement and Encryption[C]// Springer. Information Security and Cryptology:14th International Conference-Inscrypt 2018. Heidelberg: Springer, 2018: 14-17.
[30]	BENTAHAR K, FARSHIM P, MALONE-LEE J, et al. Generic Constructions of Identity-Based and Certificateless KEMs[J]. Journal of Cryptology, 2008, 21(1): 178-199.

符号	解释
$x\leftarrow \$ X$	从非空集合X中均匀随机选取一个元素x
$y\leftarrow \$F(x)$	随机算法F的随机输出
[i, j]	从i到j的整数集合
negl(n)	可忽略函数
poly(n)	概率多项式时间算法（Probabilistic Polynomial Time，PPT）
P+Q	两点在椭圆曲线上的加法
kP	k个P相加
$\|z\|$	z的长度
^OF	函数F的预言机
O^F(x)	x为输入询问函数F的预言机

运算符号	解释
Pair	双线性映射操作
MG₁	G₁中的点乘操作
MG₂	G₂中的点乘操作
AG₁	群G₁上的加法操作
HN	映射到[1, N-1]的哈希操作
HG₁	映射到群G₁的哈希操作
KDF	密钥派生函数操作
MAC	消息验证码操作
\|G₁\|	G₁群中元素的长度
\|G₂\|	G₂群中元素的长度
\|G_T\|	G_T群中元素的长度
\|ID\|	身份长度
\|C\|	密文长度

算法	计算开销				通信开销
算法	初始化系统	密钥提取	加密	解密	通信开销
SM9	MG₁	HG₁+MG₂	HN+2MG₁+MAC+ AG₁+Pair+KDF	Pair+KDF+ MAC	\|ID\|+\|C\|
SR-SM9	MG₁	HG₁+MG₂	2HN+3MG₁+MAC+ AG₁+Pair+KDF	Pair+KDF+ MAC	\|ID\|+\|C\|