| Effective Key Management for Wireless Sensor Networks |
| This
is a three-year EPSRC funded project that commenced in February 2007.
We are looking at key management issues for distributed networks
of lightweight computing devices, such as wireless sensor networks. The project has involved:
|
| Research papers |
| K.M. Martin and M.B. Paterson, An application-oriented framework for wireless sensor network key establishment, Proceedings
of the Third Workshop on Cryptography for Ad-hoc Networks
WCAN'07 (2007), Electronic Notes in Theoretical Computer
Science 192(2), 31 - 41, 2008. The term wireless sensor network is applied broadly to a range of significantly different networking environments. On the other hand there exists a substantial body of research on key establishment in wireless sensor networks, much of which does not pay heed to the variety of different application requirements. We set out a simple framework for classifying wireless sensor networks in terms of those properties that directly influence key distribution requirements. We fit a number of existing schemes within this framework and use this process to identify areas which require further attention from key management architects. |
| S.R. Blackburn, T. Etzion, K.M. Martin and M.B. Paterson, Efficient key predistribution for grid-based wireless sensor networks , Information Theoretic Security, Lecture Notes in Computer Science 5155, 54 - 69, 2008. Official conference version available from Springer Online. In this paper we propose a new key predistribution scheme for wireless sensor networks in which the sensors are arranged in a square grid. We describe how Costas arrays can be used for key predistribution in these networks, then define distinct difference configurations, a more general structure that provides a flexible choice of parameters in such schemes. We give examples of distinct difference configurations with good properties for key distribution, and demonstrate that the resulting schemes provide more efficient key predistribution on square grid networks than other schemes appearing in the literature. |
| S.R. Blackburn, K.M. Martin M.B. Paterson and D.R. Stinson, Key refreshing in wireless sensor networks , Information Theoretic Security, Lecture Notes in Computer Science 5155, 156 - 170, 2008. Official conference version available from Springer Online. The problem of establishing symmetric keys in wireless sensor networks has been extensively studied, but other aspects of key management have received comparitively little attention. In this paper we consider the problem of refreshing keys that are shared among several nides in a WSN, in order to provide forward security. We discuss several applications that lead to sensor networks with very different properties, and we propose key refreshing schemes that are useful in each of these environments, together with resynchronisation methods that allow nodes possessing different versions of a key to arrive at a common version. |
| S.R. Blackburn and S. Gerke, Connectivity of the uniform random graph, 2008. A uniform random intersection graph G(n,m,k) is a random graph constructed as follows. Label each of n nodes by a randomly chosen set of k distinct colours taken from some finite set of possible colours of size m. Nodes are joined by an edge if and only if some colour appears in both their labels. These graphs arise in the study of the security of wireless sensor networks. Such graphs arise in particular when modelling the network graph of the well known key predistribution technique due to Eschenauer and Gligor. The paper determines the threshold for connectivity of the graph G(n,m,k) when n tends to infinity with k a function of n such that $k\geq 2$ and $m=\lfloor n^\alpha\rfloor$ for some fixed positive real number $\alpha$. In this situation, G(n,m,k) is almost surely connected when \[ \liminf k^2n/m\log n>1, \] and G(n,m,k) is almost surely disconnected when \[ \limsup k^2n/m\log n<1. \] |
| K.M. Martin M.B. Paterson and D.R. Stinson, Key predistribution for homogeneous wireless sensor networks with group deployment of nodes, 2008, in submission. Recent literature contains proposals for key predistribution schemes for sensor networks in which nodes are deployed in separate groups. In this paper we consider the implications of group deployment for the connectivity and resilience of a key predistribution scheme. After showing that there is a lack of flexibility in the parameters of a scheme due to Liu, Ning and Du, limiting its application in networks with small numbers of groups, we propose a more general scheme, based on the structure of a resolvable transversal design. We demonstrate that this scheme permits effective trade-offs between resilience, connectivity and storage requirements within a group-deployed environment as compared to other schemes in the literature, and show that group deployment can be used to increase network connectivity, without increasing storage requirements or sacrificiing resiliency. |
| S.R. Blackburn, T. Etzion, K.M. Martin and M.B. Paterson, Two-Dimensional Patterns with Distinct Differences -- Constructions, Bounds, and Maximal Anticodes, 2008, in submission. A two-dimensional grid with dots is called a configuration with distinct differences if any two lines which connect two dots are distinct either in their length or in their slope. These configurations are known to have many applications such as radar, sonar, physical alignment, and time-position synchronization. Rather than restricting dots to lie in a square or rectangle, as previously studied, we restrict the maximum distance between dots of the configuration; the motivation for this is a new application of such configurations to key distribution in wireless sensor networks. We consider configurations in the hexagonal grid as well as in the traditional square grid, with distances measured both in the Euclidean metric, and in the Manhattan or hexagonal metrics. We note that these configurations are confined inside maximal anticodes in the corresponding grid. We classify maximal anticodes for each diameter in each grid. We present upper bounds on the number of dots in a pattern with distinct differences contained in these maximal anticodes. Our bounds settle (in the negative) a question of Golomb and Taylor on the existence of honeycomb arrays of arbitrarily large size. We present constructions and lower bounds on the number of dots in configurations with distinct differences contained in various two-dimensional shapes (such as anticodes) by considering periodic configurations with distinct differences in the square grid. |
| S.R. Blackburn, T. Etzion, K.M. Martin and M.B. Paterson, Distinct Difference Configurations: Multihop Paths and Key Predistribution in Sensor Networks, 2008, in submission. A distinct difference configuration is a set of points in $\mathbb{Z}^2$ with the property that the vectors (difference vectors) connecting any two of the points are all distinct. Many specific examples of these configurations have been previously studied: the class of distinct difference configurations includes both Costas arrays and sonar sequences, for example. Motivated by an application of these structures in key predistribution for wireless sensor networks, we define the $k$-hop coverage of a distinct difference configuration to be the number of distinct vectors that can be expressed as the sum of $k$ or fewer difference vectors. This is an important parameter when distinct difference configurations are used in the wireless sensor application, as this parameter describes the density of nodes that can be reached by a short secure path in the network. We provide upper and lower bounds for the $k$-hop coverage of a distinct difference configuration with $m$ points, and exploit a connection with $B_{h}$ sequences to construct configurations with maximal $k$-hop coverage. We also construct distinct difference configurations that enable all small vectors to be expressed as the sum of two of the difference vectors of the configuration, an important task for local secure connectivity in the application. |
| M.B. Paterson and D.R. Stinson, Two attacks on a sensor network key distribution scheme of Cheng and Agrawal, Journal of Mathematical Cryptology, Vol. 2, Issue 4, 393-403, 2009. Official version is available online. A sensor network key distribution scheme for hierarchical sensor networks was recently proposed by Cheng and Agrawal. A feature of their scheme is that pairwise keys exist between any pair of high-level nodes (which are called cluster heads) and between any (low-level) sensor node and the nearest cluster head. We present two attacks on their scheme. The first attack can be applied for certain parameter sets. If it is applicable, then this attack can result in the compromise of most if not all of the sensor node keys after a small number of cluster heads are compromised. The second attack can always be applied, though it is weaker. |
| S.R. Blackburn, T. Etzion, K.M. Martin and M.B. Paterson, Efficient implementation of lightweight key predistribution techniques for grid-based wireless sensor networks, 2009, preprint. The key predistribution scheme (KPS) of Blackburn et al. for grid-based wireless sensor networks makes use of distinct-difference configurations (DDC) to achieve a lightweight and resilient distribution of symmetric keys. Significant theoretical progress on DDCs has been made recently. This paper examines the implications of this research for the construction of KPSs for grid-based sensor networks. We explore the connectivity and resilience requirements of such schemes and give explicit algorithms for efficiently constructing DDCs that lead to shemes with the desired properties for a large range of parameters. |
| K.M. Martin and M.B. Paterson, Ultra-lightweight key predistribution in wireless sensor networks for monitoring linear infrastructure, Information Security Theory and
Practice: Smart Devices, Pervasive Systems and Ubiquitous Networks
(WISTP 2009), Lecture Notes in Computer Science 5746, 143 - 152, 2009. Official conference version available from Springer Online. One-dimensional wireless sensor networks are important for such security-critical applications as pipeline monitoring and perimeter surveillance. When considering the distribution of symmetric keys to secure the communication in such networks, the specific topology leads to security and performance requirements that are markedly distinct from those of the more widely-studied case of a planar network. We consider these requirements in detail, proposing a new measure for connectivity in one-dimensional environments. We show that, surprisingly, optimal results may be obtained through the use of extremely lightweight key predistribution schemes. |
| K.M. Martin, On the applicability of combinatorial designs to key predistribution for wireless sensor networks,Coding and Cryptology (IWCC2009), Lecture Notes in Computer Science 5557, 124-145, 2009. Official conference version available from Springer Online. The constraints of lightweight distributed computing environments such as wireless sensor networks lend themselves to the use of symmetric cryptography to provide security services. The lack of central infrastructure after deployment of such networks requires the necessary symmetric keys to be predistributed to participating nodes. The rich mathematical structure of combinatorial designs has resulted in the proposal of several key predistribution schemes for wireless sensor networks based on designs. We review and examine the appropriateness of combinatorial designs as a tool for building key predistribution schemes suitable for such environments. |
| Presentations |
| Ultra-lightweight key predistribution in wireless sensor networks for monitoring linear infrastructure, WISTP 2009, Brussels, Belgium, September 2009. On the applicability of combinatorial designs to key predistribution for wireless sensor networks, IWCC 2009, Zhangjiajie, Hunan, China, June 2009. Lightweight key establishment for distributed networking environments, COSIC seminar, Katholieke Universiteit Leuven, Belgium, September 2007. Efficient key predistribution for grid-based wireless sensor networks, ICITS 2008, Calgary, Canada. Key refreshing in wireless sensor networks, ICITS 2008, Calgary, Canada. Properties of distinct-difference configurations and lightweight key predistribution schemes for grid-based networks, Claude Shannon Institute Workshop on Coding and Cryptography, Cork, Ireland |
| Keith's Electronic Domicile |