[tor-dev] Open topics of prop247: Defending Against Guard Discovery Attacks using Vanguards

[s7r]

George Kadianakis wrote:
> Hello,
> 
> here is some background information and summarizing of proposal 247
> "Defending Against Guard Discovery Attacks using Vanguards" for people
> who plan to work on this in the short-term future.
> 

Hello,

I have discussed in Amsterdam briefly with David about this and want to
further discuss it here where everyone can throw an eye on it. I have an
idea to use a different technique that will replace the concept of
vanguards and will only activate in case the hidden service might be
under attack - I refer here to Hidden Service Guard Discovery Attack,
which is currently fast, easy, (relatively, depending on adversary)
cheap and effective. It will also address the load balancing questions
we have in the context of using vanguards and make it much harder and
more expensive for an adversary to mount a HS Guard Discovery attack.

The main idea was discussed last year a little bit:
https://lists.torproject.org/pipermail/tor-dev/2016-January/010291.html

but its initial logic (banning a suspicious rendezvous point for a
period of time) had some issues as pointed out by arma:
https://lists.torproject.org/pipermail/tor-dev/2016-January/010292.html

So, to mitigate those, we could do something different:

Each hidden service server will keep in persistent memory the following
information and always validate a rule before selecting the path for any
rendezvous circuit:
- total number of successfully established rendezvous circuits for the
last 24 hours;
- middle probability based on consensus weight fraction for each
rendezvous relay in the list (if this value is less than 0.3, it
defaults to 0.3);
- hop 2 and 3 from the last circuit used to each rendezvous relay in the
list;
- number of successfully established rendezvous circuits per each
rendezvous relay fingerprint in the last 24 hours.

A table with the required columns would look like this:
Fingerprint | Middle Prob | Last circ hop2,hop3 | num circs last 24 hrs

A rendezvous relay is considered suspicious when the number of
successfully established circuits in the last 24 hours per a certain
rendezvous relay exceeds with more than x2 factor the number of expected
circuits having that relay as rendezvous point.

The number of expected circuits having a relay as rendezvous point is
simply computed:
n = total number of successfully established rendezvous circuits in the
last 24 hours
p = middle probability based on consensus weight fraction for a relay
that is used as a rendezvous point / 100.

Example:
n = 1000
p = 0.032 / 100 = 0.00032

1000 * 0.00032 = 0.32. Let's further call this result Q.
* If the result of this equation is < 5, we default to 5 (any relay is
allowed to have at least 5 established rendezvous circuits in the last
24 hours).
* If the result is not a whole number, we approximate to the next whole
number regardless. (For example if the result is 5.03, we treat it as 6).

The protection is triggered when the number of successfully established
rendezvous circuits per a given rendezvous relay is greater than Q * 2.

Part of an issue still remains: the attacker can grow the popularity of
the hidden service (global number of established rendezvous circuits) by
using dummy clients that build rendezvous circuits using random honest
relays in order to grow the number of expected rendezvous circuits for
his evil relay. At least this requires more resources, time and effort
from the attacker, but maybe we can better mitigate it by setting a hard
limit per fingerprint that will trigger the protection regardless the
global number of established rendezvous circuits. It's hard to come with
a right number here without relying on something dynamic (such as the
total number of established circuits) - for example we currently have a
relay with 0.8% probability in the consensus, this means that out of
1.000.000 rendezvous circuits, 8000 clients could have genuinely
selected it as rendezvous point. It is very hard to come up with a
proper estimation for how many total rendezvous circuits we expect in a
given time frame.

When a relay triggers it, instead of banning it and refusing to use it
any longer, we just use hop 2 and hop 3 from the last circuit to further
build new rendezvous circuits with this relay as rendezvous point for a
random period between 24 to 72 hours. This ensures we mitigate the issue
where the attacker DoS-es the HS by making all the relays in the
consensus suspicious by hitting the limit for every relay, one by one.

If during this period either hop 2 and hop 3 disappear from the
consensus or fail to build circuits we replace the one missing or not
being usable after one retry. Note that I suggest to only remember hop 2
and hop 3 because the Guard rotation period should be independent from this.

It is assumed that the protection is not usually triggered, only in
exceptional cases (a normal Tor client will just randomly pick
rendezvous points based on middle probability, this should not be able
to trigger the protection). In the exceptional cases where we reuse hop
2 and hop 3 of the last circuit for a 24 to 72 hours period, the load
balancing issues shouldn't be a problem given we talk about isolated cases.

One question:
Are we creating an additional risk by keeping this additional
information (hop2, hop3 of every rendezvous circuit) on the hidden
service server side? How useful can this historic information be for an
attacker that comes aware of the location of the hidden service? We
already keep this information regarding the Guard. From my point of view
this is irrelevant, given this information only becomes available after
the location of the hidden service is already discovered (which is
pretty much maximum damage).

Thanks.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 488 bytes
Desc: OpenPGP digital signature
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20170702/fb753814/attachment.sig>