# Secure Collaborative Key Management for Dynamic Groups in Mobile Networks

Authors: Sukin Kang; Cheongmin Ji; Manpyo Hong
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

Mobile networks are composed of heterogeneous mobile devices with peer-to-peer wireless communication. Their dynamic and self-organizing natures pose security challenge. We consider secure group key management for peer dynamic groups in mobile wireless networks. Many group based applications have achieved remarkable growth along with increasing use of multicast based services. The key sharing among the group members is an important issue for secure group communication because the communication for many participants implies that the likelihood of illegal overhearing increases. We propose a group key sharing scheme and efficient rekeying methods for frequent membership changes from network dynamics. The proposed method enables the group members to simply establish a group key and provide high flexibility for dynamic group changes such as member join or leave and group merging or partition. We conduct mathematical evaluation with other group key management protocols and finally prove its security by demonstrating group key secrecy, backward and forward secrecy, key independence, and implicit key authentication under the decisional Diffie-Hellman (DDH) assumption.


---

## Body

## 1. Introduction

Advances in wireless communications and mobile devices have made various types of mobile networks such as mobile ad hoc networks (MANETs), wireless mobile sensor networks (WMSNs), and Internet of things (IoT). In mobile networks, heterogeneous devices such as smartphones, laptops, and smart sensors perform peer-to-peer (machine-to-machine) communications without depending on any fixed infrastructure. Mobile networks have features distinct from conventional networks. First, network topology changes dynamically due to the mobility of nodes, which causes frequent switching of network connection state. Additionally, many applications in mobile networks support one-to-many (multicast) communication, where common data are transferred to multiple destinations from a source, for instance, military communication (battlefield), health care system, industrial monitoring, on-line conferencing, collaborative workspace, and disaster management. They build a collaborative group of entities, called group members, which participate in multicast group communications as a group member and manage group membership changed by node mobility.Group communication over wireless networks is susceptible to illegal overhearing such as packet sniffing. When a group deals with sensitive information, secure group communication must be achieved by sharing a common secret key—group key for confidentiality of group messages with data encryption. In other words, it is essential to decide how to share a key among group members and how to update the group key for group membership change [1–3]. A typical approach is based on centralized key distribution with a trusted third party (TTP) [4–8]. It provides scalable group key management for large groups using symmetric encryption such as advanced encryption standard (AES) and hierarchical logical key tree. However, it fairly depends on a constantly accessible TTP. This requirement is not suitable for mobile networks with peer-to-peer communication. To apply a symmetric key based approach without a TTP, a node should establish secure connection for sharing a pairwise key with all other mobile nodes in a group. It requires much communication and depends on another key sharing scheme [9]. Diffie-Hellman (DH) key exchange [10] is a protocol to establish a common key based on asymmetric keys without any TTP. It allows two parties to share a key using their secrets over an insecure channel. To extend DH into group setting, group key agreement (GKA) protocols have been developed [11–16]. In the protocols, also known as contributory key agreement, all group members contribute to generation of a common key. While providing dynamic group key management, they require considerable messages or operations to establish and update group keys. An approach for reducing computation cost deploys tree structure to handle key management. Tree-based group key protocols [15–18] need to support management of tree structure and require ordered message delivery for calculation from leaves to the root of the tree.In this paper, we investigate secure group key distribution and management for collaborative groups with high group flexibility. We propose a DH-based group key management protocol and show security proof of the proposed scheme and mathematical evaluation with other GKA protocols.The remainder of the paper is organized as follows. In Section2, we address related works. Section 3 explains our group key management scheme with group membership events and security requirements. Section 4 describes performance analysis and Section 5 shows security proof for the proposed key management. We conclude the paper in Section 6.


## 2. Related Work

Over the past few decades, a considerable number of studies have been conducted on group key establishment and management. A typical approach is centralized key distribution based on constantly accessible TTP and pairwise keys [4–8]. These studies showed apparent efficiency for large groups such as wireless sensor network (WSN). Since, however, a mobile network is comprised of peer-to-peer communications with dynamic mobility and without a TTP, it is difficult to provide scalable group key management on arbitrary group setting [15].We focus on DH based group key management, known as group key agreement (GKA), in which a common key is generated by all group members’ equal contributions. DH protocol allows two parties to share a key using their secrets over an insecure channel [10]. The key computation of DH uses the multiplicative group of integer modulo p, where p is a large prime number. Each party chooses a random number x
i in Z
p and computes g
x
i
mod
⁡
p, where g is a primitive root (generator) mod
⁡
p. They exchange the computed values, g
x
1
mod
⁡
p and g
x
2
mod
⁡
p, and agree on the common key:
(1)
K
=
(
g
x
1
)
x
2
mod
⁡
p
=
(
g
x
2
)
x
1
mod
⁡
p
.For extending it to group setting, Burmester and Desmedt (BD) proposed a conference key exchange system [11] depending on a broadcast manner. When the number of group members isn, the group key (GK) of BD becomes
(2)
GK
=
g
x
1
x
2
+
x
2
x
3
+
⋯
+
x
n
-
1
x
n
mod
⁡
p
.
As BD system requires large communication messages, Steiner et al. proposed group key agreement protocols called group Diffie-Hellman (GDH) [12, 13]. In GDH,
(3)
GK
=
g
x
1
x
2
…
x
n
-
1
x
n
mod
⁡
p
.
They showed not only that DH can be extended efficiently to group setting, but also that their protocol can deal efficiently with group membership change. They presented three distinct group key agreements GDH.1, GDH.2, and GDH.3, which later was advanced as a protocol suite known as CLIQUES [13]. In GDH.x, group members can individually or massively join and leave; CLIQUES also considers group integration and group division. A variant of GDH protocol is a centralized key distribution (CKD) scheme. In CKD, a controller distributes the group key to every member using pairwise temporal keys between the controller and each of the members, which is computed using DH fashion.As group dynamics have become an important issue, some studies have adopted tree-based approach [15–18]. Skinny tree (STR) protocol [16] has good performance for member addition. In STR,
(4)
GK
=
g
x
n
g
x
n
-
1
g
…
g
x
3
g
x
1
x
2
mod
⁡
p
.
While STR uses unbalanced key tree for group key computation, tree-based group Diffie-Hellman (TGDH) leverages balanced tree structure. Given eight group members in TGDH, the group key is computed as follows:
(5)
GK
=
g
g
g
x
1
x
2
g
x
3
x
4
g
g
x
5
x
6
g
x
7
x
8
mod
⁡
p
.
STR and TGDH require a sponsor node which distributes intermediate computing keys in the tree during membership event changes. As tree-based protocols apparently help to reduce communication cost and operation cost, there have been several variants of TGDH [17, 18]. However, they need to support management for tree balance and require message delivery order due to hierarchical tree structure. In mobile networks, much communication would be required to make sure that the group members can keep the synchronized tree structure.In summary, DH-based group key protocol is generally known as GKA protocol. Although our protocol is based on DH, we do not classify it as a GKA protocol because of key distribution feature from a controller. Our proposed scheme provides the advantage of dynamics and collaborative contribution in computing group keys with a modified key agreement method.


## 3. Secure Group Key Management for Mobile Networks

### 3.1. Membership and Security Requirements

Group membership events occur with either insertion of a new node or deletion of an existing member. We define the insertion event asmember join and the deletion event asmember leave. When there is only one event node specifically, we call eachsingle join andsingle leave, and when there are two or more event nodes we call eachmass join andmass leave. Furthermore, we consider a group insertion into a group and a group partition into two distinct groups. We define them asgroup merging andgroup partition, respectively. Figure 1 shows summary of defined membership events.Figure 1
Four kinds of membership events;(
1
) member join (single join or mass join), (
2
) member leave (a single leave or mass leave), (
3
) group merging (group join), and (
4
) group partition (group leave). A small circle represents a node while a big circle represents a group of nodes.Group membership change is closely related to security of group communication. Outgoing members should have no access to group communication after it leaves the group, and ingoing nodes should be prevented from accessing previous group communication before it joins the group. We define cryptographic properties in which a secure group, depending on a group key, should meet(
1
)
group key secrecy that guarantees an adversary who knows that messages sent to group members cannot discover any group key in polynomial time, (
2
)
backward secrecy that guarantees a new member or an adversary who knows that the current group key cannot discover any previous group key in polynomial time, (
3
)
forward secrecy that guarantees a former group member or an adversary who knows that previous group keys cannot discover any subsequent group key in polynomial time, (
4
)
key independence that guarantees an adversary who knows that a proper subset of group keys cannot discover any other group keys in polynomial time, and (
5
) (implicit)key authentication that guarantees that no one apart from a group member recovers the group key.


### 3.2. Group Key Establishment

We present a new group key protocol, collaborative Diffie-Hellman (CODH). CODH has centralized topology and key distribution property from a leader node. But, unlike conventional centralized scheme with TTP, in CODH, a group leader computes and distributes a group key by using public keys of group members. We formalize the group key protocol and prove its security.CODH has one leader calledmaster. The leader is also one of group members. It consumes more energy than normal nodes for communication and operation in managing group keys. There will be a policy for choosing a leader. In mobile networks, signal strength, degree to neighbors, identity, and resources (CPU, memory, battery, and bandwidth) would be criteria for leader election [19–21]. When a group is created, the first master is elected among group members and performs group key initialization. Afterwards, group members select a new master when receiving master notification for leader change. Once a new group master is selected for group management, the previous master forwards information about group members to the new master; that is, a delegation process is run (refer to Sections 3.3 and 3.4). On the other hand, connection failure may occur by network isolation or denial of service attacks. (We assume that group participants are honest and not compromised. However, they can be threatened by network adversaries who can perform all of network-based attacks.) We consider the connection failure as a kind of member leave whether the left node is a member or the master.Notation section represents notations used to illustrate our group key protocol. The index “s” stands for the master node in a group that is distinct from i or j which indicates a general member node. Therefore, M
i or M
j means an identity for general member, while M
s denotes the master.Lock-secret is defined as a secret value of a member. It locks the group key so that M
s can securely transfer the group key to the members. General members use theirunlock-secret to extract the group key from M
s’s broadcast message of a locked group key.We adopt inverse exponentiation for obtaining the group key. LetC
n be a group of size n; that is, C
n
=
{
M
1
,
M
2
,
…
,
M
n
} and M
s
∈
C
n. To share the initial group key, the group C
n runs steps in Box 1 for the initial phase.Box 1:Group key initialization.
Assume that the group ofn members establish a group key.
Step  1. Each member selects random x
i
∈
Z
q and computes X
i
=
g
x
i mod p.
M
i → M
s: X
i (i
∈ [1,n], i
≠
s)
Step  2. M
s selects random k in Z
q for group key sharing and computes key-locks.
M
s
⇒
C
n: {
(
X
i
)
k
|
i
∈
[
1
,
n
]
,
i
≠
s
}The initial phase consists of two rounds. In the first round, all members except the group master send their lockerg
x
i to the master via unicast and the master produces the locker list, X
L
C, from receiving messages. In the second round, the master M
s selects a random secret k and computes and broadcasts the locked group key (
X
i
)
k
=
(
g
x
i
)
k using X
L
C. Then, each member can compute the group key GK using their own unlock-secret, y
i, as follows:
(6)
GK
≡
(
X
i
k
)
y
i
mod
⁡
p
≡
(
g
x
i
y
i
)
k
mod
⁡
p
≡
g
k
mod
⁡
p
.The group key is equal to the locker of the group master whenk is the master’s secret. Therefore, operations for computing X
i
k and group messages never include X
s.


### 3.3. Group Rekeying for Member Join and Leave

The master-secret should be renewed when membership changes, since it is used for the new group keyGK
′. In Box 2 (member join process), k
′ means a new master-secret that M
s selects. Let M
n
+
1 be the first new member and let M
n
+
m be the last new member, when m new members join the group C
n (if a single member joins, the new member is only one node, M
n
+
1). A new member M
j
(
n
+
1
≤
j
≤
n
+
m
) sends its locker X
j to the master, and then M
s broadcasts locked new group key GK
′
=
g
k
′ to all the group members in the same manner as second round of initial phase, as in Box 2. All members, including new members, can extract the new group key GK
′ in the same way as (6).Box 2:Group rekeying for member join.
Assume thatm members are added to the group C
n.
Step  1. Each new member M
j (n
+
1
≤
j
≤
n
+
m) selects random x
j
∈
Z
q and computes X
j = g
x
j mod p.
M
j → M
s: X
j (j
∈ [n
+
1, n
+
m])
Step  2. M
s selects random k
′ in Z
q for new group key and computes key-locks.
M
s
⇒
C
n: {
(
X
i
)
k
′
|
i
∈
[
1, n
+
m
]
,
i
≠
s
}Unlike the join event, member leave process does not require the first round for sending lockers to the master. Let a subset ofC
n for leaving members be L
m
⊂
C
n (M
s
∉
L
m). Group members conduct rekeying operations for the new group key GK
′ as in Box 3.Box 3:Group rekeying for member leave.
Assume that a subsetL
m of current group C
n is composed of m leaving members in
the group and does not include the group masterM
s.
Step  1. M
s selects random k
′ in Z
q for new group key and computes key-locks with updated locker list.
M
s
⇒
C
n ∖ L
m: {
(
X
i
)
k
′
|
i
∈
[
1
,
n
]
∧
M
i
∉
L
m
,
i
≠
s
}The leaving nodes cannot learn the new group key because the broadcast message fromM
s does not contain any locker X
i for leaving members. Note that the set L
m for the leaving node does not include the master. Leaving of the master requires ‘delegation’ during which the master forwards locker list X
L
C for group C
n to new group master(
M
s
′
) as follows:
(7)
M
s
⟶
M
s
′
:
X
L
C
=
{
X
j
∣
M
j
∈
C
n
,
j
≠
s
}
.
The delegation can be used for another case where the master wishes to finish its master’s role for a reason such as network topology change or resource exhaustion; that is, the master turns to a group member not leaving the group. In this case, the delegation message includes the former master’s locker generated with new selected secret x
s as follows:
(8)
M
s
⟶
M
s
′
:
X
L
C
=
{
X
j
∣
M
j
∈
C
n
,
x
s
≠
k
,
x
s
≠
k
′
}
.When group members detect unexpected disconnection from the master, they restart group key initialization with new master selection. At the worst case, members can suffer from frequent connection failure with the master. In this case, the first protocol should be slightly modified to make all of group members have the locker list and any member be the group master to proceed Box3. For instance, a general member at the first step of Box 1 broadcasts its locker to the group as follows:
(9)
M
i
⟹
C
n
:
X
i
(
i
∈
[
1
,
n
]
,
i
≠
s
)
.
The group members continue secure communication with a fresh group key obtained through group rekeying. We provide formal security proofs in Section 5.


### 3.4. Group Rekeying for Group Merging and Partition

There are two ways to integrate two groups into one group completely:individual join andgroup join. The former is that members of a group join another group individually. It is similar to the mass joining process, saving that the joining master should generate his lock-secret, x
s, and locker, g
x
s. The latter way is that a group is absorbed into the other group via delegation process between both group masters.Let two groups be mergedC
n
=
{
M
1
,
M
2
,
…
,
M
n
} and R
m
=
{
M
1
,
M
2
,
…
,
M
m
} (n
≥
m). The master M
s of C
n survives after group merging, while the master M
s
′ of R
m becomes a member of the merged group. Smaller group members (∈
R
m) become a member of C
n
+
m; that is, C
n
+
m
=
{
M
1
,
M
2
,
…
,
M
n
,
M
n
+
1
,
…
,
M
n
+
m
} and M
s
∈
C
n after group merging. Group merging process runs with delegation (in the first round) as in Box 4. Figure 2 represents an instance for a merging process for a current group C
4 and a merged group R
3. In Figure 2, the number in a circle indicates members’ index (such as by a joined order). Before they are merged, the number of the current group C is four including the group master (i.e., n
=
4, C
4) and the number of members of joining group is three (i.e., m
=
3, R
3). To be merged, the master of R
3 sends the master of C
4 the locker list X
L
R for M
1 and M
2. Note that the master M
s of R
m must forward its locker after changing its own secret because it was used as the former group key. The master of C
4 becomes the master for the merged group. It updates X
L
C and generates key-locks X
L
C
k with a new selected random k.Box 4:Group merging.
Assume that a groupR
m is merged into a group C
n where n
≥
m, and the merged
groupC
n
+
m = C
n
∪
R
m. M
s
′ is the master of R
m and M
s is the master of C
n.
Step  1. M
s
′ selects a random number x
s
′ in Z
q, computes X
s
′= g
x
s
′mod p, and updates
the locker list intoX
L
R= {
X
1, X
2
,
…, X
m
}
∪
X
s
′.
(delegation) M
s
′ → M
s: X
L
R
Step  2. M
s selects random k
′ in Z
q for new group key and computes key-locks with updated locker list.
M
s
⇒
C
n
+
m: {
(
X
i
)
k
′
|
i
∈
[
1, n
+
m
]
,
i
≠
s
}Group merging process: (a) when groupsC
4 and R
3 are merged,R’s master sends the locker list of R toC’s master and (b) after groups are merged,C’s master becomes the master for merged group and broadcasts the key-locks for new group key to all of the members.
(a)
(b)As shown in Figure3, the current group will be divided into two groups. When the number of left members is m, the current group will have (n
-
m) members after the partition process. Group partition requires one more master M
s
′ for a separated subgroup P
m
⊂
C
n (M
s
∉
P
m). Group partition process can be easily conducted through delegation, from the master M
s of group C
n to the fresh master M
s
′ of subgroup P
m. The divided groups perform a group key initial phase after the delegation process, as in Box 5.Box 5:Group partition.
Assume that a current groupC
n is partitioned into two groups, P
m (⊂
C
n) and C
n
-
m (=C
n ∖ P
m).
The master ofR
m is M
s
′ and the master of C
n is M
s (∉
P
m)
Step  1. M
s generate X
L
P = {
X
j
|
M
j
∈
P
m
,
j
≠
s
} from X
L
C.
(delegation) M
s → M
s
′: X
L
P
Step  2. M
s and M
s
′ select random k
′, k
′
′ in Z
q respectively and compute key-locks with their locker list.
M
s
⇒
C
n
-
m: {
(
X
i
)
k
′
|
i
∈
[1, n
]
∧
M
i
∉
P
m, i
≠
s
}
M
s
′
⇒
P
m: {
(
X
j
)
k
′
′
|
M
j
∈
P
m, j
≠
s
}Group partition process: (a) when groupC
7 is partitioned into two groups (new group P
3), the master of the original group sendsP’s master the locker list of the new subgroup and (b) after the group is split, each group master broadcasts the key-locks for each new group key.
(a)
(b)


### 3.5. Implicit Key Authentication

For the secure key authentication, the messages sent from all members should be signed with a signature key. Hash-based signature such as message authentication code (MAC) is fairly efficient in terms of computation cost. However, it is too costly to share one-to-one pairwise keys between all of group members in advance.We assume that a member holds long-term private and public keys certified by a trusted certificate authority (CA). (Each member can use a different signature algorithm such as RSA-based signature algorithm, digital signature algorithm (DSA), and elliptic curve digital signature algorithm (ECDSA). Note that some of them do not provide message encryption; that is, it is used for message signing and verifying. We consider that DSA is better for our scheme since its public key includesg
x mod p.) The group members send to the master the signed messages with their own private key; for example, in the first step of Box 1, a member, M
i, sends to the master {
X
i
,
S
i
g
M
i
(
X
i
)
} which M
i signs for X
i with its private key. Note that this process runs one-time at initial phase or it can be precomputed with X
i.Members can obtain the group key securely by verifying the messages of the master with signature signed with the master’s private key. All of messages from the master come with a master-signed signature for the origin and integrity of a group key. For example, in the second step of Box1, the master broadcasts {
X
1
k
,
X
2
k
,
…
,
X
n
k
,
S
i
g
M
s
(
GK
)
}. The master produces a locked set for the group key using verified members’ locker. It implies that outsiders cannot recover the group key from the master’s messages.


## 3.1. Membership and Security Requirements

Group membership events occur with either insertion of a new node or deletion of an existing member. We define the insertion event asmember join and the deletion event asmember leave. When there is only one event node specifically, we call eachsingle join andsingle leave, and when there are two or more event nodes we call eachmass join andmass leave. Furthermore, we consider a group insertion into a group and a group partition into two distinct groups. We define them asgroup merging andgroup partition, respectively. Figure 1 shows summary of defined membership events.Figure 1
Four kinds of membership events;(
1
) member join (single join or mass join), (
2
) member leave (a single leave or mass leave), (
3
) group merging (group join), and (
4
) group partition (group leave). A small circle represents a node while a big circle represents a group of nodes.Group membership change is closely related to security of group communication. Outgoing members should have no access to group communication after it leaves the group, and ingoing nodes should be prevented from accessing previous group communication before it joins the group. We define cryptographic properties in which a secure group, depending on a group key, should meet(
1
)
group key secrecy that guarantees an adversary who knows that messages sent to group members cannot discover any group key in polynomial time, (
2
)
backward secrecy that guarantees a new member or an adversary who knows that the current group key cannot discover any previous group key in polynomial time, (
3
)
forward secrecy that guarantees a former group member or an adversary who knows that previous group keys cannot discover any subsequent group key in polynomial time, (
4
)
key independence that guarantees an adversary who knows that a proper subset of group keys cannot discover any other group keys in polynomial time, and (
5
) (implicit)key authentication that guarantees that no one apart from a group member recovers the group key.


## 3.2. Group Key Establishment

We present a new group key protocol, collaborative Diffie-Hellman (CODH). CODH has centralized topology and key distribution property from a leader node. But, unlike conventional centralized scheme with TTP, in CODH, a group leader computes and distributes a group key by using public keys of group members. We formalize the group key protocol and prove its security.CODH has one leader calledmaster. The leader is also one of group members. It consumes more energy than normal nodes for communication and operation in managing group keys. There will be a policy for choosing a leader. In mobile networks, signal strength, degree to neighbors, identity, and resources (CPU, memory, battery, and bandwidth) would be criteria for leader election [19–21]. When a group is created, the first master is elected among group members and performs group key initialization. Afterwards, group members select a new master when receiving master notification for leader change. Once a new group master is selected for group management, the previous master forwards information about group members to the new master; that is, a delegation process is run (refer to Sections 3.3 and 3.4). On the other hand, connection failure may occur by network isolation or denial of service attacks. (We assume that group participants are honest and not compromised. However, they can be threatened by network adversaries who can perform all of network-based attacks.) We consider the connection failure as a kind of member leave whether the left node is a member or the master.Notation section represents notations used to illustrate our group key protocol. The index “s” stands for the master node in a group that is distinct from i or j which indicates a general member node. Therefore, M
i or M
j means an identity for general member, while M
s denotes the master.Lock-secret is defined as a secret value of a member. It locks the group key so that M
s can securely transfer the group key to the members. General members use theirunlock-secret to extract the group key from M
s’s broadcast message of a locked group key.We adopt inverse exponentiation for obtaining the group key. LetC
n be a group of size n; that is, C
n
=
{
M
1
,
M
2
,
…
,
M
n
} and M
s
∈
C
n. To share the initial group key, the group C
n runs steps in Box 1 for the initial phase.Box 1:Group key initialization.
Assume that the group ofn members establish a group key.
Step  1. Each member selects random x
i
∈
Z
q and computes X
i
=
g
x
i mod p.
M
i → M
s: X
i (i
∈ [1,n], i
≠
s)
Step  2. M
s selects random k in Z
q for group key sharing and computes key-locks.
M
s
⇒
C
n: {
(
X
i
)
k
|
i
∈
[
1
,
n
]
,
i
≠
s
}The initial phase consists of two rounds. In the first round, all members except the group master send their lockerg
x
i to the master via unicast and the master produces the locker list, X
L
C, from receiving messages. In the second round, the master M
s selects a random secret k and computes and broadcasts the locked group key (
X
i
)
k
=
(
g
x
i
)
k using X
L
C. Then, each member can compute the group key GK using their own unlock-secret, y
i, as follows:
(6)
GK
≡
(
X
i
k
)
y
i
mod
⁡
p
≡
(
g
x
i
y
i
)
k
mod
⁡
p
≡
g
k
mod
⁡
p
.The group key is equal to the locker of the group master whenk is the master’s secret. Therefore, operations for computing X
i
k and group messages never include X
s.


## 3.3. Group Rekeying for Member Join and Leave

The master-secret should be renewed when membership changes, since it is used for the new group keyGK
′. In Box 2 (member join process), k
′ means a new master-secret that M
s selects. Let M
n
+
1 be the first new member and let M
n
+
m be the last new member, when m new members join the group C
n (if a single member joins, the new member is only one node, M
n
+
1). A new member M
j
(
n
+
1
≤
j
≤
n
+
m
) sends its locker X
j to the master, and then M
s broadcasts locked new group key GK
′
=
g
k
′ to all the group members in the same manner as second round of initial phase, as in Box 2. All members, including new members, can extract the new group key GK
′ in the same way as (6).Box 2:Group rekeying for member join.
Assume thatm members are added to the group C
n.
Step  1. Each new member M
j (n
+
1
≤
j
≤
n
+
m) selects random x
j
∈
Z
q and computes X
j = g
x
j mod p.
M
j → M
s: X
j (j
∈ [n
+
1, n
+
m])
Step  2. M
s selects random k
′ in Z
q for new group key and computes key-locks.
M
s
⇒
C
n: {
(
X
i
)
k
′
|
i
∈
[
1, n
+
m
]
,
i
≠
s
}Unlike the join event, member leave process does not require the first round for sending lockers to the master. Let a subset ofC
n for leaving members be L
m
⊂
C
n (M
s
∉
L
m). Group members conduct rekeying operations for the new group key GK
′ as in Box 3.Box 3:Group rekeying for member leave.
Assume that a subsetL
m of current group C
n is composed of m leaving members in
the group and does not include the group masterM
s.
Step  1. M
s selects random k
′ in Z
q for new group key and computes key-locks with updated locker list.
M
s
⇒
C
n ∖ L
m: {
(
X
i
)
k
′
|
i
∈
[
1
,
n
]
∧
M
i
∉
L
m
,
i
≠
s
}The leaving nodes cannot learn the new group key because the broadcast message fromM
s does not contain any locker X
i for leaving members. Note that the set L
m for the leaving node does not include the master. Leaving of the master requires ‘delegation’ during which the master forwards locker list X
L
C for group C
n to new group master(
M
s
′
) as follows:
(7)
M
s
⟶
M
s
′
:
X
L
C
=
{
X
j
∣
M
j
∈
C
n
,
j
≠
s
}
.
The delegation can be used for another case where the master wishes to finish its master’s role for a reason such as network topology change or resource exhaustion; that is, the master turns to a group member not leaving the group. In this case, the delegation message includes the former master’s locker generated with new selected secret x
s as follows:
(8)
M
s
⟶
M
s
′
:
X
L
C
=
{
X
j
∣
M
j
∈
C
n
,
x
s
≠
k
,
x
s
≠
k
′
}
.When group members detect unexpected disconnection from the master, they restart group key initialization with new master selection. At the worst case, members can suffer from frequent connection failure with the master. In this case, the first protocol should be slightly modified to make all of group members have the locker list and any member be the group master to proceed Box3. For instance, a general member at the first step of Box 1 broadcasts its locker to the group as follows:
(9)
M
i
⟹
C
n
:
X
i
(
i
∈
[
1
,
n
]
,
i
≠
s
)
.
The group members continue secure communication with a fresh group key obtained through group rekeying. We provide formal security proofs in Section 5.


## 3.4. Group Rekeying for Group Merging and Partition

There are two ways to integrate two groups into one group completely:individual join andgroup join. The former is that members of a group join another group individually. It is similar to the mass joining process, saving that the joining master should generate his lock-secret, x
s, and locker, g
x
s. The latter way is that a group is absorbed into the other group via delegation process between both group masters.Let two groups be mergedC
n
=
{
M
1
,
M
2
,
…
,
M
n
} and R
m
=
{
M
1
,
M
2
,
…
,
M
m
} (n
≥
m). The master M
s of C
n survives after group merging, while the master M
s
′ of R
m becomes a member of the merged group. Smaller group members (∈
R
m) become a member of C
n
+
m; that is, C
n
+
m
=
{
M
1
,
M
2
,
…
,
M
n
,
M
n
+
1
,
…
,
M
n
+
m
} and M
s
∈
C
n after group merging. Group merging process runs with delegation (in the first round) as in Box 4. Figure 2 represents an instance for a merging process for a current group C
4 and a merged group R
3. In Figure 2, the number in a circle indicates members’ index (such as by a joined order). Before they are merged, the number of the current group C is four including the group master (i.e., n
=
4, C
4) and the number of members of joining group is three (i.e., m
=
3, R
3). To be merged, the master of R
3 sends the master of C
4 the locker list X
L
R for M
1 and M
2. Note that the master M
s of R
m must forward its locker after changing its own secret because it was used as the former group key. The master of C
4 becomes the master for the merged group. It updates X
L
C and generates key-locks X
L
C
k with a new selected random k.Box 4:Group merging.
Assume that a groupR
m is merged into a group C
n where n
≥
m, and the merged
groupC
n
+
m = C
n
∪
R
m. M
s
′ is the master of R
m and M
s is the master of C
n.
Step  1. M
s
′ selects a random number x
s
′ in Z
q, computes X
s
′= g
x
s
′mod p, and updates
the locker list intoX
L
R= {
X
1, X
2
,
…, X
m
}
∪
X
s
′.
(delegation) M
s
′ → M
s: X
L
R
Step  2. M
s selects random k
′ in Z
q for new group key and computes key-locks with updated locker list.
M
s
⇒
C
n
+
m: {
(
X
i
)
k
′
|
i
∈
[
1, n
+
m
]
,
i
≠
s
}Group merging process: (a) when groupsC
4 and R
3 are merged,R’s master sends the locker list of R toC’s master and (b) after groups are merged,C’s master becomes the master for merged group and broadcasts the key-locks for new group key to all of the members.
(a)
(b)As shown in Figure3, the current group will be divided into two groups. When the number of left members is m, the current group will have (n
-
m) members after the partition process. Group partition requires one more master M
s
′ for a separated subgroup P
m
⊂
C
n (M
s
∉
P
m). Group partition process can be easily conducted through delegation, from the master M
s of group C
n to the fresh master M
s
′ of subgroup P
m. The divided groups perform a group key initial phase after the delegation process, as in Box 5.Box 5:Group partition.
Assume that a current groupC
n is partitioned into two groups, P
m (⊂
C
n) and C
n
-
m (=C
n ∖ P
m).
The master ofR
m is M
s
′ and the master of C
n is M
s (∉
P
m)
Step  1. M
s generate X
L
P = {
X
j
|
M
j
∈
P
m
,
j
≠
s
} from X
L
C.
(delegation) M
s → M
s
′: X
L
P
Step  2. M
s and M
s
′ select random k
′, k
′
′ in Z
q respectively and compute key-locks with their locker list.
M
s
⇒
C
n
-
m: {
(
X
i
)
k
′
|
i
∈
[1, n
]
∧
M
i
∉
P
m, i
≠
s
}
M
s
′
⇒
P
m: {
(
X
j
)
k
′
′
|
M
j
∈
P
m, j
≠
s
}Group partition process: (a) when groupC
7 is partitioned into two groups (new group P
3), the master of the original group sendsP’s master the locker list of the new subgroup and (b) after the group is split, each group master broadcasts the key-locks for each new group key.
(a)
(b)


## 3.5. Implicit Key Authentication

For the secure key authentication, the messages sent from all members should be signed with a signature key. Hash-based signature such as message authentication code (MAC) is fairly efficient in terms of computation cost. However, it is too costly to share one-to-one pairwise keys between all of group members in advance.We assume that a member holds long-term private and public keys certified by a trusted certificate authority (CA). (Each member can use a different signature algorithm such as RSA-based signature algorithm, digital signature algorithm (DSA), and elliptic curve digital signature algorithm (ECDSA). Note that some of them do not provide message encryption; that is, it is used for message signing and verifying. We consider that DSA is better for our scheme since its public key includesg
x mod p.) The group members send to the master the signed messages with their own private key; for example, in the first step of Box 1, a member, M
i, sends to the master {
X
i
,
S
i
g
M
i
(
X
i
)
} which M
i signs for X
i with its private key. Note that this process runs one-time at initial phase or it can be precomputed with X
i.Members can obtain the group key securely by verifying the messages of the master with signature signed with the master’s private key. All of messages from the master come with a master-signed signature for the origin and integrity of a group key. For example, in the second step of Box1, the master broadcasts {
X
1
k
,
X
2
k
,
…
,
X
n
k
,
S
i
g
M
s
(
GK
)
}. The master produces a locked set for the group key using verified members’ locker. It implies that outsiders cannot recover the group key from the master’s messages.


## 4. Evaluation

We measure performance of the proposed scheme through communication and computation cost spent for all group members to complete group rekeying by membership change. Table1 shows summary of comparison with other DH-based key management protocols: CKD, GDH, BD, STR, and TGDH. In Table 1, n, m, and p denote the number of current group members, joining or merged-group members, and leaving or partitioned-group members, respectively. Therefore, m
=
1 or p
=
1 indicates the single-member event. For TGDH, the height of the key tree is denoted as h, and, for STR, s is denoted as the index of the sponsor, which helps other members to calculate group keys. Group merging is a case where a group of m members is merged into a group of n members (n
≥
m), and group partition is a case where a group of n members is divided into separate subgroups: (
1
) a group of p members and (
2
) a group of (n
-
p) members, where (n
-
p)≥
p. The costs for the group partition event include the costs for updating two subgroup keys. In computation costs, we consider concurrent execution in distributed nodes if it is possible. In CODH, we assume the master is selected by group-join order; the first master is M
1, and when M
1 leaves the group, M
2 becomes the next master.Table 1
Communication and computation costs.
Rounds
Messages
Exponentiations
Signatures
Verifications
GDH
Join, merge
m + 3
n + 2m + 1
n + 2m + 1
m + 3
n + 2m + 1
Leave
1
1
n
-
p
1
1
Partition
2
p + 1
n
-
p
2
p
Master leave
2
n
-
1
n
-
1
2
n
-
1
STR
Join
3
m + 2
3m
2
m + 2
Leave
1
1
3
(
n
-
p
)
-
2
s
-
1
1
1
Merge
3
3
3
m
-
1
2
3
Partition
2
3
3
(
n
-
p
)
-
2
s
-
1
2
3
TGDH
Join, merge
2
3
3
h
-
3
2
3
Leave, partition
h
2h
3
h
h
h
BD
Join, merge
2
2n + 2m
3
2
2
n
+
2
m
-
2
Leave
2
2
n
-
2
p
3
2
2
n
-
2
p
-
2
Partition
2
2n
3
2
2
n
-
2
p
-
2
CKD
Join, merge
3
m + 2
n + 2m
3
m + 2
Leave
1
1
n
-
p
1
1
Partition
3
p + 2
max
⁡
(
n
-
p, 2
p
-
1
)
3
4
Master leave
3
n
2
n
-
3
3
n
CODH
Join
2
m + 1
n + m + 1
2
m + 1
Leave
1
1
n
-
p
1
1
Merge
2
2
n
+
m
2
2
Partition
2
3
n
-
p
2
2
Master leave
2
2
n
-
1
2
2CKD distributes the group key in a similar way with our protocol. Its communication and computation costs are also similar to our protocol. However, the worst case of CKD is when the master leaves. It requires large costs for rekeying. On the other hand, in CODH, the rekeying cost for a leaving master is analogous to that for a leaving member due to efficient delegation or sharing of public locker list. GDH is operated through communication chain from the first node to the last node, and the last node becomes the master of the group. Steiner et al. presented three GDH protocols: GDH.1, 2, and 3. GDH.2 is the most efficient in communication whereas GDH.3 is the most efficient in computation cost among GDH.x. We select GDH.3 for comparison. As shown in Table 1, GDH has weaknesses in group merging and mass joining. BD employs a completely distributed way using broadcast messages. Without sponsors or controllers, all of members broadcast messages for updating the group key. Although it seems to be fairly efficient in computation cost, there are hidden costs for multiplications. In addition, it requires a large communication cost compared to other protocols. STR and TGDH are tree-based key agreement protocols. They use different tree structures for key management. STR, especially, uses the extremely unbalanced tree structure. Accordingly, the performance of STR depends on the location of the sponsors. In TGDH, the costs depend on the height of the resulting key tree and locations of joining or leaving members in the tree. We provide the worst case cost for TGDH.Most of the cost in CODH comes from the master node. A general node consumes only one communication, modular exponentiation, signature, and verification in all of group rekeying process. We summarize the costs for a general member and the group master in Table2. Although the exponentiation cost looks heavy in the master, its cost is insignificant. We conducted an experiment to measure computation delays for modular exponentiations. Table 3 shows the average delay of 10 experimental results for each. The first device has less CPU power than the second device. When modular prime p is 1024 bits long and n
≤
50, the computation delay is less than 1 s. The average delay of one exponentiation is less than 8 ms in the second device. Moreover, reducing communication cost is important for mobile devices because data communication consumes more energy than any other process. Therefore, our group key protocols can be efficiently applied in dynamic mobile networks.Table 2
Communication and computation costs for CODH member and master.
Send
Receive
Exponentiations
Signatures
Verifications
Generalmember
Join, merge
0
1
1
0
1
Leave, partition
0
1
1
0
1
Groupmaster
Join
1
m
n + m
1
1
Leave, partition
1
0
n
-
p
1
0
Merge
1
1
n + m
1
1Table 3
Computation delays on mobile devices (ms).
p = 1024-bit
p = 2048-bit
n
=
1
n
=
25
n
=
50
n
=
1
n
=
25
n
=
50
Exponentiation(1 GHz CPU, 512 MB RAM)
37
452.6
907.8
168.9
3385.4
6762.5
Exponentiation (2.26 GHz CPU, 2 GB RAM)
12.9
192.8
385.3
75.4
1458.8
2917.4


## 5. Security

Letp be a large prime number of the form 2
q
+
1 for a prime q in Z
p. Let G be a cyclic group of prime order q and let g be a generator of G; that is, G
=
〈
g
〉. The decisional Diffie-Hellman problem (DDH) is as follows: given (g, g
x, g
y, g
z), where x
,
y
,
z
∈
Z
q, decide whether z
=
x
y or a randomly chosen number. In particular, the security of our protocol is based on the divisible decisional Diffie-Hellman problem (DDDH), which is stronger assumption than the divisible computational Diffie-Hellman problem (DCDH).Definition 1.
The DCDH problem is as follows: given (g
,
g
x
,
g
y), where x
,
y
∈
Z
q, compute g
y
/
x.Definition 2.
The DDDH problem is as follows: given (g
,
g
x
,
g
y
,
g
z), where x
,
y
,
z
∈
Z
q, decide whether z
=
y
/
x or a randomly chosen number.The DDDH problem is weaker than DCDH, since if an adversary could solve the DCDH problem, he could solve the DDDH problem by computingg
x to decide g
z
=
g
y
/
x; thus the DDDH assumption is stronger than the DCDH assumption. Similarly, the DDH problem is weaker than the computational Diffie-Hellman problem (CDH), which is weaker than discrete logarithm problem (DL) [22]. We want to prove the security of our protocol under the DDH and DDDH assumptions.Theorem 3.
The DDDH problem is equivalent to the DDH problem.Proof.
Given the DDDH input (g
,
g
x
,
g
y
,
g
z), where z
=
y
/
x, one submits (g
,
g
x
,
g
z
,
g
y) to DDH to decide whether y
=
x
z or a randomly chosen number. Similarly, given the DDH input (g
,
g
x
,
g
y
,
g
z), where z
=
x
y, one submits (g
,
g
x
,
g
z
,
g
y) to DDDH to decide if y
=
z
/
x or a randomly chosen number.Therefore, we know that if there is no polynomial time algorithm to solve the DDH problem, it is hard to solve the DDDH problem.Theorem 4.
If the DDH problem is hard, it is hard to find a polynomial time algorithm to recover the group key from the proposed protocol; in other words, it provides group key secrecy against passive adversaries under the DDH assumption.Proof.
Letview(n
,
k) be public information for a group of n members to establish a group key g
k; thus it is a view of passive attackers,
(10)
v
i
e
w
(
n
,
k
)
:
=
(
g
x
1
,
g
x
1
k
,
g
x
2
,
g
x
2
k
,
…
,
g
x
n
,
g
x
n
k
)
.
Suppose we had an algorithmF that with significant probability succeeds to distinguish between (view(n
,
k), g
y), where y is a random number y
∈
Z
q, and (view(n
,
k), g
k) where g
k is the group key; that is, F
(
v
i
e
w
(
n
,
k
)
,
g
y
)
=
F
(
g
x
1
,
g
x
1
k
,
g
x
2
,
g
x
2
k
,
…
,
g
x
n
,
g
x
n
k
,
g
y
)
=
1, where y
=
k, otherwise, returns 0. Then we can query to F with inputview
(
n
-
1
,
k
)
=
(
g
x
1
,
g
x
1
k
,
g
x
2
,
g
x
2
k
,
…
,
g
x
n
-
1
,
g
x
n
-
1
k
) for n
-
1 members’ information and additional input (
(
g
x
i
)
r
,
(
g
x
i
k
)
r
) for a random number r
∈
Z
R
q, where 0
<
i
<
n, that is, F
(
v
i
e
w
(
n
-
1
,
k
)
,
g
x
i
r
,
g
x
i
k
r
,
g
y
). It follows that (
v
i
e
w
(
1
,
k
)
,
g
x
r
1
,
g
x
k
r
1
,
g
x
r
2
,
g
x
k
r
2
,
…
,
g
x
r
n
-
1
,
g
x
k
r
n
-
1
,
g
y
)
=
F
(
g
x
,
g
x
k
,
g
x
r
1
,
g
x
k
r
1
,
g
x
r
2
,
g
x
k
r
2
,
…
,
g
x
r
n
-
1
,
g
x
k
r
n
-
1
,
g
y
), where r
i
∈
Z
R
q for 0
<
i
<
n. Then F can solve the DDDH problem since it can decide whether y
=
x
k
/
x or a random number, given (
v
i
e
w
(
1
,
k
)
,
g
y
)
)
=
(
g
x
,
g
x
k
,
g
y
). It means that F can also solve the DDH problem by Theorem 3.Theorem 5.
The proposed scheme provides backward secrecy, forward secrecy, and key independence provided the DDH problem is intractable.Proof.
Whenever membership is changed or the group key is updated, the group controller alters its own secretk to k
′, where k
′ is an independently random number to k
∈
Z
q; it implies that it is impossible to find an algorithm F such that F
(
g
k
)
→
g
k
′ without knowledge of k and k
′. We assume that the secret values are uniformly distributed by a pseudorandom generator. Therefore, when the group key has been changed, an adversary must use new public information, v
i
e
w
(
n
,
k
′
)
=
(
g
x
1
,
g
x
1
k
′
,
g
x
2
,
g
x
2
k
′
,
…
,
g
x
n
,
g
x
n
k
′
), to recover the group key updated into g
k
′ and it depends on a solution to solve the DDH problem by Theorem 4. It follows that past members, future members, or adversaries who know a subset of previous group keys cannot learn the current group key, since the broadcast message from the master does not contain their locker X
i inview().Theorem 6.
The proposed scheme provides implicit key authentication under the security of certified public key.Proof.
A locker which the master obtains from group members is what a group member signs with its public key certified by a CA. Concretely, a lockerX
i is hashed by a one-way function such as SHA-2, and hash (X
i) is signed with M
i’s private key using a digital signature algorithm such as RSA, DSA, and ECDSA. Then, the locker is verified with the public key bound to M
i and certified by CA. If there is a locker of nonmember in the locker list of a group, it must be along with a forged signature. It means that the problem occurs in a hash collision attack or a rogue CA certificate [23]. Once all verified lockers are transferred to the master, any other nodes which are not a group member cannot recover the group key under the DDH assumption (Theorems 4 and 5).


## 6. Conclusion

In this paper, we propose a secure group key management protocol based on DH key agreement. The proposed key management requires only one data communication and one modular exponentiation at each member for any membership event. It shows prominent efficiency in renewing the group keys against dynamic group membership change, member join/leave and group merging/partition. We proved group key secrecy, backward/forward secrecy, key independence, and key authentication. No outsiders can learn the group key under the DDH assumption. We conclude that CODH can be adapted efficiently for multicast security in mobile networks.



---

*Source: 601625-2014-08-21.xml*