If someone is simultaneously watching a user’s traffic as it enters and leaves the network, it is possible to de-anonymise the communication. This could occur if the first and last node for a connection is controlled by the same person. Tor takes some steps to avoid this possibility e.g. no two computers on the same /16 network may be chosen for each connection. However, someone with access to several networks could circumvent this measure.

Not only is route selection critical for security, but it’s also a significant performance factor. Tor nodes vary dramatically in their capacity, mainly due to their network connections. If all nodes were chosen with equal likelihood, the slower ones would cripple the network. This is why Tor weights the selection probability for a node proportional to its contribution to the network bandwidth.

Because of the dual importance of route selection, there are a number of proposals which offer an alternative to Tor’s bandwidth-weighted algorithm. Later this week at PETS I’ll be presenting my paper, co-authored with Robert N.M. Watson, “Metrics for security and performance in low-latency anonymity systems”. In this paper, we examine several route selection algorithms and evaluate their security and performance.

Intuitively, a route selection algorithm which weights all nodes equally appears the most secure because an attacker can’t make their node count any more than the others. This has been formalized by two measures: Gini coefficient and entropy. In fact the reality is more complex — uniform node selection resists attackers with lots of bandwidth, whereas bandwidth-weighting is better against attackers with lots of nodes.

Our paper explores the probability of path compromise of different route selection algorithms, when under attack by a range of different adversaries. We find that none of the proposals are optimal against all adversaries, and so summarizing effective security in terms of a single figure is not feasible. We also model the performance of the schemes and show that bandwidth-weighting offers both low latency and high resistance to attack by bandwidth-constrained adversaries.

This limits the attack since in many cases TCP timestamps may be unavailable. In particular, Tor hidden services operate at the TCP layer, stripping all TCP and IP headers. If an attacker wants to estimate clock skew over the hidden service channel, the only directly available clock source may be the 1 Hz HTTP timestamp. The quantization noise in this case is three orders of magnitude above the TCP timestamp case, making the approach I used in the paper effectively infeasible.

While visiting Cambridge in summer 2007, Sebastian Zander developed an improved clock skew measurement technique which would dramatically reduce the noise of clock-skew measurements from low-frequency clocks. The basic idea, shown below, is to only request timestamps very close to a clock transition, where the quantization noise is lowest. This requires the attacker to firstly lock-on to the phase of the clock, then keep tracking it even when measurements are distorted by network jitter.

Sebastian and I wrote a paper — An Improved Clock-skew Measurement Technique for Revealing Hidden Services — describing this technique, and showing results from testing it on a Tor hidden service installed on PlanetLab. The measurements show a large improvement over the original paper, with two orders of magnitude lower noise for low-frequency clocks (like the HTTP case). This approach will allow previous attacks to be executed faster, and make previously infeasible attacks possible.

The paper will be presented at the USENIX Security Symposium, San Jose, CA, US, 28 July – 1 August 2008.

[ slides (PDF 9.6M) | video (BitTorrent — MPEG4, 106M) ]

The CCC is a great conference to attend and a good source of ideas for papers. There were many excellent talks, but here are a few I can particularly recommend (I’m still working though the videos of talks I couldn’t attend in person):

Current events in Tor development

Roger Dingledine gives Tor-related news, including anti-censorship features and interaction with law enforcement

Design Noir

ladyada talks about controversial electronics projects, including the TV-B-Gone and her own cellphone jammer

DNS Rebinding And More Packet Tricks

Dan Kaminsky describes the DNS Rebinding attack and demonstrates tunneling arbitrary TCP streams over a browser

Mifare

Karsten Nohl and Henryk Plötz describe how they reverse-engineered the Mifare encryption algorithm, Crypto1, and the weaknesses they discovered

Steam-Powered Telegraphy

Jens Ohlig et al. demonstrate their Internet connected (but not quite steam-powered) Telex machine

What can we do to counter the spies?

Annie Machon describes her work with MI5, why she left and her life on the run

Why Silicon-Based Security is still that hard: Deconstructing Xbox 360 Security

Michael Steil and Felix Domke demonstrate the clever techniques they developed to install Linux on the XBox360

The spread of wide-scale Internet surveillance has spurred interest in anonymity systems that protect users’ privacy by restricting unauthorised access to their identity. This requirement can be considered as a flow control policy in the well established field of multilevel secure systems. I apply previous research on covert channels (unintended means to communicate in violation of a security policy) to analyse several anonymity systems in an innovative way.

One application for anonymity systems is to prevent collusion in competitions. I show how covert channels may be exploited to violate these protections and construct defences against such attacks, drawing from previous covert channel research and collusion-resistant voting systems.

In the military context, for which multilevel secure systems were designed, covert channels are increasingly eliminated by physical separation of interconnected single-role computers. Prior work on the remaining network covert channels has been solely based on protocol specifications. I examine some protocol implementations and show how the use of several covert channels can be detected and how channels can be modified to resist detection.

I show how side channels (unintended information leakage) in anonymity networks may reveal the behaviour of users. While drawing on previous research on traffic analysis and covert channels, I avoid the traditional assumption of an omnipotent adversary. Rather, these attacks are feasible for an attacker with limited access to the network. The effectiveness of these techniques is demonstrated by experiments on a deployed anonymity network, Tor.

Finally, I introduce novel covert and side channels which exploit thermal effects. Changes in temperature can be remotely induced through CPU load and measured by their effects on crystal clock skew. Experiments show this to be an effective attack against Tor. This side channel may also be usable for geolocation and, as a covert channel, can cross supposedly infallible air-gap security boundaries.

This thesis demonstrates how theoretical models and generic methodologies relating to covert channels may be applied to find practical solutions to problems in real-world anonymity systems. These findings confirm the existing hypothesis that covert channel analysis, vulnerabilities and defences developed for multilevel secure systems apply equally well to anonymity systems.

Steven J. Murdoch, Covert channel vulnerabilities in anonymity systems, Technical report UCAM-CL-TR-706, University of Cambridge, Computer Laboratory, December 2007.