Subversion Attacks and Countermeasures of SM9 Encryption

doi:10.3969/j.issn.1671-1122.2024.06.002

Abstract

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

CLC Number:

TP309

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

Figures/Tables 6

References 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\|