Transcript Document

Mobile Traffic Sensor Network vs. Motion-MIX:
Tracing & Protecting Mobile Wireless Nodes
#Jiejun
#Dept
Kong,
*Dapeng Wu, +Xiaoyan Hong, #Mario Gerla
of Computer Science *Dept of Computer Science +Dept of EE
UCLA
University of Florida University of Alabama
November 7, 2005
@ACM SASN’05
Problem: Mobile Anonymity
Fixed Anonymity: Identity (net addr)
 Mobile Anonymity: Identity  Location

– Identity (net addr/identity)
– Location (positioned by the adversary)
– Motion pattern (deduced by the adversary)

Significance of anonymous wireless
communication
– 1996 A.D.: Chechnya rebel leader, General Dzhokhar
Dudayev, always on the move, but killed during a
traceable wireless call
Mobile Traffic Sensor Network

Mobile traffic analyst
– Unmanned aerial vehicle (UAV)
– Coordinated positioning
(tri-lateration / tri-angulation)
can reduce location uncertainty

If moving faster than
the transmitter, can
always trace the victim
Outline

Background

Proposed solution
– In theory: Asymptotic network security model
– In practice: Motion-MIX

Security analysis
– Motion-MIX satisfies the asymptotic network
security model

Summary
Notion: Security as a “landslide” game

Played by the guard and the adversary
– Proposal can be found as early as Shannon’s 1949 paper
– Not a 50%-50% chance game, which is too good for the
adversary

The notion has been used in modern crypto since
1970s
–
–
–
–
Based on NP-complexity
The guard wins the game with 1 - negligible probability
The adversary wins the game with negligible probability
The asymptotic notion of “negligible” applies to one-way
function (encryption, one-way hash), pseudorandom
generator, zero-knowledge proof, ……
AND this time ……
Our Asymptotic Network Security Model


Concept: the probability of security breach decreases
exponentially toward 0 when network metric increases
linearly / polynomially
Consistent with computational cryptography’s asymptotic
notion of “negligible / sub-polynomial”
Definition: A function m: N  R is negligible, if for every
positive integer c and all sufficiently large x’s (i.e., there
exists Nc>0, for all x>Nc),

is negligible by definition
x is key length in computational crypto
x is network metric (e.g., # of nodes) in network security
Probability of security breach
The Asymptotic Cryptography Model
The “negligible” line
(sub-polynomial line)
Insecure
1 2
•
(Ambiguous area)
# of key bits (key length)
Secure
128
See Lenstra’s analysis for proper key length
 Security can be achieved by a polynomial-bounded guard
(given adversary’s brute-force computational power)
polynomial-bounded
• against
There aare
approximately 2268adversary
atoms in the entire universe
Probability of network security breach
Our Asymptotic Network Security Model

The “negligible” line
(sub-polynomial line)
Insecure
Secureline
The “exponential”
(Ambiguous(memory-less
area)
line)
Network metric (e.g., # of nodes -- network scale)
Conforming to the classic notion of security used in modern
cryptography ! We’ve used the same security notion
Design Assumptions

Adversary model
– Passive
– Few insiders (captured & compromised nodes),
– Global (or equivalently, mobile and capable of scanning
the entire network area in short time)
– Honest-but-curious (protocol-compliant)
– External: polynomially-bounded by key length
– Internal: fraction  of N (which is # of network nodes)

Network model
– Loquor ergo sum (I speak, so I exist): nodes must transmit
upon application demand, cannot shut up
– Pairwise key sharing (via Diffie-Hellman, KPS, or
“mobility helps security”)
Venue

“Venue”
is the smallest area that
Venue
the adversary can “pinpoint” a
wireless transmitter via its
The VIP node
wireless transmission
being traced
Assumption: Imperfect Wireless Positioning
D. Niculescu, B. Nath, “VOR Base
Stations for Indoor 802.11 Positioning,”
ACM MOBICOM’04, pp.58—69.
Motion Pattern Tracing (1 node)


1 transmitting node in the network
No way to protect it
– Just like a cryptographic case using 1-bit key
Motion Pattern Tracing (2 nodes)



2 transmitting nodes in the network; Better security protection
What’s the network-based analytic model behind this phenomenon?
What happens if there are many nodes in a scalable network?
We need Motion-MIX
Motion-MIX: Design Goal


 k incoming mobile nodes or wireless packet
flows get fully mixed in the Motion-MIX
 k-anonymity: the adversary cannot
differentiate these k nodes
Motion-MIX vs. Chaumian MIX

Effectiveness determined by the adversary’s
capability & the guard’s capability
1. Privacy model: like Chaumian MIX processor, the
internal state of Motion-MIX is private
 The adversarial side cannot position any transmitting
node inside the area quantified by 
2. Temporal-spatial model: like Chaumian MIX (e.g., pool
mix), the guarding side can delay and gather the
protected items in a Motion-MIX
 Motion-MIX’s size is determined bi-laterally (the
adversary & the guard) in terms of time and space
Size of Motion-MIX

Adversary determines
inner circle

Guard determines outer
ring
– t is the minimum delay

between any 2
transmissions from a single
node
Adversary’s capability
– vavg is the
’
average/expected node
mobility speed

Motion-MIX’s size is a
bilaterally-determined
quantity
’ = ( + vavg*t)
Wireless Traffic Mixing Per Venue
Algorithm D -- Wireless traffic mixing:
(Each venue transmits approximately k packets per t in a fully distributed manner)
Prerequisite: Pre-defined system parameter k and unit time t.
1 Divide current unit time t into k slices.
2 FOR (each time slice i) DO
3 IF (I have only heard x<i transmissions so far during the current unit time interval)
4
In the next time slice, transmit a decoy packet with probability (i-x)/i.
5 END IF
6 END FOR
Ensures: Greater-than-zero effect
1. If at least a “good” node is in a venue, the adversary can only estimate
there are averagely E(k’) nodes inside.
Actually # of nodes inside the venue can be
from minimally 1 to maximally (N - #_of_non-empty_venues).
2. Otherwise, the venue is empty. Motion-MIX is not functional.
Necessary Conditions of Motion-MIX

Protocol-stack-wise concerns, not limited to
application/middleware layer (unlike MIX-Zone)

Building blocks
1. Identity-free routing  ANODR (MOBIHOC’03)
•
Anonymous even against any insider
2. One-time packet contents  XOR-tree (TISS’00)
•
E.g., for 100 packets, the 2 extreme cases (1 sender to 1
recipient & 100 different senders to 100 different recipients) and
all cases in-between are equally probable
 looks truly random / independent
3. Radio interface calibration to remove RF signatures
 “Shake them up” (MOBISYS’05)
Identity-free Routing: ANODR
(MOBIHOC’03)
#B
B
A
Route-REQuest
E
Route-REPly
global_trap denotes an encryption of a wellC tagD
known
(“You are the destination”) using a
KA(hello)
KAB(hello)
( BK( AK
( CK(BK
( BKE
K
K
(AK(hello)))
K
K(hello))
C(hello))
key only known
by
destination
A(hello)))
A
#D
#C
#E
 ANODR: destination E receives
RREQ, global_trap, onion where
onion = KD( KC( KB( KA(hello))))
RREP,global_proof,
global_proof,
onion #
 X K (only
RREP,
onion,
KX(m) denotes
using symmetric
key
#X is
random
packet stamp
selectedmby X
known
bya X)
to encrypt
a message
and shared on the hop
Identity-free Data Forwarding
A
#1
#1
C
B
#2
payload
#2
#2
payload
#3
#3
#3
payload
#4
#4
payload

Table driven virtual circuit: stores mapping of a pair
of packet stamps

Packet marked with #
– Matched incoming # is replaced by corresponding
outgoing #
– IP address, 802.11 MAC address not used in ANODR
One-time Packet Contents (cont’d)
“Unpredictable” pseudorandom packet contents
Key
1
56a35d537fe
56a35d537fe
2
198573f8d5b
198573f8d5b
3
e53410957fa
e53410957fa
...
– In secular term, looks truly random to the adversary
– Key management & distribution needed
...

Identity-free Packet Flow (ANODR)
4342747
5452343
9746411
6175747
5422819
8543358
1745634
Mobile network model

Divides the network into large number n of very
small tiles (i.e., possible “positions”)
– A node’s presence probability p at each tile is small
 Follows a spatial binomial distribution B(n,p)
– When n is large and p is small, B(n,p) is approximately a
spatial Poisson distribution with rate r1
– If there are N mobile nodes roaming i.i.d.
rN = N·r1
– The probability of exactly k nodes in an area A’
Venue
’
Venue
Average Venue

Publicity assumption (Kerckhoff’s Desiderata): the
adversary knows the entire identity set and the
network area, it can estimate that expectation of # of
nodes in each venue is
– Thus, nodes in each venue transmit k = E(k') real/decoy
packets in a fully distributed manner

A motion-MIX is min(k, E(k'))–anonymous
where '=(+vavg*t) is the bi-lateral Motion-MIX
size
– In each non-empty venue, min(k, E(k')) - anonymous
– In the entire network, ubiquitously min(k, E(k')) anonymous due to identity-free routing, one-time packet
contents and RF signature hiding
Untraceable Mobile Nodes (or Packet Flows)
All motion patterns equally likely if
contiguous venues are non-empty
(in the previous time slot t)
 Untraceable
(per Shannon’s information theoretic notion)
The VIP node
being traced
Security Analysis: Impact of N (# of nodes)
Probability of having less than k good nodes is negligible with respect to network scale N
Probability of tracing a mobile node is negligible with respect to N and motion time |T|
Probability of tracing a packet flow is negligible with respect to N and # of traveled venues |X|
Summary

Anonymous communication in mobile networks has its own
idiosyncrasy
– Motion pattern of mobile nodes can be traced
 Motion-MIX needed

We propose a novel asymptotic network security model that
is consistent with classic security notions
– Identity-free routing, one-time packet contents, and radio signature
hiding are necessary conditions to implement Motion-MIX
– Motion-MIX + ANODR is practical

Work-in-progress: Currently, doing real-world experiments on
Motion-MIX and ANODR
– Related to MANET localization/positioning, QualNet simulation,
ANODR Linux implementation, UAV experiment
– More rigorous formalization & proofs
UCLA E-mail contacts:
Jiejun Kong:
[email protected]
Mario Gerla:
[email protected]
Notion: Perfect Secrecy (C.E.Shannon)
fkey
m1
m2
m3
m4
1
2
3
4
2
1
4
3
1
plaintext


e2
34
1
2
43
e1
2
e1 e2 e3 e4
m 1 00
1 01
2 10
3 11
4
XOR
1 01
2
3 11
4 00
10
m 2 01
2 00
1 11
4 10
3
e3
m3
e4
m 4 11
4 10
3 01
2 00
1
m k = e
ciphertext
A triangluar relation: plaintext M, ciphertext E, key K
Given ciphertext E, adversary gains no information
H(M|E) = H(M)
a posteriori = a priori
Notion: Perfect Anonymity
(IACR ePrint TR2005-132)
s3
s4
anonymity
set
r1
s1
r2
s2
r3
s3
r4
s4
anonymity
set
Sender Anonymity
anonymity
set
r1
flooding
s2
indistinguishable
synchronized
s1
indistinguishable
Route-driven connection
Route-driven connection
r2
r3
r4
anonymity
set
Recipient Anonymity
Message Secrecy & Anonymity
(information theoretic notion)
Perfect Secrecy
H(M|E) = H(M)


Perfect Anonymity
H(XAS|C) = H(XAS)
Security degradation can be defined as the ratio between
H(XAS|C) and H(XAS),
as demonstrated in 2 PET’02 papers
[Serjantov&Danezis,PET’02] and [Diaz et al., PET’02]
This non-scalable solution is not our answer !
r1

Inspired by Bettstetter et al.’s work
– For any mobility model (random walk, random way point),
Bettstetter et al. have shown that
r1 is computable following
– For example, in random way point model
in a square network area of size a£a defined by -a/2·x· a/2
and -a/2·y· a/2
– r1 is “location independent”, yet computable in NS2 &
QualNet given any area A’ (using finite element method)
r1 in Random Way Point model
[Bettstetter et al.]
a=1000
WASP Micro-Aerial Vehicle (MAV)






Wingspan: 13 inches
Combined wing structure (Lithium-Ion battery pack): 4.25 ounces (120 gm)
Total weight of the vehicle: 6 ounces (170 gm)
Power: 9 Watts during the flight.
Flying time: 1 hour and 47 min
Good enough to trace a mobile soldier or a few soliders per MAV