• Proof of Forward Security for Password-Based Authenticated ...


  •   
  • FileName: ijns-2008-v7-n3-p335-341.pdf [read-online]
    • Abstract: in practice, we only provided the rigorous proof of forward ... flaw in the proof. given in [3]. Section 5 presents the rigorous proof of for- ward ...

Download the ebook

International Journal of Network Security, Vol.7, No.3, PP.335–341, Nov. 2008 335
Proof of Forward Security for Password-Based
Authenticated Key Exchange
Shuhua Wu and Yuefei Zhu
(Corresponding author: Shuhua Wu)
Zhengzhou Information Science Technology Institute
Mailbox 1001 no. 770, Zhengzhou, 450002, China
(Email: [email protected])
(Received Mar. 21, 2007; revised and accepted June 14, 2007)
Abstract inal form AuthA did not achieve the notion of forward-
secrecy in a provably-secure way. The forward-secrecy of
Recently, M. Abdalla et al. proposed a slightly different AuthA was indeed explicitly stated as an open problem
variant of AuthA, based on the scheme proposed by E. in [6, 11]. Recently, M. Abdalla et al. proposed a slightly
Bresson et al., and provided the first complete proof of different variant of AuthA, based on the scheme proposed
forward-secrecy for AuthA. They claimed that under the by E. Bresson et al. [9], and argued that their proposal
Gap Diffie-Hellman assumption the variant of AuthA was was not created for the sake of having one more vari-
forward-secure in the random-oracle model. In this paper, ant, but simply because it allows them to prove forward-
we present an active attack to reveal a previously unpub- secrecy for AuthA [3]. They claimed that under the Gap
lished flaw in their proof. To fix their proof, we have to Diffie-Hellman assumption [12] the variant of AuthA was
introduce one more variant Diffie-Hellman assumption. If forward-secure in the random-oracle model.
so, we found the scheme proposed by E. Bresson et al.
could be proved forward secure as well. Since the pro-
posal of E. Bresson et al. is simpler for implementation In this paper, we present an active attack to reveal a
in practice, we only provided the rigorous proof of forward previously unpublished flaw in their proof. Indeed, we
security for it. found a significant gap in the reasoning of the proof given
in [3]. To fix their proof, we have to introduce one more
Keywords: Key exchange, password, security proof
variant Diffie-Hellman assumption. If so, we found the
slight variance, which made the scheme quite complicated,
was unnecessary any longer and the original scheme pro-
1 Introduction posed by E. Bresson et al. could also be proved forward
secure based on this new algorithmic assumption. Since
The Password Authenticated Key Exchange (PAKE) is the proposal of E. Bresson et al. is simpler for implemen-
a protocol which allows one party authenticate the other tation in practice, we only provide the rigorous proof of
party by a simple password known by the two parties forward security for it. There were ever many schemes
(that is, password-based authentication), and to agree on that were claimed to be provably secure but were found
a fresh symmetric key securely such that it is known only insecure subsequently. And the paradox was found often
to these two parties (that is, key exchange). Humans di- due to incorrectness of the proof, e.g. [10]. So the rigorous
rectly benefit from this approach since they only need to proof of security is especially important.
remember a low-quality string chosen from a relatively
small dictionary (e.g. 4 decimal digits). The vast major-
ity of protocols found in practice do not account, however, The remainder of this paper is organized as follows.
for such scenario and are often subject to so-called dictio- In Section 2, we introduce the formal model of security
nary attacks. So there is a great need for provably secure for password-based authenticated key exchange. Next,
password-authentication key-exchange technologies, espe- in Section 3, we presents algorithmic assumptions upon
cially for provably forward-secure ones that can protect which the security of the protocol is based upon. Section
the secrecy of session keys established before the corrup- 4 then reveals a previously unpublished flaw in the proof
tion. given in [3]. Section 5 presents the rigorous proof of for-
AuthA is a password-authentication key-exchange ward security for the proposal of E. Bresson et al.. Some
technology considered for standardization by the IEEE important remarks are also presented in this section. In
P1363.2 working group [6, 11]. Unfortunately in its orig- the last section, we conclude this paper.
International Journal of Network Security, Vol.7, No.3, PP.335–341, Nov. 2008 336
2 Security Models for Password- 2.2 Security Definitions
based Key Exchange In order to define a notion of security for the key exchange
protocol, we consider an experiment in which the proto-
A secure password-based key exchange is a key exchange col P is executed in the presence of the adversary A. In
protocol where the parties use their password in order to this experiment, we first draw a password pw from a dic-
derive a common session key sk that will be used to build tionary D, provide coin tosses and oracles to A, and then
secure channels. Loosely speaking, such protocols are said run the adversary, letting it ask any number of queries as
to be secure against dictionary attacks if the advantage of described above, in any order.
an attacker in distinguishing a real session key from a Forward Security. In order to model the forward se-
random key is less than O(n/ |D|) + (l) where |D| is the crecy (semantic security) of the session key, we consider
size of the dictionary D, n is the number of active sessions a game Gameake−f s (A, P), in which two additional or-
and (l) is a negligible function depending on the security acles are available to the adversary: the T est(U i ) and
parameter l. Corrupt(U ): oracle.
In this section, we recall the security model for
password-based authenticated key exchange of Bellare et
• T est(U i ): This query tries to capture the adversary’s
al. [5]. In this paper, we prove the protocol is secure in
ability to tell apart a real session key from a random
this model(referred as BPR2000 model).
one. In order to answer it, we first flip a (private)
coin b and then forward to the adversary either the
2.1 The Security Model session key sk held by U i (i.e., the value that a query
Reveal(U i ) would output) if b = 1 or a random key
We denote by A and S two parties that can participate of the same size if b = 0.
in the key exchange protocol. Each of them may have
several instances called oracles involved in distinct, pos- • Corrupt(U ): This query returns to the adversary the
sibly concurrent, executions of the protocol. We denote long-lived key pwU for participant U . As in [5], we
A (resp. S) instances by Ai (resp. S j ), or by U when we assume the weak corruption model in which the inter-
consider any user instance. The two parties share a low- nal states of all instances of that user are not returned
entropy secret pw which is drawn from a small dictionary to the adversary.
D, according to the uniform distribution.
The key exchange algorithm P is an interactive pro- The T est-oracle can be queried at most once by the
tocol between Ai and S j that provides the instances of adversary A and is only available to A if the attacked
A and S with a session key sk. The interaction between instance U i is FS-Fresh, which is defined to avoid cases
an adversary A and the protocol participants occurs only in which adversary can trivially break the security of the
via oracle queries, which model the adversary capabilities scheme. In this setting, we say that a session key sk is
in a real attack. The types of oracles available to the FS-Fresh if all of the following hold:
adversary are as follows:
1) the instance holding sk has accepted,
• Execute(Ai , S j ): This query models passive attacks
in which the attacker eavesdrops on honest execu- 2) no Corrupt-query has been asked since the beginning
tions between a client instance Ai and a server in- of the experiment; and
stance S j . The output of this query consists of the
messages that were exchanged during the honest ex- 3) no Reveal-query has been asked to the instance hold-
ecution of the protocol. ing sk or to its partner (defined according to the ses-
sion identification).
• Send(U i , m): This query models an active attack,
in which the adversary may intercept a message and In other words, the adversary can only ask T est-queries
then either modify it, create a new one, or simply to instances which had accepted before the Corrupt query
forward it to the intended participant. The output is asked. Let Succ denote the event in which the adver-
of this query is the message that the participant in- sary successfully guesses the hidden bit b used by T est
stance U i would generate upon receipt of message oracle. The FS-AKE advantage of an adversary A is then
m. defined as AdvP,D s (A) = 2P r[Succ] − 1 when pass-
ake−f
words are drawn from a dictionary D. The protocol P is
• Reveal(U i ): This query models the misuse of the said to be (t, ε)-FS-AKE-secure if A’s advantage is smaller
session key by instance U i (known-key attacks). If than ε for any adversary A running with time t. The def-
a session key is not defined for instance U i or if a inition of time-complexity that we use henceforth is the
T est query (see Section 2.2) was asked to either U i usual one, which includes the maximum of all execution
or to its partner, then return ⊥. Otherwise, return times in the experiments defining the security plus the
the session key held by the instance U i . code size [1].
International Journal of Network Security, Vol.7, No.3, PP.335–341, Nov. 2008 337
3 Algorithmic Assumptions security in the BPR2000 model, and then reveal the flaws
in their proof for it.
The arithmetic is in a finite cyclic group G = g of order The protocol was based on password-based key ex-
a l-bit prime number q, where the operation is denoted change protocols in [9], which in turn were based on the
multiplicatively. encrypted key exchange(EKE) of Bellovin and Merritt
[7, 8]. As illustrated on Figure 1, the protocol ran be-
3.1 GDH-Assumption tween two parties A and S, where H represents a hash
function from {0, 1} to {0, 1}l and G represents a full-
A (t, ε) − CDHg,G attacker in G is a probabilistic ma- domain hash function from {0, 1} to G. It ran as follows.
chine ∆ running in time t such that: Succcdh (A) = g,G The client chose at random a private random exponent x
P r[∆(g x , g y ) = g xy ] ≥ ε, where the probability is taken and computed its Diffie-Hellman public value g x . The
over the random values x and y(can equal to x). The client encrypted the latter value using a password-based
CDH-Problem is (t, ε)- intractable if there is no (t, ε)- mask, as the product of a Diffie-Hellman value with a full-
attacker in G. The CDH-assumption states that is the domain hash of the password, and sent it to the server.
case for all polynomial t and any non-negligible ε. The server in turn chose at random a private random ex-
A (t, n, ε) − GDHP,G attacker A is a (t, ε) − CDHP,G ponent y and computed its Diffie-Hellman public value g y
attacker, with access to an additional oracle: a DDH- which it encrypted using another password-based mask.
oracle, which on any input (g x , g y , g z ) answers whether The client (resp. server) then decrypted the flow it had
z = xy mod q. Its number of queries is limited to n. received and computed the session key sk using H.
Similarly, we can define the GDH-Problem and the GDH-
assumption. More information about them can be found
in [12]. We denote by Succgdh (n, t) the maximal success
g,G
probability over every such adversaries A.
3.2 PCGDH-Assumption
The so-called Password-based Chosen-basis CDH (PC-
CDH) problem is a variation of the computational Diffie-
Hellman that is more appropriate to the password-based
setting: Let D = {1, · · · , |D|} be a dictionary contain-
ing |D| equally likely password values and let M be a
public injective map from {1, · · · , |D|} into Zq . Now let
us consider an adversary A that runs in two stages. In
the first stage, the adversary is given as input three ran- Figure 1: An execution of M. Abdalla’s protocol
dom elements P (can be 1),Q and X(can equal to Q) in G
as well as as the public injective map M and it outputs M. Abdalla et al. claimed that under the Gap Diffie-
an element Y in G (the chosen-basis). Next, we choose Hellman assumption the protocol was forward-secure in
a random password k ∈ {1, · · · , |D|} and give it to thethe random-oracle model. Here we present an active at-
adversary. We also compute the mapping r = M(k) of tack (called Attk) to reveal a previously unpublished flaw
the password k. The goal of the adversary in this sec- in their proof. We assume the adversary A tries to imper-
ond stage is to output K = CDHg,G (X/P r , Y /Qr ). The sonate S to A. When A initiates the protocol execution
idea behind the password-based chosen-basis computa- with the first message A, X ∗ , A intercepts this mes-
tional Diffie-Hellman assumption is that the success prob- sage, produces an element Y ∗ ∈ G and then replies to A
ability Succpccdh (A) cannot be significantly larger than
g,G,M with S, Y ∗ as if it originated from S. Since, from A’s
1/|D| for any A running in polynomial time t, where |D| point of view,the message S, Y ∗ is perfectly indistin-
is the size of the dictionary D. More information about guishable from that of an honest execution, A believes
them can be found in [2, 4]. that the message is from S and accepts the execution
Similarly, we can define the PCGDH-Problem and the after A receives it. When A accepts the execution, A
PCGDH-assumption. We denote by Succpccdh (n, t) the
g,G,M asks T est-queries to the instance of A. Later, A cor-
maximal success probability over every such PCGDH- rupts the user A, thereby learning the shared password
adversaries A. with S, pw. Then A tries to find K ∈ G such that
K = CDHg,G (X ∗ /PWas , Y ∗ /PWsa ) if he can. Finally,
A asks the random oracle H with A S X ∗ Y ∗ pw K as
4 Flaws in the Security Proof input to obtain sk (denoted by the event AskHSK)and
Given by M. Abdalla thus knows the bit b involved in the T est-queries. The
attacker completely compromises the sematic security of
In this section, we revisit the protocol presented by M. the session key but one can not build an attacker against
Abdalla et al. (2005), which carries a proof of forward the GDH-assumption over G simply using A. M. Abdalla
International Journal of Network Security, Vol.7, No.3, PP.335–341, Nov. 2008 338
et al. argued that the probability that the event AskHSK
occurs was no larger than 1/|D| (For easy analysis, we
assume D is a uniformly distributed dictionary). It is not
correct.
Indeed, an adversary that correctly guessed the pass-
word pw in its first stage can easily find K ∈ G by com-
puting PWsa = G(S A pw), PWas = G(A S pw) and
making, for instance, Y ∗ = g y × PWsa so that K = X y .
If an adversary chose to guess the password and followed
this strategy, he can succeed with probability 1/|D|. How-
ever, one can not justly proved that no adversary can do
better than the adversary described above. Therefore,
there is a significant gap in the reasoning of the proof
given in [3]. Fortunately, we can prove that the protocol Figure 2: An execution of E. Bresson’s protocol
is forward-secure in the BPR2000 model by introducing
another algorithmic assumption— PCGDH-assumption.
Furthermore, we find the original scheme proposed by E. sive eavesdroppings (Execute-queries), and asking qh ,qg
Bresson et al. could also be proved forward secure based hash queries to any H, G respectively, AdvP,D s (A) ≤
ake−f
on this new algorithmic assumption. So their slight vari- (qp +qs )2 3q2 q2
q + qg + 2h + 6Succpcgdh (qh , t + 2τ ), where τ rep-
l g,G,D
ance, which made the scheme quite complicated, was un-
resents the computational time for an exponentiation in
necessary any longer. Due to this, we only provide the
G.
rigorous proof of forward security for the E. Bresson’s
scheme in the next section. Proof. Let A be an adversary against the semantic secu-
Notes. In the attack Attk, the adversary A queried rity of P. The idea is to use A to build adversaries for
the random oracle H only once. If the adversary is not each of the underlying primitives in such a way that if
allowed to ask Corrupt-oracle throughout the attack, we A succeeds in breaking the semantic security of P, then
can have P r[AskHSK] ≤ 1/|D| because the adversary has at least one of these adversaries succeeds in breaking the
to guess the password pw when he queries H. After all, security of an underlying primitive. Our proof consists of
pw appears explicitly as part of input to H query. a sequence of hybrid games, starting with the real attack
and ending in a game in which the adversary’s advantage
is 0, and for which we can bound the difference in the ad-
5 Security Proof for E. Bresson’s versary’s advantage between any two consecutive games.
Protocol In the following games Gamen , we study the event Sn
which occurs if the adversary correctly guesses the bit b
E. Bresson’s protocol is also a variation of the password- involved in the T est-query. Let us remember that in this
based EKE, where both flows are encrypted using a com- attack game, the adversary is provided with the Corrupt-
mon mask PW instead of separate ones, as shown in Fig- query.
ure 2. The protocol is simpler than that of M. Abdalla et Game0 : This is the real protocol in the random-oracle
al. and thus more practical. It is so because a full-domain model. By definition, we have
hash function G onto the represented group G is difficult
to implement directly in practice for some discrete groups AdvP,D s (A) = 2P r[S0 ] − 1.
ake−f
and usually contains an implicit exponentiation over G.
In that case, the computational cost of such hashes would Game1 : In this game, we simulate the hash oracles
be quite high. E. Bresson’s protocol require one less such (G, H but also additional hash function H : {0, 1}∗ →
operations for each side. {0, 1}l that will appear in the Game3 ) as usual by main-
In the rest of this section, we prove the E. Bresson’s taining hash lists ∧G , ∧H and ∧H (see Figure 3). We also
scheme is forward secure in the BPR2000 model. More simulate all the instances, as the real players would do,
specifically, as Theorem 1 states, the password-based key for the Send, Execute, Corrupt, and T est-queries. From
authenticated protocol is forward secure in the random or- this simulation, we easily see that the game is perfectly
acle model as long as we believe that the PCGDH problem indistinguishable from the real attack. Thus, we have
is hard in G.
P r[S1 ] = P r[S0 ].
Theorem 1. Let D be a uniformly distributed dictionary
of size |D|. Let P describe the password-based authenti- Game2 : For an easier analysis in the following, we can-
cated key exchange protocol associated with these prim- cel games in which some unlikely collisions Coll appear:
itives as defined in Figure 2. Then, for any adversary collisions on the partial transcripts((A, X ), (S, Y )) and
A within a time bound t, with less than qs active in- on hash values. Since transcripts involve at least one hon-
teractions with the parties (Send-queries) and qp pas- est party, and thus the probability are bounded by the
International Journal of Network Security, Vol.7, No.3, PP.335–341, Nov. 2008 339
For a hash query G(m) for which there exists a record If a) pw is corrupted ;
(m, r, ∗) in the list ΛG , return r. Otherwise the answer b) m is the form of A S X Y ;
r is defined according to the following rule: c) there is a record (m , r ) in the list
Rule G ΛH , where m =A S X Y P W K
| Choose an element r. The record (m, r, ⊥) to the and K = CDHg,G (X /P W, Y /P W )
list ΛG (checked using the DDH- oracle);
For a hash query H(m) for which there exists a record Then set r to r .
(m, r) in the list ΛH , return r. Otherwise the answer r Else
is defined according to the following rule: Then randomly choose r ∈ {0, 1}l .
Rule H Note we still stimulates the random oracle H and H
| Choose an element r ∈ {0, 1}l . perfectly since we just replaces some random values by
One adds the record (m, r) to the list ΛH . other random values. We can safely do so because colli-
For a hash query H (m) for which there exists a record sions of partial transcripts have been excluded in Game2 .
(m, r) in the list ΛH , return r.Otherwise the answer r The Games Game3 and Game2 are now indis-
is defined according to the following rule: tinguishable unless A queried the hash function H
Rule H on A S X Y P W K for some session transcript
| Choose an element r ∈ {0, 1}l . ((A, X ), (S, Y )) that corresponds to the session ID of
One add the record (m, r) to the list ΛH . a session accepted before the corruption: event DiffH.
This means that, for some transcript of this kind, the
tuple A S X Y P W K lies in the list ∧H . Note the
Figure 3: Simulation of random oracles G, H and H
adversary can only ask T est-queries to instances which
had accepted before corrupting the password. Since the
birthday paradox: session key is computed with the random oracle H that
is private to the simulator before the corruption, one can
2
(qp + qs )2 qg 2
qh remark that the bit b involved in the T est-query cannot
|P r[S2 ] − P r[S1 ]| ≤ P r[Coll] ≤ + + l+1 .
2q 2q 2 be guessed by the adversary, better than at random for
each attempt.
Game3 : In this game, we compute X , Y simply as
1
X = g x , Y = g y for two random integers x, y. Mean- |P r[S3 ] − P r[S2 ]| ≤ P r[DiffH] P r[S3 ] = .
time, we compute the session key sk using the private 2
oracles H instead so that the values sk is completely in- To bound the difference between this game and previ-
dependent not only from H, but also from pw and thus ous, our goal at this point shifts to computing the prob-
both KA and KS . More specifically, we computes it as ability of the event DiffH. We prove that the probability
follows: sk = H (A S X Y ). of such an event is negligible in Game4 .
Due to it, we do no longer need to compute the values Game4 : In order to evaluate the event DiffH, we re-
KA and KS , and we can postpone choosing the value of place the Rule G with the new rule Rule NG, where Q is
the password pw until the Corrupt query is asked by the a random element in G. The simulation introduces values
adversary A. in the third component of the elements of ∧G , but does
The games Game3 and Game2 are indistinguish- not use it. It would let the probabilities unchanged.
able unless A queries the hash function H on Rule NG
A S X Y P W K for some execution transcript Randomly choose k ∈ Zq , and compute r = Qk ;
((A, X ), (S, Y )), where K = KA or KA . To avoid the The record (m, r, k) is added to ∧G .
trivial difference in the sessions on which A uses the pass- For a more convenient analysis, we firstly exclude the
word he corrupted to mount an active attack, we make case Case0: PW = 1 . Since we just exclude k = 0, we
q q2
answers from H and H to be the same for such sessions have P r[Case0] ≤ qg ≤ q . Without Coll and Case0,
g
when they correspond to the same query. To do so, we the event DiffH can be split in 3 disjoint sub-cases as
replace the Rule H and Rule H with the following rules: follows. Note that both X and Y are produced before
Rule NH the corruption.
If a) pw is corrupted ;
b) m is the form of A S X Y P W K, • CaseA: Both X and Y have been sim-
where K = CDHg,G (X /P W, Y /P W ) ulated and there is an element P W such
(checked using the DDH- oracle); that (C, S, X , Y , P W, K) is in ∧H , with
c) no instance accepts the session before the K = CDHg,G (X /P W, Y /P W ) =
corruption; (Y /P W )x /(CDHg,G (Q, Y /kQ))k . As a con-
Then set r to H (A S X Y ). sequence, one can solve the PCGDH-problem. Thus,
Else we have P r[CaseA] ≤ Succpcgdh (qh , t + 2τ ).
g,G,,D
Then randomly choose r ∈ {0, 1}l . • CaseB: X has been simulated, but Y has been
Rule NH produced by the adversary. Due to Rule NH and
International Journal of Network Security, Vol.7, No.3, PP.335–341, Nov. 2008 340
Rule NH , we just need to consider those ses- schemes that were claimed to be provably secure but were
sions accepted before the corruption. If here is found insecure subsequently. And the paradox was found
an element P W such that (A, S, X , Y , P W, K) is often due to incorrectness of the proof. So the rigorous
in ∧H , with K = CDHg,G (X /P W, Y /P W ) = proof of security is especially important.
(Y /P W )x /(CDHg,G (Q, Y /kQ))k , we can have:
P r[CaseB] ≤ Succpcgdh (qh , t + 2τ ).
g,G,D
Acknowledgments
• CaseC: Y has been simulated, but X has been
produced by the adversary. Due to Rule NH and This work was supported by the National Natural Science
Rule NH , we just need to consider those ses- Fundation of China (60473021). The authors are grateful
sions accepted before the corruption. If here is to the anonymous reviewers for valuable comments.
an element P W such that (A, S, X , Y , P W, K) is
in ∧H , with K = CDHg,G (X /P W, Y /P W ) =
(X /P W )y /(CDHg,G (Q, X /kQ))k , we can have: References
P r[CaseC] ≤ Succpcgdh (qh , t + 2τ ).
g,G,D
[1] M. Abdalla, M. Bellare, and P. Rogaway, “The or-
As a consequence, acle Diffie-Hellman assumptions and an analysis of
DHIES,” CT-RSA ’01, LNCS 2020, pp. 143-158,
2
qg pcgdh Springer-Verlag, 2001.
P r[DiffH] ≤ + 3Succg,G,D (qh , t + 2τ ).
q [2] M. Abdalla, E. Bresson, O. Chevassut, B. M¨ller,
o
and D. Pointcheval, “Provably secure password-
Finally, combining all the above equations, one gets
based authentication in TLS,” ACM AsiaCCS ’06,
the announced result as follows.
pp. 35-45, 2006.
[3] M. Abdalla, O. Chevassut, and D. Pointcheval,
f tg−ake 1
AdvP,D (A) = 2P r[S0 ] − 1 = 2(P r[S0 ] − 2 ) “One-time verifier-based encrypted key exchange,”
1
= 2(P r[S1 ] − 2 ) PKC ’05, LNCS 3386, pp. 47-64, Springer-Verlag,
≤ 2(|P r[S1 ] − P r[S2 ]| + |P r[S2 ] − P r[S3 ]|) 2005.
2
(qp +qs )2 3qg 2
qh pcgdh [4] M. Abdalla, and D. Pointcheval, “Simple password-
≤ q + q + 2l + 6Succg,G,D (qh , t + 2τ ).
based encrypted key exchange protocols,” CT-RSA
’05, LNCS 3376, pp. 191-208, Springer-Verlag, 2005.
[5] M. Bellare, D. Pointcheval, and P. Rogaway, “Au-
Remark 1. In our proof, we reduce the problem to thenticated key exchange secure against dictionary
the SPGDH one when we evaluate P r[DiffH]. We can not attacks,” Eurocrypt ’00, LNCS 1807, pp. 139-155,
use the technique in [9] to upper-bound P r[DiffH] since Springer-Verlag, 2000.
the main idea of it is to reduce the problem to password-
[6] M. Bellare, and P. Rogaway, The AuthA Protocol for
guessing. The event DiffH can be due to some query that
Password-Based Authenticated Key Exchange, Tech-
occurs after the corruption. An example has been given
nical Report, IEEE P1363, Mar. 2000.
in the previous section. This technique in [9] can work
[7] S. M. Bellovin, and M. Merritt, “Encrypted key ex-
only when the Corrupt-oracle is not allowed in the model.
change: Password-based protocols secure against dic-
That is why the proof given in [3] was not correct.
tionary attacks,” Proceedings of the IEEE Sympo-
Remark 2. In [9], E. Bresson et al. also proposed
sium on Security and Privacy, pp. 72-84, 1992.
a password-based authenticated key exchange protocol,
[8] S. M. Bellovin, and M. Merritt, “Augmented en-
where only one flow was masked. The protocol can be
crypted key exchange: A password-based protocol
proved forward secure as above. Since the proof is very
secure against dictionary attacks and password file
similar, we omit it here.
compromise,” Proceedings of the 1st ACM Confer-
ence on CCS, pp. 244-250, 1993.
6 Conclusion [9] E. Bresson, O. Chevassut, and D. Pointcheval,
“New security results on encrypted key exchange,”
We have revealed a previously unpublished flaw in the PKC’04, LNCS 2947, pp. 145-158, Springer-Verlag,
proof given by M. Abdalla. To fix their proof, we intro- 2004.
duce one more variant Diffie-Hellman assumption. Since [10] N. Junghyun, K. Seungjoo, and W. Dongho,
their scheme is very similar to that of E. Bresson and “Security weakness in a three-party password-
the latter is more practical, we only present the rigor- based key exchange protocol using weil pair-
ous proof of forward security for the latter. Finally, we ing,” Cryptology ePrint Archive Report, 2005,
should point out that provable security is claimed against http://eprint.iacr.org/2005/269.ps.
all attacks, not just against known attacks. If the proof [11] P. D. MacKenzie, The PAK Suite: Protocols
is not correct, there is no guarantee that it will prevent for Password-Authenticated Key Exchange, IEEE
some potential attacks not identified. There were many P1363.2, Oct. 2002.
International Journal of Network Security, Vol.7, No.3, PP.335–341, Nov. 2008 341
[12] T. Okamoto, and D. Pointcheval, “The Gap- Yuefei Zhu is a professor of Zhengzhou Institute of In-
problems: A new class of problems for the security of formation Science Technology. His research interest is in-
cryptographic schemes,” PKC ’01, LNCS 1992, pp. formation security and cryptology.
104-118, Springer-Verlag, 2001.
Shuhua Wu is a Ph. D. candidate at Zhengzhou In-
stitute of Information Science Technology. His research
interest is information security.


Use: 0.0468