基于验证元的三方口令认证密钥交换协议.doc

第10期李文敏等：基于验证元的三方口令认证密钥交换协议153基于验证元的三方口令认证密钥交换协议李文敏，温巧燕，张华（北京邮电大学 网络与交换技术国家重点实验室，北京100876）摘 要：基于验证元的口令认证密钥交换协议的最基本安全目标是抵抗字典攻击和服务器泄露攻击。利用双线性对的性质给出了一个基于验证元的三方口令认证密钥交换协议，有如下特点：能够抵抗字典攻击和服务器泄露攻击；保持密钥秘密性，提供前向安全性；确保无密钥控制；抵抗已知密钥攻击和中间人攻击；协议执行一次可以生成4个会话密钥等。关键词：口令认证密钥交换；基于验证元；字典攻击；双线性对中图分类号：TP309 文献标识码：A 文章编号：1000-436X(2008)10-0149-04Verifier-based password-authenticated key exchange protocol for three-partyLI Wen-min, WEN Qiao-yan, ZHANG Hua(State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing 100876, China)Abstract: The fundamental security goal of verifier-based password-authenticated key exchange protocol is security against dictionary attack and server compromise attack. An efficient verifier-based protocol for three parties was proposed which contains the following characteristics: against dictionary attack and server compromise attack; providing key secrecy and forward secrecy; ensuring no key control; against known-key attack and man in-the-middle attack and receiving four session keys in performing protocol one time.Key words: password-authenticated key exchange; verifier-based; dictionary attack; bilinear pairs 1 引言收稿日期：2008-06-21；修回日期：2008-09-21基金项目：国家高技术研究发展计划(“863”计划)基金资助项目 (2006AA01Z419)；国家自然科学基金资助项目(90604023, 60873191)；北京市自然科学基金资助项目(4072020) Foundation Items: The National High Technology Research and Development Program of China (863 Program) (2006AA01Z419); The National Natural Science Foundation of China (90604023, 60873191); The Natural Science Foundation of Beijing (4072020)密钥交换协议的目的是通过各通信方的交互，建立共同的会话密钥，从而能够实现在不安全信道上的安全通信。一些协议依赖于公钥密码技术，需要PKI系统的存在，成本较高；还有一些协议需要通信双方共享长的随机密钥，这些密钥通常由一个合适的程序选取，这不便于记忆和保存。因此，一个自然的思路就是各方共享易于记忆的口令，由此构造出较高质量的会话密钥。其中，两方的基于口令的密钥交换协议（2PAKE）通常使用的是“用户服务器”模型，用户所需要记忆的口令数会随着与它通信的用户数的增加而增加，这限制了协议在实际中的应用。基于口令的三方密钥交换协议（3PAKE）解决了这个问题：每个用户只需要与一个可信的服务器共享一个简单口令，可信服务器认证通信双方并帮助持有不同口令的通信方生成会话密钥。3PAKE的模型根据用户和服务器共享的口令类型分为2类：对称模型和非对称（基于验证元）模型。对称模型中，用户和服务器持有相同的口令；基于验证元模型中，用户持有口令，服务器持有的是利用单向函数生成的口令的映像（即验证元），而非口令本身。基于验证元模型降低了服务器泄露攻击对协议的破坏程度：服务器泄露时，敌手不能直接获得用户的口令，但仍允许敌手在服务器泄露攻击后对获得的口令文件进行离线字典攻击，敌手必须进行一些额外计算才有可能发现用户真正的口令，而进行这些计算给了服务器通知用户受攻击的时间。因此，设计基于验证元的3PAKE协议的主要思想是将敌手的权利限制在只能在服务器泄露攻击后对口令文件进行离线字典攻击。已有文献中有很多关于3PAKE协议16的研究，但只有文献4和文献6是关于基于验证元的3PAKE研究。文献7中给出了一个基于验证元的2PAKE，该协议不完全且不能抵抗离线字典攻击，文献4是基于文献7给出第一个三方协议，同样不能抵抗离线字典攻击。文献8给出了对策但因为设计结构不同不能应用于三方，文献6给出了一个基于验证元的3PAKE协议，但是它生成一个会话密钥的计算开销和通信开销都很大。文中利用双线性对的性质，给出一个基于验证元的3PAKE协议，能够提供前向安全性和密钥秘密性，抵抗已知密钥攻击、服务器泄露攻击、字典攻击和中间人攻击，协议执行一次可以生成4个会话密钥等性质。2 预备知识2.1 双线性对的基本概念是阶循环加群，是阶循环乘群，是大素数。并且、上的离散对数问题是困难的，因此，满足如下性质9：1) 双线性性；，其中。2) 非退化性 存在点，使得 。3) 可计算性 对所有的，存在有效的算法计算。假设是由点生成的循环加群，下面介绍中的数学难题10：1) 离散对数问题（DLP） 给定，找到，使得。2) 计算性Diffie-Hellman问题（CDHP） 给定，计算, 。 3) 判定性Diffie-Hellman问题（DDHP） 给定，判定是否成立，。2.2 伪随机函数集8函数集是伪随机的，如果对每个概率多项式Oracle M和所有足够大的n满足 其中, 是一个均匀分布的函数集；是一个可忽略的函数；表示对所有的Oracle M，可能取到的最大值。3 协议描述3.1 公开参数是阶循环加群的生成元，是阶循环乘群，双线性对；是散列函数；是伪随机函数集；A，B是用户，是用户相应的口令；S是服务器。3.2 初始化过程假设A，B和服务器S共享的验证元分别是：，令，。3.3 协议过程假设是A需要和B建立会话密钥，则协议过程如表1所示。Round 1发起者A广播。Round 2 用户A从上随机选取，计算,令分别为的坐标值。然后按如下方法计算：。将发送给。相应地，同时进行类似的操作，生成，并将其发送给。Round 3 收到后，从中分别得到的值，然后验证 ；类似地，收到 表1协议执行的一个例子用户A服务器S用户BRound 2,Round 3， Key commutation 后，验证 ，如果任一组数据没有通过验证，则协议终止；否则，从上随机选取，计算，然后分别计算， ，并将以下2组数据 ，分别发送给和。计算密钥 收到后，验证是否成立，如果等式不成立，协议终止；如果成立，首先计算： 会话密钥分别为： 同时，进行类似的操作：首先验证是否成立，如果等式不成立，协议中止；如果成立，则进行类似计算： 然后得到相应的会话密钥 。完成 如果协议诚实执行，则通信双方得到相同的会话密钥：。其中，。4 效率和安全性分析4.1 效率分析从计算开销、存储开销和通信开销几个方面来分析协议的效率。每生成一个会话密钥，每个用户平均需要进行0.75次对数运算，2次点乘运算；服务器平均需要进行1次对数运算，1.75次点乘运算。而协议每执行一次，用户和服务器之间需要3轮交互。对于每个用户，服务器只需要存储一个与之相应的验证元。这与其他已有的同性质的协议相比较，降低了存储开销和通信开销（如表2所示），因而其实用性更好。表2各协议效率比较文献5文献7本文协议验证元数目121轮数543生成密钥数目1144.2 安全性分析检测协议对常见攻击的安全性。假设有一个外部敌手M能够监控整个通信过程，截取任何通信信息；内部敌手C，是系统的合法用户；S是一个合法可信、举止诚实的服务器。他们都是概率多项式图灵机。1) 字典攻击 基于口令的密钥交换协议易受字典攻击，字典攻击按其性质可分为3类11：离线字典攻击、可测在线字典攻击和不可测在线字典攻击。 本协议抵抗离线字典攻击，以用户A为例。一方面，由于是用户A从上随机选取的，如果外部敌手M想通过截获的信息获得其口令，就必须解决DLP问题，然而，现在还没有多项式时间算法来解决这个问题；另一方面，虽然外部敌手可以截获，但是同样因为DLP问题的困难性，敌手不能从获取，因此不能通过来进行离线字典攻击。 本协议可以抵抗可测在线字典攻击，因为服务器在第3轮里能够验证用户是否真的知道口令。一旦验证失败，服务器就会意识到是谁的口令已经作为在线字典攻击的目标了。如果失败的次数超过预定的门限值，服务器就会通知该用户停止使用该口令并启用新的口令。 如前所述，敌手不能将作为口令试验预言机，因此不能进行不可测在线字典攻击。2) 密钥保密性 密钥保密性是指敌手不能以不可忽略的概率区分一个随机串和协议中生成的会话密钥。本协议提供密钥保密性： 由于因为CDHP问题的困难性，敌手不能从截获的得到密钥的相关信息。 假设或能够以不可忽略的概率来区分会话密钥和随机串，这就意味着他们能够解决DLP问题，或者破坏了伪随机函数的伪随机性，这与DLP问题是困难的并且F是伪随机函数族矛盾。3) 前向安全性 基于口令的密钥交换协议的前向安全性是指即使敌手获得一个或多个用户的口令，也不能影响以前由该口令建立的会话密钥的安全。即会话密钥与口令之间具有独立性。本协议提供前向安全性，就是说即使被泄露，敌手仍不能破坏之前产生的会话密钥的密钥保密性，这是因为每个会话密钥的产生都需要用户选取的随机数，敌手如果想获得这些随机数，就要解决DLP问题，这是困难的。4) 服务器泄露 说一个协议是能抵抗服务器泄露攻击，就是指即使一个敌手窃取了口令文件，仍然不能冒充一名合法用户，除非它对口令文件再执行字典攻击。（当然，服务器泄露攻击仍然允许字典攻击）。本协议能够抵抗服务器泄露攻击，是因为DLP问题的困难性和单向函数H的求逆困难性，不能从获得口令，因此不能通过第3轮S的验证。5) 已知密钥安全 即使攻击者获得某次通信的会话密钥，也不能根据该会话密钥来获得其他通信的会话密钥，即会话密钥之间具有独立性。这种性质称为已知密钥安全。本协议具有已知密钥安全性，因为最终的会话密钥是由一些随机数构造的，就是说都是用户A和B相互独立地随机选取的，因此，对于敌手来讲，攻破一次通信的会话密钥，无助于猜测其他通信的会话密钥。6) 无密钥控制 通信双方中的任何一方不能强迫会话密钥选择为一个预先确定的值，即通信双方对最终生成的会话密钥都有贡献，单方不能控制密钥的选择。本协议中的最终会话密钥中的K是由A和B分别独立选取的随机数以及A、B的口令来共同构造的，并且F是伪随机函数族。因此，单方不能确定会话密钥的值。7) 抗中间人攻击 内部敌手和外部敌手均不能发起中间人攻击，这是因为如果敌手模仿A（B）与S会话，敌手不知道A（B）的口令，就不能生成有效的（），在第3轮中无法通过S的验证，协议终止；如果敌手模仿S与A（B）会话，因为敌手不知道A（B）相应的验证元（），则计算密钥过程中不能通过A（B）的验证，协议终止。5 结束语本文利用双线性对的性质，给出了一个基于验证元的三方口令认证密钥交换协议，该协议执行一次可以生成4个有效会话密钥，能够抵抗字典攻击和服务器泄露攻击，提供密钥保密性和前向安全性等性质。此外，与已有协议相比，本协议降低了存储开销和通信开销，更适用于实际应用。参考文献：1BELLARE M, ROGAWAY P. Provably secure session key distribution-the three party caseA. Proceedings of the 27th ACM Symposium on Theory of ComputingC. Las Vegas: ACM, 1995. 57-66.2CHANG C C, CHAN