Transcript C N+1

Security and Cooperation in
Wireless and Mobile Networks
Richard Yang
1
Admin.
 Homework 4

due Friday Dec. 8th
2
Recap
 TinyOS
 software
as hardware components
 Mobile CPU scheduling

dynamic voltage scaling
3
Mobile File Systems
4
Discussion
 What challenges does the file system face in
wireless/mobile environment?
5
Problems Facing File System
 Disconnected/weakly connected file system
 read miss
• stalls progress (the user has to stop working)

synchronization/consistency issues
• may need to synchronize multiple copies of the same file
• if multiple users, may need to solve consistency
problems
 Heterogeneous device types
 each device has its own file system and naming
convention, e.g., digital camera, ipod
6
Some Approaches
 Handling read miss
 explicit user file selection, e.g., MS briefcase
 automatic hoarding, e.g., CODA, SEER
 Handling synchronization/consistency issues
 keep modification logs and develop merge tools, e.g., Bayou
 efficient file comparisons and merging, e.g., rsync, low
bandwidth file system (LBFS )
 Handling heterogeneous device types
 mask the differences , e.g., EnsemBlue
7
Security and Cooperation in
Wireless and Mobile Networks
8
Introduction
 This is a vast and active field, a course by
itself
 A good recent book is
Thwarting Malicious and Selfish Behavior
in the Age of Ubiquitous Computing, by Levente
Buttyan and Jean-Pierre Hubaux, Cambridge
University Press, to appear in 2007.
 available at: http://secowinet.epfl.ch/

9
Generic Network Security and
Cooperation Issues
availability
integrity
confidentiality
authenticity; incentive-compatibility 10
Why is Security Challenging in
Wireless Networks?
 No inherent physical protection
 physical connections between devices are replaced by
logical associations
 sending and receiving messages do not need physical access
to the network infrastructure (cables, hubs, routers, etc.)
 Broadcast communications
 wireless usually means radio, which has a broadcast nature
 transmissions can be overheard by anyone in range
 anyone can generate transmissions,
• which will be received by other devices in range
• which will interfere with other nearby transmissions
 Thus it is easier to implement jamming,
eavesdropping, injecting bogus messages, and
replaying previously recorded messages
11
Why is Security Challenging in
Mobile Networks?
 Since mobile devices typically have limited
resources (e.g., CPU cycles, battery supply),
the designer might want to select simple
security mechanisms
 an
interesting example: TELSA
 However, this may lead to serious security
flaws

bad example: Wired Equivalent Protection (WEP),
the original security protocol for 802.11
12
WEP: A Bad Example
13
802.11 Message Flow
data messages
protected by WEP
14
Wired Equivalent Privacy (WEP)
 WEP was intended to provide comparable
confidentiality to a traditional wired
network, thus the name
 WEP implements message confidentiality and
integrity
 WEP encryption is used in 802.11
authentication
15
WEP Security
 WEP confidentiality

through encryption using RC4, a stream-based
encryption algorithm using a shared key
 WEP integrity
 through message check sum using encrypted
cyclic redundancy check (CRC)
 WEP authentication
 through challenge/response
16
WEP Encryption
 For each message to be sent:

RC4 is initialized with the shared secret between
station STA and access point (AP)
• WEP allows up to 4 shared keys
RC4 produces a pseudo-random byte sequence
(key stream) from the shared key
 This pseudo-random byte sequence is XORed to
the message

17
WEP Encryption
 To avoid using the same key stream, WEP
encrypts each message with a different key
stream

the RC4 generator is initialized with the shared
secret plus a 24-bit IV (initial value)
• shared secret is the same for each message
• 24-bit IV for each message
• there is no specification on how to choose the IV;
sender picks the IV value
18
WEP Integrity
 WEP integrity protection is based on
computing ICV (integrity check value) using
CRC and appended to the message
 The message and the ICV are encrypted
together
19
WEP
CRC
message | ICV
IV
secret key
RC4
KS
encode
IV
message | ICV
decode
IV
secret key
RC4
KS
message | ICV
check
CRC
20
Active Attack on WEP: IV Replay Attacks
 A known plain-text message is
sent to an observable wireless
LAN client (e.g., an e-mail
message)
 The network attacker will sniff
the wireless LAN looking for the
predicted cipher-text
 The network attacker will find
the known frame, derive the key
stream (corresponds to the give
IV+K), and reuse the key stream
 The network attacker can "grow"
the key stream
21
Active Attack on WEP: Bit-Flipping Attack
 The attacker sniffs a frame on the wireless LAN
 The attacker captures the frame and flips random bits in the data









payload of the frame
The attacker modifies the ICV (detailed later)
The attacker transmits the modified frame
The access point receives the frame and verifies the ICV based on
the frame contents
The AP accepts the modified frame
The destination receiver de-encapsulates the frame and processes the
Layer 3 packet
Because bits are flipped in the higher layer packet, the Layer 3
checksum fails
The receiver IP stack generates a predictable ICMP error
The attacker sniffs the wireless LAN looking for the encrypted error
message
Upon receiving the error message, the attacker derives the key
stream as with the IV replay attack
22
Bit-Flipping Attack
23
Generating Valid CRC
 The crucial step of the flipping attack is to
allow the frame to pass the ICV check of the
AP
 Unfortunately, the CRC algorithm allows
generating valid encrypted ICV after bit
flipping
24
Bypassing Encrypted ICV
 CRC is a linear function wrt to XOR:
CRC(X  Y) = CRC(X)  CRC(Y)
- Attacker observes (M | CRC(M))  K where K
is the key stream output
-
for any DM, the attacker can compute CRC(DM)
hence, the attacker can compute:
([M | CRC(M])  K)  [DM | CRC(DM)]
= ([M  DM) | (CRC(M)  CRC(DM)])  K
= [M  DM) | CRC(M DM)]  K
25
WEP Authentication
 Two authentication modes

open authentication --- means no authentication !
• an AP could use SSID authentication and MAC address
filtering, e.g., at Yale, but this is ineffective

shared key authentication based on WEP
26
WEP Shared Key Authentication
 Shared key authentication is based on a challenge-
response protocol:
…
AP  STA: r
STA  AP: (IV | r)  K
…
where K is a 128 bit RC4 output on IV and the shared secret
 An attacker can compute r  (r  K) = K
 Then it can use K to impersonate STA later:
…
AP  attacker: r’
attacker  AP: (IV | r’)  K
…
27
WEP: Lessons
 WEP has other problems, e.g., short IV space, weak
RC4 keys
 Engineering security protocols is difficult
 one can combine otherwise OK building blocks in a wrong
way and obtain an insecure system at the end
• example 1:
– stream ciphers alone are OK
– challenge-response protocols for entity authentication are OK
– but they shouldn’t be combined
• example 2:
– encrypting a message digest to obtain an ICV is a good principle
– but it doesn’t work if the message digest function is linear wrt to the
encryption function
 Avoid the use of WEP (as much as possible)
28
Fixing WEP
 After the collapse of WEP, Wi-Fi Protected
Access (WPA) was proposed in 2003
 Then the full 802.11x standard (also called
WPA2) was proposed in 2004
 But WEP is still in wide use
29
TELSA: A Positive Example
30
Digital Signatures Do Not Work
 Problem statement: authentication of packets
 The typical approach in the Internet is to attach
a digital signature on each packet
 However, signatures are expensive, e.g., RSA
1024 on a 2.1 GHz desktop:

high signature cost (~5 ms)

high communication cost (128 bytes/packet)
 More expensive on low-end processors
http://www.cryptopp.com/benchmarks.html
TESLA
 Timed Efficient Stream Loss-tolerant Authentication
 Uses only symmetric cryptography
Basic Authentication Mechanism
F: public one-way function; MAC: message digest function
1: Verify K
F(K)
Authentic
Commitment
P
2: Verify
MAC
K
disclosed
MAC(K,P)
3: P Authentic!
t
TELSA Security Condition
 Sender distributes initial commitment and key disclosure
schedule using, say, digital signature
 Security condition (for packet P):
on arrival of P, receiver is certain that sender did not
yet disclose K
 If security condition not satisfied, drop packet
TESLA: Example
Keys disclosed 2 time intervals after use
Authenticate K3
K3
F
K4
Time 4
P1
F
K5
K6
Time 5
Time 6
K7
Time 7
P2
P3
P4
P5
K2 K2
K3
K4
K5
Verify MACs
t
TESLA Summary
 Advantages
 low overhead
• communication (~ 20 bytes)
• computation (~ 1 MAC computation per packet)

tolerate packet loss
 Problems
 time synchronization
 delayed authentication
Secure Efficient Ad hoc Distance
Vector (SEAD)
 Uses one-way hash chains to authenticate
metric and sequence number for DSDV
 Assumes a limit k-1 on metric (as in other
distance vector protocols such as RIP, where
k=16)

metric value infinity can be represented as k
SEAD Metric Authenticators
 Each node generates a hash chain and
distributes the last element (CN+1) to allow
verification:



chain values CN-k+1, …, CN authenticate metrics
0 through k-1 for sequence number 1
CN-2k+1,…CN-k authenticate metrics 0 through k-1
for sequence number 2
CN-ik+1,…CN-(i-1)k authenticate metrics 0 through k-1
for sequence number i
C0
C1
C2
C3
C4
C5
C6
C7
C8
C9
C10
C11
C12
SEAD Metric Authenticators
 Each node generates a hash chain and
distributes the last element (CN+1) to allow
verification:



Chain values CN-k+1, …, CN authenticate metrics
0 through k-1 for sequence number 1
CN-2k+1,…CN-k authenticate metrics 0 through k-1
for sequence number 2
CN-ik+1,…CN-(i-1)k authenticate metrics 0 through k-1
for sequence number i
C0
C1
C2
C3
C4
C5
C6
C7
C8
C9
C10
C11
C12
SEAD Metric Authenticators
 Each node generates a hash chain and
distributes the last element (CN+1) to allow
verification:



Chain values CN-k+1, …, CN authenticate metrics
0 through k-1 for sequence number 1
CN-2k+1,…CN-k authenticate metrics 0 through k-1
for sequence number 2
CN-ik+1,…CN-(i-1)k authenticate metrics 0 through k-1
for sequence number i
C0
C1
C2
C3
C4
C5
C6
C7
C8
C9
C10
C11
C12
SEAD Metric Authenticators
 Each node generates a hash chain and
distributes the last element (CN+1) to allow
verification:



Chain values CN-k+1, …, CN authenticate metrics
0 through k-1 for sequence number 1
CN-2k+1,…CN-k authenticate metrics 0 through k-1
for sequence number 2
CN-ik+1,…CN-(i-1)k authenticate metrics 0 through k-1
for sequence number i
C0
C1
C2
C3
C4
C5
C6
C7
C8
C9
C10
C11
C12
SEAD Metric Authenticators
Within a sequence number i:
 CN-ik+1 represents metric 0
 CN-ik+2 represents metric 1
 CN-ik+m+1 represents metric m
 CN-ik+k represents metric k-1
When a node receives a routing update:
Metric 0
Metric 1
Metric 2
• It first checks the metric authenticator
• If the update is to be accepted:
– It increments
C9 the metric
C10 byCone
11
– and hashes the authenticator
– then adds the metric and authenticator to routing table
Cooperation in Wireless, Mobile
Networks
43
Cooperation in Wireless Networks
 A special case of “security attack” is by rational
nodes

drop packets, mis-represent information
 Motivation
 wireless networks have limited capacity
 wireless nodes have limited resource—battery power
 unlike the Internet, where commercial relationship is
worked out, many ad hoc network nodes belong to different
users and have incentive to forward others’ traffic
• similar free-riding problems in P2P applications
44
Cooperation in Wireless Networks
 Discussion: how to handle non-malicious but
selfish nodes?
45
Payment-based Routing
 The first setup (kind of the oracle version)

centralized authority: computation and payment
 Each node has a (private energy/transmission) cost of sending
one packet to a neighbor
 The network (authority)
pays the nodes so that
they will forward traffic
from a source to a
destination

the objective of the
authority is to choose
the lowest cost path
• assume cost reflects energy
• thus extending network
life time/maximizing
capacity—the social welfare
46
Node’s Utility
 Assume each node wants to maximize its utility
 Utility is the sum of all source-destination pairs
 The utility of being on the path P of a source-
destination pair:
ui  pi  ci 1 (i )
P
where
- pi is the amount the network pays node i
- 1P(i) is 1 if node i is on the path P; otherwise 0
- ci is the cost of the link used in P, if a link from i is
used
47
Payment Using VCG Mechanism
 VCG stands for Vickrey, Clarke and Groves
 The VCG mechanism
 each node sends the costs of its links to the authority
 the authority computes the lowest cost path from the
source S to the destination D
 the payment to node i:
pi  cost ( LCP(S , D;i))  cost ( LCP(S , D) \ {i})
where
- LCP(S,D) is the lowest cost path from S to D:
{S->R1, R1->R2, …, Rk->D}
- LCP(S,D)\{i} is the previous path but does not include the
link from i to its next hop, if i is on the path; if i is not on
the path, it is just the previous path
- LCP(S,D;-i) is the lowest cost path from S to D without
using i, i.e. remove node i from the graph and then find path
48
Example: N1
1
Assume the true cost of N1 to D is 2
N1
2
D
S
1
3
N2
- assume N1 declares the cost as 2, how much will N1 be
(1+3)-1 = 3
paid according to the VCG mechanism?
- what is the utility of N1?
3-2=1
- assume N1 declares the cost as 1, how much will N1 be
(1+3)-1 = 3
paid according to the VCG mechanism?
3-2=1
- what is the utility of N1?
- assume N1 declares the cost as 4, how much will N1 be
paid according to the VCG mechanism? (1+3)-(1+3) = 0
- what is the utility of N1?
0-0=0
49
Formal Results
 Each node reports its link costs truthfully
 Thus the network chooses the lowest cost
path for each source-destination pair
50
Analysis on Truthfulness
 By contradiction
 Assume node i’s true costs for its links are Ci but
reports Wi

think of Wi and Ci as vectors of link costs
 The node decides to declare Wi instead of Ci only if
the utility is higher
 The best scenario a node can be in is that it is given
the declared costs of all other nodes’ links and then
decides its declarations of the costs of its links in
order to maximize its utility

action chosen in this way is called dominant strategy
51
VCG Proof
 Assume the lowest cost path computed is
- LCP when the node reports Ci, and
- LCP’ when reports Wi
it must be the case that (1P(i) meant i on path P)
cost ( LCP' ( S , D;i ))  cost ( LCP' ( S , D) \ {i})  ci
LCP ' LCP '
 cost ( LCP( S , D;i ))  cost ( LCP( S , D) \ {i})  ci
 cost ( LCP' (S , D) \ {i})  ci
 cost ( LCP' (S , D) \ {i})  ci
LCP ' LCP '
1
LCP ' LCP '
1
1
(i )
LCP LCP
(i )
1
(i)  cost ( LCP(S , D) \ {i})  ci
(i)  cost ( LCP(S , D) \ {i})  ci
LCP LCP
1
LCP LCP
1
(i)
(i)
Right hand side is LCP we computed; left hand side is one path. Contradiction.
52