Random Walk-Based Tor Circuit Building Protocol

Tor is the second generation Onion Routing, supporting the anonymous transport of TCP streams over the Internet. Tor has become the most successful public anonymity communication service in the Internet, and has more than one thousand relay nodes and thousands of users. In this paper, we investigate Tor current Circuit-Building Protocol. We propose Random Walk-based Circuit Building Protocol (RWCBP) which is based on random walk algorithm. RWCBP includes two phases: circuit construction and application message transmission. In the first phase, we propose circuit construction protocol based on random walk algorithm, and in the second phase, we propose application message transmission algorithm. In addition we also present an evaluation to the protocol according to two categories of metrics: performance and anonymity. In the evaluation of anonymity, we introduce three types of anonymous communication properties, six degrees of anonymity, and give the evaluation result against a local eavesdropper, collaborating relay nodes and the receiver. We prove RWCBP provides the better communication anonymity. In the evaluation of performance, we evaluate the circuit construction and application message transmission performance in terms of network latency, transmission loads and computational latency. Based on our analysis, RWCBP has slight and imperceptible impact on the performance of circuit construction and application message transmission.