9512.net
甜梦文库
当前位置:首页 >> >>

New multiparty authentication services and key agreement protocols


IEEE Journal of Selected Areas in Communications, VOL 18, NO. 4, April 2000

1

New Multi-party Authentication Services and Key Agreement Protocols
Giuseppe Ateniese, Michael Steiner, Gene Tsudik
Abstract — Many modern computing environments involve dynamic peer groups. Distributed simulation, multi-user games, conferencing applications and replicated servers are just a few examples. Given the openness of today’s networks, communication among peers (group members) must be secure and, at the same time, e?cient. This paper studies the problem of authenticated key agreement in dynamic peer groups with the emphasis on e?cient and provably secure key authentication, key con?rmation and integrity. It begins by considering 2-party authenticated key agreement and extends the results to Group Di?e-Hellman key agreement. In the process, some new security properties (unique to groups) are encountered and discussed. Keywords — Communication system security, Collaborative work, Dynamic group setting, Authentication, Key establishment/agreement protocols, Decision Di?e-Hellman problem.

I. Introduction HIS paper is concerned with security services in the context of dynamic peer groups (DPGs). Such groups are common in many layers of the network protocol stack and many application areas of modern computing. Examples of DPGs include replicated servers (such as database, web, time), audio and video conferencing and, more generally, collaborative applications of all kinds. In contrast to large multicast groups, DPGs tend to be relatively small in size, on the order of a hundred members. (Larger groups are harder to control on a peer basis and are typically organized in a hierarchy of some sort.) DPGs typically assume a many-to-many communication pattern rather than oneto-many commonly found in larger, hierarchical groups. The speci?c security requirements and needs of dynamic
Giuseppe Ateniese is currently the IBM Zurich Research Laboratory, 8803 R¨ uschlikon, Switzerland. E-mail: gat@zurich.ibm.com. Work done while visiting USC Information Sciences Institute. Michael Steiner is currently at the Universit¨ at des Saarlandes, 66123 Saarbr¨ ucken, Germany. E-mail: steiner@acm.org. Work done while working for the IBM Zurich Research Laboratory, 8803 R¨ uschlikon, Switzerland. Gene Tsudik is with the USC Information Sciences Institute, Marina del Rey, CA 90292, USA. E-mail: gts@isi.edu. Research supported by the Defense Advanced Research Project Agency, Information Technology O?ce (DARPA-ITO), under contract DABT63-97C-0031. Appeared in the IEEE Journal of Selected Areas in Communications, Vol 18, No. 4, April 2000. A preliminary version of this paper was presented at the 5th ACM Conference on Computer and Communications Security, San Francisco, CA, November, 1998. Manuscript received February 7, 1999; revised August 30, 1999. A preliminary version of this paper was presented at the 5th ACM Conference on Computer and Communications Security, San Francisco, CA, November, 1998. c 2000 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other must be obtained from the IEEE.

T

peer groups – in particular, key management – are still considered as open research challenges [1]. Recently, several key agreement protocols geared for DPGs were proposed in [2]. They were obtained by extending the well-known Di?e-Hellman key exchange method [3] to groups of n parties. These protocols perform what we refer as initial key agreement (IKA) within a group. Once a group is formed and the initial key is agreed upon, group members may leave (or be excluded) and new members may join. Moreover, entire groups may join and entire sub-groups may need to be excluded. Any membership change must cause a corresponding group key change in order to preserve key independence.1 Since re-running full IKA for each membership change is expensive, other supporting protocols are necessary. The operations supported by these protocols are collectively called auxiliary key agreement (AKA). AKA protocols, also based on Di?e-Hellman extensions, have been developed in [4]. Both IKA and AKA protocols have been shown secure against passive adversaries. (The security is based on the polynomial indistinguishability of a Di?e-Hellman key from an arbitrary random value.) This paper leverages the results of [2], [4] to develop practical and secure authenticated key agreement protocols for DPGs. Also considered are other relevant security features such as key con?rmation, key integrity and entity authentication. In doing so, we discover that the meaning of these and other familiar notions need to be rede?ned in a peer group setting. Our long-term goal is the development of a comprehensive protocol suite and a toolkit for secure communication in DPGs. Although the focus is on relatively small non-hierarchical peer groups, no speci?c communication paradigm (e.g., RPC, connection-oriented) is favored, and no assumptions are made about either the topology or technology of the underlying network. The remainder of the paper is organized as follows. We ?rst discuss the general requirements and issues in authenticated key agreement as well as previous work on this ?eld. After presenting some necessary terminology in Section IV we proceed (in Section V) to develop a 2-party authenticated key agreement protocol based on the Di?e-Hellman method. We then extend the protocol to n parties (i.e., a DPG) and demonstrate security of the result in Section VI-A. Next, we consider complete group key authentication (bilateral among all group members) in Section VI-B and discuss key integrity and key con?rmation features. The paper concludes with the discussion of other group secu1 Informally, this means that old keys cannot be known to new members and new keys cannot be known to former members.

2

IEEE Journal of Selected Areas in Communications, VOL 18, NO. 4, April 2000

rity services that are contingent upon authenticated key agreement. II. Key Establishment Protocols Key establishment protocols can be roughly classi?ed in two categories: key agreement protocols [4] and (centralized) key distribution protocols based on some form of a trusted third party (TTP). Although, in this paper we focus on contributory key agreement, we brie?y note several features of centralized key distribution that make it unsuitable for DPGs: ? A TTP that generates and distributes keys for a multitude of groups is a single point of failure and a likely performance bottleneck. ? Since all group secrets are generated in one place, a TTP presents a very attractive attack target for adversaries. This is especially the case if a TTP serves as the key generation/distribution center for multiple groups. ? Environments with no hierarchy of trust are a poor match for centralized key transport. (For example, consider a peer group composed of members in di?erent, and perhaps competing, organizations or countries.) ? Some DPG environments (such as ad hoc wireless networks) are highly dynamic and no group member can be assumed to be present all the time. However, most key distribution protocols assume ?xed centers. ? It might be simply unacceptable for a single party to generate the group key. For example, each party may need assurance that the resulting group key is fresh and random (e.g., in case the key is later used for computing digital signatures). ? Achieving perfect forward secrecy (Def. IV.7 below) and resistance to known-key attacks (Def. IV.8 below) in an e?cient manner is very di?cult in the centralized key distribution setting. Although we argue in favor of distributed, contributory key agreement for DPGs, we also recognize the need for a central point of control for group membership operations such as adding and deleting members. This type of a role (group membership controller) serves only to synchronize the membership operations and prevent chaos. However, the existence and assignment of this role is orthogonal to key establishment and is largely a matter of policy. III. Previous Work We now present several prior results in multi-party key agreement protocols. None of them provide any key authentication services and all are resistant only against passive attacks. Moreover, it is unclear how to add authentication services to these schemes. One mathematically elegant proposal was proposed by Fiat et al. in [5]. A trusted center T selects a RSA-like modulus n = pq and a secret element α ∈ Z Z? n of large multiplicative order (such that it is hard to compute discrete logarithms). For any 1 ≤ i ≤ t, each party Mi receives αxi mod n from T , with xi random and relatively prime with xj for j = i. In order to establish a secret group key S , each

party Mi broadcasts xi and then, after collecting all messages, computes S = (αxi )x1 ···xi?1 xi+1 ···xt (mod n) (i.e. a Di?e-Hellman key with all the contributions). Drawbacks of this protocol are that 1) it requires a trusted third party (T ) and, 2) as shown in [5], two or more parties can collude and recover the secret α. Another interesting scheme was presented in [6]. Given a g ∈ Zp? with p prime, each party Mi computes and broadcasts yi = g xi (mod p), where xi is a randomly chosen secret. After receiving all the contributions, M1 computes the group key: S = g xt g
xt?1 g... x3 g x2 x1

.

Note that to come up with the same group key, the other protocol parties needs to behave di?erently since the order of exponentiation is right to left, i.e., the protocol is asymmetric. In particular, for j = 3, . . . , t ? 1, Mj sends vj = g vj?1 to Mj +1 (where v2 = y1 ) and then computes S . The party Mt simply waits vt?1 from Mt?1 and then xt computes S = vt ?1 . One notable recent result is due to Burmester and Desmedt [7]. They construct a very e?cient protocol (BD) which executes in only three rounds: 1. Each Mi generates its random exponent xi and broadcasts zi = αxi . 2. Each Mi computes and broadcasts Wi = (zi+1 /zi?1 )xi txi t?1 · 3. Each Mi can now compute the key S = zi ?1 · Wi t?2 Wi+1 · · · Wi?2 mod p The resulting key is S = αx1 x2 +x2 x3 +···+xt x1 . The protocol is proven secure provided the DH problem is intractable. However, there are some important assumptions underlying this protocol. Speci?cally, it requires each Mi to broadcast to the rest of the group and to receive t ? 1 messages in a single round. Moreover, the system has to handle t simultaneous broadcasts (in one round). As mentioned in Section I, Steiner et al. [4] introduced a class of protocols, called generic Group Di?e-Hellman (GDH) key agreement. This entire class has been proven resistant against passive attacks. In brief, [4] shows that if a 2-party DH key is indistinguishable from a random value then a t-party DH key is also indistinguishable from a random value. Later in this paper, we describe in more detail some of the GDH protocols and extend them to provide authentication services. IV. Goals, Definitions and Notation In addition to key independence alluded to above and resistance to all types of passive attacks, desired properties for a practical key agreement protocol typically include the following: ? Key Authentication ? Perfect Forward Secrecy (PFS) ? Resistance to Known-Key Attacks ? Key Con?rmation and Key Integrity All of these are necessary to achieve resistance to active attacks mounted by an increasingly powerful adversary. And,
xj

ATENIESE, STEINER AND TSUDIK: New Multi-party Authentication Services and Key Agreement Protocols

3

as always, ironclad security must be achievable with the lowest possible cost. We now present some de?nitions for the above and other terminology used in this paper. (Some of these are adapted from Menezes et al. [8]) De?nition IV.1: A key agreement protocol is a key establishment technique whereby a shared secret key is derived by two or more speci?ed parties as a function of information contributed by, or associated with, each of these, such that no party can predetermine the resulting value. De?nition IV.2: A key agreement protocol is contributory if each party equally contributes to the key and guarantees its freshness. For example, according to this de?nition, the basic twoparty Di?e-Hellman protocol is contributory. On the other hand, the ElGamal one-pass [8] protocol is not contributory as only one of the parties contributes a fresh exponent. De?nition IV.3: Let R be an n-party key agreement protocol, M be the set of protocol parties and let Sn be a secret key jointly generated as a result of R. We say that R provides implicit key authentication if each Mi ∈ M is assured that no party Mq ∈ / M can learn the key Sn (unless aided by a dishonest Mj ∈ M). De?nition IV.4: A protocol provides key con?rmation if a party is assured that its peer (or a group thereof) actually has possession of a particular secret key. De?nition IV.5: A contributory key agreement protocol provides key integrity if a party is assured that its particular secret key is a function of only the individual contributions of all protocol parties. In particular, extraneous contribution(s) to the group key cannot be tolerated even if it does not a?ord the attacker(s) with any additional knowledge. De?nition IV.6: An authenticated group key agreement protocol is a key agreement protocol which provides implicit key authentication. De?nition IV.7: A protocol o?ers perfect forward secrecy (PFS) if compromise of a long-term key(s) cannot result in the compromise of past session keys. De?nition IV.8: A protocol is said to be vulnerable to known-key attack if compromise of session keys allows: 1) a passive adversary to compromise keys of other sessions, or 2) an active adversary to impersonate one of the protocol parties. (See [9], [10], for details.) The notation as used throughout the paper is shown in Figure 1. All arithmetic throughout the paper is performed in a cyclic group G of prime order q which is a subgroup of Z Z? p for a prime p such that p = kq + 1 for some small k ∈ N (e.g. k = 2). No practical methods are known to compute partial information with respect to discrete logarithms (DL) in subgroup with this setting. Most DL-based schemes have been designed using a prime order subgroup. One of the advantages of working in such a group is that all the elements (except the unity element) are generators of the subgroup itself. Moreover, using subgroup of prime order seems to be a prudent habit [11]; it also results in increased e?ciency.

n i, j Mi p, q G α xi ri Sn Sn (Mi) Kij F ()

number of protocol parties (group members) indices of group members i-th group member; i ∈ [1, n] p, q prime, q |φp unique subgroup of Z Z? p of order q exponentiation base; generator in group G long-term secret key of Mi Mi ’s secret exponent ∈R Z Zq group key shared among n members Mi ’s view on a group key long-term secret shared by Mi and Mj a function mapping elements from G to Z Zq
Fig. 1 Notation

When operating in subgroups it is important to take into account the attacks outlined in [11], [12]. To prevent masquerading or leaking of (even partial) information of the secret values, each party has to verify that the purportedly random values it receives are in fact elements of the subgroup.2 Note that p, q and α are public and common to all users. Since they need to be generated only once (or very seldom), it is desirable to make the generation process unpredictable yet veri?able to prevent the selection of weak or special primes. One approach is to use the NIST method for selecting DSA primes as described in the FIPS 186 document [13]. In this context, the ability of an active adversary C to modify or inject messages is quite “limited”. In fact, any message m can be written as m = αc (mod p), where α is a generator of the unique cyclic subgroup of Z Z? p having order q and c some exponent (perhaps unknown). Later on, we will suppose that the adversary C operates on this type of elements. V. Authenticated 2-party Key Agreement In this section we develop an extension to the Di?eHellman (DH) [3] key agreement method that provides key authentication. We explicitly avoid requiring any cryptographic tools (e.g., symmetric encryption or signatures) other than those necessary for plain DH key agreement. Before turning to the actual protocol, it is important to emphasize that there exist secure protocols for authenticated DH-based key agreement. However, some are not contributory (such as El Gamal), some require more messages or assume a priori access to certi?ed long-term keys, while others do not o?er PFS or are vulnerable to so-called known-key attacks. (For example, some of the protocols
2 Verifying the order of an element x by checking, for example, that x(p?1)/q (mod p) = 1, is rather expensive. If p and q are carefully chosen such that the other prime factors of φ(p)/2 are close to the order of q , we can exclude elements of small order in an e?cient manner by checking that x2 = 1 (mod q ). Although this seems to be su?cient, the security of this method needs further study [12].

4

IEEE Journal of Selected Areas in Communications, VOL 18, NO. 4, April 2000

in the MTI protocol family [14].) An additional goal is to come up with a protocol that is easily extendible from 2- to n-party key agreement. Yet another, perhaps super?cial, issue has to do with minimizing the security dependencies of a protocol. For example, an authenticated DH-based key agreement can be easily constructed with the aid of conventional encryption. The security of the underlying protocol would then be dependent not only on the di?culty of, for example, the Di?e-Hellman Decision (DDH) problem (as far as key agreement) but also on the strength of the conventional encryption (as far as key authentication). Ideally, it should be possible to base all the security properties of a given protocol on a single hard problem such as the DDH problem in prime-order subgroups. Protocol A-DH: Let p, q , G be as de?ned above, and let α be a generator of G. Initialization: Let x1 and x2 be two integers such that 1 ≤ x1 , x2 ≤ q ? 1. Let M1 and M2 be two parties wishing to share a key and let (x1 , αx1 (mod p)) and (x2 , αx2 (mod p)) be the secret and public keys of M1 and M2 , respectively. Thus, the public values of the system are (p, q, α, αx1 , αx2 ). The actual protocol is as follows: Round 1: 1. M1 selects r1 ∈R Z Z? q. r1 2. M1 ?→ M2 : α (mod p) Round 2: x1 x2 1. M2 selects r2 ∈R Z Z? q , and computes K = F (α (mod p)). 2. M2 ?→ M1 : αr2 K (mod p) When M1 receives J = αr2 K (mod p), computes K ?1 ?1 (mod q ) and then J r1 K (mod p). The shared secret key is S2 = αr1 r2 (mod p). Function F () maps elements from G to Z Zq . If p is a safe prime (p = 2q + 1) then a perfect mapping function would be F (x)= x if (x < q ), q ? x if (x >= q ).
Fig. 2 Authenticated Diffie-Hellman (A-DH)

One protocol that satis?es the above criteria is A-DH, shown in Figure 2. It provides implicit key authentication as stated by the following theorem. Theorem V.1: The A-DH protocol is a contributory authenticated key agreement protocol. Proof: From the construction of the resultant session key S2 = αr1 r2 it is evident that A-DH is contributory. In our model we assume that the two parties M1 and M2 , wishing to share a secret, behave correctly. Moreover, we assume that any value computed as session key (S2 ), by each party, is kept secret, i.e. it is infeasible for an attacker to obtain any (even partial) information about GK2 . Let C be an active adversary able to modify, delay, or inject mes-

sages. C ’s goal is to obtain the secret shared by M1 and M2 , if any. There are four possible attack scenarios which we treat separately below. To prove our claim we use the following approach: if the attacker C were able to use a nondeterministic Turing machine T M to obtain information about the secret key, then the same T M could be used to solve an instance of the Di?e-Hellman Problem (DHP). The notation T M (x1 , . . . , xn ) = y means that, given input x1 , . . . , xn , T M outputs y . 1. A-DH ends correctly (passive attack). Suppose there exists a nondeterministic Turing machine T M1 by which the attacker C is able to ?nd the secret session key, i.e. T M1 (αr1 , αr2 K ) = αr1 r2 . Since r1 and r2 are randomly chosen, it is easy to see that T M1 could be used to solve a generic instance of DHP. In fact, given αa and αb , with unknown a, b, we would have T M1 (αa , αbK ) = αab . 2. C substitutes αr1 with αx . For simplicity’s sake, we can assume that the attacker C knows the value x. The secret computed by M1 is αr1 r2 . The problem of computing this value has been treated in the previous case. The secret computed by M2 is αxr2 . The easiest way to compute this value is extracting αr2 from αr2 K . But this is as hard as DH problem if K is the DH value of the public-keys of M1 and M2 . 3. C substitutes αr2 with αy . Suppose the attacker C knows the value y . The secret computed by M2 is αr1 r2 . The hardness of computing this value has been already treated in previous cases. C can compute the M1 ’s secret, ?1 ?1 αyr1 K , trying to get the value αr1 K . However, com?1 puting αr1 K is as hard as DHP if K is the DH value of the public-keys of M1 and M2 . 4. C substitutes αr1 , αr2 with αx and αy , respectively. Since the A-DH protocol’s messages are each other independent, this case is analogous to the cases 2 and 3. qed On top of implicit key authentication, a practical key agreement protocol must: 1) provide perfect forward secrecy and 2) be resistant to known-key attacks. These two properties are considered in the following theorems. Theorem V.2: The A-DH protocol provides perfect forward secrecy (PFS). Proof: Suppose that the long-term key K = F (αx1 x2 (mod p)) is compromised. Then, an adversary knows both ?1 αr1 (mod p) and α(r2 K )K ≡ αr2 (mod p). Given these, computing the session key S2 = αr1 r2 (mod p) is equivalent to solving the DH problem in prime-order subgroups. Theorem V.3: The A-DH protocol is resistant to knownkey attacks. Proof: The scenario is the following: the attacker C is able to modify both the A-DH protocol’s messages and then get the values computed by each party M1 and M2 as secret key. From these values, C tries to compute information by which he can impersonate one of the protocol parties. For the sake of simplicity, we can assume that the target of the attacker C is ?nding αK by which he can impersonate M2 . There are four cases to consider:

ATENIESE, STEINER AND TSUDIK: New Multi-party Authentication Services and Key Agreement Protocols

5

1. C knows αr1 , αr2 K and αr1 r2 (passive known-key attack). 2. C substitutes αr1 with αx , then knows αr1 , αr2 K , αr1 r2 and αr2 . 3. C substitutes αr2 with αy , then knows αr1 , αr2 K , αr1 r2 ?1 and αr1 K . 4. C substitutes both αr1 , αr2 with αx and αy , respec?1 tively. Then C knows αr1 , αr2 K , αr2 and αr1 K . Therefore, the general problem that C has to solve is: given αa and αab getting αb where a, b are unknown random values3 . It easy to see that, when working in subgroup of prime order, this problem is equivalent to DH problem. A nice feature of the A-DH protocol is that it does not require a priori knowledge of the long-term public keys of the parties involved. In fact, certi?cates can be piggy-backed onto existing protocol messages. This is a consequence of the protocol’s “asymmetry”. VI. Authenticated Group Key Agreement In [2], a class of generic n-party DH protocols is de?ned. The security of the entire protocol class is shown secure against passive adversaries based on the intractability of the Di?e-Hellman Decision (DDH) problem. Several concrete protocols were demonstrated that ?t the requirements of DPGs. Moreover, these protocols are shown to be optimal with respect to certain measures of protocol complexity [2], [15]. In this section we extend the GDH protocols to provide implicit key authentication. In doing so, we make use of the A-DH protocol discussed in section V. A. Authenticated GDH.2 protocol Two practical protocols: GDH.2 and GDH.3 are de?ned in [2]. (Another protocol, GDH.1, is used for demonstration purposes only.) The GDH.2 protocol is minimal in terms of the total number of protocol messages. GDH.3, on the other hand, aims to minimize computation costs. Although, the discussion below focuses on extending GDH.2, we note that all of the techniques we consider are easily adapted to GDH.3. We begin with a brief overview of GDH.2 in Figure 3. This basic protocol can be easily amended to provide implicit key authentication in an e?cient manner. This variation (A-GDH.2, shown in Figure 4) di?ers from the basic protocol only in the last round, hence we are only concerned therewith. We assume that Mn shares (or is able to share) with each Mi a distinct secret Kin . For example, we can set Kin = F (αxi · xn (mod p)) with i ∈ [1, n ? 1]. Where xi is a secret long term exponent selected by every Mi (1 ≤ xi ≤ q ? 1) and αxi (mod p) is the corresponding long-term public key of Mi . In this protocol, each group member obtains an (implicitly) authenticated shared key with Mn . Moreover, if we trust Mn to behave correctly, a group member can also be
3 For example, if this problem αK from the values αr2 , αr2 K .

Protocol GDH.2: Let M = {M1 , . . . , Mn } be a set of users wishing to share a key Sn . The GDH.2 protocol executes in n rounds. In the ?rst stage (n ? 1 rounds) contributions are collected from individual group members and then, in the second stage (n-th round) the group keying material is broadcast. The actual protocol is as follows: Initialization: Let p be a prime and q a prime divisor of p ? 1. Let G be the unique cyclic subgroup of Z Z? p of order q , and let α be a generator of G. Round i (0 < i < n): 1. Mi selects ri ∈R Z Z? q. 2. Mi ?→ Mi+1 : {α

r1 ···ri rj

|j ∈ [1, i]}, αr1 ···ri

Round n: 1. Mn selects rn ∈R Z Z? q. 2. Mn ?→ ALL Mi : {α

r1 ···rn ri

|i ∈ [1, n[}

Fig. 3 Group Diffie-Hellman (GDH.2)

Protocol A-GDH.2: Rounds 1 to n ? 1: identical to GDH.2 Round n: 1. Mn selects rn ∈R Z Z? q 2. Mn ?→ ALL Mi : {α

r1 ···rn ri

·Kin

|i ∈ [1, n[}.

Upon receipt of the above, every Mi computes: r ···rn ?1 ·Kin )·Kin · ri ( 1 = αr1 ···rn = Sn . α ri
Fig. 4 Authenticated Group Diffie-Hellman (A-GDH.2)

sure the key shared with Mn is the same key Mn shares with all other members. Theorem VI.1: A-GDH.2 is a contributory authenticated key agreement protocol. Proof (sketch): From the construction of the resultant session key Sn = αr1 ··· rn it is evident that A-GDH.2 is contributory. Let C be an active adversary who can modify, delay, or inject messages. C ’s goal is to share a key with either Mi , for i ∈ [1, n[, or with Mn by masquerading as some Mi . In case of the former, all considerations of the proof in theorem V.1 apply. Assume that C wants to masquerade as Mi . Let Sn (Mn) be the key computed by Mn . It can be expressed as: Sn (Mn) = αcn ·
rn

were easy, the attacker C could get

where cn is a quantity possibly known to C , i.e., in round

6

IEEE Journal of Selected Areas in Communications, VOL 18, NO. 4, April 2000

n ? 1 C can replace αr1 ··· rn?1 with αcn in the message from Mn?1 to Mn . C can also replace the other (n ? 1) values in the same message: α
r1 ···rn?1 rj

(j ∈ [1, n[) → αcj

for some known cj -s. This will cause Mn to output in the last round: { αcj · rn · Kjn | j ∈ [1, n[ } Now, since C knows all cj , she also knows (or can easily 1 compute) all c? j . Hence, C can compute: { αrn ·
Kjn

| j ∈ [1, n[ }

and will broadcast this value in the last protocol round. The end-result is that C shares a key with Mn . There are a few issues with this type of attack. First, it relies on the lack of key con?rmation which we discuss later in the paper. Second, it does not ?t the usual de?nition of a known-key attack since C is only able to share a key with Mn , not with the rest of the group. (We note that known-key attacks were only de?ned in the context of 2party protocols. Their de?nition in a group setting remains to be worked out.) Also, as noted in [10], a simple cure for known-key attacks is by setting Sn = h(Sn (Mi)) where h() is an appropriate collision-resistant hash function such as SHA [16]. B. Complete (Strong) Group Key Authentication The above protocol (A-GDH.2) achieves implicit key authentication in a relatively weak form since the key is not directly authenticated between an arbitrary Mi and Mj (i = j ). Instead, all key authentication is performed through Mn . This may su?ce in some environments, e.g., when the exact membership of the group is not divulged to the individual Mi ’s. Another reason may be that Mn is an entity trusted by all other members, e.g., Mn is an authentication server. According to De?nition IV.3, A-GDH.2 will result in all participants agreeing on the same key if we assume Mn behaves correctly. However, no one – including Mn – can be sure of other members’ participation. In fact, one or more of the intended group members may be “skipped” without detection. Also, a dishonest Mn could partition the group into two without detection by group members. On the one hand, we assume a certain degree of trust in all group members (including Mn ), e.g., not to reveal the group key to outsiders. On the other hand, one might want to limit this trust when it comes to group membership, i.e., Mn might not be universally trusted to faithfully include all (and only) group members. In more concrete terms, our failure model is based on: A malicious insider (group member) seeking to alter the group membership by excluding some members – possibly including itself – from participation in key agreement. For example, this may translate into attempting to physically circumvent certain group members or corrupting intermediate values that subsequently contribute to the excluded members’ keys. On the other hand, our failure model speci?cally excludes: A malicious insider revealing the group key or any other group (or its own) secrets to outsiders. An insider (malicious or otherwise) exhibiting any other form of anomalous behavior. In order to clarify the above, we introduce the following feature: De?nition VI.3: Let R be an n-party key agreement protocol and M be a set of protocol parties (DPG). We say that R is a complete group key authentication protocol if, for every i, j (0 < i = j ≤ n) Mi and Mj compute the same key Si,j only if Si,j has been contributed to by

However, extracting information of Sn (Mn) is intractable if the DDH problem in prime-order subgroup is hard. Theorem VI.2: The A-GDH.2 protocol provides perfect forward secrecy. Proof: Suppose that all long-term keys {Kin | i ∈ [1, n[ } are compromised. Then, our adversary is able to compute a subset of V = {αΠ(S ) | S ? {r1 , . . . , rn }}. But, as shown in [2], given V , it is intractable to ?nd information on the group key Sn = αr1 ,...rn , if the DDH problem in primeorder subgroup is hard. A.1 Resistance to known-key attacks. A-GDH.2 is resistant to passive known-key attacks since the session keys do not contain any long-term information. Resistance to active known-key attacks, on the other hand, is somewhat dubious for reasons stated below. Let Sn (Mi) be the session key computed by each Mi . For ?1 0 < i < n ? 1 we can re-write it as αci ri Kin . For Mn , Sn (Mn) = αcn rn where ci is a quantity possibly known to the adversary C . C also knows a subset of {αΠ(S ) | S ? ?1 {r1 , . . . , rn }}. Using these to ?nd αKin or αKin (for 1 ≤ i ≤ n ? 1), is intractable if the DDH problem in prime-order subgroup is hard. Despite the above, some forms of active known-key attacks are possible. Suppose, for example, that C tries to impersonate M1 . It starts by sending αc1 to M1 in the last protocol round (where c1 is selected by C ). As a result, ?1 M1 computes: Sn (M1) = αc1 r1 K1n . Since this key is corrupted (i.e., not shared with any other Mi ), we can assume that M1 will detect the problem and re-run the protocol. Suppose further that C somehow manages to discover this malformed key.4 In the next protocol run, C can substitute the message from Mn?1 to Mn with: αc1 r1 K1n , . . . , αc1 r1 In other words, C substitutes only the ?rst and the last sub-keys in the ?ow; the rest of the values are unchanged. This causes Mn to compute Sn (Mn) = (αc1 r1 )rn . Mn will also compute (as a sub-key for M1 ): (αc1 r1 K1n )rn K1n = αc1 r1 rn
4 This assumption is what makes active known-key attacks very unlikely in practice.
?1 ?1

ATENIESE, STEINER AND TSUDIK: New Multi-party Authentication Services and Key Agreement Protocols

7

every Mp ∈ M. (Assuming that Mi and Mj have the same view of the group membership.) An alternative de?nition for complete group key authentication is as authenticated group key agreement for all (Mi , Mj ) pairs (0 < i = j ≤ n). Protocol SA-GDH.2: Round i (0 < i < n): 1. Mi receives a set of n intermediate values: {Vk |1 ≤ k ≤ n}. (M1 which can be thought of as receiving an empty set in the ?rst round): Vk =
k1 rk α α(r1 ··· ri?1 )·(Kk1 ···

(

r1 ··· ri?1

)· (K

··· Kk(i?1) ) Kk(i?1) )

if k ≤ (i ? 1) if k > (i ? 1)

Remark VI.4: In the initial round M1 sets V1 = α1 . Round n: 1. Mn broadcasts a set of all Vk values to the group. 2. On receipt, each Mi selects the appropriate Vi where: Vi = α
(
r1 ··· rn ri

2. Mi updates each Vk as follows: ? r1 ··· ri ? (Vk )Kik ·ri = α( rk )·(Kk1 ··· Kki ) Kik ·ri Vk = = α(r1 ··· ri )·(Kk1 ··· Kki ) ? (Vk ) Vk

if k < i if k > i if k = i

Mi during stage 1 as opposed to i in A-GDH.2. Second, if pairwise keys (Kij ) are not pre-computed, as many as (n?1) additional exponentiations must be performed. Note that in the last round, only one exponentiation is done ?1 ?1 since Mi can pre-compute the value: (Ki 1 · · · Kin ) · ri immediately following the i-th round. Advantages: unlike A-GDH.2, SA-GDH.2 allows each member to be explicitly aware of the exact group membership. This may be desired in some environments. Also, the protocol is computationally symmetric, i.e., each member performs the same sequence of computational steps and the same number of exponentiations. Theorem VI.6: SA-GDH.2 o?ers complete group key authentication. Proof (sketch): Suppose Mi and Mj compute the same key while following the protocol correctly. Let Kn = Sn (Mi) = Sn (Mj) and, suppose also, that some Mp ∈ M, (p = i, j ) has not contributed to this key. Let Vi , Vj denote the values received by Mi and Mj , respectively, in the last round of the protocol. Recall that: Sn (Mi) = (Vi )(K1i and, similarly: Sn (Mj) = (Vj )(K1j
?1 ?1 ··· Knj )· r j ?1 ?1 ··· Kni )· r i

=

)·(K1i ··· Kni )

Since all other group members have contributed to the key, we can re-write Vi as (Vj is similar):
(

Mi proceeds to compute: (Vi )
?1 (K 1 ··· i ?1 Kni )· r i

= αr1 ···

rn

Vi = α Then,

r1 ···rn rp ri

)· (

?1 ?1 K ··· K 1i ni ?1 K pi

)

Remark VI.5: For the above, instead of computing ?1 n ? 1 individual key inverses of the form Kji , each Mi computes only a single compound inverse Pi?1 = ?1 ?1 (K1 i · · · Kni ) where Pi = (K1i · · · Kni )
Fig. 5 Group Diffie-Hellman with Complete Key Authentication (SA-GDH.2)

Sn (Mi) = α which must equal:

(

r1 ···rn rp

?1 )· Kpi

Sn (Mj) = α

(

r1 ···rn rp

?1 )· Kpj

?1 ?1 However, this is impossible since Kpi and Kpj are distinct and secret values.

A-GDH.2 can be augmented to provide complete group key authentication as shown in Figure 5. (To better illustrate SA-GDH.2 and its di?erences with respect to AGDH.2, a 4-party example is shown in Figure 6.) The biggest change in the present protocol, SA-GDH.2, is the requirement for a priori availability of all members’ long-term credentials. In e?ect, each Mi is required to have two shared keys (one in each direction) with every other Mj . For every distinct ordered pair < i, j > (0 < ?1 i = j ≤ n) let < Kij , Kij > denote the unidirectional key shared by Mi and Mj and its inverse, respectively. Although it may appear otherwise, individual key inverses ?1 of the form Kij do not need to be computed (see below). Drawbacks: SA-GDH.2 is clearly more expensive than AGDH.2. First, it requires n ? 1 exponentiations from every

Remark VI.7: An interesting feature of SA-GDH.2 is its resistance to known-key attacks. Although we do not treat this topic in detail, it can be easily observed that an attack of the sort described in Section VI-A cannot succeed against SA-GDH.2. C. E?ciency Summary We now consider the costs incurred by the protocols described above. The two Tables I and II summarize, respectively, the communication and computation overhead of the following: ? GDH.2 – plain group key agreement [2]. ? A-GDH.2 - authenticated group key agreement as speci?ed in Section VI-A. Long-term keys Kin are assumed to be pre-computed. ? A-GDH.2* - same as A-GDH.2 but long-term keys Kin are computed as part of the protocol; this also implies that

8

IEEE Journal of Selected Areas in Communications, VOL 18, NO. 4, April 2000

public exponents of all group members must be accumulated in the course of the protocol. ? SA-GDH.2 – complete group key authentication The ?rst table illustrates the communication, and the second computation, costs. The latter is broken down into exponentiation, inverse computation and multiplication. Exponentiation is clearly the costliest operation as it requires O(log 3 p) bit operations in Z Z? p . Given a and p, ?nding the 2 inverse of a ∈ Z Z? p requires only O(log p) bit operations (using the extended Euclidean algorithm). Similarly, the multiplication of a and b modulo p requires O(log 2 p) bit operations. (See [17], [8] for a complete treatment of modular operations.) The only somewhat surprising element of this analysis is the relatively low additional cost of SA-GDH.2 as compared to that of GDH.2 and A-GDH.2. Considering that it o?ers complete group key authentication and several other useful services (when coupled with key con?rmation; see below) the added overhead is well justi?ed. VII. New Services in Group Setting As mentioned in the introduction, key con?rmation (Def. IV.4 and [8]) is an important feature in key agreement protocols. Its purpose is to convince one or more parties that its peer (or a group of peers) is in possession of the key. It can be argued that key con?rmation is not absolutely necessary if communication immediately follows key agreement, i.e., if a proper key is subsequently used for bi-directional data ?ows, key con?rmation is achieved as a side-e?ect. However, in general, it is desirable to bundle key con?rmation with key agreement for the following reasons: 1. it makes key agreement both a more robust and more autonomous operation 2. doing otherwise can lead to an incorrectly computed key not being detected later (since there may be a delay between key agreement and actual data communication) On the other hand, it is not clear what key con?rmation means in a peer group setting. Complete key con?rmation (in the spirit of complete key authentication) would make it necessary for all group members to compute the key and then con?rm to all other members the knowledge of the key. This would entail, at the very least, one round of n simultaneous broadcasts. We take a more practical approach by concentrating on key con?rmation emanating from the group controller, the ?rst group member to compute the actual key. It turns out that the construction of A-GDH.2 (and SAGDH.2) makes key con?rmation fairly easy to add. The only change to both protocols is the addition to the last protocol message (the broadcast from Mn ) of: αF (Sn (Mn)) where Sn (Mn) denotes the key as computed by Mn and F () is as previously de?ned. Upon receipt of the broadcast, each Mi computes its key Sn (Mi) as before. Then, Mi veri?es the computed key: αF (Sn (Mi)) = αF (Sn (Mn))
?

In both A-GDH.2 and SA-GDH.2, key con?rmation coupled with implicit key authentication, has a nice side-e?ect of providing entity authentication of Mn to all other group members. Informally, this is because the up?ow message in round i can be viewed as a random challenge (ri being Mi ’s nonce) submitted to Mn (indirectly, through all other Mj ; j > i). The last broadcast, then, can be viewed as Mn ’s reply to Mi ’s challenge encrypted under a secret key shared among Mi and Mn . To support our claim that the above results in entity authentication of Mn we need to show that Mn ’s reply is fresh. (That Mn ’s reply is authentic has been shown in Section VI-A.) Freshness, however, is evident from the way Mi computes the key: by exponen?1 tiating the value received from Mn with (ri · Kin ). Remark VII.1: In SA-GDH.2, for each Mi , key con?rmation also results in entity authentication of all Mj , for i < j ≤ n. Including key con?rmation in SA-GDH.2 leads us to an interesting observation: At the end of the protocol, each Mi knows that the key it holds, Sn (Mi), has been contributed to by every group member. This follows directly from the complete group key authentication property coupled with key con?rmation. Recall that the former assures that, if any two distinct parties (Mi and Mj ) share a key, that key must be contributed to by every group member. Adding key con?rmation allows us to achieve a stronger goal: any group member can unilaterally establish that it is in possession of a correct key which has been contributed to by every member. This is both a novel and important feature of SA-GDH.2 and a new security service unique to group key agreement. De?nition VII.2: (informal) A group key agreement protocol o?ers group integrity if each protocol party is assured of every other protocol party’s participation in the protocol. Group integrity should not be confused with entity authentication. It is a weaker notion since group integrity does not guarantee freshness/timeliness. It only guarantees all parties’ participation in the protocol and, likewise, all parties’ awareness of the group membership. De?nition VII.3: (informal) A group key agreement protocol is veri?able contributory if each protocol party is assured of every other protocol party’s contribution to the group key. Note that veri?able contributory implies group integrity while the reverse is not true. For example, group integrity can be obtained by requiring every Mi to sign and forward (to all others) a statement certifying to its participation in the protocol. Also, veri?able contributory property does not imply that a group key is not contributed to by an outside party. As discussed in the section VII-A, an adversary can still inject some input into the group key. A. The Elusive Key Integrity Key integrity (Def. IV.5) is orthogonal to both key authentication and key con?rmation. A key agreement protocol may o?er one or both of the latter while at the same

ATENIESE, STEINER AND TSUDIK: New Multi-party Authentication Services and Key Agreement Protocols

9

1

α

r1

2

α

r1

α

r2

α

r1r2

3

α

r1r2

α

r1r3

α

r2r3

α

r1r2r3

α

r2r3r4 K14

α

r1r3r4 K24

α

r1r2r4 K34

4

1

α

r1K12

α

r1K13

α

r1K14

2

α

r1K12

α

r2 K21

α

r1r2 K13K23

α

r1r2 K14K24

3

α

r1r2 K13K23

α

r2r3 K21K31

GROUP CONTROLLERS

α

r1r3 K12K32

α α
r2r3r4 K21K31K41

r1r2r3 K14K24K34

α

r1r3r4 K12K32K42

α

r1r2r4 K13K23K43

4

Fig. 6 An example/comparison of A-GDH and SA-GDH.2

TABLE I Communication costs of protocols

rounds broadcasts total msgs total bandwidth msgs sent per Mi msgs received per Mi

GDH.2 n 1 n (n2 + n)/2 ? 1 1 2

A-GDH.2 n 1 n (n2 + n)/2 ? 1 1 2

A.GDH.2* n 1 n n2 1 2

SA-GDH.2 n 1 n n2 1 2

TABLE II Computation costs of protocols

exponentiations for Mi exponentiations for Mn total exponentiations inverses for Mi inverses for Mn total inverses multiplications for Mi multiplications for Mn total multiplications

GDH.2 i+1 n (n2 + 3n)/2 ? 1

A-GDH.2 i+1 n (n2 + 3n)/2 ? 1

A.GDH.2* i+2 2n ? 1 (n2 + 4n)/2 ? 2 1 n?1 1 n?1 2n ? 2

1 n?1 2n ? 2

SA-GDH.2 n n n2 1 1 n 2n ? 2 2n ? 2 2 n2 ? 2 n

10

IEEE Journal of Selected Areas in Communications, VOL 18, NO. 4, April 2000

time not guaranteeing key integrity. Consider the (3-party) SA-GDH.2 example shown in Figure 7. Round 1: M1 selects r1 ∈R Z Z? q. r1 · K12 , αr1 · M1 → M2 : α Round 2: M2 selects r2 ∈R Z Z? q. r1 · K12 , αr1 · M2 → M3 : α

K13

K13 · r2 · K23

, αr2 ·

K21

Round 3: M3 selects r3 ∈R Z Z? q , computes group key S3 (3) and broadcasts: M3 → M1 , M2 : αr1 · K12 · K32 · r3 , αr2 · K21 · K31 · r3 , αF (S3 (3)) M1 and M2 compute S3 (1) and S3 (2), respectively and con?rm the correctness of their respective keys against αF (S3 (3)) .
Fig. 7 Example run of Protocol SA-GDH.2

This protocol o?ers complete group key authentication, key con?rmation and, entity authentication of M3 . At the end, all parties wind up computing the same key. However, an adversary can exponentiate by a constant all values sent in round 1 (and/or round 2) and remain undetected. Suppose the adversary simply squares all values in round 2. Then, what M3 actually receives is: αr1 · K12 · 2 , αr1 · K13 · r2 · K23 · 2 , αr2 · K21 · 2 As a result, M3 computes S3 (3) = αr1 · r2 · r3 · 2 and both M1 and M2 compute the same value, i.e., the quadratic residue of the intended key. The key con?rmation check does not help since the adversary introduces its input before Mn computes the group key. We observe that, in SA-GDH.2, the adversary is only able to introduce multiplicative (in the exponent) input, i.e., it can cause the key to be K C for some value C . The construction of the protocol precludes the adversary from introducing any other type of input, e.g., additive in the exponent. This leads us to pose the following question: How important is key integrity in a veri?able contributory key agreement protocol? In practice, we expect that key integrity can be easily assured via an external data integrity mechanism (e.g., SSL) used hop-by-hop in the up?ow stage of the protocol. Consequently, if every protocol message between Mi and Mi+1 in the i-th (0 < i < n) protocol round is integrity-protected, the adversary is no longer able to introduce any “noise” into the group key. Note that the last, broadcast message does not need to be protected; any modi?cation will be detected by the key con?rmation check. B. Dynamic Group Changes Thus far, we treated groups as static entities. However, more often than not, group changes during the lifetime of a group. New members join in and old members leave (or get

evicted from) the group. Moreover, due to “environmental” factors such as network failures groups can be partitioned. Similarly, when network partitions heal, multiple groups need to merge into one. Therefore, the problem is how to share a secret key (achieve key agreement) in the face of membership changes. As stated in the introduction we require key independence and therefore need to compute a new (authenticated and contributory) key. Intuitively, we can approach the problem in two ways: ? Starting from scratch: all group members start the key agreement protocol anew and destroy any and all old values. ? Using previous information: in order to save computations, recycle old information to the extent possible (and secure) to share a common secret. It seems clear that the ?rst approach is expensive, unscalable and utterly unsuitable for environments with frequent membership changes. In [4] we showed how the underlying non-authenticated Group Di?e-Hellman key agreement protocols can be extended to achieve very e?cient and ?exible dynamic operation, i.e. adding/deleting a single member, fusion/?ssion of sub-groups and re-keying. Protocol GDH.2-MA: Let Mn+1 be the member to be added and Mn the group controller. Round 1: 1. Mn selects rn ∈R Z Z? q 2. Mn ?→ Mn+1 : {α
rn
r1 ···rn ri

|i ∈ [1, n]}, αrn r1 ···rn

Round 2: 1. Mn+1 selects rn+1 ∈R Z Z? q. 2. Mn+1 ?→ Mi : {α
rn

r1 ···rn+1 ri

|i ∈ [1, n + 1]}

Upon receipt of above, every Mi computes the new key as usual and stores last ?ow for future AKA protocol runs. Additionally, Mn replaces his key contribution rn with rn rn . Remark VII.4: Note that any group member can take that role; the decision who is group controller is simply a matter of policy.
Fig. 8 Member Addition Protocol for GDH.2

As an example you will ?nd in Figure 8 the (unauthenticated) member addition protocol. The trick in that protocol (as well as in all the other AKA protocols) is the caching by the group members of the keying information (i.e., partial keys) distributed in the broadcast phase of the most recent IKA/AKA protocol run. This information is incrementally updated for an AKA protocol run and redistributed to the new incarnation of the group. Figure 9 describes the authenticated version of the member addition protocol. The ?rst ?ow is exactly the same

ATENIESE, STEINER AND TSUDIK: New Multi-party Authentication Services and Key Agreement Protocols

11

Protocol A-GDH.2-MA: Round 1: 1. Mn selects rn ∈R Z Z? q. 2. Mn ?→ Mn+1 : {α
rn
r1 ···rn ri

·Kin

|i ∈ [1, n]}, αrn r1 ···rn

Round 2: 1. Mn+1 selects rn+1 ∈R Z Z? q. 2. Mn+1 ?→ Mi : {α
(r
r1 ···rn

rn

r1 ···rn+1 ri

·Kin Kin+1

|i ∈ [1, n+1]},

Upon receipt of above, every Mi computes the new
in in+1 in in+1 i key as α n ri = αrn r1 ···rn+1 = Sn+1 . and stores last ?ow for future AKA protocol runs. Additionally, Mn replaces his key contribution rn with rn rn .

·K

K

) · K ?1 K ?1 · r

Fig. 9 Member Addition Protocol for A-GDH.2

as in the unauthenticated case except that we use now the broadcast ?ow of the authenticated protocols which also contain long-term keys Kin in the exponent. The Round 2 is essentially the same as the second round of the normal A-GDH.2 protocol and guarantees implicit key authentication. As de?ned in Figure 9 each member would have to remember the sequence of AKA protocols and the corresponding group controllers to be able to factor out the long-term keys Kjk . However, if Mi substitutes his key con?1 tribution ri with ri · Kin after each broadcast ?ow, there is no need to save this history-information and computing the key is exactly the same operation as for IKA protocols. The extension from unauthenticated to authenticated AKA protocols can be performed in the same straightforward manner also for all other AKA protocol described in [4] and will be omitted in the sequel. C. Other Security Services The primary motivation for obtaining a group key (in any manner; whether centralized or contributory) is the ability to communicate securely and e?ciently once a key is established. If all DPG members share a key, they can communicate using symmetric encryption. This is more e?cient than schemes not requiring key establishment. For example, key establishment can be avoided as follows. A DPG member encrypts a message using a symmetric encryption function with a secret key K and then sends the cipher-text to the entire group along with n ? 1 versions of the key K ; each encrypted using a public key of a member. Although this simple scheme has no (cryptographic) startup overhead, it is not contributory and becomes too expensive if the group is large or the volume of message tra?c is high. Furthermore, it requires every member to be aware of the exact group membership at all times; something that can (if desired) be avoided with key agreement.

We believe that there are other incentives to consider. In particular, a shared group key can be used to provide a number of useful services (in an e?cient manner): ? Authentication to outsiders ? Intra-group authentication ? Non-repudiation of group membership ? Private communication within group ? Private communication between outsiders and group For example, we can use a secret group key (such as the one agreed upon in A-GDH.2) to derive a corresponding group Di?e-Hellman public key which can be subsequently embedded in a group certi?cate. This would allow any group member to use DSA [13] (or any El Gamal family) signatures to authenticate itself (as a group member) to both insiders and outsiders. The same group public key can be viewed as long-term group Di?e-Hellman exponent and outsiders (including other groups) can establish shared keys with the entire group in a trivial manner. Similarly, a group secret key can be used to derive an El Gamal public key-pair; the public component thereof can be embedded in a group certi?cate. Outsiders can then use this key with El Gamal public key encryption to communicate in secret with the entire group. VIII. Group Key Agreement and Byzantine Agreement Group key agreement (GKA), in general, has similarities to the well-known Byzantine Agreement (BA) problem ([18]) but there are a number of distinguishing features. The fault model in GKA is not byzantine since we certain degree of trust is assumed among the group members, e.g., not to reveal the group key. The standard BA requirements are: agreement, validity and termination. The validity requirement usually means: if all honest participants have the same input then they will agree on that value, otherwise they will agree on an an arbitrary value. Although termination and agreement would be required by complete authenticated key agreement too, the validity requirement is quite di?erent, namely that the agreement is private to the participants5 and that it is both fresh and random. Therefore, we claim that BA alone is not enough to build a robust GKA protocol.6 On the other hand, GKA has similarities with secure multiparty computation (SMPC) [19], [20]. In fact, GKA can be viewed as a special case of SMPC. However, we note that general SMPC techniques typically yield highly ine?cient protocols. IX. Current Status This paper presented new de?nitions and protocols geared for the dynamic peer group (DPG) settings. In par5 Note that BA protocols in general do not care about con?dentiality. 6 Despite the above, BA could be used for key con?rmation (Section 7) but that would represent overkill: BA protocols in the best-possible settings (signatures) require at least (t + 1) rounds to tolerate t failures. If we set t = 0 (since we do not worry about byzantine faults) we still need a parallel broadcast of n signatures which is rather costly. Moreover, the bene?ts of BA over the simple key con?rmation method sketched in Section 7 are unclear.

12

IEEE Journal of Selected Areas in Communications, VOL 18, NO. 4, April 2000

ticular, it showed how important security services (key authentication, key con?rmation and entity authentication) can be incorporated into a particular class of group key agreement protocols. We are developing a prototype implementation of the protocols described above. This includes both GDH.2based and GDH.3-based protocols. (GDH.3 is a key agreement model aimed at minimizing computations by group members [2]; protocols presented above are easily grafted onto GDH.3.) One of our central goals is to develop a general-purpose toolkit for key agreement and related security services in DPGs. Initial clients for the toolkit may include voice conferencing over IP, replicated Web servers and collaborative (multi-user) simulations. As ?rst tier of this process, we have developed a group key management API called CLQ API [21]. CLQ API implements the functions necessary to compute a group key in a distributed fashion. As it performs no communication on its own, CLQ API requires a group communication layer in order to provide reliable and sequenced message delivery. This approach allows for a small, concise and generic API (it is composed of only seven function calls). Moreover, the purely communication-related issued (such as network partitions and other abnormalities) are taken care by the communication layer. Finally, we are integrating CLQ API with a reliable group communication layer: SPREAD [22]. Developed at Johns Hopkins University, SPREAD supports process group communication. It essentially provided a multicast communication layer that facilitates the development of fault-tolerant distributed applications in both LANs and WANs. Groups are conveniently identi?ed by a name ( ASCII string) selected by the user, such that messages are addressed to the entire group by specifying the group name. Using the group abstraction, the communication subsystem relieves the user from identifying the targets of messages explicitly, and from ?nding the network routes to them. In addition, it guarantees all-or-none delivery semantics, and handles message losses and transient network failures transparently. In summary, the work is an initial attempt to analyze the requirements and issues in authenticated, contributory key agreement for DPGs. It is quite likely that the protocols presented here can be improved. We anticipate that practical experience with real DPG applications (e.g., our integration e?orts with the SPREAD system) will result in better understanding of group security needs and services. X. Acknowledgements The authors gratefully acknowledge the comments of M. Waidner and M. Reiter.
References [1] Jean E. Smith and Fred W. Weingarten, Eds., Research Challenges for the Next Generation Internet. Computing Research Association, May 1997, Report from the Workshop on Research Directions for the Next Generation Internet. Michael Steiner, Gene Tsudik, and Michael Waidner, “Di?ehellman key distribution extended to groups,” in Third ACM

[3] [4]

[5]

[6]

[7]

[8]

[9]

[10]

[11] [12]

[13] [14] [15]

[16]

[17] [18] [19]

[20]

[21] [22]

[2]

Conference on Computer and Communications Security. Mar. 1996, pp. 31–37, ACM Press. Whit?eld Di?e and Martin Hellman, “New directions in cryptography,” IEEE Transactions on Information Theory, vol. IT22, no. 6, pp. 644–654, Nov. 1976. Michael Steiner, Gene Tsudik, and Michael Waidner, “CLIQUES: A new approach to group key agreement,” in Proceedings of the 18th International Conference on Distributed Computing Systems (ICDCS’98), Amsterdam, May 1998, pp. 380–387, IEEE Computer Society Press. Amos Fiat and Moni Naor, “Broadcast encryption,” in Advances in Cryptology – CRYPTO ’93, Douglas R. Stinson, Ed. 1993, vol. 773 of Lecture Notes in Computer Science, pp. 480–491, Springer-Verlag, Berlin Germany. D. Steer, L. Strawczynski, W. Di?e, and M. Wiener, “A secure audio teleconference system,” in Advances in Cryptology – CRYPTO ’88, S. Goldwasser, Ed., Santa Barbara, CA, USA, Aug. 1990, number 403 in Lecture Notes in Computer Science, pp. 520–528, Springer-Verlag, Berlin Germany. Mike Burmester and Yvo Desmedt, “A secure and e?cient conference key distribution system,” in Advances in Cryptology – EUROCRYPT ’94, I.B. Damgard, Ed. 1994, Lecture Notes in Computer Science, Springer-Verlag, Berlin Germany, ?nal version of proceedings. Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone, Handbook of applied cryptography, CRC Press series on discrete mathematics and its applications. CRC Press, 1997, ISBN 08493-8523-7. Mike Burmester and Yvo Desmedt, “Towards practical ’proven secure’ authenticated key distribution,” in 1st ACM Conference on Computer and Communications Security, Victoria Ashby, Ed., Fairfax, Virginia, Nov. 1993, ACM Press. Mike Burmester, “On the risk of opening distributed keys,” in Advances in Cryptology – CRYPTO ’94. 1994, Lecture Notes in Computer Science, pp. 308–317, Springer-Verlag, Berlin Germany. Ross Anderson and Serge Vaudenay, “Minding your p’s and q’s,” in Advances in Cryptology: Proceeding of Asiacrypt’96. 1996, Springer-Verlag, Berlin Germany. Chae Hoon Lim and Pil Joong Lee, “A key recovery attack on discrete log-based schemes using a prime order subgroup,” in Advances in Cryptology – CRYPTO ’97, Burton S. Kaliski Jr., Ed. Aug. 1997, number 1294 in Lecture Notes in Computer Science, pp. 249–263, Springer-Verlag, Berlin Germany. U. S. National Institute of Standards and Technology NIST, “The digital signature standard (DSS),” Dec. 1998. T. Matsumoto, Y. Takashima, and H. Imai, “On seeking smart public-key-distribution systems,” The Transactions of the IECE of Japan, vol. E69, pp. 99–106, 1986. Claus Becker and Uta Wille, “Communication complexity of group key distribution,” in 5th ACM Conference on Computer and Communications Security, San Francisco, California, Nov. 1998, pp. 1–6, ACM Press. US National Institute of Standards Computer Systems Laboratory and Technology, “Secure hash standard (draft),” Federal Information Processing Standards Publication (FIPS PUB) 1801, May 1994. Neal Koblitz, A Course in Number Theory and Cryptography, Number GTM 114 in Graduate Texts in Mathematics. SpringerVerlag, Berlin Germany, Berlin, 1987. Nancy A. Lynch, Distributed Algorithms, Morgan Kaufmann, 1996. Ran Canetti, Studies in Secure Multiparty Computation and Applications, Ph.D. thesis, Department of Computer Science and Applied Mathematics, The Weizmann Institute of Science, Mar 1996, revised version. David Chaum, Claude Crepeau, and Ivan Damgard, “Multiparty unconditional secure protocols,” in Proceedings of the 20th Symposium on Theory of Computing (STOC), New York, 1988, pp. 11–19, ACM. Giuseppe Ateniese, Damian Hasse, Olivier Chevassut, Yongdae Kim, and Gene Tsudik, “The design of a group key agreement api,” Research report, IBM Research, 1999. Y. Amir and J. Stanton, “The spread wide area group communication system,” Technical Report CNDS 98-4, The Center for Networking and Distributed Systems, John Hopkins University, 1998.

ATENIESE, STEINER AND TSUDIK: New Multi-party Authentication Services and Key Agreement Protocols

13

Contents I II III IV V VI Introduction Key Establishment Protocols Previous Work Goals, De?nitions and Notation Authenticated 2-party Key Agreement Authenticated Group Key Agreement VI-A Authenticated GDH.2 protocol . . . . . . . . . . VI-B Complete (Strong) Group Key Authentication . . VI-C E?ciency Summary . . . . . . . . . . . . . . . . . 1 2 2 2 3 5 5 6 7 8 8 10 11 11 11 12

Gene Tsudik is a project leader at USC/ISI and a research associate professor in the Computer Science Department at USC. His research interests include network security, applied cryptography and routing in wireless networks. Dr. Tsudik received his Ph.D. in Computer Science from USC in 1991 and spent the next ?ve years at IBM Research working on secure systems, protocols, mobile networks and electronic commerce. His current research at ISI is sponsored by DARPA, NSF and NSA. At USC, he teaches courses in Cryptography, Computer Security and Wireless Networks.

VII New Services in Group Setting VII-A The Elusive Key Integrity . . . . . . . . . . . . . VII-B Dynamic Group Changes . . . . . . . . . . . . . . VII-C Other Security Services . . . . . . . . . . . . . . . VIII Group Key Agreement and Byzantine Agreement IX X Current Status Acknowledgements List of Figures 1 2 3 4 5 6 7 8 9

Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Authenticated Di?e-Hellman (A-DH) . . . . . . . . . . . 4 Group Di?e-Hellman (GDH.2) . . . . . . . . . . . . . . 5 Authenticated Group Di?e-Hellman (A-GDH.2) . . . . 5 Group Di?e-Hellman with Complete Key Authentication (SA-GDH.2) An example/comparison of A-GDH and SA-GDH.2 . . . 9 Example run of Protocol SA-GDH.2 . . . . . . . . . . . 10 Member Addition Protocol for GDH.2 . . . . . . . . . . 10 Member Addition Protocol for A-GDH.2 . . . . . . . . . 11 List of Tables

7

I II

Communication costs of protocols . . . . . . . . . . . . . Computation costs of protocols . . . . . . . . . . . . . .

9 9

Giuseppe Ateniese received his Ph.D in Computer Science from the University of Genoa (Italy) in February 2000. From November 1997 to December 1998 he was at the Information Sciences Institute (University of Southern California) working on applied cryptography. From January 1999 to September 1999, he was at the IBM Zurich Research Laboratory working on network security. He joined the Department of Computer Science of the Johns Hopkins University in October 1999 as an Assistant Professor.

Michael Steiner is a research scientist at the Department of Computer Science, Universit¨ at des Saarlandes, Saarbr¨ ucken and in the network security research group at the IBM Zurich Research Laboratory. His interests include secure and reliable systems as well as cryptography. He received a Diplom in computer science from the Swiss Federal Institute of Technology (ETH) in 1992 and expects to receive a Ph.D. in computer science from the Universit¨ at des Saarlandes, Saarbr¨ ucken.


赞助商链接

更多相关文章:
更多相关标签:

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图