[tor-dev] Proposal 271 - improvements

Mon Oct 14 07:56:29 UTC 2019

Hello,

I'm doing research on improving Tor security via path selection. This 
work is with Ryan Wails, Aaron Johnson, Prateek Mittal, and Olivier 
Pereira. In our work, we ran into load-balancing problems that affected 
our experiments. We identified the problem to originate in the 
specification and implementation of Proposal 271, "Another algorithm for 
guard selection", which was implemented in tor-0.3.0.1-alpha ~2 years 
ago and is thus now in tor stable. In short, 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. We have created a patch implementing this fix for the 
case affecting our experiments, which would improve the current 
situation. We are further suggesting that Tor apply the technique 
throughout the guard-selection logic.

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 (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 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).

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, which are typically on smaller networks. We believe 
that this issue has only a limited effect on Tor currently due to the 
relatively large number of guards.

However, the issue is potentially worse when there exist confirmed 
guards. In this case, primary guards are chosen from the intersection of 
confirmed and filtered guards in the order they were added to the 
confirmed set. That order seems to be the order in which circuits were 
successfully created through the guards, which would thus be both 
somewhat non-deterministic (because it depends on when a circuit 
successfully finishes) and random (because circuits are only attempted 
through primary guards, which are initially uniformly-random filtered 
guards). The non-determinism especially could yield guard selection 
probabilities that deviate quite a bit from the consensus weights.

This design has both performance and security implications. It 
potentially reduces the performance of the Tor network by making the 
load unbalanced. It also affects the correctness of performance analyses 
done with Shadow simulations, and the error is likely much larger due to 
the smaller size of simulation networks, which commonly include 100 or 
fewer guards. The design also 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.

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.

We include a patch that applies this ordering only when primary guards 
are selected from filtered guards. This fixes the problem in Shadow 
simulations because confirmed guards never exist when primary guards are 
being selected. However, to solve all issues in the real Tor network, we 
recommend that you apply similar logic to the case that primary guards 
are selected from confirmed guards.

Note that the issue of sampling skewing guard selection seems to have 
been raised in proposal discussions, which is documented in the proposal 
(although the proposed solution is less practical):

 > [Paul Syverson in a conversation at the Wilmington Meeting 2017 says that
 > we should look into how we're doing this sampling. Essentially, his
 > concern is that, since we are sampling by bandwidth at first (when we
 > choose the `sampled` set), then later there is another bias—when 
trying to
 > build circuits (and hence marking guards as confirmed) we select those
 > which completed a usable circuit first (and hence have the lowest
 > latency)—that this sort of "doubly skewed" selection may "snub" some
 > low-consensus-weight guards and leave them unused completely.  Thus the
 > issue is primarily that we're not allocating network resources
 > efficiently.  Mine and Nick's guard algorithm simulation code never
 > checked what percentage of possible guards the algorithm reasonably
 > allowed clients to use; this would be an interesting thing to check in
 > simulation at some point.  If it does turn out to be a problem, Paul's
 > intuition for a fix is to select uniformly at random to obtain the
 > `sampled` set, then weight by bandwidth when trying to build circuits and
 > marking guards as confirmed. —isis]

Best,

Florentin

-------------- next part --------------
A non-text attachment was scrubbed...
Name: 1500cli-250rel_sampling_exp.pdf
Type: application/pdf
Size: 77249 bytes
Desc: 1500cli-250rel_sampling_exp.pdf
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20191014/1585c1e1/attachment-0001.pdf>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-Makes-selection-of-filtered-guards-and-primary-guard.patch
Type: text/x-patch
Size: 7206 bytes
Desc: 0001-Makes-selection-of-filtered-guards-and-primary-guard.patch
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20191014/1585c1e1/attachment-0001.bin>