[tor-dev] Proposal 246: Defending Against Guard Discovery Attacks using Vanguards

[A. Johnson]

>> Here's another crazy idea that would potentially bring this Vanguards
>> idea closer to "Virtual Circuits": What if you divided your third-level
>> Vanguards into NUM_SECOND_GUARDS isolated buckets, and mapped exactly
>> one these buckets to each of your second-level guards? 
...
>> That way, if one third-level guard was compromised via a successful
>> Sybil attack, the adversary would learn at most 1 of your second-level
>> guards, instead of learning all of them and then getting to take their
>> pick which one(s) they want to try to compromise.
> 
> Neat idea! Concept is interesting and makes sense, since we need to
> protect second_guard_set for way longer period of time, and
> first_guard_set for even longer.

Not having the third guards be selected by every second guard makes sense when you consider that the adversary may not be able to compromise all relays equally. That was not a consideration I had in mind when I argued for “completely connected” guard sets. The purpose of multiple guards in a given position is (i) to allow onion services that have unusually high load to uses the excess capacity of more than one relay, (ii) to lower the variance of relay performance, and (iii) to recover more quickly from nodes leaving or failing. Note how these are all related to performance. The drawbacks of multiple relays are all related to security, and they are (i) more relays gives the adversary more chances to have his relays selected, (ii) more relays gives the adversary more options and opportunities to compromise relays once they are observed.

The best design for security purposes would be a single relay in each guard "set", with the final relay expiring the fastest. Currently, the suggestion was to keep one relay in the first guard position (or whatever NumEntryGuards is), because the security issue there is very serious (it can observe the onion service directly), and also because guards are already selected to have somewhat higher bandwidth and stability. Hopefully (currently unverified) this means that they have more *excess* capacity as well.

If you don’t allow all second guards to connect to all third guards, then you have to make a performance / security tradeoff. For example, suppose you give each second guard its own set (or “bucket”) of third guards. You shouldn’t give each second guard the same number of guards that we had planned to have in the third guard set, because that only makes things worse. Now Instead of choosing one set (of size, say, six), you have for each second relay a new chance for the adversary to own one of those relays. There is only a benefit if you reduce the number. It makes sense to me to reduce that number to one, because there is no reason to expect the third guard to be a bottleneck before the second guard (unlike the first guards, which it sounds like may be the only ones requiring the Guard flag). You still have some of the benefit of reducing performance variance and improving failure recovery because you have multiple second guards. And you have gained the benefit that was Mike’s original motivation of giving the adversary that compromises a third guard a view of only one of the second guards, with the hope that maybe this one he finds difficult to compromise.

There is an unanswered question of what to do with multiple first guards. The main reason I can see not to have single second guards for each first guard is that the first guard is likely to have more excess capacity and thus not be the bottleneck for high amounts of onion-service traffic. Assuming that's true, then I could imagine having separate second-guard buckets for each first guard as well. However, there is a bad multiplier effect here. For example, with three first guards and three second guards per first guard, there are now *nine* relays in the second-guard position, each of which presents a chance for a malicious relay to be chosen.

My current thought is that the following is a better design than the one currently in the proposal:
  1. One first guard
  2. Two second guards per first guard (so two unless NumEntryGuards is changed)
  3. One third guard per second guard (so two unless NumEntryGuards is changed)
This will only perform worse than the design suggested in the proposal (which is one first guard, two second guards, and six third guards, with all guards connected to all following guards). I think it might not much worse, though.

And I agree with the suggestions to randomize the expiration times.

Best,
Aaron