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.