Opened 8 years ago

Closed 2 years ago

#3678 closed enhancement (duplicate)

Disallow more than one relay per country in a circuit

Reported by: cypherpunks Owned by:
Priority: High Milestone: Tor: very long term
Component: Core Tor/Tor Version:
Severity: Normal Keywords: needs-research needs-proposal tor-client
Cc: blah@…, proper@… Actual Points:
Parent ID: #22339 Points:
Reviewer: Sponsor:

Description (last modified by nickm)

I have been running the Tor Browser Bundles that use 0.2.2.x tor branch.  It seems more and more frequently, 2 of 3 nodes in a circuit are in the same country.  My tor prefers Germany and the USA for nodes.  I frequently find circuits which start and end in the USA, or start and end in Germany.  I would like an option to avoid national surveillance by any one country.  I am willing to sacrifice performance for anonymity.

You have the option called EnforceDistinctSubnets that is set to 1 by default. Perhaps EnforceDistinctCountries could be an option.

Child Tickets

Change History (25)

comment:1 Changed 8 years ago by cypherpunks

Cc: blah@… added

comment:2 Changed 8 years ago by nickm

Description: modified (diff)

comment:3 Changed 8 years ago by nickm

Priority: normalmajor

This one is a lot more complicated than it sounds.

Please take the following concerns not as arguing that the idea of country-aware routing is broken or unworkable, but as an explanation for why the simple version of it is not necessarily a good idea, and why the complex version of it that _might_ be a good idea still has a bunch of unsolved problems.

You not only need to think about the countries used by your Tor relays, but the country that you're in and the country that your destination is in. For example, if you and your destination are in the same country, and some agency in that country is monitoring and correlating its internal communications, then current low-latency anonymity designs can't help against them.

And it gets even more complicated: internet topology does not obey national borders (it's not uncommon for a connection between two places in one country to travel through a third country -- I hear it happens in Canada a lot), and nations are not connected in a clique (traffic from country A to county B often goes through some other country C).

And to add a new fun complication, there are agencies out there who allegedly do most of their snooping at national borders and IX exchanges. Maximizing country-to-country transitions would seem to _increase_ exposure to such attackers rather than limit it.

And finally, nobody's done the math as far as I know to show whether and under what circumstances a routing algorithm of this style would give you observably different results from using the regular path generation algorithm in a way that would allow an attacker to separate your traffic from the rest of the network and thereby actually make your anonymity worse.

...

In spite of all of that, this is research that we do need to do. Murdoch and Zelinski have some important observations (http://freehaven.net/anonbib/#murdoch-pet2007). I think that one of the most promising directions I know of right now for topology-aware routing is the kind of work done by Edman and Syverson (http://freehaven.net/anonbib/#DBLP:conf/ccs/EdmanS09); I think some other groups are poking on it too. A forthcoming paper I did with Roger Dingledine, Paul Syverson, and Aaron Turner (assuming that it gets in where we submitted it) might also have some relevance, though it's more about mistrusting some countries more than others than it is about what to do if you mistrust all countries equally but think that they don't cooperate.

Anything that can be done to pick up the analysis work of any of these threads would be greatly helpful.

...

Oh! And as a workaround, if none of the above issues concern you, then you can get something close to what you want here by splitting countries with lots of Tor nodes into two halves, and saying
EntryNodes {aa},{bb},{cc},...
ExitNodes {nn},{oo},{pp},...
You'll need to use Tor 0.2.3.x for support for country codes in your EntryNodes list, and you might want to decide whether to use "StrictNodes 1" to make sure that Tor forbids circuits you don't want even when they would be needed to connect to a directory or hidden service.

Anybody else got observations here? Was there anything I missed?

comment:4 Changed 8 years ago by nickm

Oops. That should be Aaron Johnson above, not Aaron Turner. Different people.

comment:5 Changed 8 years ago by cypherpunks

An additional observation is that it means that your geoip provider gets to influence your path selection to a certain extend. They could put a relay into a country with no other relays to make sure it gets picked more. This is probably a small influence, but I haven't done any math to prove that.

--Sebastian

comment:6 Changed 8 years ago by ioerror

It seems to me that it's a reasonable option. I've long advocated that this should be a switch to flip, even if we're not sure it's safe to flip it by default. I think that it's important to consider that countries should be grouped - so if we exclude canada more than once, we should also exclude the USA at the same time - they're too close. I think I suggested the name "PoliticallyAwareCircuits" or something similar.

comment:7 in reply to:  6 ; Changed 8 years ago by rransom

Status: newneeds_information

Replying to ioerror:

It seems to me that it's a reasonable option. I've long advocated that this should be a switch to flip, even if we're not sure it's safe to flip it by default.

This switch would change a client's path-selection behaviour in a way that both entry nodes and exit nodes might be able to observe. If this option is not turned on by default, it's not safe to turn this option on at all.

And so far, I have seen several people say that we should add this option, but I have not seen anyone propose an actual reason to turn this option on. What attack does this option defend against?

The EnforceDistinctSubnets feature was added because of an actual incident in which one ISP's customers ran a large portion of the Tor network within one /16 (or smaller?) network. The reason that it's an option at all (rather than hard-coded in the Tor source code like Tor's refusal to build normal circuits that end at BadExits or that have two hops in the same ‘family’) is that developers and researchers who run testing Tor networks on a LAN need to be able to turn it off. It's not there just as a pistol for users who think they need ‘more anonymity’ to shoot themselves in their feet with.

I think that it's important to consider that countries should be grouped - so if we exclude canada more than once, we should also exclude the USA at the same time - they're too close. I think I suggested the name "PoliticallyAwareCircuits" or something similar.

Who do you think should produce and maintain a list of groups of countries that are ‘too close’?

Do you think some European countries are ‘too close’ to the U.S.? If so, how do you think they would react to being labeled as such?

Should The Tor Project ship an ‘official’ list specifying which countries are ‘too close’? If two or more groups publish different lists, and each group tells us that theirs is ‘better’ than the others, how should we choose which one to ship?

If we shouldn't ship an ‘official’ list, how will users find a list to use with their Tor client? If different users choose different lists, will Tor's anonymity set be partitioned further?

And last, but not least, what attack does this defend against?

comment:8 Changed 8 years ago by cypherpunks

As a Belgian, any circuit that begins or ends in Germany is too close for me. It's all within the larger European law enforcement zone.  Perhaps EnforceDistinctContinents is a better idea.  Or EnforceDistinctSubnets can be configurable for /4, /8 or user defined ranges.

What nickm said is that IX points are the threat. Why is there not more research done on this level?  Is it not core to Tor's anonymity? 

comment:9 Changed 8 years ago by cypherpunks

It was unclear whether in the last comment "[w]hy is there not more research done on this level?" meant that the commenter was unaware of what research there is, or if s/he was wishing for more (one of the many areas needing more). Here are some of the research papers in this area, in reverse order of appearance. All are available at http://freehaven.net/anonbib/
"AS-awareness in Tor path selection"
"Sampled Traffic Analysis by Internet-Exchange-Level Adversaries"
"Location Diversity in Anonymity Networks"

On the general difficulty of picking routes when some nodes are trusted more than others, see
"More Anonymous Onion Routing Through Trust" which is apparently not on anonbib, but
can be found at http://www.cs.utexas.edu/~ajohnson/
There is also a paper addressing trust in routing more generally to appear in the next ACM CCS "Trust-based Anonymous Communication: Adversary Models and Routing Algorithms"

HTH,
Paul (Yes, 3 of 5 of the above-mentioned papers are mine. Somebody with a different background bias will no doubt be able to mention others.)

comment:10 in reply to:  7 Changed 8 years ago by ioerror

Replying to rransom:

Replying to ioerror:

It seems to me that it's a reasonable option. I've long advocated that this should be a switch to flip, even if we're not sure it's safe to flip it by default.

This switch would change a client's path-selection behaviour in a way that both entry nodes and exit nodes might be able to observe. If this option is not turned on by default, it's not safe to turn this option on at all.

That is not true. You are not actually able to evaluate my safety concerns without more data. For example, we have ExcludeNodes and we allow country specific exclusions. It may be bad for anonymity but it may be good for my health to avoid certain nodes. For example: if a specific country would raise major red flags for me if I used it as my entry node, I should be able to avoid it. This is *not* safe by default but it's perfectly safe as far as I'm concerned to tune Tor for this use case. There isn't a better option for users.

And so far, I have seen several people say that we should add this option, but I have not seen anyone propose an actual reason to turn this option on. What attack does this option defend against?

It depends. It would defend against accidentally building a three hop circuit inside of a single country or continent.

The EnforceDistinctSubnets feature was added because of an actual incident in which one ISP's customers ran a large portion of the Tor network within one /16 (or smaller?) network. The reason that it's an option at all (rather than hard-coded in the Tor source code like Tor's refusal to build normal circuits that end at BadExits or that have two hops in the same ‘family’) is that developers and researchers who run testing Tor networks on a LAN need to be able to turn it off. It's not there just as a pistol for users who think they need ‘more anonymity’ to shoot themselves in their feet with.

It's also there because Sybil protection is frankly, a really hard problem. For ipv6, we're screwed unless we use much more general things. And frankly, I'm not convinced it would be impossible to mount a nasty attack given tunneling possibilities unless the network grows a bit more.

I think that it's important to consider that countries should be grouped - so if we exclude canada more than once, we should also exclude the USA at the same time - they're too close. I think I suggested the name "PoliticallyAwareCircuits" or something similar.

Who do you think should produce and maintain a list of groups of countries that are ‘too close’?

I think that a list of continents is a pretty reasonable grouping; mother nature solved this problem, I think.

Do you think some European countries are ‘too close’ to the U.S.? If so, how do you think they would react to being labeled as such?

No, I'm comfortable with a three hop circuit with one hop in the USA, one in Europe and one elsewhere before visiting my destination outside of the Tor network.

Should The Tor Project ship an ‘official’ list specifying which countries are ‘too close’? If two or more groups publish different lists, and each group tells us that theirs is ‘better’ than the others, how should we choose which one to ship?

This is why an option for users is a good idea - it allows people to easily experiment and give good data for answers to these questions.

If we shouldn't ship an ‘official’ list, how will users find a list to use with their Tor client? If different users choose different lists, will Tor's anonymity set be partitioned further?

There is no partitioning when there is nothing done by default.

And last, but not least, what attack does this defend against?

At the very least, it probably defends against an adversary that is able to allocate a bunch of IPs in a single country on different /16.

comment:11 in reply to:  8 ; Changed 8 years ago by cypherpunks

Replying to cypherpunks:

As a Belgian, any circuit that begins or ends in Germany is too close for me. It's all within the larger European law enforcement zone.  Perhaps EnforceDistinctContinents is a better idea.  Or EnforceDistinctSubnets can be configurable for /4, /8 or user defined ranges.

What nickm said is that IX points are the threat. Why is there not more research done on this level?  Is it not core to Tor's anonymity? 

Perhaps "why hasn't tor implemented anything related to this research?" is a better question. It seems IX points are the problem. The AS paper doesn't seem to matter much.

comment:12 Changed 8 years ago by cypherpunks

From a sampling of my own circuits.  I circuit from the US to Germany to Sweden crosses the LINX exchange in London 3x. 

Here's an actual circuit, right now: tor9, drachentor, morales. US to Germany to Germany.  My traffic passes from Belgium, through LINX to NYC, to the relay, to NYC to LINX to Germany.

comment:13 in reply to:  12 Changed 8 years ago by cypherpunks

Replying to cypherpunks:

From a sampling of my own circuits.  I circuit from the US to Germany to Sweden crosses the LINX exchange in London 3x. 

Here's an actual circuit, right now: tor9, drachentor, morales. US to Germany to Germany.  My traffic passes from Belgium, through LINX to NYC, to the relay, to NYC to LINX to Germany.

What primarily matters is not whether the circuit crosses an exchange or AS 3x per circuit, but whether it crosses that AS (IX) between you and tor9 and again between morales and the final destination. If it does then you are vulnerable to (at least one) potential attacker on the links between nodes because it can associate source and destination IP addresses and perhaps other circuit information. If not, well you might still be at risk. Research is ongoing (some mentioned in comment 9) about understanding the risk of collaboration between link-level attackers.

comment:14 in reply to:  11 Changed 8 years ago by cypherpunks

Replying to cypherpunks:

Replying to cypherpunks:

What nickm said is that IX points are the threat. Why is there not more research done on this level?  Is it not core to Tor's anonymity? 

Perhaps "why hasn't tor implemented anything related to this research?" is a better question.

With an easier answer: what to implement is far from clear. Tor's /16 independence for nodes in circuits actually does help with this problem. So, Tor _has_ implemented something related to this research. But it's very far from perfect, as a small example, found that even nodes in different /8s can share an AS. And if your circuit is entering or leaving the Tor network in parts of Europe, then the risk that it passes through the same IX makes this worse; although I don't know precisely how much. The AS-awareness paper does suggest and analyze ways to significantly improve path independence for links, but they involve a nontrivial increase in overhead of what is distributed to clients and the cost to the client of choosing nodes for circuits.

It seems IX points are the problem. The AS paper doesn't seem to matter much.

Can you explain? Do you mean because IXes are bigger aggregation points? The three AS and IX papers mentioned are addressing essentially the same problem, just different aspects of it. And the two AS papers (not sure which one you meant) show even just the path-independence concern is significant. And growth of the network has not helped (sometimes made it worse). And this is not the only risk of attack on the links, just the most salient one.

comment:15 in reply to:  7 ; Changed 8 years ago by hellais

Replying to rransom:

Replying to ioerror:

It seems to me that it's a reasonable option. I've long advocated that this should be a switch to flip, even if we're not sure it's safe to flip it by default.

This switch would change a client's path-selection behaviour in a way that both entry nodes and exit nodes might be able to observe. If this option is not turned on by default, it's not safe to turn this option on at all.

And so far, I have seen several people say that we should add this option, but I have not seen anyone propose an actual reason to turn this option on. What attack does this option defend against?

The EnforceDistinctSubnets feature was added because of an actual incident in which one ISP's customers ran a large portion of the Tor network within one /16 (or smaller?) network. The reason that it's an option at all (rather than hard-coded in the Tor source code like Tor's refusal to build normal circuits that end at BadExits or that have two hops in the same ‘family’) is that developers and researchers who run testing Tor networks on a LAN need to be able to turn it off. It's not there just as a pistol for users who think they need ‘more anonymity’ to shoot themselves in their feet with.

This feature is necessary because this attack is not something that will be easy to detect as it is highly passive and done on backbones.

I think that it's important to consider that countries should be grouped - so if we exclude canada more than once, we should also exclude the USA at the same time - they're too close. I think I suggested the name "PoliticallyAwareCircuits" or something similar.

Who do you think should produce and maintain a list of groups of countries that are ‘too close’?

Do you think some European countries are ‘too close’ to the U.S.? If so, how do you think they would react to being labeled as such?

Should The Tor Project ship an ‘official’ list specifying which countries are ‘too close’? If two or more groups publish different lists, and each group tells us that theirs is ‘better’ than the others, how should we choose which one to ship?

I believe a good starting point to for grouping countries could be the current active military alliances, this usually implies that there is some level of sharing of information between these countries [1]

I don't think it's a good idea for The Tor Project to ship an 'official' list. People should build one based on their own needs and independent organizations will be responsible for explaining the reasoning behind them and to what sort of case scenario they apply to.

If we shouldn't ship an ‘official’ list, how will users find a list to use with their Tor client? If different users choose different lists, will Tor's anonymity set be partitioned further?

And last, but not least, what attack does this defend against?

I believe this feature will not be used by everybody, just by people that are worried about a large scale targeted attack. Let me further explain:
It is a fact that the technology exists and it is being deployed capable of collection information on Terabit networks [2] . It is not so far fetched to believe that if a big government wishes to target a specific individual he will request information on that person from various other countries with which they are allied. By making circuit building sensible to the relationships that exists amongst countries, you are making this information sharing much harder (e.s. would it be easy for the Swiss government to get traffic dumps from Ukraine?).

So to synthesize we are trying to prevent traffic analysis and correlation when allied countries collude against one individual.

[1] https://secure.wikimedia.org/wikipedia/en/wiki/List_of_military_alliances#Active_alliances.
[2] https://secure.wikimedia.org/wikipedia/en/wiki/NarusInsight

comment:16 in reply to:  15 Changed 8 years ago by nickm

Replying to hellais:
[...]

I don't think it's a good idea for The Tor Project to ship an 'official' list. People should build one based on their own needs and independent organizations will be responsible for explaining the reasoning behind them and to what sort of case scenario they apply to.

The anonymity implications of this idea are very worrisome: see the "Anonymity Loves Company" paper that I did with Roger for the basic argument here.

In brief: if we're going to push the responsibility for mapping global backbone eavesdropping and data aggregation onto our users, then we'd better make sure that this is something they can be reasonably expected to do, and we had better make sure that having everybody do so in their own way will not partition the network traffic in a way that actually makes the attacker's job easier.

If we shouldn't ship an ‘official’ list, how will users find a list to use with their Tor client? If different users choose different lists, will Tor's anonymity set be partitioned further?

And last, but not least, what attack does this defend against?

I believe this feature will not be used by everybody, just by people that are worried about a large scale targeted attack. Let me further explain:
It is a fact that the technology exists and it is being deployed capable of collection information on Terabit networks [2] . It is not so far fetched to believe that if a big government wishes to target a specific individual he will request information on that person from various other countries with which they are allied. By making circuit building sensible to the relationships that exists amongst countries, you are making this information sharing much harder (e.s. would it be easy for the Swiss government to get traffic dumps from Ukraine?).

So to synthesize we are trying to prevent traffic analysis and correlation when allied countries collude against one individual.

So let's analyze that.

Say, for example, that the EU countries are all out to get me, and they are going to do so by eavesdropping all the communications under their control and doing full traffic correlation. Suppose that I know this, and declare that my circuits must never have more than one node in the EU. Does the proposed routing change actually help?

It doesn't help much if I'm in the EU: when my exit node is in the EU, they can correlate me fine. And it doesn't help if I'm outside of the EU and visiting EU websites: if my entry node is in the EU, then correlation will still work fine.

So, let's suppose that I'm not in the EU and I never visit EU websites, otherwise this whole business is hopeless.

Even then, I'm still not in the clear: sometimes the path to my first hop will travel through the EU and I'll wind up with an EU exit node; or the path from my last hop to my destination will travel through the EU and I'll wind up with an EU entry node. (Or even if I just say "ExcludeNodes {..all the EU..}", sometimes I'll wind up having both the path from me to my entry and from my exit to my destination pass through the EU.) So it still seems that the attack will still succeed pretty often if the attacker can see a reasonably large (geographic) portion of the backbone.

Now, I don't deny that this option is a cosmetic improvement: I can easily see a person (say) in the US worried about EU snooping being more comfortable with a circuit that goes {client in US} -> {DE} -> {JP} -> {RU} -> {website in IE} than with a circuit that goes {client in US} -> {DE} -> {US} -> {DE} -> {website in IE}. But -- and here's the important point -- I think that this increased comfort is probably only cosmetic. If the EU exchanges are eavesdropped, then the US->DE and RU->IE last hop are quite likely to pass through some exchanges in common.

So a large fraction of my circuits will still get snooped. If we believe in statistics, then having a random sample of my stuff get snooped is approximately as bad as having the whole thing get snooped.

And that's why I'm not convinced. I'm not interested only in an improved sense of security unless it materially increases actual resistance against a real attacker. So in order to argue for any feature like this, I want to see the analysis that shows that I'm wrong in my above and there is a real improvement, or I want to see an improved routing algorithm that doesn't fall to the analysis above.

comment:17 Changed 8 years ago by cypherpunks

Mmm. It appears I have under-estimated the problem. It seems anything Tor does at a routing level, the user loses. I know Tor cannot defeat the global passive adversary, but it seems Tor cannot even protect against a local passive adversary.  The Steven Murdoch paper on IX sampling should scare everyone the most. 

I wonder if there is a solution to this problem at all.

comment:18 in reply to:  17 Changed 8 years ago by cypherpunks

Replying to cypherpunks:

Mmm. It appears I have under-estimated the problem. It seems anything Tor does at a routing level, the user loses. I know Tor cannot defeat the global passive adversary, but it seems Tor cannot even protect against a local passive adversary.  The Steven Murdoch paper on IX sampling should scare everyone the most. 

I wonder if there is a solution to this problem at all.

It is a hard and open research problem. I think it's likely that at least a partial solution exists. As Nick said, our latest work is somewhat relevant. Expanding from trust of individual parts of the network to expectations about the likelihood that they are cooperating is still in the early stages, however.

comment:19 Changed 8 years ago by nickm

Milestone: Tor: very long term

Marking as "very long term" -- it's an active research problem, and if the research community comes with a reasonable set of answers, we should jump on, but as things stand this isn't even specifiable in a useful way. See my comments of 2011-08-02 and 2011-08-04 for an introduction to why.

comment:20 Changed 7 years ago by proper

Cc: proper@… added

I don't want to trivialize the problem with the internet exchange points. Research and a solution is still required. But let's put that attack aside for a moment, as this attack is not yet used in the wild against Tor users.

More critical at the moment is, that single countries can force their country's Tor relays, to log, through to a surveillance court order. During the investigation (depending on their local law) the local Tor relay operators may not even publish, that they are forced to log.

The adversary has to wait until their target uses a circuit with all three hops in their country.

As an intermediate solution, I suggest to stop using more than one country per circuit. That would require at least three countries to cooperate and to force their Tor node operators to log.

Implementing this as an intermediate solution would also require the adversary to use more expensive, sophisticated attacks than country wide passive logging for Tor nodes.

comment:21 Changed 7 years ago by nickm

Keywords: needs-research needs-proposal added

comment:22 Changed 7 years ago by nickm

Keywords: tor-client added

comment:23 Changed 7 years ago by nickm

Component: Tor ClientTor

comment:24 Changed 2 years ago by nickm

Severity: Normal
Status: needs_informationnew

comment:25 Changed 2 years ago by nickm

Parent ID: #22339
Resolution: duplicate
Status: newclosed

Closing these tickets and reparenting them. Some big redesign may be a wise here, but tracking it across a bunch of different sub-tickets with different ideas is not going to make progress.

Note: See TracTickets for help on using tickets.