01-03-2013, 12:26 PM
A Group Key Management Protocol Based on Weight-Balanced 2-3 Tree for
Wireless Sensor Networks
A Group Key Management.pdf (Size: 414.27 KB / Downloads: 37)
Abstract
Multicast in Wireless Sensor Networks (WSNs) is an attractive mechanism for delivering data to multiple receivers as it
saves bandwidth. To guarantee the security of multicast, the group key is used to encrypt and decrypt the packages. However,
providing key management services in WSNs is complicated because sensor nodes possess limited resources of computing,
storage and communication. To address the balance between security and limited resources, a multicast group key
management protocol based on the weight-balanced 2-3 tree is proposed to generate, distribute, and update the group key
securely and efficiently. The decentralized group key management method is employed. A weight-balanced 2-3 key tree is
formed in every subgroup. Instead of using the conventional symmetric and non-symmetric encryption algorithms, the
Maximum Distance Separable (MDS) code technique is used to distribute the multicast key dynamically. During the key
updating, a series of adjustment rules are summarized to keep the tree weight-balanced, where pseudo-nodes as leaves are
added to reduce the computation and communication complexity. Compared with some other group key management
protocols, our scheme shows higher superiority on security and performance.
Introduction
In a WSN, multicast is a more efficient method of supporting group communication than unicast, which can
save bandwidth and energy largely. Because sensor nodes suffer from limited resources such as low computation
capability, small memory, limited energy resources and low bandwidth, multicast is widely used in sensor-based
applications such as environment monitoring, health-care monitoring, etc [1]. In general, multicast is far more
vulnerable than unicast because the transmission takes place over multiple network channels [6]. It is an important
issue to assure the security for the multicast communication in WSNs. Due to the resource constraints of sensor
nodes, security in WSNs imposes several challenges which are more complex than those in the other traditional
networks [2]. At the same time, the large number of sensor nodes employed to monitor critical parameters, the lack
of a specific network architecture or infrastructure, and the frequent topology changes due to the nodes mobility
also bring the challenges when we design the group key management protocol [3].
To overcome these issues, the first security challenge is to provide an effective method to protect information
through encryption, i.e., every message must be encrypted with the Group Key (GK). GK is known only by legal
group members. The second security challenge is that GK should be changed when the nodes join or leave the
group. Changing GK can not only prevent a new member from deciphering previous messages encrypted with the
old GK, but also prevent a leaving or expelled member from accessing the subsequent messages. The third security
challenge is to consider the balance between the security and the limited resources of sensors.
Related Work
Group key management creates, distributes and updates GK for the group members. The group key
management protocols can be divided into three main categories [8]: the centralized group key management
protocol, the distributed group key management protocol and the decentralized group key management protocol.
In the centralized group key management protocols [8, 9, 17, 18, 19], a BS is employed to control the whole
group as a group controller (GC). BS assigns a secret key to each group member and encrypts GK separately by
each member’s secret key when a new GK needs regenerating and distributing. Unfortunately, the centralized
group key management protocol does not suit the highly dynamic WSNs because frequent joining or leaving of
members brings great computation burden on GC and causes the single point of failure easily.
In order to overcome the shortcomings of the centralized group key management protocol, the distributed key
management protocol is proposed [10,11,12]. GC does not exist and group members are peer to peer, therefore GK
is generated by all the members. A group rekeying scheme (PCGR) for filtering false data was proposed [12],
whose basic idea is that the GK can be preloaded to the sensor nodes before deployment and neighbors can
collaborate to protect and appropriately use the preloaded keys. However, the authors do not address the group
rekeying problem when the group includes sensor nodes separated by multiple hops. A group key distribution via
local collaboration protocol (GKD) was proposed [10]. GKD is not only based on pre-distributed personal secrets
and broadcast information, but also requires local collaboration among sensor nodes. The network lifetime is
divided into time intervals known as sessions. At each session, BS broadcasts to the whole group in order to
initiate the group key updating.
Our Group Key Management Protocol
As noted in section 1, our group key management protocol for WSNs is based on weight-balanced 2-3 trees,
where the distributed group key management method is employed. BS is responsible for the whole tree. Instead of
using the conventional symmetric and non-symmetric encryption algorithms, MDS is employed to distribute the
multicast key dynamically. In this section we begin with a brief discussion of the group initialization. Next, we
introduce our protocol when membership changes such as join, leave, mergence, and partitions. The authentication
between nodes is beyond the scope of this paper. Our main aim is focus on how to manage the GK. For ease of
reference, the notations used in the protocol description are listed in Table 1.
Group Initialization
In our protocol, keys are arranged in a logic tree hierarchy. One-way functions are used to compute a tree of
keys [21]. Fig. 1 shows a key tree including sixteen members. BS K as GK is shared by all group members. The
keys in this tree are computed from the leaves to the root. Each internal node key can be used as a subgroup key
for all descendent members of the internal node. SN1 K , SN2 K and SN3 K are three subgroup keys. For example, SN1 K is
shared by members 1 u to 8 u .
A Sensor Node’s Joining
When a sensor node joins the network, GK is renewed to satisfy the backward secrecy. In order to reduce the
communication cost and keep the tree balanced, the joing sensor node should be inserted into the node whose
children are leaves with the minimum ancestor weight W(T) in the tree. For example, the rekeying process is
followed when a new user 17 u joins the group in Fig. 3.
A Sensor Node’s Leaving
GK must be renewed to satisfy the forward secrecy when a sensor node leaves. The position cases where the
removed node may locate are shown in Fig. 5. The deletion of a single node will cause imbalance in the tree. In
our protocol, the virtual nodes, i.e. pseudo-nodes will be filled into the positions of the tree leaves to keep the tree
weight-balanced and minimize the key update operations. The adjustment rules are summarized in Fig. 6 and Fig.
7. The adjustment rules for the bottom layer led by the imbalance are shown in Fig. 6, and the rules for the middle
layer are shown in Fig. 7. These rules can be applied recursively.
Mergence
When multiple sensor nodes join the tree controlled by i SN , i SN will construct these nodes into a weightbalanced
2-3 tree with the lowest tree weight. If the new tree weight is less than the old tree weight, the new tree
will be merged into the old tree. On the contrary, the old tree will be merged into the new tree. By experiments, we
can always find a node in the higher weight tree whose tree weight difference does not exceed three compared with
the smaller weight tree. The adjustment rules are listed in Fig. 9. If the tree weight in the upper layers becomes
imbalanced, the set of rules can be used in Fig. 7. The key update process has been mentioned in Section 3.2.
Partition
When multiple sensor nodes wants to leave the tree controlled by i SN , i SN will delete these nodes one by one.
The tree structure will be reconstructed after all nodes have left the group. The tree balance adjustments will be
from bottom to top until all the subtrees are balanced. On the one hand, if the node tree weight of its children
differs by less than 3, the adjustment rules will be classified into the bottom layer rules and the upper layer rules.
In the bottom layer, some rules are shown in Fig. 6 and the other rules are shown in Fig. 10. In the upper layer,
some rules are shown in Fig. 7 and the other rules are set in Fig. 11. On the other hand, if the node tree weight of
its children differs by more than 3, the rules are the same as those in Fig. 9.