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.