A traffic analysis exercise

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:

• George Danezis and Carmela Troncoso. Vida: How to use Bayesian inference to de-anonymize persistent communications. Privacy Enhancing Technologies Symposium (PETS 2009), Seattle, USA.

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.

Syllabus and course material on Privacy Technology

I just come back from a visit to COSIC at K.U. Leuven, to teach a course on Computer Security. Claudia Diaz and myself discussed over lunch the idea of putting together a syllabus for Privacy Technologies. Many in this field have been teaching courses and giving guest lectures, but there does not seem to be yet a canonical curriculum, describing that an advanced course in Privacy Technology should teach.

Here is my attempt at proposing such a syllabus — which I will probably revise after discussions at PETS 2009 next week.

1. An introduction to Privacy Technology
   An overview of the basic concepts, different fields like technology and law, motivation, threat models, Soft versus Hard privacy technology.
   Slides from the 2007 COSIC course: Introduction to Privacy Technology [pdf]
   (Claudia Diaz has vastly improved these slides to present a lecture on the same topic in this years COSIC course.)
2. Privacy in authentication
   Modern authentication protocols, initiator privacy and responder privacy, JFKi and JFKr examples, secure password authentication, PAK.
   Slides from Estonia computer security course in 2007: Secure authentication[pdf, start at slide 3]
3. Selective Disclosure Credentials
   Zero knowledge proofs, selective disclosure for discrete logs, Brands credentials, CL signatures and CL credentials, e-cash, abuse prevention.
   Slides from Estonia computer security course in 2007: Anonymous credentials[pdf, start at slide 45]
4. Anonymous communications
   Proxies, Crowds, DC networks, mix networks and onion routing.
   Slides from ITE talk in 2006: Introducing Anonymous Communications[pdf]
5. An introduction to traffic analysis
   History, identification, information extraction, military applications, internet security, traffic data availability
   Slides from SantaCrypt 2005 in Prague: An introduction to traffic analysis[pdf]
6. The traffic analysis of anonymous communications
   Cryptographic attacks, long term intersection and disclosure, short term disclosure, bridging, network discovery.
   Slides from Umass Amherst talk: Introduction to traffic analysis[pdf]
7. Privacy in Databases
   Inference control, k-anonymity, differential privacy, perturbation, trackers.
   Slides from CFP 2007: Privacy in Databases[pdf, start at slide 58]
8. Privacy in Storage
   Encrypted storage, steganographic storage, remote storage, traffic analysis of storage protocols.
9. Secure Elections
   Electronic voting technologies, secure crypto elections, manual zero-knowledge proofs, receipt freeness, robust mixing.
10. Censorship resistance and availability
    Blocking technologies, counter-blocking technologies, RF technologies, peer-to-peer file sharing, decentralisation and reputation technologies, sybil attacks.
11. Location privacy
    Location based services, Mix zones, ad-hoc network privacy, location privacy friendly location services (PriPAYD), charging schemes.
12. Identity management protocols
    Federated identity management, Liberty, InfoCards, OpenID, PRIME project concepts, privacy policies, P3p, SecPAL.
13. Economic, legal and policy issues of Privacy Technology
    Privacy economics & attitudes, data protection, data retention, interception by design, lawful access, coercion, privacy as a right, health information.

Note that the order of the topics is arbitrary, and mostly related to what slides I have already available. One could start with less technical subjects and then go to the more cryptographic and statistical topics. If anyone has any nice pointers to slide decks for the topics that have none for the moment, I would appriciate them.

Mass political surveillance in the UK is alive and well!

There is a tendency amongst privacy advocates in the UK to focus on mistakes, or false positives, of ubiquitous surveillance, as well as small scale “disproportionate” uses of surveillance. These two are the key arguments used to fend off plans to increase the level of data collection. 

In the first case the argument is that perfectly honest people might be mistaken for crooks because of the imperfect view that any data collection system provides the authorities. Any automated decisions, the argument goes, will inevitably flag up Innocent people, while miss the sought targets, since they will be using an array of evasion tactics to foil it. In its essence, this first criticism is true, but can easily be countered by a good oversight mechanism, including human judgement in the loop, as well as pointing out that the bad guys will never have perfect discipline in implementing counter surveillance measures, and if they do it will be at a great cost. Needless to say the false positive / false negative argument has not been very successful, even though it is a good one.

The second argument is based on proportionality: once surveillance powers are in place for one purpose, such as the prevention of serious crime or terrorism, they will inevitably be used for other unforeseen and disproportionate aims. The key recent example is how local UK authorities are using directed surveilance powers to prevent littering and dog fouling. Similar fears have been expressed about traffic data retention that could be used as part of civil cases, or simply seized for any crime what so ever using established evidence collection laws. Again, this argument is valid but a good oversignt mechanism can take care of those cases, at least in theory.

The reason these arguments are first to be used, as well as ineffective, is that they start from the premise that institutionally those performing the surveillance are “the good guys”, and their aim is to catch “the bad guys” to protect the public. Sure, in the process mistakes happen, but they are in good faith and are rectified since all the good people are on the same side after all. “Bad apples” misusing their surveillance powers will be weeded out, since institutionally the context in which they use these powers is benevolent, and devoid of malice. On can easily see why privacy advocates in the UK have found it easy to use this assumption, since they mostly lobby politicians and have a close relationship with law enforcement as well as industry, who while admitting isolated mistakes will never admit a systematic privacy problem, let alone systematic malicious use of surveillance powers.

The tide is turning on this argument. In the recent months we have witnessed direct interference with the elected political process by the police, namely the raid on the Parliament office of MP Damian Green. As The Register reports “Green’s homes and offices were searched on 27 November following his arrest, on suspicion of leaking embarrassing informationfrom the Home Office.” The information was simply politically embarrassing, not sensitive or national security related. It seem this incident has challenged in the mainstream that those in charge of surveillance will simply act in the public interest, and other cases of mass political surveillance have since seen the light:

• First a company named The Consulting Association was found to keep an extensive database about construction workers, listing their trade union activity, past disputes with employers, and other sensitive personal information. It was providing a vetting service to the building industry to ensure that those active in the labour movement, basically do not get jobs.
• Secondly a Guardian investigation uncovered that the Metropolitan Police keeps a database of people attending protests, despite them never have been in trouble with the law, and specifically targets journalists covering protests. (The video is highly recommended.)

These are no more isolated abuses, but systematic operations running for many years, and supported at the highest level of management of both organizations. In its editorial the Guardianput its finger on the key argument against surveillance powers by finally saying out loud: “today’s revelations underline the perils surveillance represent for democracy [...]“. These worries are now being echoed at the highest echelons of the political system, as The Register reports regarding the Policing complaints at the recent Climate Camp:

“The problem with incidents of this kind, according to Norman Baker MP, who addressed the meeting on the Climate Camp protest yesterday is that they look suspiciously like police-made law and go hand in hand with the politicisation of the police. He said: “The IPCC exist to investigate allegations of individual misconduct by Police Officers. They are not there to investigate systemic abuses of power, which is what seem to be going on in cases such as the Climate Camp.”

“I am a strong supporter of the Police. But there looks increasingly to be a need for additional oversight into the ways in which they interpret the law.”

Where is European computer security research?

There is something very broken with computer security research in Europe. While EU funding is pouring in for many years through successive FPs, it seems that European research groups and institutions are systematically underrepresented in terms of Program Committee participation to the top-tier conferences. (Individual researchers of European origin, based abroad, are actually doing quite fine.)

The following graph illustrates the fraction of European researchers in some top-tier computer security conferences over the past decade. Core security conferences are chosen, namely IEEE S&P, ACM CCS, ISOC NDSS and USENIX SEC, as compared with more crypto conferences like CRYPTO, or EUROCRYPT (where European research seems to be quite competitive.) As we can see on average this fraction is less than 20%, with some venues like USENIX SEC and NDSS often figuring next to no European researcher on their PC.

Fraction of European PC members in security conferences

Even this graph says only half the story. Within Europe there is a tremendous variability in PC membership of these conferences, with few individual researchers from specific groups being invited repeatedly. One example is illustrative: the IEEE S&P committee for 2009 is composed of 48 members; 8 of them from Europe; 4 of them from Cambridge; 3 of them from Microsoft Research, Cambridge (a US company, by the way.)

What is going on? Systematic bias in the chair’s selection (unlikely), or a structural problem in the European security research field (much more likely)?

The base rate fallacy and the traffic analysis of Tor

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.

Our confidence in Cambridge college rankings for Computer Science

Increasingly traffic analysis makes use of complex statistical techniques, which are not (yet) part of the standard training of computer scientists at Cambridge (UK). As aresult I spend a lot of time reading textbooks like the excellent Bayesian Data Analysis(by Andrew Gelmanet al, who also maintains a blog) or Information Theory, Inference, and Learning Algorithms by David MacKay, who treats the subject more from a Computer Science perspective. The most fascinating aspect Bayesian statistics is that it is very easy (and even intrinsic to the analysis) to calculate one’s confidence in an inferred assertion.

One question that has been in my mind for some time is whether any Cambridge Colleges are better or worse on average than any others in Computer Science. Being `better’ is a very subjective judgement when it comes to education, but the primary issue that I wanted to study is whether one could claim that students of any particular college get consistently better or worse exam marks than others. Luckily the class marks for Part IB and Part II computer science were recently published (on a physical notice board — sorry no link) for the 2008 exams which could be subject to analysis to answer that question. But what would be the right way of doing this?

A simple minded approach would involve taking the proportion of students that got high marks (a First or Two-one) and rank colleges accordingly. Any college that is in the bottom half of this ranking is underperforming, while any college in the top half is doing well. Yet this approach gives no intuition about how significant the resutls are: different colleges have different number of students, and these numbers are in any case very small. It is likely that the resulting ranking is subject to random fluctiations.

Instead I construct a simple Bayesian model for the ranking of colleges, which readily leads itself to calculating the confidence an observer can have about the assigned ranks. The resulting graph plots the rank of each college, along with the 68% (solid line) and 90% (dotted line) confidence interval over that rank. Red intervals indicate that the college is significantly over or below average.

 

Only a handful of colleges turn out to be significanlty (i.e. more than 90% of the time) better or worse in terms of exam resutls. For the record, Churchill, St Catherine’s, Selwyn, and Fitzwilliam are definitely above average. For all others the small number of students in a single year makes it impossible to tell if the colleges are systematically or randomly getting high or low marks. There is an interesting correlation between these results and physical proximity to the Computer Laboratory!

A few more details on the model used to derive the above graph: The model assumes that each college i has a (hidden) variable pi in [0,1] representing the probability that a student at this college receives a First or Two-one (observed) mark (each student independently receives such a mark with probability pi and a binomial distribution describes the number of marks above average that each college receives, according to their number of students.) Colleges are ranked according to their respective probabilities pi, from highest to lowest.

The problem is then transformed into a simple Bayesian inference exercise: given the observed marks we need to estimate the hidden pi, for each college. We model our belief about each pi as a Beta distribution, with a non-informative prior Beta(a=1,b=1). We update the distribution according to the observations, and it becomes for each college pi ~ Beta(a=1+#(High Marks), b=1+#(Low Marks)). We then draw samples from those distributions and rank the colleges. We repeat this procedure about 55,000 times (that should be large enough) and calculate the intervals in which the college ranks lie 68% and 90% of the time. A Python script generates the samples and an R script produces the plot.

Disclaimer: there is no causation implied between college and marks. This correlation could be due to colleges selecting students in particular ways, teaching them better, or ensuring that they leave university instead of getting low marks. There is no way of telling which apply from this analysis. It is totally wrong to judge colleges just based on such exam performance statistics, and as the results show, most of the time statistically meaningless.

PET 2008 Program is out!

The list of accepted papers for the Privacy Enhancing Technologies Symposium for 2008 (PET) has just been published. The program this year is very heavy on anonymous communication, and traffic analysis, cementing the symposiumas the de-facto venue in these disciplines.

A selection of papers to appear, that make a very interesting read  (thanks to the authors giving me a copy!), include:

• Studying Timing Analysis on the Internet with SubRosa
  Hatim Daginawala and Matthew Wright (University of Texas at Arlington, USA)
• Perfect Matching Disclosure Attacks
  Carmela Troncoso, Benedikt Gierlichs, Bart Preneel, and Ingrid Verbauwhede (COSIC, K.U. Leuven, Belgium)
• On the Impact of Social Network Profiling on Anonymity
  Claudia Diaz, Carmela Troncoso (K.U.Leuven, Belgium), and Andrei Serjantov (The Free Haven Project, UK)
• Chattering Laptops
  Tuomas Aura (Microsoft Research, UK), Janne Lindqvist (Helsinki University of Technology, Finland), Michael Roe (Microsoft Research, UK), and Anish Mohammed (Royal Holloway, University of London, UK)
• Metrics for Security and Performance in Low-Latency Anonymity Systems
  Steven J. Murdoch and Robert N. M. Watson (Computer Laboratory, University of Cambridge, UK)

I should blog in detail about our own contributions, when the final drafts are in, so that I can provide a link to the full text:

• Bridging and Fingerprinting: Epistemic Attacks on Route Selection
  George Danezis (Microsoft Research, Cambridge, UK) and Paul Syverson (Naval Research Laboratory, USA)
• How to Bypass Two Anonymity Revocation Schemes
  George Danezis (Microsoft Research, Cambridge, UK) and Len Sassaman (K.U. Leuven, Belgium)

Lets not forget that the PET Award for 2008 deadline is still ahead of us, and good papers from the last two years deserve to be nominated for it!

Sane security assumptions

In security engineering it is a known fact that few practical systems can claim unconditional security. Security is always reducible to a set of assumptions that are believed to hold.

In traditional cryptography these assumptions are quite clear: keys have to be kept safe; block ciphers and hash functions should be indistinguishable from random permutations and random functions; and public key primitives rely on the hardness of a small set of mathematical problems.

Traditional security engineering is encouraging us to think along similar lines: any secure system has to have a well defined Trusted Computing Base (TCB) that functions according to the specification, and ensure that the security properties of the larger system overall hold. It is the role of the TCB to make sure access control, key storage, memory protection, and privileges, to only mention a few hold in commodity operating systems. In operating systems with mandatory access control the TCB is in charge of imposing the security policy, on sometimes unwilling users. Often the correctness of the TCB cannot be shown mathematically and sound engineering practices have to be employed to implement it: these include code reviews, safe languages, verification and most importantly simplicity and few lines of code.

Hidden under the mathematical assumption or the secure TCB assumption, are people. People will hold access to keys, and coalitions of them are going to have access and permissions to modify the TCB. Shamir’s secret sharing scheme, despite being mathematically unconditionally secure, still relies on some fraction of users holding shares to abide by a security policy and not divulge their shares. For a long time people were considered outside the system, and now security engineering starts considering them explicitly.

So far so good: mathematics, trusted computing bases, or quorums of people are a same foundation on which one can build secure systems.

Yet a worrying trend comes from some corners of systems research: researchers extend or build over complex underlying system without fully understanding their security assumptions — and assume that the final system will be secure. A typical example is any security paper that makes use of a secure Distributed Hash Table (DHT). Some paper discuss how one could build such a beast, either making assumption about admission control and detection of mis-routing, or trying to use social structure to alleviate routing problems and the sybil attack. Those `secure’ DHTs are fragile, make multiple assumptions about their operational environment and impose restrictions and overheads on how the DHT can be used. It is not acceptable to use them as black box replacements for insecure DHTs thinking that their security properties will magically make the overall design secure.

Even worse than not understanding the composition of security properties or assumptions it to make assumptions that are demonstrably false in the real world for the sake of providing a security argument. To use again an example of DHTs, it has become a meme in the systems research community that it is acceptable to do addmission and rate control to limit the Sybil attack, based on IP addresses. The assumption is that IP addresses are a scarse resource, and that an adversary will find it hard to be able to route streams from multiple IP addresses. This is simply not the case: powerful adversaries control large national firewalls / routers that they can use to pretend they are any machine they wish, and pathetic adversaries can buy bot-net time on thousands of machines for little money. How have we allowed this bogus `security assumption’ to appear in so many publications?

Another meme is that selecting a quorum of nodes from an undefined population will increase security. This is an exterme form of the `kindness of strangers’ assumption and comes down to assuming that given enough people a proportion of them will be good. This might be true (even though sociologists will have to work hard to prove it) if the population is guaranteed to be drawn at random, or representative at least of the user base. But if a system can be joined by adversaries perfoming a Sybil attack, it is not clear there is any basis for trusting 1000 nodes more than 10, or think that within those 1000 nodes only 30% would be corrupt. This is a parody of the quorum of people assumption in Shamir’s secret sharing sheme: in secret sharing you know who the people are, and assume that a quotum of them will be honest — given that you know their identity, and have made a trust decision upon it!

The cryptocracy podcast

I am writing this as I am listening to the new cryptocracy podcast, an Internet radio show dedicated to research in computer security and cryptography. The host is Thomas S. Heydt-Benjamin an active researcher in privacy technology and computer security, based in ETH and IBM Zurich. The show features an eclectic selection of announcements, interviews with researchers and presentation of key papers in the field.

It is refreshing to hear that the content is clear, but uncompromising on technical accuracy and detail. It feels like a technical conference chat delivered right into my living room! Highly recommended for those with a serious interest in security research beyond what the popular trade press can deliver.