SGor: Trust graph based onion routing

Ang Chen, Peng Zhou, Xiapu Luo, Ang Chen 0001, Rocky K. C. ChangComputer Networks 2013 · DOI

TL;DR

This paper introduces SGor, a novel trust graph-based onion routing protocol that enhances anonymity by addressing key limitations in existing trust models. SGor leverages group trust from mutual friends to verify trust assignments and employs an adaptive trust propagation algorithm to derive global trust, effectively mitigating inference attacks and improving router selection.

What Problem Does This Paper Address?

Onion routing protocols, like Tor, are designed to provide anonymity by encrypting traffic in layers and routing it through multiple nodes. However, these systems are vulnerable to correlation-like attacks, where adversaries can compromise a significant number of routers to deanonymize users. While trust-based onion routing has emerged as a defense, existing approaches suffer from two main issues:

  1. Incorrect Trust: Users might assign trust to malicious routers based on incomplete or inaccurate local knowledge, and there's no robust mechanism to correct these errors.
  2. Biased Trust Distribution: Since users only know a fraction of the network, their trust assignments are often biased, creating predictable patterns that adversaries can exploit for inference attacks (e.g., guessing the origin of a circuit).

SGor aims to overcome these limitations by building a more robust and less biased trust system on top of onion routing.

Methods

SGor introduces three key novelties:

  • Trust Graph: It utilizes a trust graph, representing relationships between users and router owners, as the foundation for trust assessment.
  • Group Trust: SGor aggregates "group trust" from mutual friends to verify the correctness of individual trust assignments. This means a user's trust in another node is strengthened if many of their mutual friends also trust that node, making it harder for a single incorrect trust assignment to go unnoticed.
  • Adaptive Trust Propagation (Global Trust): SGor employs an adaptive algorithm to derive "global trust" from the trust graph. This algorithm intelligently propagates trust, limiting the influence of potentially compromised nodes and guiding users to discover and trust more honest routers, thereby reducing trust distribution bias. This is achieved by making trust propagation capacity proportional to the group trust a user has in their friends.
  • Decentralized Architecture: The entire system operates in a fully decentralized manner, meaning no central server is required. This enhances privacy by preventing the leakage of a priori trust relationships and improves scalability.

Datasets

SGor was evaluated using two real-world social interaction graph datasets:

  • New Orleans Dataset [19]: Collected from Facebook interactions, containing 46,952 nodes and 876,993 trust edges.
  • Anonymous Dataset [20]: Collected from another anonymous Facebook regional network, containing 431,995 nodes and 781,862 trust edges.

These datasets were preprocessed to remove nodes with low degrees and self-linked edges.

Key Insights and Ideas

  • Collective Wisdom for Trust: The core idea is that the collective trust of a group of honest individuals is more reliable than the trust of a single person. SGor formalizes this through "group trust."
  • Mitigating Inference Attacks via Global Trust: By deriving global trust, SGor allows users to trust routers they don't directly know, reducing the bias in trust distributions. This makes it much harder for adversaries to infer the origin of an onion circuit by observing a few routers.
  • Decentralization is Key for Privacy and Scalability: Avoiding a central server is crucial for preventing trust relationship leakage and for the system to scale effectively with large trust networks.
  • Trade-off Between Evasion and Inference Defense: The paper highlights that parameters like the group trust threshold ($\Phi_h$) and trust propagation length ($L_i$) involve a trade-off. Higher thresholds and shorter propagation lengths are better for evading adversaries, while lower thresholds and longer propagation lengths are better for defeating inference attacks. SGor aims to find a balance.

Key Results

  • Improved Evasion of Malicious Routers: SGor significantly outperforms traditional trust-based onion routing in evading adversaries' routers. With parameters $\Phi_h=2$ and $L_i=1$, SGor showed over a 10x improvement, and with $\Phi_h=4$, this improvement reached around 1000x.
  • Enhanced Defense Against Inference Attacks: SGor demonstrates a better capability of defeating inference attacks by increasing the number of users who can select honest routers. The results show that SGor, especially with larger $L_i$, leads to a higher $Deg(v_j)$ (number of users selecting a router) compared to trust-based onion routing.
  • Superior Anonymity: When compared to Pisces (another global trust-based scheme), SGor achieves a smaller deanonymization expectation ($E_i$), indicating better overall anonymity protection.
  • Low Overheads: SGor introduces minimal storage overhead (users store only their local trust edges) and communication overheads (largely dependent on $L_i$, which is kept small). Additional traffic is also found to be manageable.
  • Negligible Leakage of Trust Relationships: The fraction of leaked trust relationships during group trust calculation was found to be negligible (less than 0.0002).

Limitations and Future Work

  • Trust Graph Completeness: The effectiveness of SGor relies on the availability of sufficient robust trust paths to form group trust. If the trust graph is sparse or incomplete, SGor might degenerate into traditional trust-based onion routing. Future work could explore ways to address incomplete graphs, potentially through centralized services, though this might impact scalability.
  • Adversary Distribution: The current evaluation assumes independent and identically distributed adversaries. Future work should investigate SGor's effectiveness against more realistic adversary distributions, potentially derived from real-world datasets.
  • Dynamic Trust Networks: SGor assumes a stable trust graph. The dynamics of users joining and leaving networks, and frequent online/offline behavior, could lead to incomplete graphs. The authors suggest running user-agents in uninterrupted services like virtual machines.
  • Social Engineering Attacks: SGor, like other trust-based systems, is vulnerable to social engineering attacks where adversaries might trick honest users into assigning trust. While group trust and adaptive propagation help mitigate this, it remains a weakness.
  • Customized Trust Networks: The authors suggest building customized trust networks where users and router owners can evaluate each other independently to create more robust trust graphs.

Summary updated

BibTeX
@article{chen2013sgor,
  author = {Ang Chen and Peng Zhou and Xiapu Luo and Ang Chen and Rocky K. C. Chang},
  title = {{SGor: Trust graph based onion routing}},
  journal = {Computer Networks},
  year = {2013},
  doi = {10.1016/j.comnet.2013.08.005},
}
Figure