[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[tor-commits] [torspec/master] Add proposal 310 from Florentin Rochet, Aaron Johnson et al
commit 42339301d427e831498ba592a41473afc12f8900
Author: Nick Mathewson <nickm@xxxxxxxxxxxxxx>
Date: Mon Nov 25 12:00:37 2019 -0500
Add proposal 310 from Florentin Rochet, Aaron Johnson et al
---
proposals/000-index.txt | 2 +
proposals/310-bandaid-on-guard-selection.txt | 95 ++++++++++++++++++++++++++++
2 files changed, 97 insertions(+)
diff --git a/proposals/000-index.txt b/proposals/000-index.txt
index 44de59f..50cd921 100644
--- a/proposals/000-index.txt
+++ b/proposals/000-index.txt
@@ -230,6 +230,7 @@ Proposals by number:
307 Onion Balance Support for Onion Service v3 [DRAFT]
308 Counter Galois Onion: A New Proposal for Forward-Secure Relay Cryptography [DRAFT]
309 Optimistic SOCKS Data [DRAFT]
+310 Towards load-balancing in Prop 271 [OPEN]
Proposals by status:
@@ -267,6 +268,7 @@ Proposals by status:
296 Have Directory Authorities expose raw bandwidth list files
299 Preferring IPv4 or IPv6 based on IP Version Failure Count
306 A Tor Implementation of IPv6 Happy Eyeballs
+ 310 Towards load-balancing in Prop 271
ACCEPTED:
188 Bridge Guards and other anti-enumeration defenses
249 Allow CREATE cells with >505 bytes of handshake data
diff --git a/proposals/310-bandaid-on-guard-selection.txt b/proposals/310-bandaid-on-guard-selection.txt
new file mode 100644
index 0000000..642d90f
--- /dev/null
+++ b/proposals/310-bandaid-on-guard-selection.txt
@@ -0,0 +1,95 @@
+Filename: 310-bandaid-on-guard-selection.txt
+Title: Towards load-balancing in Prop 271
+Author: Florentin Rochet, Aaron Johnson et al.
+Created: 2019-10-27
+Supersedes: 271
+Status: Open
+
+1. Motivation and Context
+
+ Prop 271 causes guards to be selected with probabilities different than their
+ weights due to the way it samples many guards and then chooses primary guards
+ from that sample. We are suggesting a straightforward fix to the problem, which
+ is, roughly speaking, to choose primary guards in the order in which they were
+ sampled.
+
+ In more detail, Prop 271 chooses guards via a multi-step process:
+ 1. It chooses 20 distinct guards (and sometimes more) by sampling without
+ replacement with probability proportional to consensus weight.
+ 2. It produces two subsets of the sample: (1) "filtered" guards, which are
+ guards that satisfy various torrc constraints and path bias, and (2)
+ "confirmed" guards, which are guards through which a circuit has been
+ constructed.
+ 3. The "primary" guards (i.e. the actual guards used for circuits) are
+ chosen from the confirmed and/or filtered subsets. I'm ignoring the
+ additional "usable" subsets for clarity. This description is based on
+ Section 4.6 of the specification
+ (https://gitweb.torproject.org/torspec.git/tree/guard-spec.txt).
+
+
+1.1 Picturing the problem when Tor starts the first time
+
+ The primary guards are selected *uniformly at random* from the filtered guards
+ when no confirmed guards exist. No confirmed guards appear to exist until some
+ primary guards have been selected, and so when Tor is started the first time
+ the primary guards always come only from the filtered set. The uniformly-random
+ selection causes a bias in primary-guard selection away from consensus weights
+ and towards a more uniform selection of guards. As just an example of the
+ problem, if there were only 20 guards in the network, the sampled set would be
+ all guards and primary guard selection would be entirely uniformly random,
+ ignoring weights entirely. This bias is worse the larger the sampled set is
+ relative to the entire set of guards, and it has a significant effect on Tor
+ simulations in Shadow, which are typically on smaller networks.
+
+2. Solution Design
+
+ We propose a solution that fits well within the existing guard-selection
+ algorithm. Our solution is to select primary guards in the order they were
+ sampled. This ordering should be applied after the filtering and/or confirmed
+ guard sets are constructed as normal. That is, primary guards should be
+ selected from the filtered guards (if no guards are both confirmed and
+ filtered) or from the set of confirmed and filtered guards (if such guards
+ exist) in the order they were initially sampled. This solution guarantees that
+ each primary guard is selected (without replacement) from all guards with a
+ probability that is proportional to its consensus weight.
+
+2.1 Performance implications
+
+ This proposal is a straightforward fix to the unbalanced network that may arise
+ from the uniform selection of sampled relays. It solves the performance
+ correctness in Shadow for which simulations live on a small timeframe. However,
+ it does not solve all the load-balancing problems of Proposal 271. One other
+ load-balancing issue comes when we choose our guards on a date but then make
+ decisions about them on a different date. Building a sampled list of relays at
+ day 0 that we intend to use in a long time for most of them is taking the risk
+ to slowly make the network unbalanced.
+
+2.2 Security implications
+
+ This proposal solves the following problems: Prop271 reduces Tor's security by
+ increasing the number of clients that an adversary running small relays can
+ observe. In addition, an adversary has to wait less time than it should after
+ it starts a malicious guard to be chosen by a client. This weakness occurs
+ because the malicious guard only needs to enter the sampled list to have a
+ chance to be chosen as primary, rather than having to wait until all
+ previously-sampled guards have already expired.
+
+2.3 Implementation notes
+
+ The code used for ordering the confirmed list by confirmed idx should be
+ removed, and a sampled order should be applied throughout the various lists.
+ The next sampled idx should be recalculed from the state file, and the
+ sampled_idx values should be recalculated to be a dense array when we save the
+ state.
+
+3. Going Further -- Let's not choose our History (future work)
+
+ A deeper refactoring of Prop 271 would try to solve the load balancing problem
+ of choosing guards on a date but then making decisions about them on a
+ different date. One suggestion is to remove the sampled list, which we can
+ picture as a "forward history" and to have instead a real history of previously
+ sampled guards. When moving to the next guard, we could consider *current*
+ weights and make the decision. The history should resist attacks that try to
+ force clients onto compromised guards, using relays that are part of the
+ history if they're still available (in sampled order), and by tracking its
+ size. This should maintain the initial goals of Prop 271.
_______________________________________________
tor-commits mailing list
tor-commits@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-commits