Transcript A Pairwise Key Pre-Distribution Scheme for Wireless Sensor Networks

Securing
Wireless Sensor Networks
Wenliang (Kevin) Du
Department of Electrical Engineering and
Computer Science
Syracuse University
Overview
• Overview of Wireless Sensor Networks (WSN).
• Security in wireless sensor networks.
– Security risks
– Security objectives
– Technology limitations
• Key management in WSN
Wireless Sensor Networks
• Motes
– Tiny computing platform
– Wireless communication
– Low power operation (using battery)
• Sensors
– Sensing the environment (light, motion, etc.)
• Networks
– Self configuring and maintaining connectivity
– Routing
– Distributed sensing and computing
Sensor Network Applications
• Environment monitoring
– Habitat monitoring
– Forrest fire monitoring
• Animal monitoring
• Structure and equipment monitoring
• Supply chain monitoring
– Manufacturing flows, asset tracking
• Battle field surveillance
Enabling Technologies
• Very low power electronics (μW)
• Very low cost hardware ($)
• Very easy to develop, install, maintain.
Mica2, Mica2Dot, MicaZ
Motes
• CPU: ATMega128L 8-bit, 8MHz,
• 4KB EEPROM, 4KB RAM, 128KB Flash
• Chipcon CC100, C2420 radio.
TelosB Mote
•
•
•
•
•
CPU: 8 MHz TI MSP430
48 KB Flash memory
10 KB RAM
Chipcon CC2420 radio, 2.4GHz
IEEE 802.15.4
Intel® Mote
• CPU: ARM7TDMI, 12MHz, 32-bit
• 512 KB Flash, 64kB RAM
• Bluetooth 1.1 radio, ~30m range
• 2.4 GHz antenna
Gateway (Stargate)
• 400 Mhz Intel PXA255 Processor
– Same processor found in IPAQ & Dell Axim
• Small, 3.5” x 2.5’ form factor
• Embedded Linux BSP
Technologies for Energy Saving
• Other source of energy
– Solar energy
– Vibration
• Multi-hop routing
• Sleeping
• Dynamic voltage scaling
Operating System and Programming
Language
• TinyOS
– Developed by UC Berkeley
– “industry standard”
– Freely-available and open source
• Programming Language: NesC
– An extension of C
– Event driven
– concurrency model enables the motes to be
programmed to handle many events in parallel
Motes on the Market
• $50 - $100 at current price:
– prototypes developed by Intel Research and UC
Berkeley
• $5 over the next five years:
– Through re-engineering, Moore’s Law, and
volume production
• Crossbow Technology Inc: first commercial
manufacture of motes.
Security in Sensor Networks
Securing WSN
• Security objectives in sensor networks
– Unique security problems.
• Why not use existing security mechanisms?
– Unique features of sensor networks
– Call for unique security solutions.
What should we protect?
• The CIA Model:
– Confidentiality
– Integrity
– Availability
• What do they mean in sensor networks?
– Unique meaning
– Difference and similarity with traditional
networks.
Confidentiality and Privacy
• Contents of data
– Eavesdropping
• Source of data
– Example: the pander-hunter problem
– Traffic analysis
• Destination of data
– Finding and destroying the base stations
Integrity
• Integrity of broadcast
– Broadcast authentication
•
•
•
•
Integrity of communication among sensors
Integrity of sensing
Integrity of nodes
Integrity of location
– Location discoveries, e.g. beacon-based schemes
– Location verification
• Integrity of time
– Time synchronization
Availability
• Physically destroying sensors
• Denial of Service (DOS) Attacks
–
–
–
–
Attack at physical layer: jamming
Attack at link layer (e.g. violating protocols)
Attack at routing layer (e.g., refusing to route)
Attack at application layer
• Energy consumption attacks
– Depriving sleep
– Making CPU busy
Questions
• Don’t we have similar problems in traditional
networks?
• Why don’t we use similar solutions?
• Can’t we use encryption to solve most of the
problems?
* Unique properties of sensor networks make
the problems and solutions unique.
Unique Properties:
Broadcasting
• Main communication channel: Broadcasting
– One-to-many and one-to-one communication
– The channel is easy to access
•
•
•
•
Eavesdropping
Message injection
Traffic analysis
Jamming
• Encrypting broadcast is hard
• Broadcast Authentication is hard
Unique Properties:
Physical Security of Nodes
• Nodes: Low-Cost, Commodity Hardware
– Ease of access to internal node state
– Physical node protection is impractical
• Nodes are unattended
– Adversary can capture and tamper with nodes
– Detection of tampering in real-time is expensive
Unique Properties:
Physical Security of Nodes
Two Extreme Examples
Low end: Smart Cards (< $40)
- no tamper resistance
- non-invasive phys. attacks
- side-channel (timing, DPA)
High end: IBM 4758 co-proc. (~ $4K)
- tamper resistance, real time resp.
- independent battery, secure clock
- battery-backed RAM (BBRAM)
- wrapping: several layers of non-metallic
- unusual operating conditions
- temperature, power clock glitches grid of conductors in a grounded shield
- invasive phys. attacks
- chip removal from plastic cover
- microprobes, electron beams
- reduce detectable EM emanations
- tamper detection: sensors (+ battery)
- temp., humidity, pressure, voltage,
clock, ionizing radiation
- response: erase BBRAM, reset device
Unique Properties:
Physical Security of Nodes
• Friends or Enemy?
– Enemy's malicious nodes
– Good nodes turns malicious (compromised)
– Sybil Attacks: A node takes on multiple
identities
• Encryption cannot solve this problem
– Protecting secret keys depends on physical
security
Unique Properties:
Trusted Infrastructure
• Many security solutions (for traditional networks)
depends on trusted infrastructures
–
–
–
–
Public Key Infrastructure (PKI): certificate servers
Key distribution center: Kerberos
Location: GPS satellites
Time synchronization: trusted time servers
• Not Practical for Sensor Networks
– High cost
– Main target of attacks: difficult to protect
Unique Properties:
Constraints on Sensor Nodes
• Sensor Node Constraints
– Energy
– CPU power
– Memory
• Asymmetric Arm Race
– Sensors against powerful attackers
Sensor Node Constraints
• Battery Power Constraints
– Computational Energy Consumption
• Crypto algorithms
• Public key vs. Symmetric key
– Communications Energy Consumption
• Exchange of keys, certificates, etc.
• Per-message additions (padding, signatures,
authentication tags)
Constraints (Cont.)
Public Key Encryption
• Slow
– 1000 times slower than symmetric encryption
• Hardware is complicated
• Energy consumption is high
Processor
Energy Consumption (mJ/Kb)
RSA/E/V
RSA/D/S
AES
MIPS R4000
0.81
16.7
0.00115
MC68328
42
840
0.0130
Memory Constraints
• Program Storage and Working Memory
– Embedded OS, security functions (Flash)
– Working memory (RAM)
• Mica2 Motes:
• 128KB Flash and 4KB RAM
Key Management Problem
Key Management Problem
Sensors
Deploy
Key Management Problem
Sensors
Deploy
Secure Channels
General Approaches
• Trusted-Server Schemes
– Finding trusted servers is difficult.
• Public-Key Schemes
– Expensive and impractical for many sensors.
• Key Pre-distribution Schemes
Key Pre-distribution



Loading Keys into sensor nodes prior to
deployment
Two nodes find a common key between them after
deployment
Challenges



Memory/Energy efficiency
Security: nodes can be compromised
Scalability: new nodes might be added later
Naïve Solutions

Master-Key Approach



Memory efficient, but low security.
Needs Tamper-Resistant Hardware.
Pair-wise Key Approach



N-1 keys for each node (e.g. N=10,000).
Security is perfect.
Need a lot of memory and cannot add new
nodes.
A Probabilistic Approach
Key Pool
Each node
randomly
selects m keys
A
S
B
C
D
E
• When |S| = 10,000, m=75
Pr (two nodes have a common key) = 0.50
Establishing Secure Channels
A
B
C
Key Pre-Distribution Using
Deployment Knowledge
Observations and Objectives
A
B
F
Property:
Pr(A, B) = Pr(A, F)
Our objective: Pr(A, B) >> Pr(A, F)
Using deployment knowledge
Modeling Deployment Knowledge
Deployment points for a group of sensors
I
A
J
F
Key Pre-distribution Scheme
Key Pools
Key Sharing Among Key Pools
Horizontal
a
B
A
b
Vertical
a
D
G
a
a
b
C
b
a
a
H
F
Diagonal
I
b
b
Local Connectivity
Network Resilience
• What is the damage when x nodes are
compromised?
– These x nodes contain keys that are used by the
good nodes.
– What percentage of communications can be
affected?
Network Resilience
A Pairwise
Key Pre-distribution Scheme
Objectives
• Pairwise key pre-distribution scheme.
– Each pair of sensor share a unique secret key
– Can be used for Authentication
• Our Approach:
– We use Blom Scheme to achieve Pairwise
– We use Random Key Selection scheme to
improve performance and resilience
Blom Scheme
• Public matrix G
• Private matrix D (symmetric).
D
G
+1
N
Let A = (D G)T
A G = (D G)T G = GT DT G = GT D G = (A G)T
Blom Scheme
A = (D G)T
G
j
i
i
+1
Kij
=
X
j
(D G)T G
N
Node i carries:
Node j carries:
N
Kji
N
Properties of Blom Scheme
• Blom’s Scheme
–
–
–
–
Network size is N
Any pair of nodes can directly find a secret key
Tolerate compromise up to  nodes
Need to store +2 keys
• Challenge: Can we increase  without
increasing the storage usage.
Multiple Space Scheme
Key-Space Pool
 spaces
 spaces
(D1, G)
 spaces
(D2, G)
Two nodes can find
a pairwise key if they
carry a common key space!
(D, G)
Measure Local Connectivity
plocal = the probability that two neighboring nodes
can find a common key.
plocal  1 
( )(  )
( ) 2

((  )!) 2
(  2 )! !
Plocal for different  and 
Resilience (p = 0.33, m=200)
Blom
Resilience (p = 0.50, m =200)
Blom
Summary
• Overview of sensor networks technologies
• Security is unique for sensor networks
• Sensor networks’ unique properties make the
security problems and solution unique.
• Security is quite different from traditional
(wired) networks.