Cyber Defense Laboratory

TinyKeyMan: Key Management for Sensor Networks

People

• Dr. Peng Ning
• Donggang Liu
• Rongfang Li

Platform

TinyOS

Software Package

TinyKeyMan.zip

How to Use

   This software can be invoked through the interfaces we provide. More details are in Readme

Performance Results

• Code Size (on MICA2)

  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 F_q' (q'= 2⁸ + 1 or 2¹⁶ + 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: 

Using the above key computation optimization, we implement the random subset assignment scheme and the grid-based scheme with q' = 2¹⁶ + 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:

• Computational Cost (on MICA2)

  The following figure compares the cost of computing a 64-bit key using our optimized technique when q'= 2⁸ + 1 (8-bit version) and 2¹⁶ + 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).

• 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 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 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.

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 52--61, Washington D.C., October, 2003.

[2] 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.

[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 41--77, February 2005. (More results than the conference version, including actual implementation and performance results on MICA2 motes.)

[4] 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.

[5] 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.)