commit 35ca1365111923dd661793175054685548b6e5a4 Author: Philipp Winter <phw@nymity.ch> Date: Tue Mar 17 13:53:12 2020 -0700 Allow change of distribution mechanisms. This was more work than expected because in addition to inserting a bridge into a new hashring, we had to implement new methods that allow us to remove bridges from their previous hashrings. This fixes <https://bugs.torproject.org/33631>. --- CHANGELOG | 7 ++ bridgedb/Bridges.py | 122 +++++++++++++++++++++++++---------- bridgedb/Storage.py | 29 ++++----- bridgedb/test/test_Bridges.py | 144 ++++++++++++++++++++++++++++++++++++++++++ bridgedb/test/test_Storage.py | 2 +- 5 files changed, 251 insertions(+), 53 deletions(-) diff --git a/CHANGELOG b/CHANGELOG index f57c168..4a05fc6 100644 --- a/CHANGELOG +++ b/CHANGELOG @@ -3,6 +3,13 @@ Browser. In addition to updating the instructions, this patch also links to instructions for Android. + * FIXES https://bugs.torproject.org/33631 + So far, BridgeDB remembered only the first distribution mechanism it + ever learned for a given bridge. That means that if a bridge would + change its mind and re-configure its distribution mechanism using + BridgeDistribution, BridgeDB would ignore it. This patch changes this + behavior, so bridges can actually change their distribution mechanism. + * FIXES https://bugs.torproject.org/31967 Use a CSPRNG for selecting cached CAPTCHAs. diff --git a/bridgedb/Bridges.py b/bridgedb/Bridges.py index c29a2bf..bbc9b5f 100644 --- a/bridgedb/Bridges.py +++ b/bridgedb/Bridges.py @@ -180,6 +180,14 @@ class BridgeRing(object): for tp, val, count, subring in self.subrings: subring.clear() + def remove(self, bridge): + """Remove a **bridge** from this hashring.""" + for tp, val, _, subring in self.subrings: + subring.remove(bridge) + pos = self.hmac(bridge.identity) + if pos in self.bridges: + del self.bridges[pos] + def insert(self, bridge): """Add a **bridge** to this hashring. @@ -411,8 +419,17 @@ class UnallocatedHolder(object): def __init__(self): self.fingerprints = [] + def remove(self, bridge): + logging.debug("Removing %s from unallocated" % bridge.fingerprint) + i = -1 + try: + i = self.fingerprints.index(bridge.fingerprint) + except ValueError: + return + del self.fingerprints[i] + def insert(self, bridge): - logging.debug("Leaving %s unallocated", bridge.fingerprint) + logging.debug("Leaving %s unallocated" % bridge.fingerprint) if not bridge.fingerprint in self.fingerprints: self.fingerprints.append(bridge.fingerprint) @@ -488,43 +505,52 @@ class BridgeSplitter(object): return validRings = self.rings - distribution_method = None + distribution_method = orig_method = None - # If the bridge already has a distributor, use that. with bridgedb.Storage.getDB() as db: - distribution_method = db.getBridgeDistributor(bridge, validRings) + orig_method = db.getBridgeDistributor(bridge, validRings) + if orig_method is not None: + distribution_method = orig_method + logging.info("So far, bridge %s was in hashring %s" % + (bridge, orig_method)) + + # Check if the bridge requested a distribution method and if so, try to + # use it. + if bridge.distribution_request: + distribution_method = bridge.distribution_request + logging.info("Bridge %s requested placement in hashring %s" % + (bridge, distribution_method)) + + # Is the bridge requesting a distribution method that's different + # from the one we have on record? If so, we have to delete it from + # its previous ring. + if orig_method is not None and \ + orig_method != distribution_method and \ + distribution_method in (validRings + ["none"]): + logging.info("Bridge %s is in %s but wants to be in %s." % + (bridge, orig_method, distribution_method)) + prevRing = self.ringsByName.get(orig_method) + prevRing.remove(bridge) + + # If they requested not to be distributed, honor the request: + if distribution_method == "none": + logging.info("Bridge %s requested to not be distributed." % bridge) + return - if distribution_method: - logging.info("%s bridge %s was already in hashring %s" % - (self.__class__.__name__, bridge, distribution_method)) - else: - # Check if the bridge requested a specific distribution method. - if bridge.distribution_request: - distribution_method = bridge.distribution_request - logging.info("%s bridge %s requested placement in hashring %s" - % (self.__class__.__name__, bridge, - distribution_method)) - - # If they requested not to be distributed, honor the request: - if distribution_method == "none": - logging.info("%s bridge %s requested to not be distributed." - % (self.__class__.__name__, bridge)) - return - - # If we didn't know what they are talking about, or they requested - # "any" distribution method, and we've never seen this bridge - # before, then determine where to place it. - if ((distribution_method not in validRings) or - (distribution_method == "any")): - - pos = self.hmac(bridge.identity) - n = int(pos[:8], 16) % self.totalP - pos = bisect.bisect_right(self.pValues, n) - 1 - assert 0 <= pos < len(self.rings) - distribution_method = self.rings[pos] - logging.info(("%s placing bridge %s into hashring %s (via n=%s," - " pos=%s).") % (self.__class__.__name__, bridge, - distribution_method, n, pos)) + # If we didn't know what they are talking about, or they requested + # "any" distribution method, and we've never seen this bridge + # before, then deterministically determine where to place it. + if ((distribution_method not in validRings) or + (distribution_method == "any")): + + pos = self.hmac(bridge.identity) + n = int(pos[:8], 16) % self.totalP + pos = bisect.bisect_right(self.pValues, n) - 1 + assert 0 <= pos < len(self.rings) + distribution_method = self.rings[pos] + logging.info(("%s placing bridge %s into hashring %s (via n=%s," + " pos=%s).") % (self.__class__.__name__, bridge, + distribution_method, n, pos)) with bridgedb.Storage.getDB() as db: ringname = db.insertBridgeAndGetRing(bridge, distribution_method, @@ -588,6 +614,32 @@ class FilteredBridgeSplitter(object): self.bridges = [] self.filterRings = {} + def remove(self, bridge): + """Remove a bridge from all appropriate sub-hashrings. + + :type bridge: :class:`~bridgedb.bridges.Bridge` + :param bridge: The bridge to add. + """ + logging.debug("Removing %s from hashring..." % bridge) + + all_fingerprints = [b.fingerprint for b in self.bridges] + index = -1 + try: + index = all_fingerprints.index(bridge.fingerprint) + except ValueError: + # The given bridge doesn't exist, so there's nothing to remove. + logging.warn("Was asked to remove non-existant bridge %s " + "from ring." % bridge) + return + assert index > -1 + del self.bridges[index] + + for ringname, (filterFn, subring) in self.filterRings.items(): + if filterFn(bridge): + subring.remove(bridge) + logging.debug("Removed bridge %s from %s subhashring." % + (bridge, ringname)) + def insert(self, bridge): """Insert a bridge into all appropriate sub-hashrings. diff --git a/bridgedb/Storage.py b/bridgedb/Storage.py index cfd60bb..d725fa3 100644 --- a/bridgedb/Storage.py +++ b/bridgedb/Storage.py @@ -166,9 +166,8 @@ class Database(object): def insertBridgeAndGetRing(self, bridge, setRing, seenAt, validRings, defaultPool="unallocated"): - '''Updates info about bridge, setting ring to setRing if none was set. - Also sets distributor to `defaultPool' if the bridge was found in - the database, but its distributor isn't valid anymore. + '''Updates info about bridge, setting ring to setRing. Also sets + distributor to `defaultPool' if setRing isn't a valid ring. Returns the name of the distributor the bridge is assigned to. ''' @@ -178,26 +177,22 @@ class Database(object): h = bridge.fingerprint assert len(h) == HEX_ID_LEN - cur.execute("SELECT id, distributor " - "FROM Bridges WHERE hex_key = ?", (h,)) + # Check if this is currently a valid ring name. If not, move into + # default pool. + if setRing not in validRings: + setRing = defaultPool + + cur.execute("SELECT id FROM Bridges WHERE hex_key = ?", (h,)) v = cur.fetchone() if v is not None: - i, ring = v - # Check if this is currently a valid ring name. If not, move back - # into default pool. - if ring not in validRings: - ring = defaultPool + bridgeId = v[0] # Update last_seen, address, port and (possibly) distributor. cur.execute("UPDATE Bridges SET address = ?, or_port = ?, " "distributor = ?, last_seen = ? WHERE id = ?", - (str(bridge.address), bridge.orPort, ring, - timeToStr(seenAt), i)) - return ring + (str(bridge.address), bridge.orPort, setRing, + timeToStr(seenAt), bridgeId)) + return setRing else: - # Check if this is currently a valid ring name. If not, move back - # into default pool. - if setRing not in validRings: - setRing = defaultPool # Insert it. cur.execute("INSERT INTO Bridges (hex_key, address, or_port, " "distributor, first_seen, last_seen) " diff --git a/bridgedb/test/test_Bridges.py b/bridgedb/test/test_Bridges.py index 77eff1c..2deeec7 100644 --- a/bridgedb/test/test_Bridges.py +++ b/bridgedb/test/test_Bridges.py @@ -17,11 +17,18 @@ import copy import io import ipaddr import logging +import tempfile +import os from twisted.trial import unittest +import bridgedb.Storage + from bridgedb import Bridges +from bridgedb import crypto from bridgedb.test import util +from bridgedb.distributors.https.distributor import HTTPSDistributor +from bridgedb.distributors.moat.distributor import MoatDistributor # For additional logger output for debugging, comment out the following: logging.disable(50) @@ -153,3 +160,140 @@ class FixedBridgeSplitterTests(unittest.TestCase): # The first bridge's fingerprint should be within the data somewhere self.assertIn(first, data) + + +class BridgeSplitterTests(unittest.TestCase): + """Unittests for :class:`bridgedb.Bridges.BridgeSplitter`.""" + + def setUp(self): + + self.bridges = copy.deepcopy(util.generateFakeBridges()) + + self.fd, self.fname = tempfile.mkstemp(suffix=".sqlite", dir=os.getcwd()) + bridgedb.Storage.initializeDBLock() + self.db = bridgedb.Storage.openDatabase(self.fname) + bridgedb.Storage.setDBFilename(self.fname) + + key = 'fake-hmac-key' + self.splitter = Bridges.BridgeSplitter(key) + ringParams = Bridges.BridgeRingParameters(needPorts=[(443, 1)], + needFlags=[("Stable", 1)]) + self.https_distributor = HTTPSDistributor( + 4, + crypto.getHMAC(key, "HTTPS-IP-Dist-Key"), + None, + answerParameters=ringParams) + self.moat_distributor = MoatDistributor( + 4, + crypto.getHMAC(key, "Moat-Dist-Key"), + None, + answerParameters=ringParams) + self.unallocated_distributor = Bridges.UnallocatedHolder() + + self.splitter.addRing(self.https_distributor.hashring, "https", p=10) + self.splitter.addRing(self.moat_distributor.hashring, "moat", p=10) + self.splitter.addRing(self.unallocated_distributor, "unallocated", p=10) + self.https_ring = self.splitter.ringsByName.get("https") + self.moat_ring = self.splitter.ringsByName.get("moat") + self.unallocated_ring = self.splitter.ringsByName.get("unallocated") + + def tearDown(self): + self.db.close() + os.close(self.fd) + os.unlink(self.fname) + + def _len_all_subrings(self, ring): + """Return the sum of the length of all subrings.""" + all_subrings = [subring for _, subring in ring.filterRings.values()] + return sum([len(subring) for subring in all_subrings]) + + def test_no_distribution(self): + """Make sure that bridges can un-distribute themselves.""" + bridge = self.bridges[0] + bridge.distribution_request = "https" + + # Assume a bridge wants to be distributed over HTTPS. + self.splitter.insert(bridge) + self.assertEqual(len(self.https_ring), 1) + + # ...and now the bridge no longer wants to be distributed. + bridge.distribution_request = "none" + self.splitter.insert(bridge) + self.assertEqual(len(self.https_ring), 0) + self.assertEqual(len(self.moat_ring), 0) + self.assertEqual(len(self.unallocated_ring), 0) + + def test_change_distribution(self): + """Make sure that bridges can change their distribution mechanism.""" + bridge = self.bridges[0] + # We hard-code our identity to make this test deterministic. + bridge.identity = b"\xfd{\xe7\x90a'\n\xf483@H\xd6-\x9c\xf3\x8f\x12~$" + bridge.distribution_request = "https" + + # Assume a bridge wants to be distributed over HTTPS. + self.splitter.insert(bridge) + self.assertEqual(len(self.https_ring), 1) + self.assertEqual(len(self.moat_ring), 0) + self.assertEqual(self._len_all_subrings(self.moat_ring), 0) + + # ...and now the bridge changes its mind and wants Moat. + bridge.distribution_request = "moat" + self.splitter.insert(bridge) + self.assertEqual(len(self.https_ring), 0) + self.assertEqual(self._len_all_subrings(self.https_ring), 0) + self.assertEqual(len(self.moat_ring), 1) + + # ...if the bridge uses "any", it should stay where it is. + bridge.distribution_request = "any" + self.splitter.insert(bridge) + self.assertEqual(len(self.https_ring), 0) + self.assertEqual(self._len_all_subrings(self.https_ring), 0) + self.assertEqual(len(self.moat_ring), 1) + + # ...if it uses "none", it shouldn't be distributed at all. + bridge.distribution_request = "none" + self.splitter.insert(bridge) + self.assertEqual(len(self.https_ring), 0) + self.assertEqual(self._len_all_subrings(self.https_ring), 0) + self.assertEqual(len(self.moat_ring), 0) + self.assertEqual(self._len_all_subrings(self.moat_ring), 0) + + # ...if the distribution method is unrecognised, it should be treated + # as "any". + bridge.distribution_request = "foobar" + self.splitter.insert(bridge) + self.assertEqual(len(self.https_ring), 0) + self.assertEqual(self._len_all_subrings(self.https_ring), 0) + self.assertEqual(len(self.moat_ring), 1) + + # ...and finally, it wants HTTPS again. + bridge.distribution_request = "https" + self.splitter.insert(bridge) + self.assertEqual(len(self.https_ring), 1) + self.assertEqual(len(self.moat_ring), 0) + self.assertEqual(self._len_all_subrings(self.moat_ring), 0) + + def test_https_remove(self): + """Make sure that we can remove bridges from our BridgeRing.""" + bridge = self.bridges[0] + + self.assertEqual(len(self.https_ring), 0) + self.https_ring.insert(bridge) + self.https_distributor.prepopulateRings() + self.assertEqual(len(self.https_ring), 1) + + self.https_ring.remove(bridge) + self.assertEqual(len(self.https_ring), 0) + self.assertEqual(self._len_all_subrings(self.https_ring), 0) + + def test_unallocated_remove(self): + """Make sure that we can remove bridges from our UnallocatedHolder.""" + bridge = self.bridges[0] + bridge.distribution_request = "unallocated" + + self.assertEqual(len(self.unallocated_distributor), 0) + self.splitter.insert(bridge) + self.assertEqual(len(self.unallocated_distributor), 1) + + self.unallocated_distributor.remove(bridge) + self.assertEqual(len(self.unallocated_distributor), 0) diff --git a/bridgedb/test/test_Storage.py b/bridgedb/test/test_Storage.py index ca10bb9..720afdd 100644 --- a/bridgedb/test/test_Storage.py +++ b/bridgedb/test/test_Storage.py @@ -82,7 +82,7 @@ class DatabaseTest(unittest.TestCase): time.time(), self.validRings) self.assertIn(ringname, self.validRings) - self.assertEqual(ringname, 'moat') + self.assertEqual(ringname, 'https') def test_getBridgeDistributor_recognised(self): bridge = self.fakeBridges[0]