TinyKeyMan: Key Management for Sensor Networks
This package provides an implementation on TinyOS
for pairwise key establishment in wireless sensor networks using
the polynomial poolbased key predistribution scheme [1,
3]. It includes the implementation of the random subset assignment
scheme and the gridbased scheme. These
two schemes have a number of nice properties, including high probability
(or guarantee) to establish pairwise keys, tolerance of node captures,
and low communication and computation overhead.
For details see the related publications.
People
Platform
TinyOS
Software Package
TinyKeyMan.zip
This software can be invoked through the interfaces we provide. More
details are in Readme
Performance Results

Evaluating a tdegree polynomial is the basic operation
in the computation of a pairwise key in the polynomial poolbased
key predistribution schemes. We use an optimization technique
to reduce the cost of polynomial evaluation at sensor nodes. The
basic idea is to compute multiple pieces of key fragments over
some special finite fields F_{q'} (q'=
2^{8} + 1
or 2^{16}
+ 1), and concatenate these fragments into a regular
key. A nice property provided by such finite fields is that no
division is necessary for modular multiplication. The
code sizes for polynomial evaluation are given below:
Scheme

ROM
(bytes) 
RAM
(bytes) 
q'
= 2^{8}
+ 1 
288 
11 
q'
= 2^{16}
+ 1 
416 
20 
Using the
above key computation optimization, we implement the random subset
assignment scheme and the gridbased scheme with q'
= 2^{16} + 1,
since it can accommodate a larger number of nodes than the other
option with slightly additional computation overhead (see computational
cost). The code sizes for these two schemes are given below:
Scheme 
ROM
(bytes) 
RAM
(bytes) 
Random
Subset Assignment 
2824

106 
GridBased

1160 
67 

The following figure compares the cost of computing a 64bit
key using our optimized technique when q'=
2^{8} + 1
(8bit version) and 2^{16}
+ 1 (16bit version) with the cost of generating a 64bit
MAC (Message Authentication Code) on a 64bit long message using
a 64bit key with RC5 and SkipJack. It shows that this optimization
technique has advantages for a reasonable degree t of polynomial,
and the degree of polynomial is not necessary to be a large number,
which can be seen from the security analysis (see security).

Assume the probability p of sharing
a key between two nodes directly is 0.33. The first figure clearly
shows that before the number of compromised sensor nodes reaches
a certain point, the random subset assignment scheme (denoted
by RS in the figure) performs much better than both of the
other schemes. When the number of compromised nodes exceeds a
certain point, the other schemes have fewer compromised links
or keys than the random subset assignment scheme. Nevertheless,
under such circumstances, none of these schemes provide sufficient
security due to the large fraction of compromised links (over
60%). Thus, the random subset assignment scheme clearly has advantages
over the basic probabilistic scheme and the qcomposite
scheme.
To compare the security between different schemes,
we assume the network size is N=20,000, and each node can store
up to 200 keys or polynomial coefficients. In the gridbased scheme,
we have m=142 and p=0.014, where m is the
number of rows or columns in the grid. The four curves in the right
part of the following Figure show the fraction of compromised links
keys between noncompromised nodes as a function of the number of
compromised sensor nodes given p=0.014. We can see that the
random subset assignment scheme and the gridbased scheme perform
much better for less than 14,000 compromised nodes, while none of
the schemes can provide sufficient security for more than 14,000
compromised nodes because of the large fraction of compromised links
(over 60% compromised links).
Though p=0.014 is acceptable for the gridbased scheme, for
the basic probabilistic, the qcomposite, and the random subset
assignment schemes, p should be large enough to make sure the whole
network is fully connected. Assume p=0.33. This requires
about 42 neighbor nodes for each sensor node to make sure the whole
network with 20,000 nodes is connected with a high probability.
The three curves in the left part of the figure show the fraction
of compromised links between noncompromised nodes as a function
of the number of compromised sensor nodes for the above three schemes
when p=0.33. We can see that a small number of compromised
nodes reveal a large fraction of secrets in the network in these
schemes; however, the fraction of compromised links are much lower
in the gridbased scheme for the same number of compromised nodes.
Related Publications
[1] Donggang Liu, Peng Ning, "Establishing
Pairwise Keys in Distributed Sensor Networks," in Proceedings
of the 10th ACM Conference on Computer and Communications Security
(CCS '03), pages 5261, Washington D.C., October, 2003.
[2] Donggang Liu, Peng Ning, "LocationBased
Pairwise Key Establishments for Static Sensor Networks,"
in 2003 ACM Workshop on Security in Ad Hoc and Sensor Networks
(SASN '03), October 2003.
[3] Donggang Liu, Peng Ning, Rongfang Li, "Establishing Pairwise Keys in Distributed Sensor Networks", in ACM Transactions on Information and System Security, Vol. 8, No.1, pages 4177, February 2005. (More results than the conference version, including actual implementation and performance results on MICA2 motes.)
[4] Donggang Liu, Peng Ning, “Improving Key PreDistribution with Deployment Knowledge in Static Sensor Networks,” in ACM Transactions on Sensor Networks (TOSN), Vol. 1, No. 2, pages 204239, November 2005.
[5] Donggang Liu, Peng Ning, Wenliang Du, “GroupBased Key PreDistribution in Wireless Sensor Networks,” in Proceedings of 2005 ACM Workshop on Wireless Security (WiSe 2005), September 2005. (This paper, unlike the previous methods using deployment knowledge, removes the need for sensors' expected locations.)

