[tor-dev] Sibyls: introducing AS-level sign-up rate limits, per relay caps, family-level caps

[nusenu]

Hi,

there is a strict limit on the number of relays that one can run on a
single IP address to make Sybil attacks harder, but there are no limits
on sign-up rates.

Such sign-up rate limits would prevent many of the known and simple
Sibyls of the past months and probably reduce the manual actions
required by dir auth ops to mitigate them (but I've little inside on
that part).

In the past 8 months the proposed AS sign-up rate limit thresholds (see
below) triggered on ~27 events [some-examples]. I consider all of them
to be true-positives, but 15 (vs total: >750) likely unrelated relays
signed up on the same ASes during these events.


AS-level sign-up rate limit thresholds
---------------------------------------

max new relays per 24 hours per AS per OS family: 9 (default);
value for OVH/ONLINE/Digital Ocean ASes: 14

I deduced to these threshold values by watching the past 8 months of
OrNetRadar emails while keeping false-positives at a minimum (at the
price of more false-negatives).


How does a well behaving operator (aka Brian) add more than 9 relays per
AS per day?
All relays in an effective family should be treated as "1 new relay".
(In my opinion a reason to keep the family [0] functionality and
implement prop242).

denial of service risk

To prevent trivial dos attacks where an attacker with a single IP
generates several new relay fingerprints until the entire AS is blocked
from adding new relays for a few hours these relays should come from
distinct IP addresses.


Pros:
 + automatically enforced
 + less manual action required by dir auth ops (maybe some dir auths can
commend on that.)
 + address more (and smaller) Sibyls (I assume that many small Sibyls
are currently ignored due to risk/effort trade-offs)

Cons:
 - maxmind AS-IP mapping db becomes crucial and needs to be in sync
across dir auths
 - false-positives
 - non-dir auths will not notice if an AS run into this limit unless
they publish some kind of transparency reports
 - dir auths must keep more state (not sure if they know all existing
FPs of the past already)


Feasibility

Initially the idea was to provide immediate feedback to the relay that
tries to publish its descriptor to the dir auth via the HTTP response
(an important point), but since descriptors are not uploaded to a single
central dir auth that does not work I guess. So before thinking on how
one would actually achieve that or something similar I wanted to gather
the general opinion about something like this.



single relay caps
------------------

250000 consensus weight (to prevent [1])

family-level caps
------------------

max cw fraction: 2.5% [2]

max. exit probability: 10% [3]
guard probability: 5% [4]

AS-level caps:
---------------

max cw fraction/guard/exit probability: 15% [5]

AS12876 (ONLINE SAS) and AS16276 (OVH) are already past that value, so
if you do not want to change the game for them you would have to set it
to ~20%.



[0] https://trac.torproject.org/projects/tor/ticket/6676
[1]
https://lists.torproject.org/pipermail/tor-talk/2015-December/039696.html
https://trac.torproject.org/projects/tor/ticket/17810#comment:8

[2]
https://raw.githubusercontent.com/ornetstats/stats/master/o/main_operators_by_cw.txt
[3]
https://raw.githubusercontent.com/ornetstats/stats/master/o/main_exit_operators.txt
[4]
https://raw.githubusercontent.com/ornetstats/stats/master/o/main_guard_operators.txt
[5] https://compass.torproject.org

[some-examples]
http://article.gmane.org/gmane.network.onion-routing.ornetradar/1135
http://article.gmane.org/gmane.network.onion-routing.ornetradar/1132
http://article.gmane.org/gmane.network.onion-routing.ornetradar/1100
http://article.gmane.org/gmane.network.onion-routing.ornetradar/1030
http://article.gmane.org/gmane.network.onion-routing.ornetradar/939
http://article.gmane.org/gmane.network.onion-routing.ornetradar/943
http://article.gmane.org/gmane.network.onion-routing.ornetradar/898
http://article.gmane.org/gmane.network.onion-routing.ornetradar/856
http://article.gmane.org/gmane.network.onion-routing.ornetradar/813

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