[freehaven-cvs] first pass of edits

[feamster@seul.org (Nick Feamster)]

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

Modified Files:
	routing-zones.tex 
Log Message:
first pass of edits



Index: routing-zones.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/routing-zones/routing-zones.tex,v
retrieving revision 1.31
retrieving revision 1.32
diff -u -d -r1.31 -r1.32
--- routing-zones.tex	28 Jan 2004 07:35:09 -0000	1.31
+++ routing-zones.tex	28 Jan 2004 17:40:01 -0000	1.32
@@ -96,8 +96,7 @@
 topology so messages can enter or exit at more places in the network
 (compared to a cascade topology~\cite{disad-free-routes});
 or by \emph{jurisdictional arbitrage} --- coordinating network behavior
-so each transaction includes zones (i.e., jurisdictions) controlled by
-several different adversaries.
+so each transaction includes multiple administrative domains, or jurisdictions.
 
 In this paper, we investigate a variant of jurisdictional arbitrage by
 taking advantage of the fact that the Internet is divided into thousands
@@ -109,33 +108,50 @@
 % XXX unless it reflects something else. intra-network independence and
 % user-network independence? hm.
 entry point of a mix network and the path from the exit point will
-traverse the same AS.  We then consider the node selection algorithms of
-two existing mix networks---Tor~\cite{tor-design} and
-Mixmaster~\cite{mixmaster-spec}---and evaluate the independence metric for
-these networks.
+traverse the same AS.  We then consider the topologies and node
+selection algorithms of two existing mix
+networks---Tor~\cite{tor-design} and
+Mixmaster~\cite{mixmaster-spec}---and evaluate the independence metric
+for these networks.
 
-We find that both Tor and Mixmaster have multiple mix nodes in the same
-autonomous system.  Users of these networks should take care to avoid
-selecting two nodes from the same AS.  Furthermore,
-we note that {\bf XXX some property about mix paths and AS paths}.
-Users of these networks should take extreme care to select mix nodes to
+This paper presents several interesting results.  
+First, we find that both Tor and Mixmaster have multiple mix nodes in
+the same autonomous system.  Users of these networks should take care to
+avoid selecting two nodes from the same AS.  In light of this, we argue
+that node selection algorithms used in previous systems, such as
+Tarzan~\cite{freedman:ccs02} and MorphMix~\cite{morphmix:fc04}, are
+likely to be ineffective.
+
+Next, we measure the jurisdictional independence of inter-mix network
+paths and find that, given existing mix network topologies, the
+Mixmaster and Tor selection algorithms will nearly always result in
+paths that can be observed by a single AS in multiple locations.  We
+also discover that, because paths between mix nodes often cross the same AS,
+a user's vulnerability to eavesdropping does not decrease proportionally
+with the number of mix nodes in the path.
+
+Finally, using a model of typical senders and receivers in anonymity
+networks we measure the likelihood that a single AS can observe both the
+path from the sender to the entry node and from the exit node to the
+receiver; we find that entry and exit paths resulting from random entry
+and exit node selection are often likely to be observed by a single AS
+between 10\% and 30\% of the time, depending on the sender and receiver,
+and that the single AS that can observe these paths is always a backbone
+ISP.  Users of these networks should take care to select mix nodes to
 minimize the likelihood that the entry path and exit path for the mix
-network do not traverse the same AS.  We also argue that, because
-paths between mix nodes often cross the same AS, a user's
-vulnerability to eavesdropping does not decrease proportionally with the
-number of mix nodes in the path.
+network do not traverse the same AS.
+
 
 \section{Background}
 
-Here
 %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 also provide some background on Internet routing. 
+We first 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 also provide some background on
+Internet routing.
 
 \subsection{Anonymity networks}
 \label{subsec:background-anonymity}
@@ -169,32 +185,33 @@
 and long-term intersection or disclosure attacks against high-latency
 systems \cite{disad-free-routes,statistical-disclosure,e2e-traffic}.
 
-Mixmaster and Tor are deployed networks with dozens of nodes
-around the world (tables showing the current networks can be
-found in the Appendix). We will describe their threat models in
+Mixmaster and Tor are deployed networks with dozens of nodes around the
+world (Appendix~\ref{sec:mixnode_summary} has tables with the lists of
+nodes in each network). We will describe their threat models in
 Section~\ref{sec:threat-model} and their path selection algorithms in
 Section~\ref{sec:path-selection}.
 
-The idea of jurisdictional independence is not new. Tim May and
-Eric Hughes wrote about it in early posts to the cypherpunks list.
-Mixmaster operators attempt to track which ISPs can control
-each node, to get an informal intuition of the independence of the
-network~\cite{riot-remap}. Even designs published in the literature, such
-as Tarzan and Morphmix, aim to provide collusion resistance by comparing
-the IP of each peer~\cite{freedman:ccs02,morphmix:fc04}. Our contribution
-is to consider actual anonymity networks in the context of actual Internet
-routing tables, and come up with ways to quantify the results.
+Previous work has recognized the importance of jurisdictional
+independence.  Tim May and Eric Hughes wrote about the idea of
+jurisdictional independence in early posts to the cypherpunks list.
+Mixmaster operators attempt to track which ISPs can control each node,
+to get an informal intuition of the independence of the
+network~\cite{riot-remap}. Previous anonymity networks, such as Tarzan
+and Morphmix, aim to provide collusion resistance by comparing the IP of
+each peer~\cite{freedman:ccs02,morphmix:fc04} (our results show that
+this technique is ineffective). In this paper, {\em
+actual anonymity networks in the context of the properties of Internet
+routing at the AS-level} and design ways to quantify the results.
 
 \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 available data on Internet topologies and our assumptions
-regarding how well this data reflects the paths that packets actually
-travel.
+To determine the networks that packets will traverse between each node
+of a mix network, 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 available data on Internet
+topologies and our assumptions regarding how well this data reflects the
+paths that packets actually travel.
 
 \subsubsection{Border Gateway Protocol}
 
@@ -205,13 +222,13 @@
 Each AS has a network of routers that route traffic to global
 destinations using the information propagated by routing protocols.  To
 find the route to a destination IP address, a router typically performs
-a longest prefix match on that IP address to find the smallest IP prefix
+a ``longest prefix match'' on that IP address to find the smallest IP prefix
 in the routing table that contains that IP address.  For example, a
 router performing a route lookup for {\em IP address} {\tt 18.31.0.82}
 might find a route for the {\em prefix} {\tt 18.0.0.0/8}, a prefix that
 contains the destination IP address.  The router then forwards packets
 for that destination to the next hop specified for the route to the
-prefix.  Routers will select the route that is the {\em longest} prefix
+prefix.  Routers will select the route that is the {\em smallest} prefix
 that contains the IP address; for example, if a router's routing table
 had a prefix for, say, {\tt 18.31.0.0/16}, that router would prefer this
 route over the former.
@@ -224,7 +241,7 @@
 the AS.  Some of these routers will, in turn, exchange routes with other
 ASes.  A router will typically readvertise the route to neighboring
 ASes, prepending its own AS number to the AS path in the process.  In
-this fashion, BGP allows any AS to learn the AS-level path of a route to
+this fashion, BGP allows each AS to learn the AS-level path of a route to
 a destination that it learns via BGP.  
 
 ASes do not blindly propagate routes to all of their neighbors; rather,
@@ -257,7 +274,7 @@
 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
+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.
 
@@ -317,8 +334,7 @@
 policies, but the graph is fairly representative enough for our
 purposes.  In the future, we could improve our analysis by incorporating
 newer techniques for capturing AS-level topologies~\cite{Chang2004}.
-
-Knowledge of the AS-level topology is not enough to determine the
+Knowing the AS-level topology is not enough to determine the
 AS-level path between two arbitrary mix nodes; to determine this, we
 need to make further modeling assumptions, which we describe in
 Section~\ref{sec:mix_aspath}.
@@ -330,7 +346,7 @@
 AS. Such an adversary might be a curious ISP or a corrupt law enforcement
 officer abusing his subpoena powers.
 This threat model is based on the assumption that the ability to control
-more than one AS is significantly more rare, either because far fewer
+more than one AS is significantly more difficult, either because far fewer
 ISPs exist that control multiple ASes, or because law enforcement will
 be less willing to face the increased accountability and risk associated
 with obtaining multiple unapproved subpoenas.
@@ -342,7 +358,7 @@
 attacks into intra-network attacks and endpoint attacks, as described
 in Section~\ref{subsec:background-anonymity}.
 
-Most clearly successful is the endpoint attack on low-latency networks:
+Endpoint attacks on low-latency networks are most likely to succeed:
 an adversary observing both Alice and Bob can quickly learn that they
 are communicating. Onion Routing analysis~\cite{onion-routing:pet2000}
 has shown that an adversary observing $c$ of the $n$ nodes in the network
@@ -385,7 +401,7 @@
 \subsection{Node Selection in Mix Networks}
 \label{sec:path-selection}
 
-To build a path in an anonymity network, clients must somehow learn a set
+To build a path in an anonymity network, clients must somehow discover a set
 of currently available nodes. In Mixmaster, clients examine the output
 of ``pinger'' software that measures node reliability and publishes keys
 and addresses for each remailer~\cite{echolot}. In Tor, clients download
@@ -397,7 +413,7 @@
 from this node (some operators choose instead to be middleman nodes,
 to avoid needing to deal with abuse complaints.)
 
-We abstract away the details of fetching this list: assume Alice ends up
+We abstract the details of fetching this list: assume Alice ends up
 with a set $N$ of possible choices, of which $E \subseteq N$ are exit nodes.
 We also assume that all nodes in the network are listed as working.
 
@@ -469,7 +485,7 @@
   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
+  question.}  To determine 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
@@ -516,12 +532,14 @@
 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
+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{Data}
@@ -533,10 +551,10 @@
 
 \subsection{Mix Networks, Senders, and Receivers}
 
-To perform our evaluation of node selection in the Mixmaster and Tor mix
-networks, we use the list of operational mix nodes for each respective
-network; the tables Appendix~\ref{sec:mixnode_summary} provide lists of
-mix nodes for each of these networks.
+To evaluate node selection in the Mixmaster and Tor networks, we use the
+list of operational mix nodes for each respective network; the tables
+Appendix~\ref{sec:mixnode_summary} provide lists of mix nodes for each
+of these networks.
 
 Since we are also interested in the AS-level paths between the sender
 (Alice) and the mix entry point, and between the mix exit point and the
@@ -549,27 +567,28 @@
 network, a DSL network, etc.) and that Bob is a content host located at
 a data hosting ISP.
 
-To generate a reasonable, unbiased list of ASes senders might be
+To generate a reasonable list of ASes senders might be
 located, we created a list DSL and cable modem providers from {\tt
 www.dslreports.com} that would be likely senders and mapped these
 providers to their respective AS numbers. To generate a list of typical
 receivers, we sample reasonable sites from comScore Media Metrix's ``Top
 50 US Internet Properties'' from December 2003~\cite{www-comscore}, as
-well as sites that we think may be popular on anonymity networks.  The
-lists of senders and receivers that we used for our experiments are in
+well as sites that we think might be popular on anonymity networks.  The
+lists of senders and receivers that we used in our experiments are in
 Appendix~\ref{sec:send_recv}.
 
 
 \subsection{Network Topology}
 
-To generate an estimate of AS-level topology, we use the routing table
-dump from the {\tt route-views.oregon-ix.net} route server on January
-25, 2004 at 10:22 p.m. GMT.  The table has 67 external BGP (eBGP) feeds from
-53 ASes (some ASes have multiple eBGP feeds to the route server).  We
-use this table to (1)~generate our view of the AS-level topology,
-including inter-AS relationships, and compute pairwise AS-level shortest
-paths, as we described in Section~\ref{sec:mix_aspath} and (2) map IP
-addresses to the ASes where they are located.
+To generate an estimate of the Internet's AS-level topology, we use the
+routing table dump from the {\tt route-views.oregon-ix.net} route server
+on January 25, 2004 at 10:22 p.m. GMT.  The table has 67 external BGP
+(eBGP) feeds from 53 ASes (some ASes have multiple eBGP feeds to the
+route server).  We use this table to (1)~generate our view of the
+AS-level topology, including inter-AS relationships, and compute
+pairwise AS-level shortest paths, as we described in
+Section~\ref{sec:mix_aspath} and (2) map IP addresses to the ASes where
+they are located.
 
 
 \section{Results}\label{sec:results}
@@ -730,7 +749,7 @@
 MIT use AS 3356 for most inbound and outbound paths, with the exception
 of paths to and from Internet2 destinations.
 
-Second, many paths in the Internet, particularly those between edge
+Second, many paths in the Internet, particularly those between two edge
 networks, will traverse at least one large ``tier-1'' ISP (i.e., an ISP
 that operates its own backbone and does not by upstream service from
 another ISP).  Not surprisingly, Table~\ref{tab:path_ind} shows that
@@ -761,9 +780,9 @@
 of the edges along the mix network path.  Second, Tor's node selection
 algorithm seems to defend it slightly against observation at multiple
 edges, but this node selection scheme helps Mixmaster less.  This result
-makes sense: because Tor only as 14 nodes, random node selection is much
+makes sense: because Tor has only 14 nodes, random node selection is much
 more likely to result in the same hop being used twice along a single
-mix path, if a constraint preventing this is not imposed.
+mix path, if this is not explicitly prevented.
 
 \subsection{Jurisdictional Attacks on Entry and Exit Paths}
 
@@ -858,8 +877,7 @@
 tier-1 ISP (e.g., AS 4999, which is associated with Sprint).  This might
 be because the path from the sender to the entry point is already
 located in a tier-1 ISP, and thus will not have to cross other tier-1
-ISPs en route to the entry point; this result deserves further
-exploration.
+ISPs en route to the entry point.
 
 \section{Design Recommendations and Future Work}\label{sec:design}
 
@@ -868,12 +886,12 @@
 recommendations with regard to mix network design.  First, mix networks
 should select paths with the underlying AS-level topology in mind.
 Second, mix networks should strive to deploy more nodes in locations
-with a large number of AS-level exit points.  
+with rich connectivity to other ASes.  
 
 \subsection{Explicit Consideration of AS-level Paths}
 
 Our results suggest that, to reduce the probability of eavesdropping
-attacks using dispersity, designers and users of mix networks should
+attacks using dispersal, designers and users of mix networks should
 take into account the underlying AS-level paths of the underlying mix
 network path.  Mix network paths can be made more if senders increase
 the jurisdictional independence of the paths they use, by explicitly
@@ -898,7 +916,7 @@
 which mix network designers should place nodes as they expand their
 networks. 
 
-One observation that can be made from our work is that mix nodes that
+Our results suggest that that mix nodes that
 are placed in edge networks (e.g., cable modem and DSL providers,
 universities, etc.) are likely to traverse the same AS on both the
 inbound and outbound paths to those nodes.  Far-flung node locations

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