Transcript Taxis Slides

Taxis: Scalable Strong
Anonymous Communication
Andreas Hirt
Michael J. Jacobson, Jr.
Carey Williamson
Department of Computer Science
University of Calgary
Financial support for this research support was provided by:
National Sciences and Engineering Research Council (NSERC),
Informatics Circle of Research Excellence (iCORE),
Alberta Ingenuity Fund (AIF), and
Canadian Foundation for Innovation (CFI)
Introduction



Anonymous communication conceals who
communicates what, to whom, and when
Allows individuals to communicate without
fear of embarrassment, ridicule, or retribution
Cornerstone for freedom of speech
MASCOTS 2008
2
Some Real World Applications

Good:








Freedom of speech in totalitarian regime
Crime stoppers
On-line counseling
Whistle blowing
Group evaluations
Military communications
…
Bad:



Organized crime
Terrorist groups
...
MASCOTS 2008
3
Outline







Anonymity Crash Course
Anonymous Communication with Practical
Buses
Analysis of Practical Buses
Evolving Practical Buses to Taxis
Analysis of Taxis
Experimental Results
Conclusion
MASCOTS 2008
4
Types of Anonymity

Data Anonymity (Application Layer)


Filtering of identifying data at application layer, i.e., user
names, sender address in e-mails, etc.
Connection Anonymity (IP Layer)


Hides network routing info (such as IP address)
Several versions (dependent on perspective):




?
Sender Anonymity
Receiver Anonymity
Mutual Anonymity
Unlinkability
MASCOTS 2008
5
Main Anonymity Approaches
1) Broadcasting




Broadcasting: Encrypt the message, and send it to everyone
Everyone is equally likely to be the receiver
Only the intended receiver can decrypt
Problem: Does not scale well
hello
S
?
?
xmkz
?
xmkz
xmkz
R !
xmkz
xmkz
xmkz
xmkz
?
?
MASCOTS 2008
xmkz
hello
?
6
2) Re-routing



Re-routing: encrypt the message, and re-route it via one or
more intermediate nodes en route to the destination
Receiver only learns last node in the re-routing path
Problem: Trace message through network with static contents
Sender?
hello
xmkz
hello
MASCOTS 2008
7
Re-routing: Layered
Encryption

Layered Encryption: Add layers of encryption
to make message contents change each hop
hello
xmkz
iwqm
qkdx
ykrz
MASCOTS 2008
8
Re-routing: Layered
Encryption

Layered Encryption: Add layers of encryption
to make message contents change each hop
hello
xmkz
iwqm
ykrz
MASCOTS 2008
9
Re-routing: Layered
Encryption

Layered Encryption: Add layers of encryption
to make message contents change each hop
hello
xmkz
ykrz
MASCOTS 2008
10
Re-routing: Layered
Encryption


Layered Encryption: Add layers of encryption
to make message contents change each hop
Problem: Timing analysis
Sender?
hello
xmkz
hello
MASCOTS 2008
11
Main Anonymity Approaches
3) Mixes


Senders use nested (layered) encryption along re-routing path
Mixes (re-routing nodes) mix input-output correlations:



Collect input batch
Peel encryption layer away
Output in random order
Message 1
Message 2
Message 2
Message 4
Message 3
Message 3
Message 4
Message 1
Message 5
Message 5
MASCOTS 2008
12
Problems with Mixes

Batch: wait until a message for every sender
and every receiver
→ High latency

Cover traffic: Add dummy traffic between
every sender-receiver pair as needed
→ Quadratic cover traffic → High latency
Research goal is to design an anonymous
communication scheme that achieves both
strong anonymity and low latency
MASCOTS 2008
13
Current Solutions
No Cover
Traffic
Partial Cover
Traffic
Full Cover
Traffic
Schemes
Crowds, TOR
JAP, MorphMix
Mixmaster,
Mixminion,
Tarzan
Anonymity
Weak
Moderate
Strong
Problems
Vulnerable to
known attacks
Vulnerable to
known attacks
Not suitable for
interactive
applications,
don’t scale well
MASCOTS 2008
14
Outline







Anonymity Crash Course
Anonymous Communication with
Practical Buses
Analysis of Practical Buses
Evolving Practical Buses to Taxis
Analysis of Taxis
Experimental Results
Conclusion
MASCOTS 2008
15
Practical Buses General Idea


Metaphor: city bus, with regularly scheduled route,
which obscures the movements of its messengers
Assume dark windows, and enclosed garages at each stop
hello
hello
MASCOTS 2008
16
Practical Buses General Idea


Metaphor: city bus, with regularly scheduled route,
which obscures the movements of its messengers
Assume dark windows, and enclosed garages at each stop
hello
hello
MASCOTS 2008
17
Practical Buses Anonymity


Sender Anonymity: Suspected sender can
claim they are forwarding a message on
behalf of any other participant on the bus
path
Receiver Anonymity: Suspected receiver
can claim they forwarded a message to any
other participant on the bus path
MASCOTS 2008
18
Practical Buses Main Ideas




Indirection path: re-routing path on top of
bus overlay
Layered Encryption: encryption on reverse
indirection path
Owned Seats: Each participant replaces
owned seats every bus tour (online)
Receiving seats: bus copied and decrypted
offline to find messages
MASCOTS 2008
19
Main Anonymity Approaches
4) Practical Buses
hello
S
R
MASCOTS 2008
20
Main Anonymity Approaches
4) Practical Buses
hello
S
R
xmkz
MASCOTS 2008
21
Main Anonymity Approaches
4) Practical Buses
hello
S
R
ymkq
MASCOTS 2008
22
Main Anonymity Approaches
4) Practical Buses
hello
S
R
MASCOTS 2008
23
Main Anonymity Approaches
4) Practical Buses
hello
S
R
MASCOTS 2008
24
Main Anonymity Approaches
4) Practical Buses
hello
S
R
ymkq
xmkz
MASCOTS 2008
25
Main Anonymity Approaches
4) Practical Buses
hello
S
R
xmkz
hello
MASCOTS 2008
26
Additional Features

Security:



Fault-Tolerance:



Signed Bus seats (digital signatures)
Replay protection to fix anonymity attack
Anonymous Acknowledgements
Resends due to timeout if no ACK received
Performance:




Expired seat deletion
Persistent TCP connections
Multithreading
Hybrid Encryption: RSA-OAEP/CBC-AES
MASCOTS 2008
27
Outline







Anonymity Crash Course
Anonymous Communication with Practical
Buses
Analysis of Practical Buses
Evolving Practical Buses to Taxis
Analysis of Taxis
Experimental Results
Conclusion
MASCOTS 2008
28
Practical Buses Simple Model


Average message latency: average time
from when a message is first sent until an
anonymous acknowledgment is received
Abstract Model:
E[LB] = 2 (dIR + h(dnet + dproc))
MASCOTS 2008
29
Practical Buses Detailed Model

E[LB] = 2 (dIR + h(dnet + dproc))
Avg # of hops

E[LB] = 2 (dIR + (3nl + 2n – 1)/2 *
[(kns)/r + c) + kndseat] )
Network delay per hop
Processing delay per hop

where n is number of participants.

O(n2)
MASCOTS 2008
33
Outline







Anonymity Crash Course
Anonymous Communication with Practical
Buses
Analysis of Practical Buses
Evolving Practical Buses to Taxis
Analysis of Taxis
Experimental Results
Conclusion
MASCOTS 2008
34
Buses Problem and Solution

Problem:



Processing Delay: Unowned seats wait
unnecessarily for owned seats to be replaced
Network Delay: Sending of unowned seats can be
pipelined
Solution: divide bus so that each node has a
taxi that contains only its own seats
MASCOTS 2008
35
Resulting Improvements

Processing Delay decreased by O(n)


Owned seats are delayed once per bus tour
instead of n times (see paper for proof)
Networking Delay decreased by O(n)

Forwarding of unowned taxis can be pipelined by
giving unowned taxis network priority over owned
taxis (see paper for proof)
MASCOTS 2008
36
Outline







Anonymity Crash Course
Anonymous Communication with Practical
Buses
Analysis of Practical Buses
Evolving Practical Buses to Taxis
Analysis of Taxis
Experimental Results
Conclusion
MASCOTS 2008
37
Taxis Detailed Model
Avg # of hops

E[LB] = 2 (dIR + (3nl + 2n – 1)/2 *
[(kns)/r + c) + kndseat] )
Network delay per hop



Processing delay per hop
Divide processing delay and network delay by n
E[LT] = 2 (dIR + (3nl + 2n – 1)/2 *
[(ks)/r + c/n) + kdseat] )
O(n)
MASCOTS 2008
38
Outline







Anonymity Crash Course
Anonymous Communication with Practical
Buses
Analysis of Practical Buses
Evolving Practical Buses to Taxis
Analysis of Taxis
Experimental Results
Conclusion
MASCOTS 2008
39
Experimental Methodology



Experimental implementation and benchmarking of
Practical Buses protocol and Taxis protocol
Beowulf cluster: 14 state-of-art CPUs, 1 Gbps LAN
Synthetically generated workload files:





Poisson message arrival process (30 messages/minute)
Message size: uniform random between 1 byte and 2 KB
Initiators and responders chosen uniformly at random
Uniform and non-uniform (Zipf) traffic models
Number of indirection nodes (layers): 1 or 2
MASCOTS 2008
40
Analysis of Practical Buses Fit
MASCOTS 2008
41
Analysis of Taxis Fit
MASCOTS 2008
42
Taxis versus Practical Buses
MASCOTS 2008
43
Outline







Anonymity Crash Course
Anonymous Communication with Practical
Buses
Analysis of Practical Buses
Evolving Practical Buses to Taxis
Analysis of Taxis
Experimental Results
Conclusion
MASCOTS 2008
44
Conclusions

The average message latency of Practical Buses
scales quadratically with number of participants




Model
Experimental results
Good fit of model to experimental results
The average message latency of Taxis scales linearly
with the number of participants



Model
Experimental Results
Good fit of model to experimental results
MASCOTS 2008
45
Future Work



More rigorous scalability testing for Taxis
(e.g., 2 →100 nodes)
PlanetLab experiments to study WAN effects
Utilize Taxis as a “stepping stone” for a new
protocol with logarithmic scalability
MASCOTS 2008
46
Thank-you
Questions???
MASCOTS 2008
47