CHAT: Clustered hierarchical key management for wireless sensor networks using network topology

Abstract

For wireless sensor networks, key management is a challenging issue because of the limited node resources, network size, and diverse requirements, depending on the exact application. This work presents CHAT, a key management scheme based on the well-known logical key hierarchy class of protocols. CHAT exploits topological network information to reduce rekeying costs and tessellates the network into topological clusters, to further localize rekeyings, leading to greater rekeying cost reductions. A modification that adds a network key is also presented, aiming to provide a group communication scheme which still incurs a low rekeying cost.

Keywords

Wireless sensor networks key management hierarchy logical key hierarchy clusters topology security

Introduction

Key management¹ is one of the key components of network security. It comprises the procedures of establishment of keying relationships between the network nodes, as well as the maintenance thereof.

The application of secure communication, and particularly key management in wireless sensor networks (WSNs), leads to several challenges, which stem from the scale and limited computational and communication resources in these types of networks. There are several approaches to solve this issue, each supporting different types of communication models and network dynamicity and leading to different performance and security trade-offs.

Numerous key management protocols targeted toward WSNs have been designed, both symmetric and asymmetric.² The first ones generally have lower network and computational costs, but require some form of key pre-distribution. Key compromisation is an issue and needs special key revocation procedures to handle it. Conversely, asymmetric schemes impose higher costs, both in computation and communication, but no secrets need to be distributed or revoked between nodes. Trust, however, still needs to be addressed and is generally handled by a certificate authority (CA), or pre-distribution of network nodes’ public keys.

Key management schemes can be classified by the communication model they support; depending on how secrets are shared between the network nodes, different communication patterns can be natively supported. Some common classes include the star-type base station participation,³ random possibility for pairwise communication, such as in polynomial⁴ and probabilistic,⁵ or group communication,⁶ where nodes can, cryptography-wise, communicate directly with any peer. Some applications can be accommodated without a problem with simpler communication models, while others can be more demanding or unpredictable and might need the any-to-any pattern of the latter class.

Another requirement for subsystems used in WSNs is scalability.⁷ This, naturally, applies to key management, the procedures of which must, for some applications, be able to effectively applied on networks of hundreds or thousands of nodes. The difficulty of such implementations is further increased when combined with communication flow requirements, such as group communication where a network-wide key is used.

A group of schemes that scales well and supports group communication is the logical key hierarchy (LKH) class of key management schemes, which additionally supports dynamic network membership. It was initially introduced by Wong et al.⁸ and independently by Wallner et al.⁹ Variations and adaptations on the main scheme have been developed, targeted at mobile networks and WSNs in particular, such as Lazos and Poovendran,¹⁰ Pietro and Mancini,¹¹ Pietro et al.,¹² and Dini and Savino.¹³

Some works based on LKH aimed to minimize the number of messages¹⁴ or to find computation-wise optimal key structures,¹⁵ but the cost of multihop transmissions was not taken into account.

In many WSN usage scenarios, the network topology will be heavily multihop, something that affects the total transmissions incurred by the rekeying procedures. Depending on the mapping between key management structures and the actual network topology, the communication cost can vary greatly. This issue was explored by Lazos and Poovendran,¹⁰ in which the creation of location-aware structures was discussed, assuming the node position is known. For non-uniform, hierarchical networks, a topology-matching key management tree scheme is presented in Wang et al.¹⁶ Son et al.¹⁷ present a topological key hierarchy (TKH) approach where key hierarchies are constructed using their connection graph. The results presented show better performance than several LKH class techniques using randomly picked structures. Topology-aware LKH key (TALK)¹⁸ is an attempt to efficiently apply the LKH scheme on multihop networks in an efficient way, deciding on both the key server location and the hierarchical key structures, aiming to minimize network traffic. Another approach is by Cheikhrouhou et al.,¹⁹ where a topological approach is also followed; however, the focus is on relieving the group controller of costs by offloading key management responsibilities to almost the whole network, while also not taking advantage of multicast.

An interesting group-based approach is presented in Dini and Savino,²⁰ where partially overlapping groups, defined by the application layer, are used. This can have advantages both at the security and at the efficiency level, as rekeying material and procedures are contained within the relevant group, but with disadvantageous group overlap patterns, the rekeying cost can easily climb. Moreover, prior knowledge of the application layer grouping is needed, which, for some applications, could depend on having already established lower layers.

This work bases on and expands on TALK¹⁸ management and LKH⁸ schemes in general, providing a method to divide a network into clusters and apply LKH key management operations to each of them as needed. Dividing the network into clusters leads to significant reductions in rekeying cost, compared to schemes that use a network-wide key. The scheme is targeted at larger networks where the rekeying cost would naturally increase and applications that would demand mostly local traffic. A variation that adds a cross-cluster key is also presented, which incurs a larger, but still relatively low rekeying cost. This variation is targeted at smaller networks or applications that would demand excessive cross-cluster traffic.

The rest of the article is organized as follows: in “Previous work,” the building blocks for this work such as LKH and TALK are described. Section “CHAT” describes the basic scheme of CHAT, including network tessellation, key hierarchy design, and rekeying procedures. “CHAT with network key” presents a modification to the basic scheme, which makes use of a network key. “Distributed on-network CHAT configuration” gives algorithms for the distributed calculation of clusters. Our simulation setup and results are presented in “Simulation studies.” Finally, in “Conclusion,” we draw our conclusions.

Previous work

Secure communications with LKH

Due to the diversity of WSN applications, there are a large number of communication models that can be applied, tailored to each case. However, the model which allows the most flexibility at the application layer is to assume any node can wish to communicate with any other node, the so-called group communication model.⁶

For this model, when symmetric ciphers are used for encryption, a common traffic encryption key (TEK), shared between all network nodes, is generally used. Alternatives, such as probabilistic key distribution, exist, but they introduce considerable overhead to data transmissions, when no keying material is shared between the two communicating nodes.

A common requirement and feature of key management for WSNs is the ensurance of forward and backward secrecy.²¹ (Forward secrecy is the property of a system which states that knowledge of a particular communication key does not enable discovery of future keys for an adversary. Backward secrecy is held when knowledge of a particular key does not enable discovery of previous keys.) To ensure forward and backward secrecy, the TEK needs to be changed when nodes join or leave the group. Also, a periodic TEK refresh can be applied, reducing the amount of material encrypted with the same key.

Changing the TEK is an easy and low-cost task, as it can be achieved by simply multicasting the new TEK to current nodes. However, node kick operations pose a greater problem, as there is no simple and straightforward way to distribute a new TEK to all nodes but the leaving one and ensuring the latter cannot acquire it.

LKH^8,9 handles this problem using modeling network nodes as leaves in a tree (Figure 1). Key encryption keys (KEKs) $K_{i}$ are created for each internal tree node $C l_{i}$ . Each network node possesses all $K_{i}$ on its path to the tree root. The key associated with the root, $K_{0}$ , is thus shared among all nodes and can be used as a TEK (more accurately, it can be used as a seed to derive one). Each leaf $u_{j}$ (network node) also possesses a unique (unicast) KEK $K_{u_{j}}$ , shared with the key server.

Figure 1.

Logical key hierarchy—node kick example $(u_{7})$ .

For a node kick operation, it is apparent that all keying materials that the leaving node $u_{l}$ possesses are invalidated and must be replaced. These are the keys associated with the internal tree nodes $C l_{i}$ on the path from $u_{l}$ to the root. Refreshing is done in a bottom-up fashion. For each $C l_{i}$ that needs its $K_{i}$ refreshed, a $K'_{i}$ is calculated at the key server and distributed each of the subtrees rooted at Cl_i’s children, encrypted with its relevant $K_{j}$ (or $K_{u_{j}}$ if it is a single node). If a child $C l_{j}$ is on the path of $u_{l}$ to the root, its $K_{j}$ is exposed to $u_{l}$ but it has been already replaced by $K'_{j}$ , since the calculations are made bottom–up. Figure 1 gives a graphic representation of such an operation.

In the example of Figure 1, $u_{7}$ is to be kicked, so the keys $K_{0}$ , $K_{2}$ , and $K_{6}$ , which it possesses, must be replaced. The replacement of $K_{6}$ is performed by sending the new key $K'_{6}$ to all the children of $C l_{6}$ , encrypted with their respective keys, and excluding $u_{7}$ . Specifically, $K'_{6}$ is sent to $u_{6}$ , encrypted with $K_{u_{6}}$ . Subsequently, $K_{2}$ is replaced, by sending $K'_{2}$ to the two descendant groups, $C l_{5}$ and $C l_{6}$ , encrypted with $K_{5}$ and $K'_{6}$ , respectively. It should be noted that $u_{7}$ , not possessing $K'_{6}$ , cannot acquire the new key. Likewise, $K_{0}$ is replaced by creating $K'_{0}$ and sending it to groups $C l_{1}$ and $C l_{2}$ , encrypted with $K_{1}$ and $K'_{2}$ , respectively.

Node joins are simpler, in that the keys held by the current (before the join) nodes are not known to the new node, so messages containing the new keys can be simply sent encrypted with their respective current keys.

Rekeying authentication

An issue that comes up on the use of LKH on WSNs is that of authentication. The digital signatures used for authentication in the original work²² are practically unusable in WSNs, primarily because of their size. Other signature algorithms, particularly those based on elliptic curves,²³ have been shown to be viable on WSNs,²⁴ but not without a significant overhead to the node processors and network traffic. This, however, is bound to change, as mode powerful microcontroller units (MCUs) are being introduced, which even have hardware accelerated public key cryptography functions.²⁵ This will largely mitigate the processing overhead, but the network overhead is still non-trivial, for example, a signature length of 320 bits is needed for a security level of 80 bits.

We thus consider two options for authentication: the use of proper digital signatures for the authentication of the rekeying commands, particularly elliptic curve digital signature algorithm (ECDSA),²⁶ and the use of key chains, as described $S^{2} RP$ .¹³

In the latter, each key server does not generate independent random keys for each rekeying, but uses key chains, pre-calculated by the key server. Key chains are created by repeatedly applying a one-way hash function $H$ unto an initial random key $s$ . Assuming $N$ applications of the hash function, the sequence $s, H (s), H^{2} (s), \dots, H^{N} (s)$ is created, where $H^{i} (s)$ is the application of $i$ times $H$ on $s$ . The chain is revealed (distributed) in the reverse order, that is, if $K^{(i)}$ is the ith element of the chain (to be revealed), $K^{(i)} = H^{N - i} (s)$ . This allows the recipient that possesses the first element of the list to be able to authenticate all subsequent keys sent to it. In $S^{2} RP$ , all keys in the key tree of LKH are replaced by key chains, so rekeyings in the event of a node kick are performed by revealing the next keys of the appropriate key chains, in the fashion of the original LKH. Regarding the event of a node join, to preserve backward security, $S^{2} RP$ introduces the mixing of the tree keys with a new component, the join key. When a node join occurs, the join key is to be refreshed at each group node, by applying a hash function on the current one. This prevents the new node, which will only receive the new join key, from decrypting past communications, as it is infeasible to derive past join keys, and all communications are encrypted using a mix of a tree key and the join key. The join key refresh command itself is authenticated using another key chain, named the command key chain.

TALK

TALK is a method for generation of LKH key trees which exploits the network topology in order to reduce the network transmissions required for rekeying operations. The general idea is that network topology information is collected, which allows computation of various metrics, including an estimation of average and maximum rekeying costs, for each key server candidate. The metrics are combined in a fitness function, which is used to select the key server. Once the server is selected, key trees are constructed using a topological network tree rooted at it, and finally additional optimizations are made. It comprises two main steps: (a) the server selection and (b) the key trees formation and optimization.

TALK: key server selection

At the beginning of the key server selection step of TALK, a form of network discovery is performed, by means of flooding the network with route information packets. At the end of the discovery step, each key server candidate contains a partial representation of the network topology, which has the form of a tree, rooted to this candidate itself. Candidates use the discovered topology information to calculate each own cost metrics corresponding to rekeying operations with itself as the key server. The metrics include the maximum and average distance between itself and all other network nodes and maximum and average node kick rekeying costs, measured in number of transmissions, using a generated draft key tree. Fitness information is then exchanged, and the fittest candidate is selected as the key server.

TALK: key tree generation

The second part of TALK is the generation of the key trees, which takes place after the key server has been selected. The fittest candidate already has gathered topological information of the network and has generated a draft key tree. The key server processes the information further and applies various optimizations to the draft key tree. Optimizations are performed in parts of the tree, following two rules that were found to decrease the rekeying cost. They comprise removing superfluous internal tree nodes in chain-like parts of the tree and nesting leaves under additional nodes, where those are siblings to internal nodes. The result is the proper LKH tree used for rekeying operations, and keys are forwarded to network nodes as appropriate.

CHAT

Overview

CHAT is a key management scheme based on LKH and TALK. It also splits the network into (keying) clusters, aiming to further reduce the number of messages required for rekeying operations. As a first step, it uses the key server selection of the basic TALK approach. After that, more nodes are selected to work as end-cluster-heads (ECHs), using a novel algorithm which aims to spatially spread the cluster heads within the network and also place cluster heads in relevant spots, which will minimize rekeying transmissions. Each of the selected ECH subsequently creates its own TALK-based key tree, and a super-cluster (SC) is also constructed, having the original key server as its head and the rest of the ECHs as members. At the end of the procedure for the basic scheme, the network is divided into several clusters, dubbed the ECs, which share no keying information, and one SC, which comprises all ECHs. Non-ECHs nodes only contain keying material from a single cluster. Thus, for a node kick rekeying operation, it is only necessary to refresh keys within this cluster, and not the whole network, which is the case for the plain LKH.

Network and security assumptions

For every node of the network, unicast and broadcast capabilities are assumed, within a specified range. All nodes are assumed to have the same communication range, meaning all links are bidirectional.

The existence of an uncompromisable key master server is also assumed, with the capability of secure pairwise communication with all network nodes at network bootstrap.

CHAT: basic scheme

CHAT is based on splitting the topological network graph into local clusters. These clusters, dubbed the ECs, have some optional parametric overlap, while each node possesses keying material only for the clusters it belongs to. We call the basic case, without overlap, CHAT/basic.

Intra-cluster communication is simple; as the cluster is essentially an LKH network, there is a key shared between all its nodes, the EC_iTK (for cluster $i$ ).

For inter-cluster communication, an additional cluster is formed, comprising all ECHs, dubbed the SC. The message is routed initially to the ECHs of the source cluster, which forwards it to the destination cluster’s ECH.

For example, on the network of Figure 2, if node 28, belonging to EC (headed by) 25, needs to send a message to node 46, belonging to EC 30, it routes the message through its ECH, node 25. Node 25, in turn, decrypts and reencrypts the packet, using $E C_{25} TK$ and SCTK, respectively. The packet is forwarded through the network, reaching node 30. The latter applies the same procedure, decrypting the packet with SCTK and encrypting it again with $E C_{30} TK$ , before it forwards it to node 46. The complete packet route is shown in Figure 3.

Figure 2.

Network example with clusters.

Figure 3.

CHAT/basic inter-cluster data transfer.

These structures are created as follows: first, ECHs are selected, using TALK fitness data and topological criteria. Then, nodes are assigned to ECs with an algorithm that aims to achieve high cluster locality.

Selection of cluster heads

As the first step in creating the CHAT keying structures, a set of ECHs is selected out of a set of candidates. The candidate set can be network-specific and depends on the node characteristics and network composition. It makes sense that in a completely homogeneous network, all nodes will be candidates, but in heterogeneous networks, where some nodes might, for example, be much more low-end, those will be excluded from the candidate set.

Let $S_{ECH}$ be the set of already selected ECHs, initially empty, and $C_{ECH}$ the set of candidate ECHs (CECHs). Let also $N_{ec}$ be a parameter corresponding to the target number of ECHs for the network. To select the first ECHs, the TALK key server selection procedure is executed. The selected node acts as a cluster head for one of the ECs, and also for the SC. The rest of the ECHs are selected using an iterative algorithm. The idea behind the selection is that ECHs should have as many nodes as possible in their neighborhood and also be spaced apart from each other. A parameter, MD, is introduced, signifying the network area that we examine around an ECH candidate. MD is heuristically defined as the average number of EC nodes, divided by the average node neighbors (ANs) in the network and rounded up

MD = ⌈ \frac{\frac{N}{N_{ec}}}{AN} ⌉

(1)

Intuitively, it is used as a rough prediction of the reach of the clusters (in hops), being the ratio of the average cluster size in nodes, to ANs, which is a metric of network density.

The selection algorithm selects candidates that are as close as possible to a large number of other nodes, which in turn are not close to already selected ECHs. The base formula used is the sum of $w \times (MD - D (i, j) + 1)$ for all nodes in the candidate i’s neighborhood (closer than MD), where $D (i, j)$ is the distance in hops from node $j$ . This satisfies the first criterion, yielding a large value for nodes one hop from it, less for nodes two hops from it, and so on, cutting off at MD hops. The second criterion is satisfied using a smaller weight $w$ for all $j$ nodes that are in the neighborhood of already selected ECHs. $w$ is equal to 1 if $j$ is more than MD from all already selected ECHs, and ε otherwise, the latter being a positive number, significantly less than 1. In our simulation studies, the value used for ε was 0.05

G_{i} = \sum_{k \in K} MD - D (i, k) + 1 + \sum_{l \in L} ε (MD - D (i, l) + 1)

(2)

where

\begin{matrix} K = {k \in N : D (i, k) \leq MD \\ and (D (k, j) > MD \forall j \in S_{ECH})} \end{matrix}

(3)

\begin{matrix} L = {l \in N : D (i, l) \leq MD \\ and (D (l, j) \leq MD \forall j \in S_{ECH})} \end{matrix}

(4)

0 < ε << 1

(5)

The algorithm for the ECH selection is given as pseudocode in Algorithm 1.

Algorithm 1. End-cluster head selection
$S_{ECH}$ = {TalkKeyServer} Num = 0 Reached = {TalkKeyServer} $Las t_{ECH}$ = TalkKeyServer $C_{ECH}$ = AllNodes - {KeyServer} while $Num < Target$ do for i in $C_{ECH}$ do if $D (i, Las t_{ECH}) < MD$ then $Reached + = {i}$ end if end for $Cur = None$ $G_{cur} = 0$ for i in $C_{ECH}$ do $G_{i} = 0$ for j in AllNodes do if $D (i, j) < MD$ then if $j \notin Reached$ then $G_{i} + = MD - D (i, j) + 1$ else $G_{i} + = 0.05 (MD - D (i, j) + 1)$ endif endif end for if $G_{i} > G_{cur}$ then $G_{cur} = G_{i}$ $Cur = i$ endif end for $C_{ECH} + = G_{cur}$ $Num + = 1$ end while

Algorithm 1. End-cluster head selection

S_{ECH}

= {TalkKeyServer}
Num = 0
Reached = {TalkKeyServer}

Las t_{ECH}

= TalkKeyServer

C_{ECH}

= AllNodes - {KeyServer}
while

Num < Target

do
for i in

C_{ECH}

do
if

D (i, Las t_{ECH}) < MD

then

Reached + = {i}

end if
end for

Cur = None

G_{cur} = 0

for i in

C_{ECH}

G_{i} = 0

for j in AllNodes do
if

D (i, j) < MD

then
if

j \notin Reached

then

G_{i} + = MD - D (i, j) + 1

else

G_{i} + = 0.05 (MD - D (i, j) + 1)

endif
endif
end for
if

G_{i} > G_{cur}

then

G_{cur} = G_{i}

Cur = i

endif
end for

C_{ECH} + = G_{cur}

Num + = 1

end while

An example of the progressive selection of ECHs is shown in Figure 4, where the red node is the SC-head (SCH), green nodes are already selected ECHs, and gray nodes are nodes that will count with a reduced weight in calculating suitability for future ECH candidates, due to them being close (closer than MD) to one of the already selected ECHs.

Figure 4.

ECH selection example $(N_{ec} = 8, MD = 3, ε = 0.05)$ : (a) Step 1, (b) Step 2, (c) Step 3, (d) Step 4, (e) Step 5, (f) Step 6, (g) Step 7, and (h) Step 8.

Node assignment to clusters

At the end of the previous step, a set of ECHs, $S_{ECH}$ , has been obtained, and an SCH has also been selected. Using these, nodes are assigned to ECs. The algorithm used aims to achieve high locality, and to that end, it assigns nodes to the cluster with the closest ECH. Depending on the traffic patterns expected for the application, an optional overlap can be introduced at the ECs, providing overhead-free communication for all local traffic, at the expense of some additional rekeying cost.

In more detail, the algorithm works as follows:

Let $N$ and CH be the sets of all network nodes and the selected ECHs, respectively. We then define $L$ as the nodes that remain unassigned at any time, which at the beginning of this procedure is $L = N - CH$ . Let also Cl be a dictionary of ECHs to the sets of EC nodes. Initially, each EC contains only its ECH, so $Cl [i] = {i} \forall i \in N$ .

The main algorithm is iterative, and similar in concept and function to Dijkstra’s shortest path algorithm.²⁷ In each iteration, every node in $L$ that is adjacent to one or more clusters is randomly assigned to one of them. The algorithm is also given in pseudocode in Algorithm 2.

Algorithm 2. CHAT node assignment to clusters
N = All network nodes CH = Cluster heads L = N - CH for i in CH do Cl[i] = { i } PrimAssigned[i] = i end for while L do for i in CH do New[i] = { } end for for i in L do for c in RandomOrder(CH) do if $MinDistance (Cl [c], i)$ = 1 then New[c] += i PrimAssigned[i] = c end if end for end for for (c,n) in New do Cl[c] +=n L -= n end for end while overlap section o = cluster overlap (hops) for i in N do for j in N do if $MinDistance (i, j) \leq o$ then $Cl [PrimAssigned [i]] + = j$ end if end for end for

Algorithm 2. CHAT node assignment to clusters

N = All network nodes
CH = Cluster heads
L = N - CH
for i in CH do
Cl[i] = { i }
PrimAssigned[i] = i
end for
while L do
for i in CH do
New[i] = { }
end for
for i in L do
for c in RandomOrder(CH) do
if

MinDistance (Cl [c], i)

= 1 then
New[c] += i
PrimAssigned[i] = c
end if
end for
end for
for (c,n) in New do
Cl[c] +=n
L -= n
end for
end while
*overlap section*
o = cluster overlap (hops)
for i in N do
for j in N do
if

MinDistance (i, j) \leq o

then

Cl [PrimAssigned [i]] + = j

end if
end for
end for

This algorithm guarantees that nodes are assigned to the closest ECH; similar to Dijkstra’s algorithm, this can be proved by induction. We define $MinMinD (i)$ as the least of the minimum distances between the node $i$ and each of the ECHs.

Hypothesis: After $n$ iterations, each node $i \in L$ that is adjacent to one or more nodes in $N - L$ has a $MinMinD (i)$ of $n + 1$ .

The trivial case is after Step 0, where $N - L$ is the set of ECHs. All nodes that are adjacent to ECHs do indeed have a MinMinD of 1, and conversely, all nodes that have a MinMinD of 1 must be neighbors of an ECH. Those nodes are all assigned to ECs in this step.

Assuming the hypothesis stands for step $n - 1$ , each node $i \in L$ , adjacent to $L - N$ , must have a MinMinD of $n$ . It is obvious that its MinMinD cannot be larger than $n$ . If it had a $MinMinD (i) < n (\leq n - 1)$ , it would have been picked in a previous step. Thus, its MinMinD must be $n$ . If $i$ is adjacent to more than one ECs, it has the same minimum distance for all of their ECHs. There also cannot exist a node $j$ with $MinMinD (j) = n$ that is not adjacent to $N - L$ , because its predecessor $k$ in the MinMinD path would have a $MinMinD (k) = n - 1$ , and thus would have been picked already.

An example is given in Figure 5, where the iterations of the assignment algorithm are shown, starting from the ECHs selected in the example of Figure 4. Each EC is shown with a different color.

Figure 5.

Node assignment to clusters: (a) Step 1, (b) Step 2, and (c) Step 3.

Overlap

Some overlap between clusters can be introduced, by extending the node assignment process. The scheme, when using overlap, is dubbed CHAT/overlap.

The reasons to use cluster overlap are as follows: (a) the increase in intra-cluster (overhead-free) traffic; by increasing the number of destination nodes, a source node shares an EC with. (b) More paths for routing inter-cluster packets, as potentially shorter source → source ECH → destination paths can be formed using additional ECHs, than using exclusively primary ECHs. (c) Since each node shares at least one EC with each neighbor, the absolute shortest path can be followed for every inter-cluster message, by simply using more decryption–reencryption cycles at EC borders, effectively trading energy used for encryption for communication energy.

A parameter $o$ is introduced, corresponding to the desired amount of EC overlap, in hops. When the primary node assignment is completed, an additional step is performed: For each node pair $i$ , $j$ that have a distance less or equal to $o$ , node $j$ is additionally assigned to i’s primary EC (the cluster $i$ was originally to).

Key trees’ creation

Having the ECHs and the EC members decided, each ECH can create the key trees for its cluster. This is done per the formation and optimization of the key tree steps, as described in TALK.

Rekeying procedures

At network bootstrap, each node $i$ is set up with an individual global key $I G_{i}$ that it shares with the SCH. This allows the SCH to unicast any new keying material to the network nodes, including the remaining initial keys. Additionally, each node receives all keying materials relevant to the function of the LKH or $S^{2} RP$ clusters it belongs to, according to the exact scheme that is chosen. Namely, for each cluster (a single EC for all nodes, and additionally the SC for ECH nodes), assuming signatures are used, the node receives all the relevant keys $K_{x}$ , depending on its place in the key tree, as well as its individual end key, $I E_{i}$ . If $S^{2} RP$ is used, each node receives the relevant current keys in the key tree $K_{x}$ , the current command key $K_{C}$ , join key $K_{J}$ , and its individual end key $I E_{i}$ . (Individual end keys are simply named individual keys in the prior works, or $K_{u_{x}}$ , mentioned in section “Secure communications with LKH.”“End” is added to distinguish between them and the individual global keys, which are not a part of LKH or $S^{2} RP$ .) IGs are used to transmit new keying material in the occasion of an ECH node kick, where all EC-specific keys are invalidated.

IGs and IEs are derived by mixing respective master keys and the node ids, as done in $S^{2} RP$ . This reduces storage cost for cluster heads, and transmission overhead, in the case of an ECH replacement, as will be described below.

Non-ECH node kick

When a non-ECH node $i$ , member of $E C_{k}$ , needs to be excluded from group communication, a normal LKH (or $S^{2} RP$ ) rekeying procedure takes place; all keys in the key tree of $E C_{K}$ that are known to $i$ are replaced.

ECH node kick

If the leaving node $i$ is the ECH of $E C_{k}$ , it is also a member of SC, and all keying materials that it possesses, from both clusters, are invalidated. A new ECH is picked from the remaining nodes in $E C_{k}$ , using the procedure that will be described below. The SCH creates a new master key for the EC’s nodes IEs. The id of the new ECH, along with the new IE, is sent to each of the member of $E C_{k}$ from the SCH via unicast, encrypted with its IG. The new ECH is also notified of its new role and also receives the master key for the IEs. The ECH then creates a key tree for the EC and unicasts the relevant keying material to each node, using its IE.

Selection of ECH node replacement

For use in the event of an ECH kick, an up-to-date list of suitable ECH replacements should be kept at SCH. When an ECH needs to be replaced, the new one is picked from the stored list. The procedure for selecting the most suitable ECH replacement in an EC can be run after every or few ECH membership changes. (Not necessarily at exactly the time of the rekeying procedure. It can be run later, to avoid network congestion.) Choosing to run the procedure less often trades ECH selection communication costs for the risk of ending up with a sub-optimal ECH.

The decision of which node will take the role of $E C_{k} H$ in the event of the former leaving the network is made at every change in membership of $E C_{k}$ . On such an event, each node in $E C_{k}$ calculates a modified version of its suitability, the reverse suitability (Gr), which is the sum of $E C_{k}$ node distances from itself

G r_{i} = \sum_{j \in E C_{k}} D (i, j)

(6)

All Gr values are gathered by the ECH, which sends the id of the node with the smallest Gr to the SCH.

Node join

The node is added to the EC of the ECH which is closest to it; if there is a tie between the closest ECHs, one is chosen at random. The new node’s position on the EC key tree is then decided: having a shortest path to the ECH discovered, the node is placed on the key tree as a sibling to its immediate parent on that path. The join procedure is performed as a plain node join operation, as described for the exact underlying protocol: if plain LKH is used, all keys on the node’s path to the root in the key tree are refreshed, and then the new ones are sent to the new node. If $S^{2} RP$ is used, the join key is refreshed, and then the relevant keying material is handed out to the node.

CHAT with network key

A possible variation in the CHAT scheme is CHAT/network, the inclusion of a global TEK, or global traffic encryption key (gTEK) to the scheme, mitigating the normal data traffic overhead, while potentially still being more efficient in rekeying, compared to previous work that makes use of a network key. Using plain LKH, the gTEK is generated by the key server and distributed to the SC and subsequently to the ECs. Using $S^{2} RP$ , the gTEK is derived from the root key of SC, $K_{0}^{SC}$ , and a separate join key, $K_{J}^{G}$ . Both are distributed to all network nodes.

Node kick

For every node kick operation that occurs in the network, all nodes must update the gTEK; first, the nodes that belong to the leaving node’s ECH need to perform a kick-node rekeying procedure. Then, if plain LKH is used, a new gTEK is generated by the SCH, broadcasted to the SC, and, following that, to all the ECs. If $S^{2} RP$ is used, the next $K_{0}^{SC}$ is broadcast to the whole network.

Node join

If plain LKH is used, a new gTEK is calculated and broadcast to the SC and the whole ECs afterward. The EC that the new node will be a part of also performs a normal node join operation. Using a refresh of $K_{J}^{G}$ is triggered first in SC, and then in all ECs (authenticating the join key refresh command with their own command keys), with the cluster receiving the new node also refreshing the local join key.

Distributed on-network CHAT configuration

The algorithms in sections “Selection of cluster heads” and “Node assignment to clusters” are centralized and would require knowledge of the whole network topology to be gathered at one point, and the ECs are calculated. Running the centralized algorithms is not infeasible, taking into account that this procedure would be performed only at network bootstrap, and perhaps rarely during the network lifetime, to restore rekeying performance when the network has severe changes in the topology.

However, we also offer distributed versions of these algorithms which do not require global network knowledge and can be run cooperatively by the network nodes.

Distributed selection of cluster heads

As mentioned in the centralized version, the first ECH/SCH is selected using the procedure described in TALK. During that step, each node acquires a subset of the network connection graph, in the form of a tree rooted to itself. This can be used for the calculation of the node’s gravity.

The SCH broadcasts a search ECH (SECH) message. The message contains its own id; the step number (2 as the first ECH is already selected) has a distance up to MD from itself (which from now on count with a reduced weight toward increasing the candidates’ gravity). If the SCH has a large enough neighborhood, the message is split into multiple packets.

All nodes receive the message, along with the blacklisted nodes, and can calculate their own gravity. Each ECH candidate sends back a CECH message which contains its gravity along with the list of nodes in its vicinity (up to MD hops). To reduce traffic congestion, messages are not forwarded by nodes if the gravity in the received message is less than the largest they already forwarded. After sufficient time has passed, the SCH declares chosen the node with the largest gravity received and sends a new SECH containing the new ECH id, the new step number, and the new reduced weight nodes. The process repeats until the desired number of ECHs is selected.

Distributed node assignment to ECs

The distributed node assignment algorithm is also performed in rounds. Each round is initiated by the SCH, which broadcasts a node assignment trigger (NAT) message to the network, including the round number. For the first step, the nodes that are one hop away from one or more ECHs select one and join its EC. Each node that joins an EC sends a node assigned to end-cluster (NAE) message both to the ECH and as a local broadcast. ECHs wait an appropriate amount of time to receive new assignments and report the new nodes to the SCH with a end-cluster membership update (ECMU) message. If no new nodes have been assigned to an EC, the ECMU is still sent, albeit empty.

At the end of the step, the ECHs know which new nodes joined their cluster, and all nodes that received one or more local broadcast NAEs know they are now adjacent to the respective ECs. When the SCH has received ECMU messages from all ECHs, it triggers the next round of assignments.

The procedure stops when all ECHs report no new nodes. (Practically, after a round passes with no new nodes for an EC, that EC will not receive any other nodes in general. The empty ECMU thus only needs to be sent once by each ECH, and the SCH, in turn, just counts the number of null ECMUs it has received throughout the process.)

Overlap

After the primary node assignment procedure is completed, the SCH broadcasts an NAT request, indicating it is for an overlap round, plus the overlap round number. Each node that is on a cluster border (has previously overheard a NAE broadcast regarding another EC) has kept information on the nearby cross-cluster nodes and transmits a NAE for each of them. Each ECH transmits an ECMU with the new nodes. This procedure ends after a predefined number of overlap rounds.

Simulation studies

Simulation setup

For the evaluation of our scheme, we developed our own simulation framework in Python. For our purposes, we have assumed an ideal wireless transmission medium, where 100% of a node’s transmissions are successful within a circle of a predefined radius $r_{TX}$ , which is the transmission range of the node.

For our evaluation studies, we create simulated networks; a network is created by randomly placing $n$ nodes of a communications range $r_{TX}$ , in a square area of side length $l$ . We also calculate the average neighbors AN per node for each created network. When investigating scheme behavior with regard to network scale, we keep a constant AN to isolate changes in scale from changes in density.

Finally, each presented point on the by-node-number plots is calculated by averaging multiple (10) simulation results.

Simulation results

Figure 6 shows the relation between area length (l), number of nodes (n), and AN, for node communication range set to 100.

Figure 6.

Relation between physical network size, number of nodes, and AN, $r_{TX} = 100$ .

We compare the performance of CHAT against other LKH-based schemes; “vanilla” random binary and quad LKH trees and TALK. In the random tree schemes, balanced key trees are created, and the leaves are randomly assigned to network nodes.

The average node kick costs for networks of various sizes can be seen in Figure 7, and with more detail in Figures 8 and 9. There are three CHAT schemes, “basic,”“overlap,” and “network,” and each is run with two different target ECH numbers: 8 and 21. CHAT/overlap refers to the basic scheme configured with cluster overlap, at one hop.

Figure 7.

Node kick rekeying costs.

Figure 8.

Node kick rekeying costs, CHAT/basic, and CHAT/overlap only.

Figure 9.

Node kick rekeying costs and CHAT/network only.

All schemes based on random LKH trees are shown to be considerably more costly than the topology-based TALK and CHAT schemes. Quad random trees seem to perform better than binary trees, as also seen in Zhu.¹⁵

The cost for CHAT/basic is very low—the lowest of all schemes—and increases very little with the network size. For 400 node networks, and using 21 ECHs, the average node kick cost was only 30 transmissions.

The use of cluster overlap (in CHAT/overlap) incurs some additional cost and has meaning on networks of more than 100 nodes, but for large enough networks, it offers more flexibility for overhead-free communication patterns, especially applications that make heavy use of local communications, having considerably less cost than using a network key.

CHAT/network, while more expensive than the other variations, is shown to improve on TALK, requiring 51%–60% of the transmissions for the networks of 60 nodes or more, and as little as 19.8% of the transmissions versus random quad trees, for the largest networks simulated; this while still offering completely overhead-free group communication.

Figures 10 and 11 show the overhead incurred for normal data traffic when using CHAT/basic and CHAT/overlap, when the traffic patterns are random, or to a single sink node, set as the SCH, accordingly.

Figure 10.

Overhead % for random traffic when using CHAT/basic and CHAT/overlap.

Figure 11.

Overhead % for traffic to the key server when using CHAT/basic and CHAT/overlap.

Using a larger number of clusters is beneficial for inter-cluster traffic, as the 21-cluster configuration is always better than the 8-cluster one; using 21 clusters leads to an overhead up to about 30% for random traffic and 20% for traffic to the sink. Using cluster overlap also decreases the traffic overhead significantly, having an overhead of up to 14% and 11%, for random and to-sink traffic, respectively. This is due to many nodes belonging to multiple clusters, increasing the number of overhead-free destinations, as well as having more solutions to route inter-cluster traffic, which potentially are less costly than using the nodes’ primary ECs.

Intra-cluster traffic is overhead-free in any case. However, when not using overlap, this traffic is constrained to regions around ECHs. This is sufficient when, for example, data from each area are aggregated, but do not accommodate applications that require each node to be able to communicate with all its neighbors.

Overlapping the clusters solves this problem, leading to much greater flexibility to the communication patterns efficiently supported. For applications that use local broadcasts or involve modifications to messages before propagation, using an overlap of one hop essentially brings traffic overhead down to zero. Moreover, even when the application requires long-distance multihop messages, without any intermediate modification, the communication overhead can be traded with reencryption overhead, as the absolute shortest paths can be followed, reencrypting where needed (every hop in worst case, practically less often).

Conclusion

In this work, we presented a key management scheme targeted at WSNs, and based on LKH, combined with topological clustering techniques focused on achieving low-cost rekeying. Three variations were presented, the latter two applicable to practically any application scenario, but each of them most effective in a particular application subset.

The first variation, CHAT/basic, is the basic scheme, with no network key, and without cluster overlap. This incurs the least rekeying cost and is recommended for applications having their main traffic within cluster boundaries, possibly aggregating data through cluster heads.

The second variation, CHAT/overlap, is the basic scheme, using cluster overlap. The rekeying cost for this variation is larger than the previous case, but still scales very well with the network size. The benefit is having much more flexibility in traffic, as each node can gather/send traffic overhead-free to any other node in its neighborhood. The communication overhead for longer multihop routes is much less than the non-overlapping approach, and it can even be completely traded with reencryption overhead, by simply following shortest path routing and reencrypting as often as necessary. This approach is recommended for large networks, if the application traffic patterns are not well matched to the non-overlapping clusters.

The third variation, CHAT/network, is the addition of a network key to the basic scheme. This approach naturally incurs greater communication cost for rekeying, but offers true group communication model capabilities. It is recommended for cases where long-range multihop traffic is expected to be common.

Footnotes

Appendix 1

Handling Editor: Michele Amoretti

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

References

Menezes

Oorschot

PCV

Vanstone

et al . Handbook of applied cryptography. Boca Raton, FL: CRC Press, 1997.

Zhang

Varadharajan

. Wireless sensor network key management survey and taxonomy. J Netw Comput Appl 2010; 33(2): 63–75.

Perrig

Szewczyk

Tygar

et al . Spins: security protocols for sensor networks. Wirel Netw 2002; 8(5): 521–534.

Liu

Ning

. Establishing pairwise keys in distributed sensor networks. In: Proceedings of the 10th ACM conference on computer and communications security CCS ’03, Washington, WA, 27–30 October 2003, pp.52–61. New York: ACM Press.

Eschenauer

Gligor

. A key-management scheme for distributed sensor networks. In: Proceedings of the 9th ACM conference on computer and communications security, Washington, WA, 18–27 November, pp.41–47. New York: ACM Press.

Sinopoli

Sharp

Schenato

et al . Distributed control applications within sensor networks. Proc IEEE 2003; 91(8): 1235–1246.

Zhang

Wang

. Key management in wireless sensor networks: development and challenges. Appl Mech Mater 2014; 665: 654–660.

Wong

Gouda

Lam

. Secure group communications using key graphs. IEEE/ACM T Network 2000; 8(1): 16–30.

Wallner

Harder

Agee

. Key management for multicast: issues and architectures (informational). RFC 262, June 1999. Reston, VA: The Internet Society, http://www.ietf.org/rfc/rfc2627.txt

10.

Lazos

Poovendran

. Energy-aware secure multicast communication in ad-hoc networks using geographic location information. In: IEEE international conference on acoustics, speech, and signal processing, Hong Kong, China, 6–10 April 2003, pp.201–204. New York: IEEE.

11.

Pietro

Mancini

. Efficient and secure keys management for wireless mobile communications. In: Proceedings of the Second ACM International Workshop on Principles of Mobile Computing, Toulouse, 30–31 October 2002, pp.66–73. New York: ACM Press.

12.

Pietro

Mancini

Law

et al . LKHW: a directed diffusion-based secure multicast scheme for wireless sensor networks. In: International Conference on Parallel Processing Workshops, Kaohsiung, Taiwan, 6–9 October 2003, pp.397–406. New York: IEEE.

13.

Dini

Savino

. S2rp: a secure and scalable rekeying protocol for wireless sensor networks. In: IEEE International Conference on Mobile Adhoc and Sensor Systems (MASS), Vancouver, 9–12 October 2006, pp.457–466.

14.

Lee

Son

Park

et al . Optimal level-homogeneous tree structure for logical key hierarchy. In: International Conference on Communication Systems Software and Middleware and Workshops, 2008. COMSWARE, Bangalore, India, 6–10 January 2008, pp.677–681. New York: IEEE.

15.

Zhu

. Optimizing the tree structure in secure multicast key management. IEEE Commun Lett 2005; 9(5): 477–479.

16.

Wang

Srinivasan

. Efficient key management for secure wireless multicast. In: Third international conference on convergence and hybrid information technology ICCIT ’08, Los Alamitos, CA, 11–13 November 2008, pp.1131–1136. New York: IEEE.

17.

Son

Lee

Seo

. Topological key hierarchy for energy-efficient group key management in wireless sensor networks. Wireless Pers Commun 2010; 52(2): 359–382.

18.

Tsitsipis

Tzes

Koubias

. TALK: topology aware LKH key management. Int J Distrib Sens N 2014; 10: 762194.

19.

Cheikhrouhou

Kouba

Dini

et al . Lnt: a logical neighbor tree secure group communication scheme for wireless sensor networks. Ad Hoc Netw 2012; 10(7): 1419–1444.

20.

Dini

Savino

. LARK: a lightweight authenticated rekeying scheme for clustered wireless sensor networks. ACM T Embed Comput S 2011; 10(4): 4111–4135.

21.

Kim

Perrig

Tsudik

. Simple and fault-tolerant key agreement for dynamic collaborative groups. In: Proceedings of the 7th ACM conference on computer and communications security (CCS ’00), Athens, 1–4 November 2000, pp.235–244. New York: ACM Press.

22.

Merkle

. A certified digital signature. In: Advances in cryptology — CRYPTO’ 89 proceedings, 9th annual international cryptology conference (ed Brassard

), Santa Barbara, CA, 20–24 August 1989, pp.218–238. Lecture Notes in Computer Science, Vol. 435. New York, NY: Springer.

23.

Johnson

Menezes

Vanstone

. The elliptic curve digital signature algorithm (ECDSA). Int J Inf Secur 2001; 1(1): 36–63.

24.

Gaubatz

Kaps

Ozturk

et al . State of the art in ultra-low power public key cryptography for wireless sensor networks. In: Proceedings of the Third IEEE International Conference On Pervasive Computing and Communications Workshops (PERCOM), Washington, WA, 8–12 March 2005, pp.146–150. New York: IEEE.

25.

Texas Instruments. CC2538 powerful wireless microcontroller system-on-chip for 2.4-GHz IEEE 802.15.4, 6LoWPAN, and ZigBee applications, 2015, http://www.ti.com/lit/ds/symlink/cc2538.pdf

26.

ANSI X9.62-2005. Public key cryptography for the financial services industry: the elliptic curve digital signature algorithm (ECDSA).

27.

Dijkstra

. A note on two problems in connexion with graphs. Numer Math 1959; 1(1): 269–271.