[freehaven-cvs] slides for wpes04 talk

[arma@seul.org (Roger Dingledine)]

Update of /home2/freehaven/cvsroot/doc/routing-zones
In directory moria.mit.edu:/tmp/cvs-serv26834

Added Files:
	slides-wpes04.mgp 
Log Message:
slides for wpes04 talk


--- NEW FILE: slides-wpes04.mgp ---
%deffont "standard" xfont "Arial:style=Regular"
%deffont "thick" xfont "Arial:style=Bold"
%deffont "typewriter" xfont "Courier New:style=Regular"
%deffont "italic" xfont "Arial:style=Italic"
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%deffont "standard" xfont "comic sans ms-medium-r"
%%deffont "thick" xfont "arial black-medium-r"
%%deffont "typewriter" xfont "courier new-bold-r"
%%deffont "type2writer" xfont "arial narrow-bold-r"
%%deffont "standard"   tfont "standard.ttf",   tmfont "kochi-mincho.ttf"
%%deffont "thick"      tfont "thick.ttf",      tmfont "goth.ttf"
%%deffont "typewriter" tfont "typewriter.ttf", tmfont "goth.ttf"
%%deffont "standard" xfont "helvetica-medium-r", tfont "arial.ttf", tmfont "times.ttf"
%%deffont "thick" xfont "helvetica-bold-r", tfont "arialbd.ttf", tmfont "hoso6.ttf"
%%deffont "italic" xfont "helvetica-italic-r", tfont "ariali.ttf", tmfont "hoso6.ttf"
%%deffont "typewriter" xfont "courier-medium-r", tfont "typewriter.ttf", tmfont "hoso6.ttf"
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% Default settings per each line numbers.
%%
%default 1 leftfill, size 8, fore "black", back "white", font "thick", hgap 1
%default 2 size 8, vgap 10, prefix " ", ccolor "black"
%default 3 size 6, bar "gray70", vgap 0
%default 4 size 6, fore "black", vgap 0, prefix " ", font "standard"
%%
%%default 1 area 90 90, leftfill, size 9, fore "yellow", back "blue", font "thick"
%%default 2 size 9, vgap 10, prefix " "
%%default 3 size 7, bar "gray70", vgap 10
%%default 4 size 7, vgap 30, prefix " ", font "standard"
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% Default settings that are applied to TAB-indented lines.
%%
%tab 1 size 5, vgap 40, prefix "     ", icon arc "red" 50
%tab 2 size 4, vgap 35, prefix "            ", icon delta3 "blue" 40
%tab 3 size 3, vgap 35, prefix "                        ", icon dia "DarkViolet" 40
%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%page
%nodefault
%center, size 10, font "thick", back "white", fore "black"

Location Diversity in
Anonymity Networks

%size 7
Nick Feamster        Roger Dingledine        
MIT CSAIL        The Free Haven Project

%font "typewriter", fore "blue"
http://freehaven.net/

%font "thick", fore "black"
WPES, October 2004
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%page

Overview

%leftfill
The problem we're trying to solve.

Background: anonymity systems

Background: Internet routing

Some things we learned

Questions we still need to answer

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%page

The big picture

Alice wants to transact with Bob on the Internet (fetch a web page, send an email) without letting anybody link them together.

Alice wants to be safe from somebody watching her or somebody watching Bob.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%page

A trusted proxy isn't good enough

%newimage -xscrzoom 85 "single-hop.eps"
These proxies are trust/performance bottlenecks.

Add a constraint: want to be safe from a compromised middle node too.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%page

So: distributed trust

%newimage -xscrzoom 85 "whole-network.eps"

By using multiple hops, no single node can link Alice to Bob.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%page

Tor and Mixmaster

Two widely deployed anonymity networks (thousands of users each).

Tor is for TCP streams (low-latency).

Mixmaster is for email (high-latency).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%page

Two major attack classes

Follow-the-transaction attack:
	Try to learn each hop of a transaction and follow it from beginning to end.

%size 6
Endpoint attack:
	Use statistics to match a transaction coming into the network to a transaction leaving the network.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%page

Three major defense classes

Batching and pooling:
	Delay messages to get a large batch, and mix them together to hinder the adversary from linking Alice to the message that comes out.
%size 6
Padding:
	Senders provide decoy traffic as well as normal traffic.
%size 6
Dispersal:
	Reduce the chance that the adversary sees enough of the network to complete his attack.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%page

Dispersal approaches

Grow the network: a given adversary sees less.

Arrange the topology so messages can enter or exit at many places (e.g. cascade vs free route).

Location arbitrage: spread each transaction over multiple jurisdictions.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%page

Many different families of locations

E.g. Areas controlled by a single country, state, company, ...

E.g. Nodes running the same operating system or class of software.

We focus here on ISPs.
More correctly, "autonomous systems" (ASes).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%page

AS-level paths

The key insight: while we typically think of a connection as going from Alice to Node1, actually it traverses many different ASes on every hop.

Routing table gives the next closer AS for any IP.

BGP paths based on policies, not just shortest
path.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%page

Need to passively estimate paths

Can't pull down all routing tables. Can't traceroute.

Used Oregon RouteViews Project data to learn
adjacencies.

Mao et al's [24] estimation technique is >80%
right.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%page

Location independence metric

What is the chance that some AS is on both

(a) the path from Alice to the mix-net, and
(b) the path from the mix-net to Bob?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%page

Question one

Is considering IP prefix good enough?

Tarzan, Morphmix, etc recommend this.

Not the same. In practice, we see several cases of same-AS nodes with different prefixes.

Of the 5 pairs in Mixmaster in the same AS, three have different class A prefixes!

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%page

Question two (1)

How much can one AS attack inside the network?

This lets him follow a transaction (easier than doing stats).

Also means we're not getting the full protection of the number of hops we thought we had.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%page

Question two (2)

Top two AS-level adversaries to both Tor and Mixmaster: Level 3 and Abovenet.

Together they watch over half the links in the Tor
network!

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%page

Question two (3)

Choosing paths without replacement helps: a 4-hop Tor path can be observed by a single AS with prob .10, compared to .16 if replacement is
allowed.

Don't forget that forward paths may be different from reverse paths.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%page

Question three (1)

How much can one AS attack the endpoints?

Remember that it's sufficient to look at endpoints, both for low-latency and high-latency networks.

Endpoints can be first and last node, but they can also be Alice and Bob.

We picked some reasonable sounding Alices and Bobs, mostly in the US.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%page

Question three (2)

Given random entry and exit points, a single AS will often be able to win 10% to 30% of the time.

It's possible to reduce this to almost 0.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%page

Lessons: Node placement

Best node placement for protection against the AS-level adversary is in ASes that have the most links to other ASes: tier-1 ISPs.

A given transaction is safest when Alice, Bob, or both are in tier-1 ISPs.

With US-based Alices and Bobs, adding a far-flung node (e.g. in Asia) _hurts_ us, not helps.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%page

Future work (1)

Consider a more diverse set of Alices and Bobs.

How to get routing table to Alice? Are there practical approximations that still work ok?

How sensitive is this metric to adding or subtracting a few nodes?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%page

Future work (2)

What about repeated web fetches, using different entry and exit points each time -- how quickly does Alice's location independence degrade?

Correlation between speed/reliability of network and its location independence?

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%page

Future work (3)

Do this analysis for different location metrics, such as countries.

Caching at exit nodes (when feasible) changes the equation.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%page

Future work (4)

Akamai? Different routing, also dangerous
observer.

Do we _hurt_ anonymity by restricting path choices, against larger adversaries who can take advantage of knowing our algorithm?


***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs       in the body. http://freehaven.net/