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

[s7r]

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

Hi,

Your points are correct and I cannot agree more. I don't think that an
adversary running his own relays is less of a threat, just that it
depends on the adversary and the context. Running his own relays might
be the more expensive and time consuming way, as opposite to the one
described by me. After all, having the majority of relays 'honest' is
key to the network's strength, it's basically a fundamental limitation
of the technology itself. We can't go too paranoid about the number of
evil relays and only choose 5 relays from a total of ~6600 (even for a
limited period of time [guard rotation period]) in the circuits of a
hidden service. If too many relays are compromised, this raises the
question if it's safe to still use Tor or not.

If we are talking about legal authorities being the targeted observer,
they have simplified procedure for information exchange especially
within the EU or maybe even US-EU, which means some target IP
addresses can be monitored for incoming and outgoing traffic with a
simple fax letter. A 6 hours guard rotation period is more than
sufficient.

While I see both Sybil attack and targeted observer attack as big
threats, I don't think we can say one is less important than the other.
While a Sybil attack would require more time and money to run evil
relays (costs grow proportional with Tor network's grow), a targeted
observer attack would just need proper motivation. Also, forcing an
adversary to do a Sybil attack and run his own evil relays will
increase the network capacity (making Sybil attacks more expensive and
with lower probabilistic rates for future attackers targeting other
users) as well as help the non-targeted users by relaying their
anonymous traffic. The targeted observer attack does not offer any
benefit at all.

We need to put these things in balance somehow and find the correct
balance between lowering the chances of a successful Sybil attack and
also making an adversary to have to watch as many parts of the
internet as possible, to make it harder/ more expensive/ not worth it
/ maybe even impossible. You are right, probably I am seeing it wrong
and the threat of a Sybil attack is more realistic. Let's meet
somewhere half way.

That's why I only made reference to third_guard_set number of relays
and their rotation period and didn't say to increase the relays in
second_guard_set or rotate the second guards faster. We can implement
the Sybil defense at second_guard_set level and of course
first_guard_set (already implemented). This way, we have a little from
both of our goals (win, win). 'Better is the enemy of perfect' doesn't
apply in such a complex structure, with so many possible threats and
attacks, and if we can have some gains from both points it's a step
forward.

third_guard_set is always assumed to be known to the attacker - it can
be trivially discovered just by running one evil client and one or two
evil relays to act as rendezvous points. If I recall correctly, an
attacker won't even need special flags, uptime or any kind of history
in the consensus for the relay(s) so enumerating all relays in
third_guard_set is very cheap and simple. You can even do it from a
laptop with a decent connection in < 30 minutes.

I just don't want to leave an equation too easy to solve for an
attacker. If we can have protection for both (Sybil protection at
second_guard_set and targeted observer protection and third_guard_set)
I would prefer to have them both.

On 7/18/2015 7:19 AM, Aaron Johnson wrote:
> I agree with most of what you said regarding the threat of a
> targeted observer. What I disagree with is that an adversary
> running his own relays is less of a threat. Running relays is
> trivial, and running 5% of the guards is fairly cheap (I estimate
> ~$3000/month (please ask for details)). If you increase the number
> of third guards to, say, ten, with average expiration times of,
> say, 6 hours, then after only 24 hours an adversary with 5% of the
> bandwidth has an 87% chance of compromising at least one third
> guard. By reducing the number of third guards to 2 and increasing
> the expiration time to an average of 24 hours, then it takes 20
> days until 87% chance of compromise is reached.
> 
> Observing the network traffic of third parties is, it seems to me,
> actually much more difficult and excludes most adversaries except
> legal authorities. And legal authorities often do have to follow
> some legal procedures to observe network traffic, especially if it
> is being done between different legal jurisdictions.
> 
> But ultimately the point of the quickly-rotating third guards is
> only to *force* the adversary to invest resources into running
> malicious relays. That is a different type of attack than just
> traffic observation, and requiring it may stymie some adversaries
> who don’t have those skills or processes in place. So more and
> more-quickly rotating third guards would serve that purpose just as
> well. If the consensus is that an adversary that can observe
> arbitrary third-party traffic within hours is more of a concern
> than an adversary that can run 1-5% of the vanguards, then very
> short-lived third guards would be a reasonable solution, in my
> opinion. I would not be part of that consensus, but figuring out
> the speed and size of the adversaries we care about is
> unfortunately educated guessing at this point.
> 
> Best, Aaron
> 
> 
>> On Jul 17, 2015, at 8:11 PM, s7r <s7r at sky-ip.org> wrote:
>> 
>> Signed PGP part On 7/18/2015 12:49 AM, A. Johnson wrote:
>>> 
>>> Not having the thir

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

iQEcBAEBCAAGBQJVqvSoAAoJEIN/pSyBJlsRxWIIAM/qmn32bbm5zAXJpXAfgr1i
chjARDmcmsdm6yEa7tq7rpxL/Z9TEOgO33ssOScHdGb0NNRp123H4qWQyHAsCsoE
jUrhK/u+rcN05/oL5TeP0H4FsFblJAwKviWQMbXSIWE2Cc+xKhpmngOhRdEra1Sl
6lJKmHQzM0R50WD5GRlMg6T+gZ9KdkqfSdJNbdZzFpH6hE0XMOpfIO7b79uGSuLg
kKeiyOILF5uk24wv+L5R0oyIrilutYvddSRd2iKAPWgreYybEJDuDIU+w6l2XjMI
KQcITym0xsbU1ZZLq5DG8H1z/kTPsNJh9fxG6rQ9UQAttf9Y6uxtI5pdDlRjFYk=
=tbgl
-----END PGP SIGNATURE-----