[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[freehaven-cvs] progress on section 2.2 and parts of 3.
Update of /home/freehaven/cvsroot/doc/routing-zones
In directory moria.mit.edu:/tmp/cvs-serv23780
Modified Files:
routing-zones.bib routing-zones.tex
Log Message:
progress on section 2.2 and parts of 3.
feel free to help write 3.1 and 3.2 :)
or, if you prefer, we could discuss and I could write them...eventually
Index: routing-zones.bib
===================================================================
RCS file: /home/freehaven/cvsroot/doc/routing-zones/routing-zones.bib,v
retrieving revision 1.2
retrieving revision 1.3
diff -u -d -r1.2 -r1.3
--- routing-zones.bib 14 Jan 2004 03:24:21 -0000 1.2
+++ routing-zones.bib 18 Jan 2004 01:06:24 -0000 1.3
@@ -142,3 +142,32 @@
www_section = {Anonymous publication},
}
+@manual{rfc1771,
+ author= "Y. Rekhter and T. Li",
+ title="{A Border Gateway Protocol 4 (BGP-4)}",
+ note = {RFC 1771},
+ organization = "{Internet Engineering Task Force}",
+ year=1995,
+ mon=mar,
+}
+
+@InProceedings{Mao2003,
+ author = {Zhuquing Morley Mao and Jennifer Rexford and Jia Wang and Randy Katz},
+ title = {Towards an Accurate AS-level Traceroute Tool},
+ booktitle = {Proc. ACM SIGCOMM},
+ year = {2003},
+ address = {Karlsruhe, Germany},
+ month = {August},
+}
+
+
+@Article{Gao2001,
+ author = {Lixin Gao},
+ title = {On Inferring Automonous System Relationships in the {I}nternet},
+ year = {2001},
+ month = {December},
+ journal = {IEEE/ACM Transactions on Networking},
+ volume = {9},
+ number = {6},
+ pages = {733--745},
+}
Index: routing-zones.tex
===================================================================
RCS file: /home/freehaven/cvsroot/doc/routing-zones/routing-zones.tex,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -d -r1.1 -r1.2
--- routing-zones.tex 13 Jan 2004 08:31:35 -0000 1.1
+++ routing-zones.tex 18 Jan 2004 01:06:24 -0000 1.2
@@ -47,12 +47,13 @@
\cite{defensive-dropping,SS03}.
Anonymity designs use three major strategies to mitigate these attacks.
-{\bf{Batching and pooling:}} The network collects a group of input
+\begin{itemize}
+\item {\bf{Batching and pooling:}} The network collects a group of input
messages and reorders them before they exit, to prevent the adversary
from learning which message in the batch originated from a given sender
\cite{chaum81,trickle02}.
% (Of course, this only works if the system can tolerate some latency.)
-{\bf{Padding:}} Senders also provide decoy traffic, to
+\item {\bf{Padding:}} Senders also provide decoy traffic, to
complicate the adversary's attempts to correlate sender and receiver
\cite{pipenet,defensive-dropping,langos02}.
%Pipenet \cite{pipenet} conceals traffic patterns by
@@ -64,10 +65,11 @@
%difficulty of intersection attacks with a scheme for preparing plausible
%dummy traffic and having other nodes send it for you while you're offline
%\cite{langos02}; but their design has many practical problems.
-{\bf{Dispersal:}} Reducing the chance that the adversary sees
+\item {\bf{Dispersal:}} Reducing the chance that the adversary sees
both endpoints for a given communication can entirely block some
attacks on low-latency networks, and slow down intersection attacks on
high-latency networks.
+\end{itemize}
Dispersal can be achieved by increasing the number of nodes in the
network, so an adversary of a given strength sees less of the network
@@ -103,41 +105,216 @@
so if we can make a good improvement in protection with not too much
effort, we should.
-\subsection{Internet topology}
- B. Network Topology
+\subsection{Overview of Internet Routing}
- - Brief overview of the structure of the internet, its division
- in to ASes (ISPs), best route selection, etc.
+We eventually would like to determine which networks packets will
+traverse between each node of a mix-net. To do this, we must first
+understand how packets are routed between two arbitrary hosts on the
+Internet. In this section, we first present a brief overview of
+interdomain routing (i.e., routing between ISPs) on the Internet. We
+then describe how to estimate the network-level path between two hosts
+on the Internet using the BGP routing tables.
- - Inferring AS-level paths. Work from Mao et al. on how to
- predict/estimate the sequence of ASes that a packet will
- travel through.
+\subsubsection{Border Gateway Protocol}
- - Brief mention of routeviews, perhaps
+The Internet is composed of over 15,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
+Internet Service Provider (ISP), a corporate network, or a university.
+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
+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
+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.
-\section{Model/Analysis Techniques}
+The Internet's routing table has over 130,000 distinct prefixes, each of
+which has an associated route. An AS that originates a route
+readvertises this route to neighboring ASes via BGP and attaches its AS
+number to the {\em AS path} of the route. When a router in neighboring
+AS learns this route, that router propagates it to all of the routers in
+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
+a destination that it learns via BGP.
+
+ASes do not blindly propagate routes to all of their neighbors; rather,
+each pair of ASes has a commercial relationship, and an AS may prefer to
+send traffic via one AS other 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; and (2)~a peering relationship, where two ASes
+exchange traffic between their own networks (and the networks of their
+customers), but do neither pays the other for this privilege.
+
+BGP is a distinctive routing protocol because it is based on {\em
+policy}, rather than on shortest paths. For example, an AS will
+typically prefer to route traffic to a destination via one of its
+customers (who pays it for connectivity) than via one of its providers
+(who it must pay to send traffic towards) or one of its peers. These
+relationships also determine which routes one AS will advertise to
+another. For example, an AS will typically not advertise a route
+learned from one of its peers or providers to any of its other peers or
+providers: doing so would constitute an implcit agreement to forward
+traffic (i.e., provide ``transit'' service) between two of its
+providers, two of its peers, etc. {\bf XXX maybe put a figure here}
+
+\begin{figure}
+\begin{small}
+\begin{verbatim}
+ Network Next Hop Metric LocPrf Weight Path
+*>i18.0.0.0/8 64.243.30.141 100 0 6347 3356 3 i
+* i 65.115.97.141 10 100 0 209 10578 3 i
+\end{verbatim}
+\end{small}
+\caption{Example BGP routing table entry (taken from a Cisco-like router).}
+\label{fig:bgp_example}
+\end{figure}
+
+
+Figure~\ref{fig:bgp_example} shows a simplified BGP routing table entry.
+This router has learned two routes to the destination prefix {\tt
+18.0.0.0/8} via BGP. Each route has various attributes, which include
+the ``next hop'' IP address to route packets too to use this path,
+various attributes that affect which route is selected as the preferred
+route to the destiantion, 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}.}
+
+\subsubsection{AS-level Internet Topology}
+
+There are many publically-available places that provide access to
+routing table data. The most prevalent is the Oregon Routeviews
+Project~\cite{www-routeviews}, which maintains a route server that peers
+with more than 30 ASes. Each of these ASes sends its routing tables to
+the Routeviews server, which include that AS's best route to each
+destination prefix. Each AS's routing table is slightly different,
+which means that
+
+
+\section{Modeling Techniques}
+In this section, we describe how we model mix-nets and Internet routing
+to draw conclusions about how vulnerable a mix-net might be to
+eavesdropping by an adversary. We first provide a detailed description
+of our threat model; i.e., the types of adversaries that we are trying
+to defend against. Then, we describe how our model of mix-net node
+selection. Finally, we present our techniques for estimating the
+AS-level path between two arbitrary hosts on the Internet.
+
+\subsection{Threat Model}
+
+Briefly describe the threat model here. Who are we defending against?
+Presumably some government agency (or other malcontent) that can go get
+subpoenas for ISPs. Also, perhaps the ISPs themselves.
+
+\subsection{Mix-nets}
A. Overview of how systems like Tor select mix nodes, and our
approximation of this (for the purposes of analyzing the
routeviews data)
- B. How we determine the AS-level path between two arbitrary
- nodes.
- o pretty easy when you have access to the source (i.e., the
- initial vertex)
- o more difficult when you don't have access to either of the
- two endpoints but you can make reasonable approximations
- - passive: use something like Mao's techniques on
- routeviews data. basically, a constrained shortest AS
- hop count thing
+\subsection{AS-level path estimation}
+
+If the initiator of a mix-net path had access to an up-to-date routing
+table of every network where it had mix nodes, then it 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, the initiator
+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, the initiator cannot generally ask for routing tables for
+each of the mix nodes when it wishes to construct a mix tunnel. First,
+the initiator's act of requesting a routing table from a particular
+network might raise the suspicion of an eavesdropper (particularly if an
+initiator asks for a large number of routing tables, since each full
+routing table is approximate 10 megabytes). Second, asking each network
+that contains a mix node for its current routing table is likely to be
+quite slow, given the size of routing tables; additionally, as routes
+are continually changing, parts of the table are likely to be
+out-of-date before the initiator even receives it. Third, this method
+introduces another vulnerability to attack: if an adversary compromises
+any of the domains that contain a mix node, it could send back an
+inaccurate version of the routing table. Because of these shortcomings,
+the initiator 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 the 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, etc.) and can provide reasonable
+information about what path an arbitrary Internet host might take to
+reach any given destiantion. 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 very similar to this proposed
+technique.
+
+\begin{enumerate}
+\itemsep=1pt
+\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
+ 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
+ the AS-level topology of the Internet.
+
+\vspace{0.1in}
+ Of course, because the policies that are applied due to commercial
+ relationships (i.e., an AS may filter routes learned from one peer
+ when advertising routes to another peer or provider, etc.) certain
+ edges in this graph will not be globally visible. As a result, our
+ approximation of the AS-level graph may omit certain edges.
+ Typically, these missing edges will between smaller ASes; this means
+ that our algorithm may not realize that a particular edge exists
+ between two ASes and, as a result, infer the wrong AS-level path to a
+ destination.
+
+\item {\em Determine the relationships between each pair of ASes.} This
+ is a notoriously difficult problem, because ASes typically guard the
+ nature of the relationships they have with neighboring ASes.
+ Fortunately, we can use heuristics from previous work that tend to
+ work reasonably well~\cite{Gao2001}.
+
+\vspace{0.1in}
+ The basic idea is to exploit the {\em valley-free} property of
+ Internet paths to assign pairwise relationships between ASes. That
+ is, an AS path traverses a sequence of customer-provider edges, zero
+ or one peering edges, followed by a sequence of provider-customer
+ edges. The trick is to follow
+
+\item {\em Determine the origin and destination AS for the path in
+ question.}
+
+\item {\em Estimate the AS-level path between the two ASes by finding
+ the shortest AS path that complies with common policy practices.} Mao
+ finds that this type of technique works XX\% of the time. As these
+ techniques improve, the accuracy of our analysis will also improve.
+ More importantly, more accurate techniques for estimating the AS-level
+ path between two arbitrary Internet hosts will allow the initiator of
+ a mix-net to make more informed decisions about the mix nodes it
+ should choose.
+
+\end{enumerate}
+
- - active: if you could actually _ask_ one of these nodes to
- do traceroutes, or send you a view of its routing table,
- you could obviously do better, but this:
- - is likely slow/can't be precomputed
- - might tip off the adversary
- - is open to attacks where the node lies
\section{Results}
@@ -166,7 +343,7 @@
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
+ simply just tells the adversary where Alice is *not*, but
there are plenty of places Alice could still be...)
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/