[tor-talk] Network properties of a social graph formed by relay operators

[Abhishek Singh]

Hi to all,

I wonder if a social network formed by the operators of the Tor relay nodes is
beneficial in Tor for sybil-defense. I have some questions regarding such a
mechanism. I have described the context first and it is followed by the
questions that I have in this regard.

The number of relay nodes an attacker can introduce in Tor is based on the
distinct IP addresses it can obtain. Obtaining these has become easier as there
are large number of cloud service providers willing to provide these (other
options are botnet or a resourceful adversary). Attackers have exploited this
to perform a combination of traffic analysis attack and sybil attack to
deanonymize clients' actions. Couple of examples include: 1) the attack
described by Biryukov et al. in IEEE SP 2013, and 2) the RELAY_EARLY attack
observed earlier this year.

Merits of a sybil-defense mechanism which is based on social networks has been
debated in academia and I wonder if such a mechanism will be beneficial for
Tor. In this scheme a node in the social graph represents the relay operator
and an edge between two nodes nodes represents the mutual trust between the
respective relay operators. The node can be represented by pseudonym of its
operator. A relay operator can register its edges with the Tor authorities. Tor
authorities (and clients) can analyze the social graph to detect sybil
identities and then limit the use of such identities.

Existing social network based sybil defense mechanism (such as SybilLimit)
assume a small cut between the honest region and the sybil region of the
network. Typically, these are evaluated over dense social graphs (higher
average degree) such as Facebook social graph.

Following are the questions about the feasibility of the mechanism and the
network properties of the resulting social graph:

1. Would relay operators disclose their edges to other relay operators in this
social graph to others? Or, are there privacy and other concerns which makes
such disclosures infeasible?

2. Do relay operators know each other or communicate with among themselves? It
may be the case that will be some relay operators who do not have edge to any
other relay operator. However, this technique will be helpful as long as there
is a large enough connected component in the social graph.

3. As establishing an edge in this graph is more difficult because of privacy
reasons, would it exhibit network properties similar to other social graphs
(say Facebook social graph)? Or, would it be less denser (lower avg. degree,
lower connectivity, higher path lengths) than these social graphs? If the graph
is sparse, then existing techniques may not work optimally.

4. As the social graph composed of relay operators does not exist yet, are
there any other social graphs which are close approximation for it? And, are
such social graphs available for doing further network analysis?

Thanks,
Abhishek