B.3. The Basic Bootstrapping Framework

Key establishment in a sensor network is effected by a three-stage process called bootstrapping. Subsequent node-to-node communication uses the keys established during the bootstrapping phase. The three stages of bootstrapping are as follows:

Key predistribution

This step is carried out before the deployment of the sensors. A key set-up server chooses a pool of randomly generated keys and assigns to each sensor node u_i a subset of . The set is called the key ring of the node u_i. The key predistribution algorithms essentially differ in the ways the sets and are selected. Each key is associated with an ID that need not be kept secret and can even be transmitted in plaintext. Similarly, each sensor node is given a unique ID which need not be maintained secretly.

Direct key establishment

Immediately after deployment, each sensor node tries to determine all other sensor nodes with which it can communicate directly and secretly. Two nodes that are within the communication ranges of one another are called physical neighbours, whereas two nodes sharing one (or more) key(s) in their key rings are called key neighbours. Two nodes can secretly (and directly) communicate with one another if and only if they are both physical and key neighbours; let us plan to call such pairs direct neighbours.

In the direct key establishment phase, each sensor node u locates its direct neighbours. To that end u broadcasts its own ID and the IDs of the keys in its key ring. Each physical neighbour v of u responds by mentioning the matching key IDs, if any, stored in the key ring of v. This is how u identifies its direct neighbours.

If sending unencrypted key IDs can be a potential threat to the security of the network, each node u can encrypt some plaintext message m by the keys in its ring and broadcasts the corresponding ciphertexts instead of the key IDs. Those physical neighbours of u that can decrypt one of the transmitted ciphertexts using one of the keys in their respective key rings establish themselves as direct neighbours of u.

Path key establishment

This is an optional stage and, if executed, adds to the connectivity of the network. Suppose that two physical neighbours u and v fail to establish a direct link between them in the direct key establishment phase. But there exists a path u = u₀, u₁, u₂, . . . , u_h–1, u_h = v in the network with each u_i a direct neighbour of u_i+1 (for i = 0, 1, . . . , h – 1). The node u then generates a random key k, encrypts k with the key shared between u and u₁ and sends the encrypted key to u₁. Subsequently, u₁ retrieves k by decryption, encrypts k by the key shared by u₁ and u₂ and sends this encrypted version of k to u₂. This process is repeated until the key k reaches the desired destination v. Now, u and v can communicate secretly and directly using k and thereby become direct neighbours.

The main difficulty in this process is the discovery of a path between u and v. This can be achieved by u initiating a message reflecting its desire to communicate with v. Let u₁ be a direct neighbour of u. If u₁ is also a direct neighbour of v, a path between u and v is discovered. Else u₁ retransmits u’s request to the direct neighbours u₂ of u₁. This process is repeated, until a path is established between u and v, or the number of hops exceeds a certain limit. Note that path discovery may incur substantial communication overhead and so the maximum number h of hops allowed needs to be fixed at a not-so-big value. Typically, the values h = 2, 3 are recommended.

A bootstrapping algorithm, or more precisely, a key predistribution algorithm must fulfill the following requirements. These requirements often turn out to be mutually contradictory. A key predistribution scheme attempts to achieve suitable trade-offs among them.

Compactness

Each key ring should be small enough to fit in a sensor node’s memory. Typically 50–200 cryptographic keys (say, 128-bit keys of block ciphers) can be stored in each processor. That number is between n – 1 (a key for each pair) and 1 (a master key for the entire network).

Randomness

The key rings in different nodes are to be randomly chosen from a big pool, so that there is not enough overlap between the rings of two nodes.

Network connectivity

The resulting network should be connected in the sense that the undirected graph G = (V, E) with V comprising the nodes in the network and E containing a link (u, v) if and only if u and v are direct neighbours, must be (or at least with high probability) connected.

Resilience against node capture

Ideally, the capture of any number of nodes must not divulge the secret key(s) between uncaptured direct neighbours. Practically, the fraction of communication links among uncaptured nodes, that are compromised because of node captures, must be small, at least as long as the fraction of nodes that are captured is not too high.

Scalability

Arbitrarily (but not impractically) big networks should be supported.

Future addition of nodes

One should allow new nodes to join the network at any point of time after the initial deployment, for example, to replenish captured, faulty and dead nodes.

Additional requirements may also be conceived of in order to take curative measures against active attacks and/or faults. However, a study of active attacks and of countermeasures against those is beyond the scope of our treatment here.

Detection of bad nodes

There should be a mechanism to detect the presence and identities of dead, malfunctioning and rogue nodes. Here, a rogue node stands for a captured node that is used by the enemy to disrupt the natural working of the network. Active attacks mountable by the enemy include transmission of unauthorized and misleading data across the network, making neighbours always busy and letting them run out of battery sooner than the expected lifetime (sleep deprivation attack), and so on.

Revocation of bad nodes

Faulty and rogue nodes must be pruned out of the network before they can cause sizeable harm.

Resilience against node replication

Captured nodes can be replicated and the copies deployed by the enemy with the intention that these added nodes outnumber the legitimate nodes and eventually take control of the network. There should be a strategy to detect and cure replication of malicious nodes.

We now concentrate on some concrete realizations of the bootstrapping scheme. The optional third stage (path key establishment) will often be excluded from our discussion, because there are little algorithm-specific issues in this stage.

Before we introduce specific algorithms, let us summarize the notations we are going to use in the rest of this chapter:

n	= Number of nodes in the sensor network
n′	= (Expected) number of nodes in the physical neighbourhood of each node
d	= Degree of connectivity of each node in the key/direct neighbourhood graph
Pc	= Global connectivity (a high probability like 0.9999)
p′	= Local connectivity (probability that two physical neighbours share a key)
M	= Size of the key pool
m	= The size of key ring of each node (in number of cryptographic keys)
	= The underlying field for the poly-pool and the matrix-pool schemes
S	= Size of the polynomial (or matrix) pool
s	= Number of polynomial (or matrix) shares in the key ring of each node
t	= Degree of a polynomial (or dimension of a matrix)
c	= Number of nodes captured
Pe	= Probability of successful eavesdropping expressed as a function of c