B.4. The Basic Random Key Predistribution Scheme
The paper [88] by Eschenauer and Gligor is a pioneering research on bootstrapping in sensor networks. Their scheme, henceforth referred to as the EG scheme, is essentially the basic bootstrapping method just described.
The key set-up server starts with a pool 
of randomly generated keys. The number M of keys in 
is taken to be a small multiple of the network size n. For each sensor node u to be deployed, a random subset of m keys from 
is selected and given to u as its key ring. Upon deployment, each node discovers its direct neighbours as specified in the generic description. We now explain how the parameters M, m are to be chosen so as to make the resulting network connected with high probability.
Let us first look at the key neighbourhood graph Gkey on the n sensor nodes in which a link exists between two nodes if and only if these nodes are key neighbours. Let p denote the probability that a link exists between two randomly selected nodes of this graph. A result on random graphs due to Erdös and Rényi indicates that in the limit n → ∞, the probability that Gkey is connected is
Equation B.1
We fix Pc at a high value, say, 0.9999, and express the expected degree of each node in Gkey as
Equation B.2
In practice, we should also bring physical neighbourhood in consideration and look at the direct neighbourhood graph G = Gdirect on the n deployed sensor nodes. In this graph, two nodes are connected by an edge if and only if they are direct neighbours. G is not random, since it depends on the geographical distribution of the nodes in the deployment area. However, we assume that the above result for random graphs continues to hold for G too. In particular, we fix the degree of direct connectivity of each node to be (at least) d and require
Equation B.3
where n′ denotes the expected number of physical neighbours of each node, and where p′ is the probability that two physical neighbours share one or more keys in their key rings 
and 
. (Pc is often called the global connectivity and p′ the local connectivity.)
For the determination of p′, we first note that there is a total of 
key rings of size m that can be chosen from the pool 
of size M. For a fixed 
, the total number of ways of choosing 
such that 
does not share a key with Ki is equal to the number of ways of choosing m keys from 
. This number is 
. It then follows that
Equation B.4
Equations (B.2), (B.3) and (B.4) dictate how the key-pool size M is to be chosen, given the values of n, n′ and m.
Example B.1.
|
As a specific numerical example, consider a sensor network with n = 10,000 nodes. For the desired probability Pc = 0.9999 of connectedness of Gkey, we use Equation (B.2) to obtain the desired degree d as d ≥ 18.419. Let us take d = 20. Now, suppose that the expected number of physical neighbours of each deployed node is n′ = 50. By Equation (B.3), we then require p′ = d/n′ = 0.4. Finally, assume that each sensor can hold m = 150 keys in its memory. Equation (B.4) indicates that we should have M ≤ 44,195 in order to ensure p′ ≥ 0.4. In particular, we may take M = 40,000. |
Let us now study the resilience of the EG scheme against node captures. Assume that c nodes are captured at random from the network and that u and v are two uncaptured nodes that are direct neighbours. We compute the probability Pe that an eavesdropper can decipher encrypted communication between u and v based on the knowledge of the keys available from the c captured key rings. Clearly, smaller values of Pe indicate higher resilience against node captures.
Suppose that u and v use the key k for communication between them. Then, Pe is equal to the probability that k resides in one of the key rings of c captured nodes. Since each key ring consists of m keys randomly chosen from a pool of M keys, the probability that a particular key k is not available in a key ring is 
and consequently the probability that k does not appear in all of the c compromised key rings is 
. Thus, the probability of successful eavesdropping is
Example B.2.
|
As in Example B.1, take n = 10,000, n′ = 50, m = 150 and M = 40,000. If c = 100 nodes are captured, the fraction of compromised communication is Pe ≈ 0.313. Thus, a capture of only 100 nodes leads to a compromise of about one-third of the traffic. That is not a satisfactory figure. We need better algorithms. |
B.4.1. The q-composite Scheme
Chan et al. [44] propose several modifications of the basic EG scheme in order to improve upon the resilience of the network against node capture. The q-composite scheme, henceforth abbreviated as the qC scheme, is based on the requirement of a bigger overlap of key rings for enabling nodes to communicate.
As in the EG scheme, the key set-up server decides a pool 
of M random keys and loads the key ring of each node with a random subset of size m of 
. Let the network consist of n nodes.
In the direct key establishment phase, each node u discovers all its physical neighbours that share q or more keys with u, where q is a predetermined system-wide parameter. Those physical neighbours that do so are now called direct neighbours of u. Let v be a direct neighbour of u and let q′ ≥ q be the actual number of keys shared by u and v. Call these keys k1, k2, . . . , kq′. The nodes use the key
k := H(k1‖k2‖ · · · ‖kq′)
for future communication, where ‖ denotes string concatenation and H is a hash function. A pair of physical neighbours that share < q predistributed keys do not communicate directly.
Recall that for the basic EG scheme q = 1 and the key k for communication between direct neighbours is taken to be one shared key instead of a hash value of all shared keys. The motivation behind going for the qC scheme is that requiring a bigger overlap between the key rings of a pair of physical neighbours leads to a smaller probability Pe of successful eavesdropping, since now the eavesdropper has to possess the knowledge of at least q shared keys (not just one). However, the requirement of q (or more) matching keys between communicating nodes restricts the key pool size M more than the EG scheme, and consequently a capture of fewer nodes reveals a bigger fraction of the total key pool 
to the eavesdropper. Chan et al. [44] report that the best trade-off is achieved for the value q = 2 or 3.
Let us now derive the explicit expressions for M and Pe. Equations (B.1), (B.2) and (B.3) hold for the qC scheme with the sole exception that now the interpretation of the probability p′ of direct neighbourhood is different. There is a total of 
ways of choosing two random key rings of size m from a pool of M keys. Let us compute the number 
of such pairs of key rings sharing exactly r keys. First, these shared r keys can be chosen in 
ways. Out of the remaining M – r keys, the remaining m – r keys for the first ring can be chosen in 
ways. Finally, the remaining m – r keys for the second ring can be chosen in 
ways from M – m keys not present in the first ring. Thus, we have
is the equivalent of Equation (B.4) for the qC scheme.
Example B.3.
|
As in Example B.1, consider n = 10,000, n′ = 50, m = 150. For d = 20, we require p′ ≥ 0.4. This, in turn, demands M ≤ 16,387 for q = 2 and M ≤ 9,864 for q = 3. Compare these with the requirement M ≤ 44,195 for the EG scheme. |
Let us now calculate the probability Pe of successfully deciphering the communication between two uncaptured nodes u and v, given that c nodes are already captured by the eavesdropper. Let q′ ≥ q be the actual number of keys shared by u and v; this happens with probability 
. Each of these common keys is available to the eavesdropper with a probability 
. It follows that
Example B.4.
|
Let us continue with the network of Examples B.1, B.2 and B.3. The following table summarizes the probabilities Pe for various values of c. For the EG scheme, we take M = 40,000, whereas for the qC scheme, we take M = 16,000 for q = 2 and M = 9,800 for q = 3.
This table indicates that when the number of nodes captured is small, the qC scheme outperforms the EG scheme. However, for large values of c, the effects of smaller values of the key-pool size show up, leading to a poorer performance of the qC schemes compared to the EG scheme. | |||||||||||||||||||||||||||||||||||||||||||||
B.4.2. Multi-path Key Reinforcement
Another way to improve the resilience of the network against node captures is the multi-path key reinforcement scheme proposed again by Chan et al. [44]. As in the EG scheme, sensor nodes are deployed each with m keys in its key ring chosen randomly from a pool of M keys. Let u and v establish themselves as direct neighbours sharing the key k. Instead of using k itself as the key for future communication, the nodes try to locate several pairwise node-disjoint paths between them. Such a path u = v0, v1, . . . , vl = v consists of pairs of direct neighbours (vi, vi+1) for i = 0, . . . , l – 1. A randomly generated key k′ is then routed securely along the path from u to v.
Assume that r node-disjoint paths between u and v are discovered and the random keys 
are transfered securely along these paths. The nodes u and v then use the key
The reason why this scheme improves resilience against node captures is that even if the original k resides in the memory of a captured node, the new key k′ is computable by the adversary if and only if she can obtain all of the r session secrets 
. The bigger r is, the more difficult it is for the adversary to eavesdrop on all of the r node-disjoint paths. On the other hand, if the lengths of these paths are large, then the probability of eavesdropping at some links of the paths increases. Moreover, increasing the lengths of the paths incurs bigger communication overhead. The proponents of the scheme recommend only 2-hop multi-path key reinforcement.
We do not go into the details of the analysis of the multi-path key reinforcement scheme, but refer the reader to Chan et al. [44]. We only note that though it is possible to use multi-path key reinforcement for the q-composite scheme, it is not a lucrative option. The smaller size of the key pool for the q-composite scheme tends to nullify the effects of multi-path key reinforcement.