Key establishment in ad hoc networks : Key establishment in ad hoc networks exploiting
physical contact;
mobility and vicinity;
Exploiting physical contact : Exploiting physical contact target scenarios
modern home with multiple remotely controlled devices
DVD, VHS, HiFi, doors, air condition, lights, alarm, …
modern hospital
mobile personal assistants and medical devices, such as thermometers, blood pressure meters, …
common in these scenarios
transient associations between devices
physical contact is possible for initialization purposes
the resurrecting duckling security policy
at the beginning, each device has an empty soul
each empty device accepts the first device to which it is physically connected as its master (imprinting)
during the physical contact, a device key is established
the master uses the device key to execute commands on the device, including the suicide command
after suicide, the device returns to its empty state and it is ready to be imprinted again
Key establishment in ad hoc networks
Does mobility increase or reduce security ? : Does mobility increase or reduce security ? Mobility is usually perceived as a major security challenge in networking
Wireless communications
Sporadic availability of the user/node
Higher vulnerability of the device
Reduced computing capability of the devices
However, in real life, people often move (and gather) to increase security
Face to face meetings
Transport of assets and documents
Authentication by physical presence
Can we take advantage of mobility to increase security in networking?
Yes, we can, assuming that
nodes are operated by humans
when in the vicinity of each other, nodes can use a secure side channel (e.g., infra red) to exchange a key
each node has some friends (peers that are trusted by the node), and there is already a key shared between each pair of friends Key establishment in ad hoc networks
Exploiting vicinity and the secure side channel : Infrared link (Alice, XYZ, key material) (Bob, UVW, key material) Visual recognition, conscious establishment of a two-way security association Secure side channel
Typically short distance (a few meters)
Ensures integrity and confidentiality Alice Bob Exploiting vicinity and the secure side channel Key establishment in ad hoc networks
Taking advantage of common friends : Colin
(common friend
of Alice and Bob) Bob
(Colin’s friend) Alice Taking advantage of common friends trust and already
established key trust and already
established key identifiers and
key material Key establishment in ad hoc networks
What if there’s no common friend? : What if there’s no common friend? Key establishment in ad hoc networks Colin
(a friend Bob) Bob
(Colin’s friend) Alice trust and already
established key key established
via the secure
side channel key material David
(a friend of Alice) trust and already
established key key established
via the secure
side channel key material
A possible implementation : A possible implementation notes:
single trusted party is replaced with two parties trusted by one entity each
if f and g are not colluding, then they cannot compute kuv
both u and v trust at least one of f and g for not colluding Key establishment in ad hoc networks
Pace of establishment of the security associations : Depends on several factors:
Area size
Number of communication partners: s
Number of nodes: n
Number of friends
Mobility model and its parameters (speed, pause times, …)
Established security associations :
eij(t) = 1, if at time t nodes i and j
already share a key, and 0 otherwise Desired security associations :
pij = 1, if i and j wants to setup
a shared key, and 0 otherwise Convergence : Pace of establishment of the security associations Key establishment in ad hoc networks
Mobility models : Random walk
discrete time
simple, symmetric random walk
area: Bounded and toroid grids (33x33, 100x100, 333x333)
number of nodes: 100
Random waypoint
most commonly used in mobile ad hoc networks
continuous time
area size: 1000m x1000m
max speed: 5m/s, 20m/s
pause time: 5s, 100s, 200s
security power range: 5m (SSC), 50m 100m (radio)
Common simulation settings
simulations are run 20 times
confidence interval: 95% p=1/5 p=1/5 p=1/5 p=1/5 p=1/5 Mobility models Key establishment in ad hoc networks
(Restricted) random waypoint : f/8 f/8 f/8 f/8 f/8 f/8 f/8 f/8 1-f
Any point on the plane Restricts the movement of nodes to a set of points with a predefined probability f
Regular random waypoint is a special case (f = 0) area size: 1000m x1000 m
max speed: 5m/s, 20m/s
pause time: 5s, 100s, 200s
restriction probability: 0.1, 0.5, 1
number of restriction points: 20
(Restricted) random waypoint Key establishment in ad hoc networks
Size matters : Size matters tM=O(NlogN) Key establishment in ad hoc networks
Friends help : Friends help Key establishment in ad hoc networks
Security range matters : Security range matters Key establishment in ad hoc networks
Meeting points help : Meeting points help Key establishment in ad hoc networks
Pause time : Pause time Key establishment in ad hoc networks
Can the secure side channel be based on radio? : Can the secure side channel be based on radio? Diffie-Hellman with authentication of messages by the human operator of the devices
Alice and Bob comes together
their devices execute the basic Diffie-Hellman protocol over the radio channel
Alice’s device hashes the concatenation of all messages that it sent and that it received in the protocol
Bob’s device hashes the concatenation of all messages that it received and that it sent in the protocol
the two hash must match
both devices display the hash values in some human readable format
select a set of worlds from a common dictionary based on the hash value
visualize the hash function with a Random Art image
the human operators compare the displayed hash value Key establishment in ad hoc networks
Application of Random Art images : Application of Random Art images the hash value is converted into three two-variable functions
each can be represented as a tree
these formulae define the color value of each pixel of the resulting image Key establishment in ad hoc networks
Can the secure side channel be based on radio? : Can the secure side channel be based on radio? Diffie-Hellman with I-codes
special PHY layer that uses on-off keying (presence of signal means 1, absence of signal means 0)
active adversary can turn a 0 into a 1, but not vice versa
each message sent is encoded in such a way that it contains the same number of 0s and 1s (I-codes)
messages cannot be modified in an unnoticeable way
encoding messages with I-codes ensures the integrity of the communications Man-in-the-Middle is excluded Key establishment in ad hoc networks
Summary : Summary it is possible to establish pairwise shared keys in ad hoc networks without a globally trusted third party
mobility, secure side channels, and friends are helpful
the pace of establishment of the security associations is strongly influenced by the area size, the number of friends, and the speed of the nodes
the proposed solution can easily be implemented with both symmetric and asymmetric crypto
Key establishment in ad hoc networks
Key establishment in sensor networks : Key establishment in sensor networks key types;
establishment of link keys using a short-term master key;
random key pre-distribution:
the basic scheme, and
some improvements;
Key establishment in sensor networks : Key establishment in sensor networks due to resource constraints, asymmetric key cryptography should be avoided in sensor networks
we aim at setting up symmetric keys
requirements for key establishment depend on
communication patterns to be supported
unicast
local broadcast
global broadcast
need for supporting in-network processing
need to allow passive participation
useful key types
node keys – shared by a node and the base station
link keys – pairwise keys shared by neighbors
cluster keys – shared by a node and all its neighbors
network key – a key shared by all nodes and the base station Key establishment in sensor networks
Setting up node, cluster, and network keys : Setting up node, cluster, and network keys node key
can be preloaded into the node before deployment
cluster key
can be generated by the node and sent to each neighbor individually protected by the link key shared with that neighbor
network key
can also be preloaded in the nodes before deployment
needs to be refreshed from time to time (due to the possibility of node compromise)
neighbors of compromised nodes generate new cluster keys
the new cluster keys are distributed to the non-compromised neighbors
the base station generates a new network key
the new network key is distributed in a hop-by-hop manner protected with the cluster keys Key establishment in sensor networks
Design constraints for link key establishment : Design constraints for link key establishment network lifetime
severe constraints on energy consumption
hardware limits
8-bit CPU, small memory
large integer arithmetics are infeasible
no tamper resistance
nodes can be compromised
secrets can be leaked
no a priori knowledge of post-deployment topology
it is not known a priori who will be neighbors
gradual deployment
need to add new sensors after deployment Key establishment in sensor networks
Traditional approaches : Traditional approaches use of public key crypto (e.g., Diffie-Hellman )
limited computational and energy resources of sensors
use of a trusted key distribution server (Kerberos-like)
base station could play the role of the server
requires routing of key establishment messages to and from the base station
routing may already need link keys
unequal communication load on the sensors
base station becomes single point of failure
pre-loaded link keys in sensors
post-deployment topology is unknown
single “mission key” approach
vulnerable to single node compromise
n -1 keys in each of the n sensors
excessive memory requirements
gradual deployment is difficult
doesn’t scale Key establishment in sensor networks
Link key setup using a short-term master key (LEAP) : Link key setup using a short-term master key (LEAP) main assumptions:
any sensor node deployed will not be compromised within Tmin time
any node can discover its neighbors and set up neighbor relationships within Test < Tmin time
typically, Test is a few seconds, so these assumptions make sense in practice
protocol:
key pre-distribution phase
neighbor discovery phase
link key establishment phase
key erasure phase Key establishment in sensor networks
Link key setup using a short-term master key (LEAP) : Link key setup using a short-term master key (LEAP) key pre-distribution phase
before deployment, each node is loaded with KI
each node u derives a node key Ku as Ku = f(KI, u), where f is a one-way function
neighbor discovery phase
when a node deployed, it tries to discover its neighbors by broadcasting a HELLO message
u *: u, Nu
where Nu is a random nonce
each neighbor v replies with
v u: v, mac(Kv, v|Nu)
u can compute f(KI, v) = Kv, and verify the authenticity of the reply Key establishment in sensor networks
Link key setup using a short-term master key (LEAP) : Link key setup using a short-term master key (LEAP) link key establishment phase
u computes the link key Kuv = f(Kv, u)
v computes the same key
no messages are exchanged
note:
u does not authenticate itself to v, but …
only a node that knows KI can compute Kuv
a compromised node that tries to impersonate u cannot know KI (see below)
key erasure phase
Tmin time after its deployment, each node deletes KI and all keys it computed in the neighbor discovery phase Key establishment in sensor networks
Random key pre-distribution – Preliminaries : Random key pre-distribution – Preliminaries Given a set S of k elements, we randomly choose two subsets S1 and S2 of m1 and m2 elements, respectively, from S.
The probability of S1 Ç S2 ¹ Æ is Key establishment in sensor networks
The basic random key pre-distribution scheme : The basic random key pre-distribution scheme initialization phase
a large pool S of unique keys are picked at random
for each node, m keys are selected randomly from S and pre-loaded in the node (key ring)
direct key establishment phase
after deployment, each node finds out with which of its neighbors it shares a key (e.g., each node may broadcast the list of its key IDs)
two nodes that discover that they share a key verify that they both actually posses the key (e.g., execute a challenge-response protocol)
path key establishment phase
neighboring nodes that do not have a common key in their key rings establish a shared key through a path of intermediaries
each link of the path is secured in the direct key establishment phase Key establishment in sensor networks
Setting the parameters : Setting the parameters connectivity of the graph resulting after the direct key establishment phase is crucial
a result from random graph theory [Erdős-Rényi]:
in order for a random graph to be connected with probability c (e.g., c = 0.9999), the expected degree d of the vertices should be:
(1)
in our case, d = pn’ (2), where p is the probability that two nodes have a common key in their key rings, and n’ is the expected number of neighbors (for a given deployment density)
p depends on the size k of the pool and the size m of the key ring
(3)
c d p k, m (1) (2) (3) Key establishment in sensor networks
Setting the parameters – an example : Setting the parameters – an example number of nodes: n = 10000
expected number of neighbors: n’ = 40
required probability of connectivity after direct key establishment: c = 0.9999
using (1):
required node degree after direct key establishment: d = 18.42
using (2):
required probability of sharing a key: p = 0.46
using (3):
appropriate key pool and key ring sizes:
k = 100000, m = 250
k = 10000, m = 75
… Key establishment in sensor networks
Qualitative analysis : Qualitative analysis advantages:
parameters can be adopted to special requirements
no need for intensive computation
path key establishment have some overhead …
decryption and re-encryption at intermediate nodes
communication overhead
but simulation results show that paths are not very long (2-3 hops)
no assumption on topology
easy addition of new nodes
disadvantages:
node capture affects the security of non-captured nodes too
if a node is captured, then its keys are compromised
these keys may be used by other nodes too
if a path key is established through captured nodes, then the path key is compromised
no authentication is provided Key establishment in sensor networks
Improvements: q-composite rand key pre-distribution : Improvements: q-composite rand key pre-distribution basic idea:
two nodes can set up a shared key if they have at least q common keys in their key rings
the pairwise key is computed as the hash of all common keys
advantage:
in order to compromise a link key, all keys that have been hashed together must be compromised
disadvantage:
probability of being able to establish a shared key directly is smaller (it is less likely to have q common keys, than to have one)
key ring size should be increased (but: memory constraints) or key pool size should be decreased (but: effect of captured nodes)
Key establishment in sensor networks
q-composite scheme: Simulation results : q-composite scheme: Simulation results m = 200, p = 0.33 taken from: H. Chan and A. Perrig and D. Song, "Random key predistribution
schemes for sensor networks", IEEE Security and Privacy Symp. (Oakland),
2003 Key establishment in sensor networks
Improvements: Multipath key reinforcement : Improvements: Multipath key reinforcement basic idea:
establish link keys through multiple disjoint paths
assume two nodes have a common key K in their key rings
one of the nodes sends key shares k1, …, kj to the other through j disjoint paths
the key shares are protected during transit by keys that have been discovered in the direct key establishment phase
the link key is computed as K + k1 + … + kj
Key establishment in sensor networks
Improvements: Multipath key reinforcement : Improvements: Multipath key reinforcement advantages:
in order to compromise a link key, at least one link on each path must be compromised increased resilience to node capture
disadvantages:
increased overhead
note:
multipath key reinforcement can be used for path key setup too
Key establishment in sensor networks
Multipath scheme: Simulation results : Multipath scheme: Simulation results m = 200, p = 0.33
Key establishment in sensor networks taken from: H. Chan and A. Perrig and D. Song, "Random key predistribution
schemes for sensor networks", IEEE Security and Privacy Symp. (Oakland),
2003
Polynomial based key pre-distribution : Polynomial based key pre-distribution let f be a bivariate t-degree polynomial over a finite field GF(q), where q is a large prime number, such that f(x, y) = f(y, x)
each node is pre-loaded with a polynomial share f(i, y), where i is the ID of the node
any two nodes i and j can compute a shared key by
i evaluating f(i, y) at point j and obtaining f(i, j), and
j evaluating f(j, y) at point i and obtaining f(j, i) = f(i, j)
this scheme is unconditionally secure and t-collusion resistant
any coalition of at most t compromised nodes knows nothing about the shared keys computed by any pair of non-compromised nodes
any pair of nodes can establish a shared key without communication overhead (if they know each other’s ID)
memory requirement of the nodes is (t +1) log(q)
problem: t is limited by the memory constraints of the sensors Key establishment in sensor networks
Polynomial based random key pre-distribution : Polynomial based random key pre-distribution operation:
let S be a pool of bivariate t-degree polynomials
for each node i, we pick a subset of m polynomials from the pool
we pre-load into node i the polynomial shares of these m polynomials computed at point i
two nodes that have polynomial shares of the same polynomial f can establish a shared key f(i, j)
if two nodes have no common polynomials, they can establish a shared key through a path of intermediaries
advantage:
can tolerate the capture of much more than t nodes (t can be smaller, but each node needs to store m polynomials)
in order to compromise a polynomial, the adversary needs to obtain t + 1 shares of that polynomial
it is very unlikely that t + 1 randomly captured nodes have all selected the same polynomial from the pool
Key establishment in sensor networks
Simulation results : Simulation results m = 200, p = 0.33 taken from D. Liu and P. Ning, “Establishing pairwise keys in distributed sensor
networks", ACM CCS, 2003. Key establishment in sensor networks
Matrix based key pre-distribution (Blom’s scheme) : Matrix based key pre-distribution (Blom’s scheme) let G be a (t + 1)×n matrix over a finite field GF(q) (where n is the size of the network)
let D be a random (t +1)×(t +1) symmetric matrix over GF(q)
G is public, D is secret
let A = (DG)T and K = AG
K is a symmetric matrix, because
K = AG = (DG)TG = GTDTG = GTDG = GTAT = (AG)T = KT
each node i stores the i-th row of A
any two nodes i and j can compute a shared key Kij
i computes A(i,.)G(.,j) = Kij
j computes A(j,.)G(.,i) = Kji = Kij Key establishment in sensor networks
Matrix based random key pre-distribution : Matrix based random key pre-distribution G is as before
D1, …, Dk are random (t +1)×(t +1) symmetric matrices
Av = (DvG)T and {Av} is the pool (of spaces)
for each node i, we pick a random subset of the pool and pre-load in the node the i-th row of the selected matrices (i.e., Av(i,.) for each selected v)
if two nodes i and j both selected a common matrix Av, then they can compute a shared key using Blom’s scheme
if two nodes don’t have a common space, they can setup a key through intermediaries Key establishment in sensor networks
Simulation results : Simulation results m = 200, p = 0.33 taken from W. Du and J. Deng and Y. S. Han and P. K. Varshney, "A pairwise
key pre-distribution scheme for wireless sensor networks", ACM CCS, 2003
Key establishment in sensor networks
Assumptions revisited (and more) [DiPietro et al.] : Assumptions revisited (and more) [DiPietro et al.] the connectivity graph resulting after the first phase of the basic protocol is not a random graph (in the sense of Erdős-Rényi)
an edge between two nodes exists if they have at least one common key AND they are in power range of each other
the Erdős-Rényi theorem may not hold for these types of graphs
almost sure connectivity after the first phase of the basic protocol is ensured if
m2 / k = c log(n) / n
k > n-1
m > 4
Key establishment in sensor networks
Assumptions revisited (and more) [DiPietro et al.] : Assumptions revisited (and more) [DiPietro et al.] a definition of security:
a network is redoubtable, if the probability that compromising a sub-linear fraction of nodes (uniformly chosen at random) can compromise a constant fraction of links in the network is 0
a network is redoubtable if m/k ~ 1/n
a practical choice of parameters:
m = log(n)
k = n log(n) Key establishment in sensor networks
Summary : Summary
in sensor networks, we need different types of keys
node keys, cluster keys, and network keys can be established relatively easily using the technique of key pre-loading and using already established link keys
link keys can be established using a short-term master key or with the technique of random key pre-distribution
Key establishment in sensor networks