[freehaven-cvs] sections 6.2 and 7.2.

[feamster@seul.org (Nick Feamster)]

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

Modified Files:
	routing-zones.tex 
Log Message:
sections 6.2 and 7.2.
last results table going in shortly



Index: routing-zones.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/routing-zones/routing-zones.tex,v
retrieving revision 1.27
retrieving revision 1.28
diff -u -d -r1.27 -r1.28
--- routing-zones.tex	28 Jan 2004 04:04:11 -0000	1.27
+++ routing-zones.tex	28 Jan 2004 05:00:04 -0000	1.28
@@ -541,19 +541,23 @@
 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
 receiver (Bob) we must also estimate the ASes where the sender (Alice)
-and receiver (Bob) may typically be located.  While usage data for these
-mix networks is not readily available, we can perform reasonable
-approximations by assuming that Alice is located on a home network
-(e.g., a cable modem network, a DSL network, etc.) and that Bob is a
-content host located at a data hosting ISP.
+and receiver (Bob) may typically be located.  Unfortunately, usage data
+for these mix networks is not readily available, so it is not possible
+to drive our simulation with lists of common locations of senders and
+receivers.  Nevertheless, we can perform reasonable approximations by
+assuming that Alice is located on a home 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, unbiased list of ASes where Alice and Bob may
-be located, we analyze Web logs and summary statistics to generate lists
-of common locations of Web clients and servers.  We use the Web server
-logs from {\tt nms.lcs.mit.edu} from January 2004 to generate a list of
-ASes where a typical sender might be located.  To generate a list of
-typical receivers, we use the top 25 sites from comScore Media Metrix's
-``Top 50 US Internet Properties'' from December 2003~\cite{www-comscore}.
+To generate a reasonable, unbiased 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
+Appendix~\ref{sec:send_recv}.
 
 
 \subsection{Network Topology}
@@ -737,14 +741,21 @@
 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 mix network at more than one location
-increases.  Figure~\ref{fig:as_observe} shows the probability that an AS
-will be able to observe more than half of the edges along the mix
-network path, for mix network paths of different lengths.  The figure
-shows results for both the Tor and Mixmaster networks, with two
-different node selection schemes: (1)~allowing the same mix node to be
-used twice along the mix path, as long as the same mix node is not used
-for two consecutive hops (Mixmaster's node selection scheme) and
-(2)~allowing each mix node to be used only once (Tor's scheme).
+increases.  To test this hypothesis, we generated random mix paths (both
+remailer paths and onion routing paths) through the mix network of
+lengths two hops through eight hops and measured the probability that
+these paths crossed the same AS on multiple edges.  For each length and
+type of path, we ran 100,000 trials and counted the number of times the
+mix network path traversed the same AS more than once.
+
+Figure~\ref{fig:as_observe} shows the probability that an AS will be
+able to observe more than half of the edges along the mix network path,
+for mix network paths of different lengths.  The figure shows results
+for both the Tor and Mixmaster networks, with two different node
+selection schemes: (1)~allowing the same mix node to be used twice along
+the mix path, as long as the same mix node is not used for two
+consecutive hops (Mixmaster's node selection scheme) and (2)~allowing
+each mix node to be used only once (Tor's scheme).
 Figure~\ref{fig:as_observe} shows two interesting results.  First, for
 all mix paths longer than four hops, some AS can observe at least half
 of the edges along the mix network path.  Second, Tor's node selection
@@ -756,32 +767,47 @@
 
 \subsection{Jurisdictional Attacks on Entry and Exit Paths}
 
-	A. Given our model of node selection and our AS-level path
-	approximation:
+To discover the jurisdictional 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
+topologies.  
 
-\begin{itemize}
-	   \item How often do the entry and exit paths (i.e., Alice->Entry
-	      and Exit->Bob) cross the same AS path?
+To do this, we generated a list of 10,000 random entry and exit pairs
+for each network and, for each sender/receiver pair, observed the number
+of times the path from the sender to the entry node traversed at least
+one AS on both paths.  Tables~\ref{tab:as_obs_ee_tor}
+and~\ref{tab:as_obs_ee_mm} shows the probability, for each sender and
+receiver, the likelihood of this event.  The table also shows the AS
+that was traversed upon both entry and exit most often.  We see that
+each pair of sender and receiver has at least some subset of entry and
+exit paths that traverse the same AS upon both entry and exit.
+Additionally, for all sender/receiver pairs, the AS that was traversed
+upon both entry and exit most often was {\em always} a tier-1 ISP.
 
-	   \item Can you do something intelligent to prevent this from
-	      happening?  i.e., constrain node selection?
-\end{itemize}
+These results suggest that the sender in a mix network should exercise
+care when selecting entry and exit nodes to avoid this scenario.  These
+results suggest that it is certainly {\em possible} for an intelligent
+sender to select entry and exit nodes such that the entry and exit paths
+do not traverse the same AS on entry and exit (e.g., between Speakeasy
+and Google, only 8\% of Tor entry/exit node pairs result in entry and
+exit paths that cross the same AS on both entry and exit).  However,
+because many Internet paths cross tier-1 ISPs, a careless sender is
+likely to be eavesdropped by a single AS at both entry and exit.
 
 
 \subsection{Secondary Attacks}
-	   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...)
+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...)
 
 
 
-\section{Design Recommendations}
+\section{Design Recommendations and Future Work}
 
 In light of our analysis, which has shown that certain ASes have
 considerable easvesdropping capabilities on mix networks, we propose two
@@ -792,9 +818,35 @@
 
 \subsection{Explicit Consideration of AS-level Paths}
 
+Our results suggest that, to reduce the probability of eavesdroping
+attacks using dispersity, designers and users of mix networks should
+take into account the underlying AS-level paths of the underlying mix
+network path.   
+
+
 \subsection{Improving Jurisdictional Independence with Node Placement}
 
-where would you add nodes, if you had the choice? talk about internap.
+Our analysis of inter-mix network paths suggest that currently deployed
+mix networks could benefit from increased diversity in node placement,
+to reduce the probability that inter-node paths traverse the same AS.
+An interesting avenue for future work would be to explore the ASes in
+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
+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
+that provide significant geographical diversity are likely to actually
+{\em reduce} jurisdictional independence, because such nodes do not
+typically have diverse AS-level connectivity.  Rather, the best places
+to place nodes for mix networks 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; this suggests that placing one node in each tier-1 ISP and
+building mix paths between those nodes may be a reasonable strategy for
+increasing jurisdictional diversity.  Exploring this question is an
+excellent direction for future work.
 
 
 %% 	B. How do these results change as we change our assumptions

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