Recent advances in Micro-Electro-Mechanical Systems (MEMS) technology, wireless
communications and digital electronics have enabled the development of low-cost,
low-power, multifunctional sensor nodes that are small in size and communicate
untethered in short distances (Akyildiz et al., 2002).
The resulting Wireless Sensor Networks (WSNs) in recent years have obtained
more and more attention. Wireless sensor networks are used for a wide variety
of applications: ocean and wildlife monitoring, manufacturing, building safety
and earthquake monitoring and many military applications (Perrig
et al., 2004). When WSNs are deployed in a hostile environment, security
becomes extremely important as they are vulnerable to different types of malicious,
such as node capture (Conti et al., 2008; Taguea
and Poovendran, 2007), node replication attacks (Conti
et al., 2007), eavesdropping, traffic-analysis, etc. One of the most
vexing problems is the node capture attack. An adversary can capture a node
from the network as the first step for further different types of attacks. So,
in this study we focus on how to improve the resilience against node capture
attacks using secure pairwise key and guarantee the communication in sensor
nodes is secure.
Due to the constrained nature of the resources available on sensor nodes, traditional
wireless networking security solutions such as Public Key Cryptography (PKC)
and Key Distribution Center (KDC ) are not viable due to their processing requirements,
power consumption, speed and communications overhead (Michael
et al., 2009). Recent research suggests that symmetric secret key
pre-distribution is probably the only practical approach for establishing secure
channels among sensor nodes. Before deployment, the nodes can be preloaded with
some keys or secret material which can be used to calculate the pairwise key.
After deployment, the communicating nodes can calculate the pairwise key using
certain rules. As two extreme cases, one may use a global key to setup session
key between the sensor nodes, or assign each sensor node a unique random key
with each of the other nodes. However, the former is vulnerable to node capture
attack and the latter involves huge storage overhead on sensor nodes.
Eschenauer and Gligo (2002) first proposed Random Key
Predistribution Scheme (RKP) which is based on probability density and random
graph theory and is further improved by Chan et al.
(2003), Chan and Perrig (2005), by Du
et al. (2003, 2004) and by Liu
and Ning (2003, 2005).
Although these existing schemes provide viable solutions to the key pre-distribution
problem, they are vulnerable to node capture attacks. The capture of each node
will increase fraction of keys known to the adversary. When a certain number
of the nodes are captured, the adversary can obtain enough keys to compromise
a large number of links and make the network ineffective. Meanwhile, the key
connectivity is always related to the memory cost, the higher connectivity will
introduces huge storage overhead on sensor nodes.
In order to improve the resilience against node capture attacks we are the
first to present the KS scheme. In our proposal, the entire sensor network is
devided into several non-overlapping triangle cell and KS scheme is applied
to each pair of neighboring cells. After deployment, the communications between
neighboring cells are accomplished through pairwise key, which is computed based
on the Blom scheme. We study the resilience against node capture attacks, the
local connectivity and memory cost. Analysis and simulation results show our
scheme has a nice property: when large number of nodes are compromised, communications
between any other nodes in the same cell are still secure. Present results show
substantial improvement over (Eschenauer and Gligor, 2002;
Chan and Perrig, 2005).
The main contribution of our scheme:
||We are the first to present the KS scheme based on Blom scheme
||We integrate nodes deployment knowledge with predistribution
pairwise key and KS
||KS can remarkablely enhance node resilience against node capture
Although, like other schemes, such as (Yu and Guan. 2008),
also, the KS scheme uses nodes deployment knowledge. However, the KS scheme
and other scheme are different. In the KS scheme, nodes are devided into groups,
each of which is deployed in a cell, the communications between the neighbor
nodes in a cell are achieved through pairwise key pre-distributed using Blom
scheme. It will ensure the communications within a cell are absolutely safe.
So in will greatly enhance the resilience against node capture attack. In order
to ensure the connectivity of the network, sensor nodes in neighboring cells
should choose the secret materials from the same matrix. So, a node from its
neighbor cells can communicate with the relevant nodes in the cell securely
as long as it holds the secret key materials from the same matrix. Meanwhile,
each cell has the same number of neighboring cells, thus the memory cost in
a sensor node is not related to the connectivity.
Blom scheme can ensure that any pair of nodes in the network can create a unique shared key. Specific process is as follows:
A central authority first constructs a (λ+1)xN matrix G over a finite field GF(q), where, N is the total number of sensor node and q>N. G is known to all users. Then central authority constructs a (λ+1)x(λ+1) symmetric matrix D, where, D must be secret and can not be exposed to any node. An Nx(λ+1) matric A = (D·G)T is computed, where, A is called Blom matrix. Because matrix D is symmetric, so it is easy to see that the matrix AAG is also symmetric.
From Eq. 1, we can see Kij = Kji, where Kij is the element in row i and column j of matrix K. So, user pair(i, j) can use the Kij and Kji as the pairwise key. Specific means is as follows:
||The central authority assigns the i-th row of matrix G to
the node ni (i = 1...N)
||The central authority assigns the i-th column of matrix G
to the node ni (i = 1...N)
||The node ni and nj exchange the i-th
column and the j-th column, then they can compute Kij and Kji
using their private rows of A, respectively
Because the matrix G is public and is known to all users, so the information of matrix G can be delivered using plaintext during the phase of exchanging. In the Blom scheme, if any λ+1 columns of G are linearly independent, the scheme will have the desirable t-secure property. That is to say, in a network with N users the collusion of less than t + 1 users can not reveal any key held by other normal users.
The definition of key superset: A set S1 is a key superset of another key set S2 if every element in S2 is in S1. S1 may have elements which are not in S2.
We define a key subset S2 as a matrix D a node holds key subset S2 if the node stores the secret information generated from (D,G) which belongs to S2. Note that two nodes can calculate pairwise key if they hold the secret materials from the same matrix. Fig. 1 shows the model of key superset and the details of KS scheme.
PAIRWISE KEY ESTABLISHMENT BASED ON TRIANGLE CELL DEPLOYMENT MODEL
Attack model: Data in the process of sending and transmitting should ensure its confidentiality, integrity and freshness. As the broadcast characteristic of wireless communication, data in the process of transmitting may suffer from eavesdropping, tampering and replay.
|| Key superset model
Moreover, due to performance limitations of node itself, the attacker can easily capture any node and obtain the secret material in the node. When the number of captured nodes increases, the attacker may deduce and get more secret information, which will threaten the entire network security. Because the fact that nodes are compromised is impossible to avoid, we should reduce the impact from the compromised node or limit the impact within a small area as possible as we can, which will guarantee the security of entire network.
Network deployment model: In WSNs, as the node energy is limited, communication coverage is very small, thus usually only communicates with its neighboring nodes. According to the node deployment knowledge, the entire sensor network is devided into several non-overlapping triangle cells, Fig. 2 shows the congruent relationship between cell G0 and its three neighboring cells G1, G2 and G3. Accordingly, the sensor nodes are devided into the appropriate group, the groups of nodes can be deployed in the triangular cells, respectively. Thus the same group of nodes are more likely to be neighboring and establish pairwise key after deployment. According to the different deployment models, nodes may be subject to different distribution. In this paper we assume that the size of network is N, total of cells is G, each cell nodes are uniformly deployed.
Detail of key pre-distribution based on triangle cell deployment model: As shown in Fig. 1, each cell has public side with its three neighboring cells, thus each cell is among the three pairs of the cell. In the proposed scheme, KS scheme is applied to each pair of neighboring cells, if the neighboring cells store the secret key materials from the same matrix, they will calculate the pairwise key and establish a secure communication mechanism.
The proposed scheme includes four phases: key pre-distribution phase, pairwise key discovery phase, path-key establishment phase, node revocation and addition.
|| Network deployment model
Key pre-distribution scheme: The purpose of this phase is to assign the secret key materials to each node. Neighboring nodes can establish pairwise keys after deployment using the secret key materials:
Construct Public Matrix: We assume that the size of network is N and there are Nc nodes in each cell . Each node has a unique positive identifier ni for I = 1,2,...,N. The central authority constructs a (λ+1)xN matrix G like Eq. 2 over a finite field GF(q), where N is the size of network. Since, G is Vandermonde matrix and the node ID is used to be as the seed value of each column, thus each node only need to store a positive value which can be used to deduce the according column of matrix P to reduce the memory cost. Because the node ID is unique and it can be shown that any t+1 columns of G are linearly independent. Here, we choose λ+2Nc-2, the reason is to be stated later.
Construct key superset: First secret symmetric matrix D1, D2...,DS of size (λ+1)x(λ+1) are constructed randomly for each pair of neighboring cells in the entire network. We assum the total number of pairs of neighboring cells is NS and the set of key subset (Di, G) for i = 1,2...M is called key superset, where M = SxNS. Then matrix Ai = (Di, G)T of size Nx(λ+1) is computed for i = 1,2,...S, let Ai(j) represent the j-th of matrix Ai. We can see that each secret matrix Ai is used by 2Nc nodes. In order to guarantee the secrecy of each secret matrix Ai, the (2Nc-2)-secure Blom scheme should be used, that is to say λ should satisfy λ = 2Nc-2 and the size of Ai is (2Nc-1)x(2Nc-1).
Select key subset: Each node selects t(2≤t<s) secret key materials from the corresponding key sunset randomly . If node nj selects matrix Di, the i-th row of matrix Ai will be preloaded into node njs memory space. For example, in Fig. 1, the pair of (G0, G1) is assigned a key subset and is corresponding to the matrix Ai, node nj is in (G0, G1), thus the j-th row of Ai will be preloaded into the node njs memory space, so are the pair of (G0, G2) and (G0, G3).
Pairwise key discovery phase: After deployment, sensor nodes exchange their ID and the indices of key subset it carries . If two nodes share the secret key materials from the same matrix, they can calculate the shared key. Specifically, if nodes ni and nj store the i-th row and the j-th of matrix Ai, respectively, after exchanging their ID, node ni can deduce the j-th column of matrix P using the node njs ID, so is node nj. The pairwise key can be calculated as follows:
Path-key establishment phase: After exchanging their ID and the indices of the subset it carries, if two nodes have no common secret key materials from the same matrix, they need to find an intermediate neighbor sensor node that shares pairwise keys with both of them to help establish an indirect key. Specifically, we suppose that there are intermediate nodes n1,n1,...ni between the source node ns and destination node nd and each pair of adjacent nodes in the path has pairwise key. Source node ns broadcasts the indices of the subset it carries, which is forwarded through the intermediate nodes securely until it discovers a bridge sensor node that shares a pairwise key with the two sensor nodes, respectively. The source node and destination node can then establish pairwise key along the message broadcast path in reverse.
Node revocation and addition: When the sensor nodes are compromised or captured, it is very likely to expose the pairwise key and the key subset, If more than λ sensor nodes that share the secret key materials from the same matrix are compromised, the according secret matrix is no longer considered secure . Thus we should remove these secret matrix as well as the IDs of all sensor nodes that share the secret key materials from the same matrix. When the number of the compromised nodes increase, the network connectivity will be affected, so the new nodes should be added. Prior to the deployment of new nodes, the according secret material is preloaded into the new nodes memory. After deployment,they can quickly establish direct or indirect shared key with their neighbouring nodes.
Since, the ID of each node is unique, the pairwise key is also unique to the pair of neighboring nodes. This property is very useful for secure communications, because it may not only provide encryption services, but also provide authentication service. Meanwhile, the sensor nodes are devided into several cells, nodes from specific cell are more likely to be neighbors of nodes from the same cell and those from nearby cells. In the entire network, the property that the pairwise key which is established along the message broadcast path is very few not only improves the resilience to node capture attacks, but also reduces the communication cost and saves memory space.
Our scheme mainly discusses the following metrics:
Local connectivity: local connectivity is the probability that two nodes which are from the same cell or the neighbouring cells have at least one common secret key materials.
Memory cost: that is the memory requirement for storing key materials at one node.
Resilience against node captured: The additional key exposal probability that the keys stored in normal nodes are exposed should be as small as possible when some nodes are compromised is used to evaluate the resilience to the node capture attack.
Local connectivity: According to random graph theory, if a graph with N nodes is to achieve the given global connectivity Pc (Global connectivity is the ratio of the number of sensor nodes forming the largest isolated connected component in the final key graph G to the size of the whole network), the average degree of each node should satisfy Eq. 4:
For sensor network, the density is defined as:
where, N is the size of entire work, R is communication radiu of each node, A is the area of deployment region.
When the size of network is N, the communication radiu of each node is R, thus the average neighboring number of each node is D-1. Suppose the local connectivity between a node and its neighboring nodes is Plocal, for a given global connectivity Pc, Plocal should satisfy Eq. 6:
In (Du et al., 2003), for a given global connectivity
Pc in WSNs, the probability Pshare that two nodes have
at least one common secret key materials from the same matrix should satisfy
In our scheme, the entire sensor network is devided into several non-overlapping triangle cells and KS scheme is applied to each pair of neighboring cells. Let Pinner-cell presents the probility that any two nodes from the same cell share at least one common secret key materials from the same matrix, Pinter-cell presents the probility that any two nodes from neighbouring cells share at least one common secret key materials from the same matrix, Pactural presents the local connectivity in our scheme. Pinner-group and Pinter-cgroup can be denoted as follows:
For a given global connectivity Pc, we can select appropriate parameters(such
as t) to enable Pinter-cell≥Plocal, Pinner-cell≥Plocal
and Pactrual≥Plocal. Because Pactrual≥Pinner-cell,
only Pinter-cell≥Plocal can the global connectivity
Pc be guaranteed In E-G scheme (Eschenauer and
Gligor, 2002), each node randomly selects m keys from the key pool S, so
the local connectivity is:
In (Chan and Perrig, 2005), each node has shares key
so the local connectivity is:
In (Du et al., 2003), each node randomly selects
τ sub-space key from the multiple-space key ω in WSNs which is not
partitioned, so the local connectivity is:
In our proposal, the KS scheme is applied to each pair of adjacent cells and
we can select parameters such as S and T appropriately to achieve high local
connectivity. In E-G scheme, due to the memory limitation, the number of selected
keys should not be too large and thus the local connectivity which is related
to the memory cost may be low. In (Chan and Perrig, 2005),
if the size of whole network is large, the local connectivity will be more lower.
In (Du et al., 2003), because the multiple-space
key is applied to the entire network, it will be difficult to balance the security
and efficiency. We will use experiments to analyse comparatively in part 5.
Memory cost: After deployment, each node is preloaded with 3t rows secret
material which are from different matrix A and their neighborings ID,
so the memory cost of each node is 3t+D-1. However, the actual memory cost is
less than 3t+D-1, because after the establishment of pairwise keys, the unused
rows can be removed to save memory resources. In part 5, we will see that for
the given global connectivity Pc = 0.999, D = 5.76π and t should
satisfy t≥2. In E-G (Eschenauer and Gligo, 2002)
and (Du et al., 2003), in order to maintain the
probability that establishes direct shared key among any two nodes in a high
level, the number of selected sub-key and sub-space key should not be small.
For example, in E-G scheme, when the key pool S is 100000, only when the number
of selected key reach to 250 can the probability that any two nodes establish
direct share key equal to 0.5. Compared to our scheme, E-G scheme need more
memory and the local connectivity is low. Meanwhile, if the number of selected
sub-key or sub-space key is too large, although the high local connectivity
is maintained, it means that an attacker can obtain more key material by compromising
a smaller number of nodes, thus a good tradeoff between local connectivity and
security performance is difficult to satisfy. In Chan and
Perrig, 2005), the memory cost of each node is
where N is the size of entire network, we can see that as the size of network
increases, the space to store keys of each node also increases accordingly.
A merit of our scheme is that the memory cost is unrelated with local connectivity,
thus it is easy to achieve high level security. Besides, our scheme is scalable
in that the number of cells can increase while the memory cost of each node
is almost fixed.
Resilience against node capture: The additional key exposal probability that the keys stored in normal nodes are exposed should be as small as possible when some nodes are compromised is used to evaluate the resilience to the node capture attack. In our scheme, KS scheme is applied to each pair of neighboring cells, each pair of nodes select randomly a certain number of secret key materials from the key subset. As long as the number of captured nodes are less than λ(λ = 2Nc-2 ), the secrecy of the secret material in key subset will be guaranteed. That is to say even if the number of captured nodes equal to λ, the remaining two nodes can still communicate securely, which means the additional key exposal probability is zero. Thus, our scheme has perfect resilience to the node capture attack.
In E-G scheme (Eschenauer and Gligo, 2002), the additional
key exposal probability may be calculated as Eq. 14:
where, x is the number of captures nodes, m is the size of a selected key subset, S is the size of key pool.
In (Du et al., 2003), the additional key exposal
probability may be calculated as Eq. 15:
where each node has τ spaces from ω spaces and x is the number of captures nodes, t is the safe threshold value.
As shown in Eq. 14, if the parameters m and S are definite
value, the additional key exposal probability PC will increase with
the growth of the captured nodes number. In (Du et al.,
2003), if the number of captured nodes exceed the safe threshold value,
PC will increase rapidly. We will use experimental results to illustrate
the above analysis in part 5.
We use the setup in Table 1 for our simulation and numerical analysis.
Local connectivity: Based on Table 1 and Eq. 4, we can obtain:
According to the analysis of Section 4.1, for given global connectivity Pc, Pactrual should satisfy Eq. 17:
Figure 3 gives Pinter-group (sharing at least one common secret key materials from the same matrix) as a function of key subset. As shown in Fig. 3, for the given global connectivity Pc, when the key subset S equals to 10, if only t≥2, inequality Eq. 17 can be satisfied.
In E-G scheme, if the size of key pool S is 100000, the memory for storing key materials in each node is 200, ω = 9, τ = 2; S = 10, t = 2, Based on the equation in Section 4.1, we can obtain the results which is shown in Fig. 4.
As shown in Fig. 4, compared to other schemes, our scheme has very high local connectivity, which means each node can establish direct keys with almost all its neighbors, thus can save a lot of energy on the establishment of indirect keys along the message broadcast path. Dus scheme is used to the entire network and the selected sub-space key should not be too large, so the local connectivity which is related to the memory cost is low. The local connectivity in E-G scheme and Chans scheme is also related to the number of selected keys and the size of entire network respectively and it is difficult to balance the security and efficiency. The results commendably support our analysis in part 4 and objective of the paper.
|| Simulation setup
|| (Sharing at least one common secret key materials from the
same matrix) as a function of key subset
|| Local connectivity of different schemes
Resilience against node capture attacks: The additional key exposal probability is used to evaluate the resilience to the node capture attack. In our scheme, we obtain the (2Nc-2)-secure property in each pair of neighboring cells by setting λ = 2Nc-2, which means that even though up to (2Nc-2) nodes are captured the remaining two nodes in the neighboring cells can still communicate securely. Hence, in our proposal when an adversary captures some nodes, he/she only knows the secret key materials in the captured nodes but can not derive the keys stored in other normal nodes, which means the additional key exposal probability is zero. Thus, our scheme has perfect resilience to the node capture attack. the additional key exposal probability is zero, the results are stated in Fig. 5.
As shown in Fig. 5, compared to other schemes, our scheme has excellent resilience against node captured attacks. Because in our scheme, the entire network is devided into several non-overlapping triangle cells, KS scheme is applied to each pair of neighboring cells and the consequence of node capture attack is restricted within a small range, which can guarantee that the communication between sensor nodes is secure. Dus scheme has the property that when the number of captured nodes reach to a threshold value, the additional key exposal probability will increase rapidly. What is different with Dus scheme is that the additional key exposal probability in E-G scheme will increase with the number of captured nodes. The performance results again well support our analysis in part 4 and our design goal.
Several schemes have been proposed for use in WSNs, such as the use of elliptic-curvecryptography
(ECC), the use of group and keyed-hash Chain (Hussian et
al., 2009). Eschenauer and Gligo (2002) first
proposed Random Key Predistribution Scheme which is based on probability density
and random graph theory. Before deployment, each node is preloaded into a random
subset of key from a large key pool. Any two nodes in the communication range
can talk to each other only if they share a common key.
|| The additional key exposal probability as a function of fraction
of captured nodes
Chan et al. (2003) further improved the E-G
scheme and developed the q-composite key establishment scheme and random pairwise
key scheme, The difference between this scheme and the previous one is that
the q-composite scheme requires two nodes to find q (with q>1) keys in common
before establishing shared key, which improves the resilience of the network.
Liu and Ning (2003) developed a framework in which pairwise
keys are predistributed by using bivariate polynomials, Their scheme takes advantage
of expected node locations to improve the efficiency of establishing shared
key. Moreover, (Liu and Ning, 2005) used node deployment
knowledge to improve the local secure connectivity. Their approach assumes a
group-based deployment model, in which the entire network is devided into several
non-overlapping square cells and nodes are devided into groups, each of which
is deployed in a cell. Meanwhile, the depolyment knowledge and hierarchical
clustering algorithm are used to achieve a good performance in term of lifetime
and balance power consumption (Wei et al., 2007;
Xin et al., 2008). Du et
al. (2003) proposed a multiple-space key pre-distribution scheme which
is based on Blom scheme. This scheme exhibits a nice threshold property: when
the number of compromised nodes is less than the threshold, the probability
that communications between any additional nodes are compromised is close to
zero. Moreover, Du et al. (2003) proposed a novel
random key pre-distribution scheme that exploits deployment knowledge and avoids
unnecessary key assignments, which improves the performance (including connectivity,
memory usage and network resilience against node capture) of sensor networks.
Chan and Perrig (2005) proposed a Peer Intermediaries
for Key Establishment (PIKE), a class of key-establishment protocols that involves
using one or more sensor nodes as a trusted intermediary to facilitate key establishment.
Although the existing schemes can improve some these metrics, they have a common
weakness that they are vulnerable to node capture attacks.
In this study, we propose an efficient scheme against node capture attacks using secure pairwise key in wireless sensor networks. We utilize key superset scheme and the triangle cell deployment model to restrict the consequence of attacks within a small range, which greatly enhances the resilience against node capture attacks. We presented both the analytical and numerical results, compared to existing schemes, high local connectivity which is unrelated to memory cost is achieved and the resilience against node capture attacks outperforms others.
This study was partially or fully supported by National Basic Research Program of China (973 Program) under Grant No. 2006CB303000 (2006.9-2011.8, Hunan University), 2009CB326202 (2009.4-2011.8, Hunan University) and 2010CB334706 (2010.4-2013.3, Hunan University). Key Program of National Natural Science Foundation of China under Grant No. 60736016 (2008.1-2011.12, Hunan University). National Natural Science Foundation of China under Grant No.60873198 (2009.1-2011.12, Hunan University), 60973128 (2010.1-2012.12, Hunan University) and 60973113 (2010.1-2012.12, Hunan University).