Bridging and Fingerprinting: Epistemic Attacks on Route Selection

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.

Privacy concerns amongst PAYD problems

Carmela Troncoso points to an article in “Telematics Update” about Norwich Union (NU) discontinuing their pilot pay-as-you-drive scheme. Despite them being rather coy about the exact reasons, some experts guess:

“Strategy Analytics analyst, Clare Hughes, said that prohibitive launch costs, privacy violations, patent fees, back-office data integration and difficulties in measuring costs versus benefits would inhibit the immediate widespread launch of PAYD schemes.”

There are two items of interest in this list, one obvious and one less so. The obvious one concerns privacy violations, and the perception from drivers that the insurance company and anyone who can get hold of the data can spy on their every movement. This fear is to some extent justified, which led us to propose PriPAYD, to alleviate exactly those privacy concerns. It is good to see that once more it is proved that privacy technology is an enabler, sadly the hard way for NU.

More subtlety the “back-office data integration” also relates to privacy. Requiring every data point to be transmitted to a central server, and building a gigantic silo of location data comes at a price. Processing this information to extract billing data, or even worse securing and managing access to it is an expensive business. If only PAYD providers stick to their core business model, i.e. provide insurance by the mile, type of road and time of day, they could get rid of data as soon as it is processed, reducing the costs of storage, further processing and management.

Interestingly the article points out that the future of PAYD rests in the services area: roadside assistance, emergency help, etc. This points towards an integration of the PAYD box with other components of a car, making it in fact part of a more general computing platform. Again, lets hope that this platform will be user centric, and will not be emitting a location trail to third parties.

Pay-as-you-drive “wins” German Big Brother Award

The German Big Brother award winners’ list is out, and the Technology award was given to a Pay-as-you-drive insurance company. The nomination and award statement reads:

The Big Brother Award 2007 in the “Technology” category goes to

PTV Planung Transport Verkehr AG,
represented by Dr Hans Hubschneider

for their system for individual rating of car insurances with the so-called “pay-as-you-drive” technology, i.e. a device that records routes and driving behaviour in a car and transmits these data to the insurance company. […]

It is good to see that for once Privacy Technology proposals are not lagging behind: an interdisciplinary team from K.U.Leuven has already put forward a proposal for a privacy friendly pay-as-you-drive scheme.

Carmela Troncoso, George Danezis, Eleni Kosta, Bart Preneel: Pripayd: privacy friendly pay-as-you-drive insurance. WPES 2007: 99-107