Transcript nms.csail.mit.edu

Slicing the Onion:
Anonymity Using Unreliable Overlays
Sachin Katti
Jeffrey Cohen & Dina Katabi
Problem Statement
Leverage existing popular P2P overlays
to send confidential, anonymous
messages without keys
Overlays rock!
Ideal for anonymous communication
• Thousands of nodes
• Plenty of traffic to hide anonymous
communication
• Diverse membership  Nodes unlikely to
collude
• Dynamic  Hard to track
Overlays suck!
• Nodes don’t have public keys
• Nodes are not trustworthy
• Nodes are unreliable
This talk:
Information Slicing
• Message confidentiality, and source and
destination anonymity
• No public keys
• Churn resilient
1. Message Confidentiality
Without Keys
Confidentiality via Information Slicing
Split message to random pieces and send
pieces along node-disjoint paths
“Borat: Cultural
Leanings of America”
“Borat: Cultural”
“Leanings of America”
a11 a12 
“Borat: Cultural”
a
 “Leanings of America”
a
 21 22 
“aaspdgfqw”
“asdlfrwe”
Original Message
Split into two
Randomize them!
Random pieces
Confidentiality via Information Slicing
a11, a12 “aaspdgfqw”
Me
a21, a22 “asdlfrwe”
D
Message Recovery by destination
a11 , a12 ,“aaspdgfqw”
a21 , a22 , “asdlfrwe”
a11
a
 21
a12 
a 22 
1
“aaspdgfqw”
“asdlfrwe”
“Borat: Cultural”
“Leanings of America”
“Borat: Cultural
Leanings of America”
Received random pieces
Matrix inversion
Pieces of
original message
Original Message
Even an attacker that gets all but one piece
cannot decode!
Destination gets all pieces  can decode 
2. Anonymity without Keys
System Setup
Anonymous communication has two phases
• Route Setup
• A node learns how to forward a received
message
• Data transmission
• Just follow the routes
Setup Anonymous Routes
• Each node knows its next hop
• No one else knows the next hop of a node
• Why not tell each node the ID of its next
hop in a confidential message?
Idea : Build anonymity by confidentially
sending to each node it’s routing info!
Naïve way to send to a node its next hop
Exponential Blowup!
Challenge: Exponential Blowup
Solution:
Reuse nodes without giving them
too much information
V
Z
W
R
Z’s next hop information: IZ1, IZ2
R’s next hop information: IR1,IR2
Challenge: Exponential Blowup
Solution:
Reuse nodes without giving them
too much information
V
IZ1
Z
IZ2
IR1
W
IR2
R
V and W will know Z and R’s next hops
Challenge: Exponential Blowup
Solution:
Reuse nodes without giving them
too much information
V
IZ1
Z
IR1
W
R
Reuse V to send pieces that belong to different
nodes
Challenge: Exponential Blowup
Solution:
Reuse nodes without giving them
too much information
V
IZ1
IZ2
W
Z
IR1
IR2
R
Reuse nodes to send multiple pieces as long as
the pieces belong to different messages
Slicing Protocol
Source has multiple IP addresses
S
S’
Slicing Protocol
Source organizes nodes into stages
S
V
Z
D
S’
W
R
X
Slicing Protocol
Destination D is placed randomly (here in last stage)
S
V
Z
D
S’
W
R
X
Slicing Protocol
Source confidentially tells each node its next hop info
S
V
Z
D
S’
W
R
X
Slicing Protocol
V receives the ids of its next hops along disjoint paths
S
IV1
V
Z
D
W
R
X
IV2
S’
Slicing Protocol
V also receives one piece meant for Z and one for R,
but cannot decipher their next hops
S
IV1 , IZ1
V
Z
D
W
R
X
IV2 , IR2
S’
Slicing Protocol
W also receives its info and pieces for Z and R
W cannot decipher Z’s and R’s next hops
S
IV1 , IZ1
IV2 , IR2
S’
V
Z
D
R
X
IW1, IR1
IW2 , IZ2
W
Slicing Protocol
V and W have pieces meant for Z and R
S
S’
IZ1, IR2
V
Z
D
W
R
X
IZ2 , IR1
Slicing Protocol
V and W forward the pieces meant for Z and R
S
IV1 , IZ1
V
IZ1
Z
D
R
X
IR2
IV2 , IR2
S’
IW1, IR1 IZ2
IW2 , IZ2
W
IR1
Slicing Protocol
Node disjoint paths to deliver to Z its IZ1, IZ2
V and W do not have enough pieces to know Z’s info
S
IV1 , IZ1
V
IZ1
Z
D
R
X
IR2
IV2 , IR2
S’
IW1, IR1 IZ2
IW2 , IZ2
W
IR1
Slicing Protocol
The same for R
S
IV1 , IZ1
V
IZ1
Z
D
R
X
IR2
IV2 , IR2
S’
IW1, IR1 IZ2
IW2 , IZ2
W
IR1
Slicing Protocol
V and W are reused without revealing anything
about Z and R’s routing information
S
IV1 , IZ1
V
IZ1
Z
D
R
X
IR2
IV2 , IR2
S’
IW1, IR1 IZ2
IW2 , IZ2
W
IR1
Slicing Protocol
Similarly source constructs entire graph
S
V
Z
D
S’
W
R
X
Slicing Protocol
S
V
Z
D
S’
W
R
X
Anonymity without keys!
3. Dealing With Churn
Slicing Protocol - Churn
• What if node V departs?
S
V
Z
D
S’
W
R
X
Slicing Protocol - Churn
• What if node V departs?
• Destination cannot decode
S
S’
V
Z
D
W
R
X
X
How Do We Combat Churn?
• Churn causes data loss
• Typical solution  Add Redundancy
• Use coding to efficiently add redundancy
Source Coding the Data
• Source Coding (Erasure Codes)
• Split into 3 pieces instead of 2
a11
a
 21
a 31
a12 
m 
a 22   1 
m2 

a 32 
I1 
 
I2 
I3 
 
• Any 2 pieces suffice to retrieve data
a 21
a
 31
a 22 
a 32 
1
I2 
I 
 3
m1 
m 
 2
• Added redundancy of (1/2) = 50%
Source
Coding
For
Robustness
S
Z
V
D
X
S1
W
R
X
S2
U
P
Y
tolerate
one
• Source
Destinationcoding
D gets twocan
pieces
 Can decode
node failure in the network
Source
Coding
For
Robustness
S
Z
V
D
X
S1
W
R
X
S2
U
P
Y
• What if a second node (here Z) fails?
Source
Coding
For
Robustness
S
Z
V
X
X
D
S1
W
R
X
S2
U
P
Y
• What if a second node (here Z) fails?
• Destination D cannot decode
Coding
partially
solves
problem
S
Z
V
X
X
D
S1
W
R
X
S2
U
P
Y
• Focus on node R
Coding partially solves problem
I1
R
I2
Due to upstream node failure, R receives
2 pieces instead of 3
Coding partially solves problem
I1
I1
R
I2
I2
R can only send out two pieces now,
Initial redundancy is destroyed
Regenerating Redundancy
I1
R
I1  a11m1  a12 m2
I2  a21m1  a22 m2
I2
Pieces are linear combinations of message fragments
Network Coding
I1  a11m1  a12 m2
R
I1
I2
I2  a21m1  a22 m2
Take Linear combination
of the pieces
I  I1  I2  (a11  a21 )m1  (a12  a22 )m2
'
3
New piece
I
'
3
R can create a linear combination of the pieces he
received to generate a new piece
Network Coding
I1
I1
I2
R
I2
I
'
3
R can now send out 3 pieces instead of 2
Redundancy is regenerated inside the network
Network Coding
I1
I1
I2
R
I2
I
'
3
Network coding can tolerate one
Can tolerate downstream node failures
node failure in every stage
General Network Coding
• Nodes send linear combinations of incoming pieces
• Technique generalizes to any number of extra pieces
For k extra pieces, network
coding tolerates k failures in
every stage
4. Evaluation
Evaluation Environment
• Implementation in Python
• Evaluated both in simulation and on PlanetLab
• Evaluate anonymity, performance and churn
resilience
• Each metric is evaluated against the optimal
existing baseline
Anonymity
• Simulate an overlay of 10000 nodes
• Attackers are placed randomly in the network
• Attackers can control nodes, snoop on their
edges, and collude
• Comparison with Chaum mixes (optimal baseline)
• Entropy is standard anonymity metric
 P( x) log(P( x))
Anonymity  
log(N )
x
How anonymous is information slicing?
Anonymity
Source Anonymity
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
Chaum mix
Info. Slicing
0
0.005
0.05
0.3
0.7
Fraction of Attacking Nodes
High anonymity despite no keys
Churn Resilience
• Compared against practical anonymity
system  Onion Routing
• For fairness, onion routing is modified to
have redundancy using source coding
• Metric:
• Prob. of successfully sending a message,
given a particular redundancy
Churn Resilience
Probability of Success
Results for a Probability of Node Failure = 0.3
Info. Slicing
Onion Routing
with source coding
Added Redundancy
Large increase in probability of success
because of network coding
Implementation on PlanetLab
Probability of Success
Churn Resilience - Planetlab
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
Information
Slicing
Onion Routing
with source
coding
0
0.5
1
Added Redundancy
1.5
Network Coding nearly doubles the
churn resilience with the same overhead!
Performance
• Two nodes in each stage and five stages
PlanetLab
Info. Slicing
Onion Routing
No. of Stages
Throughput (Mb/s)
Throughput (Mb/s)
Local Network
Info. Slicing
Onion Routing
No. of Stages
Parallel paths  Increased throughput
Conclusion
Enabled anonymous communication in P2P
overlays with no keys.
Information Slicing provides
• Confidentiality  Node disjoint paths
• Low Cost Anonymity  Node Reuse
• Churn Resilience  Network Coding