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

[s7r]

Comments inline.

On 7/16/2015 7:26 AM, Mike Perry wrote:
> George Kadianakis:
>> Hello,
>>
>> I'm attaching a proposal draft that should help us defend against
>> guard discovery attacks.
>>
>> There are a few pieces left unfinished (see the XXXs) but I decided to
>> release early and release often for the sake of moving forward with
>> this. I consider this issue very important and any feedback is greatly
>> appreciated.
> 
> This looks pretty good, George. Some comments in-line.
> 
>> ----
>>
>> Filename: 246-hs-guard-discovery.txt
>> Title: Defending Against Guard Discovery Attacks using Vanguards
>> Author: George Kadianakis
>> Created: 2015-07-10
>> Status: Draft
>>
>> 2. Design
>>
>>   This feature requires the HiddenServiceGuardDiscovery torrc option
>>   to be enabled.
>>
>>   When a hidden service picks its guard nodes, it also picks two
>>   additional sets of guard nodes `second_guard_set` and
>>   `third_guard_set` of size NUM_SECOND_GUARDS and NUM_THIRD_GUARDS
>>   respectively.
>>
>>   When a hidden service needs to establish a circuit to an HSDir,
>>   introduction point or a rendezvous point, it uses nodes from
>>   `second_guard_set` as the second hop of the circuit and nodes from
>>   `third_guard_set` as third hops of the circuit.
>>
>>   A hidden service rotates 'second_guard_set' every
>>   SECOND_GUARD_ROTATION hours, and 'third_guard_set' every
>>   THIRD_GUARD_ROTATION hours.
>>
>>   These extra guard nodes should be picked with the same path
>>   selection procedure that is used for regular guard nodes. Care
>>   should be taken such that guard sets do not share any common
>>   relays. XXX or simply that they are not used in the same circuit?
>>
>>   XXX maybe pick the second and third layer guards from the set of
>>       middle nodes but also enforce some kind of uptime requirement?
>>       that should greatly help our load balancing.
> 
> I think for path fingerprinting reasons ("WTF, I appear to be a middle
> node, but I'm a Guard node in between two Guard nodes. This must be an
> *extra* interesting hidden service!") you should use nodes from the same
> flag set as normal path selection for the middle and third hop.
> 

+1; I have commented on this in my previous mails related to this
thread, but I will repeat again in order to highlight your comment. Some
things to take into consideration:

- add another flag called 'Vanguard', which will be assigned with lower
requirements than the 'Guard' flag, in order to make the vast majority
of relays Vanguards and gain more diversity / increase possible paths;
- choose first_guard_set from relays with 'Guard' flag, as we currently
do, no changes;
- choose second_guard_set and third_guard_set from relays with
'Vanguard' flag. A certain Vanguard relay should not be in
second_guard_set and third_guard_set at the same time.

>>   XXX maybe we should also introduce consensus flags for the extra
>>       guard layers? Vanguard?
>>
>>   XXX how should proposal 241 ("Resisting guard-turnover attacks") be
>>       applied here?
>>
>> 2.1. Security parameters
>>
>>   We set NUM_SECOND_GUARDS to 2 nodes and NUM_THIRD_GUARDS to 6 nodes.
>>   We set SECOND_GUARD_ROTATION to 2 weeks and THIRD_GUARD_ROTATION to 1 day.
>>
>>   See the discussion section for more analysis on these constants.
> 
> I am worried that THIRD_GUARD_ROTATION of 1 day is not fast enough to be
> sure that a targeted attack on a specific currently-used third-level
> guard wouldn't work. Can you maybe expand your table from Section 3 to
> show us datapoints for 4, 8, 12 hour THIRD_GUARD_ROTATION rates?
> 
> It would also be interesting to see tables for a 1%, and 10% adversary
> as well.
> 
> In terms of specific implementation, what if the THIRD_GUARD_ROTATION
> period was randomized between M and N hours (for M~=2, N~=10 for an
> average of 6 hours, or M~=8, N~=16 for an average of 12), so that
> the adversary could not be sure that a given third-level guard would
> remain in place for a predictable time period long enough that they
> could successfully mount a reliable attack on a specific relay itself?
> 

Randomization of the rotation periods is a must, from my point of view.
second_guard_set should have more than 2 Vanguards. Maybe we can look
into this numbers:

second_guard_set -> NUM_SECOND_GUARDS = 6 Vanguards
SECOND_GUARD_ROTATION = random between M and N (M~=1 month ; N~=3 months)

third_guard_set -> NUM_THIRD_GUARDS 18 Vanguards
THIRD_GUARD_ROTATION = random between M and N (M~=6 hours ; N~=10 hours;
average ~= 8 hours)

Of course not just any hidden service would need so many Vanguards in
second_guard_set and third_guard_set - only the popular ones. The low
usage hidden services can select and keep in memory a second_guard_set
and third_guard_set but only use 2 relays from the second_guard_set and
6 relays from the third_guard_set unless required to build a large
amount of rendezvous circuits. An attacker could force a hidden service
to build a large amount of rendezvous circuits, but if the entire
second_guard_set and third_guard_set is already selected and kept
somewhere with the rotation periods configured, it shouldn't open the
door for a new attack which is not possible already.


> The overall time-to-sybil-compromise of a randomized guard rotation
> duration should be the same as a fixed duration, and I think the
> randomization would remove the certainty of being able to walk right up
> the whole chain if you timed everything right beforehand.
> 
> This might also be a good idea for SECOND_GUARD_ROTATION, too, and IIRC
> we already to a form of this for the first Guard (or at least we used
> to).
> 
> I think each guard should be rotated independently, for similar reasons,
> and the same intuition is also making me think we want more than two
> second-level Guards, as well. If you are not sure when the second-level
> guard you found might rotate away, you're going to be forced to try to
> compromise a larger fraction of them if you want more certainty before
> you have to start over. This will also be noisy.
> 
> 
>> 4. Future directions
>>
>>   Here are some more ideas for improvements that should be done sooner
>>   or later:
>>
>>   - Maybe we should make the size and rotation period of
>>     secondary/third guard sets to be configurable by the user.
> 
> What about as a function of the consensus? That third hop could also
> rotate faster if we had more nodes/more diversity..
> 

A consensus parameter is always better, it means less headache for the
users and should give better results, because everyone will be using it
regardless if they know about it or not.

> 
> 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? Then, when making
> Rend Circs, after you select a second-level hop for a given circuit, you
> can only extend to the third-level guards that correspond to the bucket
> for that second-level guard.
> 
> 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.
> 
> Does that make sense?
> 
> With this change, it seems like we could then make the third-level
> rotation even faster, because even successful Sybils get you much less
> info.
> 
> 

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.

Third_guard_set should always be considered known by an attacker. Given
that the client selects the rendezvous relay in a hidden service
circuit, we can start with the assumption that the rendezvous relay is
evil and all the relays from third_guard_set are known to the attacker.
It's quite easy with a few evil clients and evil relays being selected
as rendezvous every time, to learn about all the relays (let's assume
number is 18) from third_guard_set in < 30 minutes?  We need a value for
THIRD_GUARD_ROTATION as low as possible and possibly a bigger value for
NUM_THIRD_GUARDS.

> 
> 
> 
> _______________________________________________
> tor-dev mailing list
> tor-dev at lists.torproject.org
> https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
>