[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] editing pass
Update of /home/freehaven/cvsroot/doc/routing-zones
In directory moria.mit.edu:/tmp/cvs-serv21588
Modified Files:
routing-zones.bib routing-zones.ps routing-zones.tex
sig-alt-full.cls
Log Message:
editing pass
Index: routing-zones.bib
===================================================================
RCS file: /home/freehaven/cvsroot/doc/routing-zones/routing-zones.bib,v
retrieving revision 1.21
retrieving revision 1.22
diff -u -d -r1.21 -r1.22
--- routing-zones.bib 25 Aug 2004 11:37:57 -0000 1.21
+++ routing-zones.bib 1 Sep 2004 07:06:37 -0000 1.22
@@ -272,7 +272,7 @@
@InProceedings{Mao2003,
author = {Zhuoqing Morley Mao and Jennifer Rexford and Jia Wang and Randy Katz},
- title = {Towards an Accurate AS-level Traceroute Tool},
+ title = {Towards an Accurate {AS}-level Traceroute Tool},
booktitle = {Proc. ACM SIGCOMM},
year = {2003},
address = {Karlsruhe, Germany},
@@ -309,7 +309,7 @@
@Article{Chang2004,
author = {H. Chang and R. Govindan and S. Jamin and S. Shenker and W. Willinger},
- title = {Towards Capturing Representative AS-Level Internet Topologies},
+ title = {Towards Capturing Representative {AS}-Level Internet Topologies},
journal = {Computer Networks Journal},
year = {2004},
}
Index: routing-zones.ps
===================================================================
RCS file: /home/freehaven/cvsroot/doc/routing-zones/routing-zones.ps,v
retrieving revision 1.5
retrieving revision 1.6
diff -u -d -r1.5 -r1.6
--- routing-zones.ps 27 Aug 2004 19:42:42 -0000 1.5
+++ routing-zones.ps 1 Sep 2004 07:06:37 -0000 1.6
@@ -10,7 +10,7 @@
%DVIPSWebPage: (www.radicaleye.com)
%DVIPSCommandLine: dvips -t letter routing-zones.dvi -o routing-zones.ps
%DVIPSParameters: dpi=600, compressed
-%DVIPSSource: TeX output 2004.08.27:1538
+%DVIPSSource: TeX output 2004.09.01:0305
%%BeginProcSet: texc.pro
%!
/TeXDict 300 dict def TeXDict begin/N{def}def/B{bind def}N/S{exch}N/X{S
@@ -1091,107 +1091,106 @@
32 29 36 1[36 42 39 48 2[26 19 42 42 36 36 42 39 36 36
6[19 29 29 1[29 1[29 29 29 29 29 16 15 19 15 2[19 19
[...3621 lines suppressed...]
1169 718 V 248 w(205.158.23.142)p 1651 718 V 118 w(US)p
1932 718 V 206 w(2828)h(\(XO)g(Communications\))p 3124
-718 V 753 785 V 800 765 a Fc(peertech)p 1169 785 V 203
+718 V 753 785 V 800 765 a Fd(peertech)p 1169 785 V 203
w(207.36.86.132)p 1651 785 V 147 w(US)p 1932 785 V 206
w(3064)g(\(CyberGate)g(Inter)o(net)g(T)-5 b(echnologies,)14
b(Inc\))p 3124 785 V 753 851 V 800 831 a(dizum)p 1169
@@ -5419,10 +5428,10 @@
3124 918 V 753 984 V 800 964 a(itys)p 1169 984 V 329
w(209.221.142.117)p 1651 984 V 89 w(US)p 1932 984 V 206
w(3742)g(\(Semaphor)o(e)h(Cor)o(poration\))p 3124 984
-V 753 1050 V 800 1031 a Fb(tor26)p 1169 1050 V 294 w(62.116.124.106)p
+V 753 1050 V 800 1031 a Fc(tor26)p 1169 1050 V 294 w(62.116.124.106)p
1651 1050 V 118 w(A)-6 b(T)p 1932 1050 V 208 w(5424)15
b(\(A)-6 b(Tnet\))p 3124 1050 V 753 1117 V 800 1097 a
-Fc(r)o(ootdo)o(wn)p 1169 1117 V 180 w(166.70.93.2)p 1651
+Fd(r)o(ootdo)o(wn)p 1169 1117 V 180 w(166.70.93.2)p 1651
1117 V 205 w(US)p 1932 1117 V 206 w(6315)15 b(\(XMission\))p
3124 1117 V 753 1183 V 800 1163 a(c3po)p 1169 1183 V
300 w(128.187.170.212)p 1651 1183 V 89 w(US)p 1932 1183
Index: routing-zones.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/routing-zones/routing-zones.tex,v
retrieving revision 1.81
retrieving revision 1.82
diff -u -d -r1.81 -r1.82
--- routing-zones.tex 27 Aug 2004 19:42:43 -0000 1.81
+++ routing-zones.tex 1 Sep 2004 07:06:37 -0000 1.82
@@ -114,7 +114,7 @@
the overlay
topology so messages can enter or exit at more places in the network
(compared to a cascade topology~\cite{disad-free-routes});
-and by \emph{location diversity} --- coordinating network behavior
+and by \emph{location diversity}---coordinating network behavior
so each transaction is spread over multiple jurisdictions.
In this paper, we investigate a variant of location diversity that
@@ -132,7 +132,8 @@
This paper presents several interesting results.
First, we find that both Tor and Mixmaster have multiple nodes in
-the same autonomous system. Users of these networks should take care to
+the same autonomous system from different IP address spaces. 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 that look only at IP prefixes, such as
those used in
@@ -160,12 +161,10 @@
\section{Background}
-%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.
+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. Then, we provide some background on
+Internet routing and topology.
\subsection{Anonymity networks}
\label{subsec:background-anonymity}
@@ -178,10 +177,10 @@
Subsequent anonymity systems have diverged in two directions. Systems
like Babel~\cite{babel}, Mixmaster, and
-Mixminion~\cite{minion-design} aim to defend against powerful adversaries,
-but at
+Mixminion~\cite{minion-design} defend against powerful adversaries
+at
the cost of requiring high and variable latency. Other systems, such as
-Onion Routing, its successor Tor, and the
+Onion Routing~\cite{or-jsac98}, its successor Tor~\cite{tor-design}, and the
Freedom network~\cite{freedom2-arch}, support
low-latency transactions such as web browsing, but necessarily have a
weaker threat model. Onion Routing and Freedom differ from single-hop
@@ -189,16 +188,16 @@
like Web Mixes~\cite{web-mix} in that they aim to achieve as much
diversity in node placement and path selection as possible.
-Anonymity networks aim to protect against a wide variety of both passive
+Anonymity networks try to protect against a wide variety of both passive
and active attacks~\cite{back01,raymond00}. Such attacks generally
fall into two categories: attacks inside the network and endpoint
-attacks. Attacks inside the network aim to partition anonymity sets
+attacks. Attacks inside the network partition anonymity sets
through passive observation~\cite{disad-free-routes,minion-design}
or active traffic manipulation~\cite{trickle02}, or otherwise narrow
the set of suspects for a given transaction. Endpoint attacks treat the
network as a black box and consider only the entry node and exit node
for the transaction; such attacks include simple timing and counting
-attacks against low-latency systems~\cite{defensive-dropping,SS03},
+attacks against low-latency systems~\cite{defensive-dropping,SS03}
and long-term intersection or disclosure attacks against high-latency
systems \cite{disad-free-routes,statistical-disclosure,e2e-traffic}.
@@ -211,10 +210,10 @@
Previous work has recognized the importance of location
independence. Tim May and Eric Hughes wrote about the idea of
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
+Mixmaster operators attempt to track which ISPs can control each node
+to gain 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
+and MorphMix, attempt to provide collusion resistance by comparing the IP of
each peer~\cite{freedman:ccs02,morphmix:fc04} (our results show that this
technique is less effective than claimed). In this paper, we evaluate the
topologies of {\em real anonymity networks} in the context of the
@@ -241,7 +240,7 @@
find the route to a destination IP address, a router performs
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
+in the routing table that contains that IP address. For example,
to look up {\em IP address} {\tt 18.31.0.82}, a router
might use a route for the {\em prefix} {\tt 18.0.0.0/8}. % a prefix that
%contains the destination IP address.
@@ -267,8 +266,8 @@
each pair of ASes has a commercial relationship, and an AS may prefer to
send traffic via one AS over another for economic reasons. ASes form
bilateral arrangements that can be broadly categorized as either (1)~a
-customer-provider relationship, where the customer pays the provider to
-route traffic for it; or (2)~a peering relationship, where two ASes
+{\em customer-provider} relationship, where the customer pays the provider to
+route traffic for it; or (2)~a {\em peering} relationship, where two ASes
exchange traffic between their own networks (and the networks of their
customers), but neither pays the other for this privilege.
@@ -289,7 +288,7 @@
%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---an AS will typically not
+will advertise to another---an AS will not typically
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 between
@@ -328,8 +327,8 @@
{\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.
+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
@@ -350,36 +349,36 @@
policies hide edges in the graph from some
perspectives~\cite{Chang2004}. For example, in
Figure~\ref{fig:policy_summary}, a routing table captured at Peer 1 will
-not contain any routes with the $AS \leftrightarrow \mbox{Peer} 2$ link,
+not contain any routes with the $AS \leftrightarrow \mbox{Peer}~2$ link,
since the AS in the center will not readvertise routes learned from one
peer to another.
-There are many publicly-available places that provide access to routing
+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 50 ASes. Each of these ASes sends its routing tables to
the RouteViews server, which learns that AS's best route to each
destination prefix. Each AS's routing table is slightly different,
which means that the AS-level topology constructed from the RouteViews
-route server is probably missing some inter-AS edges due to bilateral
+route server is missing some inter-AS edges due to bilateral
policies, but the graph is representative enough for our
purposes. In the future, we could improve our analysis by incorporating
newer techniques for capturing AS-level topologies~\cite{Chang2004}.
Knowing the AS-level topology is not enough to determine the AS-level
path between two arbitrary mix nodes, though; to determine this,
-we need to make further modeling assumptions, which we describe in
-Section~\ref{sec:mix_aspath}.
+we need to make some assumptions about the AS-level paths that packets
+actually traverse, which we describe in Section~\ref{sec:mix_aspath}.
\section{Threat Models}
\label{sec:threat-model}
Alice wants to communicate with Bob without revealing her location. We
-aim to improve Alice's anonymity against an adversary who can monitor a
+intend to improve Alice's anonymity against an adversary who can monitor a
single AS (for example, a curious ISP or a corrupt law enforcement officer
abusing his subpoena powers). We assume that the ability to observe
multiple ASes is significantly more difficult than observing a single
-AS, either because few
-ISPs control multiple ASes, or because law enforcement will
+AS, because most
+ISPs do not control multiple ASes, and because law enforcement will
be less willing to face the increased accountability and risk associated
with obtaining multiple unapproved subpoenas.
%By requiring the adversary to control multiple ASes, we raise the
@@ -392,9 +391,9 @@
Endpoint attacks on low-latency networks are the most straightforward:
an adversary observing both Alice and Bob can quickly learn that they
-are communicating. Onion Routing analysis~\cite{onion-routing:pet2000}
+are communicating. Previous analysis of Onion Routing
has shown that an adversary observing $c$ of the $n$ nodes in the network
-can break $\frac{c^2}{n^2}$ of the transactions. By
+can break $(c/n)^2$ of the transactions~\cite{onion-routing:pet2000}. By
requiring the path from Alice to the anonymity network and the
path from the anonymity network to Bob to traverse separate
ASes, we can prevent all of these
@@ -412,8 +411,8 @@
Mixmaster takes a lot more time and effort than one against a low-latency
system like Tor. However, because an observer of even a few Mixmaster nodes
may be able to link Alice to her recipients over time~\cite{e2e-traffic},
-our work here is also relevant for protecting such high-latency systems
-from a one-AS adversary. Further, intra-network observations
+our work is also relevant for protecting such high-latency systems
+from a single-AS adversary. Further, intra-network observations
(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
@@ -427,17 +426,18 @@
We now describe how we model mix networks and Internet routing to draw
conclusions about an anonymity network's vulnerability to eavesdropping
by the adversary detailed in Section~\ref{sec:threat-model}. First we
-describe our model of node selection, and then we present our techniques
+describe our model of node selection in a mix network. Then, we present
+our techniques
for estimating the AS-level path between two arbitrary hosts on the
Internet.
\subsection{Node Selection in Mix Networks}
\label{sec:path-selection}
-To build a path in an anonymity network, clients must somehow discover a set
+To establish a path in an anonymity network, clients must somehow discover a set
of current 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
+and addresses for each node~\cite{echolot}. In Tor, clients download
a similar network snapshot from special nodes called directory
servers~\cite{tor-design}. The pingers and
directory servers note whether each node is an \emph{exit node}---meaning
@@ -458,26 +458,6 @@
\subsection{AS-level Mix Network Path Estimation}\label{sec:mix_aspath}
-If Alice had access to an up-to-date routing
-table from every network containing mix nodes, she could construct a
-reasonable estimate of the AS-level path fairly easily: to discover the
-AS-level path between nodes $i$ and $i+1$, for example, she
-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 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: an adversary who
-compromises any of the domains that contain a mix node could send
-back an inaccurate version of the routing table.
-
\emph{Active measurement} tools such as ``traceroute'' could also be
used to discover AS-level paths. For example, the mix network operator
could execute traceroutes between each pair of mix nodes to determine the
@@ -499,7 +479,28 @@
destination node to her chosen exit node (i.e., the path that traffic
from the destination to Alice will traverse): in this case,
Alice can only discover the AS-level path from the destination to her
-chosen exit node using passive inference techniques.
+chosen exit node using passive inference techniques, such as examining
+routing tables.
+
+If Alice had access to an up-to-date routing
+table from every network containing mix nodes, she could construct a
+reasonable estimate of the AS-level path fairly easily: to discover the
+AS-level path between nodes $i$ and $i+1$, for example, she
+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 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: an adversary who
+compromises any of the domains that contain a mix node could send
+back an inaccurate version of the routing table.
Because of these shortcomings, Alice must {\em passively}
determine the AS-level path (or a reasonable approximation of it)
@@ -524,7 +525,7 @@
\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
+ AS path attribute, which provides a list of AS adjacencies. For
example, from the routes in Figure~\ref{fig:bgp_example}, we know that
AS 3356 and AS 3 are directly connected. Given the complete list of
adjacencies from a BGP routing table, we can reasonably approximate
@@ -587,16 +588,16 @@
common practice of preferring customer routes over peering routes and
peering routes over provider routes. Mao {\em et al.}'s algorithm
suggests that this assumption is reasonable.
+\end{enumerate}
\vspace{0.05in}
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
mix nodes she 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
+Given both a model for how anonymizing networks select nodes and an
+estimation of the AS-level path between two arbitrary hosts on the
Internet, Alice can determine the complete set of ASes that a typical
mix network path traverses using only passive techniques.\footnote{We
performed our analysis in Section~\ref{sec:results} using this passive
@@ -617,15 +618,16 @@
\section{Data}
-Here we summarize the data that we use in our analysis of AS-level paths
+In this section, we summarize the data that we use in our analysis of
+AS-level paths
in mix networks. We base our analysis on the location of mix nodes in
deployed systems today. We then describe the data we used to generate
the AS-level network topology.
\subsection{Mix Networks, Senders, and Receivers}
-To evaluate node selection in the Mixmaster and Tor models, we use the
-list of operational mix nodes for each respective network; the tables in
+To evaluate node selection in the Mixmaster and Tor models, we use
+operational mix nodes for each respective network; the tables in
Appendix~\ref{sec:mixnode_summary} provide lists of mix nodes for the
two networks.
@@ -639,9 +641,9 @@
network (e.g., a cable modem network, a DSL network, etc.) and that Bob
is a content host located at a data hosting ISP.
-To generate a reasonable list of ASes where senders might be
+To generate a set of ASes where senders might be
located, we created a list of DSL and cable modem providers from {\tt
-www.dslreports.com} that would be likely senders and mapped these
+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 sampled sites from comScore Media Metrix's ``Top
50 US Internet Properties'' from December 2003~\cite{www-comscore}, as
@@ -649,16 +651,17 @@
lists of senders and receivers that we used in our experiments are in
Appendix~\ref{sec:send_recv}.
-Note that in this paper we use the topologies of existing mix networks
+In this paper, we use the topologies of existing mix networks
to get a plausible set of nodes for our model. The Tor nodes represent a
newborn network where the only participants are developers and very
early adopters, whereas the Mixmaster network represents a wider
participant set because it has been deployed for many years. We compare
how each of these node sets performs when the initiators are typical DSL
or cable modem users in the US, and the responders are popular websites
-in the US---in effect, we are evaluating the safety of the newborn Tor
-network and the safety of a node set that we hope reflects how the Tor
-network will look when it grows more mature.
+in the US---in effect, we are evaluating the location independence of
+the newborn Tor
+network and the independence of a node set that should resemble that of
+Tor network as Tor matures.
\subsection{Internet Topology}
@@ -677,14 +680,17 @@
%In this section, we present the results of our analysis.
First, we
-discuss the fundamental robustness properties of existing mix networks
-and how these properties would change in response to an increased number
-and diversity of mix nodes. This analysis is independent of our model
-for mix network users (i.e., senders and receivers), since we are only
-examining properties of the mix nodes themselves. (In addition to
-worrying about endpoints,
+discuss the fundamental robustness properties of existing mix networks.
+In addition to
+maximizing location independence at the entry and exit points of the mix
+network,
we should try to minimize the cases where one AS can observe
-multiple links along a mix network path.) Next, we compute the
+multiple links along a mix network path.
+%and how these properties would change in response to an increased number
+%and diversity of mix nodes.
+This analysis is independent of our model
+for mix network users (i.e., senders and receivers), since we are only
+examining properties of the mix nodes themselves. Next, we compute the
probability that the AS-level path from the sender to the entry node and
the path from the exit node to the receiver traverse the same AS (i.e.,
the probability that a single AS can observe both endpoints of a mix
@@ -710,6 +716,33 @@
\subsection{Independence of Mix Nodes and Paths}
+\begin{table*}[t]
+\begin{scriptsize}
+\begin{center}
+\begin{tabular}{r|l|p{0in}r|l} \\
+& {\bf Tor} & & & {\bf Mixmaster} \\ \hline
+\# of AS-disjoint mix node pairs & 961 & & & 1764 \\ \hline\hline
+\multicolumn{5}{c}{{\bf\# of mix node pairs with common AS}} \\
+AS 3356 (Level 3 Communications, LLC) & 276 (28.7\%) & & AS 3356 (Level 3 Communications, LLC) & 291 (16.5\%)\\
+AS 6461 (Abovenet Communications, Inc) & 249 (25.9\%) & & AS 6461 (Abovenet Communications, Inc) & 251 (14.2\%)\\
+AS 2914 (Verio, Inc) & 65 (6.8\%) & & AS 7018 (AT\&T WorldNet Services) & 234 (13.3\%)\\
+AS 16631 (Cogent Communications) & 64 (6.7\%) & & AS 3549 (Global Crossing) & 104 (5.9\%)\\
+AS 701 (UUNET Technologies, Inc) & 61 (6.3\%) & & AS 14188 (Ashland Fiber Network) & 82 (4.6\%)\\
+AS 23342 (United Layer, Inc) & 60 (6.2\%) & & AS 23342 (United Layer, Inc) & 82 (4.6\%)\\
+AS 19782 (Indiana University) & 60 (6.2\%) & & AS 1668 (AOL Transit Data Network) & 82 (4.6\%)\\
+AS 2152 (California State University) & 60 (6.2\%) & & AS 15290 (Allstream Corp. Corporation Allstream) & 49 (2.8\%)\\
+AS 10578 (Harvard University) & 53 (5.5\%) & & AS 2914 (Verio, Inc) & 46 (2.6\%)\\
+AS 3491 (CAIS Internet) & 52 (5.4\%) & & AS 6993 (Internap Network Services) & 42 (2.4\%)\\
+%%\hline
+\end{tabular}
+\end{center}
+\end{scriptsize}
+\caption{Characterizing location independence in Mixmaster and Tor.}
+\label{tab:path_ind}
+\end{table*}
+
+
+
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
@@ -729,8 +762,8 @@
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.).
-However, the fact that both of these networks have multiple duplicated
+from their Internet connections at home (e.g., DSL providers, etc.).
+Nevertheless, the fact that both of these networks have multiple duplicate
ASes suggests that users of these mix
networks should exercise caution when selecting mix nodes (particularly
the entry and exit nodes).
@@ -739,7 +772,7 @@
nodes from disjoint subsets of the IP address space will achieve
independence in node placement; it is clear from our survey of Mixmaster
and Tor that these types of prefix-based mechanisms are, in general,
-ineffective, and they can lead the user into a false
+ineffective, and they can give the user a false
sense of security. For example, Tarzan and MorphMix suggest subdividing
the node
space into {\tt /16} prefixes, and subsequently into {\tt /24} prefixes
@@ -762,33 +795,37 @@
participation outside of the US.
\subsubsection{Path properties}
-\begin{table*}[t]
-\begin{scriptsize}
-\begin{center}
-\begin{tabular}{r|l|p{0in}r|l} \\
-& {\bf Tor} & & & {\bf Mixmaster} \\ \hline
-\# of AS-disjoint mix node pairs & 961 & & & 1764 \\ \hline\hline
-\multicolumn{5}{c}{{\bf\# of mix node pairs with common AS}} \\
-AS 3356 (Level 3 Communications, LLC) & 276 (28.7\%) & & AS 3356 (Level 3 Communications, LLC) & 291 (16.5\%)\\
-AS 6461 (Abovenet Communications, Inc) & 249 (25.9\%) & & AS 6461 (Abovenet Communications, Inc) & 251 (14.2\%)\\
-AS 2914 (Verio, Inc) & 65 (6.8\%) & & AS 7018 (AT\&T WorldNet Services) & 234 (13.3\%)\\
-AS 16631 (Cogent Communications) & 64 (6.7\%) & & AS 3549 (Global Crossing) & 104 (5.9\%)\\
-AS 701 (UUNET Technologies, Inc) & 61 (6.3\%) & & AS 14188 (Ashland Fiber Network) & 82 (4.6\%)\\
-AS 23342 (United Layer, Inc) & 60 (6.2\%) & & AS 23342 (United Layer, Inc) & 82 (4.6\%)\\
-AS 19782 (Indiana University) & 60 (6.2\%) & & AS 1668 (AOL Transit Data Network) & 82 (4.6\%)\\
-AS 2152 (California State University) & 60 (6.2\%) & & AS 15290 (Allstream Corp. Corporation Allstream) & 49 (2.8\%)\\
-AS 10578 (Harvard University) & 53 (5.5\%) & & AS 2914 (Verio, Inc) & 46 (2.6\%)\\
-AS 3491 (CAIS Internet) & 52 (5.4\%) & & AS 6993 (Internap Network Services) & 42 (2.4\%)\\
-%%\hline
-\end{tabular}
-\end{center}
-\end{scriptsize}
-\caption{Characterizing location independence in Mixmaster and Tor.}
-\label{tab:path_ind}
-\end{table*}
-\begin{figure}[t]
+%% \begin{table}[t]
+%% \begin{tabular}{r|p{1.25in}|p{0.5in}p{0.5in}p{0.5in}p{0.5in}}
+%% {\bf Mix Network} & \parbox{1.25in}{{\centering\bf \# of \\ AS-disjoint Edges}} &
+%% \multicolumn{4}{c}{{\bf \# of Edges with $n$ common ASes}} \\
+%% & & \parbox{0.5in}{\centering 1} & \parbox{0.5in}{\centering 2} & \parbox{0.5in}{\centering 3} & \parbox{0.5in}{\centering 4+} \\ \hline
+%% Tor \\
+%% Mixmaster\\
+%% \end{tabular}
+%% \vspace{0.1in}
+%% \caption{Characterizing location independence in today's mix
+%% networks.}
+%% \label{tab:path_ind}
+%% \end{table}
+
+Table~\ref{tab:path_ind} shows the extent of location independence
+in Mixmaster and Tor. Tor has 35 nodes that are located in 31 distinct
+ASes, for a total of 961 AS-disjoint mix node pairs; similarly,
+Mixmaster has 49 nodes located in 42 distinct ASes, or 1764 AS-disjoint
+node pairs. The most striking statistic is that AS 3356 appears on 276,
+(nearly 30\%) of Tor's AS-disjoint paths; AS 3356 also appears on about
+17\% of Mixmaster's AS-disjoint paths between node pairs. The reason
+for this prevalence
+can be explained by two factors: (1)~the location of nodes in the mix
+network, and (2)~fundamental properties of the AS-level topology (i.e.,
+many paths ultimately traverse some tier-1 ISP; those in the mix
+topologies we examined seem particularly likely to traverse AS~3356).
+
+
+\begin{figure*}[t]
\begin{minipage}[ht]{6.75cm}
\mbox{\epsfig{figure=as_observe_all_fwd_log.eps,width=7.75cm}}
\caption{Fraction of paths where a single AS can observe all
@@ -796,7 +833,7 @@
\label{fig:as_observe}
\end{minipage}
\hfill
-\begin{minipage}[ht]{6.75cm}
+\begin{minipage}[ht]{7.5cm}
\mbox{\epsfig{figure=as_observe_75_fwd_log.eps,width=7.75cm}}
\caption{Fraction of paths where a single AS can observe all but one
of the links in the mix network path.%\protect\footnotemark
@@ -804,9 +841,9 @@
\label{fig:as_observe_75}
\end{minipage}
\hfill
-\end{figure}
+\end{figure*}
-\begin{figure}[h!]
+\begin{figure*}[t]
\begin{minipage}[ht]{6.75cm}
\mbox{\epsfig{figure=as_observe_all_rev_log.eps,width=7.75cm}}
\caption{Fraction of paths where a single AS can observe all
@@ -814,7 +851,7 @@
\label{fig:as_observe_rev}
\end{minipage}
\hfill
-\begin{minipage}[ht]{6.75cm}
+\begin{minipage}[ht]{7.5cm}
\mbox{\epsfig{figure=as_observe_75_rev_log.eps,width=7.75cm}}
\caption{Fraction of paths where a single AS can observe all but one
of the links in the {\em reverse} mix network path. ({\em Note:}
@@ -823,35 +860,11 @@
\label{fig:as_observe_75_rev}
\end{minipage}
\hfill
-\end{figure}
-
-
-%% \begin{table}[t]
-%% \begin{tabular}{r|p{1.25in}|p{0.5in}p{0.5in}p{0.5in}p{0.5in}}
-%% {\bf Mix Network} & \parbox{1.25in}{{\centering\bf \# of \\ AS-disjoint Edges}} &
-%% \multicolumn{4}{c}{{\bf \# of Edges with $n$ common ASes}} \\
-%% & & \parbox{0.5in}{\centering 1} & \parbox{0.5in}{\centering 2} & \parbox{0.5in}{\centering 3} & \parbox{0.5in}{\centering 4+} \\ \hline
-%% Tor \\
-%% Mixmaster\\
-%% \end{tabular}
-%% \vspace{0.1in}
-%% \caption{Characterizing location independence in today's mix
-%% networks.}
-%% \label{tab:path_ind}
-%% \end{table}
+\end{figure*}
-Table~\ref{tab:path_ind} shows the extent of location independence
-in Mixmaster and Tor. Tor has 35 nodes that are located in 31 distinct
-ASes, for a total of 961 AS-disjoint mix node pairs; similarly,
-Mixmaster has 49 nodes located in 42 distinct ASes, or 1764 AS-disjoint
-node pairs. The most striking statistic is that AS 3356 appears on 276,
-or nearly 30\% of Tor's AS-disjoint paths; AS 3356 also appears on about
-17\% of Mixmaster's AS-disjoint paths. The reason for this prevalence
-can be explained by two factors: (1)~the location of nodes in the mix
-network, and (2)~fundamental properties of the AS-level topology.
First, many of both Tor's and Mixmaster's nodes are located in {\em
-edge} networks; this means that, for some nodes, the path both two and
+edge} networks; this means that, for some nodes, the path both to and
from that node will cross the same AS much of the time. This
phenomenon is especially true for nodes that are located on edge
networks with a single preferred upstream ISP; for example, the nodes at
@@ -866,12 +879,17 @@
tier-1 ISPs (e.g., UUNet, Qwest, Global Crossing, AT\&T, AOL, Verio, and
Abovenet).
+
The prevalence of certain ISPs between mix node pairs suggests that as
the length of a mix network path increases, the likelihood that an AS
-will be able to observe the path at more than one location
-increases. To test this hypothesis, we generated random mix paths through
+will be able to observe the path at more than one location also
+increases. Still, the likelihood that an AS should be able to observe
+a significant fraction of the links on a mix network path should decrease as
+the length of the path increases. To test this hypothesis, we generated
+random mix paths through
the mix network. Using both the \emph{remailer} and \emph{onion routing}
-node selection algorithms, and varying lengths from
+node selection algorithms (as described in
+Section~\ref{sec:path-selection}), and varying lengths from
two hops to eight hops, we measured the probability that
a path crosses the same AS on multiple links. For each length and
type of path, we ran 10,000 trials. % and counted the number of times the
@@ -914,7 +932,7 @@
without node replacement will be observed by a single AS on all links
with probability 0.10, whereas a four-hop path constructed with node
replacement will be observed with probability 0.16. This result makes
-sense: random node selection with replacement is much more likely to
+sense: random node selection with replacement is more likely to
result in the same hop being used twice along a single mix path, if this
is not explicitly prevented. Figures~\ref{fig:as_observe_rev}
and~\ref{fig:as_observe_75_rev} also seem to indicate that reverse paths
@@ -922,6 +940,7 @@
users) are slightly more vulnerable to observation on both entry and
exit than vice versa.
+
\subsection{Independence of Entry and Exit Paths}
@@ -1273,7 +1292,7 @@
\end{table*}
-To discover the location independence of the entry and exit paths
+To evaluate 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
@@ -1300,7 +1319,7 @@
AS on entry and exit (e.g., between Speakeasy and Google, only 7\% of
Tor entry/exit node pairs result in entry and exit paths that cross the
same AS on both entry and exit). However, a careless sender that does
-not pay attention to the AS-level topology may well be eavesdropped by a
+not pay attention to the AS-level topology may well be observed by a
single AS at both entry and exit. For example, if Alice uses AOL (AS
1668) as her ISP and attempts to connect to {\tt cnn.com} (AS 5662), a
single AS (i.e., AS 1668) will observe both the entry and exit paths
@@ -1312,7 +1331,8 @@
(AS~22909) to indymedia (AS~22489), 45\% of the entry/exit node pairs
result in paths that traverse the same AS on both entry and exit; from
indymedia to Comcast, on the other hand, random entry and exit node
-selection is much less susceptible to observation on both paths. This
+selection is susceptible to observation on both paths in only 9\% of
+cases. This
result suggests that, in certain cases, {\em a user may wish to establish
different mix-level paths for forward and reverse traffic} to minimize
the possibility that a single AS can observe both entry and exit
@@ -1431,33 +1451,31 @@
\begin{tightlist}
\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
+ different jurisdictions, this technique is not
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
+\item Certain tier-1 ISPs are prevalent on many mix network
paths. If node replacement is used in path selection, the probability
that a single AS observes all links in a four-hop path through the mix
is between 0.1 and 0.2; if node replacement is not used, this
probability is no more than 0.1 for both the Tor and Mixmaster
topologies.
-\item Figures~\ref{fig:as_observe} and~\ref{fig:as_observe_75} show
- that the intra-network diversity for the Tor topology is nearly equivalent to
- that of the Mixmaster topology. At least against observation
- attacks from a single AS, a newborn network with nodes almost entirely
- in the US is as robust as a mature network like Mixmaster.
-
-\item We analyzed common entry and exit paths in existing mix network
- topologies. We show that given random entry and exit node selection,
+\item Given random entry and exit node selection,
even when the initiator chooses distinct entry and exit nodes, a
single AS will often be able to observe both the entry and exit path
- to the mix network between 10\% and 30\% of the time. Because of path
+ to the mix network between 10\% and 30\% of the time. {\em Because of path
asymmetry in the Internet, an entry/exit node pair that has good
location independence for a forward path through the mix network may
- not always have good location independence in the reverse direction.
+ not always have good location independence in the reverse direction.}
However, if the initiator chooses entry and exit nodes with location
independence in mind, she can prevent most such attacks.
+
+\item Figures~\ref{fig:as_observe} and~\ref{fig:as_observe_75} show
+ that the intra-network diversity for the Tor topology is nearly equivalent to
+ that of the Mixmaster topology. At least against observation
+ attacks from a single AS, a newborn network with nodes almost entirely
+ in the US is as robust as a mature network like Mixmaster.
\end{tightlist}
%This work brings to light an important insight that should guide the
Index: sig-alt-full.cls
===================================================================
RCS file: /home/freehaven/cvsroot/doc/routing-zones/sig-alt-full.cls,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- sig-alt-full.cls 27 Aug 2004 19:42:43 -0000 1.2
+++ sig-alt-full.cls 1 Sep 2004 07:06:37 -0000 1.3
@@ -207,7 +207,7 @@
\topsep 4pt plus 2pt minus 2pt\parsep 2pt plus 1pt minus 1pt
\itemsep \parsep}}
-\def\footnotesize{\@setsize\footnotesize{9pt}\ixpt\@ixpt
+\def\footnotesize{\@setsize\footnotesize{8pt}\viiipt\@viiipt
\abovedisplayskip 6.4pt plus 2pt minus 4pt%
\belowdisplayskip \abovedisplayskip
\abovedisplayshortskip \z@ plus 1pt%
@@ -1231,7 +1231,7 @@
\ifnum\addauflag=0\addauthorsection\global\addauflag=1\fi
\section{%
{REFERENCES}
- \vskip -9pt % GM July 2000 (for tighter spacing)
+% \vskip -9pt % GM July 2000 (for tighter spacing)
\@mkboth{{\refname}}{{\refname}}%
}%
\list{[\arabic{enumi}]}{%
***********************************************************************
To unsubscribe, send an e-mail to majordomo@seul.org with
unsubscribe freehaven-cvs in the body. http://freehaven.net/