Image Processing Reference
In-Depth Information
The number of possible key rings is
P
k
)=
P
!
(
k
!
(
P
−
k
)
!
The number of possible key rings after
k
keys have been drawn from the key pool without replace-
ment is
P
−
k
)=
(
k
P
−
k
)
!
(
k
!
(
P
−
k
)
!
Thus, the probability that no key is shared is the ratio of the number of key rings without a match
divided by the total number of key rings. Concluding the probability of at least one common key is
k
!
(
P
−
k
)
!
(
P
−
k
)
!
Pr
(
at least one common key
)=
−
P
!
k
!
(
P
−
k
)
!
After being installed, all sensor nodes start discovering their neighbors within the wireless commu-
nication range, and any two nodes, wishing to find out if they share a key, simply exchange lists of
key ids on their key ring. Alternatively, each node could broadcast a list:
s
→∗∶
α
∣
E
(
K
, α
)∣⋯∣
E
(
K
k
, α
)
A node receiving such a list would then have to try all its keys, to find out matching keys (with a high
probability). This would hide from an attacker which node holds which key ids but requires more
computational overhead from each sensor node. The shared key discovery establishes a (random
graph) topology in which links exist between nodes that share at least one key. It might happen that
one key is used by more than one pair of nodes.
In the path key establishment phase, path keys are assigned to pairs of nodes
that do not
share a key but are connected by two or more links so that there is a sequence of nodes which share
keys and “connect”
s
to
s
n
. .The article [EG], however, does not contain any clear information on
how path keys are computed or distributed. It only states that they do not need to be generated by
the sensor nodes. Furthermore, it is mentioned that “the design of the DSN ensures that, after the
shared key discovery phase is finished, a number of keys on any ring are left unassigned to any link.”
However, it does not become clear from [EG] how two nodes can make use of these unused keys
for establishing a path key.
If a node is detected to be compromised, all keys on its ring need to be revoked. For this, the con-
troller node generates a signature key
K
e
and sends it individually to every sensor node
si
,encrypted
with the key
K
ci
,
si
:
(
s
,
s
n
)
ci
→
si
∶
E
(
K
ci
,
si
,
K
e
)
Afterwards, it broadcasts a signed list of all identifiers of keys that have to be revoked:
ci
→∗∶
id
∣
id
∣⋯∣
id
k
∣
MAC
(
K
e
,
id
∣
id
∣⋯∣
id
k
)
Every node receiving this list has to delete all listed keys from his key ring. his removes all links to
the compromised node plus some more links from the random graph. Every node that had to remove
some of its links afterwards tries to reestablish as much as possible of them by starting a shared key
discovery and a path key establishment phase.
In Ref. [CPS], Chan et al. propose a modification to the basic random pre-distribution scheme
described thus far by requiring to combine multiple-shared keys. In this variant, two nodes are
