[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] more fleshing out of background section
Update of /home/freehaven/cvsroot/doc/routing-zones
In directory moria.mit.edu:/tmp/cvs-serv6016
Modified Files:
routing-zones.tex
Log Message:
more fleshing out of background section
Index: routing-zones.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/routing-zones/routing-zones.tex,v
retrieving revision 1.4
retrieving revision 1.5
diff -u -d -r1.4 -r1.5
--- routing-zones.tex 18 Jan 2004 07:37:15 -0000 1.4
+++ routing-zones.tex 18 Jan 2004 07:39:55 -0000 1.5
@@ -1,6 +1,9 @@
\documentclass{llncs}
+\usepackage{pst-all}
+\newpsobject{showgrid}{psgrid}{subgriddiv=2,griddots=10,gridlabels=6pt}
+
\newenvironment{tightlist}{\begin{list}{$\bullet$}{
\setlength{\itemsep}{0mm}
\setlength{\parsep}{0mm}
@@ -87,6 +90,14 @@
\section{Background}
+In this section, we provide necessary background information on
+anonymizing networks and on Internet routing. We describe the different
+types of mix networks and present a brief explanation of the types of
+attacks that each type of mix network must protect against. Because we
+argue that designers of mix networks should, in certain cases, pay
+attention to the IP-level path traversed by a path through a mix
+network, we provide some background on Internet routing.
+
\subsection{Anonymity networks}
describe nested crypts, and mix networks in general, to show the endpoint
@@ -105,15 +116,17 @@
so if we can make a good improvement in protection with not too much
effort, we should.
-\subsection{Overview of Internet Routing}
+\subsection{Overview of Internet Routing and Topology}
+
Our overall goal is to determine the networks that packets will
traverse between each node of a mix-net. To do this, we must first
understand how packets are routed between two arbitrary hosts on the
Internet. In this section, we first present a brief overview of
interdomain routing (i.e., routing between ISPs) on the Internet. We
-then describe how to estimate the network-level path between two hosts
-on the Internet using the BGP routing tables.
+then describe available data on Internet topologies and our assumptions
+regarding how well this data reflects the paths that packets actually
+travel.
\subsubsection{Border Gateway Protocol}
@@ -156,17 +169,30 @@
exchange traffic between their own networks (and the networks of their
customers), but do neither pays the other for this privilege.
+\begin{figure}[t]
+\include{policy_summary}
+\caption{Summary of common export restrictions and route preferences.}
+\label{fig:policy_summary}
+\end{figure}
+
BGP is a distinctive routing protocol because it is based on {\em
policy}, rather than on shortest paths. For example, an AS will
typically prefer to route traffic to a destination via one of its
customers (who pays it for connectivity) than via one of its providers
-(whom it must pay to send traffic towards) or one of its peers. These
-relationships also determine which routes one AS will advertise to
-another. For example, an AS will typically not advertise a route
-learned from one of its peers or providers to any of its other peers or
-providers: doing so would constitute an implicit agreement to forward
-traffic (i.e., provide ``transit'' service) between two of its
-providers, two of its peers, etc. {\bf XXX maybe put a figure here}
+(who it must pay to send traffic towards) or one of its peers. In
+Figure~\ref{fig:policy_summary}, an AS will typically prefer a route to
+a destination via its customer, if one exists, over one through a peer
+or a provider. These relationships also determine which routes one AS
+will advertise to another. For example, an AS will typically not
+advertise a route learned from one of its peers or providers to any of
+its other peers or providers: doing so would constitute an implcit
+agreement to forward traffic (i.e., provide ``transit'' service) between
+two of its providers, two of its peers, etc. The AS in
+Figure~\ref{fig:policy_summary} would advertise routes learned from its
+customer to all of its neighbors, but would not readvertise routes learned
+from Peer 1 to Peer 2 (and vice versa) nor to its provider; it would
+advertise the routes learned from its provider to its customer, but not
+to other peers.
\begin{figure}
\begin{small}
@@ -200,7 +226,7 @@
\subsubsection{AS-level Internet Topology}
-There are many publically-available places that provide access to
+There are many publicly-available places that provide access to
routing table data. The most prevalent is the Oregon Routeviews
Project~\cite{www-routeviews}, which maintains a route server that peers
with more than 30 ASes. Each of these ASes sends its routing tables to
@@ -236,11 +262,13 @@
By requiring the adversary to control multiple ASs, we raise the bar
for breaking the anonymity of the system.
-\subsection{Mix-nets}
+\subsection{Mix Networks}
A. Overview of how systems like Tor select mix nodes, and our
approximation of this (for the purposes of analyzing the
routeviews data)
+Here we should also describe the current list of nodes for each of the
+mix networks we analyze. A table would be appropriate.
\subsection{AS-level path estimation}
@@ -279,7 +307,7 @@
technique.
\begin{enumerate}
-\itemsep=1pt
+\itemsep=3pt
\item {\em From one or more BGP routing tables, construct an AS-level graph
representing the Internet's topology.} Routes in BGP routing tables have an
AS path attribute; this provides a list of AS adjacencies. For
@@ -299,6 +327,23 @@
between two ASes and, as a result, infer the wrong AS-level path to a
destination.
+\item {\em Determine the origin and destination AS for the path in
+ question.} To figure out the AS-level path between two hosts, we must
+ obviously determine the ASes where the hosts are located. This is
+ reasonably easy: generally, it is sufficient to look in a BGP routing
+ table and find the final AS in the AS path for a particular
+ destination. For example, in Figure~\ref{fig:bgp_example}, the last
+ AS in each AS path to the prefix {\tt 18.0.0.0/8} is AS~$3$ (MIT);
+ therefore, it is generally safe to assume that any prefix contained
+ within {\tt 18.0.0.0/8} is located in AS~$3$.
+
+\vspace{0.1in}
+ This approach has a few subtleties. First, ASes often allocate
+ address space to their customers from their own address space, this
+ technique should be applied to the longest matching prefix in the
+ routing table. {\bf XXX multiple origin AS conflicts}
+
+
\item {\em Determine the relationships between each pair of ASes.} This
is a notoriously difficult problem, because ASes typically guard the
nature of the relationships they have with neighboring ASes.
@@ -310,25 +355,39 @@
Internet paths to assign pairwise relationships between ASes. That
is, an AS path traverses a sequence of customer-provider edges, zero
or one peering edges, followed by a sequence of provider-customer
- edges. The trick is to follow
+ edges. Then, in each AS path, a AS pair can be assigned either a
+ customer-provider or a provider-customer relationship; every pair
+ before the AS with the highest degree in the path is assigned a
+ customer-provider relationship, and every pair after this AS is
+ assigned a provider-customer relationship. The complete details of
+ the inference algorithm are provided in previous work~\cite{Gao2001}.
-\item {\em Determine the origin and destination AS for the path in
- question.}
\item {\em Estimate the AS-level path between the two ASes by finding
- the shortest AS path that complies with common policy practices.} Mao
- finds that this type of technique works XX\% of the time. As these
- techniques improve, the accuracy of our analysis will also improve.
- More importantly, more accurate techniques for estimating the AS-level
- path between two arbitrary Internet hosts will allow the initiator of
- a mix-net to make more informed decisions about the mix nodes it
- should choose.
+ the shortest AS path that complies with common policy practices.}
+ Previous work suggests that this type of technique works XX\% of the
+ time~\cite{Mao2004}. As AS-level path estimation techniques improve,
+ the accuracy of our analysis will also improve. More importantly,
+ more accurate techniques for estimating the AS-level path between two
+ arbitrary Internet hosts will allow the initiator of a mix-net to make
+ more informed decisions about the mix nodes it should choose.
\end{enumerate}
+Given both a model for how anonymizing networks select nodes and a way
+to estimate the AS-level path between two arbitrary hosts on the
+Internet, we can determine the complete set of ASes that a typical mix
+network path traverses. For example, we can determine if a mix network
+path will traverse the same AS twice (i.e., at two different hops along
+the mix path). We can also determine whether a mix network path
+traverses the same AS anywhere between the origin and the entry point
+and between the exit point and the destination (a situation that would
+make timing attacks more feasible). We explore these questions in
+further detail in Section~\ref{sec:results}.
-\section{Results}
+
+\section{Results}\label{sec:results}
[We should of course take a look at these questions abstractly,
to get a feel for how to answer them, but I'd like to get results on
***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs in the body. http://freehaven.net/