The Tor Cloud images for all the seven regions have been updated to include the latest cloud image for stable Ubuntu release 10.04 LTS (Lucid Lynx). These new images are available on the Tor Cloud website.
If you are already running a Tor Cloud bridge, you will need to either manually update your image, or set up a new Tor Cloud bridge and terminate the old one. If you decide not to take action, your image may fail to download package updates correctly.
What follows is an important message from the ubuntu-cloud mailing list:
In an effort to improve on reliability of the Ubuntu archive mirrors for EC2 instances, Canonical is replacing the existing EC2 archive mirrors with mirrors backed by Amazon S3. This change itself will be done via modification of DNS entries and will be transparent to users.
However, due to a bug in the http pipelining implementation in S3 a change to apt configuration needs to be made to avoid download errors. We have chosen to deliver this change via a package upgrade in cloud-init.
The action required is one of the following:
- Upgrade cloud-init using sudo apt-get update ; sudo apt-get install -y cloud-init
- Launch official AMI's released after 2012-04-01, which will have the fix included
- Manually disable http pipeline use in apt using echo 'Acquire::http::Pipeline-Depth "0";' | sudo tee /etc/apt/apt.conf.d/99-no-pipelining
Should you choose not to take appropriate action, you will likely experience transient apt downloading errors after the change is implemented. In order to give appropriate time to apply the change, this transition will not occur before April 18, 2012.
Our progress report for March 2012 is now available. Highlights include lots and lots of metrics work, bridge infrastructure work, new tor alpha release, support queue stats, and some press and speaking slots.
Available as a pdf with full color graphs, https://archive.torproject.org/monthly-report-archive/2012-March-Monthly...
or as a plain text file for portability and readability, https://archive.torproject.org/monthly-report-archive/2012-March-Monthly...
The Tor network relies on volunteers to donate bandwidth. The more people who run Tor as a bridge or a relay, the faster and safer the network becomes. Tactical Tech created a video to encourage you to join the Tor Network. The video, and information about how you can set up a bridge or a relay, can be found on https://www.torproject.org/relays. If you want to help us translate the video into your language, let us know!
The full HD video can be found here: https://media.torproject.org/video/2012-03-04-BuildingBridges-HD.ogv
The Tor Cloud images for all the seven regions have been updated to include the latest cloud image for stable Ubuntu release 10.04.4 LTS (Lucid Lynx). These new images are available on the Tor Cloud website.
Users who wish to update their existing installations can do so with: apt-get update && apt-get dist-upgrade && reboot.
The Tor Cloud images for all the seven regions have been updated to include the anonymizing relay monitor (arm). This works much like top does for system usage, providing real time statistics for bandwidth, cpu, memory usage, current Tor configuration, connection details etc.
If you're already running a Tor Cloud instance and wish to install arm, connect to your instance with SSH and run sudo aptitude install tor-arm.
Once we get more (and more diverse) bridge addresses, the next research step is that we'll need to get better at telling which bridges are blocked in which jurisdictions. For example, most of the bridges we give out via https and gmail are blocked in China. But which ones exactly? How quickly do they get blocked? Do some last longer than others? Do they ever get unblocked? Is there some pattern to the blocking, either by time, by IP address or network, by user load on the bridge, or by distribution strategy? We can't evaluate new bridge distribution strategies if we can't track whether the bridges in each strategy are being blocked.
Generally speaking, bridge reachability tests break down into two approaches: passive and active. Passive tests don't involve any new connections on the part of Tor clients or bridges, whereas active tests follow the more traditional "scanning" idea. None of the reachability tests we've thought of are perfect. Instead, here we discuss how to combine imperfect tests and use feedback from the tests to balance their strengths and weaknesses.
We should explore two types of passive testing approaches: reporting from bridges and reporting from clients.
Passive approach 1: reporting from bridges. Right now Tor relays and bridges publish aggregate user counts — rough number of users per country per day. In theory we can look at the user counts over time to detect statistical drops in usage for a given country. That approach has produced useful results in practice for overall connections to the public Tor relays from each country: see George Danezis's initial work on a Tor censorship detector.
But there are two stumbling blocks when trying to apply the censorship detector model to individual bridges. First, we don't have ground truth about which bridges were actually blocked or not at a given time, so we have no way to validate our models. Second, while overall usage of bridges in a given country might be high, the load on a given bridge tends to be quite low, which in turns makes it difficult to achieve statistical significance when looking at usage drops.
Ground truth needs to be learned through active tests: we train the models with usage patterns for bridges that get blocked and bridges that don't get blocked, and the model predictions should improve. The question of statistical significance can be overcome by treating the prediction as a hint: even if our models don't give us enough confidence to answer "blocked for sure" or "not blocked for sure" about a given bridge, they should be able to give us a number reflecting likelihood that the bridge is now blocked. That number should feed back into the active tests, for example so we pay more attention to bridges that are more likely to be newly blocked.
Passive approach 2: reporting from clients. In addition to the usage reporting by bridges, we should also consider reachability reporting by clients. Imagine a Tor client that has ten bridges configured. It tries to connect to each of them, and finds that two work and eight don't. This client is doing our scanning for us, if only we could safely learn about its results. The first issue that comes up is that it could mistakenly report that a bridge is blocked if that bridge is instead simply down. So we would want to compare the reports to concurrent active scans from a "more free" jurisdiction, to pick out the bridges that are up in one place yet down in another.
From there, the questions get trickier: 1) does the set of bridges that a given user reports about create a fingerprint that lets us recognize that user later? Even if the user reports about each bridge through a separate Tor circuit, we'd like to know the time of the scan, and nearby times can be used to build a statistical profile. 2) What if users submit intentionally misleading reports? It seems there's a tension between wanting to build a profile for the user (to increase our confidence in the validity of her reports) versus wanting to make sure the user doesn't develop any recognizable profile. Perhaps the Nymble design family can contribute an "unlinkable reputation" trick to resolve the conflict, but as we find ourselves saying so often at Tor, more research remains.
The goal of active scanning is to get ground truth on whether each bridge is really blocked. There's a tradeoff here: frequent scans give us better resolution and increased confidence, but too many scan attempts draw attention to the scanners and thus to the addresses being scanned.
We should use the results of the passive and indirect scans to give hints about what addresses to do active scans on. In the steady-state, we should aim to limit our active scans to bridges that we think just went from unblocked to blocked or vice versa, and to a sample of others for spot checks to keep our models trained.
There are three pieces to active scanning: direct scans, reverse scans, and indirect scans.
Active approach 1: direct scans. Direct scans are what we traditionally think of when we think of scanning: get access to a computer in the target country, give it a list of bridges, and have it connect directly to each bridge on the list.
Before I continue though, I should take an aside to discuss types of blocking. In September 2009 when China first blocked some bridges, I spent a while probing the blocked bridges from a computer in Beijing. From what I could tell, China blocked the bridges in two ways. If the bridge had no other interesting services running (like a webserver), they just blackholed the IP address, meaning no packets to or from the IP address made it through the firewall. But if there was an interesting service, they blocked the bridge by IP and port. (I could imagine this more fine-grained blocking was done by dropping SYN packets, or by sending TCP RST packets; but I didn't get that far in my investigation.)
So there are two lessons to be learned here. First, the degree to which our active scans match real Tor client behavior could influence the accuracy of the scans. Second, some real-world adversaries are putting considerable effort — probably manual effort — into examining the bridges they find and choosing how best to filter them. After all, if they just blindly filtered IP addresses we list as bridges, we could add Baidu's address as a bridge and make them look foolish. (We tried that; it didn't work.)
These lessons leave us with two design choices to consider.
First, how much of the Tor protocol should we use when doing the scans? The spectrum ranges from a simple TCP scan (or even just a SYN scan), to a vanilla SSL handshake, to driving a real Tor client that does a genuine Tor handshake. The less realistic the handshake, the more risk that we conclude the bridge is reachable when in fact it isn't; but the more realistic the handshake, the more we stand out to an adversary watching for Tor-like traffic.
The mechanism by which the adversary is discovering bridges also impacts which reachability tests are a smart idea. For example, it appears that China may have recently started doing deep packet inspection (DPI) for Tor-like connections over the Great Firewall and then doing active-followup SSL handshakes to confirm which addresses are Tor bridges. If that report turns out to be true, testing bridge reachability via active scans that include handshaking would be counterproductive: the act of doing the test would influence the answer. We can solve their attack by changing our handshake so they don't recognize it anymore, or by introducing scanning-resistance measures like bridge passwords. In the shorter-term, we should confirm that simple connection scanning (without a handshake) doesn't trigger any blocks, and then restrict ourselves to that type of scanning in China until we've deployed a better answer.
Second, should we scan "decoy" addresses as well, to fool an observer into thinking that we're not scanning for Tor bridges in particular, and/or to drive up the work the observer needs to do to distinguish the "real" bridges? Whether this trick is useful depends on the level of sophistication and dedication of the adversary. For example, China has already demonstrated that they check IP addresses before blocking them, and in general I worry that the more connections you make to anything, the more likely you are to attract attention for further scrutiny. How would we generate the list of decoy addresses? If we choose it randomly from the space of IP addresses, a) most of them will not respond, and b) we'll invite abuse complaints from security people looking for worms. Driving up the work factor sounds like a great feature, but it could have the side effect that it encourages the adversary to invest in an automated "is this a Tor bridge" checker, which would be an unfortunate step for them to take if they otherwise wouldn't.
Active direct scans come with a fundamental dilemma: the more we think a bridge has been blocked, the more we want to scan it; but the more likely it is to be blocked, the more the adversary might already be watching for connections to it, for example to do a "zig-zag" bridge enumeration attack. So we need to avoid scanning bridges that we think are not blocked. But we also need to explore more subtle scanning techniques such as the ones below.
Active approach 2: reverse scans. A bridge that gets duplex blackholed by a government firewall can learn that it has been filtered by trying to make a connection into the filtered country.
For example, each bridge might automatically connect to baidu.com periodically, and publish the results of its reachability test in its extrainfo descriptor. We could either feed this information into the models and follow up with other active probes if the bridge thinks it's been blocked; or we could use it the other way by instructing bridges that we think have been blocked to launch a reverse scan.
We can actually take advantage of the flexibility of the Tor protocol to do scanning from each bridge to Baidu without changing the bridge code at all: we simply try to extend an ordinary circuit from the bridge to the target destination, and learn at what stage the 'extend' request failed. (We should extend the Tor control protocol to expose the type of failure to the Tor controller, but that's a simple matter of programming.)
Note that these reverse scans can tell us that a bridge has been blocked, but it can't tell us that a bridge hasn't been blocked, since it could just be blocked in a more fine-grained way.
Finally, how noticeable would these reverse scans be? That is, could the government firewall enumerate bridges by keeping an eye out for Tor-like connection attempts to Baidu? While teaching the bridges to do the scanning themselves would require more work, it would give us more control over how much the scans stick out.
Active approach 3: indirect scans. Indirect scans use other services as reflectors. For example, you can connect to an FTP server inside the target country, tell it that your address is the address of the bridge you want to scan, and then try to fetch a file. How it fails should tell you whether that FTP server could reach the bridge or not.
There are many other potential reflector protocols out there, each with their own tradeoffs. For example, can we instruct a DNS request in-country to recurse to the target bridge address, and distinguish between "I couldn't reach that DNS server" and "that wasn't a DNS server"? (DNS is probably not the right protocol to use inside China, given the amount of DNS mucking they are already known to do.)
Another avenue is a variant on idle scanning, which takes advantage of predictable TCP IPID patterns: send a packet directly to the bridge to learn its current IPID, then instruct some computer in-country to send a packet, and then send another packet directly to find the new IPID and learn whether or not the in-country packet arrived.
What other services can be bent to our will? Can we advertise the bridge address on a bittorrent tracker that's popular in China and see whether anybody connects? Much creative research remains here.
Putting it all together
One of the puzzle pieces holding us back from rolling out the "tens of thousands of bridge addresses offered by volunteers with spare net blocks" plan is that we need better ways to get feedback on when addresses get blocked. The ideas in this blog post hopefully provide a good framework for thinking about the problem.
For the short term, we should deploy a basic TCP connection scanner from inside several censoring countries (China, Iran, and Syria come to mind). Since the "clients report" passive strategy still has some open research questions, we should get all our hints from the "bridges report" passive strategy. As we're ramping up, and especially since our current bridges are either not blocked at all (outside China), or mostly blocked (inside China), we should feel free to do more thorough active scans to get a better intuition about what scanning can teach us.
In the long term, I want to use these various building blocks in a feedback loop to identify and reward successful bridge distribution strategies, as outlined in Levchenko and McCoy's FC 2011 paper.
Specifically, we need these four building blocks:
2) A way to get fresh bridge addresses over time. The more addresses we can churn through, the more aggressive we can be in experimenting with novel distribution approaches. See the "more bridge addresses" blog post for directions here.
3) A way to discover when a bridge is blocked in a given country. That's what this blog post is about.
4) Distribution strategies that rely on different mechanisms to make enumeration difficult. Beyond our "https" and "gmail" distribution strategies, we know a variety of people in censored countries, and we can think of each of these people as a distribution channel.
We can define the efficiency of a bridge address in terms of how many people use it and how long before it gets blocked. So a bridge that gets blocked very quickly scores a low efficiency, a bridge that doesn't get blocked but doesn't see much use scores a medium efficiency, and a popular bridge that doesn't get blocked scores high. We can characterize the efficiency of a distribution channel as a function of the efficiency of the bridges it distributes. The key insight is that we then adapt how many new bridges we give to each distribution channel based on its efficiency. So channels that are working well automatically get more addresses to give out, and channels that aren't working well automatically end up with fewer addresses.
Of course, there's more to it than that. For example, we need to consider how to handle the presence of bridge enumeration attacks that work independently of which distribution channel a given bridge address was given to. We also need to consider attacks that artificially inflate the efficiency of bridges (and thus make us overreward distribution channels), or that learn about a bridge but choose not to block it. But that, as they say, is a story for another time.
The Tor Cloud project gives you a user-friendly way of deploying bridges to help users access an uncensored Internet. By setting up a bridge, you donate bandwidth to the Tor network and help improve the safety and speed at which users can access the Internet.
Bridges are Tor relays that aren't listed in the main directory. This means that to use a bridge, you'll need to locate one first. And because there is no complete public list of all the bridges, they are also harder to block. A bridge will act as the first hop in a circuit, and will only forward traffic on to other relays in the Tor network.
Setting up a Tor bridge on Amazon EC2 is simple and will only take you a couple of minutes. The images have been configured with automatic package updates and port forwarding, so you do not have to worry about Tor not working or the server not getting security updates.
You should not have to do anything once the instance is up and running. Tor will start up as a bridge, confirm that it is reachable from the outside, and then tell the bridge authority that it exists. After that, the address for your bridge will be given out to users.
To help new customers get started in the cloud, Amazon is introducing a free usage tier. The Tor Cloud images are all micro instances, and new customers will be able to run a free micro instance for a whole year. The Tor Cloud images have been configured with a bandwidth limit, so customers who don't qualify for the free usage tier should only have to pay an estimated $30 a month.
For more information, see the Tor Cloud website.
UPDATE: Some users have asked about the AWS free usage tier and pointed out that it only includes 15 GB of bandwidth out per month. I have updated the Tor Cloud website (changes should go live soon) with the following:
The Tor Cloud images have been configured to use no more than 40 GB of bandwidth out per month. We have estimated that customers who do not qualify for the free usage tier will pay up to $30 a month. Customers who qualify for the free usage tier, but who run bridges that use more than 15 GB of bandwidth out per month, will pay up to $3 per month.
I hope that this better clarifies the cost of running a bridge in the Amazon cloud, let me know if you have any questions.
While we're exploring smarter ways of getting more bridge addresses, and while the bridge arms race hasn't heated up yet in most countries (or has surpassed the number of bridges we have, in the case of China), it's the perfect time to take stock of bridge address enumeration attacks and how well we can defend against them.
For background, bridge relays (aka bridges) are Tor relays that aren't listed in the main Tor directory. So even if an attacker blocks all the public relays, they still need to block all these "private" or "dark" relays too.
Here are ten classes of attacks to discover bridges, examples of them we've seen or worry about in practice, and some ideas for how to resolve or mitigate each issue. If you're looking for a research project, please grab one and start investigating!
#1: Overwhelm the public address distribution strategies.
China broke our https bridge distribution strategy in September 2009 by just pretending to be enough legitimate users from enough different subnets on the Internet. They broke the Gmail bridge distribution strategy in March 2010. These were easy to break because we don't have enough addresses relative to the size of the attacker (at this moment we're giving out 176 bridges by https and 201 bridges by Gmail, leaving us 165 to give out through other means like social networks), but it's not just a question of scale: we need better strategies that require attackers to do more or harder work than legitimate users.
#2: Run a non-guard non-exit relay and look for connections from non-relays.
Normal clients use guard nodes for the first hop of their circuits to protect them from long-term profiling attacks; but we chose to have bridge users use their bridge as a replacement for the guard hop, so we don't force them onto four-hop paths which would be less fun to use. As a result, if you run a relay that doesn't have the Guard flag, the only Tors who end up building circuits through you are relays (which you can identify from the public consensus) and bridges.
This attack has been floating around for a while, and is documented for example in Zhen Ling et al's Extensive Analysis and Large-Scale Empirical Evaluation of Tor Bridge Discovery paper.
The defense we plan is to make circuits through bridges use guards too. The naive way to do it would be for the client to choose a set of guards as her possible next hops after the bridge; but then each new client using the bridge increasingly exposures the bridge. The better approach is to make use of Tor's loose source routing feature to let the bridge itself choose the guards that all of the circuits it handles will use: that is, transparently layer an extra one-hop circuit inside the client's circuit. Those familiar with Babel's design will recognize this trick by the name "inter-mix detours".
Using a layer of guards after the bridge has two features: first, it completely removes the "bridges directly touch non-guards" issue, turning the attack from a deterministic one to a probabilistic one. Second, it reduces the exposure of the bridge to the rest of the network, since only a small set of relays will ever see a direct connection from it. The tradeoff, alas, is worse performance for bridge users. See proposal 188 for details.
[Edit: a friendly researcher pointed out to me that another solution here is to run the bridge as multi-homed, meaning the address that the relay sees isn't the address that the censor should block. That solution also helps resolve issues 3-5!]
#3: Run a guard relay and look for protocol differences.
Bridges are supposed to behave like relays with respect to the users using them, but like clients with respect to the relays they make connections to. Any slip-ups we introduce where the bridge acts like a relay with respect to the next hop are ways the next hop can distinguish it. Recent examples include "bridges fetched directory information like relays rather than like clients", "bridges didn't use a CREATE_FAST cell for the first hop of their own circuits like clients would have", "bridges didn't reject CREATE and CREATE_FAST cells on connections they had initiated like clients would have", and "bridges distinguish themselves in their NETINFO cell".
There's no way that's the end of them. We could sure use some help auditing the design and code for similar issues.
#4: Run a guard relay and do timing analysis.
Even if we fix issues #2 and #3, it may still be possible for a guard relay to look at the "clients" that are connecting to it, and figure out based on latency that some of the circuits from those clients look like they're two hops away rather than one hop away.
I bet there are active tricks to improve the attack accuracy. For example, the relay could watch round-trip latency from the circuit originator (seeing packets go towards Alice, and seeing how long until a packet shows up in response), and comparing that latency to what he sees when probing the previous hop with some cell that will get an immediate response rather than going all the way to Alice. Removing all the ways of probing round-trip latency to an adjacent Tor relay (either in-protocol or out-of-protocol) is a battle we're not going to win.
The research question remains though: how hard is this attack in practice? It's going to come down to statistics, which means it will be a game of driving up the false positives. It's hard to know how best to solve it until somebody does the engineering work for the attack.
If the attack turns out to work well (and I expect it will), the "bridges use guards" design will limit the damage from the attack.
#5: Run a relay and try connecting back to likely ports on each client that connects to you.
Many bridges listen for incoming client connections on port 443 or 9001. The adversary can run a relay and actively portscan each client that connects, to see which ones are running services that speak the Tor protocol. This attack was published by Eugene Vasserman in Membership-concealing overlay networks and by Jon McLachlan in On the risks of serving whenever you surf: Vulnerabilities in Tor's blocking resistance design, both in 2009.
The "bridges use guards" design partially resolves this attack as well, since we limit the exposure of the bridge to a small group of relays that probably could have done some other above attacks as well.
But it does not wholly resolve the concern: clients (and therefore also bridges) don't use their entry guards for directory fetches at present. So while the bridge won't build circuits through the relay it fetches directory information from, it will still reveal its existence. That's another reason to move forward with the "directory guard" design.
#6: Scan the Internet for services that talk the Tor protocol.
Even if we successfully hide the bridges behind guards, the adversary can still blindly scan for them and pretend to be a client. To make it more practical, he could focus on scanning likely networks, or near other bridges he's discovered. We called this topic "scanning resistance" in our original bridge design paper.
There's a particularly insidious combination of #5 and #6 if you're a government-scale adversary: watch your government firewall for SSL flows (since Tor tries to blend in with SSL traffic), and do active followup probing to every destination you see. Whitelist sites you've already checked if you want to trade efficiency for precision. This scale of attack requires some serious engineering work for a large country, but early indications are that China might be investigating exactly this approach.
The answer here is to give the bridge user some secret when she learns the bridge address, and require her to prove knowledge of that secret before the bridge will admit to knowing the Tor protocol. For example, we could imagine running an Apache SSL webserver with a pass-through module that tunnels your traffic to the Tor relay once she's presented the right password. Or Tor could handle that authentication itself. BridgeSPA: Improving Tor Bridges with Single Packet Authorization offers an SPA-style approach, with the drawbacks of requiring root on both sides and being OS-specific.
Another avenue to explore is putting some of the bridge addresses behind a service like Telex, Decoy Routing, or Cirripede. These designs let users privately tag a flow (e.g. an SSL handshake) in such a way that tagged flows are diverted to a Tor bridge while untagged flows continue as normal. So now we could deploy a vanilla Apache in one place and a vanilla Tor bridge in another, and not have to modify either of them. The Tor client bundle would need an extra piece of software though, and there are still some engineering and deployment details to be worked out.
#7: Break into the Tor Project infrastructure.
The bridge directory authority aggregates the list of bridges and periodically sends it to the bridgedb service so it can parcel addresses out by its various distribution strategies. Breaking into either of these services would give you the list of bridges.
We can imagine some design changes to make the risk less bad. For one, people can already run bridges that don't publish to the bridge directory authority (and then distribute their addresses themselves). Second, I had a nice chat with a Chinese NGO recently who wants to set up a bridge directory authority of their own, and distribute custom Vidalia bridge bundles to their members that are configured to publish their bridge addresses to this alternate bridge directory authority. A third option is to decentralize the bridge authority and bridgedb services, such that each component only learns about a fraction of the total bridge population — that design quickly gets messy though in terms of engineering and in terms of analyzing its security against various attacks.
#8: Just watch the bridge authority's reachability tests.
You don't actually need to break in to the bridge authority. Instead, you can just monitor its network connection: it will periodically test reachability of each bridge it knows, in order to let the bridgedb service know which addresses to give out.
We could do these reachability tests through Tor, so watching the bridge authority doesn't tell you anything about what it's testing. But that just shifts the risk onto the rest of the relays, such that an adversary who runs or monitors a sample of relays gets to learn about a corresponding sample of bridges.
One option is to decentralize the testing such that monitoring a single location doesn't give you the whole bridge list. But how exactly to distribute it, and onto what, is messy from both the operational and research angles. Another option would be for the bridges themselves to ramp up the frequency of their reachability tests (they currently self-test for reachability before publishing, to give quick feedback to their operator if they're misconfigured). Then the bridges can just anonymously publish an authenticated "still here" message once an hour, so (assuming they all tell the truth) the bridge authority never has to do any testing. But this self-testing also allows an enumeration attack, since we build a circuit to a random relay and then try to extend back to our bridge address! Maybe bridges should be asking their guards to do the self-testing — once they have guards, that is?
These questions are related to the question of learning whether a bridge has been blocked in a given country. More on that in a future blog post.
#9: Watch your firewall and DPI for Tor flows.
While the above attacks have to do with recognizing or inducing bridge-specific behavior, another class of attacks is just to buy some fancy Deep Packet Inspection gear and have it look for, say, characteristics of the SSL certificates or handshakes that make Tor flows stand out from "normal" SSL flows. Iran has used this strategy to block Tor twice, and it lets them block bridges for free. The attack is most effective if you have a large and diverse population of Tor users behind your firewall, since you'll only be able to learn about bridges that your users try to use.
We can fix the issue by making Tor's handshake more like a normal SSL handshake, but I wonder if that's really a battle we can ever win. The better answer is to encourage a proliferation of modular Tor transports, like obfsproxy, and get the rest of the research community interested in designing tool-neutral transports that blend in better.
#10: Zig-zag between bridges and users.
Start with a set of known bridge addresses. Watch your firewall to see who connects to those bridges. Then watch those users, and see what other addresses they connect to. Wash, rinse, repeat.
As above, this attack only works well when you have a large population of Tor users behind your firewall. It also requires some more engineering work to be able to trace source addresses in addition to destination addresses. But I'd be surprised if some major government firewalls don't have this capability already.
The solution here probably involves partitioning bridge addresses into cells, such that zig-zagging from users to bridges only gives you a bounded set of bridges (and a bounded set of users, for that matter). That approach will require some changes in our bridgedb design though. Currently when a user requests some bridge addresses, bridgedb maps the user's "address" (IP address, gmail account name, or whatever) into a point in the keyspace (using consistent hashing), and the answers are the k successors of that point in the ring (using DHT terminology).
Dan Boneh suggested an alternate approach where we do keyed hashes of the user's address and all the bridge fingerprints, and return all bridges whose hashed fingerprints match the user's hash in the first b bits. The result is that users would tend to get clustered by the bridges they know. That feature limits the damage from the zig-zag attack, but does it increase the risks in some distribution strategies? I already worry that bridge distribution strategies based on social networks will result in clusters of socially related users using the same bridges, meaning the attacker can reconstruct the social network. If we isolate socially related users in the same partition, do we magnify that problem? This approach also needs more research work to make it scale such that we can always return about k results, even as the address pool grows, and without reintroducing zig-zag vulnerabilities.
#11: ...What did I miss?
We need more bridges. When I first envisioned the bridge address arms race, I said "We need to get lots of bridges, so the adversary can't learn them all." That was the wrong statement to make. In retrospect, the correct statement was: "We need the rate of new bridge addresses to exceed the rate that the adversary can block them."
For background, bridge relays (aka bridges) are Tor relays that aren't listed in the main Tor directory. So even if an attacker blocks all the public relays, they still need to block all these "private" or "dark" relays too. We deployed them several years ago in anticipation of the upcoming arms race, and they worked great in their first showing in 2009. But since then, China has learned and blocked most of the bridges we give out through public (https and gmail) distribution channels.
One piece of the puzzle is smarter bridge distribution mechanisms (plus see this post for more thoughts) — right now we're getting 8000 mails a day from gmail asking for bridges from a pool of less than a thousand. The distribution strategy that works best right now is ad hoc distribution via social connections. But even if we come up with brilliant new distribution mechanisms, we simply need more addresses to work with. How can we get them? Here are five strategies.
Approach one: Make it easy to become a bridge using the Vidalia interface. This approach was our first try at getting more bridges: click on "Sharing", then "Help censored users reach the Tor network". Easy to do, and lots of people have done it. But lots here is thousands, not hundreds of thousands. Nobody knows that they should click it or why.
Approach two: Bridge-by-default bundles. People who want to help out can now simply download and run our bridge-by-default bundle, and poof they're a bridge. There's a lot of flexibility here. For example, we could provide a customized bridge-by-default bundle for a Chinese human rights NGO that publishes your bridge address directly to them; then they give out the bridge addresses from their volunteers through their own social network. I think this strategy will be most effective when combined with targeted advocacy, that is, after a given community is convinced that they want to help and want to know how they can best help.
Approach three: Fast, stable, reachable Tor clients auto-promote themselves. Tor clients can monitor their own stability, performance, and reachability, and the best clients can opt to become bridges automatically. We can tune the thresholds ("how fast, how stable") in the directory consensus, to tailor how many clients promote themselves in response to demand. Read the proposal for more details. In theory this approach could provide us with many tens of thousands of bridges in a wide array of locations — and we're drawing from a pool of people who already have other reasons to download Tor. Downsides include a) there's quite a bit of coding work remaining before we can launch it, b) there are certainly situations where we shouldn't turn a Tor user into a bridge, which means we need to sort out some smart way to interact with the user and get permission, and c) these users don't actually change addresses as often as we might want, so we're still in the "gets lots of bridges" mindset rather than the "increase the rate of new bridge addresses" mindset.
Approach four: Redirect entire address blocks into the Tor network. There's no reason the bridge and its address need to run in the same location, and it's really addresses that are the critical resource here. If we get our friends at various ISPs to redirect some spare /16 networks our way, we'd have a lot more addresses to play with, and more importantly, we can control the churn of these addresses. Past experience with some censors shows that they work hard to unblock addresses that are no longer acting as proxies. If we light up only a tiny fraction of the IP space at a time, how long until they block all of it? How much does the presence of other services on the address block make them hesitate? I want to find out. The end game here is for Comcast to give us a few random IP addresses from each of their /24 networks. All the code on the Tor bridge side already works here, so the next steps are a) figure out how to teach an ISP's router to redirect some of its address space to us, and then b) sign up some people who have a good social network of users who need bridges, and get them to play that arms race more actively.
Approach five: More generic proxies. Originally I had thought that the extra layer of encryption and authentication from a bridge was a crucial piece of keeping the user (call her Alice) safe. But I'm increasingly thinking that the security properties she gets from a Tor circuit (anonymity/privacy) can be separated from the security properties she gets from the bridge (reachability, and optionally obfuscation). That is, as long as Alice can fetch the signed Tor network consensus and verify the keys of each of the public relays in her path, it doesn't matter so much that the bridge gets to see her traffic. Attacks by the bridge are no more effective than attacks by a local network adversary, which by design is not much. Now, this conclusion is premature — adding a bridge into the picture means there's a new observation point in addition to the local network adversary, and observation points are exactly what the attacker needs to correlate traffic flows and break Tor's anonymity, But on the flip side, right now bridges already get to act as these observational points, and the extra layer of encryption they add doesn't seem to help Alice any. So it's too early to say that a socks or https proxy is just as safe as a bridge (assuming you use a full Tor circuit in either case), but I'm optimistic that these more generic proxies have a role to play.
If we go this route, then rather than needing volunteers to run a whole Tor (which is especially cumbersome because it needs libraries like OpenSSL), people could run socks proxies on a much broader set of platforms. For example, they should be easy to add into Orbot (our Tor package for Android) or into Seattle (an overlay network by UW researchers that restricts applications to a safe subset of Python). We could even imagine setting up a website where volunteers visit a given page and it runs a Flash or Java applet socks proxy, lending their address to the bridge pool while their browser is open. There are some gotchas to work through, such as a) needing to sign the applets so they have the required network permissions, b) figuring out how to get around the fact that it seems hard to allow connections from the Internet to a flash plugin, and c) needing to program the socks proxy with a Tor bridge or relay address so the user doesn't have to ask for it (after all, socks handshakes are unencrypted and it wouldn't do to let the adversary watch Alice ask for an IP address that's known to be associated with Tor). This 'flash proxy' idea was developed in collaboration with Dan Boneh at Stanford, and they are currently designing and building it — stay tuned.