Thoughts on “Oft Target” (HotPETs 17)

21 July 2017

I just watched the, as ever provocative, presentation of Paul Syverson at HotPETs 2017, on targeting adversaries against Tor. I will just put down here some thoughts on onion routing, threat models, and security engineering loosely related to the talk.

Onion routing, as a concept, has committed an original sin, that has since its inception been haunting it: it dismisses the Global Passive Adversary as “unrealistic”, and attempts to provide anonymity properties against most limited “realistic” adversaries. This was necessary to achieve the performance and low cost required for anonymizing streams; it also seems logical enough to only protect against the actual adversaries that can be instantiated. Yet, with hint sight, it opens the door to all sorts of practical attacks, and also (importantly) theoretical confusion.

The Global Passive Adversary (GPA) is an abstraction, not a real thing. In security engineering, saying that the GPA is the adversary of a scheme means that the designers ensure that the schemes security properties hold even though all network communications are visible to the adversary. However, this is not the important practical implication. When a scheme is secure against the GPA it is also secure against any subset of network traffic, or any aspects of the network traffic — content or meta-data — being available to the adversary.

So while the GPA cannot exist, adversaries that have subsets of the GPA capability of course exist and are ubiquitous. Trivially, your ISP, your employer, an internet exchange, or the NSA, all can capture some traffic. The GPA model ensures a scheme is secure against them all. So while the GPA in its full capacity is not realistic, any subset of the GPA becomes realistic. The key question is: which subset is relevant? Different users would be concerned with different subsets; which exact subset the adversary has, is usually a well guarded secret; and assumptions about cost etc, are fragile.

A subtle implication of a scheme being secure against a GPA is that any aspect of the traffic can be seen by the adversary without compromising the anonymity system. That is not limited to actually capturing the traffic on the list, but also all partial function or views of the traffic. Paul presents a very interesting example of IRC traffic: even observing one user’s IRC traffic to a hidden IRC server, gives a very good idea of what the traffic will look like in all other links carrying the same IRC channel. In this case the adversary leverages knowledge of the structure of the IRC protocol (namely it relays chat traffic and mirrors it to all users in a channel), to build models of the network traffic that can be used to detect the channel.

This capability is taken into account when a system protects against the GPA. However, when a system like onion routing, only protects against “partial” or “local” adversaries, it is unclear what this implies about an adversary’s prior knowledge about the protocol, and indirect observations of load on far links. Such indirect observations were used in our early 2005 traffic analysis of tor paper. Fingerprinting websites is also another setting in which an an adversary does not have to “see” one side of an onion routing connection, and may simply model it and match the model using machine learning techniques.

So to conclude: the GPA does not exist, it is a super set of all adversaries users may care. But because we cannot know which is real, we chose to protect against the GPA. Furthermore, not only we do not what links or messages real adversaries can access, but we are also unsure about what other types of information they may extract from links that are not fully observed — through indirect observation, knowledge of the protocols, or modelling. Thus it is very likely that we will continue to see the slow trickle of attacks against onion routing systems as researchers discover more about capabilities or real adversaries, better side-channels to observe relevant information from far links, or better models for web or IRC traffic that require no or few observations.

One Response to “Thoughts on “Oft Target” (HotPETs 17)”

  1. Hi George. Thanks for the shout out, and observations. I appreciate them. Nonetheless, I generally disagree with them and in a few different ways.

    First, the realism limitations observed by myself and others of the GPA are threefold, but you only considered one of these, that it is too strong if it is observing all traffic everywhere. Another is that it is too weak if it cannot do anything active to affect traffic. Finally, there is the combination of the first two: it is unrealistic that an adversary can observe all traffic everywhere it flows and yet not even delay a single flow of traffic anywhere for a time indistinguishable from normal processing to any but itself (e.g. as in Houmansadr’s work) or ever send or insert a single message of its own into the network traffic.

    But more to the point of your post, in presenting GPA as an important theoretical construct you have instantiated an intuitively convincing but mistaken notion regarding computer security in saying, “When a scheme is secure against the GPA it is also secure against any subset of network traffic, or any aspects of the network traffic — content or meta-data — being available to the adversary.” Whether this is a cardinal sin I leave to those more saintly than myself. I discussed this and illustrated with examples in “Sleeping dogs lie in a bed of onions but wake when mixed” (which citation count indicates remains as much an instance of as a treatise on sleeping dogs). The mistake is assuming that the most secure system against the strongest adversary is also the most secure system against a weaker adversary. (I speak here at the abstract-system level and ignore other compelling points about usability, implementation, etc.) And the associated avoidable danger is that we may then choose system designs that are weaker against a more limited but more likely adversary just because they are stronger against a more powerful adversary.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

<span>%d</span> bloggers like this: