Inference attacks against trust-based onion routing: Trust degree to the rescue

Trust-based onion routing enhances anonymity protection by means of constructing onion circuits using trust-based routers. However, attackers who have the knowledge of a priori trust distributions are still capable of largely reducing the anonymity protected by trust-based circuits. The root cause is that these attackers have a high probability to guess the users who initiate trust-based circuits through the routers trusted by few other users (i.e., inference attacks). In this paper, we uncover trust degree, an essential feature of routing anonymity that is effective in defeating inference attacks but has been overlooked in the design of existing trust-based onion routing. We conduct an isolated model based analysis to understand why the trust degree is effective and how it can be used to resist inference attacks. Our major contributions are three-fold. First, we present a model to exclusively reason about inference attacks in trust-based onion routing. This model isolates the anonymity compromised by inference attacks from other attacks (e.g., correlation-like attacks), and hence derives an exclusive design space that reveals trust degree as the key feature against inference attacks. Second, to show the usefulness of our model, we design a new routing algorithm by taking into account of trust degree. Our algorithm can protect anonymity against inference attacks without sacrificing the capability against attackers' routers. Third, we compare trust-based routing algorithms with and without considering trust degree using real-world social networking datasets. These comparisons present evidence to confirm the effectiveness of trust degree in defeating inference attacks under real-world settings.