基于身份的认证密钥协商协议的安全分析与改进.doc

第12期汪小芬等：基于身份的认证密钥协商协议的安全分析与改进21基于身份的认证密钥协商协议的安全分析与改进汪小芬1,2, 陈原1, 肖国镇1(1. 西安电子科技大学 综合业务网国家重点实验室，陕西 西安 710071；2. 电子科技大学 计算机学院，四川 成都 610054)摘 要：对基于身份的标准模型下可证明安全的认证密钥协商协议进行安全性分析，发现恶意的密钥生成中心（PKG, private key generator）能计算出所有的会话密钥，即它在无会话密钥托管模式下不满足PKG前向安全性。因此，为满足无托管的要求，提出一个改进的基于身份的认证密钥协商协议，并在标准模型下证明其为安全的认证密钥协商协议。结果表明，改进后协议满足完善前向安全性和PKG前向安全性。关键词：基于身份的认证密钥协商；完善前向安全性；PKG前向安全性；标准模型中图分类号：TN918.1 文献标识码：A 文章编号：1000-436X(2008)12-0016-06Analysis and improvement of an ID-based authenticated key agreement protocol WANG Xiao-fen1,2, CHEN Yuan1, XIAO Guo-zhen1(1. National Key Lab of Integrated Service Networks, Xidian University, Xian 710071, China;2. School of Computer Science and Technology, UESTC, Chengdu 610054, China)Abstract: The security of a recently proposed ID-based authenticated key agreement protocol was analyzed. Although it is provably secure in the standard model, a malicious PKG (private key generator) can still obtain all of the agreed session keys, that is, it doesnt provide PKG-forward secrecy in escrowless mode. To satisfy the security requirement in escrowless mode, an improved version of the protocol was presented and it was proved to be a secure authenticated key agreement in the standard model. Results show that it provides perfect forward secrecy and PKG-forward secrecy.Key words: ID-based authenticated key agreement; perfect forward secrecy; PKG-forward secrecy; standard model1 引言密钥协商是安全通信的重要环节。通过密钥协商协议，可在通信节点之间建立共享会话密钥，以便实现开放网络中的安全通信。收稿日期：2008-06-21；修回日期：2008-10-24基金项目：国家自然科学基金资助项目（60473028,60603010）；陕西省自然科学基金资助项目(2006F19)Foundation Items: The National Natural Science Foundation of China (60473028,60603010); The Natural Science Foundation of Shanxi Province (2006F19)Diffie和Hellman提出第一个两方的密钥协商协议1。自Shamir提出基于身份的密码系统2以来,利用Shamir的密钥构造方法，研究者们相继提出一些基于身份的密钥协商协议3,4。2001年Boneh等人利用双线性对提出基于身份的加密方案5。此后大量文章利用双线性对构建基于身份的密钥协商协议6,7，然而，这些协议都不满足完善前向安全性和PKG前向安全性。尽管Shim的协议8满足完善前向安全性，但对于中间人攻击是脆弱的9。McCullagh等提出一种有效的密钥协商协议10，然而他们的协议无法抵抗密钥泄露伪装攻击11。Chen等人的协议12首次在随机预言机模型下证明其安全性，但他们的协议也不满足完善前向安全性和PKG前向安全性。1993年Bellare和Rogaway提出基于随机预言机的安全模型13。在该模型中，散列函数被模拟为随机预言机，随机预言机模型在很多方案的安全性证明中起到了关键作用。但是，近年来人们逐渐认识到某些在随机预言机模型下可证明安全的方案在实际应用中并不安全14，因为散列函数不能真正模拟随机预言机。因此，在不借助随机预言机的标准模型下可证明安全的方案更具有实际意义。2007年Wang等利用Gentry的基于身份的加密方案15，提出第一个标准模型下可证明安全的基于身份的密钥协商协议16。对其无会话密钥托管模式下的密钥协商协议进行安全性分析后，发现该协议不能满足PKG前向安全性，恶意的密钥生成中心（PKG）能计算出所有的会话密钥。因此，针对无托管的要求,本文提出一个改进的基于身份的认证密钥协商协议,在标准模型下证明新协议的安全性，并且分析了新协议满足完善前向安全性和PKG前向安全性。2 预备知识2.1 双线性对和困难问题假设假定为一个大素数(如160bit)，群,阶为,而为的一个生成元，双线性对为具有如下性质的映射：1) 双线性：对任意和,有；2) 非退化性：,是的单位元；3) 可计算性：对任意,存在有效多项式算法计算。定义1 判定性q-ABDHE问题：给定 ,判断是否成立。这里,。2.2 ID-BJM安全模型Chen等在文献12中定义了基于身份的认证密钥协商协议的形式化安全模型ID-BJM模型，它是对Blake-Wilson等人的BJM模型17的扩展。ID-BJM模型下安全的认证密钥协商协议的安全性定义包含了已知密钥安全性、未知密钥共享安全性、抗被动攻击和主动攻击、抗密钥泄露伪装性和无密钥控制性等基本的安全属性16。该模型包括了一个协议参与者集合U和一个主动攻击者E。每个参与者被模拟为一组预言机(Oracle)，预言机指协议的参与者与之间会话的第个实例。攻击者被定义为一个概率多项式时间图灵机，并能访问模型中所有的预言机。对于良性(benign)的攻击者,它只是诚实地传递预言机之间的信息。定义2 会话标识符SID：预言机发送和接收的所有消息的串联。定义3 搭档预言机PID：若2个预言机和在同意(accept)状态时有相同的会话标识符SID，则称与互为搭档预言机,和互为搭档。通过定义挑战者与敌手之间的游戏来定义密钥协商协议的安全性。挑战者可以模拟所有的预言机，密钥生成中心PKG和随机预言机，产生主密钥和所有的系统参数，并为参与者产生私钥。攻击者允许进行下列预言机查询(Oracle query)。1) 查询：E可以向预言机发送消息M，该预言机按照协议规范应答一个响应消息m，预言机将每个收到和发出的消息都记入它的运行脚步记录中。若预言机收到的第一条消息,那么该预言机作为发起者(initiator)发起一次会话；否则,它担任响应者(responder)的角色。2) 查询：收到此查询的预言机,返回它协商得到的会话密钥。如果该预言机的状态还不是“已接受”(accpted),那么它返回一个符号表示终止。执行了Reveal查询的预言机状态是打开的(opened)。3) 查询：此查询要求被询问的协议参与者I返回它拥有的长期私钥SI。相应地,回答过Corrupt查询的实体的状态被称为“已腐化”(corrupted)。4) 查询：此查询要求返回系统主密钥。5) 查询：在游戏的某个时刻,E 可以向一个“新鲜”的预言机发出Test查询，E将收到该预言机所拥有的会话密钥或者一个随机值。该预言机通过投掷一枚公平硬币来回答此查询：若投币结果为0,那么它返回自己协商获得的会话密钥；否则，它返回会话密钥空间上的一个随机值。这里，表示会话密钥的比特长度。在游戏的第2阶段,E 可以继续针对预言机进行Send, Reveal和Corrupt查询。E 所受到的限制为：它不能对它所选被测试的预言机及其搭档预言机(若搭档预言机存在的话)进行Reveal查询。另外,E 也不能对被测试参与者的意定伙伴进行Corrupt查询。输出：最后，E输出一个对的判断(记为)。若,那么称E 赢得了此游戏。文中定义获胜的优势概率为（为安全参数）。定义4 新鲜预言机：预言机在同意(accept)状态(因此得到一个会话密钥)是未打开的,其搭档预言机也未打开,搭档没有被腐化,则预言机是新鲜的(fresh)。定义5 ID-BJM模型下安全的认证密钥协商协议若协议满足下列性质：1) 只存在良性攻击者的情况下，预言机与其搭档预言机在接受状态时得到相同的会话密钥，且均匀分布在密钥空间上。2) 游戏结束后,敌手成功的优势是可忽略的。称该协议为ID-BJM模型下安全的认证密钥协商协议。3 Wang协议本节简要介绍文献16中给出的无会话密钥托管模型下的基于身份的认证密钥协商协议(简称Wang协议)。其中涉及的参数与困难问题假设沿用文献16。1) 系统建立密钥生成中心PKG随机选取3个生成元以及,计算。设置系统公开参数为,系统主密钥为。2) 私钥生成对应身份,随机选择,计算私钥,其中。对每一个身份ID固定。3) 密钥协商假设Alice(身份为)与Bob(身份为)进行会话密钥的协商。令,和。Alice随机选择,计算, , 将发送给Bob；Bob随机选择,计算,将发送给Alice。Alice计算共享秘密和。Bob计算共享秘密和。根据双线性对的性质,容易得出,。最后Alice与Bob计算出相同的会话密钥为。4 对Wang协议的安全性分析本节分析Wang协议的安全性,说明恶意密钥生成中心(PKG)能通过下述方法获得Alice与Bob协商的所有会话密钥。1) 系统生成阶段PKG随机选取2个生成元以及,计算。随机选择整数,计算。设置系统公开参数为,系统主密钥为。PKG保密的信息。2) 恢复第1个共享秘密PKG拥有Alice的私钥,Bob的私钥。从公开信道上截获和。PKG可计算出 和，因此可恢复第1个共享秘密。3) 恢复第2个共享秘密PKG有主密钥,Alice的公开身份信息和Bob的公开身份信息,可计算出和,满足, 。然后从截获的信息和,可计算出和。由此恢复出第2个共享秘密。4) 恢复会话密钥PKG恢复出Alice与Bob的会话密钥。恶意的PKG可以利用主密钥和秘密参数,根据截获的中间消息恢复出所有的会话密钥。因此，Wang协议不满足PKG前向安全性。5 改进的无会话密钥托管的认证密钥协商协议针对无密钥托管的认证密钥协商协议的要求(协议必须满足PKG前向安全性)，对Wang协议做了改进,提出一个无会话密钥托管的认证密钥协商协议。5.1 系统建立密钥生成中心(PKG)输入安全参数,产生系统参数：1) 阶群、,生成元,随机选取,双线性对；2) 随机选取作为PKG的私钥，PKG公钥为；3) 密钥生成函数,表示会话密钥的长度。系统公开参数为,系统主密钥为由PKG秘密保管。5.2 用户密钥对生成对应身份,私钥生成方式如下：随机选择,计算，身份ID对应的公钥为，私钥为。对每一个身份ID，固定，且确保。5.3 密钥协商协议假设Alice(身份为，公钥，私钥)与Bob(身份为,公钥,私钥)进行会话密钥的协商。Alice与Bob计算公开参数。1) Alice随机选择,计算, ,将发送给Bob；Bob随机选择,计算, , ,将发送给Alice。2) Alice计算共享秘密 和；Bob计算共享秘密 和。3) Alice计算会话密钥 ；Bob计算会话密钥 。显然, ，因此Alice与Bob计算出相同的会话密钥为。5.4 安全性证明在ID-BJM模型下，证明改进协议的安全性。根据2.3节给出的基于身份的密钥协商协议的安全模型,得到如下定理。定理1 在q-ABDHE假设成立的条件下,改进协议是一个安全的认证密钥协商协议。证明 首先,说明条件1是满足的。因为若2个协议的参与者遵守协议规则，而且攻击者是良性的,则2个参与者都能正确地接收来自对方的消息，他们之间有匹配会话，因此,，两方计算出相同的会话密钥SK。而参与者计算密钥的临时参数是随机均匀选取的，所以密钥SK在密钥空间上是均匀随机分布的。下面证明第2个条件也满足。采用反证法，若存在多项式时间的敌手A能够以不可忽略的优势赢得游戏(假设敌手最多进行次查询，发起算法次会话),则存在一个模拟器X能够以不可忽略的优势解判定q-ABDHE问题。模拟器X对于一个判定q-ABDHE问题的输入,需要判断是否成立。初始化阶段：为产生系统参数，模拟器X按照下述方式进行初始化。随机选取一个次秘密多项式,然后根据计算。将系统公开参数发送给A，X不知道主密钥。这样设置的参数与真实系统参数具有相同的分布。随机选取3个整数, 。和分别表示第和第个参与者，X选择检测预言机为。模拟器X为攻击者A模拟攻击游戏，他们之间进行如下交互。1) 查询：输入为。若,直接用解判定q-ABDHE问题；否则,若,令,是一个次多项式，计算,返回私钥。由于是一个均匀随机多项式，它满足正确的分布，因此这一私钥对于攻击者A来说是有效的。若，则报错退出()。2) Send查询：A诚实回答除之外的其他预言机的Send查询。当对做Send查询时，产生2个次多项式, 。返回预言机的消息,和,其中， ), 。这里是中的系数。令。若,则,。且。假设预言机收到的消息为,和。则生成的共享秘密为和。对应的会话密钥为。3) 查询：当查询的预言机为或其匹配预言机，报错退出()。否则，返回对应的会话密钥。4) ：在模拟的过程某个时刻，将选择一个预言机做查询。若A没有选择X事先猜测的预言机做Test查询，则报错退出（）； 否则，返回。输出：游戏结束后，A输出他的猜测值。事件表示模拟器X不报错退出，则。假如，则A能以的概率正确猜测。否则，A没有任何优势猜测正确的值。A若能以不可忽略的优势正确判断的值，则X能以不可忽略的概率判断是否成立。模拟器X不报错退出的概率至少为。综上可得，。总结上述结果，可得X能以不可忽略的概率解解判定q-ABDHE问题，这与判定q-ABDHE假设矛盾。因此，假设不成立。改进协议是安全的认证密钥协商协议。协议满足完善前向安全性和PKG前向安全性。即使敌手获得Alice和Bob的私钥,以及系统主密钥,只能计算出第1个共享秘密 。但若要得到第2个共享秘密,必须由和,计算。然而这是CDH困难问题。因此PKG无法计算出协商的会话密钥，新协议成功取消了密钥托管。6 结束语PKG前向安全性是基于身份的认证密钥协商协议重要的安全性质。本文对文献16的标准模型下可证明安全的基于身份的认证密钥协商协议进行安全性分析,得出其无会话密钥托管模式下的协议不满足PKG前向安全性。针对无密钥托管的要求，本文给出一个改进的基于身份的认证密钥协商协议,同样在标准模型下证明改进协议是可证明安全的；最后分析改进协议满足完善前向安全性与PKG前向安全性。参考文献：1DIFFIE W, HELLMAN M E. New directions in cryptographyJ. IEEE Trans Info Theory, 1976, 22(6): 44-654.2SHAMIR A. Identity-based cryptosystems and signature schemesA. Advances in CryptologyCrypto84C. Berlin: Springer-Verlag, 1984. 47-53.3OKAMOTO E. Proposal for identity-based key distribution systemJ. Electron Letters, 1986, 22: 1283-1284.4TANAKA K, OKAMOTO E. Key distribution system for mail systems using ID-related information directoryJ. Computer Security, 1991, 10:5-33.5BONEH D, FRANKLIN M. Identity based encryption from the Weil pairingA. Advances in CryptologyCrypto 2001C. Berlin: Springer- Verlag, 2001. 213-229.6SMART N P. An identity based authenticated key agreement rotocol based on the Weil pairingJ. Electro Letters, 2002, 38:30-632.7XUN Y. Efficient ID-based key agreement from the Weil pairingJ. IEE Electronics Letters, 2003, 39(2): 206-208.8SHIM K. Efficient ID-based authenticated key agreement protocol based on the Weil pairingJ. IEE Electronics Letters,2003, 39(8): 653-654.9SUN H, HSIEH B. Security analysis of Shims authenticated key agreement protocols from pairingsEB/OL. http:/eprint. / 2003/113.10MCCULLAGH N, BARRETO P. A new two party identity-based authenticated key agreementA. Proceedings of the RSA Conference 2005C. Berlin: Springer-Verlag, 2005.262-274.11XIE G. Cryptanalysis of the Noel McCullagh and Paulo S L M Barretos two party identity-based key agreementEB/OL. http:/eprint. /2004/343.12CHEN L, KULDA C. Identity based authenticated key agreement protocols from pairingA. Proceedings of 16th IEEE Computer Security Foundations WorkshopC. New York, 2003. 219-233.13BELLARE M, ROGAWAY P. Random oracles are practical: a paradigm for designing efficient protocolsA. Proceedings of the First ACM Conference on Computer and Communication SecurityC. New York,1993.62-73.14CANETTI R, GOLDREICH O, HALEVI S. The random oracle methodology, revisitedJ. Journal of the ACM, 2004,51(4):557-594.15GENTRY C. Practical identity-based encryption without random oraclesA. Proceedings of the Advances in Cryptology- Eurocrypt06C. Berlin, 2006.445-464.16.WANG S B, CAO Z F , DONG X L. Provably secure identity-based authenticated key agreement protocols in the