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

[s7r <s7r@xxxxxxxxxx>]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

I find it better to add a new consensus flag called 'Vanguard' which
will be assigned to relays with lower requirements than the 'Guard'
(less bandwidth, just the Stable flag). We will then select
second_guard_set and third_guard_set from relays having 'Vanguard'
flag. I know this could theoretically make a Sybil attack cheaper, but
by selecting first guard, second_guard_set and third_guard_set just
from the 'Guard' relays in the consensus, which are currently:

$ cat /var/lib/tor/cached-microdesc-consensus | grep "Guard" | wc -l

1552


would result in a less quality service for the users and it would
hammer the existent Guards way too much.

I don't think it's wise to change how we assign 'Guard' flag to the
relays - the requirements we now have give great results for both user
performance and load balancing. It would be better to just implement a
second/third class of guards called Vanguards. To have a bigger pool
of Vanguards so that the network will be better load balanced and also
offer more diverse possible paths it is simple - remove the relays
which are not helping at all and just eating consensus document space
(or at least a big part of them) so the vast majority of relays in the
consensus would be Vanguards. A Guard relay can also have the Vanguard
flag, but if it's selected as the Guard it should not be taken in
consideration for second_guard_set and third_guard_set. This is the
easy part.

What requires more research is:
3.2 - Distinguishing new HS circuits from normal HS circuits
3.3 - Circuit nodes can now be linked to specific hidden services.

I see 3.2 as a worse problem than 3.3. I don't see a real fix for 3.3,
it is by logic that if a middle node sees two HS circuits with the
same Vanguard can assume with high probability that those circuits
correspond to the same HS. This is just a tradeoff for this approach,
but as I said I don't see 3.3 as a flaw. What I feel little more
uncomfortable about is 3.2 which I think we should focus on.


On 7/10/2015 11:58 PM, George Kadianakis wrote:
> 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.
> 
> Thanks!
> 
> 
> ----
> 
> Filename: 246-hs-guard-discovery.txt Title: Defending Against Guard
> Discovery Attacks using Vanguards Author: George Kadianakis 
> Created: 2015-07-10 Status: Draft
> 
> 
> 0. Motivation
> 
> A guard discovery attack allow attackers to determine the guard 
> node of a Tor client. The hidden service rendezvous protocol 
> provides an attack vector for a guard discovery attack since
> anyone can force an HS to construct a 3-hop circuit to a relay
> (#9001).
> 
> Following the guard discovery attack with a compromise or coercion 
> of the guard node can lead to the deanonymization of a hidden 
> service.
> 
> 1. Overview
> 
> This document tries to make the above guard discovery + coersion 
> attack harder to launch. It introduces an optional configuration 
> option which makes the hidden service also pin the second and
> third hops of its circuits for a longer duration.
> 
> With this new path selection, we force the adversary to perform a 
> Sybil attack and two coercion attacks before succeeding.  This is 
> an improvement over the current state where the Sybil attack is 
> trivial to pull off, and only a single coercion attack is
> required.
> 
> With this new path selection, an attacker is forced to do a 
> coercion attack before learning the guard node of a hidden service.
> This increases the uncertainty of the attacker, since he will need
> to perform a coercion attack before he learns the identity of the
> guard node and whether he can compromise it. Coercion attacks are
> costly and potentially detectable, so an attacker will have to
> think twice before beginning a chain of coercion attacks that he
> might not be able to complete.
> 
> 1.1. Visuals
> 
> Here is how a hidden service rendezvous circuit currently looks
> like:
> 
> -> middle_1 -> middle_A -> middle_2 -> middle_B -> middle_3 ->
> middle_C -> middle_4 -> middle_D HS -> guard   -> middle_5 ->
> middle_E -> Rendezvous Point -> middle_6 -> middle_F -> middle_7 ->
> middle_G -> middle_8 -> middle_H ->   ...    ->  ... -> middle_n ->
> middle_n
> 
> this proposal pins the two middles nodes to a much more restricted 
> set, as follows:
> 
> -> guard_3_A -> guard_3_B HS -> guard_1 -> guard_2_A -> guard_3_C
> -> Rendezvous Point -> guard_2_B -> guard_3_D -> guard_3_E ->
> guard_3_F
> 
> 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.
> 
> 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.
> 
> 3. Discussion
> 
> 3.1 How were these security parameters chosen?
> 
> Consider an adversary with the following powers:
> 
> - Can launch a Sybil guard discovery attack against any node of a 
> rendezvous circuit. The slower the rotation period of the node, the
> longer the attack takes.
> 
> - Can compromise any node on the network. We assume that the 
> adversary cannot compromise too many nodes, otherwise Tor's 
> security would be breached anyhow.
> 
> We now calculate the time it takes for the adversary to launch a 
> Sybil attack with 50% success assuming 5% network control. This 
> depends solely on how frequently the hidden service rotates that
> node:
> 
> +-------------------+-------------------------------+-----------------
- -------+----------------------------+
>
> 
|  Rotation period  | Sybil attack with 50% success | Sybil attack (2
guards)|  Sybil attack (6 guards)   |
> +-------------------+-------------------------------+-----------------
- -------+----------------------------+
>
> 
|      1 hour       |        14 hours               |      7 hours
     |       2.5 hours            |
> |      1 day        |        14 days                |      7 days
> |       2.5 days             | |      1 week       |        3.5
> months             |      6 weeks           |       2.5 weeks
> | |      2 weeks      |        7 months               |      3.5
> months        |       5 weeks              | |      1 month      |
> 1 year and 2 months    |      6 months          |       2.5 months
> | |      3 months     |        3.5 years              |      1.7
> years         |       6 months             | 
> +-------------------+-------------------------------+-----------------
- -------+----------------------------+
>
> 
Required time for Sybil attack by a 5% adversary
> 
> Our security parameters were selected so that the first two layers 
> of guards should be hard to attack using a Sybil guard discovery 
> attack and hence require a coercion attack. On the other hand, the 
> outmost layer of guards should rotate fast enough to _require_ a 
> Sybil attack.
> 
> XXX does this security model even make sense? what about a network 
> adversary, or an adversary that can launch congestion attacks 
> etc.????
> 
> 3.2. Distinguishing new HS circuits from normal HS circuits
> 
> By pinning the middle nodes of rendezvous circuits, we make it 
> easier for all hops of the circuit to detect that they are part of
> a special hidden service circuit. XXX hm how does the outermost
> guard knows?
> 
> Compare this to the current Tor network, where only the guard and 
> the third hop of the HS circuit can trivially distinguish whether 
> it's part of an HS circuit.
> 
> 3.3. Circuit nodes can now be linked to specific hidden services
> 
> With this proposal the hops of hidden service circuits will be 
> static, and hence an adversrary will be able to map them to
> specific hidden services. For example, a middle node that sees two
> hidden service circuits with the same guard node in different
> times, can assume with non-negligible probability that both
> circuits correspond to the same hidden service.
> 
> That said, this is also partially the case for the current Tor 
> network, where the middle node can associate a guard with a
> specific hidden service.
> 
> 3.4 Why is the torrc setting disabled by default, if it's so good?
> 
> We suggest this torrc option to be optional because it puts 
> additional load on guard nodes and we are not sure if the network 
> will be able to handle it.
> 
> However, by having this setting be disabled by default, we make 
> hidden services who use it stand out a lot. For this reason, we 
> should eventually fix our hidden service circuit load balancing so 
> that we can enable this globally.
> 
> XXX But hidden services traffic is only 6% of the total network,
> so maybe it's not that big of a problem and we should just enable 
> this feature by default anyway
> 
> 3.4.1. How should we load balance to enable this feature globally?
> 
> The load balancing issue with this feature is that hidden service 
> traffic that would otherwise be passing through middle nodes, will 
> now be passing through guard nodes.
> 
> Furthermore, this additional traffic is not accounted for in our 
> bandwidth weights. This means that a guard node that had 1% 
> probability of being chosen as a guard for normal circuits, will 
> still have the same probability of being chosen as a guard even 
> though the hidden service traffic that it pushes increases.
> 
> To improve the load balancing here, we could have each relay
> report the amount of hidden service traffic it pushes every day
> (#15254), and have the authorities take this into account when they
> calculate bandwidth weights. The idea here would be that the
> dirauths would know that N% of the network is hidden services
> traffic, hence they would tweak the bandwidth weights such that
> guards would reserve some N% of their bandwidth for hidden service
> purposes.
> 
> 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.
> 
> - To make it harder for an adversary, a hidden service MAY extend 
> the path length of its circuits by an additional static hop. This 
> forces the adversary to use another coercion attack to walk the 
> chain up to the hidden service.
> 
> 5. Acknowledgements
> 
> Thanks to Aaron Johnson, John Brooks, Mike Perry and everyone else 
> who helped with this idea. 
> _______________________________________________ tor-dev mailing
> list tor-dev@xxxxxxxxxxxxxxxxxxxx 
> https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
> 
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.22 (MingW32)

iQEcBAEBCAAGBQJVoREIAAoJEIN/pSyBJlsRK0YIAMzv/Nm/gmujSUO5dNUpgm1O
8M2npzpj7ki2AmPBPFv/Ncxmrh4g6G9nKyaaljL5VK9w5qCyn659cBXSuZaQfAvo
jwmaS2ejBuFq2jBLsXlIkQroERasfv5chDYg3xzLaSIXlYHDTbKPpF+xbKZmdDkG
khr4ri7j4I63IK2Rd3eyAkK8KBim8cbBYLXeydEmA0PJYM451nPWieOrAvbSyXEe
BtFiFQ9Lh62hLwC0j/Igp+wVFb7JLw5etDkvm0hTeLfPacNABSqXOD3lZQYVhx0K
uMMCZ2zTcSqhKxfCWw0Vs421d90JrBZwC8cBKZqFPCjhWmPWgYIS1zuYVbrdX+E=
=rTzC
-----END PGP SIGNATURE-----
_______________________________________________
tor-dev mailing list
tor-dev@xxxxxxxxxxxxxxxxxxxx
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev