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

[Roger Dingledine]

On Sat, Sep 13, 2014 at 04:07:13PM +0300, George Kadianakis wrote:
> 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.

Yeah, I think having so many middle-guards will undermine your goal of
rarely picking a bad middle-guard.

Incidentally, it looks like the math is about the same for the case
where you pick only one middle-guard but you rotate it every 1/3 months?

> 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.

Seems like in this case you'd want to pick your middle hop the same way
you picked your guard hop.

If approximately no Tor users (x=0%) picked their paths this way, then
the current load balancing should still work fine.

If all Tor users (x=100%) picked their paths this way, we would basically
push out all middle (non-guard non-exit) relays, and we should double
up the load that our load balancing algorithms assign to guards.

Were you thinking of doing this modification for just hidden service
users? If so, and assuming we could measure (an approximation of) how
many total Tor circuits, and how many total Tor bytes, are hidden service
related, then it seems like we could weight the shift from middle to
guard load according to this value x.

> 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).

Don't get distracted by the fact that some other fields can get great
security results. :)

>    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?

What does HS -> guard -> guard -> <middle> -> RP look like, where
the first two hops are rotated every 9 months?

--Roger