Paul Syverson paul.syverson@nrl.navy.mil writes:
On Fri, Jul 11, 2014 at 08:31:05AM -0400, Ian Goldberg wrote:
On Fri, Jul 11, 2014 at 01:44:36PM +0300, George Kadianakis wrote:
Hey Nick,
this mail is about the schemes we were discussing during the dev meeting on how to protect HSes against guard discovery attacks (#9001).
I think we have some ideas on how to offer better protection against such attacks, mainly by keeping our middle nodes more static than we do currently.
For example, we could keep our middle nodes for 3-4 days instead of choosing new ones for every circuit. As Roger has suggested, maybe we don't even need to write the static middle nodes on the state file, just use new ones if Tor has restarted.
Keeping middle nodes around for longer will make those attacks much slower (it restricts them to one attack attempt every 3-4 days), but are there any serious negative implications?
For example, if you were unlucky and you picked an evil middle node, and you keep it for 3-4 days, that middle node will always see your traffic coming through your guard (assuming a single guard per client). If we assume you use a non-popular guard node (with only a few clients using it), the middle guard might be able to think "Ah, the circuit that comes from that guard node is always user X" making your circuits a bit linkable from the PoV of your middle node.
And similarly at the exit node: the exit will now know that circuits coming from the same middle are more likely to be the same client. That's a little more worrying to me than the above.
Right. Lasse and I suggested and explored the idea of layered guards when we introduced guards. There are lots of possibilities here. You can have a set of midguards per guard. Don't remember if it made it into the paper, but when Roger, Nick, Aaron, and I did the downhill paths paper we also talked about having a rotation rate for choice of middle guards that was faster than for guards but not simply a new weighted-random midnode for each circuit. Gotta run.
I've been trying to understand how useful layered guards would be in the current Tor network purely from a Sybil attack perspective (even if we disregard the attacks that me and Ian mentioned previously in this thread).
For example, let's assume a simplified 5% adversary. That is, an adversary whose relays have 5% chance of getting picked everytime we sample a relay for a Tor circuit [0]. This allows us to model relay sampling as a coin toss with Pr[head] = 0.95 and Pr[tail] = 0.05. We are going to toss the coin a few times and hope we never get tail.
Also, let's assume that HS traffic correlation is easy if you control one of the relays of the HS circuit. I believe this is reasonable to assume, since the attacker can force the HS to send/receive traffic at any point [1].
And here is a server-side HS circuit: HS -> guard -> middle -> exit -> RP
== Guard compromise attacks ==
So, let's start with guard compromise attacks (worse than guard discovery): Everytime we pick a new guard node, we have 0.05 of failing. Since #12206, we use a single guard node and we pick a new one every 2-3 months. This means that after a year (6 coin tosses), the probability of getting owned (guard compromise) is:
Pr[at least one tail] = 1 - Pr[all heads] = 1 - 0.95^6 = 0.26~
This means that there is 1/4 chance that you will get owned after a year. This is not a particularly encouraging probability, but it's not the main point of this post and it's a powerful attack that lasts for a year, so let's just accept it.
== Guard discovery attacks ==
Now, let's try to understand how much security layered guards can offer against guard discovery attacks.
So let's say that along with our guard, we also pick 6 second-tier guards (middle nodes) that also get pinned for 2-3 months. This makes us look like this:
-> middle1 -> middle2 HS -> guard -> middle3 -> <exit> -> RP -> middle4 -> middle5 -> middle6
(where the <exit> is chosen from the set of all relays (not static).)
Since guard picks are independent, the probability of one of your 6 middles being compromised is the same probability as the one from the section above: of your main guard getting owned after 6 rotations. This means that every 2-3 months, your guard has 1/4 chance of getting discovered [2]. This means that after a few rotations your guard is guaranteed to be leaked.
Some thoughts:
a) To reduce the ownage probabilities we could pick a single middle node instead of 6. That will greatly improve guard discovery probabilities, and make us look like this:
HS -> guard -> middle -> <exit> -> RP (where <exit> is chosen from the set of all relays)
However, that will definitely degrade HS performance. I'm not sure if Tor relays are able to handle all that concentrated HS traffic. Specifically, the guards/middles that get picked by popular HSes will get flooded with traffic that is never accounted for in Tor's load balancing equations (since HS traffic is not counted) and they will get hammered both by HS traffic and regular Tor traffic.
b) To reduce the ownage probabilities we need to extend the guard lifetime period. If we switched guards every 9 months, instead of every 2 months, we would have much lower chance of getting compromised in the long run. Actually, the probabilities would even look encouraging (but still nowhere near cryptographic quality).
However, if guard discovery attacks are still possible, having guards last for 9 months gives the attacker a much larger window for attacks. Maybe we need to solve guard discovery attacks and increase the lifetime period at the same time?
c) To reduce the ownage probabilities we need the Tor network to grow, so that it's harder for adversaries to reach high guard probabilities. The good thing with this is that we don't need to grow Exit nodes, since middle/guard nodes are also sufficient for HS purposes.
Anyway, I believe that guard discovery attacks are very serious and I'm trying to think of a solution or improvement that could be incorporated in the new HS spec (rend-spec-ng.txt) so that it gets developed "soon".
[0]: This is a powerful but realistic adversary. In compass, you can see many relays with guard probability between 1.2% to 0.5%. If the adversary plants 5-10 such relays, she can get to 5% total guard probability. If the adversary controls a few ISPs, the probability can increase further.
[1]: The 'Trawling for Tor Hidden Services' paper successfully launches this guard discovery attack. See section 'VII. REVEALING GUARD NODES OF HIDDEN SERVICES'.
[2]: Of course, you can reduce the attack probability by only picking 2 or 3 middle nodes per rotation period, but that will only make you last for another rotation period or two.