国密SM2加密算法的RCCA安全设计_陈荣茂.pdf

SCIENTIA SINICA Informationis中国科学:信息科学2023年第53卷第2期:266281c 2023中国科学 杂志社论文国密SM2加密算法的RCCA安全设计陈荣茂1,王毅1,黄欣沂2*1.国防科技大学计算机学院,长沙 4100732.香港科技大学(广州)信息枢纽人工智能学域,广州 511466*通信作者.E-mail:xinyiust.hk收稿日期:20220713;修回日期:20220825;接受日期:20220831;网络出版日期:20230203国家自然科学基金(批准号:62122092,62032005,61702541)资助项目摘要国密SM2密码算法已经成为保障我国网络信息系统安全自主可控的关键技术.然而近期研究发现,SM2加密算法在实际部署应用时面临高效的算法替换攻击.该种攻击可以从当前的密文预测下一次加密所使用的随机数,从而可以在不知道解密密钥的情况下成功解密后续密文.密码逆向防火墙技术已被证实可以有效抵抗该种攻击,但其要求密文具有可重随机性,与SM2加密算法本身所具备的CCA(chosen-ciphertext attack)安全性相冲突.针对该问题,本文改进SM2加密算法,构造了具有RCCA(可重放CCA)安全性的公钥加密方案.该方案具有与SM2加密算法近似的安全性,且同时支持密文重随机操作,因此可以有效兼容密码逆向防火墙.方案的设计遵循Phan等提出的OAEP三轮构造范式,结合SM2加密算法进行改进,并在随机预言机模型下给出了严谨的安全证明.本文提出了首个基于国密算法的可重随机RCCA公钥加密方案,研究结果有助于提升SM2密码算法在实际应用中的安全性.关键词SM2,加密算法,RCCA,可重随机性,密码逆向防火墙1引言安全性是密码算法的根本属性,如何设计安全的密码算法一直以来都是密码学研究人员所面临的挑战性难题.在早期阶段,密码算法设计主要依赖人工经验和复杂的机械装置,缺乏科学的理论指导,导致算法安全问题频出.20世纪80年代,麻省理工学院(Massachusetts Institute of Technology)的Goldwasser和Micali1首次提出可证明安全技术,通过采用计算复杂性理论,将攻破密码算法与解决数学难题建立近似等价关系,为密码算法的安全性提供了科学的理论依据.他们的工作奠定了现代密码学可证明安全理论的基础,使得密码学从艺术走向科学,并极大地促进密码技术应用的蓬勃发展.引用格式:陈荣茂,王毅,黄欣沂.国密SM2加密算法的RCCA安全设计.中国科学:信息科学,2023,53:266281,doi:10.1360/SSI-2022-0282Chen R M,Wang Y,Huang X Y.RCCA-secure public-key encryption based on SM2(in Chinese).Sci Sin Inform,2023,53:266281,doi:10.1360/SSI-2022-0282中国科学:信息科学第 53 卷第 2 期可证明安全的鲁棒性依赖于一系列的条件假设.其中一个非常重要的假设是密码算法的实际部署严格遵守相应的标准规范.然而2013年的“斯诺登事件”以及越来越多的供应链攻击事件表明,实际生活中用户所使用的密码系统可能偏离应该遵守的部署规范,甚至遭受恶意篡改植入隐蔽后门,使得攻击者可以获取系统密钥,彻底破坏密码系统安全.2014年国际密码年会上,Bellare等2首次提出了“算法替换攻击”(algorithm substitution attack)的概念,展示了如何通过对加密算法进行隐蔽篡改,在用户无法察觉的情况下实现加密算法的密钥渗漏.事实上,在早期阶段,Yung等3也提出了类似的攻击思想,即“盗码学攻击”(kleptographic attack).该攻击也是通过设计隐蔽后门窃取算法密钥.然而由于当时密码技术发展处在比较早期的阶段,该种攻击在学术界并没有得到广泛的重视.因此,“算法替换攻击”可以看作是“盗码学攻击”的延伸.2013年的“斯诺登事件”促使了越来越多的学者相信该种攻击存在于现实世界中,并投入精力开展研究.商用密码算法(SM系列)是我国自主设计的密码算法,近年来已经在越来越多的行业得到推广应用4,5,为实现我国网络信息系统自主可控提供了关键技术支撑.然而,近期黄等6研究发现,SM2加密算法面临极其高效的算法替换攻击威胁.攻击者通过修改加密算法中随机数的选取方式,可以从两个连续的密文恢复出整个底层明文.考虑到SM2密码算法的重要性,本文拟重点针对SM2加密算法,设计能够抵抗算法替换攻击的防护技术,强化SM2加密算法安全保障功能.事实上,目前学术界在算法替换攻击防护研究方面已经取得了若干积极进展.根据防护机制的核心思想,主要分为阻止型(prevention-based)和检测型(detection-based).前者假设存在可信的“密码逆向防火墙”(cryptographic reverse firewall)7,通过重随机的方式净化密码算法输出,消除可能携带的隐蔽信息.后者假设存在可信的“看护犬”(watchdog)对组成密码算法的各个模块进行标准测试8,确保通过测试的模块所组装的算法能够抵抗算法替换攻击.这两种类型的防护方法所依赖的假设不同,然而密码逆向防火墙(简称逆向防火墙)因为其简洁的工作模式,被认为具有较高的实用性,也因此得到了学术界的广泛研究.逆向防火墙设计所面临的主要难点是如何在不影响原有算法功能的前提下,对算法输出进行重随机操作,从而消除可能携带的潜在信息.然而对于具有标准安全性即适应性选择密文攻击(chosen-ciphertext attack,CCA)安全的公钥加密算法而言,重随机操作会导致密文无法被接收者正常解密.针对该问题,Dodis等9在2016年国际密码年会上指出,可重放适应性选择密文攻击(replayable chosen-ciphertext attack,RCCA)安全是一种理想的解决方案.具备该安全性的公钥加密方案可以在提供近似CCA安全保障的同时支持对密文的重随机化操作.因此,本文主要考虑如何对CCA安全的SM2加密算法进行拓展设计,构造具有RCCA安全性的SM2加密方案变体,从而实现逆向防火墙的兼容性,抵抗潜在的算法替换攻击.1.1本文贡献针对SM2加密密文不具备可重随机性的问题,本文提出了具有可重随机RCCA安全性的公钥加密方案.方案设计的核心思想是采用Phan等10提出的OAEP三轮范式,将其应用于SM2加密算法得到RCCA安全变体,并在随机预言机模型下证明该方案满足Canetti等11所定义的RCCA安全性.此外,相比原有的SM2公钥加密算法,该方案包含了一个新的密文重随机化算法,能够在不影响密文可解密性的情况下对密文进行修改,从而支持逆向防火墙对密文进行净化操作,消除算法替换攻击所引起的潜在信息渗漏.本文所设计的方案是首个基于国密算法的可重随机RCCA公钥加密方案,研究结果有助于提升SM2密码算法在实际应用中的安全性.267陈荣茂等:国密 SM2 加密算法的 RCCA 安全设计1.2相关工作本小节简要介绍现有可重随机RCCA安全的公钥加密方案.Groth12首次提出了在通用群模型(generic group model)下的可重随机RCCA安全的公钥加密方案.该方案的缺点在于密文大小随消息比特长度线性增长.标准模型下的可重随机RCCA安全的公钥加密方案则由Prabhakaran和Rosulek13在2007年国际密码年会上首次提出.该方案的核心思路是针对Cramer-Shoup密文的变种应用双股结构实现可重随机性与抗主动攻击安全之间的平衡.遗憾的是,该方案并不具有匿名性.而在RCCA安全性下同时实现可重随机性和匿名性对于提升现有隐私保护应用的安全性具有重要意义.该问题一直未能得到解决,直到Wang等14在2021年国际密码年会上提出了基于哈希证明系统的具有匿名性的可重随机RCCA加密方案框架.此外,一些工作在构造可重随机RCCA加密方案的同时实现了新的性质.Chase等15提出使用可延展的非交互零知识证明系统构造具有公开可验证性的加密方案.Libert等16尝试对Chase等方案的效率进行优化,但非交互零知识证明系统的应用仍然带来了较大的计算开销和密文大小.为此,Faonio等17提出了基于MDDH假设的方案构造,将密文大小减少至只有6个群元素.该方案同样基于椭圆曲线构造,但其加解密过程涉及许多耗时的双线性对运算,因此效率比较低.随后,Faonio和Fiore18在随机预言机模型下提出了更为高效的RCCA方案,但该方案仅满足弱可重随机性.近来,Wang等19将RCCA安全性拓展至标识加密的背景下,提出了ID-RCCA安全性,并给出了具有匿名性的可重随机ID-RCCA标识加密构造方案.该方案可用于构造基于标识的混淆网络,以实现对隐私保护应用中恶意滥用行为的审计.1.3本文组织结构第2节回顾公钥加密方案、单向陷门函数、困难性假设以及安全性定义等预备知识.第3节重点阐述了本文所提出的新型公钥加密方案,并详细给出了该方案在随机预言机模型下的RCCA安全性分析.第4节对本文工作做了总结.2预备知识2.1符号表示令poly()表示关于的多项式函数.给定函数f():N R+,若对于任意多项式函数poly(),存在正整数Nc使得f()Nc成立,那么函数f()是可忽略的.令negl()表示任意关于的可忽略函数.对于任意非空集合X,x$X表示从X中随机选取元素x.对于任意随机性算法F(),y$F(x)表示算法F输出随机结果y.对于任意确定性算法F(),y F(x)表示算法F输出确定结果y.2.2公钥加密方案定义1(公钥加密方案)一个公钥加密方案=(KGen,Enc,Dec)由以下3个算法组成:密钥生成算法KGen(1),该算法输入安全参数,输出公私钥对(pk,sk);加密算法Enc(pk,M),该算法输入公钥pk和明文M M,输出密文 CT;解密算法Dec(sk,),该算法输入私钥sk和密文,输出明文M,其中集合M和CT分别表示明文空间和密文空间.268中国科学:信息科学第 53 卷第 2 期图1SM2 公钥加密方案Figure 1SM2 public key encryption公钥加密方案需要满足如下正确性:对于任意(pk,sk)$KGen(1),M$M,以下公式成立:PrDec(sk,)=M:$Enc(pk,M)6 negl().定义2(可重随机公钥加密方案)令=(KGen,Enc,Dec)为一个公钥加密方案.当方案满足以下两个条件时,我们称该公钥加密方案是可重随机的.(1)存在概率多项式时间算法Rerand.该算法输入公钥pk和密文,输出新密文;(2)对于任意(pk,sk)$KGen(1),$CT,以下公式成立:PrDec(sk,)=Dec(sk,):$Rerand(pk,)6 negl().若对于任意(pk,sk)$KGen(1),M$M,$Enc(pk,M),算法Rerand(pk,)和Enc(pk,M)输出密文的分布相同,那么是完美可重随机的.SM2公钥加密方案如图1所示,其中P为具有素数阶n的椭圆曲线循环群中随机选取的生成元,KDF为输入字符串S和整数输出比特长度为的字符串的密钥派生函数,H为密码杂凑函数.2.3单向陷门函数定义3(单向陷门函数)令f:E R F为一个陷门函数.若对于任意概率多项式时间敌手A,以下优势是可忽略的,则函数f满足单向性:Advowf(1)=PrASamef(y)=x:x$E,w$R,y=f(x,w),其中Samef(y,y)是一个判断f1(y)=f1(y)是否成立的预言机.269陈荣茂等:国密 SM2 加密算法的 RCCA 安全设计2.4困难性假设定义4(gap Diffie-Hellman(GDH)困难性假设20)令为安全参数,G为一个具有素数阶p的循环群,g为群G的任意生成元.若GDH困难性假设在群G上成立,则对于任意概