Extending BridgeDB to reallocate bridges from a blocked country to others that do not block.
The following is a draft proposal of changes to BridgeDB to address the deliverable "Automated bridge allocation to reallocate bridges from a blocked country to others that do not block" (https://trac.torproject.org/projects/tor/wiki/org/sponsors/SponsorE/PhaseThr...)
This draft proposes two different approaches -- any feedback or questions are very welcome!
--Aaron
==== Filename: xxx-bridgedb-reallocates-bridges.txt Title: BridgeDB Reallocates Bridges Author: Aaron Gibson Created: 15 Jan 2015 Status: Draft
Introduction:
This proposal outlines the required changes for BridgeDB to reallocate bridges from a blocked country to others that do not block.
Current Status:
Presently, BridgeDB does not allocate bridges to specific countries. The HTTPS distributor divides bridges into a cluster of rings. Requests for bridges are mapped to a single ring in the cluster using the class C network of the client, so that the IPv4 space is divided amongst the rings in the cluster (presently 4 rings). For an attacker to obtain the complete set of bridges she must control a number of IP addresses in diverse networks. The email based distributor uses a single ring, and bridge buckets are dumped from a single pool of unallocated bridges.
Required modifications:
1. BridgeDB must be able to produce an unblocked set of bridges for a specific country, if these bridges are available.
2. If a bridge is blocked in a country, it must be available to users in other countries.
BridgeDB could be modified to assign bridges to geographic regions. To do so, the cluster concept must be extended to support 'geographic clusters' of bridges that correspond to a set of country codes, so that requests will be directed to a corresponding cluster, by either automatic geoip detection or by client choice.
Alternately, BridgeDB could be modified to guarantee that a client requesting unblocked bridges for a region would receive these bridges, if unblocked bridges exist. Presently, patches exist for BridgeDB that mark known blocked bridges as "Might be blocked", but makes no further effort to respond with unblocked bridges, even if those bridges exist.
Proposed Solution 1
Modify BridgeDB to assign bridges to geographic regions. Regions are designated by a list of country codes. Regions should be balanced in size, or proportional to the number of bridge users. If a bridge is blocked in a region, the bridge should be reallocated to another region. Bridges for a region are stored in a cluster of rings.
Pitfalls
Bridges assigned to one geographic area are not available to clients requesting bridges from other regions.
Possible Solution 2
Modify BridgeDB to dynamically produce rings of bridges 'Not blocked in' a specified country. Bridges are not mapped to a specific country or region, but BridgeDB's response would contain only unblocked bridges (if available).
Pitfalls
As bridges are not allocated to a specific region, bridges could not be reserved for distribution to specific regions.
Common pitfalls
As BridgeDB learns about blocked bridges that it may no longer provide, BridgeDB replaces blocked bridges with good bridges. An attacker with control over addresses from many class C networks could iteratively request and block bridges, until the entire set has been consumed. The rate of consumption could be limited by the rate that blocked bridges are updated, but clients would be more likely to receive a bridge that has been blocked.
On Sun, Jan 15, 2012 at 09:34:49AM -0800, Aaron wrote:
This proposal outlines the required changes for BridgeDB to reallocate bridges from a blocked country to others that do not block.
I guess I'll be the grumpy one here, but: doesn't bridgedb already do that, just based on how it picks its answers? Or are we trying to load balance by giving out bridges-blocked-in-China more commonly to Saudi users? I'm missing the big picture goals here.
Current Status:
Presently, BridgeDB does not allocate bridges to specific countries. The HTTPS distributor divides bridges into a cluster of rings. Requests for bridges are mapped to a single ring in the cluster using the class C network of the client, so that the IPv4 space is divided amongst the rings in the cluster (presently 4 rings). For an attacker to obtain the complete set of bridges she must control a number of IP addresses in diverse networks. The email based distributor uses a single ring, and bridge buckets are dumped from a single pool of unallocated bridges.
Ok.
Required modifications:
- BridgeDB must be able to produce an unblocked set of bridges for a specific country, if these bridges are available.
Ok. Though I'd be nervous about enabling this functionality for normal users, since it makes "ask for some bridges, block them; wait for bridgedb to notice; ask for new bridges, block them" easier.
- If a bridge is blocked in a country, it must be available to users in other countries.
Why does this need a modification? It is already the case, right?
BridgeDB could be modified to assign bridges to geographic regions. To do so, the cluster concept must be extended to support 'geographic clusters' of bridges that correspond to a set of country codes, so that requests will be directed to a corresponding cluster, by either automatic geoip detection or by client choice.
If the client can specify what country he wants to ask about, that makes the above enumeration attack even more effective.
Alternately, BridgeDB could be modified to guarantee that a client requesting unblocked bridges for a region would receive these bridges, if unblocked bridges exist. Presently, patches exist for BridgeDB that mark known blocked bridges as "Might be blocked", but makes no further effort to respond with unblocked bridges, even if those bridges exist.
Right -- I thought we considered that a feature. We are telling the user that we think the bridges we're giving them won't work, and we're not giving them replacements because that would accelerate the defeat of the rate limiting goals.
Proposed Solution 1
Modify BridgeDB to assign bridges to geographic regions. Regions are designated by a list of country codes. Regions should be balanced in size, or proportional to the number of bridge users. If a bridge is blocked in a region, the bridge should be reallocated to another region. Bridges for a region are stored in a cluster of rings.
Pitfalls
Bridges assigned to one geographic area are not available to clients requesting bridges from other regions.
Possible Solution 2
Modify BridgeDB to dynamically produce rings of bridges 'Not blocked in' a specified country. Bridges are not mapped to a specific country or region, but BridgeDB's response would contain only unblocked bridges (if available).
Again, some security analysis would be good here: in what situations are we expecting this to be a good idea?
--Roger
On Mon, Jan 30, 2012 at 1:14 AM, Roger Dingledine arma@mit.edu wrote:
On Sun, Jan 15, 2012 at 09:34:49AM -0800, Aaron wrote:
This proposal outlines the required changes for BridgeDB to reallocate bridges from a blocked country to others that do not block.
I guess I'll be the grumpy one here, but: doesn't bridgedb already do that, just based on how it picks its answers? Or are we trying to load balance by giving out bridges-blocked-in-China more commonly to Saudi users? I'm missing the big picture goals here.
No, BridgeDB does not allocate bridges by region, nor is load balancing a concern of this proposal. Presently, bridges are served and available to clients of all countries.
The deliverable "Automated bridge allocation to reallocate bridges from a blocked country to others that do not block" either misunderstands how BridgeDB assigns bridges, or is suggesting that BridgeDB should assign bridges by country.
If bridges are assigned by country, then BridgeDB can limit the addresses that these bridges are exposed to, increasing the bridges/addresses ratio for that region, and potentially reduce the rate that bridges get blocked. When the bridges are blocked, they will be made available to other countries.
Required modifications:
1. BridgeDB must be able to produce an unblocked set of bridges for a specific country, if these bridges are available.
Ok. Though I'd be nervous about enabling this functionality for normal users, since it makes "ask for some bridges, block them; wait for bridgedb to notice; ask for new bridges, block them" easier.
This is true, but we can control the rate that bridges are consumed because we control when the blocked bridge list is updated.
And I think the strongest argument for exposing this functionality to normal users is that of usability. How many users are turned away because the bridges don't work or "might be blocked"? A censor can afford to check bridges.tpo continuously and block bridges as it sees them, but a user is more likely to just give up.
2. If a bridge is blocked in a country, it must be available to users in other countries.
Why does this need a modification? It is already the case, right?
Yes, BridgeDB does not allocate bridges to countries. This requirement only makes sense if BridgeDB did allocate bridges to countries.
If the client can specify what country he wants to ask about, that makes the above enumeration attack even more effective.
BridgeDB should probably differentiate between requests coming from the requested region and requests coming from outside the requested region, though legitimate requests and requests for legitimate users are likely to arrive from outside the requested region.
Alternately, BridgeDB could be modified to guarantee that a client requesting unblocked bridges for a region would receive these bridges, if unblocked bridges exist. Presently, patches exist for BridgeDB that mark known blocked bridges as "Might be blocked", but makes no further effort to respond with unblocked bridges, even if those bridges exist.
Right -- I thought we considered that a feature. We are telling the user that we think the bridges we're giving them won't work, and we're not giving them replacements because that would accelerate the defeat of the rate limiting goals.
That's been our assumption, but I don't think we have any data as to how serial enumeration compares to parallel enumeration. I do think we can control how fast bridges are burned via the blocked bridge list update. Ideally we'll be able to get an idea of what works and what doesn't experimentally, and use that to guide any improvements we make.
Possible Solution 2
Modify BridgeDB to dynamically produce rings of bridges 'Not blocked in' a specified country. Bridges are not mapped to a specific country or region, but BridgeDB's response would contain only unblocked bridges (if available).
Again, some security analysis would be good here: in what situations are we expecting this to be a good idea?
Upon reflection, I think solution 2 is too limited. I am convinced that we do want to be able to assign bridges to specific regions, because our distribution strategy should be customizable for different regions.
There are a few questions I'd like to ask too, in the context of this proposal:
1. Although the number of bridges is limited, that may not always be the case. If we had several orders of magnitude more bridges available, how should our strategy change? Do these changes help?
2. Should we be trying to conserve bridges? What about bridges who may not stick around very long anyway? How long do bridges last, on average?
3. Does limiting the set of addresses (region mapping) that correspond to a set of bridges significantly reduce the ability of a censor to obtain the set of bridges? Via a botnet? Via the national ISP?
4. What about censors who hurt Tor users? Could our distribution strategy change for just those regions? For example, bridges that are handed out a limited number of times, never re-allocated to other countries, etc?
Thanks for your feedback!
--Aaron
-
Aaron -
Roger Dingledine