18-09-2012, 11:19 AM
Exact Formulae for Resilience in Random Key Predistribution Schemes
1Exact Formulae for Resilience.pdf (Size: 122.28 KB / Downloads: 17)
Abstract
As wireless sensor networks are often deployed
in adverse or hostile environments, key management schemes
are required for sensor nodes. The random key predistribution
(RKP) scheme is a probabilistic key management scheme where
each node is preloaded with a subset of keys that are randomly
selected from a pool of keys. If a pair of neighbor nodes have a
common key, it can be used to establish a secure link between
the nodes. The q-composite RKP scheme requires that a pair of
neighbor nodes have at least q common keys for a secure link.
In this article, we show that the previous security analysis (i.e.,
resilience against node capture) of the q-composite RKP scheme
is inaccurate and present new formulae for resilience in the RKP
scheme and the q-composite RKP scheme.
INTRODUCTION
WIRELESS sensor networks (WSNs) are ad hoc networks
that include a large number of tiny, cheap,
and highly resource-constrained sensor nodes. Since WSNs
are often deployed in a hostile environments and the data
are transmitted over the air, security measures to prevent
eavesdropping or tampering of private information are critical.
However, due to the resource constraints on sensor nodes,
traditional key establishment techniques (e.g., public key
cryptography and online key distribution center) cannot be
employed. Lightweight and flexible key distribution schemes
are essential to secure the communication between sensor
nodes.
The most straightforward key distribution possible is to
have a single network-wide key [1]. Such simplicity results
in a high level of efficiency and flexibility, requiring minimal
memory for the storage of keys no matter the size of the
network. However, the network-wide key approach has serious
security vulnerabilities; the capture of a single node discloses
the common key, compromising all the nodes in the network.
RANDOM KEY PREDISTRIBUTION SCHEMES
A random key predistribution scheme consists of three
phases: (1) initialization, (2) shared-key discovery, and (3)
path-key establishment. In the initialization phase, a large pool
of keys S is generated. For each sensor node, m keys are
randomly selected from the key pool S and stored into the
node’s memory. After the sensor nodes are deployed, a sharedkey
discovery is performed where each node tries to discover
its neighbor nodes with which it shares common keys. Let
k1, k2, . . . , ki be the common keys shared by two neighbor
nodes. In the RKP scheme, a link key K is chosen randomly
from the common keys k1, k2, . . . , ki. In the q-composite RKP
scheme, if i ≥ q, a link key K is generated as the hash of
all common keys, i.e., K = hash(k1k2 · · ·ki). Note that
the 1-composite RKP scheme (i.e., q = 1) is different from
the RKP scheme; while the link key in the 1-composite RKP
scheme is the hash of all common keys, the link key in the
RKP scheme is equal to a single key that is chosen from the
common keys. After the shared-key discovery is completed,
two neighbor nodes may not have a link key because their key
rings do not have enough common keys. When the two nodes
need to establish a secure communication, they can setup a
path-key by finding a multi-hop secure path between them. If
the graph of secure links is connected, a path always exists
between any two nodes.
CONCLUSION
We show that the previous analysis of the q-composite
RKP scheme is inaccurate because the dependency between
probabilistic events is not fully considered. Interestingly, a
similar inaccurate analysis was also made in the algorithm
community when the false positive rate of the Bloom filter
was analyzed. Readers who are interested in the exact analysis
of the Bloom filter can refer to [8], [9].