# Security weaknesses in Harn-Lin and Dutta-Barua protocols for group key establishment.

1. IntroductionKey establishment protocols allow two or more communicating parties to establish their common secret key called a session key. Establishment of session keys is one of the fundamental cryptographic operations and provides a typical way of building secure communication channels over insecure public networks. Traditionally, protocols which can be run by an arbitrary number of parties are called group (or conference) key establishment protocols [1][2][3][4][5], in contrast to protocols which can be run only by two or three parties. In the group setting, a session key is also called a group key. Key establishment protocols are often classified into two types: key agreement protocols and key transfer protocols. Key agreement protocols require each participant to contribute their parts to the final form of the session key, whereas key transfer protocols allow one trusted entity to generate the session key and then transfer it to all participants.

The first priority in designing a key establishment protocol is placed on ensuring the security of the protocol. Even if it is computationally infeasible to break the cryptographic algorithms used, the whole system becomes vulnerable to all manner of attacks if the keys are not securely established. But the experience shows that the design of secure key establishment protocols is notoriously difficult. Over the last decades, a number of protocols have been found to be insecure years after they were published [6][7][8][9][10]. Thus, key establishment protocols must be subjected to a thorough scrutiny before they can be deployed into a public network which might be controlled by an adversary.

The fundamental security attribute that a key establishment protocol is expected to achieve is implicit key authentication. Informally, this attribute means that no one other than the intended parties can compute the session key. A key establishment protocol achieving implicit key authentication is said to be authenticated, and is a primitive of crucial importance in much of modern cryptography and network security. Authenticated key establishment inevitably requires some secret information to be established between the communicating parties before the protocol is ever executed. The pre-established secrets are commonly known as long-term keys. Implicit key authentication can be achieved only when the secrecy of every long-term key is guaranteed. As soon as the long-term key of a party is disclosed, all the protocol sessions that the party participates become completely insecure. It is thus crucial that long-term keys must not be revealed under any circumstances.

Resistance to unknown key-share (UKS) attacks is among many desirable security attributes that key establishment protocols should achieve. An adversary [U.sub.A] is said to succeed in an UKS attack if the attack results in two parties [U.sub.i] and [U.sub.j] such that: (1) [U.sub.i] and [U.sub.j] have computed the same session key; (2) [U.sub.i] is unaware of the "key share" with [U.sub.j] and falsely believes its key is shared with [U.sub.A]; and (3) [U.sub.j] correctly believes its key is shared with [U.sub.i]. As implied by this definition, the adversary [U.sub.A] need not obtain any session key to benefit from an UKS attack. The adversary [U.sub.A] may be able to take advantage of [U.sub.i]'s false belief in various ways if subsequent messages are encrypted or authenticated with the established key [11]. UKS attacks were first discussed by Diffie et al. [12] and have been found against many key establishment protocols [7][8][13][14][11][15].

In this work, we are concerned with the security of two recent key establishment protocols, namely the group key transfer protocol due to Harn and Lin [16] and the group key agreement protocol due to Dutta and Barua [17]. The Harn-Lin protocol employs Shamir's secret sharing [18] and assumes a trusted key generation center (KGC) who provides key distribution service to its registered users. During registration, KGC issues each user a long-term key which should be kept privately by the user. One of the security claims made for this protocol is that the long-term key of each user cannot be learned by other users. But, it turns out that this claim is not true. The truth is that the Harn-Lin protocol is vulnerable to a replay attack whereby a malicious user, who is registered with KGC, can readily obtain the long-term key of any other registered user. We reveal this security vulnerability of the Harn-Lin protocol and then suggest a countermeasure against the replay attack. The attack we mount on the Dutta-Barua protocol is an UKS attack. The Dutta-Barua protocol is based on the well-known protocol of Burmester and Desmedt [1] and requires 2 communication rounds to establish a session key among a group of users. This protocol carries a claimed proof of its security in an adversarial model which captures UKS attacks. But, the proof simply assumes non-concurrent executions of the protocol and so does not capture our UKS attack. Hence, we not only fix the protocol but also extend its proof to the concurrent case. The replay attack on the Harn-Lin protocol is given in Section 2 while the UKS attack on the Dutta-Barua protocol is given in Section 3.

2. Harn and Lin's Group Key Transfer Protocol

This section investigates the security of Harn and Lin's group key transfer protocol HL [16]. We first review the HL protocol and cryptanalyze it by mounting a replay attack. We then show how to fix the protocol by presenting a simple countermeasure against the attack.

2.1 Protocol Description

The protocol HL consists of three phases: system initialization, user registration, and key distribution.

System initialization. KGC randomly chooses two safe primes p and q (i.e., p and q are primes such that p' = (p - 1)/2 and q' = (q - 1)/2 are also primes) and computes n = pq. n is made publicly known.

User registration. Each user is required to register at KGC to subscribe the key distribution service. During registration, KGC shares a secret ([x.sub.i], [y.sub.i]) with each user [U.sub.i] where [x.sub.i], [y.sub.i]

Key distribution. This phase constitutes the core of the protocol and is performed whenever a group of users [U.sub.1], ..., [U.sub.t] decide to establish a common session key.

Step 1. A designated user of the group, called the initiator, sends a key-distribution request to KGC. The request carries the list of participating users <[U.sub.1], ..., [U.sub.t]>.

Step 2. KGC broadcasts the participant list <[U.sub.1], ..., [U.sub.t]> in response to the request.

Step 3. Each user [U.sub.i], for i = 1, ..., t, sends a random challenge [r.sub.i] [epsilon] [Z.sup.*.sub.n] to KGC.

Step 4. KGC randomly selects a session key k and constructs by interpolation a t-th degree polynomial f(x) passing through the (t + 1) points: ([x.sub.1], [y.sub.1] [direct sum] [r.sub.1]), ..., ([x.sub.t], [y.sub.t] [direct sum] [r.sub.t]) and (0, k). Next, KGC selects t additional points [P.sub.1], ..., [P.sub.t] that lie on the polynomial f (x). KGC then computes [beta] = h(k, [U.sub.1], ..., [U.sub.t], [r.sub.1], ..., [r.sub.t], [P.sub.1], ..., [P.sub.t]), where h is a one-way hash function, and broadcasts <[beta], [r.sub.1], ..., [r.sub.t], [P.sub.1], ..., [P.sub.t]> to the users. All computations with respect to f (x) are performed modulo n.

[FIGURE 1 OMITTED]

Step 5. Each [U.sub.i] constructs the polynomial f (x) from the (t + 1) points: [P.sub.1], ..., [P.sub.t] and ([x.sub.i], [y.sub.i] [direct sum] [r.sub.i]). Then [U.sub.i] recovers the session key k = f (0) and checks the correctness of [beta] in the straightforward way. [U.sub.i] aborts if the check fails.

Since the above protocol HL focuses on protecting the keying material broadcasted from KGC to users, Harn and Lin also present (in Remark 2 of [16]) how HL can be extended to provide user authentication and key confirmation. Let [HL.sup.+] be the extended version of HL. [HL.sup.+] is constructed from HL by revising Steps 3 and 4 to achieve user authentication and by adding Steps 6 and 7 to achieve key confirmation.

Step 3 (of [HL.sup.+]). Each user [U.sub.i], for i = 1, ..., t, selects a random challenge [r.sub.i] [epsilon] [Z.sup.*.sub.n], computes [[alpha].sub.i] = h([x.sub.i], [y.sub.i], [r.sub.i]), and sends <[[alpha].sub.i], [r.sub.i]> to KGC.

Step 4 (of [HL.sup.+]). KGC checks the correctness of each [[alpha].sub.i] in the straightforward way. KGC aborts if any of the checks fails. Otherwise, KGC continues with Step 4 of HL.

Step 6. Each [U.sub.i] sends [[gamma].sub.i] = h([x.sub.i], [y.sub.i], k) to KGC.

Step 7. After receiving all [[gamma].sub.i]'s, KGC sends [[delta].sub.i] = h([x.sub.i], [y.sub.i], k, [U.sub.i], ..., [U.sub.t]) to [U.sub.i] for i = 1, ..., t.

All other parts (including the phases of system initialization and user registration) remain unchanged between HL and [HL.sup.+]. A high level description of [HL.sup.+] is given in Fig. 1.

2.2 Replay Attack

The fundamental security goal of a key establishment protocol is to ensure that no one other than the intended users can compute the session key. In the cases of HL and [HL.sup.+], this goal can be achieved only when the secrecy of every ([x.sub.i], [y.sub.i]) is guaranteed. As soon as ([x.sub.i], [y.sub.i]) is disclosed, all the protocol sessions that [U.sub.i] participates become completely insecure. Thus, it is important that [x.sub.i]'s and [y.sub.i]'s must not be revealed under any circumstances.

Harn and Lin claim that their protocols prevent the secret ([x.sub.i], [y.sub.i]) of each [U.sub.i] from being disclosed to other users, either insiders or outsiders (Theorem 3 of [16]). However, we found that this claim is wrong. Suppose that a malicious registered user [U.sub.j] has a goal of finding out [U.sub.i]'s secret ([x.sub.i], [y.sub.i]). Then [U.sub.j] can achieve its goal by mounting the following attack against the protocol [HL.sup.+].

Step 0. As a preliminary step, the adversary [U.sub.j] eavesdrops on a protocol session, where [U.sub.i] participates, and stores the message <[[alpha].sub.i], [r.sub.i]> sent by [U.sub.i] in Step 3 of the session.

[U.sub.j] then initiates two (either concurrent or sequential) sessions S and S' of the protocol alleging that the participants of both sessions are [U.sub.i] and [U.sub.j]. Once KGC responds with the participant list ([U.sub.i], [U.sub.j]) in Step 2 of each session, [U.sub.j] performs Step 3 of the sessions while playing dual roles of [U.sub.j] itself and the victim [U.sub.i].

Step 3 of S. [U.sub.j] sends the eavesdropped message <[[alpha].sub.i], [r.sub.i]> to KGC as if the message is from [U.sub.i]. But, [U.sub.j] behaves honestly in sending its own message; [U.sub.j] selects a random [r.sub.j] [epsilon] [Z.sup.*.sub.n], computes [[alpha].sub.j] = h([x.sub.j], [y.sub.j], [r.sub.j]), and sends <[[alpha].sub.j], [r.sub.j]> to KGC.

Step 3 of S'. [U.sub.j] replays the messages <[[alpha].sub.i], [r.sub.i]> and <[[alpha].sub.j], [r.sub.j]>. That is, [U.sub.j] sends <[[alpha].sub.j], [r.sub.j]> as [U.sub.i]'s message and sends <[[alpha].sub.j], [r.sub.j]> as its own message.

KGC cannot detect any discrepancy since [[alpha].sub.i] and [[alpha].sub.j] are both valid. Note that KGC does not check for message replays. Hence, KGC will distribute the keying materials for the sessions. Let f (x) = [a.sub.2] [x.sup.2] + [a.sub.i] x + k and f'(x) = [a'.sub.2] [x.sup.2] + [a'.sub.1] x + k' be the polynomials constructed by KGC respectively in sessions S and S'. As soon as receiving the keying materials, [U.sub.j] derives these polynomials as specified in Step 5 of the protocol. Now let

g(x) = f (x) - f'(x)

= ([a.sub.2] - [a'.sub.2])[x.sup.2] + ([a.sub.1] - [a'.sub.1])x + k - k'.

Then, g([x.sub.i]) = 0 and g([x.sub.j]) = 0 since f([x.sub.i]) = f'([x.sub.i]) = [y.sub.i] [direct sum] [r.sub.i] and f([x.sub.j]) = f' ([x.sub.j]) = [y.sub.j] [direct sum] [r.sub.j]. This implies that [x.sub.i] and [x.sub.j] are the two roots of the quadratic equation ([a.sub.2] - [a'.sub.2])[x.sup.2] + ([a.sub.1] - [a'.sub.1])x + k - k' = 0. It follows that

([a.sub.2] - [a'.sub.2])[x.sup.2] + ([a.sub.1] - [a'.sub.1])x + k - k' = ([a.sub.2] - [a'.sub.2])(x - [x.sub.i])(x - [x.sub.j]).

Since k - k' = ([a.sub.2] - [a'.sub.2]) [x.sub.i][x.sub.j], we get

[x.sub.i] = [x.sup.-1.sub.j] [([a.sub.2] - [a'.sub.2]).sup.-1] k - k'). (1)

Here, the computations are done modulo n. Once [x.sub.i] is obtained as in Eq. (i), [y.sub.i] can be easily computed from f ([x.sub.i]) = [y.sub.i] [direct sum] [r.sub.i]. The value of [y.sub.i] is different depending on whether [y.sub.i] [direct sum] [r.sub.i] < n or [y.sub.i] [direct sum] [r.sub.i] [greater than or equal to] n.

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

[[alpha].sub.i] can serve as a verifier for checking which of the two cases is true. Using ([x.sub.i], [y.sub.i]) obtained as above, [U.sub.j] is able to complete the protocol without the attack being noticed.

The above attack assumes, for ease of exposition, that KGC allows for the key establishment between two parties. But, this assumption is not necessary. If two-party key establishments are not allowed, [U.sub.j] can collude with another malicious user [U.sub.k] to mount a slight variant of the attack. Assume two sessions of the protocol, in both of which the participants are [U.sub.i], [U.sub.j] and [U.sub.k]. If [U.sub.j] and [U.sub.k] collude together and run the two sessions as in the attack above, they can construct a cubic polynomial g(x) = ([a.sub.3] - [a'.sub.3])[x.sup.3] + ([a.sub.2] - [a'.sub.2])[x.sup.2] + ([a.sub.1] - [a'.sub.1])x + k - k' such that g([x.sub.i]) = g([x.sub.j]) = g([x.sub.k]) = 0. Then, with [x.sub.j] and [x.sub.k] in hand, the adversaries can compute [x.sub.i] as

[x.sub.i] = (-i)[x.sup.-1.sub.j][x.sup.-1.sub.k][([a.sub.3] - [a'.sub.3]).sup.-1](k - k')

and thereby can determine [y.sub.i] as above.

So far, we have seen the vulnerability of the protocol [HL.sup.+]. As can be expected, the basic protocol HL also suffers from the same vulnerability. The attack against HL is essentially similar to the above attack, and its description is omitted due to the similarity.

Disclosure of a long-term key can easily lead to a devastating result. Suppose, for example, that the malicious user [U.sub.j] gets unregistered with KGC after obtaining the long-term secret ([x.sub.i], [y.sub.i]) of [U.sub.i]. Then [U.sub.j], without reregistering, can completely compromise all the sessions that [U.sub.i] will participate in the future.

2.3 Countermeasure

The security failure of [HL.sup.+] (and HL) is attributed to one obvious flaw in the protocol design: the messages sent by users in Step 3 can be replayed in different protocol sessions. This flaw allows our adversary [U.sub.j] to send the same random challenges twice and thereby to construct a quadratic polynomial g(x) such that g([x.sub.i]) = g([x.sub.j]) = 0. Fortunately, message replays can be effectively prevented if Steps 2 and 3 of the protocols are revised as follows:

Step 2 (revision). KGC selects a random [r.sub.0] [epsilon] [Z.sup.*.sub.n] and broadcasts it along with the participant list <[U.sub.1], ..., [U.sub.t]>.

Step 3 (revision). Each user [U.sub.i], for i = 1, ..., t, selects a random [r.sub.i] [epsilon] [Z.sup.*.sub.n], computes [[alpha].sub.i] = h([x.sub.i], [y.sub.i],[r.sub.i],[r.sub.0],[U.sub.1], ..., [U.sub.t]), and sends <[[alpha].sub.i], [r.sub.i]> to KGC.

The other steps of the protocols remain unchanged except that in Step 4 of HL, KGC has to check the correctness of [[alpha].sub.i], for i = i, ..., t, before starting to construct the polynomial f(x). As a result of our modification, the protocols HL and [HL.sup.+] become identical except that [HL.sup.+] requires two additional steps (Steps 6 and 7) for key confirmation. With the modification applied, the message <[[alpha].sub.i], [r.sub.i]> eavesdropped in a protocol session can no longer be replayed in any other sessions. Hence, our attack is not valid against the improved protocols.

3. Dutta and Barua's Group Key Agreement Protocol

As previously mentioned, Dutta and Barua's group key agreement protocol DB [17] is vulnerable to an unknown key-share attack. We here reveal this security problem with the protocol DB and show how to address it. We also interpret our attack in the context of the formal proof model to invalidate the claimed proof of security for DB.

3.1 Protocol Description

Let U be a set of all users who can participate in the protocol DB. Any subset of U may decide at any point to establish a session key. Thus, a user may have several instances involved in distinct, possibly concurrent, protocol sessions. The protocol DB requires each user [U.sub.i] to maintain a counter [c.sub.i] whose value indicates the number of instances created by [U.sub.i]. The counters of users are used in defining session identifiers, as specified in the protocol description below. The network where the users interact is assumed to be fully controlled by an active adversary who may read, intercept and fabricate any messages at will. The protocol is authenticated using signatures. Let [summation] = (KGen, Sign, Vrfy) be a signature scheme which is existentially unforgeable under an adaptive chosen message attack. Here, KGen is the key generation algorithm, Sign is the signature generation algorithm, and Vrfy is the signature verification algorithm. Before the protocol is ever executed, the following initialization should be performed to generate system parameters and long-term keys.

* The users in U choose a cyclic multiplicative group of prime order q and fix an arbitrary generator g of the cyclic group.

* Each user [U.sub.i] [epsilon] U generates its long-term verification/signing keys ([VK.sub.i], [SK.sub.i]) by running KGen.

* Each [U.sub.i] [epsilon] U sets its counter [c.sub.i] to 0. ([c.sub.i] is incremented whenever a new instance of [U.sub.i] is created.)

If there are n participants [U.sub.1], ..., [U.sub.n], DB proceeds as follows. (Throughout the protocol description, all indices are to be taken in a cycle, i.e., [U.sub.n+1] = [U.sub.1], etc.)

Round 1: Each [U.sub.i] chooses a random [x.sub.i] [epsilon] [Z.sup.*.sub.q], computes [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], and sends [Exp.sub.i] = [U.sub.i] |1 | [y.sub.i] | [c.sub.i]] | [[alpha].sub.i] to [U.sub.i-1] and [U.sub.i+1]. Here, the symbol | denotes the string concatenation operation.

Round 2: Upon receiving [Exp.sub.i-1] and [Exp.sub.i+1], [U.sub.i] checks that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. [U.sub.i] aborts if either of two verifications fails. Otherwise, [U.sub.i] computes [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

Then [U.sub.i] broadcasts [Div.sub.i] = [U.sub.i] 2 | [Y.sub.i] | [c.sub.i] | [[beta].sub.i].

Key computation: Each [U.sub.i] checks that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]. [U.sub.i] aborts if any of the verifications fails. Otherwise, [U.sub.i] computes

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

[U.sub.i] checks that [K.sup.R.sub.i+n-1] is equal to [K.sup.L.sub.i]. If not, [U.sub.i] aborts. Otherwise, [U.sub.i] computes the session key sk as

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

and defines the session identifier [SID.sub.i] as [SID.sub.i] = <([U.sub.1], [c.sub.1]), ..., ([U.sub.n],[c.sub.n])>.

[FIGURE 2 OMITTED]

3.2 Unknown Key-Share Attack

We here mount an UKS attack against the protocol DB described above. Consider a protocol session S to be run by the users of group G = {[U.sub.1], [U.sub.2], [U.sub.3]} Now suppose that [U.sub.1] and [U.sub.2] accept the invitation by the malicious adversary [U.sub.A] to participate in a new concurrent session S', thus forming the group G' = {[U.sub.1], [U.sub.2], [U.sub.A]}. Let [U.sup.S.sub.1] and [[U.sup.S'.sub.1] denote [U.sub.i]'s instances participating respectively in S and S'. Then the goal of the adversary [U.sub.A] is to trick [U.sup.S'.sub.1] and [U.sup.S'.sub.2] into establishing a session key with [U.sub.3]. The attack works as follows:

1. As session S starts, [U.sup.S.sub.1], [U.sup.S.sub.2] and [U.sub.3] will send their first messages [Exp.sub.1] = [U.sub.1] | 1 |[y.sub.1] | [c.sub.1] | [[alpha].sub.1], [Exp.sub.2] = [U.sub.2] | 1 | [y.sub.2] | [c.sub.2] | [[alpha].sub.2] and [Exp.sub.3] = [U.sub.3] | 1 | [y.sub.3] | [c.sub.3] | [[alpha].sub.3], respectively. The adversary [U.sub.A] intercepts [Exp.sub.3] while blocking [Exp.sub.1] and [Exp.sub.2] from reaching [U.sub.3]. In other words, [U.sup.S.sup.1] and [U.sup.S.sup.1] never receive [Exp.sub.3] and [U.sub.3] receives neither [Exp.sub.1] nor [Exp.sub.2].

2. As a participant of session S', the adversary [U.sub.A] sends the message [Exp.sub.A] = [U.sub.A] | 1 | [y.sub.3] | [c.sub.A] | [[alpha].sub.A] to [U.sup.S'.sub.1] and [U.sup.S'.sub.2] and receives the messages [Exp'.sub.1] = [U.sub.1] | 1 | [y'.sub.1] | [c'.sub.1] | [[alpha]'.sub.1] and [Exp'.sub.2] = [U.sub.2] | 1 | [y'.sub.2] | [c'.sup.2] | [[alpha]'.sub.2] respectively from [U.sup.S'.sup.1] and [U.sup.S'.sup.2]. Notice that [Exp.sub.A] contains [y.sub.3] (which is generated by [U.sub.3] and is obtainable from [Exp.sub.3]). We mean by this that [U.sub.A] has computed its signature [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

3. [U.sub.A] forwards the received messages [Exp'.sub.1] and [Exp'.sub.2] to [U.sub.3] as if they are sent by [U.sup.S.sub.1] and [U.sup.S.sub.2], respectively. These messages will pass [U.sub.3]'s verification since [[alpha].sub.1'] (resp. [[alpha].sub.2']) is a valid signature on [U.sub.1] | 1 | [y'.sub.1] | [c'.sup.1] (resp. [U.sub.2] | 1 | [y'.sub.2] | [c'.sub.2]) under the verification key [VK.sub.1] (resp. [VK.sub.2]). Hence, [U.sub.3] will send out its second message [Div.sub.3] = [U.sub.3] | 2 | [Y.sub.3] | [c.sub.3] | [[beta].sub.3]. If we let [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII], then clearly

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

4. [U.sub.A] intercepts [Div.sub.3], computes [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (using [Y.sub.3] from [U.sub.3]), and sends [Div.sub.A] = [U.sub.A] | 2 | [Y.sub.3] | [c.sub.A] | [[beta].sub.A] to [U.sup.S'.sub.1] and [U.sup.S'.sub.2]. Meanwhile, [U.sup.S'.sub.1] and [U.sup.S'.sub.2] will send [U.sub.A] their second messages [Div'.sub.1] = [U.sub.1] | 2 | [Y'.sub.1] | [c'.sub.1] | [[beta]'.sub.1] and [Div'.sub.2] = [U.sub.2] | 2 | [Y'.sub.2] | [c'.sub.2] | [[beta]'.sub.2] where

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

5. [U.sub.A] forwards [Div'.sub.1] and [Div'.sub.2] to [U.sub.3] as if they are from [U.sup.S.sub.1] and [U.sup.S.sub.2], respectively. These messages will pass [U.sub.3]'s verifications since the signatures [[beta]'.sub.1] and [[beta]'.sub.2] are both valid and [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

6. Consequently, [U.sup.S'.sub.1], [U.sup.S'.sub.2] and [U.sub.3] will compute the same session key

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

At the end of the attack: (1) [U.sub.1], [U.sub.2] and [U.sub.3] have computed the same session key sk; (2) [U.sub.1] and [U.sub.2] believe that sk is shared with [U.sub.A], while in fact it is shared with [U.sub.3]; (3) [U.sub.3] believes that sk is shared with [U.sub.1] and [U.sub.2]. This shows that the protocol DB is vulnerable to an UKS attack when two protocol sessions are running concurrently with some joint participants.

3.3 Attacking in the Model

The protocol DB carries a claimed proof of security in a formal model of communication and adversarial capabilities. The proof model used for DB is a typical one [3] and allows the adversary A to access all the standard oracles: Send, Execute, Reveal, Corrupt and Test. Any key establishment protocol proven secure in such a model should be resistant to UKS attacks [8]. But as we have shown, the DB protocol is vulnerable to an UKS attack. The existence of our attack means, in the context of the proof model, that there exists an adversary A whose advantage in attacking protocol DB is 1, or in other words, there exists an adversary A who can distinguish, with probability 1, random keys from real session keys. The construction of such an A is rather straightforward from the attack above, and its brief description follows:

Signing-key disclosure: First, A obtains [U.sub.A]'s long-term signing key [SK.sub.A] by querying Corrupt([U.sub.A]).

Initiation: Next, A asks Send queries required to initiate two protocol sessions S : G = {[U.sub.1],[U.sub.2],[U.sub.3]} and S': G' = {[U.sub.1],[U.sub.2],[U.sub.A]}. For example, a query of the form Send([U.sub.1], *, <[U.sub.2],[U.sub.A]>) prompts an unused instance * of [U.sub.1] to initiate the protocol with [U.sub.2] and [U.sub.A]. But, no instance of [U.sub.A] needs to be asked this form of Send query because A will simulate by itself the actions of [U.sub.A].

Run: Now, A runs the two sessions in the exact same way as [U.sub.A] did in the above-described attack. Note that A can perfectly simulate [U.sub.A]'s attack by asking Send queries and by using the disclosed long-term signing key [SK.sub.A]. Let [U.sup.S.sub.i] and [U.sup.S.sub.i] be [U.sub.i]'s instances participating respectively in S and S'. Then, as in the attack above, the instances [U.sup.S'.sub.1], [U.sup.S'.sub.2] and [U.sup.S.sub.3] will eventually accept the same session key sk.

Session-key disclosure: A obtains the session key sk by querying either Reveal([U.sup.S'.sub.1]) or Reveal([U.sup.S'.sub.2]).

Test: The instance [U.sup.S.sub.3] is fresh because (1) no Corrupt query has been asked for any of the users [U.sub.1], [U.sub.2] and [U.sub.3] and (2) no Reveal query has been made for any of the instances [U.sup.S.sub.1], [U.sup.S.sub.2] and [U.sup.S.sub.3]. Thus, A may test (i.e., ask a Test query against) the instance [U.sup.S.sub.3]. Since A knows the value of sk, the probability that A guesses correctly the bit b used by the Test oracle is 1 and so is the advantage of A in attacking DB.

3.4 Countermeasure

The vulnerability of DB to the UKS attack is attributed to the fact that [U.sub.3] cannot distinguish between the signatures generated by [U.sup.S.sub.1] (resp. [U.sup.S.sub.2]) and those generated by [U.sub.i] (resp. [U.sup.S'.sub.2]). Given this observation, it is not hard to figure out how to fix the protocol. As a simple countermeasure against the attack, we recommend to change the computations of the signatures at [[alpha].sub.i] [[beta].sub.i] to

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII].

The identities of all protocol participants are now included as part of the messages to be signed. With this modification applied, the signatures from [U.sup.S'.sub.1] and [U.sup.S'.sub.2] can no longer pass [U.sub.3]'s verification since the participants are different between the two sessions S and S'. Hence, the UKS attack is not valid against the improved protocol.

3.5 Security Proof

Since our UKS attack can be simulated in the proof model used for DB, there must be some problems with the security proof given by Dutta and Barua [17]. The problem with Dutta and Barua's proof is that it simply assumes non-concurrent executions of the protocol. We here prove the security of our improved protocol [DB.sup.+] by extending Dutta and Barua's proof to the concurrent case. As in [17], we use UP to denote the unauthenticated version of the protocol DB (or [DB.sup.+]). The following theorem presents our result on the security of [DB.sup.+]. It claims that [DB.sup.+] is secure against active adversaries under the security of UP against passive adversaries. (All the notations that are not defined here are taken over from [17].)

Theorem 1. For any adversary who asks [q.sub.E] Execute queries and [q.sub.S] Send queries with time complexity t, its advantage in breaking the security of the protocol [DB.sup.+] is upper bounded by

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

where Q = [q.sub.E] + [q.sub.S] and P is a polynomial-sized set of potential participants.

Proof. We prove the theorem by finding a reduction from the security of protocol [DB.sup.+] to the security of protocol UP. As shown in [17], the unauthenticated protocol UP is provably secure against a passive adversary. Assuming an active adversary [A.sup.+] who attacks protocol [DB.sup.+], we construct a passive adversary A that uses [A.sup.+] in its attack on UP. As in a typical reductionist approach, the adversary A simply runs [A.sup.+] as a subroutine and answers the oracle queries of [A.sup.+] on its own. The idea in constructing A is to use the fact that in attacking [DB.sup.+], the adversary [A.sup.+] is able to relay messages only between user instances with the same set of participants and counters. Based on this idea, the adversary A obtains a transcript T of UP for each unique combination of participants and nonces by calling its own Execute oracle, and generates a transcript [T.sup.+] of [DB.sup.+] by patching T with appropriate signatures. A then uses the messages of [T.sup.+] in answering [A.sup.+]'s Send queries directed to user instances which have the same participants and nonces as used in generating [T.sup.+]. In this way, [A.sup.+] is limited to sending messages already contained in [T.sup.+], unless signature forgery occurs. In essence, A is ensuring that [A.sup.+]'s capability of attacking protocol [DB.sup.+] is demonstrated only on the session key associated with the patched transcript [T.sup.+] and thus is translated directly into the capability of attacking protocol UP.

However, there exists a difficulty in constructing the passive adversary A from the active adversary [A.sup.+]. Since [A.sup.+] can obtain a private signing key at any time by calling the Corrupt oracle, it may send arbitrary - but still valid - messages of its choice (i.e., messages that are not contained in the patched transcript [T.sup.+]) to an instance. The problem in this case is that A cannot simulate the actions of the instance because it does not have appropriate internal data used by the instance at earlier stage. The exact same problem arises in proving security for the compiler of Katz and Yung [3]. The proof for the Katz-Yung compiler circumvents this simulation problem by letting A guess the session in which [A.sup.+] will take advantage of its only chance to access the Test oracle. For the guessed session, A handles the queries of the active adversary by calling its own Execute oracle as described above, and for all other sessions, A honestly responds by directly executing protocol [DB.sup.+] (i.e., without accessing the Execute oracle). Our proof follows this approach in extending Dutta and Barua's proof to the concurrent case.

The passive adversary a begins by choosing a random [chi] [epsilon] {1, ..., Q} which represents a guess of the session for which [A.sup.+] will ask its Test query. A simulates the queries of the active dversary [A.sup.+] as follows:

Corrupt Queries. These queries are answered in the obvious way. Namely, a returns the long-term signing key [SK.sub.i] in response to the query Corrupt([U.sub.i]).

Execute Queries. If an Execute query is not the [chi]-th Send/Execute query of [A.sup.+], then a simply generates by itself a transcript of an execution of [DB.sup.+] and returns this to [A.sup.+]. A can do this because it knows all the signing keys of users. If an Execute query is the [chi]-th Send/Execute query of a+, a proceeds exactly as in Dutta and Barua's simulation of Execute queries.

Send Queries. If a Send query is not the x-th Send/Execute query of [A.sup.+], then a simulates on its own the actions of the instance and returns a response as needed. A can do this because it knows all the signing keys of users. If a Send query is the x-th Send/Execute query of [A.sup.+], a proceeds exactly as in Dutta and Barua's simulation of Send queries.

Reveal Queries. If a Reveal query is asked to an instance simulated by a itself, then the appropriate session key can be computed/returned. Otherwise, a aborts and outputs a random bit since its guess x was incorrect.

Test Queries. If the Test query is asked to an instance for which a has asked its single Execute query, then a asks its own Test query and returns the result to [A.sup.+]. Otherwise, a aborts and outputs a random bit since its guess x was incorrect.

As long as Forge does not occur and a correctly guesses x, the above simulation for [A.sup.+] is perfect. Let Guess denote the event that a correctly guesses x. If Forge occurs, A aborts and outputs a random bit. Let Win = Guess [conjunction] [bar.Forge]. Then, clearly, Pr[Succ | [bar.Win]] = 1/2. Now, to derive the statement of Theorem 1, we apply a series of simple modifications to the definitional equation [Adv.sub.A,UP] = [absolute value of 2[Pr.sub.A, UP][Succ] -1] as follows:

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII]

It follows that [MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII] (see [3]), this yields the statement of the theorem.

4. Conclusion

This work has revealed the security weaknesses in two key establishment protocols: Harn and Lin's group key transfer protocol and Dutta and Barua's group key agreement protocol. The Harn-Lin protocol cannot protect the long-term keys of users while the Dutta-Barua protocol is vulnerable to an unknown key share attack. We have also suggested how the weaknesses can be eliminated. One implication of our result is that the claimed proof of security for the Dutta-Barua protocol is not rigorous enough to capture unknown key share attacks. The problem we found with Dutta and Barua's proof is that it fails to consider concurrent executions of the protocol. We have addressed this problem by extending Dutta and Barua's proof to the concurrent case.

DOI: 10.3837/tiis.2012.02.018

This work was supported by Priority Research Centers Program through the National Research Foundation of Korea(NRF) funded by the Ministry of Education, Science and Technology(2011-0018397).

References

[1] M. Burmester and Y. Desmedt, "A secure and efficient conference key distribution system," Advances in Cryptology--EUROCRYPT 1994, vol.950, pp.275-286, 1995. Article (CrossRef Link)

[2] E. Bresson, O. Chevassut, D. Pointcheval and J.-J. Quisquater, "Provably authenticated group Diffie-Hellman key exchange," in Proc. of 8th ACM Conference on Computer and Communications Security, pp.255-264, 2001. Article (CrossRef Link)

[3] J. Katz and M. Yung, "Scalable protocols for authenticated group key exchange," in Proc. of Advances in Cryptology--CRYPTO 2003, vol.2729, pp.110-125, 2003. Article (CrossRef Link)

[4] J. Nam, S. Kim and D. Won, "Secure group communications over combined wired and wireless networks," in Proc. of 2nd International Conference on Trust, Privacy, and Security in Digital Business, vol.3592, pp.90-99, 2005. Article (CrossRef Link)

[5] M. Abdalla, E. Bresson, O. Chevassut and D. Pointcheval, "Password-based group key exchange in a constant number of rounds," in Proc. of 9th International Workshop on Practice and Theory in Public Key Cryptography, vol.3958, pp.427-442, 2006. Article (CrossRef Link)

[6] O. Pereira and J.-J. Quisquater, "A security analysis of the cliques protocols suites," in Proc. of 14th IEEE Computer Security Foundations Workshop, pp.73-81, 2001. Article (CrossRef Link)

[7] H. Krawczyk, "HMQV: a High-Performance secure Diffie-Hellman protocol," Advances in Cryptology--CRYPTO 2005, vol.3621, pp.546-566, 2005. Article (CrossRef Link)

[8] K.-K. Choo, C. Boyd and Y. Hitchcock, "Errors in computational complexity proofs for protocols," Advances in Cryptology--ASIACRYPT 2005, vol.3788, pp.624-643, 2005. Article (CrossRef Link)

[9] J. Nam, S. Kim and D. Won, "Attack on the Sun-Chen-Hwang's three-party key agreement protocols using passwords," IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol.E89-A, no.1, pp.209-212, 2006.

[10] J. Nam, J. Paik, U. Kim and D. Won, "Security enhancement to a password-authenticated group key exchange protocol for mobile ad-hoc networks," IEEE Communications Letters, vol. 12, no.2, pp.127-129, 2008. Article (CrossRef Link)

[11] B. S. Kaliski, "An Unknown Key-Share attack on the MQV key agreement Protocol," ACM Transactions on Information and System Security, vol.4, no.3, pp.275-288, 2001. Article (CrossRef Link)

[12] W. Diffie, P. Oorschot and M. Wiener, "Authentication and authenticated key exchanges," Designs, Codes, and Cryptography, vol.2, no.2, pp.107-125, 1992. Article (CrossRef Link)

[13] S. Blake-Wilson and A. Menezes, "Unknown Key-Share attacks on the Station-to-Station (STS) protocol," in Proc. of 2nd International Workshop on Practice and Theory in Public Key Cryptography, vol.1560, pp.154-170, 1999. Article (CrossRef Link)

[14] J. Baek and K. Kim, "Remarks on the unknown Key-Share attacks," IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol.E83-A, no.12, pp.2766-2769, 2000.

[15] K. Shim, "Cryptanalysis of mutual authentication and key exchange for low power wireless communications," IEEE Communications Letters, vol.7, no.5, pp.248-250, 2003. Article (CrossRef Link)

[16] L. Harn and C. Lin, "Authenticated group key transfer protocol based on secret sharing," IEEE Transactions on Computers, vol.59, no.6, pp.842-846, 2010. Article (CrossRef Link)

[17] R. Dutta and R. Barua, "Provably secure constant round contributory group key agreement in dynamic setting," IEEE Transactions on Information Theory, vol.54, no.5, pp.2007-2025, 2008. Article (CrossRef Link)

[18] A. Shamir, "How to share a secret," Communications of the ACM, vol.22, no.11, pp. 612-613, 1979. Article (CrossRef Link)

Junghyun Nam received the B.E. degree in Information Engineering from Sungkyunkwan University, Korea, in 1997. He received his M.S. degree in Computer Science from University of Louisiana, Lafayette, in 2002, and the Ph.D. degree in Computer Engineering from Sungkyunkwan University, Korea, in 2006. He is now an associate professor in Konkuk University, Korea. His research interests include cryptography and computer security.

Moonseong Kim received the M.S. degree in Mathematics, August 2002 and the Ph.D. degree in Electrical and Computer Engineering, February 2007 both from Sungkyunkwan University, Korea. He was a research professor at Sungkyunkwan University in 2007. From December 2007 to October 2009, he was a visiting scholar in ECE and CSE, Michigan State University, USA. Since October 2009, he has been a patent examiner in Information and Communication Examination Bureau, Korean Intellectual Property Office (KIPO), Korea. His research interests include wired/wireless networking, sensor networking, mobile computing, network security protocols, and simulations/numerical analysis.

Juryon Paik received the B.E. degree in Information Engineering from Sungkyunkwan University, Korea, in 1997. She received her M.E. and Ph.D. degrees in Computer Engineering from Sungkyunkwan University in 2005 and 2008, respectively. Currently, she is a research professor at the Department of Computer Engineering, Sungkyunkwan University. Her research interests include XML mining, semantic mining, and web search engines.

Dongho Won received his B.E., M.E., and Ph.D. degrees from Sungkyunkwan University in 1976, 1978, and 1988, respectively. After working at ETRI (Electronics & Telecommunications Research Institute) from 1978 to 1980, he joined Sungkyunkwan University in 1982, where he is currently Professor of School of Information and Communication Engineering. In the year 2002, he served as the President of KIISC (Korea Institute of Information Security & Cryptology). He was the Program Committee Chairman of the 8th International Conference on Information Security and Cryptology (ICISC 2005). His research interests are on cryptology and information security.

Junghyun Nam (1), Moonseong Kim (2), Juryon Paik (3) and Dongho Won (3)

(1) Department of Computer Engineering, Konkuk University, Korea [e-mail: jhnam@kku.ac.kr]

(2) Information and Communications Examination Bureau, Korean Intellectual Property Office, Korea [e-mail: moonseong@kipo.go.kr]

(3) Department of Computer Engineering, Sungkyunkwan University, Korea [e-mail: wise96@ece.skku.ac.kr, dhwon@security.re.kr]

* Corresponding author: Dongho Won

Received August 14, 2011; revised October 7, 2011; revised November 18, 2011; revised January 11, 2012; accepted January 19, 2012; published February 28, 2012

Printer friendly Cite/link Email Feedback | |

Author: | Nam, Junghyun; Kim, Moonseong; Paik, Juryon; Won, Dongho |
---|---|

Publication: | KSII Transactions on Internet and Information Systems |

Article Type: | Report |

Date: | Feb 1, 2012 |

Words: | 7251 |

Previous Article: | An image-based CAPTCHA scheme exploiting human appearance characteristics. |

Next Article: | JsSandbox: a framework for analyzing the behavior of malicious JavaScript code using internal function hooking. |

Topics: |