Transcript pptx - Jeff Pang

Improving the Privacy of
Wireless Protocols
Jeffrey Pang
Carnegie Mellon University
Protocol Header
Protocol Header
Blood pressure: high
Protocol Header
B
Protocol Control Info
Protocol Header
Protocol Control Info
Protocol Header
Home loc
2
Link
Layer Header
Protocol
Header
Blood
Blood
pressure:
pressure:
highhigh
Link
Layer Header
Protocol
Header
PrivateVideo1.avi
Protocol Control Info
Link
Layer Header
Protocol
Header
PrivatePhoto1.jpg
Protocol Control Info
Link
Layer Header
Protocol
Header
Buddy
Buddy
list:list:
Alice,
Alice,
Bob,
Bob,
… …
Link
Layer Header
Protocol
Header
Home
Home
location=(47.28,…
location=(47.28,…
3
What can Protocol Control Info Reveal?
www.bluetoothtracking.org
Location traces can be deanonymized
[Beresford 03, Hoh 05-07, Krum 07]
Kim’s House
00:16:4E:11:22:33
4
Who Might be Tracking You?
5
Talk Overview
• Motivation
• Quantifying the tracking threat
• Building identifier-free protocols
• Other research
6
Talk Overview
•
– Previous work: Temporary device addresses
[Gruteser 05, Hu 06, Jiang 07, Stajano 05]
Quantifying
the tracking
threat
– My work: Temporary
addresses
are not enough;
Other protocol info can be used to track devices
[MobiCom 07, HotOS 07]
• Building identifier-free protocols
– My work: How to build efficient protocols that
reveals no transmitted bits to eavesdroppers
[MobiSys 08 Best Paper, HotNets 07]
7
Best Security Practices Today
Bootstrap
Name: Alice’s Device
Secret: Alice<3Bob
Name: Bob’s Device
Secret: Alice<3Bob
Out-of-band (e.g., password, PIN)
Discover
Authenticate
and Bind
Send Data
From: 11:22:33:44:55:66
To: BROADCAST
Search probe
From: 11:22:33:44:55:66
To: BROADCAST
From: 11:22:33:44:55:66
To: AA:BB:CC:DD:EE:FF
Announcement
Credentials, key exchange
From: AA:BB:CC:DD:EE:FF
To: 11:22:33:44:55:66
From: 11:22:33:44:55:66
To: AA:BB:CC:DD:EE:FF
From: AA:BB:CC:DD:EE:FF
To: 11:22:33:44:55:66
Credentials, key exchange
 Ksession
Use to encrypt
& authenticate
• Confidentiality
• Authenticity
• Integrity
8
Best Security Practices Today
Temporary Addresses:
[Gruteser 05, Hu 06, Jiang 07, Stajano 05]
Discover
Authenticate
and Bind
Send Data
From: 19:1A:1B:1C:1D:1E
To: BROADCAST
Search probe
From: 22:1E:3E:4F:A1:45
To: BROADCAST
From: 19:1A:1B:1C:1D:1E
To: 22:1E:3E:4F:A1:45
Announcement
Credentials, key exchange
From: 22:1E:3E:4F:A1:45
To: 19:1A:1B:1C:1D:1E
From: 19:1A:1B:1C:1D:1E
To: 22:1E:3E:4F:A1:45
From: 22:1E:3E:4F:A1:45
To: 19:1A:1B:1C:1D:1E
Credentials, key exchange
 Ksession
• Confidentiality
• Authenticity
• Integrity
9
Tracking Example
• Consider one user at SIGCOMM 2004
– Seen in an “anonymized” wireless trace
(device addresses hashed, effectively a temporary address)
– Transferred 512MB via BitTorrent on a congested 802.11 network
(Poor network etiquette?)
• Can we still identify the culprit?
bittorrent transfer
00:0E:35:CE:1F:59
??
00:0E:35:CE:1F:59
00:0E:35:CE:1F:59
10
Tracking Example
• Fingerprint: network names in probes
Wardriving Database
00:0E:35:CE:1F:59
Probe: “roofnet”
?
User of “roofnet”
community network at MIT
11
Problem: Long-term Linkability
Bootstrap
Name: Bob’s Network
Secret: Alice<3Bob
Discover
Authenticate
and Bind
Send Data
From: 11:22:33:44:55:66
To: BROADCAST
Name: Alice’s Laptop
Secret: Alice<3Bob
Search
probe here?
Is Bob’s
Network
From: 11:22:33:44:55:66
To: BROADCAST
From: 11:22:33:44:55:66
To: AA:BB:CC:DD:EE:FF
Announcement
Bob’s
Network is here
Credentials,
Proof thatkey
I’mexchange
Alice
From: AA:BB:CC:DD:EE:FF
To: 11:22:33:44:55:66
Credentials,
key
exchange
Proof that
I’m
Bob
Identifiers
needed for
rendezvous!
Identifiers
needed for
authentication!
From: 11:22:33:44:55:66
To: AA:BB:CC:DD:EE:FF
From: AA:BB:CC:DD:EE:FF
To: 11:22:33:44:55:66
12
Tracking Example
bittorrent transfer
11:11:22:33:44:55
11:11:22:33:44:55
00:0E:35:CE:1F:59
11:11:22:33:44:55
Probe: “roofnet”
?
time
13
Tracking Example
• Fingerprint: IP broadcast packet sizes
– Set of broadcast packet sizes in network traffic
– e.g., advertisements by Apple Bonjour, iTunes, NetBIOS
00:0E:35:CE:1F:59
239 bytes
11:11:22:33:44:55
239 bytes
00:0E:35:CE:1F:59
245 bytes
11:11:22:33:44:55
245 bytes
00:0E:35:CE:1F:59
257 bytes
11:11:22:33:44:55
257 bytes
?
time
14
Problem: Short-term Linkability
Data packets in the same session remain linked;
in aggregate, these can be fingerprints
From: 12:34:56:78:90:ab
To: 11:22:33:44:55:66
500 bytes
From: 12:34:56:78:90:ab
To: 11:22:33:44:55:66
500 bytes
From: 00:00:99:99:11:11
To: 22:33:AA:BB:CC:DD
11:22:33:44:55:66
From: 12:34:56:78:90:ab
To: 11:22:33:44:55:66
From: 00:00:99:99:11:11
To: 22:33:AA:BB:CC:DD
11:22:33:44:55:66
From: 12:34:56:78:90:ab
To: 11:22:33:44:55:66
From: 00:00:99:99:11:11
To: 22:33:AA:BB:CC:DD
11:22:33:44:55:66
250 bytes
200 bytes
11:22:33:44:55:66
Source
Decryption
Address
key
12:34:56:78:90:ab
250 bytes
00:00:99:99:11:11
200 bytes
250 bytes
KAlice
KCharlie
22:33:AA:BB:CC:DD
15
Problem: Short-term Linkability
Bootstrap
Name: Bob’s Network
Secret: Alice<3Bob
Discover
Authenticate
and Bind
Send Data
From: 11:22:33:44:55:66
To: BROADCAST
Name: Alice’s Laptop
Secret: Alice<3Bob
Search
probe here?
Is Bob’s
Network
From: 11:22:33:44:55:66
To: BROADCAST
From: 11:22:33:44:55:66
To: AA:BB:CC:DD:EE:FF
Announcement
Bob’s
Network is here
Credentials,
Proof thatkey
I’mexchange
Alice
From: AA:BB:CC:DD:EE:FF
To: 11:22:33:44:55:66
From: 11:22:33:44:55:66
To: AA:BB:CC:DD:EE:FF
From: AA:BB:CC:DD:EE:FF
To: 11:22:33:44:55:66
Credentials,
key
exchange
Proof that
I’m
Bob
250 bytes
500 bytes
Identifiers
needed for
packet filtering!
16
Fingerprint Accuracy
• Developed an automated
identification algorithm
– Based on Naïve Bayes classifier
– Fingerprints:
Was Alice here?
• network names
• broadcast packet sizes
• supported capabilities
• Simulated user tracking with
traffic from 500+ users
– Assume encryption and device
address changes each hour
Known to be
from Alice
Question: Given some traffic samples from a device,
can we identify when it is present in the future?
17
Fingerprint Accuracy
• Results:
– 53% of devices can be identified
with 90% accuracy when at a
small hotspot for the day
(5 devices/hour)
– 27% with 99% accuracy
– 17% even if in a very busy
hotspot (100 users/hour)
– More fingerprints exist
 this is only a lower bound!
Was Alice here?
Known to be
from Alice
Question: Given some traffic samples from a device,
can we identify when it is present in the future?
18
Other Attacks Enabled
• User profiling, inventorying, relationship profiling
– [Greenstein 07, Jiang 07, Pang 07]
• Side-channel analysis on packet sizes and timing
– Exposes keystrokes, webpages, movies, VoIP calls, …
[Liberatore 06, Saponas 07, Song 01, Wright 08, Wright 07]
802.11
header
Is “djw” here?
“djw” is here
User Home
profiling attack
Movie
signature attack
Keystroke
timing attack
≈
DFT
19
Is There a Common Defense?
Bootstrap
Name: Bob’s Network
Secret: Alice<3Bob
Discover
Authenticate
and Bind
Send Data
From: 11:22:33:44:55:66
To: BROADCAST
Name: Alice’s Laptop
Secret: Alice<3Bob
Search
probe here?
Is Bob’s
Network
From: 11:22:33:44:55:66
To: BROADCAST
From: 11:22:33:44:55:66
To: AA:BB:CC:DD:EE:FF
Announcement
Bob’s
Network is here
Credentials,
Proof thatkey
I’mexchange
Alice
From: AA:BB:CC:DD:EE:FF
To: 11:22:33:44:55:66
From: 11:22:33:44:55:66
To: AA:BB:CC:DD:EE:FF
From: AA:BB:CC:DD:EE:FF
To: 11:22:33:44:55:66
Problem:
Long-term
Linkability
Credentials,
key
exchange
Proof that
I’m
Bob
Problem:
Short-term
Linkability
20
Goal: Make All Bits Appear Random
Bootstrap
Name: Bob’s Network
Secret: Alice<3Bob
Discover
Authenticate
and Bind
Send Data
Name: Alice’s Laptop
Secret: Alice<3Bob
No bits
linkable over
the long-term
Many streams
overlap in
real traffic
 much nosier
side-channels
21
Goal: Make All Bits Appear Random
Bootstrap
Name: Bob’s Network
Secret: Alice<3Bob
Discover
Name: Alice’s Laptop
Secret: Alice<3Bob
Identifiers
needed for
rendezvous!
Authenticate
and Bind
Identifiers
needed for
authentication!
Send Data
Identifiers
needed for
packet filtering!
22
Talk Overview
• Motivation
• Quantifying the tracking threat
• Building identifier-free protocols
• Other research
23
Design Requirements
• When A generates Message to B, she sends:
F(A, B, Message)
→
PrivateMessage
A→B Header… Unencrypted payload
where F has these properties:
– Confidentiality: Only A and B can determine Message.
– Authenticity: B can verify A created PrivateMessage.
– Integrity:
B can verify Message not modified.
– Unlinkability:
– Efficiency:
Only A and B can link PrivateMessages
to same sender or receiver.
B can process PrivateMessages as fast
as he can receive them.
24
Solution Summary
Today’s protocols
(e.g., 802.11 WPA)
Temporary addresses
(e.g., [Gruteser 05, Jiang 07])
Only
Data
Payload
Only
Data
Payload
Only
Data
Payload
Only
Data
Payload
Only
Data
Payload
Only
Data
Payload
Fingerprints
remain
Public Key
Symmetric Key
SlyFi: Discovery/Binding
SlyFi: Data packets
25
Straw man: Encrypt Everything
Name: Alice’s Laptop
Secret: Alice<3Bob
derive keys
Bootstrap
KAB KBA -
Name: Bob’s Network
Secret: Alice<3Bob
Key for Alice→Bob
Key for Bob→Alice
Idea: Use bootstrapped keys to encrypt everything
26
Straw man: Symmetric Key Protocol
Probe “Lucy”
Client
Service
Check MAC:
KAB
Probe “Bob”
KShared1
KShared2
KShared3
…
KSharedM
MAC: KAB
KAB
Symmetric encryption
(e.g., AES w/ random IV)
Try to decrypt with each key
(accounts + associations)
O(M)
27
Straw man: Symmetric Key Protocol
Client
Service
Too slow!
(APs
have
100s ofK accounts)
Check
MAC:
AB
Probe “Bob”
MAC: KAB
KAB
Symmetric encryption
(e.g., AES w/ random IV)
KShared1
KShared2
KShared3
…
KSharedM
One key per sender
(accounts + associations)
1.5 ms/packet (M=100)
(Need < 200 μs/packet for 802.11g)
28
Straw man: Public Key Protocol
Client
Service
Probe “Bob”
Check signature:
Sign: K-1Alice
KAlice
Too slow in practice!
KBob
K-1Bob
Key-private encryption
Try to decrypt
(e.g., ElGamal)
Based on [Abadi ’04]
~100 ms/packet
O(1)
29
Solution Summary
Today’s protocols
Temporary addresses
Only
Data
Payload
Only
Data
Payload
Only
Data
Payload
Only
Data
Payload
Only
Data
Payload
Only
Data
Payload
Fingerprints
remain
Public Key Protocol
Symmetric Key Protocol
SlyFi: Discovery/Binding
SlyFi: Data packets
30
SlyFi
• Symmetric key almost works, but tension between:
– Unlinkability: can’t expose the identity of the key
– Efficiency: need to identify the key to avoid trying all keys
• Idea: Identify the key in an unlinkable way
• Approach:
– Sender A and receiver B agree on tokens: T1AB, T2AB, T3AB, …
– A attaches TiAB to encrypted packet for B
31
SlyFi
Required
properties:
Client
Service
– Third parties can not link TiAB and TjAB if i ≠ j
Check MAC: KAB
AB
–
A
doesn’t
reuse
T
i
Probe “Bob”
– A and B can compute TiAB independently
MAC: KAB
Main challenge:
SenderKand
receiver must synchronize i
AB
TiAB
Symmetric encryption
(e.g., AES w/ random IV)
TiAB = AES(KAB, i)
KAB
Lookup TiAB in
hash table to get KAB
TiAB150
= μs/packet
AES(KAB, i)
(software)
32
SlyFi: Data Transport
i = 1
4
3
2
T1AB
T AB
2
T AB
3
T AB
4
AB
i = 1
4  T 3ABT…4123AB
3
2
T 3+k
hashtable
AB
• On
Datareceipt
messages:
of TiAB , B computes next expected: Ti+1
– Only sent
over established
• Handling
message
loss? connections
AB
AB

Expect
messages
to
be
delivered
– On
receipt
of TAB
save
T
,
…
,
T
i
i+1
i+k in table
Tolerates
i = transmission
numberlosses (k=50 is enough [Reis ‘06])
–
k consecutive
– No loss  compute one new token per reception
33
SlyFi: Discovery/Binding
Probe: “Bob’s Device”
Not here.
T2AB
Probe: “Bob’s Device”
Not here.
TiAB
Probe: “Bob’s Device”
...
T1AB
i=?
• Discovery & binding messages:
– Often sent when other party is not present
 Can’t rely on transmission reception to synchronize i
34
SlyFi: Discovery/Binding
TiAB
Probe: “Bob’s Device”
i=
i=
ABT…AB
AB
 T i-c
i T i+c
hashtable
• Handling
Discoveryclock
& binding
skew:messages:
AB
AB
– Infrequent:
Receiver B saves
only sent
Ti-c
,…
when
, Ti+c
trying
in table
to associate
– Narrow
Tolerates
interface:
clock skew
single
of capplication,
minutes few side-channels
–
state: long-term
compute one
new token
minute
Steady
Only require
unlinkability
toper
prevent
tracking
 i = current time/1 min
35
SlyFi: Putting it Together
Name: Alice’s Laptop
Secret: Alice<3Bob
Bootstrap
Name: Bob’s Network
Secret: Alice<3Bob
token
encrypt
auth
KAB
KAB
KAB
derive keys
token
encrypt
auth
KBA
KBA
KBA
token, i)
TiAB = AES(KAB
Discover
Enc(Kencrypt
,nonce, …)
AB nonce from, to, capabilities, Is Bob’s Network here?
AB
Ti
auth
other protocol fields
MAC(KAB , …)
to, capabilities,
Bob’s Network is here
TiBA nonce from,
other protocol fields
Authenticate
and Bind
to, capabilities,
Credentials, key exchange
TiAB nonce from,
other protocol fields
 Ksession1,2
from,
to,
capabilities,
TiBA nonce other protocol fields Credentials, key exchange
session1, i)
ti AB = AES(KBA
Send Data
t0AB from, to, seqno, …
t0BA from, to, seqno, …
session1
Enc(KAB
, t0AB, …)
session2, …)
MAC(KAB
36
SlyFi: Other Protocol Details
•
•
•
•
•
•
•
•
Broadcast
Higher-layer binding
Time synchronization
Roaming
Coexistence with 802.11
Link-layer ACKs
Multi-party discovery
Preventing replay attacks
See Mobisys 08
paper for details
37
Performance Evaluation
• Open-source Linux kernel module:
http://tw.seattle.intel-research.net
• Evaluated on embedded devices
• SlyFi is about as efficient as 802.11 (wifi-open)
Time to setup a link
Data throughput
(Previous proposal
similar to symmetric key)
38
Solution Summary
Today’s protocols
Temporary addresses
Only
Data
Payload
Only
Data
Payload
Only
Data
Payload
Only
Data
Payload
Only
Data
Payload
Only
Data
Payload
Fingerprints
remain
Public Key
Symmetric Key
SlyFi: Discovery/Binding
Long
Term
SlyFi: Data packets
39
Talk Overview
• Motivation
• Quantifying the tracking threat
• Building identifier-free protocols
• Other research
40
Hotspot Recommender System
Our Goal
100 kbps
community
uploads reports
Public
Report
Database
1 Mbps, blocks VoIP
Research Challenges
• Preserving location privacy
– Reports shouldn’t be linked, otherwise
they can be used to track users
– But also need to limit fraud;
e.g., 1 report per hotspot per user
– Solution: ecash-like reporting protocol
& robust summary functions
• Preserving location context
tmobile
300 kbps
attwifi (ap 1)
100 kbps
attwifi (ap 2)
300 kbps
linksys
Doesn’t work!
seattlewifi
Free Public Wifi
VoIP is blocked!
Doesn’t work!
– Performance dependent on location
with respect to access point
– Wireless channel effects loss rate
– Solution: estimate different loss
regimes w/ distributed measurements
41
Other Research and Future Plans
Ubiquitous Computing Systems
Wide-Area Internet Systems
Wireless Protocol Privacy
Peer-to-Peer Games
[MobiSys 08, Mobicom 07, HotOS 07]
Quantifying privacy threats
Identifier-free link layer protocols
[SIGCOMM 08, NSDI 06, IPTPS 07]
Scalable gameplay update distribution
Attention-based update prioritization
Player simulation with “guidable” A.I.
•
•
Wireless Service Discovery
•
•
[MobiSys 09, HotNets 07]
Hotspot recommender system
Private device discovery without
per-device bootstrapping
•
•
•
Distributed File Systems
•
•
Home Networking
•
•
•
Out-sourcing network management
Social networks for access-control
Private application-layer discovery
Internet Measurement
•
•
Community Sensing
•
Location-aware measurement platform
for mobile devices
[ICDCS 07]
Locality-preserving data placement
Decentralized load-balancing
[IMC 04 x2, SIGCOMM 04]
DNS infrastructure properties
BGP routing and multi-homing
Cloud Computing for Games
•
Automatic scaling & migration for
massively multiplayer online games
=== TOPICS ===
43
Peer-to-Peer Games
Our Goal
High-speed
P2P
Large-scale
+
+
Who I’m playing
attention to
Scaling challenges
• How to quickly discover and
replicate players in your area
• How to prioritize updates
based on attention when
bandwidth is limited
• How to disseminate updates
between peers with very little
upload capacity, on average
Me
44
Distributed File Systems
Our Goal
Traditional
DHT File System
random
placement
Challenges
Our
DHT File System
• How to maintain file locality
without knowledge of future tasks
• How to balance load without
substantial overhead
defragmented
placement
Files used by two tasks:
Preserving file locality:
• Improves task success rate;
depend on fewer machines
• Improves task performance;
need fewer lookups
nodes accessed during an NFS trace
45
DNS Measurement
Our Goal
...
Challenges
Root Servers
gTLD Servers
Authoritative
DNS Servers
Local DNS Servers
Understand server characteristics:
• Availability
• Load balance
• Deployment characteristics
• Collecting DNS server addresses
• Active monitoring of 300,000+
servers in other domains
• Inferring load from visible metrics
• Handling network irregularities,
such as dynamic DNS
Key Findings
• Vast majority are highly availability
• Load is positively correlated with
availability and is highly skewed
• Three distinct deployment styles in
different DNS domains
46
=== MOTIVATION ===
47
Who Should Care About Tracking?
• End-users
– CRA Grand Challenge:
“Give computer end-users privacy they can control”
• Service providers
– They can’t protect customers from eavesdroppers
even if they don’t track users themselves
• Device manufacturers
– Privacy concerns about tracking can hurt sales
(e.g., Intel CPUID debacle, Benetton RFID boycott)
48
Fingerprints Related Work
• Other fingerprints
–
–
–
–
Device driver fingerprints [Franklin 06]
TCP clock-skew fingerprints [Kohno 05]
AP beacon click skew [Jana 08]
Physical layer fingerprints (using specialized hardware)
[Brik 08, Patwari 07, Hall 04]
• Our contributions in comparison:
–
–
–
–
First link-layer fingerprints for individual devices
Enabling tracking when link-layer encryption is employed
Enabling better coverage than some previous work
Showing how to combine implicit identifiers
49
Unlinkable Tokens Related Work
• Unlinkable tokens in discovery
– Public key protocol (slow in practice) [Abadi 04]
– Application layer protocol to find friends (uses hash-chain) [Cox 07]
• Unlinkable tokens in data transport
– General proposal, analysis for TCP (masking piecemeal) [Nikander 05]
– 802.11 proposal (inefficient) [Armknecht 07]
– Bluetooth proposal (uses hash-chain) [Singelee 06]
• SlyFi contributions in comparison
–
–
–
–
First to ensure no bits exposed (not masking identifiers piecemeal)
First to handle all major wireless protocol functions
First to leverage existing hardware (AES counter instead of hash-chain)
First link layer protocol implementation & evaluation on real devices
50
Location Privacy Related Work
• Privacy in location-based services,
e.g., [Beresford ‘03, Gruteser ‘03, Schilit ‘03]
– Don’t protect against third party eavesdroppers
• Privacy in RFID, e.g., [Fishkin ‘04, Juels ‘05]
– General protocols do more than identification
• Privacy using temporary device addresses
[Gruteser ’05, Hu ’06, Jiang ’07, Stajano ‘05]
51
Why not GSM Pseudonyms?
• GSM pseudonym properties
– Provider must assign new pseudonym to client to change it
– Only a single application used on GSM network
• GSM pseudonyms not sufficient when
– Both parties in discovery want to be private
– May require using pseudonym when the provider is not
present (e.g., during discovery)
– Many applications with many side-channels
– Must accommodate device heterogeneity, evolution
52
802.11w: Protected Management Frames
802.11i (WPA)
802.11i + 802.11w
MAC Pseudonyms
Data
Payload
Unicast
Frames
Data
Payload
Data
Payload
Long
Term
Public Key
Symmetric Key
SlyFi: Discovery/Binding
Long
Term
SlyFi: Data packets
53
Research Goals and Future Plans
Motivation
• Ubiquitous computing
• Federated Internet systems
Example Topic Area
Secure outsourcing of computer
and network management
We will
fix it!
Research Problems
How to build systems from
partially trusted and
heterogeneous components
to operate in unpredictable
and hostile environments
Approach
• Real-world measurements
• Empirically driven design
• Building and evaluating
research prototypes
Help, my network
is broken!
Other Applications
• Secure and private cloud computing
• Enterprise network management
• Cooperative wireless fault diagnosis
54
=== MOBISYS ===
55
PHY Layer Signatures
• Physical layer fingerprints [Brik 08, Patwari 07, Hall 04]
– Require uncommon and/or expensive hardware
– Not as accurate in all circumstances
• These may be obscured by adding analog noise in hardware
• SlyFi raises the bar and is a necessary first step
Charlie
??? ->->APAP
Charlie
??? ->->APAP
Alice
??? ->
->AP
AP
Charlie
??? ->->APAP
Charlie
??? ->->APAP
Charlie
??? ->->APAP
56
Linking with Signal Strength
• Attack: website finger-printing
[Liberatore ‘06]
• Attacker has 5 nodes to record
packets’ RSSIs
• Attacker uses k-means clustering
to determine which packets
belong to each client. Set of
RSSIs is the feature vector.
• Varying RSSI by +/- 5db reduces
accuracy even further to 30%
[Bauer ‘08]
Side-channel attack accuracy degrades significantly
even if attacker tries to use signal strength to link packets
57
Why not Time for Data Transport?
• Data messages:
– Frequent: sent often to deliver data (1000+ pkts/sec)
– Wide interface: many applications, many side-channels
 Linkability at short timescales is NOT usually OK
 Can NOT use loosely synchronized time to synchronize i
= = =
TiAB
TiAB
TiAB
TiAB
58
Other Protocol Details
• Broadcast
– All broadcast packets routed through the AP
– Use same shared key for all the clients of the AP
• Higher-layer binding
– Clients report “pseudonym MAC address”-to-IP address bindings to AP
– AP answers all ARP queries
• Time synchronization and roaming
– Use protected broadcast to transmit timestamps, same BSSID info
• Coexistence with 802.11
– Encapsulate SlyFi in “anonymous” 802.11 frame with unused FC code
– Clients first search for SlyFi AP, then fall back to non-private AP search
• Link-layer ACKs
– If fast enough, just acknowledge last SlyFi token sent
– Our software implementation uses windowed ACKs
59
Multi-Party Discovery
token, i) T AC = AES(K token, i)
TiAB = AES(KAB
i
AB
...
random key
TiAB
Kpayload, offset
Enc(Kencrypt
,0, …)
AB
auth
MAC(KAB , …)
TiAC
Kpayload, offset
...
Enc(Kencrypt
,0, …)
AB
auth
MAC(KAB , …)
Search Probe
Enc(Kpayload1, 0, …)
MAC(Kpayload2, …)
• On receipt, check each 16-byte block that could be a token
– 1500 byte packets  at most 31 lookups per packet
– Can be done in parallel in hardware
• What if there are more than 31 receivers?
– Option 1: Duplicate packet with different tokens in each
– Option 2: Approximate token matching; open problem and future work
60
Packet Format
Token
Unencrypted Message
Tryst: Discovery/Binding
Shroud: Data Transport
61
Protocol Timing Diagram
Discover
Authenticate
and Bind
Send Data
62
Performance Evaluation
Similar
• Comparison protocols
–
–
–
–
–
wifi-open:
wifi-wpa:
public-key:
symmetric-key:
armknecht:
Experiment:
802.11 with no security
802.11 with WPA PSK/CCMP
straw man
straw man
previous header encryption proposal
Background
traffic
AP with
500 accounts
50 associations
Measure Alice’s connection to Bob
63
Link Setup Failures
“Encrypt everything” fails to setup many links
64
Token Computation Time
(Once every token interval)
Using software AES, 256 Mhz Geode processor
Token computation time is negligible
65
Data Throughput vs. Packet Size
SlyFi data transport overhead is similar to WPA
66
Data Throughput
Higher = Better
With simulated
AES hardware
Performs like
symmetric key
SlyFi data filtering is about as efficient as 802.11
67
Empirical Stream Interleaving
Many streams interleaved even at short timescales
68
Empirical Background Probe Rate
Background probes are frequent in practice
69
Empirical # Probes per Client
Some clients probe for many network names
70
=== MOBICOM ===
71
Tracking 802.11 Users
• Tracking scenario:
– Every users changes pseudonyms every hour
– Adversary monitors some locations
One hourly traffic sample from each user in each location
?
?
tcpdump
?
?
.....
?
?
tcpdump
Build a profile from training samples:
Traffic at 2-3PM
Traffic
2-3PM
Traffic at 2-3PM
Thenat classify
First collect some traffic known to
be
Traffic at 3-4PM
Traffic at 3-4PM
Traffic at 3-4PM
observation
samples
from user X and from random others
Traffic at 4-5PM
Traffic at 4-5PM
Traffic at 4-5PM
72
Sample Classification Algorithm
• Core question:
– Did traffic sample s come from user X?
• A simple approach: naïve Bayes classifier
– Derive probabilistic model from training samples
– Given s with features F, answer “yes” if:
Pr[ s from user X | s has features F ] > T
for a selected threshold T.
– F = feature set derived from implicit identifiers
73
Sample Classification Algorithm
• Deriving features F from implicit identifiers
Rare
linksys
Common
djw
IR_Guest
w(e) = high
SIGCOMM_1
w(e) = low
PROFILE FROM
TRAINING
SAMPLE FROM
OBSERVATION
Set similarity (Jaccard Index), weighted by frequency:
74
Evaluating Classification Effectiveness
• Simulate tracking scenario with wireless traces:
Duration
Profiled Users Total Users
SIGCOMM
conf. (2004)
4 days
377
465
UCSD office
building (2006)
1 day
153
615
Apartment
building (2006)
14 days
39
196
– Split each trace into training and observation phases
– Simulate pseudonym changes for each user X
75
Evaluating Classification Effectiveness
• Question: Is observation sample s from user X?
• Evaluation metrics:
– True positive rate (TPR)
Fraction of user X’s samples classified correctly
– False positive rate (FPR)
Fraction of other samples classified incorrectly
= ???
Measure TPR
= 0.01
Fix T for FPR
(See paper)
Pr[ s from user X | s has features F ] > T
76
1.0
Results: Individual Feature Accuracy
TPR  60%
TPR  30%
Individual implicit identifiers give evidence of identity
77
Results: Multiple Feature Accuracy
Users with TPR >50%:
Public: 63%
Home: 31%
Enterprise: 27%
Public
Home
Enterprise
netdests
ssids
bcast
fields
We can identify many users in all environments
78
Results: Multiple Feature Accuracy
Public networks:
~20% users identified
>90% of the time
Public
Home
Enterprise
netdests
ssids
bcast
fields
Some users much more distinguishable than others
79
One Application
• Question: Was user X here today?
• More difficult to answer:
– Suppose N users present each hour
– Over an 8 hour day, 8N opportunities to misclassify
Decide user X is here only if multiple samples are classified
as his
• Revised: Was user X here today for a few hours?
80
Results: Tracking with 90% Accuracy
Many users can be identified
81
=== WIFI-REPORTS ===
82
Will Reports Improve Selection?
Commercial APs at Seattle hotspot locations
red = “official” AP
grey = other visible AP
83
Other Research
Wireless Service Discovery
[MobiSys 09, HotNets 07]
• Wi-Fi hotspot reputation system
• Private device discovery without
per-device bootstrapping
Peer-to-Peer Games
[SIGCOMM 08, NSDI 06, IPTPS 07]
Internet Measurement
[IMC 04 x2, SIGCOMM 04]
• DNS infrastructure properties
• DNS cache compliance
• BGP routing and multi-homing
Distributed File Systems
[ICDCS 07]
85
What can Protocol Control Info Reveal?
Wardriving Database
Protocol Header
Probe: “IR_Guest”
Protocol Header
Probe: “Anna, Jeff, and Mark’s Net”
Me
86