TinyKeyMan: Key Management for Sensor Networks
This package provides an implementation on TinyOS
for pairwise key establishment in wireless sensor networks using
the polynomial pool-based key predistribution scheme [1,
3]. It includes the implementation of the random subset assignment
scheme and the grid-based 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.
This software can be invoked through the interfaces we provide. More
details are in Readme
Evaluating a t-degree polynomial is the basic operation
in the computation of a pairwise key in the polynomial pool-based
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 Fq' (q'=
28 + 1
+ 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:
above key computation optimization, we implement the random subset
assignment scheme and the grid-based scheme with q'
= 216 + 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:
The following figure compares the cost of computing a 64-bit
key using our optimized technique when q'=
28 + 1
(8-bit version) and 216
+ 1 (16-bit version) with the cost of generating a 64-bit
MAC (Message Authentication Code) on a 64-bit long message using
a 64-bit 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 q-composite
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 grid-based 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 non-compromised 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 grid-based 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 grid-based scheme, for
the basic probabilistic, the q-composite, 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 non-compromised 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 grid-based scheme for the same number of compromised nodes.
 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 52--61, Washington D.C., October, 2003.
 Donggang Liu, Peng Ning, "Location-Based
Pairwise Key Establishments for Static Sensor Networks,"
in 2003 ACM Workshop on Security in Ad Hoc and Sensor Networks
(SASN '03), October 2003.
 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 41--77, February 2005. (More results than the conference version, including actual implementation and performance results on MICA2 motes.)
 Donggang Liu, Peng Ning, “Improving Key Pre-Distribution with Deployment Knowledge in Static Sensor Networks,” in ACM Transactions on Sensor Networks (TOSN), Vol. 1, No. 2, pages 204-239, November 2005.
 Donggang Liu, Peng Ning, Wenliang Du, “Group-Based Key Pre-Distribution 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.)