Comments inline.
On 7/16/2015 7:26 AM, Mike Perry wrote:
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
- 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.
+1; I have commented on this in my previous mails related to this thread, but I will repeat again in order to highlight your comment. Some things to take into consideration:
- add another flag called 'Vanguard', which will be assigned with lower requirements than the 'Guard' flag, in order to make the vast majority of relays Vanguards and gain more diversity / increase possible paths; - choose first_guard_set from relays with 'Guard' flag, as we currently do, no changes; - choose second_guard_set and third_guard_set from relays with 'Vanguard' flag. A certain Vanguard relay should not be in second_guard_set and third_guard_set at the same time.
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?
Randomization of the rotation periods is a must, from my point of view. second_guard_set should have more than 2 Vanguards. Maybe we can look into this numbers:
second_guard_set -> NUM_SECOND_GUARDS = 6 Vanguards SECOND_GUARD_ROTATION = random between M and N (M~=1 month ; N~=3 months)
third_guard_set -> NUM_THIRD_GUARDS 18 Vanguards THIRD_GUARD_ROTATION = random between M and N (M~=6 hours ; N~=10 hours; average ~= 8 hours)
Of course not just any hidden service would need so many Vanguards in second_guard_set and third_guard_set - only the popular ones. The low usage hidden services can select and keep in memory a second_guard_set and third_guard_set but only use 2 relays from the second_guard_set and 6 relays from the third_guard_set unless required to build a large amount of rendezvous circuits. An attacker could force a hidden service to build a large amount of rendezvous circuits, but if the entire second_guard_set and third_guard_set is already selected and kept somewhere with the rotation periods configured, it shouldn't open the door for a new attack which is not possible already.
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.
- 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..
A consensus parameter is always better, it means less headache for the users and should give better results, because everyone will be using it regardless if they know about it or not.
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.
Neat idea! Concept is interesting and makes sense, since we need to protect second_guard_set for way longer period of time, and first_guard_set for even longer.
Third_guard_set should always be considered known by an attacker. Given that the client selects the rendezvous relay in a hidden service circuit, we can start with the assumption that the rendezvous relay is evil and all the relays from third_guard_set are known to the attacker. It's quite easy with a few evil clients and evil relays being selected as rendezvous every time, to learn about all the relays (let's assume number is 18) from third_guard_set in < 30 minutes? We need a value for THIRD_GUARD_ROTATION as low as possible and possibly a bigger value for NUM_THIRD_GUARDS.
tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev