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

[usprey]

I find this very interesting in relation to the idea for a web of trusted
exit nodes based on https://keybase.io.

Inline below.

On 12 December 2014 at 17:13, Abhishek Singh <abhishek.singh.kumar at gmail.com
> wrote:
>
> 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?
>

In regards to an independent network of trusted exit nodes, I would be
willing do disclose my status as an exit node maintainer, and my connection
to the few other exit maintainers I know personally, as we are already
traceable by IP and our nodes are listed as family members via Onionoo.


>
> 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.
>

Would a directional trust edge be useful in this context, or would it just
complicate the trustworthiness of the entire 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.
>

I suspect the graph would be quite sparse if an edge requires bidirectional
trust.
Maybe this could be turned into an advantage in the web of trusted exit
nodes scheme, e.g. only use exit nodes within N edges of specifically
trusted relays or only use exits connected to specifically trusted relays.


>
> 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?
>

Please see the thread "Idea: Public verification of exit nodes and their
maintainers - Fwd: [tor-relays] specifying your own entrance and exit
nodes".


>
> Thanks,
> Abhishek
> --
> tor-talk mailing list - tor-talk at lists.torproject.org
> To unsubscribe or change other settings go to
> https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-talk
>