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

[George Kadianakis]

"A. Johnson" <aaron.m.johnson at nrl.navy.mil> writes:

>> 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 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.
>
> I agree that it would be an improvement to remove the ability of an
> adversary to force the selection of new paths to the RP.  For security
> purposes, it seems the same as adding additional layers of “guards”
> that have shorter expiration times. And that does suggest one benefit
> of *shorter* lifetimes for secondary or tertiary guards: you may make
> expiration faster than an adversary can begin surveillance. The trick
> is to make the expiration time just under the speed of
> surveillance. If expiration is too fast, the adversary can just as
> well wait for you to choose one of his relays.
>
> Suppose the third hop from the HS was changed every hour, and the
> adversary controlled 1% of all consensus weight. Then it would take a
> little over 4 days in expectation to choose an adversarial relay and
> thereby expose the second hop. Assuming the second and first hops
> rotate slower than surveillance speed, the adversary can at that point
> move up the chain via surveillance to identify the HS. If the HS can
> hold onto that third hop for as long as a day, then it would take a
> little over 14 weeks in expectation for an adversarial relay to be
> selected.
>
> These number don’t seem great to me, but they do seem like an improvement.
>

Good thoughts!

It seems to me that we want to defend against (at least) two different
attacks here:

Sybil attack:

  We want to defend against a Sybil attack where attackers sign up
  relays to the network so that they eventually become the guards (or
  second/third guards) of HS circuits. The suggested way to deal with
  this attack is to rotate guards slowly.
  
  We currently rotate guards every 2-3 months, but we are considering
  changing this to 9 months or so according to proposal 236

Coercion attack:

  However, we also want to defend against "coercion" attacks, where
  attackers can compromise (pwn/seize/etc.) guards of HS circuits. A
  way to solve this, assuming that compromising Tor relays takes
  non-trivial time, would be to rotate guards fast. The idea is that
  by the time the attacker has compromised a guard, the HS has already
  rotated that guard and moved to another one.
  
  Let's say that compromising a relay takes 5 days. Then a good
  strategy would be to rotate every guard layer every 5 days.

The obvious problem here is that if you assume an attacker that can
pull off both attacks, the proposed solutions are incompatible. A
system that defends against one attack is left open to the other.

And I guess that's why the last few posts are suggesting to combine
the two defences. They suggest having long-term guards (anti-sybil)
near the HS, and short-term guards (anti-coercion) near the RP.

Ignoring all sorts of load balancing and bandwidth issues, let's
consider the following circuit:

    HS -> 3 months guard_1 -> 3 months guard_2 -> 5 days guard_3 -> RP

and see how an adversary would attack it:

The adversary starts off as being the RP, and hence learns the
identity of guard_3 [0].

To learn the next hop, and since it doesn't have enough time to do a
coercion attack, it has to do a sybil attack. A 5% adversary (like
CERT) starts getting over 50% probability of becoming your next hop
after about 13 rotations. So after about 2 months (13*5 days), the
adversary will become your guard_3, and hence learn the identity of
guard_2.

>From that point, he just needs to walk the coercion chain for two
hops. So basically, after 5 days he compromises guard_2 and then after
5 more days he compromises guard_1. Total time to deanonymization is
75 days. Not good. FWIW, using the same model, the time to
deanonymization with the current HS circuits is just 5 days, that is a
single coercion attack.

Some notes:

* It seems that the only reason it took 75 days to the adversary is
  because the first hop took him 65 days to crack: Sybil attacks are
  slow in this case.

  Unfortunately, it doesn't really make sense to add two '5 day
  guards' in a circuit, since a Sybil adversary has equal chances to
  pop at the guard nearest to the HS.

* While more hops are useless for Sybil attacks, they actually help
  against coercion attacks. Unfortunately, they only add 5 days per
  extra hop to the time to deanonymization.

* It seems that coercion attacks are noisy. At least in this case,
  relays got seized (why?) and people got notified that something was
  going on. It would be nice if we could make coercion attacks even
  more noisy, so that adversaries can't do them without tipping off
  the whole network.

* The more I think about this problem, the more I realize that our
  solutions are quite hacky. Maybe guards are not the right layer to
  fix this problem, and we should try to fix the guard discovery
  problem in circuit establishment as Mike has been suggesting?
  Unfortunately, the virtual circuits idea seems hard to analyze and
  do securely.

[0]: It seems to me that in all low-latency anonymity schemes based on
     rendezvous, the adversary is able to trivially learn the first
     hop of a chain that eventually leads to the HS.