Image Processing Reference
In-Depth Information
required to share at least
q
keys on their rings, to establish a link. So, if
K
, ...,
K
q
′
are the common
keys of nodes
u
and
v
(with
q
′
≥
q
), then the link key is computed as follows:
K
u
,
v
∶=
h
(
K
, ...,
K
q
′
)
On the one hand, it becomes harder with this scheme for an attacker to make use of one or multiple
keyring(s)obtainedbynodecompromise,andthisincreaseindiicultyisexponentialin
q
.Onthe
otherhand,thesizeofthekeypool
has to be decreased to have a high enough probability that two
nodes share enough keys on their rings to establish a link. his gives an attacker a higher percentage
of compromised keys per compromised nodes. In Ref. [CPS], a formula is derived how to compute
the key pool size so that any two nodes share enough keys with a given probability
∣
P
∣
>
p
.hisscheme
is called the “
q-composite scheme
.”
Inthesamepaper,Chanetal.proposeasecondscheme,called“multipathkeyreinforcement.”
The basic idea of this scheme is to “strengthen” an already established key by combining it with ran-
dom numbers that are exchanged over alternative secure links. After the discovery phase of the basic
scheme has been completed and enough routing information can be exchanged so that a node
u
knows all (or at least enough) disjoint paths
p
, ...,
p
j
to a node
v
,node
u
generates
j
random values
v
, ...,
v
j
and sends each value along another path to node
v
.Aterhavingreceivedall
j
values, node
v
computes the new link key:
K
′
u
,
v
=
K
u
,
v
⊕
v
⊕⋯⊕
v
j
Clearly, the more paths are used, the harder it gets for an attacker to eavesdrop on all of them. How-
ever, the probability for an attacker to be able to eavesdrop on a path increases with the length of
the path, so that utilizing more but longer paths does not necessarily increase the overall security to
be attained by the scheme. In Ref. [CPS], the special case of -hop multipath key reinforcement
is analyzed using probability theory. Furthermore, the paper also describes a third approach called
“random pairwise key scheme” that hands out keys to pairs of nodes which also store the identity of
therespectivepeernodeholdingthesamekey.hemotivationbehindthisapproachistoallowfor
node-to-node authentication (see Ref. [CPS] for details).
Concerning security, the following remarks on probabilistic key management should be noted. he
nice property of having a rather high probability that any two given nodes share at least one key (e.g.,
p
., if keys out of , keys are given to every node) also plays in the hands of an attacker
whocompromisesanode,andanattackerthathascompromisedmorethanonenodehasaneven
higher probability of holding at least one key with any given node. It has been shown [CPS] that
on the average
kn
=
P
nodes share a common key if for each of
n
nodes
k
keys are chosen from a key
pool of size
P
. his problem also exists with the
q
-composite scheme, as the key pool size is reduced
to ensure a high enough probability that any two nodes share at least
q
keys. his especially concerns
the attacker's ability to perform active attacks, as eavesdropping attacks are less probable because the
probability that the attacker holds exactly the key that two other nodes are using is smaller (and even
smaller in the
q
-composite scheme).
To avoid that attackers can use captured keys to eavesdrop on communication of nodes that have
not yet been compromised, Huang and Du developed a node-based probabilistic key distribution
scheme that ensures that different keys are used on different links [HD]. The main idea of this
scheme is instead of selecting keys from a large key pool for each node, the set of keys to be given to
each node is computed by first randomly choosing a set of
t
potential peers for each node and then
assigning randomly generated keys for each pair of peers. his construction ensures that no key may
be used on two different links, so that keys captured from compromised nodes cannot be exploited
for eavesdroping on communications of other nodes.
A different construction that aims to ensure the same property is based on “Blom's matrix-based
key pre-distribution scheme” [Blo]. The scheme guarantees the security property that as long as
/
