Cryptography Reference
In-Depth Information
linear to the number of nodes compromised. This characteristic of the basic scheme
motivated development of key predistribution schemes that have better resiliency to
node capture. The basic scheme was extended by the q -composite scheme proposed by
Chan et al. (2003).
6.3.5 q-Composite Scheme
In a q -composite key scheme, instead of designing for a given probability p of sharing a
single key, the parameters are altered such that any two nodes have a given probability
p of sharing at least q different keys from the key pool. All q keys are used in the gen-
eration of the key, which encrypts communications between sensor nodes; hence, to
eavesdrop on the secured link, the adversary now has to compromise all q keys, instead
of just one. As q increases, it is exponentially harder for the attacker to break a link by
taking possession of a given set. However, increasing the probability of overlap in this
fashion naturally involves reducing the size of the key pool Q . Thus, the smaller key-
pool size makes the scheme more vulnerable to an adversary that is capable of compro-
mising larger numbers of sensor nodes.
The key-predistribution phase of this model is similar to Phase I in Section 6.3.4.1,
with the only exception being the key-pool size Q . In the shared key-discovery phase,
each node must find nodes that share all common keys with each other. The discov-
ery mechanism is similar to that of Phase II . Although a broadcast-based approach is
susceptible to an eavesdropping attack, alternative methods that are slower but more
secure are suggested where the nodes use the Merkle puzzle for key discovery (Merkle
1980). After the discovery phase, each node would be able to recognize its immediate
neighboring nodes with which it would share at least q keys. Subsequently, each node
could establish a link between nodes that share at least q keys by hashing the keys in
some canonical order. For example, K = hash( k 1 || k 2 || k 3 || . . . || k q ).
In this scheme, the key pool size | Q | plays a critical role because with a larger Q , the
probability of any two nodes sharing at least q keys would be much less. Consequently,
after bootstrapping, the network may not be connected. On the contrary, if | Q | is
small, the security of the network is compromised. Hence, | Q| should be such that the
probability of sharing at least q key should be greater than or equal to the probability
of successfully achieving a key setup with any of its neighbors. The approach used to
calculate the probability of any two nodes sharing exactly i keys
p ¢ is similar to cal-
()
culating p , as shown in Eq. (6.4), and is given as
æ æ æ
-
ö
QQi
-
2(
mi
)
çç ç
÷
÷
÷
÷
÷
çç ç
÷
÷
÷
÷
çç ç
÷
÷
çç - è
÷
÷ -
ç
÷
i
2(
mi
)
mi
ø
è è ø
¢ =
pi
()
(6.6)
2
æ ç ç ç ÷ ÷
Q
m
ç èø
For example, in Figure 6.2, we f ind the value of | Q | for a given m and i. In this case,
for m = 200 and i =10, we achieve a maximum
()
pi
¢
for | Q | = 3900.
Search WWH ::




Custom Search