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-bad 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.bresson@polytechnique,emmanuel.bresson
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 cu-
狮子座女性格rity mechanisms among the process.Although protocols for authenti-
cated group Diffie-Hellman key exchange protocols em to be the natural
mechanisms for supporting the applications,current solutions are ei-
ther limited by the u of public key infrastructures or by their scalability,
requiring a number of rounds linear in the number of group members.To
overcome the shortcomings,we propo in this paper thefirst provably-
cure password-bad constant-round group key exchange protocol.It
is bad on the protocol of Burmester and Desmedt and is provably-
cure 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 ur.Moreover,the new protocol avoids
intricate authentication infrastructures by relying on passwords for au-
thentication.Keywords.Password-bad Authentication,Group Key
Exchange.
1Introduction
Motivation.Modern distributed applications often need to maintain consis-tency of replicated information and coordinate the activities of many process. Collaborative applications and distributed computations are both examples of the types of applications.With the development of g
rids[12],distributed com-putations are spread across multiple computing resources requiring efficient -curity mechanisms between the process.Although protocols for group Diffie-Hellman key exchange[5,7,6,8]provide a natural mechanism for supporting the applications,the protocols are limited in their scalability due to a number of rounds linear in the number of group members.An alternative is to u 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 ssion key in the abnce of public-key infrastructures or pre-distributed symmetric keys.In a group,the sharing of a password among the members greatly simplifies the tup 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 cour guarantee the same level of curity as high-entropy crets such as symmetric or asymmetric keys.The most rious attack against a password-bad protocol is the so-called dictionary attack:the attacker recovers the password and us it to imperson-ate the legitimate ur.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 curity against this attack. Contributions.In the prent paper,we study the problem of scalable pro-tocols for authenticated group Diffie-Hellman key exchange.Many rearchers have studied and found solutions to this problem in the context of a Public-Key Infrastructure(PKI),yet a(cure)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 rvices 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 rvices to the Burmester and Desmedt scheme[9,10].Our protocol is provably cure 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],veral rearchers have developed sim-ilar protocols but that run in a constant number of rounds.Katz and Yung[15] added authentication rvices 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 rvices followed shortly after.In[7],Bresson et al.propod thefirst solution to the group Diffie-Hellman key exchange problem in the password-bad 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-bad versions of Burmester-Desmedt protocol were propod
Password-bad 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 cure.
Outline of the paper.The paper is organized as follows.In Section2,we recall the curity model usually ud for password-bad 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-cure in the random-oracle and ideal-cipher models under the Decisional Diffie-Hellman assumption.
2Security Model
2.1Password-Bad Authentication
芋头泥In the password-bad authentication tting,we assume each player holds a password pw drawn uniformly at random from the dictionary Password of size N.This cret of low-entropy(N is often assumed to be pically less than a million)will be ud to authenticate the parties to each other Unfortunately,one cannot prevent an adversary to choo randomly a pass-word in the dictionary and to try to impersonate a player.However such on-line exhaustive arch(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“era”from the candidate list after a failure.
On the other hand,off-line exhaustive arch 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 veral 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 cret 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 ssion 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 ud.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 nt to each recipient inde-pendently.
In the usual curity model[7],veral queries are available to the adversary to model his capability.We however enhance it with the Real-or-Random no-tion for the mantic curity[1]instead of the Find-then-Guess.This notion is strictly stronger in the password-bad tting.And actually,since we focus on the mantic curity 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 nd-
ing a message to any instance U j
章鱼怎么做才好吃i .The adversary A gets back the respon 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 nt out by the instance.
–Test b(U j
i ):This query models the misu of the ssion key by instance U i
(known-key attacks).The query is only available to A if the attacked instance actually“holds”a ssion key.It either releas the actual key to A,if b=1 or a random one,if b=0.The random keys must however be consistant between urs in the same ssion.Therefore,a random key is simulated by the evaluation of a random function on the view a ur has of the ssion: 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 ssion key(a.k.a.,mantic curity).This curity notion takes place in the context of executing P in the prence of the adversary A.Onefirst draws a password pw from Password,flips a coin b,provides coin toss 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 guess the value of b.More precily we define Adv ake P(A)= 2Pr[b=b ]−1.The protocol P is said to be(t, )-AKE-cure if A’s advantage is smaller than for any adversary A running with time t.
Password-bad 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 himlf(thus without including tho 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 ssion the total number of ssions the adversary has initiated: nq ssion,where n is the size of the group,upper-bounds the total number of mes-sages the adversary has nt in the protocol(including tho he has built and tho 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 ssion starts. Moreover,suppressing the Execute queries makes the model even simpler.
The best we can expect with such a scheme is that the adversary eras no more than1password for each ssion in which he plays actively(since there exists attacks which achieve that in any password-bad 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-bad group key exchange, and namely if one want
s a constant-round protocol,is the scheme propod 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 choos 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 ssion key as K i=Z n i X n−1
i X n−2
i+1
···X i+n−2.
It is easy to e 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-Bad Approach
We immediately note that encrypting values in the cond 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,who discrete logarithm in the ba g is unknown[2]:
–Each player U i choos 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 cret 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 nds for thefirst round z 1=g u1and z 3=g u3,for known values u1and u3.On the cond 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 uless against this attack,since in the above attack,the adversary plays“honestly”.
劳务合同范本免费下载3.3The Dutta and Barua Protocol
朋友用英语怎么读Dutta and Barua[11]propod a variant of the Kim-Lee-Lee protocol[16]pre-nted at Asiacrypt’04.It
makes u of the ideal-cipher model,instead of a simple mask as above,and is claimed to be cure against dictionary attacks:–Each player U i choos 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 ssion key is t as sk=H(k1 ... k n).
