Most cryptographic primitives such as ciphers, pseudorandom functions, and authentication codes require the availability of secret keys. For example, if two nodes wish to communicate in secret using a symmetric-key cipher, then they must both have knowledge of a given secret key which is unknown to an outside adversary. However, due to the large scale of deployment of sensor networks and the limited hardware capabilities of sensor nodes, the standard methods of key distribution such as Public Key Infrastructures (PKIs) or trusted-authority key distribution are not applicable.

Key distribution refers to the problem of establishing shared secrets on sensor nodes such that secret symmetric keys for communication privacy, integrity and authenticity can be generated. A key distribution scheme should allow a sensor network to bootstrap (initialize) a secure communications infrastructure providing secrecy (i.e. outsiders cannot derive information from eavesdropping on the wireless communications of the nodes) and preferably entity and message authentication. It should also allow for the addition of new nodes and preferably the revocation of old nodes. In an early publication (SPINs) we proposed a basic symmetric key establishment protocol mediated by a base-station acting as a trusted authority.

Message-In-a-Bottle

Existing protocols for secure key establishment all rely on an unspecified mechanism for initially deploying secrets to sensor nodes. However, no commercially viable and secure mechanism exists for initial setup. Without a guarantee of secure key deployment, the traffic over a sensor network cannot be presumed secure.
To address this problem, we present a user-friendly protocol for the secure deployment of cryptographic keys in sensor networks. We propose a collection of five techniques to prevent an attacker from eavesdropping on key deployment. To demonstrate feasibility for real-world use, we implement our protocol on Telos motes and conduct a user study.

Random Key Pre-distribution

Random key pre-distribution was first proposed by Eschenauer and Gligor in 2002. Each sensor node is pre-loaded with a random subset of the keys from a secret key pool. After deployment, each sensor node will (with high probability, depending on parameters) share at least one key with some subset of its neighbors. This subset of neighbors which share pre-loaded keys is sufficient to bootstrap a complete infrastructure. We show several optimisations on the basic scheme, including requiring several shared keys instead of one; strengthening the security of shared keys by using a technique called multi-path secrecy reinforcement; and using pairwise shared keys (keys shared between exactly two nodes) to provide entity authentication and node revocation. In our journal publication we elaborate on the mechanism of distributed node revocation, making revocation practical by introducing the concept of revocation sessions. We prove several theorems showing that the revocation scheme is indeed practical and correct. A more complete version of the revocation scheme is

Peer-mediated Key Establishment

Random key predistribution suffers from the drawback that the memory required per node increases linearly with the size of the network. Standard single-authority trusted third party key establishment suffers from the drawback of communications congestions that is also linear in the size of the network. In this work we seek an attractive tradeoff point between the two: we propose peer-mediated key establishment, which achieves both sublinear memory and communication congestion overhead: specifically, the overheads are a fractional power (e.g. square root) of the total network size. The idea behind the scheme is to randomly distribute pairwise keys such that the functionality of the trusted third party is fully distributed across the network. Hence, any two nodes needing to establish a shared key can always find some third node somewhere in the network that can be their intermediary in the key-establishment process.

Key-Infection

Existing methods for key-distribution are highly complex and require assumptions such as knowing the set of nodes being deployed and being able to systematically preload each node with a set of symmetric keys. Key-infection is a bold proposal which presents a highly streamlined and simple method of key-distrbution: nodes simply send them to each other, in unencrypted messages. Based on the reasonable assumption that the adversary is unable to eavesdrop on the entire network at all times during the key establishment process, simple algorithms can be used which strengthen the security of this approach.

Contact Us