[tor-dev] Proposal 246: Defending Against Guard Discovery Attacks using Vanguards

[s7r]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

On 7/18/2015 12:49 AM, A. Johnson wrote:
> 
> Not having the third guards be selected by every second guard makes
> sense when you consider that the adversary may not be able to
> compromise all relays equally. That was not a consideration I had
> in mind when I argued for “completely connected” guard sets. The
> purpose of multiple guards in a given position is (i) to allow
> onion services that have unusually high load to uses the excess
> capacity of more than one relay, (ii) to lower the variance of
> relay performance, and (iii) to recover more quickly from nodes
> leaving or failing. Note how these are all related to performance.
> The drawbacks of multiple relays are all related to security, and
> they are (i) more relays gives the adversary more chances to have
> his relays selected, (ii) more relays gives the adversary more
> options and opportunities to compromise relays once they are
> observed.
> 
> The best design for security purposes would be a single relay in
> each guard "set", with the final relay expiring the fastest.
> Currently, the suggestion was to keep one relay in the first guard
> position (or whatever NumEntryGuards is), because the security
> issue there is very serious (it can observe the onion service
> directly), and also because guards are already selected to have
> somewhat higher bandwidth and stability. Hopefully (currently
> unverified) this means that they have more *excess* capacity as
> well.
> 
> If you don’t allow all second guards to connect to all third
> guards, then you have to make a performance / security tradeoff.
> For example, suppose you give each second guard its own set (or
> “bucket”) of third guards. You shouldn’t give each second guard the
> same number of guards that we had planned to have in the third
> guard set, because that only makes things worse. Now Instead of
> choosing one set (of size, say, six), you have for each second
> relay a new chance for the adversary to own one of those relays.
> There is only a benefit if you reduce the number. It makes sense to
> me to reduce that number to one, because there is no reason to
> expect the third guard to be a bottleneck before the second guard
> (unlike the first guards, which it sounds like may be the only ones
> requiring the Guard flag). You still have some of the benefit of
> reducing performance variance and improving failure recovery
> because you have multiple second guards. And you have gained the
> benefit that was Mike’s original motivation of giving the adversary
> that compromises a third guard a view of only one of the second
> guards, with the hope that maybe this one he finds difficult to
> compromise.
> 
> There is an unanswered question of what to do with multiple first
> guards. The main reason I can see not to have single second guards
> for each first guard is that the first guard is likely to have more
> excess capacity and thus not be the bottleneck for high amounts of
> onion-service traffic. Assuming that's true, then I could imagine
> having separate second-guard buckets for each first guard as well.
> However, there is a bad multiplier effect here. For example, with
> three first guards and three second guards per first guard, there
> are now *nine* relays in the second-guard position, each of which
> presents a chance for a malicious relay to be chosen.
> 
> My current thought is that the following is a better design than
> the one currently in the proposal: 1. One first guard 2. Two second
> guards per first guard (so two unless NumEntryGuards is changed) 3.
> One third guard per second guard (so two unless NumEntryGuards is
> changed) This will only perform worse than the design suggested in
> the proposal (which is one first guard, two second guards, and six
> third guards, with all guards connected to all following guards). I
> think it might not much worse, though.
> 
> And I agree with the suggestions to randomize the expiration
> times.
> 
> Best, Aaron

Agreed. The probability to run into a compromised relay will decrease
dramatically if we use fewer second and third guards. However, this
will put a penalty over performance, when talking about a popular
hidden service.

I still see the third hop (speaking from hidden service server start
point) is the weak part here. An attacker can connect to a hidden
service at his malicious relay selected as rendezvous. Before you know
it, all relays in third_guard_set are enumerated by the attacker. This
is why I think it's better to have a bigger value for NUM_THIRD_GUARDS
and a shorter period for THIRD_GUARD_ROTATION.

Here's why I think so:

Let's assume a journalist has published some documents offered by a
whistleblower regarding the abuses done by "Malicious-ISP" and made
them available via a hidden service to remain anonymous, until
authorities react to apply the law and punish "Malicious-ISP". Let's
assume "Malicious-ISP" is a multinational telecom company with
branches in many countries and good relations with other ISPs around
the world, who would cooperate with them (unfortunately this is not
exactly science fiction).

Currently a big part of Tor network's bandwidth power is concentrated
in DE,NL,FR. Many times, while browsing with Tor Browser, I had
circuits with all 3 hops in the same country. Even more times with 2
out of 3 hops in the same country.

Think that an attacker has enumerated all the relays in
third_guard_set, which we know it is trivial to do (for the sake of
argument, let's pretend we use 2 relays in third_guard_set). Now, it
all comes down to how fast can this attacker watch the IX point* of
those 2 relays. Note that the attacker does not necessarily need to
actually compromise these relays in a special way, just be able to
watch their traffic somewhere upstream. By watching the traffic
somewhere upstream, the attacker can enumerate the relays in
second_guard_set, and so on to eventually first_guard_set.

If the hidden service is unlucky and picked all hops in the same
country, its location can be deanon "before dinner". Even if the hops
are in different countries, depends from case to case, with a simple
phone call made by the attacker, the IX point* of the previous hop can
be watched and so on, until the location of the hidden service is
discovered. The attacker can establish unlimited connections to the
hidden service while watching all these points and, simple, that's it.

*IX point - by IX point I don't necessarily mean the internet exchange
points where the ISP of the relay is connected to, more like the
master gateway responsible for the traffic of the relay in question.

I know Tor does not try to protect against a Global Passive adversary,
but in this scenario there is no need for the adversary to be global -
this is the problem. The adversary just needs to watch few points on
the internet, which can be trivially done _before_ our guard rotation
period expires.

In short, we give the power which we now think a global passive
adversary has to a 'local passive adversary' or a 'rather ambitious
adversary'. What now we think can be accomplished by watching the
entire network, something we assume is _hard_ to do, will be possible
just by watching a few parts on the internet. To make it even worse,
the attacker will even have time to climb up on circuits (time offered
by our guard rotation period).

This would be harder to do and require way more effort if the
third_guard_set was bigger/more diverse and rotated much faster - but
this increases the chances of a Sybil attack. I think the success
chances of a Sybil attack are not tragic anyway, and will continue to
decrease as more 'honest' relays are added to the consensus (this is
the whole point of Tor anyway, that is why relays can be run by
volunteers, if the majority of relays aren't honest, then anonymity is
already killed).

By not choosing relays in our circuits so often and being paranoid
that our attacker is 1%, 5%, 10% or whatever (I am not saying it can't
be) we undermine the concept of onion routing and mixing with as many
hops as possible. There is a reason why we keep the 10 minutes
lifetime for a circuit - what's the point of it if after 10 minutes we
mark a circuit as dirty just to create another one with the very same
hops. This is intended to protect clients, I know, but in the context
of a hidden service we assume that _the client is the attacker_.
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.22 (MingW32)

iQEcBAEBCAAGBQJVqZmuAAoJEIN/pSyBJlsRVIEIAMcWQNKdbPmOXIUMCfADvREr
7cvHYxGxrRo26H4Av0hfGk9yuxYJh4uplfl+sf3UjGLGvFPonC9JGjvqf05RlJaA
RKwO9FwKbYjEJFmdqXxN+rWhgK2NiPbzmjvkoVHdzDtg6erMP5EyIjXz1gwNClxB
KG+CTMyiFRP16SyQ8UkwI60T/RceznTEvDxRP/w62G+txy4dgj7GhS8kT4/1Iyyy
8xsvOn0d2lH8VizZNvTT0MyVlk5W2uWBFbG1nqq6e7ger7KpqWUk7J09/wWtL5A8
fLcLYwxZoa00k7lFPaHinkQjBSXsONYVYUFxZ97QXKq2GGY8gDma3g/xcmx6B9A=
=MOSy
-----END PGP SIGNATURE-----