There are tensions in the Tor protocol design between the anonymity provided by entry guards and the performance improvements from better load balancing. This blog post walks through the research questions I raised in 2011, then summarizes answers from three recent papers written by researchers in the Tor community, and finishes by explaining what Tor design changes we need to make to provide better anonymity, and what we'll be trading off.
Part one: The research questions
In Tor, each client selects a few relays at random, and chooses only from those relays when making the first hop of each circuit. This entry guard design helps in three ways:
First, entry guards protect against the "predecessor attack": if Alice (the user) instead chose new relays for each circuit, eventually an attacker who runs a few relays would be her first and last hop. With entry guards, the risk of end-to-end correlation for any given circuit is the same, but the cumulative risk for all her circuits over time is capped.
Second, they help to protect against the "denial of service as denial of anonymity" attack, where an attacker who runs quite a few relays fails any circuit that he's a part of and that he can't win against, forcing Alice to generate more circuits and thus increasing the overall chance that the attacker wins. Entry guards greatly reduce the risk, since Alice will never choose outside of a few nodes for her first hop.
Third, entry guards raise the startup cost to an adversary who runs relays in order to trace users. Without entry guards, the attacker can sign up some relays and immediately start having chances to observe Alice's circuits. With them, new adversarial relays won't have the Guard flag so won't be chosen as the first hop of any circuit; and even once they earn the Guard flag, users who have already chosen guards won't switch away from their current guards for quite a while.
In August 2011, I posted these four open research questions around guard rotation parameters:
- Natural churn: For an adversary that controls a given number of relays, if the user only replaces her guards when the current ones become unavailable, how long will it take until she's picked an adversary's guard?
- Artificial churn: How much more risk does she introduce by intentionally switching to new guards before she has to, to load balance better?
- Number of guards: What are the tradeoffs in performance and anonymity from picking three guards vs two or one? By default Tor picks three guards, since if we picked only one then some clients would pick a slow one and be sad forever. On the other hand, picking only one makes users safer.
- Better Guard flag assignment: If we give the Guard flag to more or different relays, how much does it change all these answers?
For reference, Tor 0.2.3's entry guard behavior is "choose three guards, adding another one if two of those three go down but going back to the original ones if they come back up, and also throw out (aka rotate) a guard 4-8 weeks after you chose it." I'll discuss in "Part three" of this post what changes we should make to improve this policy.
Part two: Recent research papers
Tariq Elahi, a grad student in Ian Goldberg's group in Waterloo, began to answer the above research questions in his paper Changing of the Guards: A Framework for Understanding and Improving Entry Guard Selection in Tor (published at WPES 2012). His paper used eight months of real-world historical Tor network data (from April 2011 to December 2011) and simulated various guard rotation policies to see which approaches protect users better.
Tariq's paper considered a quite small adversary: he let all the clients pick honest guards, and then added one new small guard to the 800 or so existing guards. The question is then what fraction of clients use this new guard over time. Here's a graph from the paper, showing (assuming all users pick three guards) the vulnerability due to natural churn ("without guard rotation") vs natural churn plus also intentional guard rotation:
In this graph their tiny guard node, in the "without guard rotation" scenario, ends up getting used by about 3% of the clients in the first few months, and gets up to 10% by the eight-month mark. The more risky scenario — which Tor uses today — sees the risk shoot up to 14% in the first few months. (Note that the y-axis in the graph only goes up to 16%, mostly because the attacking guard is so small.)
The second paper to raise the issue is from Alex Biryukov, Ivan Pustogarov, and Ralf-Philipp Weinmann in Luxembourg. Their paper Trawling for Tor Hidden Services: Detection, Measurement, Deanonymization (published at Oakland 2013) mostly focuses on other attacks (like how to censor or track popularity of hidden services), but their Section VI.C. talks about the "run a relay and wait until the client picks you as her guard" attack. In this case they run the numbers for a much larger adversary: if they run 13.8% of the Tor network for eight months there's more than a 90% chance of a given hidden service using their guard sometime during that period. That's a huge fraction of the network, but it's also a huge chance of success. And since hidden services in this case are basically the same as Tor clients (they choose guards and build circuits the same way), it's reasonable to conclude that their attack works against normal clients too so long as the clients use Tor often enough during that time.
I should clarify three points here.
First clarifying point: Tariq's paper makes two simplifying assumptions when calling an attack successful if the adversary's relay *ever* gets into the user's guard set. 1) He assumes that the adversary is also either watching the user's destination (e.g. the website she's going to), or he's running enough exit relays that he'll for sure be able to see the correponding flow out of the Tor network. 2) He assumes that the end-to-end correlation attack (matching up the incoming flow to the outgoing flow) is instantaneous and perfect. Alex's paper argues pretty convincingly that these two assumptions are easier to make in the case of attacking a hidden service (since the adversary can dictate how often the hidden service makes a new circuit, as well as what the traffic pattern looks like), and the paper I describe next addresses the first assumption, but the second one ("how successful is the correlation attack at scale?" or maybe better, "how do the false positives in the correlation attack compare to the false negatives?") remains an open research question.
Researchers generally agree that given a handful of traffic flows, it's easy to match them up. But what about the millions of traffic flows we have now? What levels of false positives (algorithm says "match!" when it's wrong) are acceptable to this attacker? Are there some simple, not too burdensome, tricks we can do to drive up the false positives rates, even if we all agree that those tricks wouldn't work in the "just looking at a handful of flows" case?
More precisely, it's possible that correlation attacks don't scale well because as the number of Tor clients grows, the chance that the exit stream actually came from a different Tor client (not the one you're watching) grows. So the confidence in your match needs to grow along with that or your false positive rate will explode. The people who say that correlation attacks don't scale use phrases like "say your correlation attack is 99.9% accurate" when arguing it. The folks who think it does scale use phrases like "I can easily make my correlation attack arbitrarily accurate." My hope is that the reality is somewhere in between — correlation attacks in the current Tor network can probably be made plenty accurate, but perhaps with some simple design changes we can improve the situation. In any case, I'm not going to try to tackle that research question here, except to point out that 1) it's actually unclear in practice whether you're done with the attack if you get your relay into the user's guard set, or if you are now faced with a challenging flow correlation problem that could produce false positives, and 2) the goal of the entry guard design is to make this issue moot: it sure would be nice to have a design where it's hard for adversaries to get into a position to see both sides, since it would make it irrelevant how good they are at traffic correlation.
Second clarifying point: it's about the probabilities, and that's intentional. Some people might be scared by phrases like "there's an x% chance over y months to be able to get an attacker's relay into the user's guard set." After all, they reason, shouldn't Tor provide absolute anonymity rather than probabilistic anonymity? This point is even trickier in the face of centralized anonymity services that promise "100% guaranteed" anonymity, when what they really mean is "we could watch everything you do, and we might sell or give up your data in some cases, and even if we don't there's still just one point on the network where an eavesdropper can learn everything." Tor's path selection strategy distributes trust over multiple relays to avoid this centralization. The trouble here isn't that there's a chance for the adversary to win — the trouble is that our current parameters make that chance bigger than it needs to be.
To make it even clearer: the entry guard design is doing its job here, just not well enough. Specifically, *without* using the entry guard design, an adversary who runs some relays would very quickly find himself as the first hop of one of the user's circuits.
Third clarifying point: we're considering an attacker who wants to learn if the user *ever* goes to a given destination. There are plenty of reasonable other things an attacker might be trying to learn, like building a profile of many or all of the user's destinations, but in this case Tariq's paper counts a successful attack as one that confirms (subject to the above assumptions) that the user visited a given destination once.
And that brings us to the third paper, by Aaron Johnson et al: Users Get Routed: Traffic Correlation on Tor by Realistic Adversaries (upcoming at CCS 2013). This paper ties together two previous series of research papers: the first is "what if the attacker runs a relay?" which is what the above two papers talked about, and the second is "what if the attacker can watch part of the Internet?"
The first part of the paper should sound pretty familiar by now: they simulated running a few entry guards that together make up 10% of the guard capacity in the Tor network, and they showed that (again using historical Tor network data, but this time from October 2012 to March 2013) the chance that the user has made a circuit using the adversary's relays is more than 80% by the six month mark.
In this case their simulation includes the adversary running a fast exit relay too, and the user performs a set of sessions over time. They observe that the user's traffic passes over pretty much all the exit relays (which makes sense since Tor doesn't use an "exit guard" design). Or summarizing at an even higher level, the conclusion is that so long as the user uses Tor enough, this paper confirms the findings in the earlier two papers.
Where it gets interesting is when they explain that "the adversary could run a relay" is not the only risk to worry about. They build on the series of papers started by "Location Diversity in Anonymity Networks" (WPES 2004), "AS-awareness in Tor path selection" (CCS 2009), and most recently "An Empirical Evaluation of Relay Selection in Tor" (NDSS 2013). These papers look at the chance that traffic from a given Tor circuit will traverse a given set of Internet links.
Their point, which like all good ideas is obvious in retrospect, is that rather than running a guard relay and waiting for the user to switch to it, the attacker should instead monitor as many Internet links as he can, and wait for the user to use a guard such that traffic between the user and the guard passes over one of the links the adversary is watching.
This part of the paper raises as many questions as it answers. In particular, all the users they considered are in or near Germany. There are also quite a few Tor relays in Germany. How much of their results here can be explained by pecularities of Internet connectivity in Germany? Are their results predictive in any way about how users on other continents would fare? Or said another way, how can we learn whether their conclusion shouldn't instead be "German Tor users are screwed, because look how Germany's Internet topology is set up"? Secondly, their scenario has the adversary control the Autonomous System (AS) or Internet Exchange Point (IXP) that maximally deanonymizes the user (they exclude the AS that contains the user and the AS that contains her destinations). This "best possible point to attack" assumption a) doesn't consider how hard it is to compromise that particular part of the Internet, and b) seems like it will often be part of the Internet topology near the user (and thus vary greatly depending on which user you're looking at). And third, like the previous papers, they think of an AS as a single Internet location that the adversary is either monitoring or not monitoring. Some ASes, like large telecoms, are quite big and spread out.
That said, I think it's clear from this paper that there *do* exist realistic scenarios where Tor users are at high risk from an adversary watching the nearby Internet infrastructure and/or parts of the Internet backbone. Changing the guard rotation parameters as I describe in "Part three" below will help in some of these cases but probably won't help in all of them. The canonical example that I've given in talks about "a person in Syria using Tor to visit a website in Syria" remains a very serious worry.
The paper also makes me think about exit traffic patterns, and how to better protect people who use Tor for only a short period of time: many websites pull in resources from all over, especially resources from centralized ad sites. This risk (that it greatly speeds the rate at which an adversary watching a few exit points — or heck, a few ad sites — will be able to observe a given user's exit traffic) provides the most compelling reason I've heard so far to ship Tor Browser Bundle with an ad blocker — or maybe better, with something like Request Policy that doesn't even touch the sites in the first place. On the other hand, Mike Perry still doesn't want to ship an ad blocker in TBB, since he doesn't want to pick a fight with Google and give them even more of a reason to block/drop all Tor traffic. I can see that perspective too.
Part three: How to fix it
Here are five steps we should take, in rough order of how much impact I think each of them would have on the above attacks.
If you like metaphors, think of each time you pick a new guard as a coin flip (heads you get the adversary's guard, tails you're safe this time), and the ideas here aim to reduce both the number and frequency of coin flips.
Fix 1: Tor clients should use fewer guards.
The primary benefit to moving to fewer guards is that there are fewer coin flips every time you pick your guards.
But there's a second benefit as well: right now your choice of guards acts as a kind of fingerprint for you, since very few other users will have picked the same three guards you did. (This fingerprint is only usable by an attacker who can discover your guard list, but in some scenarios that's a realistic attack.) To be more concrete: if the adversary learns that you have a particular three guards, and later sees an anonymous user with exactly the same guards, how likely is it to be you? Moving to two guards helps the math a lot here, since you'll overlap with many more users when everybody is only picking two.
On the other hand, the main downside is increased variation in performance. Here's Figure 10 from Tariq's paper:
"Farther to the right" is better in this graph. When you pick three guards (the red line), the average speed of your guards is pretty good (and pretty predictable), since most guards are pretty fast and it's unlikely you'll pick slow ones for all three. However, when you only pick only one guard (the purple line), the odds go up a lot that you get unlucky and pick a slow one. In more concrete numbers, half of the Tor users will see up to 60% worse performance.
The fix of course is to raise the bar for becoming a guard, so every possible guard will be acceptably fast. But then we have fewer guards total, increasing the vulnerability from other attacks! Finding the right balance (as many guards as possible, but all of them fast) is going to be an ongoing challenge. See Brainstorm tradeoffs from moving to 2 (or even 1) guards (ticket 9273) for more discussion.
Switching to just one guard will also preclude deploying Conflux, a recent proposal to improve Tor performance by routing traffic over multiple paths in parallel. The Conflux design is appealing because it not only lets us make better use of lower-bandwidth relays (which we'll need to do if we want to greatly grow the size of the Tor network), but it also lets us dynamically adapt to congestion by shifting traffic to less congested routes. Maybe some sort of "guard family" idea can work, where a single coin flip chooses a pair of guards and then we split our traffic over them. But if we want to avoid doubling the exposure to a network-level adversary, we might want to make sure that these two guards are near each other on the network — I think the analysis of the network-level adversary in Aaron's paper is the strongest argument for restricting the variety of Internet paths that traffic takes between the Tor client and the Tor network.
This discussion about reducing the number of guards also relates to bridges: right now if you configure ten bridges, you round-robin over all of them. It seems wise for us to instead use only the first bridge in our bridge list, to cut down on the set of Internet-level adversaries that get to see the traffic flows going into the Tor network.
Fix 2: Tor clients should keep their guards for longer.
In addition to choosing fewer guards, we should also avoid switching guards so often. I originally picked "one or two months" for guard rotation since it seemed like a very long time. In Tor 0.2.4, we've changed it to "two or three months". But I think changing the guard rotation period to a year or more is probably much wiser, since it will slow down the curves on all the graphs in the above research papers.
I asked Aaron to make a graph comparing the success of an attacker who runs 10% of the guard capacity, in the "choose 3 guards and rotate them every 1-2 months" case and the "choose 1 guard and never rotate" case:
In the "3 guard" case (the blue line), the attacker's success rate rapidly grows to about 25%, and then it steadily grows to over 80% by the six month mark. The "1 guard" case (green line), on the other hand, grows to 10% (which makes sense since the adversary runs 10% of the guards), but then it levels off and grows only slowly as a function of network churn. By the six month mark, even this very large adversary's success rate is still under 25%.
So the good news is that by choosing better guard rotation parameters, we can almost entirely resolve the vulnerabilities described in these three papers. Great!
Or to phrase it more as a research question, once we get rid of this known issue, I'm curious how the new graphs over time will look, especially when we have a more sophisticated analysis of the "network observer" adversary. I bet there are some neat other attacks that we'll need to explore and resolve, but that are being masked by the poor guard parameter issue.
However, fixing the guard rotation period issue is alas not as simple as we might hope. The fundamental problem has to do with "load balancing": allocating traffic onto the Tor network so each relay is used the right amount. If Tor clients choose a guard and stick with it for a year or more, then old guards (relays that have been around and stable for a long time) will see a lot of use, and new guards will see very little use.
I wrote a separate blog post to provide background for this issue: "The lifecycle of a new relay". Imagine if the ramp-up period in the graph from that blog post were a year long! People would set up fast relays, they would get the Guard flag, and suddenly they'd see little to no traffic for months. We'd be throwing away easily half of the capacity volunteered by relays.
One approach to resolving the conflict would be for the directory authorities to track how much of the past n months each relay has had the Guard flag, and publish a fraction in the networkstatus consensus. Then we'd teach clients to rebalance their path selection choices so a relay that's been a Guard for only half of the past year only counts 50% as a guard in terms of using that relay in other positions in circuits. See Load balance right when we have higher guard rotation periods (ticket 9321) for more discussion, and see Raise our guard rotation period (ticket 8240) for earlier discussions.
Yet another challenge here is that sticking to the same guard for a year gives plenty of time for an attacker to identify the guard and attack it somehow. It's particularly easy to identify the guard(s) for hidden services currently (since as mentioned above, the adversary can control the rate at which hidden services make new circuits, simply by visiting the hidden service), but similar attacks can probably be made to work against normal Tor clients — see e.g. the http-level refresh tricks in How Much Anonymity does Network Latency Leak? This attack would effectively turn Tor into a network of one-hop proxies, to an attacker who can efficiently enumerate guards. That's not a complete attack, but it sure does make me nervous.
One possible direction for a fix is to a) isolate streams by browser tab, so all the requests from a given browser tab go to the same circuit, but different browser tabs get different circuits, and then b) stick to the same three-hop circuit (i.e. same guard, middle, and exit) for the lifetime of that session (browser tab). How to slow down guard enumeration attacks is a tough and complex topic, and it's too broad for this blog post, but I raise the issue here as a reminder of how interconnected anonymity attacks and defenses are. See Slow Guard Discovery of Hidden Services and Clients (ticket 9001) for more discussion.
Fix 3: The Tor code should better handle edge cases where you can't reach your guard briefly.
If a temporary network hiccup makes your guard unreachable, you switch to another one. But how long is it until you switch back? If the adversary's goal is to learn whether you ever go to a target website, then even a brief switch to a guard that the adversary can control or observe could be enough to mess up your anonymity.
Tor clients fetch a new networkstatus consensus every 2-4 hours, and they are willing to retry non-running guards if the new consensus says they're up again.
But I think there are a series of little bugs and edge cases where the Tor client abandons a guard more quickly than it should. For example, we mark a guard as failed if any of our circuit requests time out before finishing the handshake with the first hop. We should audit both the design and the source code with an eye towards identifying and resolving these issues.
We should also consider whether an adversary can *induce* congestion or resource exhaustion to cause a target user to switch away from her guard. Such an attack could work very nicely coupled with the guard enumeration attacks discussed above.
Most of these problems exist because in the early days we emphasized reachability ("make sure Tor works") over anonymity ("be very sure that your guard is gone before you try another one"). How should we handle this tradeoff between availability and anonymity: should you simply stop working if you've switched guards too many times recently? I imagine different users would choose different answers to that tradeoff, depending on their priorities. It sounds like we should make it easier for users to select "preserve my anonymity even if it means lower availability". But at the same time, we should remember the lessons from Anonymity Loves Company: Usability and the Network Effect about how letting users choose different settings can make them more distinguishable.
Fix 4: We need to make the network bigger.
We've been working hard in recent years to get more relay capacity. The result is a more than four-fold increase in network capacity since 2011:
As the network grows, an attacker with a given set of resources will have less success at the attacks described in this blog post. To put some numbers on it, while the relay adversary in Aaron's paper (who carries 660mbit/s of Tor traffic) represented 10% of the guard capacity in October 2012, that very same attacker would have been 20% of the guard capacity in October 2011. Today that attacker is about 5% of the guard capacity. Growing the size of the network translates directly into better defense against these attacks.
However, the analysis is more complex when it comes to a network adversary. Just adding more relays (and more relay capacity) doesn't always help. For example, adding more relay capacity in a part of the network that the adversary is already observing can actually *decrease* anonymity, because it increases the fraction the adversary can watch. We discussed many of these issues in the thread about turning funding into more exit relays. For more details about the relay distribution in the current Tor network, check out Compass, our tool to explore what fraction of relay capacity is run in each country or AS. Also check out Lunar's relay bubble graphs.
Yet another open research question in the field of anonymous communications is how the success rate of a network adversary changes as the Tor network changes. If we were to plot the success rate of the *relay* adversary using historical Tor network data over time, it's pretty clear that the success rate would be going down over time as the network grows. But what's the trend for the success rate of the network adversary over the past few years? Nobody knows. It could be going up or down. And even if it is going down, it could be going down quickly or slowly.
(Read more in Research problem: measuring the safety of the Tor network where I describe some of these issues in more detail.)
Recent papers have gone through enormous effort to get one, very approximate, snapshot of the Internet's topology. Doing that effort retroactively and over long and dynamic time periods seems even more difficult and more likely to introduce errors.
It may be that the realities of Internet topology centralization make it so that there are fundamental limits on how much safety Tor users can have in a given network location. On the other hand, researchers like Aaron Johnson are optimistic that "network topology aware" path selection can improve Tor's protection against this style of attack. Much work remains.
Fix 5: We should assign the guard flag more intelligently.
In point 1 above I talked about why we need to raise the bar for becoming a guard, so all guards can provide adequate bandwidth. On the other hand, having fewer guards is directly at odds with point 4 above.
My original guard rotation parameters blog post ends with this question: what algorithm should we use to assign Guard flags such that a) we assign the flag to as many relays as possible, yet b) we minimize the chance that Alice will use the adversary's node as a guard?
We should use historical Tor network data to pick good values for the parameters that decide which relays become guards. This remains a great thesis topic if somebody wants to pick it up.
Part four: Other thoughts
What does all of this discussion mean for the rest of Tor? I'll close by trying to tie this blog post to the broader Tor world.
First, all three of these papers come from the Tor research community, and it's great that Tor gets such attention. We get this attention because we put so much effort into making it easy for researchers to analyze Tor: we've worked closely with these authors to help them understand Tor and focus on the most pressing research problems.
In addition, don't be fooled into thinking that these attacks only apply to Tor: using Tor is still better than using any other tool, at least in quite a few of these scenarios. That said, some other attacks in the research literature might be even easier than the attacks discussed here. These are fast-moving times for anonymity research. "Maybe you shouldn't use the Internet then" is still the best advice for some people.
Third, the network-level adversaries rely on being able to recognize Tor flows. Does that argue that using pluggable transports, with bridges, might change the equation if it stops the attacker from recognizing Tor users?
Fourth, I should clarify that I don't think any of these large relay-level adversaries actually exist, except as a succession of researchers showing that it can be done. (GCHQ apparently ran a small number of relays a while ago, but not in a volume or duration that would have enabled this attack.) Whereas I *do* think that the network-level attackers exist, since they already invested in being able to surveil the Internet for other reasons. So I think it's great that Aaron's paper presents the dual risks of relay adversaries and link adversaries, since most of the time when people are worrying about one of them they're forgetting the other one.
Fifth, there are still some ways to game the bandwidth authority measurements (here's the spec spec) into giving you more than your fair share of traffic. Ideally we'd adapt a design like EigenSpeed so it can measure fast relays both robustly and accurately. This question also remains a great thesis topic.
And finally, as everybody wants to know: was this attack how "they" busted recent hidden services (Freedom Hosting, Silk Road, the attacks described in the latest Guardian article)? The answer is apparently no in each case, which means the techniques they *did* use were even *lower* hanging fruit. The lesson? Security is hard, and you have to get it right at many different levels.
And also the Washington Post article.
We're planning to write up a more detailed analysis later, but for now here's a place to centralize all the "hey did you know about this article" blog comments.
And for the journalists out there who want a statement, here's my quote from the article:
"The good news is that they went for a browser exploit, meaning there's no indication they can break the Tor protocol or do traffic analysis on the Tor network. Infecting the laptop, phone, or desktop is still the easiest way to learn about the human behind the keyboard.
Tor still helps here: you can target individuals with browser exploits, but if you attack too many users, somebody's going to notice. So even if the NSA aims to surveil everyone, everywhere, they have to be a lot more selective about which Tor users they spy on.
Just using Tor isn't enough to keep you safe in all cases. Browser exploits, large-scale surveillance, and general user security are all challenging topics for the average internet user. These attacks make it clear that we, the broader internet community, need to keep working on better security for browsers and other internet-facing applications."
We've had several requests by the press and others to talk about the Silk Road situation today. We only know what's going on by reading the same news sources everyone else is reading.
In this case we've been watching carefully to try to learn if there are any flaws with Tor that we need to correct. So far, nothing about this case makes us think that there are new ways to compromise Tor (the software or the network). The FBI says that their suspect made mistakes in operational security, and was found through actual detective work. Remember: Tor does not anonymize individuals when they use their legal name on a public forum, use a VPN with logs that are subject to a subpoena, or provide personal information to other services. See also the list of warnings linked from the Tor download page.
Also, while we've seen no evidence that this case involved breaking into the webserver behind the hidden service, we should take this opportunity to emphasize that Tor's hidden service feature (a way to publish and access content anonymously) won't keep someone anonymous when paired with unsafe software or unsafe behavior. It is up to the publisher to choose and configure server software that is resistant to attacks. Mistakes in configuring or maintaining a hidden service website can compromise the publisher's anonymity independent of Tor.
And finally, Tor's design goals include preventing even The Tor Project from tracking users; hidden services are no different. We don't have any special access to or information about this hidden service or any other. Because Tor is open-source and it comes with detailed design documents and research papers, independent researchers can verify its security.
Here are some helpful links to more information on these subjects:
Technical details of hidden services:
Our abuse FAQ:
For those curious about our interactions with law enforcement:
Using Tor hidden services for good:
Regarding the Freedom Hosting incident in August 2013, which is unrelated
as far as we can tell:
Some general hints on staying anonymous:
The Tor Project is a nonprofit 501(c)(3) organization dedicated to providing tools to help people manage their privacy on the Internet. Our focus continues to be in helping ordinary citizens, victims of abuse, individuals in dangerous parts of the world, and others stay aware and educated about how to keep themselves secure online.
The global Tor team remains committed to building technology solutions to help keep the doors to freedom of expression open. We will continue to watch as the details of this situation unfold and respond when it is appropriate and useful.
For further press related questions please contact us at firstname.lastname@example.org.
Many people set up new fast relays and then wonder why their bandwidth is not fully loaded instantly. In this post I'll walk you through the lifecycle of a new fast non-exit relay, since Tor's bandwidth estimation and load balancing has gotten much more complicated in recent years. I should emphasize that the descriptions here are in part anecdotal — at the end of the post I ask some research questions that will help us make better sense of what's going on.
I hope this summary will be useful for relay operators. It also provides background for understanding some of the anonymity analysis research papers that people have been asking me about lately. In an upcoming blog post, I'll explain why we need to raise the guard rotation period (and what that means) to improve Tor's anonymity.
A new relay, assuming it is reliable and has plenty of bandwidth, goes through four phases: the unmeasured phase (days 0-3) where it gets roughly no use, the remote-measurement phase (days 3-8) where load starts to increase, the ramp-up guard phase (days 8-68) where load counterintuitively drops and then rises higher, and the steady-state guard phase (days 68+).
Phase one: unmeasured (days 0-3).
When your relay first starts, it does a bandwidth self-test: it builds four circuits into the Tor network and back to itself, and then sends 125KB over each circuit. This step bootstraps Tor's passive bandwidth measurement system, which estimates your bandwidth as the largest burst you've done over a 10 second period. So if all goes well, your first self-measurement is 4*125K/10 = 50KB/s. Your relay publishes this number in your relay descriptor.
The directory authorities list your relay in the network consensus, and clients get good performance (and balance load across the network) by choosing relays proportional to the bandwidth number listed in the consensus.
Originally, the directory authorities would just use whatever bandwidth estimate you claimed in your relay descriptor. As you can imagine, that approach made it cheap for even a small adversary to attract a lot of traffic by simply lying. In 2009, Mike Perry deployed the "bandwidth authority" scripts, where a group of fast computers around the Internet (called bwauths) do active measurements of each relay, and the directory authorities adjust the consensus bandwidth up or down depending on how the relay compares to other relays that advertise similar speeds. (Technically, we call the consensus number a "weight" rather than a bandwidth, since it's all about how your relay's number compares to the other numbers, and once we start adjusting them they aren't really bandwidths anymore.)
The bwauth approach isn't ungameable, but it's a lot better than the old design. Earlier this year we plugged another vulnerability by capping your consensus weight to 20KB until a threshold of bwauths have an opinion about your relay — otherwise there was a several-day window where we would use your claimed value because we didn't have anything better to use.
So that's phase one: your new relay gets basically no use for the first few days of its life because of the low 20KB cap, while it waits for a threshold of bwauths to measure it.
Phase two: remote measurement (days 3-8).
Remember how I said the bwauths adjust your consensus weight based on how you compare to similarly-sized relays? At the beginning of this phase your relay hasn't seen much traffic, so your peers are the other relays who haven't seen (or can't handle) much traffic. Over time though, a few clients will build circuits through your relay and push some traffic, and the passive bandwidth measurement will provide a new larger estimate. Now the bwauths will compare you to your new (faster) peers, giving you a larger consensus weight, thus driving more clients to use you, in turn raising your bandwidth estimate, and so on.
Tor clients generally make three-hop circuits (that is, paths that go through three relays). The first position in the path, called the guard relay, is special because it helps protect against a certain anonymity-breaking attack. Here's the attack: if you keep picking new paths at random, and the adversary runs a few relays, then over time the chance drops to zero that *every single path you've made* is safe from the adversary. The defense is to choose a small number of relays (called guards) and always use one of them for your first hop — either you chose wrong, and one of your guards is run by the adversary and you lose on many of your paths; or you chose right and all of your paths are safe. Read the Guard FAQ for more details.
Only stable and reliable relays can be used as guards, so no clients are willing to use your brand new relay as their first hop. And since in this story you chose to set up a non-exit relay (so you won't be the one actually making connections to external services like websites), no clients will use it as their third hop either. That means all of your relay's traffic is coming from being the second hop in circuits.
So that's phase two: once the bwauths have measured you and the directory authorities lift the 20KB cap, you'll attract more and more traffic, but it will still be limited because you'll only ever be a middle hop.
Phase three: Ramping up as a guard relay (days 8-68).
This is the point where I should introduce consensus flags. Directory authorities assign the Guard flag to relays based on three characteristics: "bandwidth" (they need to have a large enough consensus weight), "weighted fractional uptime" (they need to be working most of the time), and "time known" (to make attacks more expensive, we don't want to give the Guard flag to relays that haven't been around a while first). This last characteristic is most relevant here: on today's Tor network, you're first eligible for the Guard flag on day eight.
Clients will only be willing to pick you for their first hop if you have the "Guard" flag. But here's the catch: once you get the Guard flag, all the rest of the clients back off from using you for their middle hops, because when they see the Guard flag, they assume that you have plenty of load already from clients using you as their first hop. Now, that assumption will become true in the steady-state (that is, once enough clients have chosen you as their guard node), but counterintuitively, as soon as you get the Guard flag you'll see a dip in traffic.
Why do clients avoid using relays with the Guard flag for their middle hop? Clients look at the scarcity of guard capacity, and the scarcity of exit capacity, and proportionally avoid using relays for positions in the path that aren't scarce. That way we allocate available resources best: relays with the Exit flag are used mostly for exiting when they're scarce, and relays with the Guard flag are used mostly for entering when they're scarce.
It isn't optimal to allow this temporary dip in traffic (since we're not taking advantage of resources that you're trying to contribute), but it's a short period of time overall: clients rotate their guards nodes every 4-8 weeks, so pretty soon some of them will rotate onto your relay.
To be clear, there are two reasons why we have clients rotate their guard relays, and the reasons are two sides of the same coin: first is the above issue where new guards wouldn't see much use (since only new clients, picking their guards for the first time, would use a new guard), and second is that old established guards would accrue an ever-growing load since they'd have the traffic from all the clients that ever picked them as their guard.
One of the reasons for this blog post is to give you background so when I later explain why we need to extend the guard rotation period to many months, you'll understand why we can't just crank up the number without also changing some other parts of the system to keep up. Stay tuned for more details there, or if you don't want to wait you can read the original research questions and the followup research papers by Elahi et al and Johnson et al.
Phase four: Steady-state guard relay (days 68+).
Once your relay has been a Guard for the full guard rotation period (up to 8 weeks in Tor 0.1.1.11-alpha through 0.2.4.11-alpha, and up to 12 weeks in Tor 0.2.4.12-alpha and later), it should reach steady-state where the number of clients dropping it from their guard list balances the number of clients adding it to their guard list.
Research question: what do these phases look like with real-world data?
All of the above explanations, including the graphs, are just based on anecdotes from relay operators and from ad hoc examination of consensus weights.
Here's a great class project or thesis topic: using our publically available Tor network metrics data, track the growth pattern of consensus weights and bandwidth load for new relays. Do they match the phases I've described here? Are the changes inside a given phase linear like in the graphs above, or do they follow some other curve?
Are there trends over time, e.g. it used to take less time to ramp up? How long are the phases in reality — for example, does it really take three days before the bwauths have a measurement for new relays?
How does the scarcity of Guard or Exit capacity influence the curves or trends? For example, when guard capacity is less scarce, we expect the traffic dip at the beginning of phase three to be less pronounced.
How different were things before we added the 20KB cap in the first phase, or before we did remote measurements at all?
Are the phases, trends, or curves different for exit relays than for non-exit relays?
The "steady-state" phase assumes a constant number of Tor users: in situations where many new users appear (like the botnet invasion in August 2013), current guards will get unbalanced. How quickly and smoothly does the network rebalance as clients shift guards after that?
[tl;dr: if you want your Tor to be more stable, upgrade to a Tor Browser Bundle with Tor 0.2.4.x in it, and then wait for enough relays to upgrade to today's 0.2.4.17-rc release.]
Starting around August 20, we started to see a sudden spike in the number of Tor clients. By now it's unmistakable: there are millions of new Tor clients and the numbers continue to rise:
Where do these new users come from? My current best answer is a botnet.
Some people have speculated that the growth in users comes from activists in Syria, Russia, the United States, or some other country that has good reason to have activists and journalists adopting Tor en masse lately. Others have speculated that it's due to massive adoption of the Pirate Browser (a Tor Browser Bundle fork that discards most of Tor's security and privacy features), but we've talked to the Pirate Browser people and the downloads they've seen can't account for this growth. The fact is, with a growth curve like this one, there's basically no way that there's a new human behind each of these new Tor clients. These Tor clients got bundled into some new software which got installed onto millions of computers pretty much overnight. Since no large software or operating system vendors have come forward to tell us they just bundled Tor with all their users, that leaves me with one conclusion: somebody out there infected millions of computers and as part of their plan they installed Tor clients on them.
It doesn't look like the new clients are using the Tor network to send traffic to external destinations (like websites). Early indications are that they're accessing hidden services — fast relays see "Received an ESTABLISH_RENDEZVOUS request" many times a second in their info-level logs, but fast exit relays don't report a significant growth in exit traffic. One plausible explanation (assuming it is indeed a botnet) is that it's running its Command and Control (C&C) point as a hidden service.
My first observation is "holy cow, the network is still working." I guess all that work we've been doing on scalability was a good idea. The second observation is that these new clients actually aren't adding that much traffic to the network. Most of the pain we're seeing is from all the new circuits they're making — Tor clients build circuits preemptively, and millions of Tor clients means millions of circuits. Each circuit requires the relays to do expensive public key operations, and many of our relays are now maxed out on CPU load.
There's a possible dangerous cycle here: when a client tries to build a circuit but it fails, it tries again. So if relays are so overwhelmed that they each drop half the requests they get, then more than half the attempted circuits will fail (since all the relays on the circuit have to succeed), generating even more circuit requests.
So, how do we survive in the face of millions of new clients?
Step one was to see if there was some simple way to distinguish them from other clients, like checking if they're using an old version of Tor, and have entry nodes refuse connections from them. Alas, it looks like they're running 0.2.3.x, which is the current recommended stable.
Step two is to get more users using the NTor circuit-level handshake, which is new in Tor 0.2.4 and offers stronger security with lower processing overhead (and thus less pain to relays). Tor 0.2.4.17-rc comes with an added twist: we prioritize NTor create cells over the old TAP create cells that 0.2.3 clients send, which a) means relays will get the cheap computations out of the way first so they're more likely to succeed, and b) means that Tor 0.2.4 users will jump the queue ahead of the botnet requests. The Tor 0.2.4.17-rc release also comes with some new log messages to help relay operators track how many of each handshake type they're handling.
(There's some tricky calculus to be done here around whether the botnet operator will upgrade his bots in response. Nobody knows for sure. But hopefully not for a while, and in any case the new handshake is a lot cheaper so it would still be a win.)
Step three is to temporarily disable some of the client-side performance features that build extra circuits. In particular, our circuit build timeout feature estimates network performance for each user individually, so we can tune which circuits we use and which we discard. First, in a world where successful circuits are rare, discarding some — even the slow ones — might be unwise. Second, to arrive at a good estimate faster, clients make a series of throwaway measurement circuits. And if the network is ever flaky enough, clients discard that estimate and go back and measure it again. These are all fine approaches in a network where most relays can handle traffic well; but they can contribute to the above vicious cycle in an overloaded network. The next step is to slow down these exploratory circuits in order to reduce the load on the network. (We would temporarily disable the circuit build timeout feature entirely, but it turns out we had a bug where things get worse in that case.)
Step four is longer-term: there remain some NTor handshake performance improvements that will make them faster still. It would be nice to get circuit handshakes on the relay side to be really cheap; but it's an open research question how close we can get to that goal while still providing strong handshake security.
Of course, the above steps aim only to get our head back above water for this particular incident. For the future we'll need to explore further options. For example, we could rate-limit circuit create requests at entry guards. Or we could learn to recognize the circuit building signature of a bot client (maybe it triggers a new hidden service rendezvous every n minutes) and refuse or tarpit connections from them. Maybe entry guards should demand that clients solve captchas before they can build more than a threshold of circuits. Maybe we rate limit TAP handshakes at the relays, so we leave more CPU available for other crypto operations like TLS and AES. Or maybe we should immediately refuse all TAP cells, effectively shutting 0.2.3 clients out of the network.
In parallel, it would be great if botnet researchers would identify the particular characteristics of the botnet and start looking at ways to shut it down (or at least get it off of Tor). Note that getting rid of the C&C point may not really help, since it's the rendezvous attempts from the bots that are hurting so much.
And finally, I still maintain that if you have a multi-million node botnet, it's silly to try to hide it behind the 4000-relay Tor network. These people should be using their botnet as a peer-to-peer anonymity system for itself. So I interpret this incident as continued exploration by botnet developers to try to figure out what resources, services, and topologies integrate well for protecting botnet communications. Another facet of solving this problem long-term is helping them to understand that Tor isn't a great answer for their problem.
This vulnerability was fixed in Firefox 17.0.7 ESR. The following versions of the Tor Browser Bundle include this fixed version:
- 2.3.25-10 (released June 26 2013)
- 2.4.15-alpha-1 (released June 26 2013)
- 2.4.15-beta-1 (released July 8 2013)
- 3.0alpha2 (released June 30 2013)
Tor Browser Bundle users should ensure they're running a recent enough bundle version, and consider taking further security precautions.
Read the full advisory here:
Journalists and activists have been asking me this week about the news that the Obama administration is now considering whether to support the latest version of the FBI's "Going Dark" legislation. Here are some points to add to the discussion.
- This is far from law currently. Nobody's even published any proposed text. Right now the White House is considering whether to back it, and now is a great time to help them understand how dangerous it would be for America.
- Forcing backdoors in communication tools is a mandate for insecurity. Haven't they been paying attention to just how much these same systems are under attack from foreign governments and criminals? Did they not learn any lessons from the wiretapping scandals in Greece and Italy, where CALEA backdoors were used to surveil politicians, without law enforcement even knowing about it? You cannot add a backdoor to a communications system without making it more vulnerable to attack, both from insiders and from the outside.
- The Justice Department is being really short-sighted here by imagining that the world is black and white. We've heard from people at the FBI, DEA, NSA, etc who use Tor for their job. If we changed the design so we could snoop on people, those users should go use a system that isn't broken by design — such as one in another country. And if those users should, why wouldn't criminals switch too?
- In any case, it seems likely that the law won't apply to The Tor Project, since we don't run the Tor network and also it's not a service. (We write free open source software, and then people run it to form a network.)
- The current CALEA already has an ugly trickle-down effect on the citizens of other countries. Different governments have different standards for lawful access, but the technology doesn't distinguish. So when the Egyptian general plugs in his telco box and sees the connector labelled "lawful access", he thinks to himself "I *am* the law" and proceeds with surveilling his citizens to stay in power. To put it bluntly, America's lawful intercept program undermines its foreign policy goals.
And lastly, we should all keep in mind that they can't force us to do anything. You always have the alternative of stopping whatever it is you're doing. So for example if they try to "force" an individual directory authority operator to do something, the operator should just stop operating the authority (and then consider working with EFF and ACLU to establish precedent that such an attempt was illegal). And so on, all the way up the chain. Good thing the Internet is an international community.
In January I did Tor talks for the Dutch regional police, the Dutch national police, and the Belgian national police. Jake and I also did a brief inspirational talk at Bits of Freedom, as well as the closing keynote for the Dutch National Cyber Security Centre's yearly conference.
You may recall that one of my side hobbies lately has been teaching law enforcement about Tor — see my previous entries about teaching the FBI about Tor in 2012 and visiting the Stuttgart detectives in 2008 back when we were discussing data retention in Germany. Before this blog started I also did several Tor talks for the US DoJ, and even one for the Norwegian Kripos.
Now is a good time to talk to the Dutch police, first because they're still smarting from the DigiNotar disaster in 2011, but second because of their 2012 ambitions to legalize breaking into foreign computers when they aren't sure what country they're in. (I say legalize because they already did it!)
Below are some discussion points that made an impression on me.
- I started the trip with a talk to about 80 people from the Dutch regional police. Apparently each regional police group has basically one cybercrime person, and pretty much all of them came to learn about Tor. These are the people who advise their police groups about how to handle Tor cases, so they're exactly the ones who need to know about services like ExoneraTor. (Afterwards, one of the national police thanked me heartily for teaching the regional police about Tor, since it makes *his* job easier.)
- One issue that came up repeatedly during the talks: what if a bad guy runs a Tor exit relay to provide plausible deniability when somebody shows up as his door? My first thought is that anybody who runs a Tor exit relay in order to attract *less* attention from the police is crazy: if you want to be ignored, you should use a botnet or whatever to do your bad things, nobody will learn that it's you, end of story. Until we educate every law enforcement person on the planet about Tor, there will always be people who raid every IP address on their suspect list without ever knowing what Tor is. The second point they found interesting was that Tor relays never write any traffic to disk; so if your suspect has bad stuff on his hard drive and says it was because of the Tor relay, he's lying. Of course, disk encryption complicates the situation (which is why, counterintuitively, we recommend *not* using disk encryption on your exit).
- Did you know that the Dutch police have their own internal anonymity network? They started out using a secret subnet ("nobody knows that it's the Dutch police, until somebody figures out that it is"). Apparently now they do smarter things like grabbing addresses from Dutch ISPs so they can blend in better. But that's still not perfect: if they borrow an IP address for 36 hours, then that's a 36-hour window where if you can recognize any of the traffic as Dutch police, you can link the rest of the traffic to them too. I hear their new generation of client-side software has an option for using Tor; I wonder if that means the Tor Browser Bundle, or just tunnelling the traffic through Tor naked? More details here and here. (Two points for transparency and open standards!)
- When we met with the US DEA earlier in January, many people there said they use Tor for their job. Most people in the Dutch national police meeting said they used it often. On the other hand, most people in the Dutch regional police meeting said they certainly did not use it, "because that would be inappropriate." We have some more educating left to do.
- One regional Dutch police woman told us that they know how to check if it's a Tor exit IP, but sometimes they do the raid anyway "to discourage people from helping Tor." I later told that statement to one of the national police, and he was shocked, said that was illegal, and said he'd look into it. Alas, I'm not optimistic that anything will come of it: giving investigators discretion about how to act can be both good and bad.
- It took me a few hours to get the regional police comfortable enough to discuss, but by the end they were answering each other's questions — which is one of my main goals, since I won't be there later to answer them. The best example was one detective who stood up and explained that in his opinion they are focusing way too much on Tor ("because we can't break it"), while at the same time there are many other crimes they *can* fight, like criminals using file sharing networks, and they're ignoring those. Certainly Tor gets a lot of publicity (last year a Dutch TV show stirred up a media fear frenzy about Tor that resulted in a Dutch Parliament member calling to ban it), but according to this detective there's a lot more crime elsewhere. My response: "Did everybody hear that?" It works best when police hear statements like this from their peers rather than from me.
- Here's an argument based on discussions with Karen Reilly for responding about child porn and banning Tor. A lot of people think that it's about trading off the good for the bad. On the one hand, you have a girl in Syria who is alive right now because of Tor. On the other hand, you have a girl in America who is harmed by some jerk and the jerk uses Tor. So, how do you balance these two? How do you decide which one is more important, or more 'valuable' to the world? The answer is that it's the wrong question to ask: you aren't actually going to save the girl in America by getting rid of Tor. Whereas getting rid of Tor *would* harm the girl in Syria (along with a wide variety of people and groups around the world).
- The day after I did the talk to the regional police, I did a short talk at Bits of Freedom, an EFF-like digital rights nonprofit in Amsterdam. They held a "Boffel" for many of their supporters to show up and socialize. It was a really great crowd — these are smart people who care. It was like a tiny CCC congress. And now that I've been clearly complimentary to them, you'll be able to properly interpret my next statement: many of the Dutch police would have fit in just fine at the Boffel. People came up to me at the NCSC conference days later and said "I liked your talk!" and I genuinely couldn't tell if they meant my talk at the regional police or my talk at Bits of Freedom. There were some exceptions, sure, but most of the Dutch police I talked to have somehow managed to not get ground down by their job and lose track of the civil liberties angle. I wonder what their trick is.
- Rejo Zenger (from BoF) and two others are working to create a Dutch organization to run fast Tor exit relays, to gather donations and centrally handle abuse complaints — like Zwiebelfreunde in Germany, Nos Oignons in France, DFRI in Sweden, and NoiseTor in the US. That's great! Please help them out however you can.
- At the NCSC conference, Jake and I did an open Q&A session on the first day, and did the closing keynote (slides) on the second day. Both talks went very well (imagine what would happen if Jake and I practiced any of our talks together before giving them! :). We now have invites to come to all sorts of CERTs around the world; the woman managing the conference is moving to Europol shortly and wants us to come talk there; and one of the heads of NCSC wants us to come back and help the Netherlands with their general direction and strategy. We should try to connect them to local Dutch Tor advocates as much as we can, since after all we have software to write.
- I'm afraid I missed most of the other talks at the conference (and I missed the alternate conference entirely), but I did see Peter Zinn's well-choreographed talk about what the Dutch national police should be focusing on. His conclusion was that the Netherlands should focus on being the "safest country in the world wrt cybercrime by 2017". I had to restrain myself from yelling out the word externalities! during his talk: if their plan is to convince cybercriminals to go elsewhere, and then the neighboring countries like Belgium become cyber-hives-of-scum-and-villainy, that's not going to end well for anybody.
- One person in the Belgian FCCU (Federal Computer Crime Unit) suggested during a break in the discussion that maybe Belgium should block all connections from the Tor network *to* any Belgian IP space. By now there's almost no such thing as a new question for me during these talks, but I have to admit that this one took me by surprise. Eventually I produced the right answer: "The Internet community would destroy you. 'Great Firewall of Belgium'? 'Adopt a Belgian dissident'? Nobody would take you seriously again as an alleged democracy." In any case, my friend at RIPE tells me that technically, it's harder than it sounds for Belgium to do this scale of blocking.
- I got into a discussion with the Belgian police about how they don't regard their Internet filtering as "censorship". In my experience, the way it starts is some legislators decide there's something so horrible on the Internet that it justifies filtering. From there, they delegate to some quasi-governmental organization which comes up with a list (in some totally non-transparent fashion) of verboten URLs. Inevitably, the list contains more types of content than the original reason for setting up the filtering; and inevitably, there's no redress mechanism to get off the list if you shouldn't be on it. The Belgian police assured me that they only filter a small set of URLs, and that each of them is discussed and transparently decided about in a democratic fashion. And then they wouldn't tell me what's on their list.
- I met a US FBI agent and a US Secret Service agent who are "permanently" stationed with the Dutch national police. They acted just like normal Dutch police, except I guess they're paid by the United States to be Dutch police. Weird world we live in.
- In each of the three police meetings, somebody suggested an alternate model for Tor where a judge should get to decide whether a given Tor user should be deanonymized. (While in America we don't trust our judges, in Europe they really do.) Putting aside for a moment the technical fact that building in a backdoor would mean that criminals can exploit it too (this argument doesn't work on them), I tried to press on the multi-jurisdictional aspect: we have governments, militaries, and law enforcement from around the world relying on Tor. When I asked the embedded Secret Service guy if he would be ok with the Dutch police having a backdoor to Tor, he said "We like our Dutch colleagues." When I rephrased it to whether he would be ok with the Dutch police knowing what the US police are using Tor for, he paused, smiled, and tactfully said "No comment."
- Several people at the Dutch cybercrime unit quietly told me they regretted their "break into a Tor hidden service and zero it out" action: it got people upset at them, but more importantly, it *didn't work*. That is, it didn't stop any bad people from doing bad things. Apparently playing whack-a-mole like this doesn't make the criminals go away. And worse, it disrupts the police's other monitoring and infiltration operations.
- If I wanted to run a hidden service website that had a nation-state adversary, I would a) run a good solid webserver like nginx; b) run it in a VM, in a way that the VM couldn't learn its location — "no looking up its IP", but also more subtle things like "no looking up nameservers", "no looking up reachable wireless access points", etc; and then c) put that VM in a VPS running in a country that hates my adversary. That way even if somebody breaks into the webserver and breaks out of the VM, they're still faced with a frustratingly long bureaucratic step.
- I took Aaron Gibson and Pepijn Le Heux with me to the Brussels meeting, and took Pepijn again to the Dutch national police meeting. Pepijn is a great guy; I'm hoping to turn him into a Roger replica so he can act as a Dutch Tor resource and so he can help organizations like Bits of Freedom save their country.