Bridging and Fingerprinting: Epistemic Attacks on Route Selection
27 June 2008
The Privacy Enhinacing Technologies Symposium for 2008 is getting closer, and many of us are looking forward to a program packed with anonymous communications and traffic analysisresearch. Paul Syverson and myself (George Danezis) will be presenting our recent work on “Bridging and Fingerprinting” (PDF), a family of attacks that affect mix or onion routing based systems in which users do not know all possible relays in the network.
The starting point of our analysis is that it is getting expensive for all clients in anonymity networks (like Tor) to know all anonymizing routers, along with their cryptographic keys and addressing information. There are about a few thousands right now, that their number will hopefully go up. So would anything bad happen if each client only knows a random subset of those routers, and builds anonymous circuits using those? We show that there is a new class of attacks that might be possible.
First there is path or circuit Fingerprinting, first introduced in a work with Richard Clayton. If Alice builds paths from a small subset of routers that she knows (that is also known to the adversary), it is likely that the resulting paths and path fragments uniquely identify her. No other client would know all nodes necessary to build them. If the adversary observed a circuit fragment, they can reduce the set of possible initiators to those clients that know all relays in the fragment — a number that is smaller than all clients in the network.
Secondly there is Bridging, the novel attack proposed. The adversary observes connections or messages going through an honest anonymizing relay, and tries to infer which input correspond to which output. It must be the case that for any potential connection though the honest node the resulting path fragment should be known to at least one node in the network. Therefore the adversary can eliminate all potential routes that could not have been created by any client, and may end up `bridging’ this honest stage.
The paper is filled with theory and probabilities describing when these attacks succeed. But what do they mean for anonymous communication designers? First they are not really a direct threat for low-latency communications like Onion Routing or Tor, since the effort of collecting the data necessary to perform these attacks is outside the threat model of these systems — an adversary that can perform bridging or fingerprinting is likely to be also to otherwise break those systems. Still it is important to point out that the only information necessary to perform them is link level information, and not fine-grained traffic data necessary for timing analysis. They are still within the threat models of mix networks like mixminion.
Still this work shows that naively allowing users to know only part of the network reduces the security of anonymous communications. Non-naive strategies for achieving such architectures could include splitting the networks or learning a random subset of nodes without the adversary finding them out. The second architecture opens the way for a new type of service: a Private Information Retrieval based Directory Server. Clients can connect to it and retrieve some router records, without any observer or the service itself learning that set: this would make both Bridging and Fingerprinting much harder.