[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[tor-commits] [tor-design-2012/master] Integrate path selection material from the blog posts
commit 7b05ef4dbef55f73ba9e87caf8a9e5a090cf2c31
Author: Nick Mathewson <nickm@xxxxxxxxxxxxxx>
Date: Wed Nov 14 00:46:50 2012 -0500
Integrate path selection material from the blog posts
---
todo | 10 ++----
tor-design-2012.tex | 81 +++++++++++++++++++++++++++++++++++++++++++++++++++
2 files changed, 85 insertions(+), 6 deletions(-)
diff --git a/todo b/todo
index 489ae86..da35f25 100644
--- a/todo
+++ b/todo
@@ -18,12 +18,12 @@ ITEMS:
o Improved authorization model for hidden services
o Faster first-hop circuit establishment with CREATE_FAST
o Cell queueing and scheduling.
- . Integrate content from the second blog post [steven]
+ o Integrate content from the second blog post [steven]
o guard nodes
o Bridges, censorship resistance, and pluggable transports
- - Changes and complexities in our path selection algorithms
- - Bandwidth authorities
- - Path selection rules
+ o Changes and complexities in our path selection algorithms
+ o Bandwidth authorities
+ o Path selection rules
o stream isolation
. Integrate content from the third blog post [steven]
o link protocol tls
@@ -43,8 +43,6 @@ ITEMS:
o Revise "other design decisions" [nick]
-
-
CAN DO AFTER SPONSOR DEADLINE:
- Revise related work [steven]
- Revise "attacks and defenses" [steven]
diff --git a/tor-design-2012.tex b/tor-design-2012.tex
index bb856e7..ebe39e8 100644
--- a/tor-design-2012.tex
+++ b/tor-design-2012.tex
@@ -996,6 +996,87 @@ attack~\cite{freedom21-security} is weakened.
% We never made any support for the above; when a node goes down, the
% circuits through it get destroyed. (Check that.) -NM
+\subsection{Choosing nodes for circuits}
+
+Early onion routing designs assumed a set of uniform nodes, from
+which clients would therefore choose uniformly at random. But this
+approach creates terrible bandwidth bottlenecks: a server that would
+allow 10x as many bytes per second as another would still get the
+same number of circuits constructed through it, leading to
+overloaded low-capacity relays and underutilized high-capacity
+bandwidth.
+
+Therefore, Tor now weights\footnote{In the original paper, we
+ imagined that we might take Morphmix's approach, and divide nodes
+ into "bandwidth classes", such that clients would choose only from
+ among nodes having at least the same approximate bandwidth as the
+ clients. This may be a good design for peer-to-peer anonymity
+ networks, but it doesn't seem to work for the Tor network: the
+ most useful high-capacity nodes have more capacity than nearly any
+ typical client.}
+its choice of nodes by servers' bandwidths, so
+that a server with more bandwidth gets more circuits, and therefore
+(probabilistically) more of the traffic.
+
+Later, it proved that weighting by bandwidth was also suboptimal,
+because of nonuniformity in path selection rules. Consider that if
+node A is suitable for use at any point in a circuit, but node B is
+suitable only as the middle node, then node A will be considered for
+use three times as often as B. If the two nodes have equal
+bandwidth, node A will be chosen three times as often, leading to it
+being overloaded in comparison with B. So now
+0.2.2.10-alpha, we moved to a more sophisticated approach, where
+nodes are chosen proportionally to their bandwidth, as weighted by
+an algorithm to optimize load-balancing between nodes of different
+capabilities.
+
+Weighting by \emph{advertised} bandwidth would open the possibility
+of an attacker trying to see a disproportionate number of
+circuits---not by running an extra-high number of nodes---but by
+claiming to have a very large bandwidth.
+
+For a while, Tor tried to limit the impact of this attack by limiting
+the maximum bandwidth that a client would believe, so that a single
+rogue node couldn't just claim to have infinite bandwidth. This
+approach proved unuseful, since some real nodes did in fact have
+very high bandwidth.
+
+But now, clients use \emph{measured} bandwidth values published in
+the network status consensus document (see
+section~\ref{what?XXX}). A subset of the authorities measure and
+vote on nodes' observed bandwidth, to prevent misbehaving nodes from
+claiming (intentionally or accidentally) to have too much capacity.
+
+\subsubection{Avoiding duplicate node families in the same circuit}
+
+As mentioned above, if the first and last node in a circuit are
+controlled by an adversary, they can use traffic correlation attacks
+to notice that the traffic entering the network at the first hop
+matches traffic leaving the circuit at the last hop, and thereby
+trace a client's activity with high probability. Research on
+preventing this attack has not yet come up with any affordable,
+effective defense suitable for use in a low-latency anonymity
+network. Therefore, the most promising mitigation strategies seem to
+involve lowering the attacker's chances of controlling both ends of
+a circuit.
+
+To this end, clients do not use any two nodes in a circuit whose IP
+addresses are in the same /16. (When we designed the network, it was
+marginally more difficult to acquire a large number of disparate
+addresses than it was to get a large number of concentrated
+addresses. This approach is imperfect, but possibly better than
+nothing.
+
+To allow honest node operators to run more than one server without
+inadvertently giving themselves the chance to see more traffic than
+they should, we also allow nodes to declare themselves to be members
+of the same ``family,'' such that a client won't use two nodes in the
+same family in the same circuit. (Clients only believe mutual family
+declarations, so that an adversary can't capture routes by having
+his nodes claim unilaterally to be in a family with every node the
+adversary doesn't control.)
+
+
\subsection{Opening and closing streams}
\label{subsec:tcp}
_______________________________________________
tor-commits mailing list
tor-commits@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-commits