聚合签名方案的安全性分析与改进
2017-08-12张永洁张玉磊王彩芬
张永洁 张玉磊 王彩芬
1(甘肃卫生职业学院 甘肃 兰州 730000) 2(西北师范大学计算机科学与工程学院 甘肃 兰州 730070)
聚合签名方案的安全性分析与改进
张永洁1张玉磊2王彩芬2
1(甘肃卫生职业学院 甘肃 兰州 730000)2(西北师范大学计算机科学与工程学院 甘肃 兰州 730070)
聚合签名可以降低签名的验证开销和签名的长度。分析三个无证书聚合签名方案的安全性,指出它们不能抵抗无证书公钥密码系统的一般用户公钥替换攻击和恶意密钥生成中心KGC伪造攻击。其中,Chen方案和喻方案既不能抵抗公钥替换攻击,也不能抵抗KGC被动攻击;张方案不能抵抗KGC主动攻击。通过具体的攻击算法和原因分析,证明该类方案不安全。对张方案进行改进,改进的方案增强了原方案的安全性。
无证书公钥密码 聚合签名 密钥生成中心 被动攻击 主动攻击
0 引 言
聚合签名[1]能够把多个同类签名聚合转换成单个签名,实现对多个用户身份的验证。聚合签名技术能够降低签名的验证计算量,缩短签名的长度[2-3]。
2001年,Al-Riyami等[4]提出无证书公钥密码体制。无证书公钥密码体制中,用户的私钥由部分私钥和秘密值组成。这样,可以克服身份公钥密码体制[5]的密钥托管问题,简化传统公钥密码的证书管理问题。基于无证书公钥密码的优势,研究者们对无证书密码方案进行了一定的研究[6-8]。
2007年,Gong等[9]提出无证书聚合签名安全模型。2010年,Zhang等[10]完善了无证书聚合签名方案的安全模型。自此,研究者对该类签名进行了相关研究[11-18]。
无证书聚合签名包含AI和AII两类攻击者[9]。AI表现为一般用户,它不能获得系统主密钥,但可以实现公钥替换攻击;AII表现为恶意KGC,它能够利用系统主密钥计算用户的部分私钥。恶意KGC攻击分为KGC被动攻击和KGC主动攻击[15]。KGC被动攻击是指KGC能够利用部分私钥进行签名伪造,KGC主动攻击是指KGC在系统建立过程中选择有利的特殊系统参数。
分析Chen、喻琇瑛和张玉磊等人分别提出的无证书聚合签名方案[12-14]的安全性,指出前两个方案存在KGC攻击和一般用户公钥替换攻击,张方案存在KGC主动攻击。针对三个方案,分别构造了攻击算法,证明以上三个方案不安全,可以实现伪造攻击。对张方案进行改进。改进方案增强了原方案的安全性。基于CDH困难问题,证明改进方案满足不可伪造性。
限于篇幅,略去对数学困难、双线性对、无证书聚合签名方案及安全模型的描述。
1 Chen方案安全性分析
首先回顾Chen方案[12],然后描述具体的攻击过程并分析方案存在攻击的原因。
1.1 Chen具体方案
Chen方案主要包括以下算法。
(2) 部分私钥生成算法:KGC计算部分私钥Si=sQi。
(4) 签名算法:用户输入公钥Xi、私钥(xi,Si)、消息mi和状态信息Δ,执行以下过程,其中1≤i≤n。
② 计算wi=H3(mi,Δ,IDi,Xi,Ri),Vi=Si+wirixiD。
③ 输出消息mi的签名σi=(Ri,Vi)。
(6) 聚合签名验证算法:输入用户身份IDi、公钥Xi、聚合签名σ=(R1,R2,…,Rn,V)、消息mi及状态信息Δ,执行以下过程,其中,1≤i≤n。
① 计算wi=H3(mi,Δ,IDi,Xi,Ri),Qi=H1(IDi),1≤i≤n。
1.2 Chen方案安全性分析
1.2.1 KGC被动攻击
当KGC获得用户对mi的签名σi=(Ri,Vi)时,可以通过以下过程实现对新消息m′的签名伪造。
(2) 伪造消息m′签名。通过以下步骤伪造签名:
② 输出消息m′的伪造签名σi=(Ri′,Vi′)。
(3) 验证签名σi=(Ri′,Vi′)的有效性。
由于以下验证等式成立,因此,签名σi=(Ri′,Vi′)有效,KGC被动攻击成功。
e(P,Vi′)=e(P,Si+tiwi′(rixiD))=
e(Ppub,Qi)e(xiP,wi′tiriD)=
e(Ppub,Qi)e(Xi,wi′Ri′)=
e(Ppub,Qi)e(wi′Ri′,Xi)
由于
验证等式成立,伪造的聚合签名有效,KGC被动攻击成功。
1.2.2 一般用户公钥替换攻击
AI类攻击者可以通过以下过程实现替换用户公钥实现,并通过获得的签名能够获得用户的部分私钥,进而可以进行签名的伪造。
(4) 攻击者利用部分私钥和替换用户公钥的秘密值可以正常执行签名算法,进行各类签名伪造。
1.2.3 原因分析
Chen方案不安全的主要原因表现在两个方面:
①AII类攻击者获得用户对mi的签名σi=(Ri,Vi)后,能够通过Vi、wi和Si=sQi计算表达式Vi=Si+wirixiD中的固定值rixiD,(其中D=H2(Δ)∈G1为固定值)。然后,KGC利用rixiD、Ri和Si成功伪造签名。
② 当AI类攻击者替换目标用户的公钥以后,可以选择新消息并提交给签名预言机,利用获得的签名σi=(Ri,Vi)可以计算出用户的部分私钥。一旦AI类攻击者获得用户的部分私钥,那么她可以代替用户实现各种密码学操作(包括签名的伪造)。
2 喻方案安全性分析
2016年,胡等[16]指出喻方案[13]存在AI类一般用户公钥替换攻击。经过分析,喻方案同时存在AII类KGC被动攻击。首先回顾喻方案,然后证明该方案存在AII类KGC被动攻击并分析原因。
2.1 喻方案
(1) 签名算法:用户输入身份IDi、公钥pkIDi=xiP、私钥(xi,dIDi=sQi)和消息mi,执行以下过程。
① 计算W=H2(P,Ppub),hi=H3(mi,IDi,pkIDi)。
(2) 聚合签名算法:输入签名σi=(Ui,Vi)后,执行以下过程,其中,1≤i≤n。
① 计算hi=H3(mi,IDi,pkIDi),W=H2(P,Ppub)。
② 验证e(P,Vi)=e(Ppub,Ui+hiQi)e(hipkIDi,W)等式是否成立。若成立,则接受签名σi。
(3) 聚合签名验证算法:验证者输入用户公钥pkIDi、消息mi,以及聚合签名σ=(U,V),执行以下过程。
① 计算Qi=H1(IDi),hi=H3(mi,IDi,pkIDi)和W=H2(P,Ppub),其中,1≤i≤n。
② 验证等式是否成立
2.2 喻方案安全性分析
2.2.1 KGC被动攻击
当KGC获得用户对mi的签名δi=(Ui,σi=(Vi,Ri)时,可以通过以下过程实现对新消息的签名伪造。
(2) 伪造消息m′的签名。任意选择Ui′∈G1,计算hi′=H3(m′,IDi,pkIDi),Vi′=sUi′+hi′(dIDi+xiW),输出伪造的签名σi=(Ui′,Vi′)。
(3) 验证签名σi=(Ui′,Vi′)的有效性。由于
e(P,Vi′)=e(P,sUi′+hi′(dIDi+xiW))=
e(P,sUi′)e(P,hi′(dIDi+xiW))=
e(Ppub,Ui′+hi′Qi,)e(hi′pkIDi,W)
成立,因此,验证等式成立,KGC被动攻击成功。
由于
验证等式成立,伪造的聚合签名有效,KGC攻击成功。
2.2.2 原因分析
3 张方案安全性分析
3.1 张方案
(1) 签名算法:输入身份IDi、公钥Pi=xiP、私钥(xi,Di=sQi)和消息mi,执行以下过程。
② 计算Vi=Di+hiriT+xiQ,输出消息mi对应的签名σi=(Ui,Vi)。
3.2 张方案安全性分析
张方案中若KGC在“系统建立算法”中选择特殊的生成元Q=tP,则KGC很容易计算签名表达式Vi=Di+hiriT+xiQ中的固定值xiQ。即使KGC不了解用户的秘密值xi,也可以扮演合法用户对任意消息伪造签名。具体攻击过程如下:
(2) 计算固定值。KGC计算xiQ=xitP=tPi。
(3) 伪造签名并验证。由于KGC了解部分私钥,固定值xiQ,因此,它可以计算任意消息的签名。
张方案的聚合签名验证等式中,由于没有出现消息(m1,m2,…,mn),因此,即使聚合验证等式成立也无法保证签名σ=(U,V)是用户(u1,u2,…,un)对消息(m1,m2,…,mn)签名的聚合,所以,张方案的聚合签名构造无效。
4 改进的无证书聚合签名方案
4.1 具体的改进方案
为了提升张方案的安全性,克服KGC主动攻击,本文提出一个改进的无证书聚合签名方案。具体方案如下:
(2) 部分私钥生成算法和用户密钥生成算法与原方案相同。其中,Qi=H1(IDi),用户完整私钥和公钥分别为(xi,Si=sQi)和Pi=xiP。
(3) 签名算法:
② 计算T=H2(Ppub),W=H3(Ppub),Vi=Di+riT+hixiW,输出消息mi的签名σi=(Ui,Vi)。
(5) 聚合签名验证算法:
① 计算hi=H0(mi,IDi,Pi,Ui),Qi=H1(IDi)和T=H2(Ppub),W=H3(Ppub)。
4.2 改进方案的安全性证明
定理1如果敌手AI以不可忽略的概率实现签名伪造,必定存在算法可以输出CDH困难问题的解。改进方案针对AI类攻击的不可伪造性证明过程与原方案相似,限于篇幅,略去该部分。以下证明改进方案针对AII类攻击的不可伪造性。
定理2如果敌手AII以不可忽略的概率实现签名伪造,必定存在算法B可以输出CDH困难问题的解。
证明:挑战者B输入(P,aP,bP),令Ppub=sP,系统参数为{G1,G2,e,P,Ppub,H0,H1,H2,H3},发送系统参数和s给AII。
B通过列表L0~L3和L保存H0~H3预言机询问、公钥询问和秘密值询问过程中产生的数据。AII执行以下询问。
(2)H2询问:B保持列表,若L2表存在询问项则直接返回Ti;否则,B选择并计算,增加到L2表并返回Ti。
(4) 秘密值询问:AII询问IDi秘密值时,B查L表,若存在对应IDi则直接返回,否则B执行“公钥询问”得到(IDi,xi,Pi,ci)。若ci=1,则终止;否则ci=0,B返回xi给AII。
因此,改进方案能够抵抗AII恶意KGC的攻击。
5 结 语
分析Chen方案、喻方案和张方案的安全性,指出它们存在一般用户公钥替换攻击和KGC伪造攻击。通过构造的攻击算法,证明Chen方案和喻方案无法抵抗公钥替换攻击和KGC被动攻击,张方案无法抵抗KGC主动攻击。最后,对张方案进行改进。改进方案不仅具有与原方案相同的计算效率,同时,改进的方案增强了原方案的安全性,可以抵抗AII攻击。设计无证书聚合签名方案时,不仅要考虑方案的计算效率,更要重视方案的安全性。
[1] Boneh D,Gentry C,Lynn B,et al.Aggregate and verifiably encrypted signatures from bilinear maps[C]//Proceedings of EUROCRYPT’03,Berlin,Springer-Verlag,2003:416-432.
[2] Chen C M,Lin Y H,Lin Y C,et al.RCDA:recoverable concealed data aggregation for data integrity in wireless sensor networks[J].IEEE Transactions on Parallel and Distributed Systems,2012,23(4):727-734.
[3] Xiong Hu,Wu Q H,Chen Z.An efficient provably secure certificateless aggregate signature applicable to mobile computation[J].Control and Cybernetics,2012,41(2):373-391.
[4] Al-riyami S S,Paterson K.Certificateless Public Key Cryptography[C]//Proceedings of the ASIACRYPT2003.Berlin,Germany:Springer-Verlag,2003:452-473.
[5] Shamir A.Identity-based cryptosystems and signature schemes[C]//Proceedings of the CRYPTO1984.Berlin,Springer,1985:47-53.
[6] Shen L,Zhang F,Sun Y.Efficient revocable certificateless encryption secure in the standard model[J].The Computer Journal,2014,57(4):592-601.
[7] 周彦伟,杨波,张文政.高效可证安全的无证书聚合签名方案[J].软件学报,2015,26(12):3204-3214.
[8] 孙银霞,张福泰,沈丽敏.抗签名密钥泄露的可撤销无证书签名[J].软件学报,2015,26(12):3196-3203.
[9] Gong Z,Long Y,Hong X,et al.Two certificateless aggregate signatures from bilinear maps[C]//Proceeding of the SNPD 2007.IEEE Computer Society,2007:188-193.
[10] Zhang Lei,Qin Bo,Wu Qianhong,et al.Efficient many-to-one authentication with certificateless aggregate Signatures[J].Computer Networks,2010,54(14):2482-2491.
[11] 杜红珍,黄梅娟,温巧燕.高效的可证明安全的无证书聚合签名方案[J].电子学报,2013,41(1):72-76.
[12] Chen Yu-Chi,Horng Gwoboa,Liu Chao-Liang,et al.Efficient Certificateless Aggregate Signature Scheme[J].Journal of Electronic Science and Te6chnology,2012,10(3):209-214.
[13] 喻琇瑛,何大可.一种新的无证书聚合签名[J].计算机应用研究,2014,31(8):2485-2487.
[14] 张玉磊,周冬瑞,李臣意,等.高效的无证书广义指定验证者聚合签名方案[J].通信学报,2015,36(2):1-8.
[15] Au M,Mu Y,Chen J,et al.Malicious KGC attack in certificateless cryptography[C]//Proceeding of the ASIACCS2007.NewYork,ACM Press,2007:302-311.
[16] 胡江红,杜红珍,张建中.两类无证书聚合签名方案的分析与改进[J].山东大学学报(理学版),2016,51(7):107-114.
SECURITYANALYSISANDIMPROVEMENTOFAGGREGATESIGNATURESCHEMES
Zhang Yongjie1Zhang Yulei2Wang Caifen2
1(GansuHealthVocationalCollege,Lanzhou730000,Gansu,China)2(CollegeofComputerScienceandEngineering,NorthwestNormalUniversity,Lanzhou730070,Gansu,China)
Aggregate signature can reduce the cost of signature verification and the length of the signature. First, we analyzed security of three certificateless aggregation signatures. We allowed certificateless public key cryptosystems to attack them. These attacks: general user public key replacement attack and malicious key generation center KGC forged attack. And Chen program and Yu scheme cannot resist the public key to replace the attack, nor resistance to KGC passive attack. Zhang program cannot resist KGC active attack. Through the specific attack algorithm and cause analysis, proved that the program is not safe. We improved the Zhang’s scheme to strengthen the security compared with the original program.
Certificate less public key cryptography Aggregate signature Key generation center Passive attack Initiative attack
2016-09-02。国家自然科学基金项目(61163038);甘肃省高等学校科研项目(2015B-220,2013A-014)。张永洁,副教授,主研领域:信息安全。张玉磊,副教授。王彩芬,教授。
TP309
A
10.3969/j.issn.1000-386x.2017.08.055