International Journal of Scientific & Engineering Research, Volume 3, Issue 5, May-2012 1

ISSN 2229-5518

ME-SMOCK: A Memory Efficient Public Key

Scheme for WSN

Divya Jegatheesan, Margret Johnson

Abstract— W ireless Sensor Networks (W SNs) are constructed by a set of small devices, called the sensor nodes, with sensing and wireless communication capabilities. They are widely used in many applications such as military, ecological, and health -related areas. WSNs have certain constraints like low computation capability, limited energy resources, s mall memory and poor resilience to physical capture. Also, they are mostly deployed in adverse or even in hostile environment. These constraints and issues make security in W SNs a challenge. So, efficient key distribution and management schemes are must. I n this paper, a novel key management scheme based on deployment knowledge has been proposed which adds memory efficiency to the existing public key based integrity scheme. Using this scheme memory efficiency can be improved by minimizing the total number of keys to be stored in each sensor node without altering the security.

Index Terms — Cryptography, Key Management, Key Predistribution, Resilience, W SN

——————————  ——————————

1 INTRODUCTION

dvances in wireless communication and electronics have resulted in the development of tiny sensor nodes which includes sensing, data processing, and communication components and hence it is possible to deploy Wireless Sensor Networks (WSNs) which represent a significant im- provement over traditional wired sensor networks [1]. WSNs are widely used in military applications, environmental appli- cations, health applications, home applications, commercial applications and so on. These applications require communi-

cation in WSN which must be highly secure.

To inhibit the adversary from intercepting the transmitted

information in the wireless communication channel and to pre-

vent the false information distribution in the network, authenti-

cation and confidentiality must be used to achieve network se-

curity, which require key management [2].

The key establishment technique for a secure application

must incorporate certain requirements like authenticity, confi-

dentiality, integrity, scalability, control resilience, flexibility,

fault-tolerance, memory efficiency, energy efficiency and self-

healing.

Cryptographic schemes can be either symmetric or asymmetric. Most of the key management schemes in WSNs are symmetric based. Inspite of perfect security,
asymmetric schemes result in more memory consumption and communication overhead. In this paper, a novel key management scheme is proposed which focuses on reduc- ing the memory usage and hence paving a way to use

————————————————

Divya Jegatheesan is currently pursuing masters degree program in com- puter science and engineering in Karunya University, India. E-mail: divs.it@gmail.com
Margert Johnson is currently working as Assistant Professor in computer science and engineering department of Karunya University, India. E-mail: margret_cse@karunya.edu
asymmetric cryptography in WSNs.
From the traditional asymmetric methods [3], [4], it is obvious that certificate based authentication leads to high overhead reducing the service availability. In contrast, self- contained public key management scheme will reduce communication overhead.

2 SMOCK - AN OVERVIEW

SMOCK is a self-contained public key management scheme which achieves zero communication overhead and high service availability [5]. According to this scheme certain number of schemes will be stored in the nodes by off-line trusted server.
SMOCK requires a pair of public and private keys to
encrypt and decrypt respectively. If node A needs to com-
municate node B, A will send an ID request to node B. De-
pending upon the ID that node A receives from node B, it
will encrypt the message using a pair of public key and B will decrypt using corresponding pair of private key. The private key pair used for encryption is related to ID and hence the public key pair to be used for encryption can be identified from the ID. This is illustrated in the Table 1.
The scenario of SMOCK will be as follows. This scheme was suggested for mobile ad-hoc networks. So it has been assumed that, each node has a unique pair of private keys and all public keys before deployment. For key allocation, following steps are followed: 1) Determine x and y 2) Allo- cation of distinct pair of private keys to the nodes. Here ‚x‛ represents the number of key pairs used by the network, in other words, public key pairs and ‚y‛ is the number of pri- vate keys in each node.

IJSER © 2012

http://www.ijser.org

The research paper published by IJSER journal is about ME-SMOCK: A Memory Efficient Public Key Scheme For WSN 2

ISSN 2229-5518

The values of x and y can be calculated using the algo- rithm which has been mentioned in [5]. It can be explained
1) Initialize I=2
2) While (C(I, ) <n))
3) I=I+1
4) x=I, y=
Here n represents the number of nodes. To illustrate, consider n=100, I=2, C(2,1)=2<100 and now I=3. The same steps are repeated. And at the eighth iteration the condition fails when I=9. So the calculated x and y values will be 9

and 4 respectively. Each node should hold ‘x+y’ keys i.e. for a network with 100 nodes only 13 keys must be stored in each node. This is much memory efficient when com- pared to traditional scheme which requies ‘n+1’ i.e 101 keys must be stored.
Fig. 2 shows the graph which demonstrates the memory efficiency of SMOCK. This graph is constructed by calculat- ing the number of keys to be stored by each node for dif- ferent network size from 10 to 200 using the steps ex- plained to calculate ‘x’ and ‘y’ and the same is compared with the traditional public key scheme.

NODE

1

Step1: ID REQUEST

Step 2: RESPONSE WITH ID say (1|3)

NODE

2

p p

Step 3: Enc (Enc (m, K1 ), K3 )

Fig. 1 SMOCK Scenario

Consider an example of a small group with 10 nodes. We need 5 distinct public-private key pairs to build pair- wise secure communication channels among 10 nodes,
which can be (K1r; K1p), (K2 ; K2 ), (K3 ; K3 ), (K4 ; K4 ), (K5 ;

Fig. 2 Comparison of Traditional Public Schemes with SMOCK in ac- cordance with memory usage

The above graph clearly shows that SMOCK is more memory efficient when compared to the traditional public scheme that requires ‘n+1’ keys to be stored.

3 ME - SMOCK

r p r p

r p r

K5p). Each node keeps 5 public keys and 2 private keys. The unique private key set allocation for each node for this sce- nario is shown in Table 1. The ID is used while communi- cation as shown in Fig. 1 where secure communication is done between 2 nodes.

Table 1

Private Key Allocation for 10 Nodes: An Example

In this paper we propose an enhanced SMOCK which is meant for increasing memory efficiency and hence it can be called as ME-SMOCK, Memory Efficient-SMOCK. In this section, we explain how ME-SMOCK can be effectively used in WSNs.

In WSNs the nodes are assumed to be static after deploy-

ment. So, deployment knowledge will be useful to know about

probable adjacent nodes which can help in key pre-

distribution. This results in high memory efficiency and low cost. If the adjacent sensors are known, only the keys required to communicate with those sensors are enough to be stored in each sensor node. This will obviously decrease the memory usage.

3.1 Applying Deployment Knowledge

The point where the sensor is supposed to be deployed is called as deployment point. The point at which the sensor ac- tually resides after deployment is called as resident point.

Let us assume that the network is divided into non- overlapping hexagonal cells. The centre of the cell (i, j) is said

IJSER © 2012

http://www.ijser.org

The research paper published by IJSER journal is about ME-SMOCK: A Memory Efficient Public Key Scheme For WSN 3

ISSN 2229-5518

to be the deployment point. The deployment knowledge can be obtained by using non-uniform distribution function like Gaussian pdf. With non-uniform distribution, there is higher probability that two adjacent sensors can belong to a same cell. Using two dimensional Cartesian coordinates [6], the pdf of resident points can be calculated as follows:

where
Here, (xi, yi) is the deployment point of the cell C(i,j) and is the standard deviation. The typical distribution of sensor nodes belonging to the cell C(1,2) is as shown in Fig 3.

Fig. 3 Deployment Model using pdf

3.2 ME-SMOCK: An Example Scenario

The memory efficiency of ME-SMOCK can be explained through an example scenario with a sample network model that can be formed using pdf as shown in Fig. 4

Fig. 4 Sample network model with 10 sensor nodes

Using deployment knowledge the possible adjacent neighbors can be figured out. Fig shows an example scena-
rio of sensor nodes that are deployed using pdf in a hex- agonal cell region. Using the scenario the memory usage is analysed only with 10 sensor nodes. But the same scheme suits for more number of sensor nodes also. It can be illu- strated as follows.
The example scenario shown is one among the probabili- ties that the network model can have when using pdf to imply deployment knowledge. Based on the number of adjacent nodes, the number of keys to be stored by a par- ticular node varies. As per SMOCK each node will encrypt using a pair of public keys. These public keys will be known from the ID they exchange. For example, node 8 has only one neighbor node i.e. node 4. So node 8 needs to store two public keys 1 and 5 (since node ID of node 4 is
1|5, refer table) and a pair of its own private key. So total- ly, only 4 keys must be stored in node 8. But in traditional SMOCK without deployment knowledge, 7 keys must be stored in node 8 (5 public keys and a pair of private keys). If node 2 is considered, it has three neighbors namely, 1, 4 and 7 with IDs 1|2, 1|5, 2|5 respectively. So three public keys 1, 2, 5 and two private keys are enough to be stored. The same calculation has been made and listed in Table 2.

Table 2

Number of Keys Calculated based on ME-SMOCK

8

7

6

5

4

3

2

1

0

1 2 3 4 5 6 7 8 9 10

Node Number

SMOCK ME-SMOCK

Fig. 5 Comparison of SMOCK with ME-SMOCK with respect to memory

IJSER © 2012

http://www.ijser.org

The research paper published by IJSER journal is about ME-SMOCK: A Memory Efficient Public Key Scheme For WSN 4

ISSN 2229-5518

usage

Fig. 5 shows the comparison graph of memory usage be- tween SMOCK and ME-SMOCK. Even if there are many sensor nodes say 100 per cell, the results stay good. Be- cause, there will be no necessity to store 100 public keys. Instead public keys of only the neighbor nodes are needed to be stored. ME-SMOCK will surely decrease the memory usage. The average number of keys to be stored by a net- work with n number of sensor nodes can be calculated us- ing the formula,
where n is the network size, AdjPubi is the number of pub- lic keys to be stored in a node i to communicate with the neighbor nodes and PrivKeyPairi is the private key pair to be owned by node i.
Also it is stated that attacks can never take place by simply knowing the node ID. This is because the node ID is related to the private key pair, say, node 1 with 1|2 as ID will have the private key pair (K1, K2). So an attacker who tries out to receive the message from a legitimate node by giving node 1’s ID as the response ID, attacker can receive the encrypted message by it cannot decrypt as the attacker will not hold the private key pair of node 1.
The evaluation made in [7] proves that, SMOCK pro-
vides scalability, control resilience and resilience to break-
ins with low communication overhead. So as an enhanc e-
ment, ME-SMOCK adds memory efficiency.

4 CONCLUSION

Memory efficiency is must in WSNs, as they comprise nodes with poor resources. Hence, public schemes are not popularly used in WSNs, though it offers perfect security. Taking this challenge, ME-SMOCK has been proposed in this paper based on public key scheme SMOCK, which was proposed for ad hoc networks. Implementing the same in WSNs must concen- trate more in memory consumption. To face this challenge, ME-SMOCK uses deployment knowledge to minimize the memory usage at the same time inheriting the features of SMOCK. The analysis made proves that ME-SMOCK can be efficiently used in WSNs by breaking the reluctance to the usage of public key schemes.

ACKNOWLEDGMENT

Our sincere thanks to the experts who have contributed to- wards the successful development of this paper.

REFERENCES

[1] I.F. Akyildiz, W. Su, Y. Sankarasubramaniam, E. Cayirci, ‚ A survey on sensor networks‛, IEEE Commun, vol.40, pp. 102-114, 2002.

[2] Yong Wang, Garhan Attebury, and Byrav Ramamurthy, ‚A survey of

security issues in wireless sensor networks‛, IEEE Commun, vol.8,

2nd quarter 2006.

[3] S.Kent and T.Polk, ‚Public-key infrastructure (x.509)(pkix)charter‛,

OnlineAvailable:http://www.ietf.org//html.charters/pkixcharter.html. [4] L. Zhou and Z. J. Haas, ‚Securing Ad Hoc Network‛, IEEE Network

Magazine, vol. 13, no. 6, pp. 24-30, Nov. 1999.

[5] S. Capkun, L. Buttyan, and J. P. Hubaux, ‚Self organized public-key management for mobile ad hoc networks,‛ IEEETrans. Mobile Compu- ting, vol. 2, no. 1, pp. 52-64, January -March 2003.

[6] W. Du et al., ‚A Key Management Scheme for Wireless Sensor Net- works using Deployment Knowledge,‛ Proc. IEEE INFOCOM, Hong Kong, pp. 586–97, 2004, (SHA1),‛ RFC 3174 (Informational), Sept. 2001.

[7] Wenbo He, Ying Huang, Ravishankar Sathyam, Klara Nahrstedt, and Whay C. Lee, ‚SMOCK: A Scalable method of cryptographic key management scheme for wireless ad hoc networks,‛ IEEE Transac- tions on Information Forensics and Security, vol. 4, no. 1, pp. 140- 150, March 2009.

IJSER © 2012

http://www.ijser.org