强安全性的三方口令认证密钥交换协议

议运行模拟 SendClient (U i ,U i , m, start ) 、 SendServer ( S j , m) 、
1 2
Execute(U , S ,U ) ，以及 Test 查询。可见，经过模拟后的
i1 j i2
G1 与 G0 是不可区分的，即：
Pr[ Succ1 ] ≈ Pr[ Succ0 ]
(2)
Game G2：取消可能会出现的碰撞，如：在部分协议 传输副本 ( A, B, S , X , Y1 , Y , Y2 ) 或 Hash 函数 ( H , T , H j ) 输出的 碰撞。由于协议副本中至少包含了一方诚实用户，因此 X (或 Y )、 Y1 (或 Y2 )是均匀分布的。根据生日悖论，可知：
22
计 算 机
工 程
2012 年 10 月 5 日
2
强安全性的 3PAKE 协议
强安全性的三方口令认证协议的描述如图 1 所示，其
为|D|。 协 议 中 使 用 了 5 个 安 全 Hash 函 数 ， 分 别 为
* ( H , T ) :{0,1}* → Z q ， H j :{0,1}* → {0,1}k ，其中， j = 1, 2,3 。A、
| Pr[ Succ2 ] − Pr[ Succ1 ] |≤
2 2 qhash − H + qhash−T + 2q
2 Adv
DDH G
(t + 8qexe ⋅τ e )
其中， D 表示字典大小， qsendA 、 qsendB 和 qsendS 表示攻击者 分别向 A、B、S 提交的 Send 查询次数； k 是 hash 函数 H j 的输出长度； τ e 表示群 G 上模指数运算的时间。 证明：本文通过定义一系列 Game ，以原始攻击 G0 开始，以 G8 结束，相邻的 Game 之间利用 Shoup 引理来 确定两者可区分的概率上界。由于这些概率上界都是可忽 略的值，因此相邻的 Game 之间是不可区分的，最终将协 议的语义安全性归约到 SDH[9]和 DDH 难题上。对每个 Gi 定义事件 Succi 为攻击者 M 成功猜测 Test 查询中隐藏的比 特 b ，即 b ' = b 。协议证明是基于随机预言模型。 Game G0： 协议 P 的真实执行， 根据语义安全性可知：
中虚线框表示预计算的数值； G 是一个 q 阶有限循环群；
q 为安全素数；群生成元为 g ； l 为群 G 的安全参数且满
B 表示客户端，S 为服务器端，且 A, B, S ∈ {0,1}* 。公开参数 为 (G, q, g ) 以及 Hash 函数。
足l= l bq 。 k 为 Hash 函数的安全参数，口令字典大小
r1 S1 1
B , A, Y
* y ← Zq ,Y ≡ g y
r1 = T ( A, S , X )
K = Y1
' 1
1 x + pw1⋅ r 1
S , Y1
r2 = T ( B, S , Y ), Y2 = (Y ⋅ W2 r2 ) S2
S , Y2
r2 = T ( B, S , Y )
' K2 = Y2 1 y + pw2 ⋅r2
vS A = H 2 ( A, B, S , X , Y1 , K1 )
vSB = H 2 ( A, B, S , Y , Y2 , K 2 )
N , Y z , MACv ( N , A, B, S , Y z )
SA
N , X z , MACv ( N , A, B, S , X z )
SB
' vS = H 2 ( A, B , S , X , Y1 , K 1' ) A
1
概述
基于口令认证的密钥交换协议 (Password-based Auth-
导致了基于口令的协议容易遭受到字典攻击，并且在三方 环境中服务器要同时与不同的用户进行交互协商会话密 钥，因此，3PAKE 协议容易遭受离线字典攻击、可检测的 在线字典攻击以及不可检测的在线字典攻击 [1]。 文献 [2]提出了一个使用服务器公钥来认证的 3PAKE 协议，但效率偏低。文献 [3]提出另一个 3PAKE 协议，且 没有使用服务器的公钥， 但文献 [4]指出该协议不能抵抗服 务器泄露攻击。文献 [5]提出一种简单的 3PAKE 协议，并 声称协议可以抵抗多种攻击且效率比同类协议都高，但 是随后文献 [6-7] 都指出该协议会遭受攻击，并给出相应 的改进协议。文献 [1] 发现改进协议仍不能抵抗不可检测 的在线字典攻击，并指出用“启发式方法”分析协议 的易错性。为解决上述问题，本文提出一个新的 3PAKE 协议，以两方下可证明安全的 AugPAKE[8]协议为蓝本，并 在 ROR 模型 [9] 下严格按可证安全的方法证明了语义安 全性。
2 2 qhash ( q + qsendA + qsendB ) 2 AKE − H + qhash −T Adv p + exe + ,D ( M ) ≤ q |G| qsendA + qsendB + qsendS − SDH + 8 | D | ×Succ1 (t + τ e ) + g ,G 2k −1 4(qsendA + qsendB + 2qsendS ) suf −cma + 2qexe × AdvMAC (t , 2, 0) + |D|
Game G1：按随机预言的方式模拟 Hash 函数 ( H , T ) 、
' ，并按实际协 H1 、 H 2 、 H 3 以及私有 Hash 函数 H1' 、 H 2
下，证明如果 SDH、 DDH 问题是难解的，则本文所提出 的协议是语义安全的。以下定理说明了这一点： 定理 1 假设 M 是一个针对本文协议语义安全的攻击 者，其运行时间不超过多项式 t，则 M 的优势为：
' ' vS = H 2 ( A, B, S , Y , Y2 , K 2 ) B
Y
z
MACv ( N , A, B, S , Y )
SA
z
Xz
MACv ( N , A, B , S , X z )
SB
σ = (Y z ) x
SK AB = H 3 ( A, B, S , N , σ )
σ = (X z )y
第 38 卷 第 19 期 Vol.38 No.19 ·专栏· 专栏·
计 算 机 工 程 Computer Engineering
文章编号： 文章编号：1000—3428(2012)19—0021—04 文献标识码： 文献标识码：A
2012 年 10 月 October 2012
中图分类号： 中图分类号：TP309
v A ≠ H1 ( A, B, S , X , Y1, K1 )
v A = H1 ( A, B, S , X , Y1 , K1' )
vA
vB ≠ H1 ( A, B, S , Y , Y2 , K 2 )
N ← {0,1} z ← Z
n * q
vB
' vB = T1 ( A, B, S , Y , Y2 , K 2 )
enticated Key Exchange, PAKE)是用户使用易于记忆的口 令与服务器进行认证，并完成密钥建立的过程。通常的 PAKE 协议一般指两方环境，即“客户 -服务器”模式。但 是随着网络应用性的增强，出现了很多三方场景，即“客 户 -服务器 -客户”模式。对于这种大规模的通信系统而言， 如果还使用 2PAKE 协议，那么用户需要记忆的口令数会 随着与它通信用户数的增加而增加，这将使通信系统无法 有效地对密钥进行管理，使得 PAKE 协议的便利性大打折 扣。而三方口令认证密钥交换 (3PAKE)协议的出现很好地 解决了这个问题，在 3PAKE 协议中，每个用户只需和可 信服务器共享一个口令 (或基于口令的验证值 )，客户双方 在服务器的帮助下生成安全的会话密钥。学者们都提出各 自的 3PAKE 协议，并给出了安全分析或基于某个困难假 设的安全证明。在实际应用中，由于口令字典集合较小，
————————————
基金项目： 基金项目：国家自然科学基金资助项目“轻量级分组密码算法研究”(61100201)；广东高校优秀青年创新人才培养计划基金资助项目(LYM 11053) 作者简介： 作者简介：陈 勇(1986－)，男，硕士，主研方向：密码学，网络安全；王立斌、龚 征，副教授、博士 收稿日期： 收稿日期：2011-12-07 修回日期： 修回日期：2012-03-06 E-mail：lbwang@
pw1
W1 = g pw1 ,W2 = g pw2
* s1 , s2 ← Z q
pw2
S1 = H ( s1 ), K1 = g S1
S 2 = H ( s2 ), K 2 = g S2
*ห้องสมุดไป่ตู้x ← Zq , X ≡ gx
A, B , X
r1 = T ( A, S , X ), Y1 = ( X ⋅ W )
Three-party Password-based Authenticated Key Exchange Protocol with Stronger Security
CHEN Yong, WANG Li-bin, GONG Zheng
(School of Computer, South China Normal University, Guangzhou 510631, China) 【Abstract】Based on the protocol AugPAKE which has been proven security, this paper proposes a strong security Three-party Password-based Authenticated Key Exchange(3PAKE) protocol, which avoids using the server’s public key to authenticate, and ensures the efficiency. It is proved to be secure against dictionary attacks, server leaked attacks and kinds of known attacks, and also applies key privacy to the server and forward security. The security of the protocol are proved based on Decisional Diffie-Hellman(DDH) problem and Strong Diffie-Hellman(SDH) problem in random oracle model. 【Key words】password authentication; key exchange; dictionary attack; Three-party Password-based Authenticated Key Exchange(3PAKE); random oracle model DOI: 10.3969/j.issn.1000-3428.2012.19.005