Today morning at PETS 2009, the paper on “Physical Layer Attacks on Unlinkability in Wireless LANs” was presented. The idea is that despite all anonymization techniques at the logical layers, though IP address modulation, the physical location of the IEEE802.11 transmitters can be localised, and thus unlinkable packets emanating from it linked together.

The approach used to do this, uses signal strength and triangulation techniques, with a machine learning twist, to cluster together emissions and link them to the same transmitter. A set of countermeasures is also presented, where transmitters modulate their signal strength to foil this clustering.

The attacker model was restricted to using commodity hardware, so physical device fingerprinting attacks were not considered.

In the last year, we have been developping a set of systematic techniques to analyse anonymity systems, to perform traffic analysis. These cast the problem of traffic analysis as a Bayesian inference problem, where the adversay observes some traces, according to a threat model, and then has to infer the hidden state of the system, that is equivalent to tracing who is talking to whom.

So far we have looked at the analysis of mix networks, the analysis of Crowds, and a Bayesian approach to long term intersection attacks. The papers describing each of these are available online:

In the 1950’s Lambros D. Callimahos built the Zendian Problem [zip] as an integrated exercise in traffic analysis, cryptanalysis, and communications intelligence operations. The state of cryptology today has moved on, beyond the point where an analyst can rely on plaintext to drive operations. The state of traffic analysis techniques, and the availability of more computing power, requires a new generation of exercises to sharpen the tools and minds of those in the field.

Steven Murdoch and myself have been developing, on (and mostly) off, over the past year an exercise in traffic analysis, and in particular the long term disclosure attacks. The exercise was first presented and used at the Brno FIDIS summer school, and we are now using it as part of an industrial training curriculum.

The exercise consists of an anonymized trace of communications, that were mediated by an anonymity system, that a group of people used to message each other. The message traces are synthetic,  but generated based on a real-world social network. Users have favorite communication partners, talk more or less according to the type of relationship and time of day, and may reply to each others messages.

The goal is to apply any disclosure attacks, and de-anonymize and trace as many messages as possible. An oracle is provided that outputs the success rate, and the instructor’s pack includes the original messages as well as the scripts used to simulate the messaging behaviours and the anonymization layer. We tried to keep the exercise and success rates realistic, so do not expect to ever get 100% — significantly better than random is already quite good.

The richness of the messaging behaviour is designed to stress the most advanced statistical disclosure techniques, that make use of social network, replies, and perfect matchings. The literature on statistical disclosure can be found on the exercise page, and an example implementing the simple SDA is provided in the bundle. The family of Disclosure Attacks (devised by Kesdoganet al.) might also be modified and applied to the exercise. Our new attack soon to be presented at PET, using Bayesian Inference, could also be applied:

A couple of caveats: this is an exercise, to help people learn about long term traffic analysis attacks, and allow them to implement the attacks on a rich, but safe, dataset. The objective is to learn.

  1. It is not a benchmarking tool between attacks. We are not sure that the traffic patterns are typical enough to make sure that when an attack performs better in the setting of our exercise it would perform better on real data.
  2. It is also not a competition or test. We publish all of the hidden state for instructors, and the random number generator used was not cryptographically strong. The point is not who can get the highest score, but the quality of understanding of the attacks.

Caveats aside, I do hope that the exercise opens a discussion about how we can exchange training or live datasets, formats for evaluating traffic analysis attacks, and a level of standardisation to the interfaces of attack scripts. These will probably be topics for debate over the Privacy Enhancing Technologies Symposium 2009, next week.

Both myself and Steven would be very interested to hear your experiences with the exercise, either if you take it yourself, or give it to a class as an instructor. If you extend the exercise, or generate particular bundles of anonymized datasets, we would also be happy to host them.

The ACLU and the BBC have today posted the first memo, dated 1 August 2002, authorising the use of torture by the CIA against Abu Zubaydah, described as “one of the highest ranking members ofAl Qaeda”. Interestingly one of the enablers for passing into an “increased pressure phase” (you have to love these euphemisms) comes down to traffic analysis, as this passage suggests:

Snippet mentioning suspicious chatter

According to the document “intelligence indicates that there is currently a level of `chatter’ equal to that which preceded the September 11 attacks”. It is not comforting at all to know that such automatic processing, as well as subjective interpretation, can be used to start torturing people, in the absence of any other concrete evidence.

Update: Steven Murdoch points to the Washington Post article clarifying the role of the Abu Zubaida as being nowhere near as important as initially assumed. The article states that “Abu Zubaida was not even an official member of al-Qaeda”. Worth reading in its entirety.

It is quite interesting that this year’s NDSS, has a special session on “Traffic Protection”. It contains two papers, one about attack (or stepping stone detection) and one on defense (or traffic analysis resistance).

The first paper from Anmir Houmansadr, Negar Kiyavash and Nikita Borisov proposes an active watermarking scheme for network flows, based on spread spectrum techniques, called RAINBOW.It seems like solid work, particularly when it comes to detectability. The authors use a statistical test to determine the covertness of the scheme, that might actually not be optimal for detection. I foresee that covertness would be the property to look at in order to break the scheme or improve on it. The full reference is:

The second paper (presented as a write) is about Traffic Morphing, i.e. how to make encrypted traffic meta-data look like traffic of another class. Unlike anonymity solutions the aim is not to make all traffic look the same, but instead to fool a classifier. This is an interesting approach, but may open up an arms a race between traffic analysis resistance solutions, and those who build better and better classifiers. The full reference is:

(No pdf is yet available for the second work.)

I am currently at NDSS 2009, to present our recent work with Prateek Mittal on SybilInfer [pdf], an inference engine to detect sybil attacks in social networks. Interestingly Carrie Gates is also presenting (right now) a traffic analysis paper on detecting coordinated scans. It would be greatly improved if cast in an inference framework but the techniques and assumptions are still quite interesting.

Coordinated Scan Detection

Carrie Gates, CA Labs
Coordinated attacks distribute the tasks involved in an attack amongst multiple sources. We present a detection algorithm that is based on an adversary model of desired information gain and employs heuristics similar to those for solving the set covering problem. A detector is developed and tested against coordinated horizontal and strobe scanning activity. Experimental results demonstrate an acceptably low false positive rate, and we discuss the conditions required to maximize the detection rate.

Strangely I cannot find a copy of it on-line…

I am currently at ACM CCS 2008 listening to the talk on “Dependent link padding algorithms for low latency anonymity systems” by Wei Wang, Mehul Motani and Vikram Srinivasan (the pdf does not seem to be on-line yet). They propose a scheme to provably defeat all packet matching attacks against low-latency anonymity systems, by introducing the minimal amount of cover traffic. The results are theoretically well founded, and of great practical importance since they show how one could provide strong anonymity without “constant rate” padding (as it is often assumed necessary.)

Shishir Nagaraja has posted on his research web-site his latest work on “The Economics of Covert Community Detection and Hiding“. This extends the line of research myself and Bettina Wittneben started with our paper “The Economics of Mass Surveillance and the Questionable Value of Anonymous Communications“, where we showed that anonymous communications themselves are not preventing target selection. Shishir’s work shows that simple covertness strategies can instead make the job of the surveillance analyst much harder.

The full abstract reads:

“We present a model of surveillance based on the detection of community structure in social networks. We examine the extent of network topology information an adver sary is required to gather in order to obtain high quality intelligence about community membership. We show that selective surveillance strategies can improve the adversary’s resource efficiency. However, the use of counter-surveillance defence strategies can signifficantly reduce the adversary’s capability. We analyze two adversary models drawn from contemporary computer security literature, and explore the dynamics of community detection and hiding in these settings. Our results show that in the absence of counter-surveillance moves, placing a mere 8% of the network under surveillance can uncover the community membership of as much as 50% of the network. Uncovering all community information with targeted selection requires half the surveillance budget where parties use anonymous channels to communicate. Finally, the most determined covert community can escape detection by adopting decentralized counter-surveillance techniques even while facing an adversary with full topology knowledge – by investing in a small counter-surveillance budget, a rebel group can induce a steep increase in the false negative ratio.”

Luke O’Connor has uploaded on the cryptology eprint archive a manuscript providing analytical bounds for the Hitting Set Attack. The paper entitled “Entropy Bounds for Traffic Confirmation” [PDF] demonstrates that after O(m log N) messages from Alice (where N is the number of all receivers and m the number of friends of Alice) the hitting set attack failure probability becomes negligible.

Highly recomended reading!

An anonymous contributor, The23rd Raccoon, sent a few days a go a very insightful post to the or-dev lists entitled “How I Learned to Stop Ph34ring NSA and Love the Base Rate Fallacy“. The key point is that tracing anonymous communications is an identification exercise: the adversary has to detect the single correct target amongst the noise of incorrect identities. Therefore reporting simply false positives and false negative rates is misleading, since even moderate false positives will lead to the vast majority of positives being misclassifications.

This is a very cool observation and leads amongst others to the conclusions that low-latency anonymity is not dead:

“[…] Second, it gives us a small glimmer of hope that maybe all is not lost against IX, National, or ISP level adversaries. Especially those with only sampled or connection-level resolution, where fine-grained details on inter-packet timings is not available (as will likely be the case with EU data retention).”


This post is of great interest because it re-opens the problem of high-precision traffic analysis, with a clearly understood and precisely known error rate. Current techniques, mostly based on heuristics, are not capable to deliver such detectors, with high reliability guarantees attached to them.


At the same time the The23rd Raccoon’s analysis overlooks one issue: many detectors do not simply perform matching of streams on a pair by pair basis, but as a whole. This means that the “best match” is selected according to some ranking metric. The mathematical analysis that has to then be presented to support the technique is the probability any non-match is selected over the correct match. Many papers in the literature provide implicitly such results (some based on the rank of the result, others based on selecting the best match and providing the total probability of error based on the selection.) Approaches that provide overall performance metrics should avoid the pitfalls of presenting “intermediate” false positive / false negative probabilities, and give an intuitive understanding of how well traffic analysis techniques work on a full body of streams or message traces.