Hello,
On 14/10/2019 13:29, Roger Dingledine wrote:
On Mon, Oct 14, 2019 at 07:56:29AM +0000, Florentin Rochet wrote:
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.
This looks like a good solution to the issue -- the ordering of the guards as we select them is proportional to their weight, so let's just use them in the order that we selected them.
One of the tricky features of the prop#271 guard selection design is that it won't just keep on choosing guards if many are unreachable, but rather it will stop after a while, so a bad ISP can't totally control what guard you pick. I think that feature is left untouched by your design change, since we're choosing from among only the same set as before, just in a different order. But please think about whether that is true.
Yes, so I think this patch is actually improving this goal since the bad ISP has first to exhaust the sampled list to have a chance to get in.
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.
Can you help us make sure we think of all the places you've already thought of? :)
Sure! This is mostly code cleanup (as the confirmed ordering is not meaningful anymore), tests unit cleanup and a bit of spec rewriting (the reverse order of steps might be preferable, though :)
I would be happy reviewing any final patch. I could also do the patch myself after my current work is submitted.
<skip> > 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. This part makes me wonder about another angle to this problem: proper load balancing when we choose our guards on one date but then make decisions about them on a different date.
For example, if we sample all these guards on day 0, and then use the first guard for a week, and then move to the second guard... but the weights have changed in that time... what will that do to our load balancing? One extreme case would be a relay that has a really high weight for a while, and then later turns out to have much lower bandwidth. It gets into a bunch of guard lists at first (but mostly not #1 since that's how the probabilities work), and then slowly clients shift load to it as their #1 guard goes away.
In an ideal world we would want to take into account current guard weights, when we're shifting from one guard to the next, rather than making that decision way earlier before we actually turn out to need the guards. Maybe that argues for delaying more of the decisions?
Note that this question is about yet another improvement that could be made to the guard part of path selection, and I think it's orthogonal to the improvement you are proposing.
I guess the amount of work is also dependent of how far we want to go. As you mention, there are still load-balancing problems when "we choose our guards on one date but then make decisions about them on a different date". It is possible to get this fixed by removing the sampled list and, instead, keeping an history a 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 sample order), and by tracking its size.
That second improvement seems to be a deeper refactoring of the proposal and the code, but it could be interesting, especially when hundreds of relays get an EoL network-reject. There might be some domino effect at play here, because some % of clients got a rotation of their EoL guard.
Is there any argument not to do both?
1) Applying this patch and extending the technique throughout the guard selection logic should be straightforward and solve most of the problem (should be fast to get). 2) Deeper refactoring of the proposal as you mention (note, this shouldn't make the step 1 useless, as the logic should be reused here).
I've opened a trac ticket for 1) https://trac.torproject.org/projects/tor/ticket/32088
Best,
Florentin