Public-Key Cryptography–Proceedings of PKC’06(April24–262006,New-York,NY,USA)芈月传主题曲
M.Yung,Y.Dodis,A.Kiayias,and T.Malkin Eds.Springer-Verlag,LNCS3958,pages427–440.
Password-based Group Key Exchange in a
Constant Number of Rounds
Michel Abdalla1,Emmanuel Bresson2,Olivier Chevassut3and David
Pointcheval1
1Departement d’Informatique,´Ecole normale sup´e rieure
45Rue d’Ulm,75230Paris Cedex05,France
{Michel.Abdalla,David.Pointcheval}@ens.fr
{mabdalla,pointche}@ens.fr
2Cryptology Department,CELAR,35174Bruz,France
emmanuel.,
3Lawrence Berkeley National Laboratory,Berkeley,CA94720,USA
v,www.v/~chevassu Abstract.With the development of grids,distributed applications are
spread across multiple computing resources and require efficient secu-
rity mechanisms among the processes.Although protocols for authenti-
cated group Diffie-Hellman key exchange protocols seem to be the natural
mechanisms for supporting these applications,current solutions are ei-
ther limited by the use of public key infrastructures or by their scalability,
requiring a number of rounds linear in the number of group members.To
overcome these shortcomings,we propose in this paper thefirst provably-
secure password-based constant-round group key exchange protocol.It
is based on the protocol of Burmester and Desmedt and is provably-
secure in the random-oracle and ideal-cipher models,under the Deci-
sional Diffie-Hellman assumption.The new protocol is very efficient and
fully scalable since it only requires four rounds of communication and
four multi-exponentiations per user.Moreover,the new protocol avoids
intricate authentication infrastructures by relying on passwords for au-
thentication.Keywords.Password-based Authentication,Group Key
Exchange.
1Introduction
Motivation.Modern distributed applications often need to maintain consis-tency of replicated information and coordinate the activities of many processes. Collaborative applications and distributed computations are both examples of these types of applications.With the development of g
rids[12],distributed com-putations are spread across multiple computing resources requiring efficient se-curity mechanisms between the processes.Although protocols for group Diffie-Hellman key exchange[5,7,6,8]provide a natural mechanism for supporting these applications,these protocols are limited in their scalability due to a number of rounds linear in the number of group members.An alternative is to use a proto-col for group key exchange that runs in a constant number or rounds[11,15,16].
c IACR2006.
428M.Abdalla et al.
The two measures of a protocol’s efficiency are the computational cost per mem-ber and the communication complexity(number of protocol rounds)of the given protocol.Since the Moore’s laws has told us that computing power grows faster than communication power,it is therefore natural to trade communication power for computing power in a group key exchange protocol.
欢聚一堂伴奏A password is the ideal authentication means to exchange a session key in the absence of public-key infrastructures or pre-distributed symmetric keys.In a group,the sharing of a password among the members greatly simplifies the setup of distributed applications[7,11].An example of distributed a
pplications could simply be the networking of all the devices attached to a human.Low-entropy passwords are easy for humans to remember,but cannot of course guarantee the same level of security as high-entropy secrets such as symmetric or asymmetric keys.The most serious attack against a password-based protocol is the so-called dictionary attack:the attacker recovers the password and uses it to imperson-ate the legitimate user.The low-entropy feature makes the job of the attacker easier since the attacker(off-line)runs through all the possible passwords in or-der to obtain partial information and to maximize his success probability.The minimum required from a protocol is security against this attack. Contributions.In the present paper,we study the problem of scalable pro-tocols for authenticated group Diffie-Hellman key exchange.Many researchers have studied and found solutions to this problem in the context of a Public-Key Infrastructure(PKI),yet a(secure)solution had to be found in the context of a(short)password shared among the members of the group.Two attempts in this direction are due to Dutta and Barua[11]and to Lee,Hwang,and Lee[17]. Unfortunately,adding authentication services to a group key exchange protocol is a not trivial since redundancy in theflows of the protocol can open the door to different forms of attacks.In fact,in Section3,we briefly describe attacks against the schemes of Dutta and Barua[11]and of Lee,Hwang,and Lee[17]. Then,in Section4,we show how to add password-authentication services to the Burmester and Desmedt scheme[9,10].Our protocol is provably secure in the random-oracle[4]and ideal-cipher models[3]under the Decisional Diffie-Hellman assumption.
Related Work.Following the work of Bresson the group Diffie-Hellman key exchange problem[5,7,6,8],several researchers have developed sim-ilar protocols but that run in a constant number of rounds.Katz and Yung[15] added authentication services to the original Burmester and Desmedt’s proto-col[9,10].Later,Kim,Lee and Lee extended the work of Katz and Yung to take into account the notion of dynamicity in the membership[16].The problem of adding password-authentication services followed shortly after.In[7],Bresson et al.proposed thefirst solution to the group Diffie-Hellman key exchange problem in the password-based scenario.Their protocol,however,has a total number of rounds which is linear in the total number of players in the group.In[11,17],two different password-based versions of Burmester-Desmedt protocol were proposed
Password-based Group Key Exchange in a Constant Number of Rounds429 along with proofs in the random-oracle and ideal-cipher models.Unfortunately, the latter two schemes are not secure.
Outline of the paper.The paper is organized as follows.In Section2,we recall the security model usually used for password-based group Diffie-Hellman key exchange.This model was previously defined in[7],but also takes advantage of[1].In Section3we recall Burmester-Desmedt scheme and describe attacks against the schemes of Dutta and Barua[11]and of Lee,Hwang,and Lee[17]. In Secti
on4,we describe the mechanics behind our protocol.In Section5,we show that our protocol is provably-secure in the random-oracle and ideal-cipher models under the Decisional Diffie-Hellman assumption.
2Security Model
2.1Password-Based Authentication
In the password-based authentication setting,we assume each player holds a password pw drawn uniformly at random from the dictionary Password of size N.This secret of low-entropy(N is often assumed to be pically less than a million)will be used to authenticate the parties to each other Unfortunately,one cannot prevent an adversary to choose randomly a pass-word in the dictionary and to try to impersonate a player.However such on-line exhaustive search(even if N is not so large)can easily be limited by requiring a minimal time interval between successive failed attempts or locking an account after a threshold of failures.Security against such active attacks is measured in the number of passwords the adversary can“erase”from the candidate list after a failure.
On the other hand,off-line exhaustive search cannot be limited by such prac-tical behaviors or comp
utational resources considerations.Hopefully,they can be prevented if the protocol is carefully designed and ensures that no information about the password can leak from passively eavesdropped transcripts,but also from active attacks.
2.2Formal Definitions
We denote by U1,...,U n the parties that can participate in the key exchange protocol P.Each of them may have several instances called oracles involved in
distinct,possibly concurrent,executions of P.We denote U i instances by U j
i .
The parties share a low-entropy secret pw which is uniformly drawn from a small dictionary Password of size N.
The key exchange algorithm P is an interactive protocol between the U i’s that provides the instances with a session key sk.During the execution of this protocol,the adversary has the entire control of the network,and tries to break the privacy of the key.
430M.Abdalla et al.
少女没有腰Remark1.In the“constant-round”protocols that we will study,simultaneous broadcasts are intensively used.However we do not make any assumption about the correctness of the latter primitive:it is actually a multi-cast,in which the adversary may delay,modify,or cancel the message sent to each recipient inde-pendently.
In the usual security model[7],several queries are available to the adversary to model his capability.We however enhance it with the Real-or-Random no-tion for the semantic security[1]instead of the Find-then-Guess.This notion is strictly stronger in the password-based setting.And actually,since we focus on the semantic security only,we can assume that each time a player accepts a key, the latter is revealed to the adversary,either in a real way,or in a random one (according to a bit b).Let us briefly review each query:
–Send(U j
i
,m):This query enables to consider active attacks by having A send-
ing a message to any instance U j
i .The adversary A gets back the response U j
i
generates in processing the message m according to the protocol P.A query Send(Start)initializes the key exchange algorithm,and thus the adversary receives the initialflows sent out by the instance.
–Test b(U j
i ):This query models the misuse of the session key by instance U i
(known-key attacks).The query is only available to A if the attacked instance actually“holds”a session key.It either releases the actual key to A,if b=1 or a random one,if b=0.The random keys must however be consistant between users in the same session.Therefore,a random key is simulated by the evaluation of a random function on the view a user has of the session: all the partners have the same view,they thus have the same random key (but independent of the actual view.)
Remark2.Note that it has been shown[1]that this query is indeed enough to model known-key attacks—where Reveal queries,which always answer with the real keys,are available—,and makes the model even stronger.Even though their result has only been proven in the two-party and three-pa
rty scenarios,one should note that their proof can be easily extended to the group scenario.
As already noticed,the aim of the adversary is to break the privacy of the session key(a.k.a.,semantic security).This security notion takes place in the context of executing P in the presence of the adversary A.Onefirst draws a password pw from Password,flips a coin b,provides coin tosses to A,as well as access to the Test b and Send oracles.
The goal of the adversary is to guess the bit b involved in the Test queries, by outputting this guess b .We denote the AKE advantage as the probability that A correctly guesses the value of b.More precisely we define Adv ake P(A)= 2Pr[b=b ]−1.The protocol P is said to be(t, )-AKE-secure if A’s advantage is smaller than for any adversary A running with time t.
Password-based Group Key Exchange in a Constant Number of Rounds431 2.3On the Simplification of the Model
In previous models,Execute queries were introduced to model passive eaves-dropping.However,they can easily be simulated using the Send queries.In our analysis,we refine the way to deal with the adversary possible behaviors.We will denote by q active the number of messages the adversary produced by himself(thus without including those he has just forwarded).This number upper-bounds
the number of on-line“tests”the adversary performs to guess the password.And we denote by q session the total number of sessions the adversary has initiated: nq session,where n is the size of the group,upper-bounds the total number of mes-sages the adversary has sent in the protocol(including those he has built and those he has just forwarded).We emphasize that this is stronger than consider-ing only Execute and Send queries:while being polynomially equivalent,the two models are not tightly equivalent,since the adversary does not need to know in advance if he will forward all theflows,or be active when a new session starts. Moreover,suppressing the Execute queries makes the model even simpler.
The best we can expect with such a scheme is that the adversary erases no more than1password for each session in which he plays actively(since there exists attacks which achieve that in any password-based scheme.)However,in our quite efficient scheme,we can just prevent the adversary from erasing more than1password for each player he tries to impersonate(we will even show our proof is almost optimal.)
3Preliminaries
The best starting point for an efficient password-based group key exchange, and namely if one want
s a constant-round protocol,is the scheme proposed by Burmester and Desmedt[9,10]at Eurocrypt94and later formally analyzed by Katz and Yung in2003[15].
3.1The Burmester and Desmedt Protocol
In the Burmester-Desmedt scheme,one considers a cyclic group G generated by g,in which the Decisional Diffie-Hellman(DDH)assumption holds.The protocol works as follows,where all the indices are taken modulo n(between1and n), and n is the size of the group:
–Each player U i chooses a random exponent x i and broadcasts z i=g x i;
–Each player computes the Z i=z x i
i−1and Z i+1=z x i+1
i
=z x i
i+1
,
and broad-
casts X i=Z i+1/Z i;
–Each player computes his session key as K i=Z n i X n−1
i X n−2
i+1
···X i+n−2.
It is easy to see that for any i,we have K i= j=n
j=1
Z j=g x1x2+x2x3+···+x n x1.
432M.Abdalla et al.
3.2A Naive Password-Based Approach
We immediately note that encrypting values in the second round would lead to a trivial dictionary attack,since the product of all values is equal to1.One may want to enhance the Burmester and Desmedt’s protocol by using a password pw to“mask”thefirst round only.One then comes up to the simple protocole,using a mask of the form h pw,where h is another generator of the group G,whose discrete logarithm in the base g is unknown[2]:
–Each player U i chooses a random exponent x i,computes z i=g x i and broad-casts z i=z i h pw;
–Each player extracts z i−1and z i+1,and computes the Z i=z x i
i−1and Z i+1=
z x i+1 i =z x i
i+1
.He then broadcasts X i=Z i+1/Z i;
–Each player computes his secret as K i=Z n i X n−1
i X n−2
i+1
···X i+n−2
Thereafter,one can add any key confirmation and/or any intricate key extrac-tion(even in the random oracle model,such as sk i=H(View,K i)),but it does not help.Indeed,the homomorphic property of this“masking”technique allows active attacks from the adversary:Assume that the adversary impersonates play-ers U1and U3and sends for thefirst round z 1=g u1and z 3=g u3,for known values u1and u3.On the second round,the adversary waits for receiving X2 from player U2:
X2=
赵惟依暗黑图z3
z1
x2
=g x2(u3−u1)=
天天向上吴磊z
2
h pw
u3−u1
.
Then one knows that h pw=z2/X(u1−u3)−1
2,which can be easily checked off-line:
a dictionary attack.
Furthermore,one can be easily convinced that any mechanism such as proof of knowledge,“enforce”the adversary to properly construct his values are useless against this attack,since in the above attack,the adversary plays“honestly”.
3.3The Dutta and Barua Protocol
Dutta and Barua[11]proposed a variant of the Kim-Lee-Lee protocol[16]pre-sented at Asiacrypt’04.It
makes use of the ideal-cipher model,instead of a simple mask as above,and is claimed to be secure against dictionary attacks:–Each player U i chooses a random exponent x i,as well as a random key k i, computes z i=g x i,and broadcasts z i=E pw(z i);
–Each player extracts z i−1and z i+1,and computes the K L i=H(z x i
i−1
)=
H(g x i−1x i)and K R i=H(z x i+1
i )=H(z x i
i+1
)=H(g x i x i+1).For i=1,...,n−1,渴望春天伴奏
U i computes X i=K L i⊕K R i,while U n computes X n=k n⊕K R n;For i=1,...,n−1,U i broadcasts E pw(k i X i),while U n broadcasts E (X n);–After decryption,they can all recover all the k i,and then the common session key is set as sk=H(k1 ... k n).
发布评论