

ISSN 2148-838Xhttp://dx.doi.org/10.13069/jacodesmath.42848

J. Algebra Comb. Discrete Appl.
3(1) • 31–36

Received: 31 October 2015
Accepted: 30 November 2015

Journal of Algebra Combinatorics Discrete Structures and Applications

An active attack on a multiparty key exchange protocol

Research Article

Reto Schnyder, Juan Antonio López-Ramos, Joachim Rosenthal, Davide Schipani

Abstract: The multiparty key exchange introduced in Steiner et al. and presented in more general form by the
authors is known to be secure against passive attacks. In this paper, an active attack is presented
assuming malicious control of the communications of the last two users for the duration of only the
key exchange.

2010 MSC: 94A60

Keywords: Multiparty key exchange, Active attacks, Group actions

1. Introduction

The increased use of light and mobile devices has led to the study of the so called mobile ad hoc
networks. These are created, operated and managed by the nodes themselves and therefore are solely
dependent upon the cooperative and trusting nature of the nodes. The ad hoc property of these mobile
networks implies that the network is formed in an unplanned manner to meet an immediate demand and
specific goal, and that the nodes are continuously joining or leaving the network. Thus, key management
in this type of networks is a very important issue and has been the aim of numerous works since then
(see [1] or [5] and their references).

One of the most widely known such schemes is due to Steiner et al. and is known as Cliques (cf. [4]).
Cliques is a multiparty key exchange protocol generalizing the Diffie-Hellman key exchange based on the
discrete logarithm problem. It is composed of an initial key agreement (IKA) to set up a first common
key and an auxiliary key agreement (AKA) in order to refresh the key at any later stage.

The Research was supported in part by the Swiss National Science Foundation under grant No. 149716.
Juan Antonio López-Ramos is partially suppported by Ministerio de Educacion, Cultura y Deporte grant “Salvador
de Madariaga” PRX14/00121, Ministerio de Economia y Competitividad grant MTM2014-54439 and Junta de
Andalucia (FQM0211). Reto Schnyder is supported by Armasuisse.
Reto Schnyder, Joachim Rosenthal, Davide Schipani (Corresponding Author); Institute of Mathemat-

ics, University of Zurich, Switzerland (email: reto.schnyder@math.uzh.ch, rosenthal@math.uzh.ch, da-
vide.schipani@math.uzh.ch).
Juan Antonio López-Ramos; Department of Mathematics, University of Almeria, Spain (email: jlopez@ual.es).

31


R. Schnyder et. al. / J. Algebra Comb. Discrete Appl. 3(1) (2016) 31–36

In [3], the authors propose a systematic way for analyzing protocol suites which extend the Diffie-
Hellman key-exchange scheme to a group setting. They find interesting attacks which exploit algebraic
properties of Diffie-Hellman exponentiation. However, our attack uses a different approach that exploits
a weakness of a specific protocol and allows for prolonged eavesdropping.

We will consider in particular one of the proposed initial key agreements referred to (in [4]) as IKA.2.
The authors generalize these schemes in [2], considering a general action on a semigroup, and this is how
IKA.2 is presented below.

We will then show an active attack on this protocol that requires control of the communications of
two particular parties for only the duration of the key exchange. That is, unlike in a regular man-in-the-
middle attack, it is not necessary for the attacker to control the communications after the key exchange
in order to translate messages, since all users are made to agree on the same key.

Although it is not possible for the attacker to keep a copy of the key after the users initiate AKA
operations, we will show how she can avoid being noticed at that point.

2. An initial key agreement protocol

The protocol below gives n users the possibility to share an initial common key built using their
private keys. A proof of its correctness and security against passive attacks can be found in [2, 4],
assuming the Diffie-Hellman problem is hard for the given group action.

Suppose we have n users U1, . . . ,Un who wish to agree upon a common key.
Let G be an abelian group, written multiplicatively. Let S be a set, and suppose we have a group

action

G×S → S
(g, s) 7→ g ·s.

The users publicly agree on a common element C0 = s ∈ S, and for each i = 1, . . . , n, the user Ui
selects a secret group element gi ∈ G.

The protocol proceeds as follows:

1. For i = 1, . . . , n− 2, Ui sends to Ui+1 the message Ci = gi ·Ci−1.

2. Un−1 broadcasts Cn−1 = gn−1 ·Cn−2 to the other users U1, . . . ,Un−2,Un.

3. Un computes the shared key K = gn ·Cn−1.

4. For i = 1, . . . , n− 1, Ui sends Di = g−1i ·Cn−1 to Un.

5. Un broadcasts {gn ·D1, gn ·D2, . . . , gn ·Dn−1, Cn−1} to Ui, i = 1, . . . , n− 1.

6. For i = 1, . . . , n− 1, Ui computes the shared key K = gi · (gn ·Di).

It is easy to see that for i = 1, . . . , n− 1, we have that

Ci =

( i∏
j=1

gj

)
·s,

Di =

(n−1∏
j=1
j 6=i

gj

)
·s,

32


R. Schnyder et. al. / J. Algebra Comb. Discrete Appl. 3(1) (2016) 31–36

and finally

K = Cn =

( n∏
j=1

gj

)
·s.

From the above, we can also observe that Cn−1 is not needed by any user to recover the session key
K. However, this information is disclosed for future rekeying purposes, as we will see later.

Example 2.1. Let Fq be a finite field. Let us consider an element g of prime order p, generating the
subgroup S ⊂ F∗q. Then the action Φ : Z∗p × S → S defined by Φ(x, h) = hx provides the Initial Key
Agreement protocol introduced in [4, Section 4.2] as IKA.2.

Example 2.2. Let us denote by ε the group of points of an elliptic curve of prime order p. Then the
action Φ : Z∗p ×ε → ε defined by Φ(x, P ) = xP gives an elliptic curve version of IKA.2 cited above.

3. An active attack on the initial key agreement

We describe an active attack on the protocol of the preceding section. Suppose that the attacker M
wants the users U1, . . . ,Un to agree on a shared key as usual, except that she is in possession of the key
as well.

In order to carry out our attack, M needs to have full control over the communication of the users
Un−1 and Un for the duration of the key exchange. However, unlike in a regular man-in-the-middle attack,
she does not need to maintain this control after the key exchange is completed.

In the beginning, M chooses her own secret group element ĝ ∈ G. She then proceeds as follows:

1. Step (1) is carried out as usual.

2. M intercepts the broadcast of Un−1 during step (2) and remembers the value Cn−1. At this point,
all users except for Un−1 are sitting in step (2), waiting for the broadcast that was halted.

3. Un−1 proceeds to step (4), where he sends g−1n−1 · Cn−1 = Cn−2 to Un. This is also intercepted by
M. Un−1 is now waiting in step (5).

4. M now makes Un believe that he received the broadcast of step (2), but actually sends him ĝ·Cn−1.
At this point, Un computes the shared key K = gnĝ ·Cn−1 and waits in step (4).

5. M now sends to Un the values {m1, . . . , mn−3, Cn−2, Cn−1}, pretending that they were sent by the
other users in step (4). The mi are random elements of the orbit G ·s.

6. In step (5), Un sends back, among others, the values gn ·Cn−2 and gn ·Cn−1, which M intercepts.
The user Un is now finished, and M can compute the shared key K = ĝgn ·Cn−1.

7. Until now, U1, . . . ,Un−2 have been waiting for the broadcast in step (2), which M now provides in
the form of gn ·Cn−1.

8. Ui, i = 1 . . . , n− 2, go to step (4) and send back g−1i gn ·Cn−1, which M intercepts.

9. In step (5), M broadcasts to Ui, i = 1 . . . , n− 2, the message

{ĝg−11 gn ·Cn−1, ĝg
−1
2 gn ·Cn−1, . . . , ĝg

−1
n−1gn ·Cn−1, gn ·Cn−1}

User Un−1 is sent the same message, but the last element, gn ·Cn−1 is substituted by Cn−1.

10. The users U1, . . . ,Un−2 now all compute the shared secret K = giĝg−1i gn ·Cn−1.

33


R. Schnyder et. al. / J. Algebra Comb. Discrete Appl. 3(1) (2016) 31–36

Let us make some comments on the attack introduced above. First, we can observe that at the end
of this procedure, all users as well as the attacker share the same key

K =

( n∏
j=1

gj

)
· (ĝ ·s).

Any passive observer will still be unable to determine the key, for the same reason that the original
protocol is secure against passive attacks, cf. [4, Theorem 2.1], whose proof also applies to the general
setting given in Section 2 whenever the action is transitive and the Diffie-Hellman problem is hard.

The attacker’s secret ĝ is not strictly required for the attack to work, but without it, the users may
notice that something is amiss. Namely, in step (e), if we leave out ĝ, the user Un may notice that M
sent the same value Cn−1 as in step (d). Similarly, in step (i), the other users could notice that the
attacker just returned their transmission from (h). Using ĝ, however, the users should be unable to tell
the difference between a regular execution of the protocol and the attack, again as a consequence of [4,
Theorem 2.1].

As in the Initial Key Agreement (IKA) protocol introduced in Section 2, the broadcast element
gn ·Cn−1 is added at the end of the message in (i) in view of future rekeying operations and is not needed
by any of the users U1, . . . ,Un−2 to recover the shared key. Note that users Ui, i = 1, . . . , n − 2, expect
that the last element of the message sent in step (i) is the one broadcast in step (2) of the protocol,
which the attacker substitutes precisely by gn · Cn−1. In the case of user Un−1, who is also expecting
the element sent in step (2) of the protocol, the element that M sends in step (b) is Cn−1. If this is not
satisfied, the users might notice that something is wrong.

4. An exit strategy

After the attack of Section 3, the attacker M shares the key with the users U1, . . . ,Un and can listen
in on their conversation without any further active measures. However, at some point after that, the
users may wish to execute an AKA operation, which is to say a key refreshment, the addition of a new
member to the group, etc. as described in [4, Section 5]. After this point, the attacker can certainly no
longer listen to the conversation. Even worse, the values the users remember from step (5) of the protocol
are substantially different from normal, and any key refresh operation will thus fail completely, alerting
the users about the attack.

In what follows, we will describe how the attacker can avoid being noticed by forging key refresh
operations herself, assuming that any user may initiate a key refreshment at any time.

First, we recall the key refresh operation after a regular execution of IKA.2, adapted from [4, Sec-
tion 5.6]. Suppose user Uc wishes to initiate a key refreshment. He remembers from step (5) of the key
agreement protocol the values {E1, . . . , En}, where Ek =

(∏n
j=1,j 6=k gj

)
·s, k = 1, . . . , n. He picks a new

secret g′c ∈ G and broadcasts

{g′c ·E1, . . . , g
′
c ·Ec−1, Ec, g

′
c ·Ec+1, . . . , g

′
c ·En}.

Now, all users can compute the new key g′c ·Cn = g′c ·
(∏n

j=1 gj
)
·s. User Uc also replaces his own secret

with g′cgc, and everyone replaces the information remembered from step (5) with this new broadcast.

Remark 4.1. One important detail to note is that when Uc initiates the key refreshment, the value Ec
he sends in position c is unchanged and already known to the other users. Hence, if M wishes to forge a
key refreshment coming from Uc, she has to make sure that each user receives in position c the value he
previously held there. Otherwise, the attack could be discovered.

Suppose now that the attacker M has just executed the attack from Section 3. Instead of
{E1, . . . , En}, the users now remember the following values:

34


R. Schnyder et. al. / J. Algebra Comb. Discrete Appl. 3(1) (2016) 31–36

• For i = 1, . . . , n− 2, Ui remembers {ĝ ·E1, . . . , ĝ ·En−1, Cn}.

• Un−1 remembers {ĝ ·E1, . . . , ĝ ·En−1, En}.

• Un remembers {gn ·m1, . . . , gn ·mn−3, En−1, Cn, ĝ ·En}.

Evidently, if some user tries to initiate a key refreshment with these values, the operation will fail.
However, M can bring the users into a consistent state by forging two key refresh operations herself. For
this, she needs to still have control over the communications of Un−1 and Un, as in the original attack.

First, M picks two new random values f̂ and ĥ ∈ G. Then, she forges a key refresh operation by
sending the following values to the different users:

• To Ui, i = 1, . . . , n− 2, she sends

{ĥĝ ·E1, ĥĝ ·E2, . . . , ĥĝ ·En−2, ĝ ·En−1, f̂ĥĝ ·En},

pretending it came from Un−1.

• To Un−1, she sends

{f̂ĥĝ ·E1, ĥĝ ·E2, . . . , ĥĝ ·En−2, ĥĝ ·En−1, En},

pretending it came from Un.

• To Un, she sends

{f̂ĥĝ ·E1, ĥĝ ·E2, . . . , ĥĝ ·En−2, Cn, ĥĝEn},

pretending it came from Un−1.

After this, the users will agree on the shared key ĥĝ ·Cn, which is also known to M. As remarked above,
if a user is made to believe that he received a key refreshment from Uc, he must receive in position c the
value he already held there.

Now, the values held by the users are still inconsistent, so M has to forge a second key refreshment:

• To Ui, i = 1, . . . , n− 2, she sends

{f̂ĥĝ ·E1, . . . , f̂ĥĝ ·En},

pretending it came from Un.

• To Un−1 and Un, she sends

{f̂ĥĝ ·E1, . . . , f̂ĥĝ ·En},

pretending it came from U1.

Now, all users and the attacker agree on the shared key f̂ĥĝ · Cn. Furthermore, all users remember the
same consistent values for key refreshment. If in the future any user initiates a key refreshment or other
AKA operation, the attacker will lose access to the key, but the operation itself will work out without
problem and without the users noticing anything wrong.

Remark 4.2. An alternative course of action for M is to convert the attack into a regular man-in-the-
middle attack on Un at the time of the first key refreshment. For this, note that given the values each user
remembers, a key refreshment initiated by Uc, c ≤ n − 2, works well for all users but Un. The attacker
can then intercept the broadcast arriving at Un and replace it with random values, except that at position
n she sends ĥ · En for some random ĥ ∈ G, and at position c she sends gn · mc, which she knows from
step (f) of the attack. Then, M will have the key ĝg′c ·Cn in common with Ui, i ≤ n−1, as well as ĥ ·Cn
with Un. From then on, she can run a regular man-in-the-middle attack. A similar attack can be carried
out if Un initiates a key refreshment, but not if Un−1 does so. In this case, the attacker can intercept
and apply ĝ to the message for Un so that all users agree on a common key without noticing the previous
attack.

35


R. Schnyder et. al. / J. Algebra Comb. Discrete Appl. 3(1) (2016) 31–36

5. Conclusions

We have presented an active attack against Cliques, one of the most popular multiparty key exchange
protocols currently known. By assuming control of the communications of the last two users in the initial
key agreement process, an attacker can eavesdrop into the subsequent communications between legitimate
users without the need of a regular man-in-the-middle attack. The attacker is also able to leave the group
unnoticed when later key renewals do not allow further eavesdropping.

References

[1] P. P. C. Lee, J. C. S. Lui, D. K. Y. Yau, Distributed collaborative key agreement and authentication
protocols for dynamic peer groups, IEEE/ACM Trans. Netw. 14(2) (2006) 263–276.

[2] J. A. López-Ramos, J. Rosenthal, D. Schipani, R. Schnyder, Group key management based on semi-
group actions, arxiv.org/pdf/1509.01075v1.pdf.

[3] O. Pereira, J. -J. Quisquater, Generic insecurity of cliques-type authenticated group key agreement
protocols, Proc. 17th IEEE Computer Security Foundations Workshop, 16–29, 2004.

[4] M. Steiner, G. Tsudik, M. Waidner, Key agreement in dynamic peer groups, IEEE Trans. Parallel
Distrib. Systems 11(8) (2000) 769–780.

[5] J. Van der Merwe, D. Dawoud, S. McDonald, A survey on peer-to-peer key management for mobile
ad hoc networks, ACM Computing Surveys 39(1) (2007) 1–45.

36

http://dx.doi.org/10.1109/TNET.2006.872575
http://dx.doi.org/10.1109/TNET.2006.872575
http://arxiv.org/pdf/1509.01075v1.pdf
http://arxiv.org/pdf/1509.01075v1.pdf
http://dx.doi.org/10.1109/CSFW.2004.1310729
http://dx.doi.org/10.1109/CSFW.2004.1310729
http://dx.doi.org/10.1109/71.877936
http://dx.doi.org/10.1109/71.877936
http://dx.doi.org/10.1145/1216370.1216371
http://dx.doi.org/10.1145/1216370.1216371

	Introduction
	An initial key agreement protocol
	An active attack on the initial key agreement
	An exit strategy
	Conclusions
	References