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

[Mike Perry]

George Kadianakis:
> Roger Dingledine <arma at mit.edu> writes:
> 
> > 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?
> >
> 
> Indeed.
> 
> I suggested multiple middle-guards so that the HS traffic gets load
> balanced. However, I mainly mentioned it to demonstrate the flaws of
> this scheme. I think the correct solution is having a single
> middle-guard :)
> 
> >> 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.
> >
> 
> Yes, I was mainly considering this modification just for hidden
> service traffic but it's still unclear to me whether this is a good
> idea.
> 
> If _all_ Tor clients (both clients and HSes) were to use single
> middle-guards, we would indeed have to do major modifications to the
> network's load balancing.
> 
> OTOH, just changing the HS logic might be easier for the network even
> though we would still need to perform load balancing changes similar
> to the ones you suggested.
> 
> A more important question is what's the anonymity impact of changing
> the HS circuit establishment logic. That will make circuits much
> easier to distinguish as HS-related, by their guard node, middle-guard
> or exit node. However, this is also currently possible if those actors
> carefully inspect the rates of incoming/outgoing cells, etc.
> 
> More research is required...
> 
> >> 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).
> p>
> > 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?
> >
> 
> Let's consider HS -> guard -> guard -> <middle> -> RP. That's the
> single middle-guard case:
> 
> In this case, the chance of getting your guard discovered is the same
> as picking a compromised guard: which is optimal.
> 
> That is, against a 5% adversary an HS does a coin flip (with 1/20 fail
> chance) every 9 months. An HS that hopes to be up for 5 years (that's
> around 7 coin flips) has a 0.7 probability (that's (19/20)^7) of being
> safe.
> 
> Of course, now we are entering the game where the adversary becomes
> the <middle> node, and learns your second-tier guard node. and then
> the attacker has to own the second-tier guard node, and then own the
> guard node to win. This is definitely an improvement over the current
> situation (one more box to own), but 9 months is a long time...
> 
> Maybe the optimal situation here is the static tunnel:
> 
>   HS -> guard -> guard -> guard -> RP
> 
> which increases the number of nodes such an attacker needs to
> compromise to three. However, such a setup will increase the guard
> load even more, and it might also allow other weird attacks (since the
> last node is pinned now, RPs know better which HS they are serving).

I am worried that anything involving a simple additional layer of guards
will only make things worse. 

The core problem with these multi-layered guard defenses is that you're
not addressing the two things that actually make hidden services
vulnerable:
  1. The adversary gets to force you to create many circuits through
     the Tor network by sending tons of client requests your way.
  2. They *also* get to tear down your RPs to force you to make even
     more circuits by sending DESTROY or similar teardown-inducing
     cells that for some reason are not dropped at the RP.

Even with these multilayer guard schemes, if these two properties are
not removed, it will be still very easy to determine the middle guard
because the "exit" will change rapidly based on the adversary's
connection attempts and destroy cells, allowing an adversary's exit to
be chosen very quickly. Once you get that middle guard, you just start
the coercion attacks there (warrants, seizures, or extralegal
rubber-hose attacks**), knowing that that middle guard will quickly give
up the first guard, and then off you go to similarly coerce the first
guard to find the service location.

As I've suggested before, I really really think you should also analyze
an I2P-like scheme where HSs try really hard to maintain path
persistence to their RPs for some fixed time period on the order of an
hour (but which can be parameterized and analyzed to give the expected
time for guard discovery).

In fact, with a fixed-duration for RP paths and such parameterized
analysis, we can actually set the guard node lifetime to match the
exptected time before guard node discovery.

In other words: instead of making many fresh RP circuits that can be
destroyed, you pick a few RP paths, and maintain them for all circuits
for a while, regardless of the activity that your HS sees, and also keep
retrying these paths regardless of any circuit failure/teardown you
experience. These RP paths would still have guards that last on the
order of several months (or whatever duration matches the expected Guard
discovery time from the analysis above), but the adversary would lose
the ability to move up the chain by causing your circuits to fail from
the client end or by driving a ton of activity at you.

We should also independently find ways such that clients cannot destroy
the whole 6 hop HS circuit from their end. Any destruction-inducing
messages should stop at the RP.


** Sure, having a random police force show up to take your computers is
   a pretty bad situation to be in, in many areas of the world.. But
   having the Zeta cartel or ISIL show up and threaten to behead you is
   way worse.


-- 
Mike Perry
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 801 bytes
Desc: Digital signature
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20141107/7af932b9/attachment.sig>