DPSelect: A Differential Privacy Based Guard Relay Selection Algorithm for Tor

Abstract

Recent research has shown that Tor is vulnerable to attacks that manipulate inter-domain routing to compromise user privacy. Proposed solutions like Counter-Raptor [6] attempt to ameliorate this issue by favoring Tor entry relays that have high resilience to these attacks. However, because these defenses bias Tor path selection on the identity of the client, they invariably leak probabilistic information about client identities. Thus, while approaches like Counter-Raptor decrease Tor clients' vulnerability to inter-domain routing attacks, they increase Tor clients' susceptibility to statistical fingerprinting attacks. As a result, a malicious adversary could observe multiple guard relays selections in order to uniquely identify the source of a given Tor connection. Counter-Raptor, in the worst-case, results in a 22.9% decrease in the Shannon entropy after 1 guard relay selection. Further amongst the top 93 Tor ASes, the Shannon entropy in the worst-case can decrease by 81.8% after 15 guard selections as well. This dramatic decrease can be used to locate and deanonymize Tor users. In this work, we identify a novel means to quantify privacy leakage in existing guard selection algorithms in Tor. We also propose modifications to some of these algorithms, specifically Counter-Raptor, in order to minimize client information leakage. By utilizing Max-Divergence as a metric, we show that the probabilistic privacy loss introduced by different guard selection algorithms can be guaranteed to be within strict bounds. Thorough a Monte-Carlo sampling based method for stochastic optimization, we further show that an $\epsilon$-differentially private algorithm can retain many of the benefits of Counter-Raptor while simultaneously preventing privacy loss over time. Compared to Counter Raptor, our approach achieved an 83% decrease in Max-Divergence in guard selection, a 459% increase in worst-case Shannon entropy after 15 guard selections, an added ability to track privacy over time, and similar performance characteristics in a simulated Tor network.