[freehaven-cvs] initial intro and outline for routing-zones paper

[arma@seul.org (Roger Dingledine)]

Update of /home/freehaven/cvsroot/doc/routing-zones
In directory moria.mit.edu:/home2/arma/work/freehaven/doc/routing-zones

Added Files:
	routing-zones.tex 
Log Message:
initial intro and outline for routing-zones paper


--- NEW FILE: routing-zones.tex ---

\documentclass{llncs}

\newenvironment{tightlist}{\begin{list}{$\bullet$}{
  \setlength{\itemsep}{0mm}
    \setlength{\parsep}{0mm}
    %  \setlength{\labelsep}{0mm}
    %  \setlength{\labelwidth}{0mm}
    %  \setlength{\topsep}{0mm}
    }}{\end{list}}

\begin{document}

%\title{Automated Jurisdictional Arbitrage}
%\title{Blocking Observers with }
%\title{Improving anonymity by considering routing zones}
\title{Blocking eavesdroppers by exploiting routing zones}
\author{Nick Feamster\inst{1} \and Roger Dingledine\inst{2}}
\institute{MIT Laboratory for Computer Science \email{(feamster@lcs.mit.edu)} \and
The Free Haven Project \email{(arma@mit.edu)}}
\maketitle
%\pagestyle{empty}

\begin{abstract}


\end{abstract}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Introduction}
\label{sec:intro}

A variety of organizations, ranging from corrupt law enforcement
to curious telcos, % to subpoena-wielding religious fanatics
can passively observe large pieces of the Internet. Anonymity
networks aim to provide communications privacy for individuals or
groups on the Internet, but such networks are still vulnerable to powerful
eavesdroppers. Against high-latency \emph{mix networks} such as Mixminion
\cite{minion-design}, an adversary who observes a large volume of
network traffic can notice over time that certain recipients are more
likely to receive messages after given senders have transmitted messages
\cite{disad-free-routes,statistical-disclosure,e2e-traffic}. Low-latency
networks like Onion Routing \cite{tor-design} are more directly
vulnerable: an eavesdropper on both ends of the connection can quickly
link sender to recipient through packet counting or timing attacks
\cite{defensive-dropping,SS03}.

Anonymity designs use three major strategies to mitigate these attacks.
{\bf{Batching and pooling:}} The network collects a group of input
messages and reorders them before they exit, to prevent the adversary
from learning which message in the batch originated from a given sender
\cite{chaum81,trickle02}.
% (Of course, this only works if the system can tolerate some latency.)
{\bf{Padding:}} Senders also provide decoy traffic, to
complicate the adversary's attempts to correlate sender and receiver
\cite{pipenet,defensive-dropping,langos02}.
%Pipenet \cite{pipenet} conceals traffic patterns by
%constant padding on every link, at the cost of robustness. Levine et al
%show in \cite{defensive-dropping} that a small amount of dummy padding
%mixed into the circuit can significant degrade the effectiveness of
%timing attacks. 
%Berthold and Langos aim to increase the
%difficulty of intersection attacks with a scheme for preparing plausible
%dummy traffic and having other nodes send it for you while you're offline
%\cite{langos02}; but their design has many practical problems.
{\bf{Dispersal:}} Reducing the chance that the adversary sees
both endpoints for a given communication can entirely block some
attacks on low-latency networks, and slow down intersection attacks on
high-latency networks.

Dispersal can be achieved by increasing the number of nodes in the
network, so an adversary of a given strength sees less of the network
\cite{econymics,bennett:pet2003}; by arranging the overlay topology so
messages can enter or exit at more places in the network \cite{something};
or by \emph{jurisdictional arbitrage} --- coordinating network behavior
so each transaction includes zones (e.g. jurisdictions) controlled by
several different adversaries \cite{something}.

In this paper we investigate a variant of jurisdictional arbitrage
based on Internet routing zones. By taking into account the topology
of the underlying Internet routing, we can learn how vulnerable we
are to certain classes of adversary, and take steps to decrease that
vulnerability. Specifically, we show <the things that we learn later>.

\section{Background}

\subsection{Anonymity networks}

describe nested crypts, and mix networks in general, to show the endpoint
attack is the right issue

	- High-latency vs. low-latency anonymity networks, and the
	  different assumptions that are reasonable to make in each case
	  => conclusion is that for low-latency stuff, you can't mix
	     arbitrarily.  this is the domain where our approach is most
	     applicable
but also similarly useful for high-latency systems

just as with \cite{onion-routing:pet2000}, an adversary observing a zone
with c nodes wins $\frac{c}{n}^2$ of the transactions with no effort.

so if we can make a good improvement in protection with not too much
effort, we should.

\subsection{Internet topology}
	B. Network Topology

	- Brief overview of the structure of the internet, its division
	  in to ASes (ISPs), best route selection, etc.

	- Inferring AS-level paths.  Work from Mao et al. on how to
	  predict/estimate the sequence of ASes that a packet will
	  travel through.

	- Brief mention of routeviews, perhaps

\section{Model/Analysis Techniques}

	A. Overview of how systems like Tor select mix nodes, and our
	   approximation of this (for the purposes of analyzing the
	   routeviews data)

	B. How we determine the AS-level path between two arbitrary
	   nodes.
	   o pretty easy when you have access to the source (i.e., the
	     initial vertex)
	   o more difficult when you don't have access to either of the
	     two endpoints but you can make reasonable approximations

	     - passive: use something like Mao's techniques on
	       routeviews data.  basically, a constrained shortest AS
	       hop count thing

	     - active: if you could actually _ask_ one of these nodes to
	       do traceroutes, or send you a view of its routing table,
	       you could obviously do better, but this:
	       	- is likely slow/can't be precomputed
		- might tip off the adversary
		- is open to attacks where the node lies

\section{Results}

[We should of course take a look at these questions in the abstract,
to get a feel for how to answer them, but I'd like to get results on
the actual real-world networks too. I can easily make a list of current
Tor nodes, current Mixminion nodes, current Mixmaster nodes, and we
can compare robustness of the network to zone-based attacks. [We need
a cool new name for "zone-based attack".] Then we can see how stable
the properties are: can we change things a lot by adding a few nodes,
or do we need significant membership changes? -RD]

	A. Given:
	   o Our model of node selection (for things like Tor)
	   o Our AS-level path approximation:

	   => How often do the entry and exit paths (i.e., Alice->Entry
	      and Exit->Bob) cross the same AS path?

	   => Can you do something intelligent to prevent this from
	      happening?  i.e., constrain node selection?

	   => Even if you do something intelligent about selecting exit
	      nodes, will this choice provide the adversary information
	      about where Alice is coming from (i.e., what her direct
	      upstream ISP is?)

	      (I actually don't think it's too big of a deal, because it
	      simply just tells the adversary where Alice is _not_, but
	      there are plenty of places Alice could still be...)

	B. How do these results change as we change our assumptions
	   about the set of nodes from which you can select:
	   
	   - If you have 10 nodes in the US, where is the best place to
	     have them?

		hypothesis: there are about 10 "tier-1 ISPs".  maybe one
		in each of those probably gives you sufficient set of
		choices, without giving too much info away based on your
		choices from the 10.

		an alternative approach would picking 10 very far-flung 
		edge ISPs who have different upstreams, etc.  this may
		work better, actually, though you do run the risk of
		having each pairwise path go through 1 or 2 of the same
		ISPs if you are not careful.

	   - How much do transatlantic nodes help, etc?  i.e., Would you
	     do anything differently if you had this option?

\section{Design Recommendations}

	Given our observations, what design recommendations can we make
	for systems like Tor re: node selection?

\section{Conclusion}

	This area has been overlooked in the past;  considering network
	level paths is important when defending against a GPA, esp. in
	low-latency networks.  

	We have provided some first steps in looking at network-level
	paths for node selection and its implications for GPA.

	Proposed some design recommendations for Tor (or, depending on
	our results, found that the Tor selection works reasonably
	well).

%\section*{Acknowledgements}

\bibliographystyle{plain}
\bibliography{routing-zones}

\end{document}


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