[tor-relays] Protecting Tor Circuit path selection from correlation attacks by an autonomous system

This thread continues the broader discussion of Tor Circuit path selection discussed at https://lists.torproject.org/pipermail/tor-relays/2018-August/015994.html regarding possible correlation attacks by an autonomous system.

Current measures include:

* Preventing two relays from the same /16 in IPv4 and /32 in IPv6 networks, from being in the same Tor circuit. CIDR is helpful, but is it enough?

* The MyFamily directive, this does rely on relay operators being honest and we shouldn't rely on this as the sole indicator.

* Others things that I am not aware of?

Some measures worth considering include:

* Preventing two relays in the same ASN from being in a circuit.

* Maybe prevent two relays in the same ASN from being Guard and Exit, excluding the middle relay from this calculation.

* Bridges could be a challenge when implementing this, although it's not impossible.

* Looking at relays with same/similar names, heuristics maybe? It's really guesswork but hey it might work.

* Looking at relays with same/similar contact info

* Looking at relays in the same geographic regions and avoiding them

* Relays with the same non-standard ports - excluding 9001, 9030, 80, 443 (anything else that's super common?)

* On device models looking at the above data to make decisions of which relays are most likely run by the same entity, use machine learning to make an informed decision based on all factors maybe?

Papers worth reviewing:

* AS-awareness in Tor Path Selection https://www.freehaven.net/anonbib/cache/DBLP:conf/ccs/EdmanS09.pdf

* Users Get Routed: Traffic Correlation on Tor by Realistic Adversaries https://www.ohmygodel.com/publications/usersrouted-ccs13.pdf

* Moving Tor Circuits Towards Multiple-Path: Anonymity and Performance Considerations https://pdfs.semanticscholar.org/aa94/7dd4762bd0f6531bacfeac9d29ef1e1d4cd6.pdf

* Avoiding The Man on the Wire: Improving Tor’s Security with Trust-Aware Path Selection https://www.nrl.navy.mil/itd/chacs/sites/www.nrl.navy.mil.itd.chacs/files/pdfs/16-1231-4380.pdf

Outside the scope:

* In AS-es where Virtual Machines are sold, and Physical Machines are not. It's quite possible that the provider may steal relay keys. Little research exists where you could successfully protect against such an adversary who isn't playing nice. Legislation (For example, GDPR) in the EU exists where such activity may violate local laws. This may or may not be enough. Certainly not against a government actor, but against an AS doing it per their only devices maybe.

* An AS hosting a Tor relay who logs or watches network traffic will always be able to learn something about the circuit, but perhaps we can prevent them from learning everything about the circuit most of the time.

Everyone on the list has a had very insightful and helpful thoughts on this discussion so far and I'm looking forward to getting more discussion of the broader issue.

Cordially,

Nathaniel Suchy