[freehaven-cvs] addressing reviewer comments

[feamster@seul.org (Nick Feamster)]

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

Modified Files:
	routing-zones.bib routing-zones.tex 
Log Message:
addressing reviewer comments



Index: routing-zones.bib
===================================================================
RCS file: /home/freehaven/cvsroot/doc/routing-zones/routing-zones.bib,v
retrieving revision 1.19
retrieving revision 1.20
diff -u -d -r1.19 -r1.20
--- routing-zones.bib	8 Jun 2004 04:12:41 -0000	1.19
+++ routing-zones.bib	17 Jun 2004 06:50:37 -0000	1.20
@@ -334,3 +334,12 @@
     month = nov,
     year = "2002"
 }
+
+@InProceedings{Griffin2002,
+  author = 	 {Timothy Griffin and Gordon Wilfong},
+  title = 	 {On the Correctness of {IBGP} Configuration},
+  booktitle = {Proc. ACM SIGCOMM},
+  year = 	 {2002},
+  address = 	 {Pittsburgh, PA},
+  month = 	 {August},
+}

Index: routing-zones.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/routing-zones/routing-zones.tex,v
retrieving revision 1.68
retrieving revision 1.69
diff -u -d -r1.68 -r1.69
--- routing-zones.tex	17 Jun 2004 02:22:20 -0000	1.68
+++ routing-zones.tex	17 Jun 2004 06:50:37 -0000	1.69
@@ -20,11 +20,11 @@
 
 \begin{document}
 
-%\title{Automated Jurisdictional Arbitrage}
+%\title{Automated Location Arbitrage}
 %\title{Blocking Observers with }
 %\title{Improving anonymity by considering routing zones}
 %\title{Blocking eavesdroppers by exploiting routing zones}
-%\title{Jurisdictional Diversity in Anonymity Networks}
+%\title{Location Diversity in Anonymity Networks}
 \title{Location Diversity in Anonymity Networks}
 \author{Nick Feamster\inst{1} \and Roger Dingledine\inst{2}}
 \institute{MIT Laboratory for Computer Science \email{(feamster@lcs.mit.edu)} \and
@@ -94,15 +94,15 @@
 the overlay
 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
+or by \emph{location arbitrage} --- coordinating network behavior
 so each transaction is spread over multiple jurisdictions.
 
-In this paper, we investigate a variant of jurisdictional arbitrage that
+In this paper, we investigate a variant of location arbitrage that
 takes advantage of the fact that the Internet is divided into thousands
 of independently operated networks called {\em autonomous systems}
 (ASes). By considering the topology of the underlying Internet routing,
 we can assess the vulnerability of existing mix networks to certain classes
-of adversary.  Specifically, our {\em jurisdictional
+of adversary.  Specifically, our {\em location
 independence} metric reflects the probability that the path to the
 entry point of a mix network and the path from the exit point will
 traverse the same AS.  We then consider the topologies and node
@@ -117,9 +117,9 @@
 that node selection algorithms that look only at IP prefixes, such as
 those used in
 Tarzan~\cite{freedman:ccs02} and MorphMix~\cite{morphmix:fc04}, are
-likely to be ineffective at achieving jurisdictional independence.
+likely to be ineffective at achieving location independence.
 
-Next, we measure the jurisdictional independence of paths inside
+Next, we measure the location independence of paths inside
 the mix network. We find that for short paths, given existing mix
 network topologies, the Mixmaster and Tor node selection algorithms
 will frequently create paths that can be observed by a single AS.
@@ -188,9 +188,9 @@
 Section~\ref{sec:threat-model} and their path selection algorithms in
 Section~\ref{sec:path-selection}.
 
-Previous work has recognized the importance of jurisdictional
+Previous work has recognized the importance of location
 independence.  Tim May and Eric Hughes wrote about the idea of
-jurisdictional independence in early posts to the cypherpunks list.
+location 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
@@ -211,7 +211,7 @@
 topologies and our assumptions regarding how well this data reflects the
 paths that packets actually travel.
 
-\subsubsection{Border Gateway Protocol.}
+\subsubsection{Border Gateway Protocol}\label{sec:bgp}
 The Internet is composed of about 17,000 independently operated networks,
 or autonomous systems (ASes), that exchange reachability information via
 the Border Gateway Protocol (BGP)~\cite{rfc1771}.  An AS could be an
@@ -219,7 +219,8 @@
 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 most specific 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
@@ -299,16 +300,27 @@
 route to the destination, and the AS path (``Path'').  The ``$>$'' at
 the beginning of the first line indicates that the router has selected
 this route as the best route to the destination, based on applying the
-BGP decision process.  Each router can only have a single best route to
-a destination at any time.  By looking at this routing table, we can be
-reasonably certain that a packet that is destined for the destination IP
-address {\tt 18.31.0.38} will traverse the networks corresponding to AS
-numbers 6347 (Savvis), 3356 (Level 3), and 3 (MIT).\footnote{Recent work
-has observed that the AS path in the routing table may not always match
-the sequence of networks that a packet is forwarded through, but
-typically the differences are minor and occur infrequently~\cite{Mao2003}.}
+BGP decision process.  
 
-\subsubsection{AS-level Internet Topology.}
+Each router can only have a single best route to a destination at
+any time.  This routing table entry allows us to be reasonably
+certain that a packet that is destined for the destination IP address
+{\tt 18.31.0.38} will traverse the networks corresponding to AS numbers
+6347 (Savvis), 3356 (Level 3), and 3 (MIT).  Packets tend to follow this
+sequence of ASes since, at the AS level, traffic flows in the opposite
+direction in which routers advertise the routes.
+\footnote{There are some rare exceptions to this rule.
+For example,
+discrepancies can result if a router that advertises a BGP route via one
+AS ``deflects'' data packets to a router within that AS that has
+selected a different next-hop AS\cite{Griffin2002} (note that this is a
+routing protocol {\em misconfiguration}).
+Additionally, recent work has
+observed that the AS path in the routing table may not always match the
+sequence of networks that a packet is forwarded through, but typically
+the differences are minor and occur infrequently~\cite{Mao2003}.  } 
+
+\subsubsection{AS-level Internet Topology}
 Paths between end-hosts in the Internet cross a sequence of ASes (or
 jurisdictions); to estimate the sequence of ASes that any given path
 crosses, we must first have a representation of the Internet topology at
@@ -385,9 +397,10 @@
 (particularly during periods of low traffic) can be combined with active
 attacks such as message flooding to shrink the set of messages that mix
 with Alice's
-message~\cite{disad-free-routes,minion-design}. As a simple example,
-an adversary who learns the first half of Alice's path learns where to
-make his next phone call to track Alice's recipient.
+message~\cite{disad-free-routes,minion-design}. 
+%As a simple example,
+%an adversary who learns the first half of Alice's path learns where to
+%make his next phone call to track Alice's recipient.
 
 \section{Modeling Techniques}
 
@@ -432,35 +445,56 @@
 could look at $i$'s routing table and determine the AS path associated
 with the route that is the longest prefix match for $i+1$'s IP address.
 
-Unfortunately, Alice cannot generally ask for routing tables for
-each of the mix nodes when constructing a mix tunnel.  First,
-her act of requesting a routing table from a particular network might
-attract the attention of an eavesdropper, particularly if she asks for a
-large number of routing tables. Second, asking each network that contains
-a mix node for its current routing table is likely to be quite slow,
-since each full routing table is approximately 10 megabytes; additionally,
-as routes
-are continually changing, parts of the table are likely to be
-out-of-date even before she requests it.  Third, this method
-introduces another vulnerability to attack: if an adversary compromises
-any of the domains that contain a mix node, he could send back an
-inaccurate version of the routing table.  Because of these shortcomings,
-Alice must be able to {\em passively} determine the AS-level
-path (or a reasonable approximation of it) without having visibility
-into the routing tables of each hop in her intended mix path.
+Unfortunately, Alice cannot ask for routing tables for
+each of the mix nodes when constructing a mix tunnel.  
+First, her act of requesting a routing table from a particular network
+might attract the attention of an eavesdropper, particularly if she asks
+for a large number of routing tables. Second, asking each network that
+contains a mix node for its current routing table is likely to be quite
+slow, since each full routing table is approximately 10 megabytes;
+additionally, as routes are continually changing, parts of the table are
+likely to be out-of-date even before she requests it.  Third, this
+method introduces another vulnerability to attack: if an adversary
+compromises any of the domains that contain a mix node, he could send
+back an inaccurate version of the routing table. 
 
-Fortunately, examining the AS paths in a BGP routing table gives a
-reasonable estimation of %the Internet's AS-level topology (i.e.,
-what ASes connect to what other ASes and can provide reasonable
+Although active measurement tools such as ``traceroute'' are generally
+useful for discovering AS-level paths, the {\em active measurement}
+activity required to these paths is not acceptable; further, performing
+these measurements would not be robust against single compromised nodes.
+For example, the mix network operator could execute traceroutes between
+each pair of mix nodes to determine the IP-level paths (and, hence, the
+AS-level paths) between them.  Although this technique could be
+effective for determining the AS-level paths within the mix network,
+Alice must {\em also} know the AS-level path between herself and the mix
+entry she selects, as well as the AS-level path between the mix exit she
+selects and the destination where she is sending packets.  To discover
+the AS-level path between herself and a good candidate mix node, Alice
+must run traceroutes to nodes in the mix network, which may engender
+suspicion.  Further, she will not be able to actively determine the
+AS-level path from her chosen exit node and her destination: routing
+tables at that node may be unavailable or difficult to obtain covertly,
+and a traceroute from candidate exit node to the destination is also
+likely to engender suspicion (this approach will not work anyway if the
+node has been compromised).
+
+Because of these shortcomings, Alice must be able to {\em passively}
+determine the AS-level path (or a reasonable approximation of it)
+without having visibility into the routing tables of each hop in her
+intended mix path.  Fortunately, examining the AS paths in a BGP routing
+table gives a reasonable estimation of %the Internet's AS-level topology
+(i.e., what ASes connect to what other ASes and can provide reasonable
 information about what path an arbitrary Internet host might take to
 reach any given destination.
 %Mao {\em et al.} have recently developed
 %similar techniques for passively determining AS-level paths between two
 %Internet hosts~\cite{Mao2004}, given a view of the AS-level topology.
-We now summarize our technique, which is similar in spirit to the
-technique recently proposed by Mao {\em et al.}  Their work suggests
-that this type of technique is accurate for more than 80\% of
-paths~\cite{Mao2004}. 
+
+We now summarize AS-level path estimation technique, which is based on
+the technique recently proposed by Mao {\em et al.}\cite{Mao2004}
+Although it is admittedly impossible to determine an AS's routing policy
+with absolute certainty, Mao's work suggests that inferring AS-level
+paths based on common policies is accurate for more than 80\% of paths.
 
 
 \begin{enumerate}
@@ -486,7 +520,7 @@
 
 \item {\em Determine the origin and destination ASes for the path in
   question.}  To determine the AS-level path between two hosts, we must
-  obviously determine the ASes where the hosts are located.  This is
+  first 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
@@ -496,7 +530,7 @@
 
 \vspace{0.1in} Because 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.
+  applied to the most specific prefix in the routing table.
 
 \item {\em Determine the relationships between each pair of ASes.}  This
   is a notoriously difficult problem, because ASes typically guard the
@@ -521,6 +555,17 @@
 \item {\em Estimate the AS-level path between the two ASes by finding
   the shortest AS path that complies with common policy practices.}  
 
+\vspace{0.1in}
+  Because BGP routers select a single best route to each destination,
+  {\em each pair of hosts will typically traverse a single, unique AS
+  path in each direction}. (See Section~\ref{sec:bgp} for a discussion
+  of exceptions.)  This step assumes that ASes implement policy
+  that prefers the shortest AS path that is consistent with the best
+  common practice of preferring customer routes over peering routes and
+  peering routes over provider routes.  Mao {\em et al.}'s algorithm
+  suggest that this assumption is reasonable.
+
+\vspace{0.1in}
   As AS-level path estimation techniques improve,
   the accuracy of our analysis will also improve. %  More importantly,
   Thus, Alice can expect to be able to make informed decisions about the
@@ -633,9 +678,9 @@
 %% Tor nodes, current Mixminion nodes, current Mixmaster nodes, and we
 %% can compare robustness of the network to zone-based attacks. 
 
-\subsection{Jurisdictional Independence of Mix Nodes and Paths}
+\subsection{Location Independence of Mix Nodes and Paths}
 
-In this section, we explore and quantify the jurisdictional independence
+In this section, we explore and quantify the location independence
 of the Mixmaster and Tor topologies. We examine cases where Tor
 and Mixmaster nodes are located in the same AS.  We also examine the
 AS-level path properties between pairs of existing mix nodes and
@@ -649,7 +694,7 @@
 three mix nodes in AS 23504 (Speakeasy DSL), and Mixmaster has two nodes
 each in ASes 3269 (Telecom Italia), 6939 (Hurricane Electric), 7132
 (SBC), 23504 (Speakeasy DSL), and 24940 (Hetzner Online).  This lack of
-jurisdictional independence in node placement is not surprising; in
+location independence in node placement is not surprising; in
 particular, it reflects the fact that these network nodes are
 operated by {\em volunteers}, many of whom commonly operate mix nodes
 from their Internet connections at home (i.e., DSL providers, etc.).
@@ -670,18 +715,18 @@
 reduce the likelihood that two mix nodes are in the jurisdiction of a
 single AS~\cite{freedman:ccs02,morphmix:fc04}.  Unfortunately, this
 technique does not
-necessarily increase the likelihood of jurisdictional independence: of
+necessarily increase the likelihood of location independence: of
 the five pairs of Mixmaster nodes that are located in the same AS, three of
 these pairs (those in ASes 3269, 7132, and 23504) not only have distinct
 {\tt /16} prefixes, they also have distinct {\tt /8} prefixes.
 Similarly, one of the Tor network nodes in AS 23504 has a distinct {\tt
-/16} prefix.  Thus, to achieve jurisdictional
+/16} prefix.  Thus, to achieve location
 independence, a mix network must explicitly consider the actual AS of
 a host, not simply its IP address.
 
 Finally, we note that all of the Tor network's exit nodes are currently
 located in the United States.  In practice, this network could achieve
-greater jurisdictional independence by increasing exit node
+greater location independence by increasing exit node
 participation outside of the US.  
 
 
@@ -707,7 +752,7 @@
 \end{tabular}
 \end{center}
 \end{scriptsize} 
-\caption{Characterizing jurisdictional independence in Mixmaster and Tor.}
+\caption{Characterizing location independence in Mixmaster and Tor.}
 \label{tab:path_ind}
 \end{table}
 
@@ -720,12 +765,12 @@
 %% Mixmaster\\
 %% \end{tabular}
 %% \vspace{0.1in}
-%% \caption{Characterizing jurisdictional independence in today's mix
+%% \caption{Characterizing location independence in today's mix
 %%   networks.}
 %% \label{tab:path_ind}
 %% \end{table}
 
-Table~\ref{tab:path_ind} shows the extent of jurisdictional independence
+Table~\ref{tab:path_ind} shows the extent of location independence
 in Mixmaster and Tor.  Tor has 14 nodes that are located in 12 distinct
 ASes, for a total of 144 AS-disjoint mix node pairs; similarly,
 Mixmaster has 49 nodes located in 42 distinct ASes, or 1764 AS-disjoint
@@ -842,7 +887,7 @@
 hop being used twice along a single mix path, if this is not explicitly
 prevented.  
 
-\subsection{Jurisdictional Independence of Entry and Exit Paths}
+\subsection{Location Independence of Entry and Exit Paths}
 
 
 \begin{table}[t]
@@ -865,7 +910,7 @@
 \end{tabular}
 \end{center}
 \end{scriptsize}
-\caption{Jurisdictional independence for typical sending and receiving
+\caption{Location independence for typical sending and receiving
   ASes for the {\bf Tor} network topology.  Each entry shows, for a
   sender/receiver pair, the probability that a single AS will
   observe both the path from the sender to the entry node and the path
@@ -893,7 +938,7 @@
 \end{tabular}
 \end{center}
 \end{scriptsize}
-\caption{Jurisdictional independence for typical sending and receiving
+\caption{Location independence for typical sending and receiving
   ASes through the {\bf Mixmaster} anonymity network topology.  
 %Each table
 %  entry shows, for a sending and receiving AS pair, the probability that
@@ -905,7 +950,7 @@
 \end{table}
 
 
-To discover the jurisdictional independence of the entry and exit paths
+To discover the location independence of the entry and exit paths
 for typical mix networks, we used the lists of common sender and receiver
 locations from Appendix~\ref{sec:send_recv} and modeled typical paths
 from the sender to receiver through both the Mixmaster and Tor
@@ -938,7 +983,7 @@
 with absolute certainty, because AOL Time Warner owns Turner
 Broadcasting (AS 5662), which includes CNN.
 
-Interestingly, these tables also show that jurisdictional independence
+Interestingly, these tables also show that location independence
 is high when either the sender, the receiver, or both are located in a
 tier-1 ISP (e.g., AS 4999, which is part of Sprint).  This might
 be because the path from the sender to the entry point is already
@@ -960,7 +1005,7 @@
 Our results suggest that designers and users of mix networks should
 take into account the underlying AS-level paths of each link in the mix
 network.  Mix network paths can be made more safe if senders increase
-the jurisdictional independence of the paths they use, by explicitly
+the location independence of the paths they use, by explicitly
 choosing entry and exit nodes to avoid traversing the same AS upon entry
 and exit to the mix network.
 
@@ -974,7 +1019,7 @@
 of our suggested algorithm on all levels of adversary; we leave this
 investigation to future work.
 
-\subsection{Improving Jurisdictional Independence with Node Placement}
+\subsection{Improving Location Independence with Node Placement}
 
 %Our analysis of inter-mix network paths suggests that currently deployed
 %mix networks could benefit from increased diversity in node placement,
@@ -987,14 +1032,14 @@
 inbound and outbound paths to those nodes.  Far-flung node locations
 that provide geographical diversity, such as nodes in Asia,
 are likely to actually
-{\em reduce} jurisdictional independence, because such nodes do not
+{\em reduce} location independence, because such nodes do not
 typically have diverse AS-level connectivity.  Rather, the best place
 for new nodes is likely to be in ASes that have {\em
 high degree}---that is, those that connect to a large number of other
 ASes.  Ironically, the ASes with the highest degree tend to be tier-1
 ISPs themselves; thus placing one node in each tier-1 ISP and
 building mix paths between those nodes may be the best strategy for
-increasing jurisdictional independence.  Exploring this question is an
+increasing location independence.  Exploring this question is an
 excellent direction for future work.
 
 \subsection{Other issues}
@@ -1042,7 +1087,7 @@
 
 \section{Conclusion}
 
-We propose that mix networks aiming to achieve jurisdictional diversity
+We propose that mix networks aiming to achieve location diversity
 should consider the underlying AS-level paths. %  Our paper
 %brings to light several interesting and important results:
 In particular, our results include:
@@ -1051,7 +1096,7 @@
 \item While previous systems have proposed
   selecting nodes from disjoint IP address prefixes to select nodes in
   different jurisdictions, we have shown that this technique is not
-  sufficient to achieve jurisdictional independence.
+  sufficient to achieve location independence.
 
 \item We analyzed the AS-level path properties of existing mix networks
   and found that certain tier-1 ISPs are prevalent on many mix network
@@ -1073,7 +1118,7 @@
   exit nodes, a single AS will be able to observe both the
   entry and exit path to the mix network between 10\% and 30\% of the time.
   However, if the initiator chooses entry and exit nodes with
-  jurisdictional independence in mind, she can prevent most such attacks.
+  location independence in mind, she can prevent most such attacks.
 \end{tightlist}
 
 %This work brings to light an important insight that should guide the

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