[tor-dev] Defending against guard discovery attacks by pinning middle nodes

[George Kadianakis]

Paul Syverson <paul.syverson at 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.