Download Trusted embedded System Operating System (TeSOS)

In a similar approach, [LS05b] deterministically divides the set of nodes into partitions such that
nodes of dierent partitions can not establish a direct link key. Resilience is increased since now
a coalition of
λ
nodes from the same partition is required to compromise all other link keys.
+
An approach based on a polynomials was proposed in [BDSV 98]. In this scheme, a symmetrical polynomial
P (x, y) = P (y, x)
with coecients from
used to derive pair-wise link keys. Each node
polynomial. For node
ni
ni
GF (q)
for suciently large prime
to derive the common key
Kij
with node
nj ,
q
is
fi (x) = P (i, x)
of the
it simply evaluates
fi (j).
stores a localized version
λ of coecients of P determines the resilience of the scheme in the sense that a
λ + 1 nodes is needed to derive all link keys. Similar to previous trade-o approaches,
The number
coalition of
[LN03b] proposes to partition the WSN, distributing multiple polynomials and thus sacricing
key connectivity for scalability and/or resilience, since polynomials can be smaller but some node
pairs may not have a shared polynomial to derive a common key from. The polynomials to store
on each node can be selected randomly, in a grouped fashion to reduce communication overhead
or based on available deployment topology information as proposed in [LN03c].
Probabilistic Pair-wise Schemes
The amount of required key storage for pre-distributed pair-wise keys is reduced in [EG02, CPS03]
by storing only
N ∗p
keys, where
0≤p≤1
is the probability that any two nodes will be able to
communicate in the resulting system. Another approach to modify the fraction of keys known
+
to each node is presented in [DDH 04], where an approximate knowledge of the later physical
topology is assumed and keys are distributed where the likelihood of reachability is large.
The authors of [ZSJ03] assume that the adversary needs a minimum time
node. In the deployment or upgrade phase, they deploy a node
keyed hash functions
fx (·)
and
hx (·)
where
x
A
t
to compromise a
with a master key
Km ,
two
is a node identity string, and a derived device key
KA = hA (Km ).
t, A can establish a pair-wise key KAB with any discovered node B
KAB = fKB (A), since B still knows its derived key KB and A can derive it as KB =
hB (Km ). After time t, key Km is deleted but KA is kept. As a result, only new nodes with
knowledge of Km can establish new links with node A. To establish keys with sleeping nodes that
do not wake up until t, [ZSJ03] suggests that A asks available nodes for a list of node IDs within
Within the time frame
using
the area and derives the corresponding link keys in advance.
of this scheme are probabilistic, but can be very good if
t
Key connectivity and resilience
is chosen correctly. However, results
+
on residual memory traces [HSH 08] and the sensor node's very limited resistance to physical
attacks [HBH05] limit the practicality of this solution.
Enhancements to Pair-wise Schemes
Several protocols require an additional key discovery phase after deployment to determine what
peers are reachable, whether link keys can be established with them and what other nodes
can be reached via these links.
In this phase, typically each node broadcasts the list of key
IDs from its key chain and observes the corresponding announcements of any neighbors. The
communication load in this phase can be reduced by grouping key IDs such that all IDs in a group
are known from the corresponding group ID [HLV04] or, in probabilistic key distribution, by using
a Pseudo-Random Function (PRF) to generate the list of IDs known to each node [ZSJ03] and
only transmitting the respective PRF seed.
The storage complexity can be further reduced by grouping
l
link keys into a single localized
master key. This reduces resilience as any compromised node will compromise the communication
link security of
of
l
[LS05b].
l−1
other nodes, however, the required storage is also reduced by a factor
A similar idea is described in [DCL04], where multiple master keys are used in
combination with random nonces and a PRF to reduce storage. Each generation of nodes uses
its own master key as well as derived keys of the master keys of future (anticipated) generations.
30