对两个口令认证密钥交换协议的安全性分析

对两个口令认证密钥交换的安全性 1，212胡学先 ，刘文芬 ，张振峰 1，212 ，，HU Xue-xianLIU Wen-fenZHANG Zhen-feng 信息工程大学 信息工程学院，郑州 1.450002 中国科学院 软件研究所 信息安全国家重点实验室，北京 2.100190 ，，，1.Department of Information EngineerinInfgormation Engineering UniversitZhengzhou y450002 China ，，，，2.State Key Laboratory of Information SecuritInstitute yof SoftwareChinese Academy of Science sBeijing 10019 0China :E-mailxuexian_hu@yahoo.com.cn ，， HU Xue -xianLIU Wen -fenZHANG Zhen -feng.Cryptanalysis of two password authenticated key exchange protocols. ，，():Computer Engineering and Applications2010461818-20. : AbstractPassword authenticatedkey exchange protocol can be used f or two parties sharing only a lowentrop y password to es,- ，tablish high entropy sharedkeys.It has been extensively studied for its great application prosperity.In this pape rcryptanalysis of a ，“”protocol proposed by Shu et al. in the paper o fProvable Secure Encrypted Key Exchange Protocol under Standard Modeandl a “”protocol proposed by Li et al. in the paper ofVerifier-Based Password Authenticated Key Exchange for Three Partyhas been presented.Concrete f -olinef dictionary attacks in which an outside adversary traverses the password dictionary and verifies its ，guess in offline manner are also presented.Furthethe rerrors in the original security proof are also analyzed. - :;;; Key wordskey exchange protocoprovable l securitpassword y authenticateoffd-line dictionary attack 摘 要:口令认证密钥交换协议使得仅共享低熵口令的用户可以通过不安全的信道安全地协商出高熵的会话密钥，由于实用性较强受到了密码学研究者的广泛关注。对最近在“模型下高效的基于口令认证密钥协商协议”一文中提出的协议以及“在基于验 证元的三方口令认证密钥交换协议”一文中提出的协议进行了分析，指出这两个口令认证密钥交换协议都是不安全的，难于抵抗 离线字典攻击，进一步分析了原协议设计或安全性证明中被疏忽之处。 关键词:密钥交换协议;可证明安全;口令认证;离线字典攻击 : 文章编号:() 文献标识码:中图分类号: DOI10.3778/j.issn.1002-8331.2010.18.0071002,8331201018-0018-03ATP309 模型进行设计和分析。最早的标准模型下可证明安全的 PAKE引言1 [7]口令认证密钥交换()协议使得共享低熵口令的用户 PAKE协议由 等提出，不过，他们的协议所需通信轮数不 Goldreich 可以通过不安全的信道安全地生成共享的高熵会话密钥，避免 固定，并且不支持两个用户之间同时运行协议的多个实例，因此 了一般密钥交换协议要求存在公钥基础设施或要求用户拥有 [8]并不实用。年，等提出了一个相对高效的协议，不过 2001 Katz 存储长对称密钥的安全硬件的前提假设，由于实用性较强受到 [9] 协议一次会话需要约 次指数运算，复杂度仍旧很高。等30 Jiang [1]了研究者的广泛关注。 在 年提出了一个改进的协议，降低了复杂度并实现了双向 2004 第一个真正意义上的口令认证密钥交换协议 由和 Bellovin[2][10]于 年提出，称为加密密钥交换()协议。认证。以此为基础，年殷胤等在服务器拥有额外的公私 Merritt1992 EKE2000 2007 [3]年，等提出了 协议的一个形式化安全性分析模 Bellare PAKE 钥对的前提下给出了一个效率更高的 协议。但是，胡学PAKE 型，即 模型，并基于随机谕示()模型和理想密码BPR2000 RO [11] 先等指出上述协议难于抵抗外部攻击者实施的假冒服务器()模型证明了 协议满足其安全性定义。随后，人们在 ICEKE [12]攻击年，舒剑等尝试在 等的协议和殷胤等的协议 。2009 Jiang 协议的基础上，根据安全性、效率、应用环境等不同的目 EKE 基础上进一步改进，提出了一个新的两方 (简记为 PAKEShu- ，[145]-标设计出了大量的 协议。PAKE )协议，并在 模型中进行了安全性证明。 2PAKEBPR2000 从安全性上讲，由于协议设计中普遍采用的 模型存在 RO 从应用环境上讲，由于两方 协议中用户需要记住的 PAKE [6]实例化问题，因此现在安全协议研究的趋势之一是采用标 准口令数随着网络规模扩大而线性增长，因此考虑可信服务器参 与的三方 PAKE(3PAKE)协议成为了PAKE 协议设计中的热 基金项目:国家高技术研究发展计划()(); 863the National HighTech Research and Dev elopment Plan of China und er Grant N o.2009AA01Z417- 国家自然科学基金()。the National Natural Science Foundation of China und er Grant N o.60873261 作者简介:胡学先()，男，博士生，研究方向为安全协议;刘文芬()，女，教授，博士生导师，主要研究方向为密码、学通信安全;张振峰1982-1965- ()，男，研究员，博士生导师，主要研究方向为安全协议。1972- 收稿日期: 修回日期: 2010-03-122010-05-11 点之一如果进一步考虑服务器泄露可能带来的危害，可以采用。消息给服务器 ; Server[13] 基于验证元的三方 ()协议。年，等PAKEVB-3PAKE2005 Lee (2)服务器 Server在收到消 息后，按照协议

规范

编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载

提出了第一个 协议，但后来被证明不能抵抗离线 VB-3PAKE x-pw y [14]计算 C=A(f / pw)=g 。然后选择随机值 y?Z ，计算 σ=C ，ak = 字典攻击。年，等利用验证元作为 公钥提 2008 Kwon ElGamal q S y 出了一个 协议，两个用户经过四轮通信可以生成一 VB-3PAKE ()，?()，并发送消息给客户 ; F3B=g f pwClient [15]S σ个共享密钥尝试利用双线性对的性质提 。年，李文敏等2008 ()攻击者 在消息到达客户 之前予3E Client 出效率更高的 (简记为 )协议，使得 VB-3PAKELi-VB-3PAKES 通信双方经过一次会话就可以生成四个会话密钥。 以拦截;[12][15]对 协议以及 进行了 协议Shu-2PAKE Li-VB-3PAKE ()根据前述步骤得到的信息，攻击者重 复进行下述步骤， 4E 分析，结果表明这两个协议都是不安全的，难于抵抗离线字典 *直到找到正确的口令:从口令字典 中选择一个口令 作为D pw 攻击这种攻击是对 协议一种严重的攻击方式，其中攻 。PAKE * -pw* x-pw*击者根据得到的数据可以离线地对用户的口令进行猜测和验 对客户的口令的猜测，计算 (，验证等式 ) ?σ =Bg ak = S 证。分别给出了针对上述两个协议的具体攻击方法，进一步分 F()是否成立。如果等式成立，则成功的猜对客户的口令 3 σ*析了原协议设计和安全性证明中被疏忽之处。 * * ;否则，将 从集合 中删除，从剩余集合中再选择 pw=pw pw D *一个新的口令，按照上述方式重新计算 ，并重新验证等式。σ 注意到 Shu-2PAKE协议作者 在 BPR2000模型中 给出了 协议 2 Shu-2PAKE 上述协议的安全性证明，因此如果证明中不存在错误的情况下， 简要回顾舒剑等提出的基于标准模型的Sh u-2PAKE协 协议应该到达模型定义的安全性目标下面分析原协议安全性。* 证明中疏忽的细节，以求在以后的安全 协议的设计和分 PAKE 议。设 ，是满足 的大素数，是乘法群 Z的一个 阶pq q|p-1 Gq q p 析中能有所借鉴。 子群且满足 假设，是 的一个生成元;是从口令空间DDH g Gf q 文献中给出的证明采用了一系列逐渐修改的实验将真 [12]到 的映射，是索引集为 的伪随机函数簇，均为公开参数;GF G q 实的协议和所有会话密钥都被替换成了随机值的实验联系 起不妨设只有两个合法用户，客户 和服务器 ，共享 Client Server 来，并通过考察每两个相邻的实验之间攻击者成功优势之差达口令 。客户 和服务器 利用上述参数进行密钥 pwClient Server 到限定真实的协议中攻击者成功优势的目的其中，实验 中 。Γ 交换的具体步骤如下: 5 考察的主动攻击者构造消息 进行 ()查询的情况。 A SendClien|tAx (1)客户 Client选择一个随机 值 x?Z，计算 A=g (f pw)，?作者“证明了”攻击者选择一个随机数 x?Z ，并猜测口令的值 q q * x 并发送消息给服务器 Server;，产生消息 pw A=g ()进行 查询时，其成功的概率为 ?f pwSend (2)服务器收到消息后，首先计算 C=A/(f pw)。然DDH r pw* ?。但是，证明过程中又取 () ，其中 为模拟者 qAdvA=gdr y xy y ，sgG 2 ()，?()， 后选择随机值 y?Z，计算 σ=C =g ，ak=F3B=g f pw q S σ随机选择的一个参数，为一个公开参数，并进一步假设模拟 d 2 并发送消息给客户; S * 者知道 ，这些步骤存在矛盾和错误。 pw -pw() -f pw ，()客户 收到消息后，计算 ?3Client Y=Bg S x ，验证是否成立 ()，不通过直接拒绝。验证通过后 ak=Fσ=Y 3协议 4 Li-VB-3PAKE S σ Li-VB-3PAKE 协议是一个基于验证元的 3PAKE，两个用计算 ()，()，认为会话成功并将 作为和 ak=F1sk=F 2sk Server σ C σ户在服务器的帮助下一次可以协商出 个会话密钥具体地， 。4 共享的会话密钥，向服务器发送确认消息; C 假设 和 分别表示阶为素数 的加法交换群和乘法交换GGq 1 2 ()服务器 收到确认消息后，利用其前4Server C 群，且 是群 的一个生成元。设群 以及群 上的离散对P GGG 1 1 2 面计算得到的 的值验证是否成立 ()，验证不通过直 σ ak=F1 C σ* l 数问题是难解的。:是双向性对;:，，eG×G?GH{01} ?{01}112 接拒绝。通过后计算会话密钥为 ()。 sk=F1 σ是抗碰撞的 函数，是伪随机函数簇;客户 ，拥Hash F={F}ABnn?N 有的口令分别是 ，，服务器 拥有相应的验证元 ?pwpwS Y=X ABAA对 协议的攻击 3 Shu-2PAKE P=H(A‖S‖pw )P，Y =XP=H(B‖S‖pw )P。客户 A，B 在??? A B B B 协议的作者认为，与其他标准模型下的协议相 Shu2PAKE -服务器 的帮助下按如下步骤进行密钥交换: S 比，该协议不需要 或 安全的加密体制，因而具有计CPA CCA2 (1)第一轮。发起者 A 广播(A，B，S)。 算复杂度低和协议描述简单的特点。尽管设计上予以了简化，但* ()第二轮。客户 从 上随机选取 ，，计算 ，2A Zaa V =a Y 是他们证明了协议的安全性并没有减弱。具体地说，基于 DDH 2 A1 1 A q 1 问题的困难性和伪随机函数簇的存在性，他们在 模型 BPR2000 ，令 ，分别为 ，的 坐标值。然后 计算V=aYTTVVx A A2 2 A A1 A2 A1 A2 下证明了所提出的协议协商得到的会话密钥的安全性，即对具 ()，发送给 ; ，并将消息 ，S=aT+aTV +a V S A1 1 A2 A1 A2 A A 1 A1 2 A2有模型中描述能力的任意攻击者，其区分一个测试会话返回的 [12]客户 对称地进行类似操作，生成消息，，，并将其B 值是真实密钥还是随机值的优势是可忽略的。 B1 B2 B 发送给 S。该文指出，协议实际上是不安全的，一个外部 Shu-2PAKE ()第三轮服务器 收到来自用户 的消息，，。 3S A 攻击者可以成功地对用户的口令实施离线字典攻击。设客户 A1 A2 A 后，从 ，中提取 坐标值 ， ，然后验证 (，) V V x T TeS Y =A1 A2 A1 A2 A A pw 和服务器 共享的口令为 ，取映射 ()，则 Client Server pwf pw=g ()是否成立;类似地，收到用户 的 ，eT V +T V +V V S B A1 A1 A2 A2 A2 A1 攻击者 E 对口令 pw 进行字典攻击的具体步骤如下:消息，，后，验证 (，)( ，) eS Y =eT V +T V +VV B1 B2 B B B B1 B1 B2 B2 B2 B1 x (1)攻击者 E 选择一个随机值 x?Z ，计算 A=g ，并发送 是否成立，如果任何一组验证没有通过，协议终止;否则，选 q S * 轮客户向服务器发送的消息中，实际上不能包含客户向服务器)， 取随机数 sZ，计算 V=sP，然后分别计算 Z=s( V+V?+Y q s A B1 B2A 认证自己的任何组成部分。这是因为，服务器在正式进行信息 ()，将消息，，，，，，， Z=s V+V+Y B B1 B2 S A A1 A2 S B B A1 A2交互之前仅拥有口令验证元，如有用于认证的等式则必定形 分别发送给客户 和 。 A B如，可以被攻击者用来进行离线字典攻击 。()会话密钥的计算客户 收到，，，。后，首4A B1 B2 S A )先验证 (，)(，(，)是否成立，不成立则eZP=eV+VVeYP A B1 B2 SA 结束语 6 终止协议;如果成立，首先计算: 对已有协议的安全性分析旨在为协议设计提供更好的参 A 考和借鉴对舒剑等在标准模型下高效的基于口令认证密钥 。“K=aXV=abXXP A1 1 A B1 1 1 A B 协商协议”一文中提出的协议、及李文敏等在“基于验证元的三 K=aXV=abXXP A2 1 A B2 1 2 A B 方口令认证密钥交换协议一文中提出的协议进行了分析，指 ”K=aXV=abXXP A3 2 A B1 2 1 A B 出这两个新近提出的口令认证密钥交换协议都是不安全的，均 K=aXV=abXXP 易于遭受离线字典攻击，进一步分析了原协议设计或安全性证 A4 2 A B2 2 2 A B 明中不合理之处。对协议的攻击能够成功的主要原因是协议消 会话密钥分别为 SK=F(A‖S‖B)，i=1，2，3，4;同时用户 B进 KAi Ai 息中本身就包含、或攻击者通过与用户简单交互就易于得到关 )行类似的操作:首先验证等式( ，)(，(，)eZP=eV+VVeYP B A1 A2 SB 于共享口令的验证等式。攻击再次表明了协议的设计和安全性 是否成立，如果不成立则协议终止;如果成立，类似地计算:证明是技巧性强且易于出错部分，需要特别谨慎对待 。K=bXV=abXXP B1 1 B A1 1 1 A B K=bXV=abXXP B2 1 B A2 1 2 A B K=bXV=abXXP 参考文献:B3 2 B A1 2 1 A B ，K=bXV=abXXP [1] Boyd CMathuria A.Protocols for authentication and key establish,B4 2 B A2 2 2 A B ment[M].Berlin:Springer-Verlag，2003:247-266.然后计算相应的会话密钥 SK=F(ASB)，i=1，2，3，4‖‖。 KBi Bi : ，[2] Bellovin S M Merritt M.Encrypted key exchangePassword based protocol secure against dictionary attack[C]//IEEE ium Sympos on Re, 对 协议的攻击 5 Li-VB-3PAKE search in Security and Privacy，Oakland，1992:72-84. 协议的作者通过启发式分析，认为该协议能 LiVB3PAKE --，，Bellare MPointcheval DRogaway . APuthenticated key exchange [3] :secure against 够抵抗字典攻击(包括离线，可测和不可测在线字典攻击)，保 dictionary attacks [C]//LNCS 1807 Eurocrypt 200 0. :，: BerlinSpringer-Verlag2000139-155. 持会话密钥私密性，提供前向安全性，抵抗服务器泄露攻、击已 : [4] MacKenzie P.The PAK Psurotocols itefor password authent icated知密钥攻击、中间人攻击，确保无密钥控制。该文指出，协议并没有达到所声称的安全 ，，Li-VB-3PAKE key exchangeTechnical Report 200 2-46[R/OL].DIMACS2002-10. 性，甚至难于抵抗外部攻击者实施的离线字典攻击攻击者只 。:http//dimacsrutger.s.edu/TechnicalReports/abstract/2002/2002-46.htm.l 需要对客户发送的消息进行窃听，得到客户在第二轮中发送的 ，[5] Katz JVaikuntanathan V.Smoothproject ive hashing and password- 消息或者是服务器在第三轮中发送的消息中的任何一条，就可 :based authent icated key exchange from lattices[C]//LNCS 591A2si, 以对相应的客户的口令进行离线字典攻击。 ，:acrypt 20092009636-652. ，，， 以客户 为例，假设攻击者 得到了诚实的客户 发送[6] Canetti RGoldreich OHalevi S.The random oracle methodologyA E A revisited[C]//The 30th Annual ACM Symposium on Theory of Com, 给服务器 的消息，，，按照如下步骤对用户 的S E A ，:puting1998209-218. A A1 A2 ， [7] Goldreich OLindell Y.Session key generation using human pas ,s口令实施字典攻击:首先从 ，中提取 坐标值 ，，VVx TT A1 A2 A1 A2 words only[C]//LNCS :213Crypto 9200 1.Berlin:Sprngeri-Verlag，2001:* 然后从口令字典 中选择一个口令 作为对用户 的口令D pwA A 408-432. * * [8] Katz J，Ostrovsky ，RYung M.Practical passwor d-authenticated key ex,)?，验证等式: 的猜测，计算 Y=H(ASpw‖‖P A A change provably secureunder standard assumptions[C]//LNCS 2045:? * (，)=(，) eSYeT V +T V +V V Eurocrypt 2001.Berl in:Springer-Verlag，2001:475-494.A AA1 A1 A2 A2 A2 A1 [9] Jiang S ，QGong G.Password based key exchange w ith mutual au,是否成立。如果等式成立，则成功地猜对用户 的口令;否则， A * thenticatoni [C]//LNCS 3357 :Selected Areas in Cryptography -SAC将 从集合 中删除，从剩余集合中再选择一个新的口令，pwD A 2004.Berlin:Springer-Verlag，2004:267-279.* 按照上述方式重新计算 ，并重新验证等式。重复上述过程直殷胤，李宝标准模型下可证安全的加密密钥协商协议软件学 Y[10] .[J]. A 报，，():2007182422-429. 到找到正确的口令。胡学先，刘文芬对一个可证安全的口令认证密钥交换协议的 分[11] . 另外，攻击者如果得到了服务器 发送给用户 的消息S A 析[C]//中国密码学会 2009年会

论文

政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载

集 ，广州，2009:240-245.，，，，也可以类似地对用户 的口令实施字典攻A B1 B2 S A [12] 舒剑，许春香.标准模型下高效的基于口令认证密钥协商协[J].议 击，只是此时攻击者通过验证等式: 电子与信息学报，2009，31(11):2716-2719.* ，，[13] Lee S W Kim H SYoo K Y.Efficient verifier-based key agree, (，)(，)(，) eZP=eV+VVeY P A A B1 B2 S’ment protocol for three parties w ithout servers public key [J]. * 来判断猜测的口令 是否正确。由于对称性，攻击者可以类pw A ，，():Applied Mathematcs and Computaton20051672996-1003. ii 似地对用户 B 进行字典攻击。，， [14] Kwon J OJeong I RSakurai K.Efficient verifier-based password上述攻击之所以能够成功，是由于 协议中 Li-VB-3PAKE authentcation key exchange in the three party settnig[J].Computer i 的验证等式中组成元素除了验证元 和 之外，其他元素要YY ，，():Standards and Interfaces2008292513-520.B A 么本身就包含在传递的消息中，要么容易从这些消息计算得李文敏，温巧燕，张华基于验证元的三方口令认证密钥交换协 [15] . 到，从而使得攻击者离线验证对口令的猜测成为可能。在第二 议通信学报，，():[J].20082910149-152.