几个无证书签名方案的伪造攻击

王菁，李祖猛

几个无证书签名方案的伪造攻击

王菁1，李祖猛2

（1. 广州市信息工程职业学校基础部，广东 广州 510640；2. 广东科学技术职业学院计算机工程技术学院（人工智能学院），广东 珠海 519090）

自2003年Al-Riyami和Paterson首次提出无证书公钥密码体制的概念和第一个无证书签名方案以来，许多无证书签名方案相继被提出。汤永利等提出了9个无双线性对运算的无证书签名方案，并声称这些无证书签名方案在椭圆曲线离散对数困难性假设下可证明是安全的。通过对这些无证书签名方案进行安全性分析后，发现其中的5个可证明安全的无证书签名方案不能抵抗替换公钥攻击，并且这5个无证书签名方案中的3个签名方案即使在不替换用户公钥的情况下，攻击者也可以利用用户的原始公钥对任意消息伪造出有效的签名。给出了具体的伪造攻击方法，证明了这5个无证书签名方案是不安全的。

无证书签名；椭圆曲线；离散对数；公钥替换攻击

1 引言

在2003年亚密会上，Al-Riyami和Paterson[1]首次提出了无证书公钥密码体制的概念，并且给出了第一个无证书签名方案。在无证书公钥密码体制中，密钥生成中心（KGC，key generation center）和用户一起完成用户的部分密钥生成过程，即用户密钥的一部分数据由KGC产生，然后KGC将其安全地传输给用户，用户自己产生密钥的另外一部分数据，这两部分密钥数据组合在一起构成用户的完整密钥。这种产生密钥的方式使KGC不能获知用户的完整私钥，进而解决了基于身份的密码体制[2]中的密钥托管问题，而且在无证书公钥密码体制中，因为不再需要证书中心（CA）对用户的证书进行管理和维护，解决了传统基于PKI公钥密码体制[3]的证书管理问题，使无证书公钥密码体制受到了广泛的关注。

无证书签名是无证书公钥密码体制中的研究热点之一。自Al-Riyami和Paterson在文献[1]中提出第一个无证书签名方案以来，很多无证书签名方案相继被提出[4-9]。在无证书公钥密码体制中，因为用户的公钥无法认证，所以无证书公钥密码方案的设计必须考虑抵抗替换公钥攻击。另外，在无证书公钥密码体制中，KGC参与用户私钥的部分数据产生，所以必须考虑恶意不诚实KGC的伪造攻击。Huang等[10]提出的无证书签名方案的安全模型定义了普通攻击者、强攻击者、超级攻击者。2012年，王圣宝等[11]基于离散对数困难问题，提出了一个不使用双线性对的无证书签名方案，并在随机预言模型中给出了安全性证明。但王亚飞等[12]指出文献[11]是完全不安全的，即攻击者可以获取用户的私钥，并且基于椭圆曲线离散对数问题提出了新的方案，同时在随机预言模型下给出了新方案的安全性证明。但樊爱苑等[13]对文献[12]中的新方案进行安全性分析后，指出其难以抵抗不诚实KGC下的公钥替换攻击，并针对此安全缺陷，改变传统无证书算法顺序，提出了能够抵抗不诚实KGC公钥替换攻击的新方案，且新方案避开了双线性运算和逆运算，提升了运算效率，声称其新方案在自适应选择消息攻击下是存在性不可伪造的。2016年，汤永利等[14]给出了针对文献[13]中新方案的一个伪造攻击，结论表明第I类强攻击者[10]能成功伪造任意用户对任意消息的有效签名，并基于椭圆曲线离散对数困难性假设提出了9个新的改进方案，声称其改进方案中的前两种方案能够抵抗第I类超级攻击者[10]、第II类超级攻击者[10]的攻击，改进方案中的第3~9种方案能够抵抗第I类强攻击者[10]、第II类超级攻击者的攻击。

本文对汤永利等的9个无证书签名方案[14]进行安全性分析后，发现其中的第1、2、5、8、9这5个无证书签名方案不能抵抗替换公钥攻击，并且其中第5、8、9这3个方案即使不替换公钥，攻击者也可以利用用户的原始公钥对任意消息伪造出有效的签名。分析结论表明，文献[14]中的这5个签名方案是不安全的。

2 预备知识

2.1 困难问题与安全假设

2.2 无证书签名方案的形式化定义

（1）系统参数建立算法

（2）部分私钥生成算法

（3）用户秘密值生成算法

（4）用户私钥生成算法

（5）用户公钥生成算法

（6）签名算法

（7）验证算法

3 汤永利等给出的签名方案

针对樊爱宛等方案[13]存在的安全漏洞，汤永利等人2016年在文献[14]中基于椭圆曲线离散对数困难假设提出了一类改进的可证明安全的无证书签名方案，具体描述如下。

（1）系统参数建立算法

（2）部分私钥生成算法

（3）用户秘密值生成算法

（4）用户私钥生成算法

（5）用户公钥生成算法

（6）签名算法

（7）验证算法

表1 签名与验证

4 替换公钥攻击

4.1 签名方案1的攻击

攻击者Eve执行以下步骤即可成功伪造签名：

4.2 其他签名方案的攻击

根据以上对签名方案1的替换公钥攻击与分析可知，文献[14]给出的签名方案2、5、8、9都可以利用类似签名方案1中的攻击方法进行替换公钥攻击，具体的替换公钥攻击过程在此不再赘述。

4.3 替换公钥攻击原因分析

具有Rafael-Ricardo无证书一般模式特征的签名方案，可以抵抗一般用户的公钥替换攻击[15]。所以文献[14]中给出的3、4、6、7方案可以抵抗前述的替换公钥攻击，具体证明过程可以参考文献[15]。

5 其他类型的伪造攻击

5.1 签名方案5的攻击

5.2 其他签名方案的攻击

根据以上对签名方案5的伪造攻击与分析可知，文献[14]中给出的签名方案8、9的验证等式分别为

显然这两个签名方案与文献[14]中签名方案5存在相同的安全漏洞，可以利用与4.1节中类似的伪造攻击方法在不替换用户公钥的情况下，对任意选择的消息进行伪造签名，具体攻击过程在此不再赘述。

5.3 攻击原因分析

6 结束语

由于无证书签名体制不存在密钥托管问题，同时在验证签名过程中无须验证签名者公钥的合法性，所以无证书公钥密码体制的研究受到了较高的关注。本文对文献[14]中的9个无证书签名方案进行安全性分析后，发现其中的5个方案不能抵抗替换公钥攻击，并且其中的3个签名方案即使在不替换用户公钥的情况下，攻击者也可以对任意选择的消息伪造出有效的签名，并给出了具体的攻击方案。分析结论表明这5个无证书签名方案是不安全的。

[1] AL-RIYAMI S S, PATERSON K G. Certificateless public key cryptography[C]//Advances in Cryptology-ASIACRYPT 2003. 2013: 452-473.

[2] SHAMIR A. Identity-based cryptosystems and signature schemes[C]// Advances in Cryptology-CRYPTO’84. 1985: 47-58.

[3] DIFFIE W, HELLMAN M E. New directions in cryptography[J]. IEEE Transactions on Information Theory, 1976, 22(6): 664-654.

[4] ISLAM S H, BISWAS G P. Provably secure and pairing-free certificateless digital signature scheme using elliptic curve cryptography[J]. International Journal of Computer Mathematics, 2013, 90(11): 2244-2258.

[5] FENG S R, MO J, FENG S R, et al. An efficient and provably secure certificateless short signature scheme[C]//International Conference on Computer Science & Electronics Engineering. 2013.

[6] GONG P, LI P. Further improvement of a certificateless signature scheme without pairing[J]. International Journal of Communication Systems, 2014, 27(10): 2083-2091.

[7] ISLAM S H, OBAIDAT M S. Design of provably secure and efficient certificateless blind signature scheme using bilinear pairing[J]. Security and Communication Networks, 2015, 8(18): 4319-4332.

[8] ALLAM A M, ALI I A, MAHGOUB S M. A provably secure certificateless organizational signature schemes[J]. International Journal of Communication Systems, 2017, 30(5): 1760-1768.

[9] KYUNG-AH S. A new certificateless signature scheme provably secure in the standard model[J]. IEEE Systems Journal, 2018:1-10.

[10] HUANG X, MU Y, SUSILO W, et al. Certificateless signature revisited[J]. Lecture Notes in Computer Science, 2007, 4586: 308-322.

[11] 王圣宝, 刘文浩, 谢琪. 无双线性配对的无证书签名方案[J]. 通信学报, 2012, 33(4): 93-98.

WANG S B, LIU W H, XIE Q. Certificateless signature scheme without bilinear pairings[J]. Journal on Communications, 2012, 33(4): 93-98.

[12] 王亚飞, 张睿哲. 强安全无对的无证书签名方案[J]. 通信学报, 2013, 34(2): 94-99, 108.

WANG Y F, ZHANG R Z. Strongly secure certificateless signature scheme without pairings[J]. Journal on Communications, 2013, 34(2): 94-99, 108.

[13] 樊爱宛, 杨照锋, 谢丽明. 强安全无证书签名方案的安全性分析与改进[J]. 通信学报, 2014, 35(5): 118-123.

FAN A W, YANG Z F, XIE L M. Security analysis and improvement of strongly secure certificate less signature scheme[J]. Journal on Communications, 2014, 35(5): 118-123.

[14] 汤永利, 王菲菲, 叶青, 等. 改进的可证明安全无证书签名方案[J].北京邮电大学学报, 2016, 39(1): 112-116.

TANG Y L, WANG F F, YE Q, et al. Improved provably secure certificateless signature scheme[J]. Journal of Beijing University of Posts and Telecommunications, 2016, 39(1): 112-116.

[15] RAFAEL C, RICARDO D. Two notes on the security of certificate- less signatures[C]//International Conference on Provable Security. Springer-verlag, 2007. 2007: 85-102.

Forgery attacks on several certificateless signature schemes

WANG Jing1，LI Zumeng2

1. Foundation Department, Guangzhou Information Engineering Vocational School, Guangzhou 510640, China 2. Computer Engineering Technical College(Artificial Intelligence College), Guangdong Polytechnic of Science and Technology, Zhuhai 519090, China

Since Al-Riyami and Paterson proposed the novel concept of certificateless cryptography and the first certificateless signature scheme in 2003, a lot of certificateless signature schemes were proposed one after another. Recently, Tang et al proposed nine certificateless signature schemes without bilinear pairing. Although they demonstrated that their schemes were unforgeable under the assumption of elliptic curve discrete logarithmic problem, it can be found that five of their schemes could not resist the public key substitution attack, the attacker could use the user's original public key to forge a valid signature for three of these schemes. The attack methods are to demonstrate that prove five certificateless signature schemes are insecure.

certificateless signature, elliptic curve, discrete logarithm problem, public key replacement attack

TP309.7

A

10.11959/j.issn.2096−109x.2020039

2019−05−09；

2019−07−29

李祖猛，zumengli@126.com

王菁, 李祖猛. 几个无证书签名方案的伪造攻击[J]. 网络与信息安全学报, 2020, 6(3): 108-112.

WANG J, LI Z M. Forgery attacks on several certificate lesssignature schemes[J]. Chinese Journal of Network and Information Security, 2020, 6(3): 108-112.

王菁（1983− ），女，山西运城人，硕士，主要研究方向为最优化理论与方法、网络算法及其在通信网中的应用。

李祖猛（1984− ），男，山东临清人，硕士，主要研究方向为密码学与信息安全。