02-06-2012, 04:36 PM
Distributed Detection of Node Replication Attacks in Sensor Networks
[attachment=24047]
Sensor Networks
Thousands of nodes, each with a CPU, ~4 KB of RAM, a radio and one or more sensors (e.g., temperature, motion, sound)
Applications: burglar alarms, emergency response, military uses
Node Characteristics:
Low cost
No tamper resistance
Limited battery life
Easy to deploy
Attacks on Sensor Networks
Replication Attacks
Capturing many nodes is hard
Instead, capture one node and copy it
Other attacks not in scope of this work
Introducing nodes with new IDs - this is readily preventable:
Admin provides each node with a certificate
ID based on keys
Other Sybil defenses [Newsome04]
Jamming attacks
Partitioning attacks
We assume legitimate nodes
form a connected component
Replication is Easy
Only need to capture one node
Offline attack to extract node’s secrets
Transfer secrets to generic nodes
Deploy clones
Repercussions
Clones know everything compromised node knew
Adversary can …
Inject false data or suppress legitimate data
Spread blame for abnormal behavior
Revoke legitimate nodes using aggregated voting
Monitor communication
Our Contributions
Thwart replication attacks using entirely distributed mechanisms
First use of emergent algorithms to provide robust security properties in sensor networks
Resilient even against an adaptive adversary
(i.e. adversary knows the protocol and can selectively compromise additional sensors)
Relies on the Birthday Paradox and the network topology
No central points of failure
Efficient Solutions
Comparable to centralized detection
Assumptions
Public key infrastructure
Occasional elliptic curve cryptography is reasonable [Malan04]
Can be replaced with symmetric mechanisms
Network employs geographic routing
Does not require GPS! [Doherty01]
Works with synthetic coordinates [Rao03, Newsome03]
Nodes are primarily stationary
Goals
Detect replication with high probability
After protocol concludes, legitimate nodes have revoked replicas
Secure against adaptive adversary
Unpredictable to adversary
No central points of failure
Minimize communication overhead
Previous Approaches Insufficient
Central Detection [EscGli02]
Each node sends neighbor list to a central base station
Base station searches lists for duplicates
Disadvantages
Some applications may not use base stations
Single point of failure
Exhausts nodes near base station (and makes them attack targets)
Localized Detection [ChPeSo03]
Neighborhoods use local voting protocols to detect replicas
Disadvantage
Replication is a global event that cannot be detected in a purely local fashion
Emergent Properties
Properties that only emerge through collective action of multiple nodes
Highly robust
No central point of failure
Difficult for adversary to attack
Emergent behavior is an attractive approach for thwarting an unpredictable and adaptive adversary
Approach Overview
Step 1: Announce locations
Each node signs and broadcasts its location to neighbors
Location = (x,y), virtual coordinates, or neighbor list
Nodes must participate or neighbors will blacklist them
Step 2: Detect replicas
Uses emergent protocol
Ensures at least one “witness” node receives two conflicting location claims
Step 3: Revoke replicas
Witness floods network with conflicting location claims
Signatures prevent spoofing or framing
Randomized Multicast Protocol
Each node signs and broadcasts its location to neighbors
Each neighbor forwards location to “witness” nodes
Witness chosen at random by selecting random geographic point and forwarding message to node closest to the point
Each neighbor selects ~ witnesses for a total of
Birthday Paradox implies location claims from a cloned node and its clone will collide with high probability
Conflicting location claims are evidence for revoking clones
Signatures prevent forgery of location claims
Randomized Multicast Analysis
High probability of detection
2 replicas (R=2), w = n, PDetect ≥ 95%,
Decentralized and randomized
Moderate communication overhead
Each node’s location sent to n witnesses
Path between two random points in the network is O( n ) hops on average
Results in O(n) message hops per node
Line-Selected Multicast Protocol
In a sensor network, nodes route data as well as collect it
Again, neighbors forward location claim to “witness” nodes
Each intermediate node checks for a conflict and forwards the location claim
If any two “lines” intersect, the conflicting location claims provide evidence for revoking clones
Line-Selected Multicast Analysis
High probability of intersection for two randomly drawn lines in the plane
Only need a constant number of lines
(e.g. for 5 lines/node, PDetect ≥ 95%)
Decentralized and randomized
Minimal communication
Line segments O( n) on average
Only requires O( n) message hops per node
[attachment=24047]
Sensor Networks
Thousands of nodes, each with a CPU, ~4 KB of RAM, a radio and one or more sensors (e.g., temperature, motion, sound)
Applications: burglar alarms, emergency response, military uses
Node Characteristics:
Low cost
No tamper resistance
Limited battery life
Easy to deploy
Attacks on Sensor Networks
Replication Attacks
Capturing many nodes is hard
Instead, capture one node and copy it
Other attacks not in scope of this work
Introducing nodes with new IDs - this is readily preventable:
Admin provides each node with a certificate
ID based on keys
Other Sybil defenses [Newsome04]
Jamming attacks
Partitioning attacks
We assume legitimate nodes
form a connected component
Replication is Easy
Only need to capture one node
Offline attack to extract node’s secrets
Transfer secrets to generic nodes
Deploy clones
Repercussions
Clones know everything compromised node knew
Adversary can …
Inject false data or suppress legitimate data
Spread blame for abnormal behavior
Revoke legitimate nodes using aggregated voting
Monitor communication
Our Contributions
Thwart replication attacks using entirely distributed mechanisms
First use of emergent algorithms to provide robust security properties in sensor networks
Resilient even against an adaptive adversary
(i.e. adversary knows the protocol and can selectively compromise additional sensors)
Relies on the Birthday Paradox and the network topology
No central points of failure
Efficient Solutions
Comparable to centralized detection
Assumptions
Public key infrastructure
Occasional elliptic curve cryptography is reasonable [Malan04]
Can be replaced with symmetric mechanisms
Network employs geographic routing
Does not require GPS! [Doherty01]
Works with synthetic coordinates [Rao03, Newsome03]
Nodes are primarily stationary
Goals
Detect replication with high probability
After protocol concludes, legitimate nodes have revoked replicas
Secure against adaptive adversary
Unpredictable to adversary
No central points of failure
Minimize communication overhead
Previous Approaches Insufficient
Central Detection [EscGli02]
Each node sends neighbor list to a central base station
Base station searches lists for duplicates
Disadvantages
Some applications may not use base stations
Single point of failure
Exhausts nodes near base station (and makes them attack targets)
Localized Detection [ChPeSo03]
Neighborhoods use local voting protocols to detect replicas
Disadvantage
Replication is a global event that cannot be detected in a purely local fashion
Emergent Properties
Properties that only emerge through collective action of multiple nodes
Highly robust
No central point of failure
Difficult for adversary to attack
Emergent behavior is an attractive approach for thwarting an unpredictable and adaptive adversary
Approach Overview
Step 1: Announce locations
Each node signs and broadcasts its location to neighbors
Location = (x,y), virtual coordinates, or neighbor list
Nodes must participate or neighbors will blacklist them
Step 2: Detect replicas
Uses emergent protocol
Ensures at least one “witness” node receives two conflicting location claims
Step 3: Revoke replicas
Witness floods network with conflicting location claims
Signatures prevent spoofing or framing
Randomized Multicast Protocol
Each node signs and broadcasts its location to neighbors
Each neighbor forwards location to “witness” nodes
Witness chosen at random by selecting random geographic point and forwarding message to node closest to the point
Each neighbor selects ~ witnesses for a total of
Birthday Paradox implies location claims from a cloned node and its clone will collide with high probability
Conflicting location claims are evidence for revoking clones
Signatures prevent forgery of location claims
Randomized Multicast Analysis
High probability of detection
2 replicas (R=2), w = n, PDetect ≥ 95%,
Decentralized and randomized
Moderate communication overhead
Each node’s location sent to n witnesses
Path between two random points in the network is O( n ) hops on average
Results in O(n) message hops per node
Line-Selected Multicast Protocol
In a sensor network, nodes route data as well as collect it
Again, neighbors forward location claim to “witness” nodes
Each intermediate node checks for a conflict and forwards the location claim
If any two “lines” intersect, the conflicting location claims provide evidence for revoking clones
Line-Selected Multicast Analysis
High probability of intersection for two randomly drawn lines in the plane
Only need a constant number of lines
(e.g. for 5 lines/node, PDetect ≥ 95%)
Decentralized and randomized
Minimal communication
Line segments O( n) on average
Only requires O( n) message hops per node