Thoughts on “Oft Target” (HotPETs 17)

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.

A technical reading of the “HIMR Data Mining Research Problem Book”

Boing Boing just released a classified GCHQ document that was meant to act as the Sept 2011 guide to open research problems in Data Mining. The intended audience, Heilbronn Institute for Mathematical Research (HIMR), is part of the University of Bristol and composed of mathematicians working for half their time on classified problems with GCHQ.

First off, a quick perusal of the actual publication record of the HIMR makes a sad reading for GCHQ: it seems that very little research on data mining was actually performed post-2011-2014 despite this pitch. I guess this is what you get trying to make pure mathematicians solve core computer science problems.

However, the document presents one of the clearest explanations of GCHQ’s operations and their scale at the time; as well as a very interesting list of open problems, along with salient examples.

Overall, reading this document very much resembles reading the needs of any other organization with big-data, struggling to process it to get any value. The constrains under which they operate (see below), and in particular the limitations to O(n log n) storage per vertex and O(1) per edge event, is a serious threat — but of course this is only for un-selected traffic. So the 5000 or so Tor nodes probably would have a little more space and processing allocated to them, and so would known botnets — I presume.

Secondly, there is clear evidence that timing information is both recognized as being key to correlating events and streams; and it is being recorded and stored at an increasing granularity. There is no smoking gun as of 2011 to say they casually de-anonymize Tor circuits, but the writing is on the wall for the onion routing system. GCHQ at 2011 had all ingredients needed to trace Tor circuits. It would take extra-ordinary incompetence to not have refined their traffic analysis techniques in the past 5 years. The Tor project should do well to not underestimate GCHQ’s capabilities to this point.

Thirdly, one should wonder why we have been waiting for 3 years until such clear documents are finally being published from the Snowden revelations. If those had been the first published, instead of the obscure, misleading and very non-informative slides, it would have saved a lot of time — and may even have engaged the public a bit more than bad powerpoint.

Should Group Key Agreement be Symmetric and Contributory?

I have a rather enlightening chat with Yvo Desmedt after the Cambridge Security Protocol‘s Workshop, who was kind enough to give me an overview and insight into the group key agreement protocols of the ’90s. As part of an on-going conversation on secure chat, I am trying to understand the genealogy, and requirement, for key group agreements to be “contributory” — namely ensure all participants contribute to the final group key, even under malice. It seems that there is also a preference for symmetric schemes, where all participants perform the same operations.

Yvo’s classic Eurocrypt paper [BD94] is the basis of GOTR [LVH13], which manages to complicate it considerably. The original paper had a O(N) broadcasts cost, and was “peer-to-peer”, meaning that everyone just does the same thing. However it did not consider an active adversary, and was also not “contributory” meaning that an insider (active) adversary could force the key to anything they liked. Interestingly, Yvo points me to [BD96], which he thinks is superior to [BD94]. This paper really illustrates that there is no magic to group key agreement: a master key for the group is determined and then propagated using a key-sharing graph. This reduces the cost from O(N) broadcasts to just O(N) point to point messages — which to me seems optimal.

Now, the idea that schemes must be “contributory” (ie. no participant is special in determining the key — no one can force the key to be some specific value) emerged sometime in the late ’90s. The first reference I found to this property is [BW98], where the authors look at the round complexity of key agreement. However they state that “If the group key is generated and distributed by a central trusted party, then it is not necessary to discuss the communication complexity“. Then, they just launch into those schemes with no justification as to the reason centralized distribution may be a problem …

Katz and Young [KY03] also state that “(we exclude here centralized protocols in which a designated group manager is assumed; such asymmetric, non-contributory schemes place an unfairly high burden on one participant who is a single point of failure and who must also be trusted to properly generate keys)“. So it seems that the security issue contributory schemes try to mitigate is a flawed RNG. However this is a marginal threat — if the RNG is bad, than it may be likely the adversary can also corrupt other aspects of the platform to extract keys. In any case the flawed RNG threat can be dealt with by including some entropy from other participants assuming that they do not act in an adaptive malicious manner (if they do they can just leak the key to the adversary). I find it strange that KY03 argue that a single participant must not be burdened, when this results in proposed protocols that burden all participants to a great extent instead.

Around 2000 a number of works spring up that attempt to extend key agreement to dynamic membership setting, including [STW00] and [KPT00]. It is not at all clear to me whether those are in fact superior to running the key exchange multiple times, or even having a central party distributing keys.

Finally, Goldberg and others [GUGC09] propose extensions to OTR for a multi-user setting. These focus on deniability and signatures (and call a generic key exchange protocol) and a shared authentic transcript. This is a fine property, however I am a bit surprised the protocols are (a) so complex to establish ephemeral signatures and (b) so simple if they are to establish transcript consistency. My understanding is that they rely on the channel to offer consistent ordering, and then simply cryptographically ensure it was not tampered by an adversary — however I only read the paper obliquely.

Conclusion: It seems that a lot of the literature on group key exchange is based on the premise that the protocols need to be symmetric and contributory. Yet, I fail to see any justification beyond the fact that centralized schemes are simple and efficient, and no one could possibly write an academic paper about them. All schemes I have seem rely on the honest channel offering ordering, and being reliable. If that is not the case some of them detect it and hard fail (for example the integrity checks fail, with no hint that it is due to missing messages). This means that they assume some ordering happens on the outside of the crypto, which is dubious without some leader election. Few works have dealt with how you determine the group, which would either go the admin way or the voting way (can of worms).

References:

[BD94] Mike Burmester, Yvo Desmedt: A Secure and Efficient Conference Key Distribution System (Extended Abstract). EUROCRYPT 1994: 275-286

[LVH13] Hong Liu, Eugene Y. Vasserman, Nicholas Hopper: Improved group off-the-record messaging. WPES 2013: 249-254

[BD96] Mike Burmester, Yvo Desmedt: Efficient and Secure Conference-Key Distribution. Security Protocols Workshop 1996: 119-129

[GUGC09] Ian Goldberg, Berkant Ustaoglu, Matthew Van Gundy, Hao Chen: Multi-party off-the-record messaging. ACM Conference on Computer and Communications Security 2009: 358-368

[KY03] Katz, Jonathan, and Moti Yung. “Scalable protocols for authenticated group key exchange.” Advances in cryptology-CRYPTO 2003. Springer Berlin Heidelberg, 2003. 110-125.

[BW98] Becker, Klaus, and Uta Wille. “Communication complexity of group key distribution.” Proceedings of the 5th ACM conference on Computer and communications security. ACM, 1998.

[STW00] Steiner, Michael, Gene Tsudik, and Michael Waidner. “Key agreement in dynamic peer groups.” Parallel and Distributed Systems, IEEE Transactions on 11.8 (2000): 769-780.

[KPT00] Kim, Yongdae, Adrian Perrig, and Gene Tsudik. “Simple and fault-tolerant key agreement for dynamic collaborative groups.” Proceedings of the 7th ACM conference on Computer and communications security. ACM, 2000.

PETS in real time: Anonymous communications

An Accurate System-Wide Anonymity Metric for Probabilistic Attacks
Rajiv Bagai, Huabo Lu, Rong Li, and Bin Tang (Wichita State University)

Traditional entropy based anonymity metrics look at the security of single messages. But how can you quantify the security provided by a whole system? The first paper in this session looks at a system-wide definition of anonymity by “counting” the possible number of matchings between inputs and outputs of an anonymity system. Furthermore, the metric extends to the probabilities over perfect matchings to express subtleties of modern anonymity systems. The paper first of all provides a thorough critique of the metric by Edman et al. (there was also previous work on this metric by the Leuven crew).

In a nutshell the proposed system-wide metric associates a probability to each possible matching, and computes the entropy over this distribution as a measure of anonymity (normalized). The choice of shanon entropy to summarise quality can be changed to min-entropy or other (which is very cool!) One key issue with system-wide metrics is that  how they express the properties that any individual message receives. Paul Syverson points out that these type of metrics express more the anonymity capacity of a system — namely how much anonymity the system could provide as a whole. The question of how this capacity for protection is distributed across users may need an extension to those metrics. For anyone who would like to extend metrics to capture this aspect, this paper is a very solid foundation.

DefenestraTor: Throwing out Windows in Tor
Mashael AlSabah, Kevin Bauer and Ian Goldberg (University of Waterloo), Dirk Grunwald (University of Colorado), and Damon McCoy, Stefan Savage, and Geoffrey Voelker (University of California-San Diego)

This paper looks at performance issues within the Tor network, and in particular the effects of the congestion and flow control protocols. Tor implements simple end-to-end flow control mechanism at the granularity of circuits and streams. It turns out that the implemented window based flow control has detrimental effects on performance: it does not protect intermediate routers (who are likely to be the congested ones) from congestion.

Two approaches were followed to solve this problem. First, a smaller window could be used — but this would not solve the problem; or windows can be computed dynamically. Second, the N23 congestion control protocol (used for ATM) could be used over Tor. N23 is simple and guarantees no packets are dropped, while implementing a steady flow of data. Its a credit based system, where packets are sent when credits are available (and consume them), and credits are sent up the network when bandwidth is available.

The evaluation was done under realistic conditions on ExperimenTor. The improvement over the current Tor strategy is significant when it comes to the time to get the first byte, but the time to complete larger (bulk) downloads do suffer (which is part of the point of the protocol).

I am really happy to see research on the intersection of traditional networking and anonymous communications. I have never heard of N23 before (shame on me!), and it seems that it is a good fit for the problem of congestion in anonymity networks (where reliability is not an issue when TCP is used).

Privacy Implications of Performance-Based Peer Selection by Onion Routers: A Real-World Case Study using I2P
Michael Herrmann and Christian Grothoff (Technische Universität München)

This is an attack paper on the I2P network, and in particular the performance based peer selection. It combines a denial-of-service attack to influence the selection of peers within the network, and force a victim to choose corrupt servers.

This is a cute attack that combines denial-of-service, traffic analysis for confirmation you are on the same circuit, and interactions with an infrastructure to attack. This is a very good reminder that anonymity engineering is not simply systems’ work. Every design choice about performance can affect security in dramatic ways. The evaluation was also very sensitive to protecting users: the researchers tried their attack on the real network, but targeted their own circuits (I still want to see details to make sure no other users were affected).

Tor too implements circuit selection on the basis of performance — I am wondering to what extent similar ideas could be applied there …

Anonymity in the wild (social network)

Shishir Nagaraja has pointed out that our Drac anonymity system is not the first one to consider an anonymity network overlayed on a social network. The performance versus security of routing messages over a social network was already considered in his work entitled ‘anonymity in the wild’.

Shishir Nagaraja: Anonymity in the Wild: Mixes on Unstructured Networks. Privacy Enhancing Technologies 2007: 254-271 [pdf][ppt]

This is important prior work and we should have cited it properly. It presents an analysis of an anonymity provided by different synthetic social network topologies, as well as real-world data from LiveJournal.

WPES10 in real time: Jack for anonymous abuse control

• Jack: Scalable Accumulator-based Nymble System by Zi Lin(University of Minnesota) and Nicholas Hopper (University of Minnesota)

The potential for abuse is a key challenge when it comes to deploying anonymity systems, and the privacy technology community has been researching solutions to this problem for a long time. Nymble systems allow administrators to blacklist anonymous accounts, without revealing or even knowing their identity.

What is the model: a user registers an account with a service, such as wikipedia. Then the user can use an anonymous channel like Tor, to do operations, like edit encyclopedia articles. This prevents identification of the author, and also bypasses a number of national firewalls that prevent users accessing the service (China for example blocks Wikipedia for some reason). If abuse it detected then the account can be blacklisted, but without revealing which one it was! The transcript of the edit operation is sufficient for preventing any further edits, but without tracing back the original account or network address of the user.

Nymble systems had some limitations. They either required trusted third parties for registration, or they were slow. A new generation of Nymble systems, including Jack, is now addressing these limitations: they use modern cryptographic accumulator constructions that have proofs of non-membership in O(1) time, to prove a hidden identity is not blacklisted. Jack can do authentication in 200ms, and opening a Nymble address in case of abuse in less than 30ms. This is getting real practical, and it is time that Wikipedia starts using this system instead of blacklisting Tor nodes out of fear of abuse.

Other Nymble systems: The original nymble | Newer Nymble | BLAC | Nymbler with VERBS | PEREA. Each of them offers a different trade-off of efficiency and security.

WPES10 in real time: Balancing the Shadows

I am just sitting in the first WPES10 talk:

Balancing the Shadows by Max Schuchard, Alex Dean, Victor Heorhiadi, Yongdae Kim, and Nicholas Hopper (University of Minnesota)

ShadowWalker is a peer-to-peer anonymity system designed by Prateek Mittal (who was our intern in 2008) and Nikita Borisov to prevent corrupt peers jeopardising the network. The authors of this new paper “Balancing the shadows” present an attack on the system, where a malicious coalition of nodes can compromise routing security and can bias the probability of choosing a malicious node as a relay. It turns out that a naïve fix opens the system instead to selective denial-of-service attack.

How does the eclipse attack on ShadowWalker work? The adversary controls a full neighbourhood of the network, i.e. a sequence of peers in the distributed hash table (DHT). This allows an adversary to corrupt the “shadow” mechanism in shadow walker. When Alice asks a malicious node in this neighbourhood about another node in the network, they can provide a false ID, along with a set of false shadows. This attack is not too bad on its own, except that the same mechanism is used during the construction of the routing tables of the DHT. As a result an adversary that controls about 10% of the nodes can corrupt about 90% of the circuits, after a few rounds of the protocol (this was backed by simulations).

How to fix the attack? Can we increase the number of shadows of each node that can testify of the correctness of its ID? It turns out this is not a good idea: the more shadows the higher the probability one of them is malicious. In that case they can maliciously refuse to attest honest nodes, effectively taking them out of the protocol. The authors propose to change the protocol to only require a fraction of shadows providing signatures to attest an ID-node relationship — time will show if this withstands attacks.

What do we learn from this: first the level of security in peer-to-peer anonymity systems is still questionable, as designs keep being proposed and broken on a yearly basis. Second, it highlights that DHT based designs inherit the characteristic that routing tables are designed as part of the protocol. This offers the adversary an opportunity of amplify their attacks. Designs should therefore not consider that the DHT is in an honest steady-state, but instead consider attacks at the time of network formation. Finally, it is worth keeping in mind that these systems try to prevent adversaries using a small fraction of malicious nodes (5%-20%) to compromise the security of a large fraction of the network. This is still far from our hope that peer-to-peer anonymity could withstand large Sybil attacks where the adversary controls a multiple of honest nodes.

“Privacy” for the UK 2011 census?

The UK goes every ten years through a national census, where every household is called to fill in details about their demographics, habits, travel and income. The next one will be the UK 2011 census.

The office for national statistics has a statutory duty to ensure that the data released from this census cannot be used to identify any individual or to infer any of unknown attribute. Techniques for doing so are called statistical disclosure control, and have been the subject of intense study for the last 40 years at least. One could never have guessed by reading the documents on confidentiality for the next UK census.

To make a long story short: the ONS never considered modern well defined notions of privacy, it lacks a reliable evaluation framework to establish the degree of risk of different methods (let alone utility), and has proposed disclosure control measures that fall rather short of the state of the art.

Moving households around (a bit)

The consultation is not totally over yet, but the current favorite after two rounds of evaluation seems to be a technique called “Record Swapping”. How does it work? The technique takes the database of all responses to the census and outputs another database, that is sufficiently different to avoid identification and inference. Record swapping first categorises all records by the household size, sex, broad age, and hard-to-count variables. Then it selects 2-20% of the records, and each of them are paired with a record from the same category. Then the geographical data of each pair of records (yes, right, only the geographical data) are swapped.

This procedure has the effect to disperse geographically the population a bit so that, it is not possible to know whether single cells in tables are indeed providing information about an individual in a region or, whether they are the product of a swap from a different region. The advantage is that the totals are the same (since swapping things around is invariant to addition), the swaps are with “similar” households, and the procedure is simple to implement.

This is in-line with the definition of privacy of the census office, namely that: 

“The Registrars General concluded that the Code of Practice statement can be met in relation to census outputs if no statistics are produced that allow the identification of an individual (or information about an individual) with a high degree of confidence. The Registrars General consider that, as long as there has been systematic perturbation of the data, the guarantee in the Code of Practice would be met.”

Problems with “Record Swapping”

So far a whole process has been followed to evaluate a list of proposed disclosure control measures, present a methodolody to evaluate them, shortlist some, and perform more in-depth research about their utility and privacy. There is a lot of repetition in these documents, a few ad-hoc indicators of quality and privacy, and no security analysis what-so-ever about inference attacks on the proposed schemes. The subject of ” disclosure by differencing” is left as a suggestion for future work in the latest interim report, while the only method left on the list is Record Swapping, as well as ABS, that has apparently not been tested yet at all.

Why is that a problem? Records include many other potentially identifying fields aside from location. Since the rest of the record stand as it is, and is aggregated into tables, with a secret small cell adjustment technique, we cannot really be sure at all that there are no re-identification attacks. (Apparently revealing the details of the technique cannot be divulged for confidentiality reasons, violating even the most basic principle of security engineering! See page 3).

The utility measures used to assess how acceptable these disclosure control measures will be to data users (Shlomo et al.), are themselves very simplistic and do not offer very tight bounds on possible errors but I will leave this matter for the statisticians to blog about.

To make the problem worse, this time the ONS, is seriously thinking of allowing data users to submit their own queries to the database of statistics. The queries are not likely to be full SQL any time soon, but tables on 3 categories (called cubes) are likely to be allowed. This leaves wide open quite a range of attacks in the literature on inference in statistical databases.

At this point there is absolutely no evidence that the disclosure control scheme is actually secure, which in security engineering means that it is probably not.

How did we get to this situation?

It seems the bulk of the work on disclosure control has been done by the ONS, in conjunction with researchers from the University of Southampton. None of the authors of any of the evaluations has a substancial research experience in privacy technology or theoretical computer security that deals with these privacy matters in a systematic way.

What is revealing is the fact that the most relevant related work is never mentioned. It includes:

• The work of Denning on trackersand inference in statistical databases (1980). Instead the archaic term “differencing” is used.
• The work of Sweeney and Samarati on linkage attacks and k-anonymity (1997).
• The work of Dwork on Differential Privacy (2007), which is the most current and strongest definition of privacy for statistical databases.

These works show repeatedly that ad-hoc inference control measures, that only aim to suppress a handful of known and obvious attacks, are systematically bypassed.

Dwork in her work on Differential Privacy (that won the 2009 year’s PET Award) provides clear arguments on why simpler ad-hoc techniques cannot provide the same guarantee of privacy: their results can be aggregated with side information known to the adversary to facilitate inference. Differential privacy on the other hand guarantees that the results of a query to the database, or published table, reveals no more information when composed with other such queries or any side information. 

This is a hot topic in research today, and all the details may not be ready for a census in 2 years time. This does not justify the ONS’s ignorance of this field.

A traffic analysis of Link-Based Relay Selection? (PETS 2009)

Micah Sherr presented at PETS a few days ago his work on “Scalable Link-Based Relay Selection for Anonymous Routing“. The key idea is that paths are generated by taking into account the network performance of each link to be used. The overhead of distributing performance information can be reduced by associating with each server a network coordinate, that allows to estimate the latency between pairs of nodes.

This is a pure path selection proposal, as quite a few have appeared in the past year to reduce latency, or increase node utilization in Tor. The question with all those proposals is: how much anonymity would these path selection strategies provide?

The methodology we present in  “The Bayesian Traffic Analysis of Mix Networks” provides a way of answering such questions, by carefully modelling the path selection strategy. Applying the same methodology to these path selection proposals would be of clear benefit, and an excellent project for anyone interested in understanding better how to apply inference based techniques to traffic analysis.

Bayesian traffic analysis

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:

• Carmela Troncoso and George Danezis.
  The Bayesian Traffic Analysis of Mix Networks. (Draft)
  ACM CCS 2009, Chicago, USA.
• George Danezis, Claudia Diaz, Emilia Kasper, and Carmela Troncoso.
  The wisdom of Crowds: attacks and optimal constructions.
  ESORICS 2009, St Malo, France.
• George Danezis and Carmela Troncoso.
  Vida: How to use Bayesian inference to de-anonymize persistent communications.
  PETS 2009, Seattle, USA.