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

[Mike Perry]

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.

>   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?

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


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.



-- 
Mike Perry
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 801 bytes
Desc: Digital signature
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20150715/dd66337d/attachment.sig>