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

[s7r]

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

Hello,

Estimations look good.

I think second_guard_set & third_guard_set should not have the same
requirements like how any Tor client chooses the guard (first hop). We
can select second guards and third guards by requiring for example
just Stable flag?

For 3.4.1 - Load balancing - wouldn't this be much easier if we only
allowed relays in the consensus with a bandwidth of > n KB/s? I still
see very low bandwidth relays included in the consensus. We should
really do some math and only include relays in the consensus which
offer at least 2x (maybe even more) what it takes for the network to
include them in the consensus document and serve it to all the clients.

Most important problems are at 3.2 and 3.3
How easy would it be to distinguish the new 'special' circuits as
opposite to regular ones, and more important, what can we do to
eliminate this risk? We know that anonymity has many variables, and a
very important one is 'mixing in the crowd'. By looking different from
other users, we make one step back.



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 at lists.torproject.org 
> https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
> 
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.22 (MingW32)

iQEcBAEBCAAGBQJVoQr+AAoJEIN/pSyBJlsRWZoIALP0NbfZ36wnuzNwATk9cY1D
dXFVB/cusTP7NxPlXRqsjwR1OQjz6v8D7pdQca2ni6l43yQSdw+5yile8GNj82Tw
RUKzxcSkvIupOf31grnMgCc5I0Q60KW0gFp1gyOqjVsU4xRvJaNr3pjgva0l6PoE
IxD/22+VZOCpSzamzGtGNPfxLJTWzvZIraDKIOjRGGqs9jR3jK79EoHNAXKt2tj3
p4ElG4dAzXlJpXhJqF/e6B3g3v8fx5Rk2UT0xq1SZIysY3Rbyg11xisTEb+DvbZx
I8+S142fhQHzLgxBgmTCV8gGyMrDITvpltr0OPw/OiA8ab2igtIBv5/xE1LgAIY=
=7Q+d
-----END PGP SIGNATURE-----