软件学报  2014, Vol. 25 Issue (5): 1125-1131   PDF    
引用本文
禹勇, 倪剑兵, 许春香, 牛磊. 安全高效基于身份签名方案的密码学分析[J].软件学报,2014, 25(5): 1125-1131.http://www.jos.org.cn/1000-9825/4526.html   
YU Yong, NI Jian-Bing, XU Chun-Xiang, NIU Lei. Cryptanalysis of a Secure and Efficient Identity-Based Signature Scheme[J]. Ruan Jian Xue Bao/ Journal of Software, 2014, 25(5): 1125-1131.http://www.jos.org.cn/1000-9825/4526.html   
安全高效基于身份签名方案的密码学分析
禹勇1,2, 倪剑兵1, 许春香1, 牛磊1    
1 电子科技大学 计算机科学与工程学院, 四川 成都 611731;
2 School of Computer Science and Software Engineering, University of Wollongong, Australia
收稿时间:2012-10-28; 定稿时间: 2013-11-26
基金项目:国家自然科学基金（61003232，61370203，61250110543）；教育部博士点基金（20100185120012）
作者简介：倪剑兵(1988－),男,硕士生,主要研究领域 为公钥密码学. E-mail: nimengze@gmail.com
许春香(1965－),女,博士,教授,博士生导 师,主要研究领域为信息安全. E-mail: chxxu@uestc.edu.cn
牛磊(1989－),男,硕士生,主要研究领域为 公钥密码学. E-mail: uestc.nl@163.com
通讯作者：禹勇(1980－),男,山东泰安人,博士,副教 授,主要研究领域为公钥密码学. E-mail: yyucd2012@gmail.com
摘要：基于身份的数字签名方案最显著的特点是，只需要签名人的身份信息而无需签名人的证书来验证签名的有效性，这极大地简化了密钥管理.2006年，Paterson和Schuldt构造了标准模型下可证明安全的基于身份的数字签名方案，但计算效率不高.谷科等人提出了新型的改进方案来提高效率，并声称新方案在标准模型下可证明安全且比同类方案更高效.然而，新方案并不具备不可伪造性.给出了两种具体的攻击：敌手可以伪造用户的密钥或者敌手可以直接伪造任何消息的签名.进一步指出安全性证明中的缺陷，即，敌手的view与安全模拟成功的事件不独立.
关键词： 数字签名     基于身份签名     标准模型     密码学分析     可证明安全    
Cryptanalysis of a Secure and Efficient Identity-Based Signature Scheme
YU Yong1,2, NI Jian-Bing1, XU Chun-Xiang1, NIU Lei1    
1 School of Computer Science and Engineering, University of Electronics Science and Technology of China, Chengdu 611731, China;
2 School of Computer Science and Software Engineering, University of Wollongong, Australia
Corresponding author: YU Yong, E-mail: yyucd2012@gmail.com
Abstract: The distinguishing characteristic of identity-based signatures is that only the identity with no certificate of a signer is involved in the verification of a signature, which simplifies the key management procedures dramatically. A novel identity-based signature scheme that can be proven secure in the standard model was given by Paterson and Schuldt in 2006. Unfortunately, the scheme is not efficient in computation. An improvement due to Gu, et al. was proposed recently to improve the computational efficiency, and it was claimed as being provably secure in the standard model and more efficient than the known schemes in the same flavor. However, this paper shows that the new scheme by Gu, et al. is insecure by demonstrating two concrete attacks in which an adversary can not only forge the private key of an identity but also forge signatures on arbitrary message. The study also identifies a flaw in their security proofs, i.e., the view of the adversary in the security reduction is not independent of the event that the simulation succeeds.
Key words: digital signature     identity-based signature     standard model     cryptanalysis     provable security    

为了简化密钥管理,1984年,Shamir提出了基于身份的密码体制[1],将标示用户身份的唯一信息如电话号码、E-mail地址等作为用户的公钥,用户的私钥由密钥生成中心利用用户的身份和自身的主密钥生成.基于身份的密码体制具有以下3个特点:用户的公钥可以根据用户身份得到;不需要PKI基础设施;加密消息或者签名验证只需要接收人或签名人的身份信息和系统参数.因此,基于身份的密码体制减轻了用户对公钥证书的依赖,解决了公钥证书的生成、验证、存储和吊销问题.基于整数分解问题,Shamir提出了第一个基于身份的签名方案[1]. 2001年,Boneh和Franklin利用双线性对构造了第一个实用的基于身份的加密方案[2],此后,基于身份的密码体制[3,4,5,6,7,8,9]得到了快速的发展,成为10年来密码学研究领域重要的研究方向.

在安全性方面,大部分基于身份的密码方案[3,4,5]都只能在随机预言机模型(random oracle model)[10]下证明是安全的.随机预言机模型是Bellare等人于1993年提出的用于安全性证明的理想模型,此模型在理想条件下对敌手的能力进行模拟,把Hash函数看作随机函数,对于敌手的每次询问,挑战者给出一个随机应答.但是在特定的数字签名方案中,因为使用的Hash函数是具体的,对于每次Hash询问的应答是特定Hash函数的真实输出,此输出一定不是随机的,这就可能导致方案的不安全.1998年,Canetti等人[11]特意构造了一些密码方案,虽然在随机预言机下可证明是安全的,但却不安全.因此,设计在标准模型下可证明安全的密码方案更有意义和价值.

2005年,Waters[12]提出了标准模型下可证明安全的基于身份的加密方案,并利用其密钥提取算法设计出一个标准模型下安全的签名方案(记为Waters签名).2006年,Paterson等人[13]基于Waters签名[12]构造了标准模型下安全的基于身份签名方案(记为PS签名方案),具有签名长度短、不可伪造性规约到计算性Diffie- Hellman问题(CDH)等优势,但不足之处在于需要多次群G上的乘法运算,计算效率不高.针对此问题,谷科等人[14]指出:可以通过转变PS方案中的群元素乘法运算为整数加法运算的方法提高计算效率,并给出了一个具体的构造.他们声称:在标准模型下,可以证明新方案的安全性归约到CDH问题,并且比同类方案高效.

然而我们发现,文献[14]提出的方案无法达到数字签名的最基本性质——不可伪造性.给出了两种具体攻击:在第1种攻击中,敌手可以伪造任意用户的私钥,利用此私钥对任意消息签名;在第2类攻击中,敌手可以直接伪造目标用户对任意消息的签名.进一步指出文献[14]中安全性证明的缺陷:敌手的view与安全模拟成功的事件不独立.

1 谷等人方案及安全性分析

本节首先回顾文献[14]提出的改进的签名方案,然后在基于身份签名的安全模型中对方案进行安全性 分析.

1.1 谷等人方案

文献[14]提出的基于身份的数字签名方案包含以下几种算法:

(1) 系统设置(setup)

PKG选择两个q阶循环群G1,G2,q为素数,g是G1的生成元,e:G1xG1®G2表示双线性对.Hu和Hm是两个安全的Hash函数:和分别用于将身份和消息映射成nu,nm长度的比特串. PKG随机选择u¢,m¢ÎZq,nu维的向量nm维的向量其中,uiÎZq,miÎZq.随机选择xÎZq,g2ÎG1,计算g1=gx.PKG的系统参数系统主密钥为

(2) 用户密钥生成(KeyGen)

设用户身份u为一个长度为nu的比特串,VÍ{1,…,nu}表示u中比特值为1的位置i的集合.PKG随机选择rÎZq,计算用户u的私钥:

并通过安全信道将du发送给用户.用户得到私钥du后,先通过以下验证式对密钥进行检验:

如果等式成立,则证明密钥有效;否则,要求PKG重新生成密钥.

(3) 签名(sign)

密钥通过验证后,用户就可以利用它来签名消息.令m为长度为nm的消息比特串,WÍ{1,…,nm}表示m中比特值为1的位置j的集合.用户随机选择sÎZq,计算m的签名:

(4) 验证(verify)

收到消息、签名对(m,s)后,验证人检验以下验证式是否成立:

若等式成立,则签名有效;否则,签名无效.

1.2 谷科等人的方案的安全性分析

本节首先回顾基于身份数字签名的安全模型[13, 15],然后,在该模型下分析文献[14]中提出的签名方案的安全性.

1.2.1 基于身份签名的安全模型

基于身份数字签名方案的不可伪造性模型刻画了以下安全行为和目标:即使敌手具备了很强的攻击能力,即对任意身份进行密钥提取询问和对任意消息进行签名询问,它能够伪造目标身份u*对目标消息m*的有效签名的概率是可忽略的.攻击模型通过敌手和挑战者之间的如下游戏来定义:

(1) 系统设置

挑战者运行系统设置算法得到系统参数和主密钥;敌手得到系统参数,但不能获得主密钥,挑战者秘密保存主密钥.

(2) 询问

敌手向挑战者自适应地进行一系列询问,询问方式如下:

1) 密钥生成询问:敌手选择任意选择身份u进行密钥生成询问;挑战者通过运行密钥生成算法计算相应私钥du,并将du返回给敌手.

2) 签名询问:敌手任意选择身份u和消息m进行签名询问;挑战者首先通过密钥生成算法计算身份u的私钥du,然后运行签名算法计算消息m的签名s,并将签名s返回给敌手.

(3) 伪造

敌手输出身份u*对消息m*的签名s*.若以下3个条件成立,则攻击成功:

1) 敌手未对身份u*进行密钥生成询问;

2) 敌手未对(u,m)进行签名询问;

3) s*是身份u*对消息m*的有效签名.

定义1. 如果敌手A经过最多qE次密钥提取询问和qS次签名询问,至少在t时间内以不小于e的概率赢得上诉游戏,则敌手A称为基于身份签名的(e,t,qE,qS)-伪造者;如果基于身份签名方案中不存在(e,t,qE,qS)-伪造者,则称方案是(e,t,qE,qS)-安全的.

1.2.2 两种具体的攻击

虽然文献[14]在标准模型下证明了改进方案的不可伪造性可以归约到CDH假设,然而本节对新方案进行安全性分析,给出两种具体的攻击,证明其不安全,并指出文献[14]安全性证明中的缺陷.

· 第1种攻击

在第1种攻击中,敌手A能够伪造任意用户的私钥,然后利用该私钥计算任何消息的签名.敌手A与挑战者进行如下游戏:

(1) 系统生成

挑战者运行系统设置算法得到系统参数params和主密钥,挑战者秘密保存主密钥,将公开参数params=发送给敌手A.

(2) 询问

敌手A在这一阶段不进行任何询问.

(3) 伪造

目标用户的身份记为u*,V*Í{1,…,nu}表示u*中比特值为1的位置i的集合,敌手要伪造签名的目标消息为m*,W*Í{1,…,nm}表示m中比特值为1的位置j的集合.敌手A通过以下步骤伪造u*的私钥,并进一步计算消息m*的签名:

① 随机选择

② 利用扩展的欧几里得算法计算mod q;

③ 计算mod q;

④ 随机选择s*ÎZq,利用伪造的目标用户u*的私钥计算目标消息m*的签名:

.

在敌手A伪造中,容易验证是目标身份u*有效密钥,因为

计算得到的是目标用户u*对目标消息m*的一个有效签名,因为

· 第2种攻击

在第2种攻击中,敌手B可以直接伪造目标用户对任意消息的签名.敌手B与挑战者进行如下游戏:

(1) 系统生成

挑战者运行系统设置算法得到系统参数params和主密钥,挑战者秘密保存主密钥,将公开参数params=发送给敌手B.

(2) 询问

敌手B在这一阶段不进行任何询问.

(3) 伪造

目标用户的身份记为u*,V*Í{1,…,nu}表示u*中比特值为1的位置i的集合;敌手要伪造的目标消息为m*, W*Í{1,…,nm}表示m*中比特值为1的位置j的集合.敌手B通过以下步骤直接伪造目标用户u*对目标消息m*的签名:

① 随机选择

② 利用扩展的欧几里德算法计算mod q;

③ 计算mod q;

④ 为敌手B伪造的目标用户u*对目标消息m*的签名.

计算得到的是目标用户u*对目标消息m*的一个有效签名,因为

虽然文献[14]在标准模型下对该签名方案的不可伪造性给出了安全性证明,但是我们发现,其安全性证明过程存在缺陷,正是此缺陷导致上述伪造攻击的存在.在文献[14]的安全性证明中,挑战者令lu=2(qe+qs),lm=2qs,随机选择且0≤ku≤nu,0≤km≤nm,对于给定的qe,qs,nu,nm,假设有lu(nu+1)<q,lm(nm+1)<q;随机选择长度为nu的向量其中,随机选择长度为nm的向量其中,定义两个函数:挑战者构造:

u¢=x¢-lu×ku,ui=xi(1≤i≤nu), m¢=y¢-lm×km, mj=yj(1≤j≤nm).

在这种设置下得到完整的安全性证明见文献[14].

最后,如果在密钥生成询问、签名询问和签名伪造这3个过程中,挑战者都不会终止,即以下3个条件同时满足,则挑战者能成功解决CDH问题的一个实例:

(1) 密钥生成询问阶段,对所有的身份ui,F(ui)¹0 mod lu;

(2) 签名询问阶段,对所有的消息mi,K(mi)¹0 mod lm;

(3) 签名伪造阶段,对目标身份u*和目标消息m*,F(u)=0 mod q且K(m)=0 mod q.

然而容易看出,敌手在安全性证明中的view与挑战者解决CDH问题成功的条件是不独立的.具体来说,挑战者能否解决CDH问题是由函数F(u)和K(m)的值决定的,而u¢,ui,m¢,mj是系统参数的一部分,对于已知的身份u和消息m,任何人都可以计算F(u)和K(m).故而在伪造阶段,在敌手输出目标用户u*对目标消息m*的伪造签名s*时,可以先计算F(u)和K(m)的值,如果F(u)=0 mod q且K(m)=0 mod q成立,则敌手不返回s*;否则,敌手将签名伪造s*返回给挑战者.因此,敌手返回给挑战者的伪造签名对应的目标身份u*和目标消息m*总能使F(u)¹0 mod q或K(m)¹0 mod q成立.条件(3)的不成立,使挑战者无法成功解决CDH问题.所以,该签名方案的不可伪造性无法归约到CDH问题.

2 结束语

文献[14]在PS签名方案[13]的基础上提出了改进的基于身份签名方案,并在标准模型下将新方案的不可伪造性规约到CDH假设.然而,本文对改进的方案[14]进行了安全性分析,发现其安全性证明过程存在缺陷,此缺陷导致签名方案容易遭受两种具体攻击.如何构造计算效率高、系统参数短、可证明安全(标准模型下)的基于身份签名,仍然是密码学研究中的一个重要问题.

参考文献
[1] Shamir A. Identity-Based cryptosystems and signature schemes. In: Blakley GR, Chaum D, des. Advances in Cryptology—CRYPTO’84. LNCS 196, Berlin: Springer-Verlag, 1985.47-53 [doi: 10.1007/3-540-39568-7_5] .
[2] Boneh D, Franklin M. Identity-Based encryption from the Weil pairing. In: Kilian J, ed. Advances in Cryptology—CRYPTO 2001. LNCS 2139, Berlin: Springer-Verlag, 2001.213-229 [doi: 10.1007/3-540-44647-8_13] .
[3] Paterson KG. ID-Based signatures from pairing on elliptic curves.Electrics Letters, 2002,38(8):1025-1026 [doi: 10.1049/el:20020 682] .
[4] Cha JC, Cheon JH. An identity-based signature from gap Diffie-Hellman groups. In: Desmedt YG, ed. Proc. of the Public Key Cryptography—PKC 2003. LNCS 2567, Berlin: Springer-Verlag, 2003.18-30. [doi: 10.1007/3-540-36288-6_2] .
[5] Xun Y. An identity-based signature scheme from the Weil pairing.IEEE Communications Letters, 2003,7(2):76-78. [doi: 10.1109/LCOMM.2002.808397] .
[6] Gu CX, Zhu YF, Pan XY. Forking lemma and the security proofs for a class of ID-based signatures. Ruan Jian Xue Bao/Journal of Software, 2007,18(4):1007-1024 (in Chinese with English abstract).http://www.jos.org.cn/1000-9825/18/1007.htm [doi: 10.1360/jos181007]
[7] Ma XL, Gu LZ, Cui W, Yang YX, Hu ZX. ID-Based transitive signature schemes without random oracle. Journal on Communications, 2010,31(5):37-43 (in Chinese with English abstract).
[8] Gu K, Jia WJ, Wang SC, Shi LW. Proxy signature in the standard model: Constructing security model and proving security. Ruan Jian Xue Bao/Journal of Software, 2012,23(9):2416-2429 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4246.htm [doi: 10.3724/SPJ.1001.2012.04246]
[9] Lu L, Hu L. Multi-Recipient public key encryption scheme based on Weil pairing. Ruan Jian Xue Bao/Journal of Software, 2008, 19(8):2159-2166 (in Chinese with English abstract).http://www.jos.org.cn/1000-9825/19/2159.htm [doi:10.3724/SP.J.1001.2008.02159]
[10] Bellare M, Rogoway P. Random oracles are practical: A paradigm for designing efficient protocols. In: Denning D, Pyle R, Ganesan R, Sandhu R, Ashby V, eds. Proc. of the 1st Conf. on Computer and Communications Security. ACM Press, 1993.62-73. [doi: 10.1145/168588.168596] .
[11] Canetti R, Goldreich O, Halevi S. The random oracle methodology, revisited.Journal of the ACM, 2004,51(4):557-594. [doi: 10.1145/1008731.1008734] .
[12] Waters B. Efficient identity-based encryption without random oracles. In: Cramer R, ed. Advances in Cryptology of EUROCRYPT 2005. LNCS 3494, Berlin: Springer-Verlag, 2005.114-127. [doi: 10.1007/11426639_7].
[13] Paterson KG, Schuldt J. Efficient identity-based signature secure in the standard model. In: Batten L, Safavi-Nain R, eds. Proc. of the ACISP 2006. LNCS 4058, Berlin: Springer-Verlag, 2006.207-222. [doi: 10.1007/11780656_18] .
[14] Gu K, Jia WJ, Jiang CL. Efficient and secure identity-based signature scheme. Ruan Jian Xue Bao/Journal of Software, 2011,22(6): 1350-1360 (in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4002.htm [doi: 10.3724/SP.J.1001.2011.04002]
[15] Li JG, Jiang PJ. An efficient and provably secure identity-based signature scheme in the standard model.Chinese Journal of Computers, 2009,32(11):2130-2136 (in Chinese with English abstract) [doi: 10.3724%2fSP.J.1016.2009.02130] .
[6] 顾纯祥,祝跃飞,潘晓豫.Forking引理与一类基于身份签名体制的安全性证明.软件学报,2007,18(4):1007-1024.http://www.jos.org.cn/1000-9825/18/1007.htm [doi: 10.1360/jos181007]
[7] 马小龙,古利泽,崔巍,杨义先,胡正名.标准模型下基于身份的传递签名.通信学报,2010,31(5):37-43.
[8] 谷科,贾维嘉,王四春,石良武.标准模型下的代理签名:构造模型与证明安全性.软件学报,2012,23(9):2416-2429.http://www.jos.org.cn/1000-9825/4246.htm[doi: 10.3724/SPJ.1001.2012.04246]
[9] 鲁力,胡磊.基于Weil对的多接收者公钥加密方案.软件学报,2008,19(8):2159-2166.http://www.jos.org.cn/1000-9825/19/2159.htm [doi: 10.3724/SP.J.1001.2008.02159]
[14] 谷科,贾维嘉,姜春林.高效安全的基于身份的签名方案.软件学报,2011,22(6):1350-1360.http://www.jos.org.cn/1000-9825/4002.htm [doi: 10.3724/SP.J.1001.2011.04002]
[15] 李继国,姜平进.标准模型下可证安全的基于身份的高效签名方案.计算机学报,2009,32(11):2130-2136. [doi: 10.3724%2fSP.J.1016.2009.02130].