An Efficient Key Management Scheme Based on ECC and AVL Tree for Large Scale Wireless Sensor Networks

Abstract

With the wide adoption of wireless sensor network (WSN), security problems emerge as a challenging issue because of the limited computational power and energy of the sensor nodes. Furthermore, the deployment of WSN in the hostile area with a large number of nodes also poses a threat. In this paper, we proposed a new efficient key management scheme based on Elliptic Curve Cryptography (ECC) and AVL tree for large scale WSNs. In our scheme the Elliptic Curve Paillier Encryption (ECPE) cryptography is adopted for communication and the AVL tree is used to store the neighbors' ID and public key. The number of keys used in our scheme is smaller than the proposed schemes as we store these keys using AVL tree to shorten the search time. Regular key updates are also designed to further improve the security of the whole network. Our scheme has a good scalability where the node addition and deletion are supported. Experimental results and analysis show our scheme can significantly reduce the energy consumed by the node and reduce the memory and computational overhead.

1. Introduction

Nowadays, wireless sensor networks (WSNs) have a critical application in military, medical, and industrial sectors. WSNs consist of a large number of tiny, cheap sensor nodes which are computational and energy-constrained. The security in WSNs is gaining importance as a large number of nodes may be exposed in hostile environments. If only one node is captured by the attacker, the whole network can be compromised.

Because of the wireless connectivity, the absence of the physical protection, and the unattended deployment, the security in WSNs becomes a challenging research hotspot. Key management protocols are the core of the secure communications [1–3]. The goal of the key management in WSNs is to establish secure links between neighbor sensors at network formation phase.

Basically, there are two architectures available for WSNs. One is a distributed flat architecture and the other is a hierarchical architecture. Considering the limitations of WSNs, the hierarchical network model has more operational advantages than the flat homogeneous model. One of the most famous hierarchical algorithms is Low-Energy Adaptive Clustering Hierarchy (LEACH) [4, 5], which was proposed by Chandrakasan to balance the energy consuming among nodes by randomly rotating cluster head memberships among all nodes.

In this paper, we propose an efficient key management scheme built on LEACH protocol. Furthermore, Elliptic Curve Paillier Encryption (ECPE) algorithm rather than general public key algorithms is adopted to achieve the key agreement with fewer keys and meet the needs of storage while catering to computing limited sensor nodes. We also use AVL tree (Georgy Adelson-Velsky and Evgenii Landis' tree, named after the inventors) [6], which is a self-balancing binary search tree, to store the nodes' ID and public keys which can greatly reduce the key search time and thus reduce the energy consumption. Combined with the energy-saving property of LEACH, our scheme can significantly reduce the energy consumed by the node and extend the network lifetime.

The contributions of this paper are as follows:

• (1)

We are the first to use the AVL tree to store the neighbors' ID and public keys; thus less search time and computing energy are consumed in large scale WSN.

(2)

A combined scheme including LEACH and ECPE is proposed in which fewer keys are needed to be stored in the node. Storage overhead is reduced for each sensor node and the network lifetime is extended.

(3)

Quantitative memory and computation overhead with a particular security analysis are provided. The obtained results show that our scheme can significantly reduce the energy consumed by the node and reduce the memory and computational overhead.

As for the rest of this paper, Section 2 introduces the related works; we give some preliminaries about ECPE algorithm and AVL tree in Section 3; Section 4 describes the scheme we proposed in detail; the performance analysis to the proposed scheme is elaborated in Section 5; finally this paper is concluded in Section 6.

2. Related Works

Key management problems in WSNs have been extensively studied in the literature and various solutions have been presented. In this work, we mainly classify these schemes into two categories: symmetric schemes and asymmetric ones. In symmetric key schemes, a preinstalled system-wide symmetric key or pairwise keys are usually stored on the devices. Symmetric key schemes are used in most of WSNs because they consume less computation time. Asymmetric key schemes adopt public key technology, such as Elliptic Curve Cryptography (ECC), to realize key distribution. Though public key technology was thought to be too computationally expensive for WSNs, recent studies [7, 8] have successfully implemented it in wireless sensor networks.

Since there are lots of symmetric key management schemes in WSNs, we will not give them a review. Useful surveys on symmetric key management schemes can be found in [3, 9, 10].

The key management schemes based on public key cryptography (PKC) are convenient for WSNs compared with those based on symmetric cryptographic algorithm. Usually the PKC schemes are considered resource-rich so that they are not suitable for WSN; but recently many researchers put their eyes on the adoption of PKC in WSN. Wandert et al. made a comparison between RSA (the Rivest-Shamir-Adleman cryptosystem, named after the inventors) and ECC in the nodes of WSNs and gave the conclusion that ECC behaves better on storage, computation, and communication overhead [11]. Ren et al. come up with several effective PKC based schemes upon the integration of several cryptographic techniques, including the Bloom filter, the partial message-recovery signature scheme, and the Merkle hash tree [12]. In terms of the elliptic curve discrete logarithm problem difficulty, they propose a key management scheme without secure channel by adopting the key threshold theory, but they did not take into account security issues confronted by each node when the share transfers in secret. A key management scheme without secure channel was proposed in [13], which is a combination of the discrete logarithm problem on elliptic curve and the threshold key theory, but has left out the security issues that arise in the exchange of the secret share between nodes. In [14], the network was divided into three levels: central authority (CA), server nodes (SN), and ordinary nodes (ON). SN generate session private/public keys for each node in the network, which makes them the most vulnerable part in the whole network when captured. Rajendiran et al. proposed a key predistribution technique using the ECC for WSNs. They choose elliptic curve points as the key pool to achieve better connectivity. But they still cannot resist the node capture attack [15]. Azarderakhsh et al. proposed a key management for heterogeneous sensor networks using a hybrid technique of public key and symmetric key cryptography, while they assume that the CHs cannot be captured and nodes know their own location [16]. In [17], VEGK is proposed for key management in heterogeneous cluster based WSNs using hybrid key management technique between public key cryptography ECC and pairwise symmetric keys.

Altogether, state-of-the-art public key cryptography schemes do not meet the strict limitation of resource-constrained sensor nodes, because a large computational overhead is introduced especially with large scale networks, which is the common case for WSNs. In this paper, we proposed a novel efficient key management scheme based on ECPE public key cryptography for WSNs. We also use AVL tree to store the ID and public key in our scheme so as to shorten the search time. Meanwhile, we design regular key updates to further improve the security of the network and our scheme also provides perfect scalability to allow nodes addition and removal.

It must be stated that in [18] the AVL tree is also used to store the ECC keys, but they store the keys in a whole WSN. In their method, each sensor node is associated with a leaf, and all keys located along the path from the leaf to the root of the AVL tree belong to that node. If two nodes need a shared key, they find the common ECC key which is at the highest level and closest to the leaves in the AVL tree. However, in our scheme, the AVL tree is used to store the neighbors' public keys in one node so as to reduce search time. When there are many neighbors in a large scale WSN, there is no need to generate the shared communication key in our scheme with the AVL tree available.

3. Preliminaries

3.1. LEACH

LEACH was proposed by Heinzelman et al. to balance the energy consumption among nodes by randomly rotating cluster head memberships among all nodes [19], and it can extend the network lifetime by 15%. The operation of LEACH is broken up into rounds. Every round of LEACH has two phases: one is the setup phase, where nodes elect CH, and the other is the steady state phase, where nodes communicate with their CHs. During the setup phase, node n chooses a random number between 0 and 1. If the number is less than the threshold $T(n)$ , the node becomes a cluster head for the current round. The threshold is set as

$$\begin{array}{cc}& T\left(n\right)=\left\{\begin{array}{cc}\frac{P}{\mathrm{1}-P\ast \left\{r\mathrm{mod}\left(\mathrm{1}/P\right)\right\}}\hfill & \text{if\hspace{0.17em}\hspace{0.17em}}n\in G\hfill \\ \mathrm{0}\hfill & \text{otherwise},\hfill \end{array}\right.\end{array}$$

(1)

where P is the desirable percentage to be CH, r is the current round, and G is a set of nodes that have not been selected as CH in previous rounds.

3.2. Elliptic Curve Paillier Encryption (ECPE)

ECPE [20] was first proposed by Paillier in 2000. It is a probabilistic encryption scheme employing elliptic curves over rings based on the use of twists of anomalous curves.

It is known that curves $E_p(a,b)$ over $F_p$ which have trace of Frobenius one (they are said to be anomalous) present the property that computing discrete logarithms on them is very easy [21]. Okamato extended this property to p-subgroup of $E_{p^{\mathrm{2}}}(a,b)$ so that the projection onto $F_p$ gives the twist of an anomalous curve.

The details of this cryptosystem are as follows.

Initialization. $n=pq$ is generated which is a product of two large primes, p and q, while $p\equiv q\equiv \mathrm{2}\hspace{0.17em}\left(\mathrm{mod}\hspace{0.17em}\mathrm{3}\right)$ . Choose an elliptic curve $E_{n^{\mathrm{2}}}(a,b)$ and a base point $G\in E_{n^{\mathrm{2}}}$ on this curve.

Public Key. Consider $PU=(n,E_{n^{\mathrm{2}}},G)$ .

Private Key. $s=\mathrm{lcm}(p+\mathrm{2},q+\mathrm{2})$ is the lowest common multiple of $p+2$ and $q+2$ .

Encryption. Suppose the plaintext is $M\in Z_n$ , pick random $r<n$ , and return the ciphertext: $C=(M+nr)·G$ .

Decryption. Compute $M={\Psi }_n(s·C)/{\Psi }_n(s·G)\mathrm{mod}n$ , where ${\Psi }_n(x,y)=-\left(x/y\right)\mathrm{mod}{n}^{\mathrm{2}}$ .

3.3. The AVL Tree

An AVL tree is a self-balancing binary search tree. For each node of the tree, the height difference of its subtrees is at most 1; therefore, it is also height-balanced. $O(\log n)$ time is needed for search, insertion, and deletion operations in both the average and worst cases.

Figure 1 shows an example of the AVL tree. The values of left subtree are always smaller than the ones of the root node, while the values of the right subtree are always larger than the ones of the root node. In order to find a particular element in the tree, for example, 28, we firstly compare the element with the root node 54. We turn left because 28 is smaller than 54, and then we find 28 larger than 17 so we turn right and find 28.

Figure 1

An example of the AVL tree.

4. The Proposed Scheme

Our scheme is based on the network model of LEACH which includes a base station and a large number of sensor nodes. The base station is assumed to be trusted and capable of computation and has storage ability. Special cluster heads are not needed in our model, which makes it more practical for WSNs. We assume the node in our network is capable of running the ECPE algorithm. The notations used in this paper are listed in “Notations.”

Our scheme can be divided into two phases: (1) network formation phase, where nodes elect CHs and generate the session key with each other, and (2) network steady state phase, where nodes communicate with each other with the session key. Node addition, node deletion, and key updating are also allowed during the second phase.

The details of our scheme are as follows.

4.1. Network Formation Phase

4.1.1. Key Predeployment

Following the rules of ECPE, firstly, base station chooses a large integer $Q=pq$ as a product of two odd primes, p and q, while $p\equiv q\equiv \mathrm{2}\hspace{0.17em}\left(\mathrm{mod}\hspace{0.17em}\mathrm{3}\right)$ . Then base station chooses a safe elliptic curve $E_{n^{\mathrm{2}}}$ and a point G on this curve. Afterwards base station calculates the parameters of ECPE for the nodes: the public key $Q=pq$ , the private key $S=\mathrm{lcm}(p+\mathrm{2},q+\mathrm{2})$ , the identity of the node ID, and an initial shared symmetric key $\mathrm{i}\text{key}$ . Finally, the base station stores these parameters, that is, $Q_i$ , $S_i$ , ${\text{ID}}_i$ , and $\text{ikey}$ , into the nodes.

4.1.2. Cluster Head Election

During this phase, all nodes are able to compete for the CHs for the current round using (1). The elected CHs send their own ID and public key to the base station to get registered. The base station makes an AVL tree list of all the CHs' public keys and IDs and sends this list to the nodes encrypted by the $\text{ikey}$ . This phase is shown as follows:

$$\begin{array}{cc}& {\text{CH}}_i\stackrel{{\text{ID}}_i\parallel Q_i}{\to }\text{BS},\\ \text{BS}\stackrel{E_{\text{ikey}}\left({\text{AVL}}_{\text{CH}}\right)}{\to }\text{All\hspace{0.17em}\hspace{0.17em}Nodes}.\end{array}$$

(2)

4.1.3. Cluster Formation

After the last step, each node gets the list of the CHs' ID and the public key. In order to form the clusters, each CH broadcasts its own ID and public key to its neighbors. The neighboring nodes can verify their identifiers according to the list received from the base station. Once a sensor node j decides to join cluster i, it replies its ID and public key to ${\text{CH}}_i$ . CH stores the nodes' ID and public key in a form of AVL tree. This phase is shown as follows:

$$\begin{array}{cc}& {\text{CH}}_i\stackrel{{\text{ID}}_i\parallel Q_i}{\to }\text{Neighbor\hspace{0.17em}\hspace{0.17em}Nodes},\\ {\text{Node}}_j\stackrel{E_{Q_i}\left({\text{ID}}_j\parallel Q_j\right)}{\to }{\text{CH}}_i.\end{array}$$

(3)

4.1.4. The AVL Tree Formation of Nodes' Information

After the clusters are formed, each node broadcasts its own ID and public key to its neighboring nodes. The node gathers its neighbors' IDs and public keys and then stores them in AVL tree. The creation of AVL tree is shown in Figure 2; the IDs of five nodes in this AVL tree are listed from small to large: ${\text{ID}}_{\mathrm{1}}<{\text{ID}}_{\mathrm{2}}<{\text{ID}}_{\mathrm{3}}<{\text{ID}}_{\mathrm{4}}<{\text{ID}}_{\mathrm{5}}$ . We put smaller nodes in left subtrees and larger nodes in right subtrees. Then the rotation operation of AVL tree is used to keep the balance so that the height difference of the subtrees is 1 at most. Consider

$$\begin{array}{cc}& {\text{Node}}_j\stackrel{E_{\text{ikey}}\left({\text{ID}}_j\parallel Q_j\right)}{\to }{\text{Node}}_{\text{neighbor}}.\end{array}$$

(4)

Figure 2

The AVL tree formation process.

4.1.5. The Session Key Agreement between Nodes

Suppose node A wants to communicate with node B; then node A needs to generate a session key with node B. Firstly, A queries B's public key in its AVL tree and then generates a random number sKey as the session key. A then encrypts sKey and the timestamp $T_1$ with its own private key and reencrypts the ciphertext plus A's public key and ID using B's public key. After B decrypts the message, B verifies the legitimacy of A's public key using its AVL tree. If authentication passed B uses A's public key to obtain the session key sKey and the timestamp and checks the timestamp $T_1$ to prevent the replay attack. B then encrypts sKey and the timestamp $T_2$ with its own private key and reencrypts them together with B's public key and ID using A's public key. A takes similar procedure to verify the identity of B. In this way, mutual authentication is finished and a session key is generated. The above process is shown as follows:

$$\begin{array}{cc}& {\text{Node}}_A\stackrel{E_{Q_B}\left(E_{S_A}\left(\text{sKey}\parallel T_{\mathrm{1}}\right)\parallel {\text{ID}}_A\parallel Q_A\right)}{\to }{\text{Node}}_B,\\ {\text{Node}}_B\stackrel{E_{Q_A}\left(E_{S_B}\left(\text{sKey}\parallel T_{\mathrm{2}}\right)\parallel {\text{ID}}_B\parallel Q_B\right)}{\to }{\text{Node}}_A.\end{array}$$

(5)

4.2. Network Steady State Phase

4.2.1. New Node Addition

It is essential to add new nodes due to the node energy depletion or capture. The new node has to be registered at BS before being added to the network and BS will store the current CH list to it. After the deployment of the new node, it sends a “join-in” request message including its ID and public key encrypted by its private key to the nearby CH. The CH will reencrypt the message with its own private key and then send it to BS. BS verifies the identity of the new node and replies with a confirming message to CH. Then CH broadcasts the new node's ID and public key to the nodes in its cluster. Now the new node can exchange public keys with its neighbor nodes and negotiate session keys with them. This above process is shown as follows:

$$\begin{array}{cc}& \text{BS}\stackrel{E_{Q_{\text{new}}}\left({\text{AVL}}_{\text{CH}}\right)}{\to }{\text{Node}}_{\text{new}},\\ {\text{Node}}_{\text{new}}\stackrel{E_{S_{\text{new}}}\left({\text{ID}}_{\text{new}}\parallel Q_{\text{new}}\right)}{\to }{\text{CH}}_i,\\ {\text{CH}}_i\stackrel{E_{S_i}\left(E_{S_{\text{new}}}\left({\text{ID}}_{\text{new}}\parallel Q_{\text{new}}\right)\right)}{\to }\text{BS},\\ \text{BS}\stackrel{E_{Q_i}\left(Y/N\right)}{\to }{\text{CH}}_i,\\ {\text{CH}}_i\stackrel{E_Q\left({\text{ID}}_{\text{new}}\parallel Q_{\text{new}}\right)}{\to }\text{ALL\hspace{0.17em}\hspace{0.17em}Nodes}.\end{array}$$

(6)

4.2.2. Node Deletion

If a sensor node does not send data for a long time, it will be considered as a dead node and will be removed from the network. CH broadcasts a message including the node's ID and public key to all nodes in this cluster. CH and the live node will update their AVL tree at the same time.

4.2.3. Key Update

In LEACH algorithm reclustering is needed after a certain period of time. New CH will be elected according to formula (1). With the establishment of the new clusters, the nodes will update the session key with its neighbors. Therefore, the energy consumption can be balanced, which will extend the lifetime of the whole network. Meanwhile security is also enhanced by the updated session key.

5. Performance Evaluation

5.1. Security Analysis

Prior to the deployment of sensor nodes in our scheme, a shared key is preset to encrypt the information exchanged during the network formation phase; therefore the adversary is unable to acquire the nodes' identity. What is more, each node mutually verifies the other's identity by AVL tree when they try to agree on a session key. Hence it is impossible for the adversary to launch identity related attacks, for instance, the Sybil attack. The usage of ECPE cryptography makes our network more secure than either symmetric cryptography or the traditional public key cryptography like RSA. Public key cryptography prevents plenty of frequent attacks on the network like selective forwarding, Flooding, and Sinkhole attack. In addition, signature verification can be achieved by the private key encryption. A timestamp is also adopted in our scheme to avoid the replay attack.

We use public key cryptography to generate a session key, which will be updated after a certain period of time, between two nodes. In our scheme, different pairs of nodes share different session keys. Even if the adversary captures a few sensor nodes he cannot get the session key between other nodes and cannot recover the keys used before, so that the forward secrecy of the network is ensured. On the contrary, in Rajendiran et al.'s scheme, if an adversary compromises one more node every time, he can obtain more information about the ECC key pool. When the number of captured nodes exceeds some threshold, the adversary will be able to recover the entire ECC key pool and thus compromise the whole network.

5.2. Memory Overhead

For the convenience of comparison on memory overhead, we follow the network size of Azarderakhsh et al.'s [16], 1000 nodes and 10 clusters every round, while each node has 31 neighbor nodes. As stated previously, a sensor node in our scheme only needs to store the public keys of its cluster head and neighbors, and the CH needs to store the nodes' public keys in its cluster. In El-Din et al.'s scheme, CH only stores its neighbors' keys, which makes it hard for the CH to manage the cluster. However, in Azarderakhsh et al.'s scheme, a node needs to store its neighbors' public keys plus the public keys of all CHs. In Rajendiran et al.'s scheme, they combined ECC with E-G scheme to distribute keys. The probability of a sensor node sharing one key with its neighbor is $P^{\prime }=\mathrm{1}-\left\{\left(p-r\right)!/\left[\left(p-\mathrm{2}\times r\right)!\times p^r\right]\right\}$ , where p is the size of key pool and r is the size of key chain. For Rajendiran et al.'s scheme, they need $p=5000$ and a chain of 120 keys to achieve a 95% connectivity, while 328 keys are needed to have 99.999% connectivity. Suppose the length of ECC key is 160 bits; Table 1 shows the superiority of our proposed scheme compared to those proposed by El-Din et al. [22], Azarderakhsh et al. [16], and Rajendiran et al. [15].

Table 1

Comparison of memory overhead.

	Rajendiran et al.'s	Azarderakhsh et al.'s	El-Din et al.'s	Ours
Storage needed for CH (bit)	52480	144480	8000	16000
Storage needed for sensor node (bit)	52480	16320	7040	5120

5.3. Computational Overhead

Our scheme uses along with El-Din et al.'s and Azarderakhsh et al.'s schemes, ECC based algorithm for encryption and decryption. Since ECC based encryption and decryption are the most energy consuming operations in the schemes, we make a comparison on the times of ECC based encryption and decryption to show the computational efficiency. In order to facilitate the comparison, we assume a small cluster with one cluster head (CH) and 10 normal nodes. We first compare the ECC operations in CH. In Azarderakhsh et al.'s scheme, the session key shared between two nodes is distributed by CH. For the 10 nodes cluster, there are altogether 45 keys between each two nodes; then CH encrypts the session key with the two node public keys, respectively, so it needs 90 ECC based encryption operations plus the 10 session keys between itself and the 10 nodes which means 100 ECC based encryption operations in total. In El-Din et al.'s scheme, CH needs 4 ECC based encryption and decryption operations with one node, which equals 400 ECC operations needed by CH for 10 nodes. However, in our scheme, only 1 ECC operation is needed for one node and 10 for 10 nodes. Then we compare the ECC operations for one normal node during the period it joins in the cluster and shares a session key with its neighbor. In Azarderakhsh et al.'s scheme, a node needs 3 ECC operations, while 5 are needed for the node in El-Din et al.'s scheme. In our scheme, the nodes need to authenticate each other through verifying signature, so the node needs 5 ECC operations too. Comparisons of the number of ECC based encryption and decryption operations executed by CH and nodes are shown in Table 2. We can see from the table that our scheme has superiority in overall computational overhead.

Table 2

Comparison of computational overhead (ECC operations).

	Azarderakhsh et al. (times)	El-Din et al. (times)	Ours (times)
Cluster head	100	40	10
Sensor node	3	5	5

5.4. Energy Consumption

Given the large number of nodes, WSNs usually take a long time and lot of energy to find the public key of a certain node. In our scheme, we use the AVL tree to store the data so that search time and the energy cost can also be significantly reduced. For instance, it needs $(n+\mathrm{1})/\mathrm{2}$ operations to search one node among n nodes in direct search; namely, the time complexity is $O(n)$ . It is only $O(\log n)$ when using AVL tree, while the schemes of Rajendiran et al., Azarderakhsh et al., and El-Din et al. are direct search. Figure 3 shows the comparison of search time between the direct search and the AVL tree. We also implement our proposed scheme in Microsoft Visual C++ 6.0. The operating system is Windows 7 Ultimate. The computer configuration is as follows: CPU, Intel Core i5 3.2 GHz; memory, 4 GB; hard disc, 500 GB. We test our AVL tree method in 3 scenarios: 100 nodes, 2000 nodes, and 10000 nodes. Ten searches are executed for every scenario and the average time cost is listed in Table 3. The result shows that, with the increasing nodes number, the AVL tree method demonstrates its superiority in search time. In other words, the energy consumption of searching in our scheme is much less than in the schemes using direct search method.

Table 3

Comparison of average search time.

Number of nodes	Ours (μs)	Rajendiran et al.'s, Azarderakhsh et al.'s, and El-Din et al.'s (μs)
100	259	4798
2000	271	4929
10000	296	5240

Figure 3

Search time comparison.

6. Conclusion

In this paper, an efficient key management scheme based on ECPE and AVL tree for large scale wireless sensor networks is proposed. Our scheme follows the network model of LEACH. We use ECPE to generate session keys between nodes since ECPE can achieve the same security as normal public key cryptography but with shorter keys, thus saving storage. In addition, our approach adopts AVL tree for storing public keys which can significantly reduce the search time in large scale WSN. Experimental results and theory analysis show the memory and computational overhead are reduced and the energy consumption is also cut down. Furthermore, our scheme has a good scalability that supports the node addition and deletion; key updates also support guaranteeing the security of WSN.