tor/doc/spec/proposals/156-tracking-blocked-ports.txt

Filename: 156-tracking-blocked-ports.txt
Title: Tracking blocked ports on the client side
Version: $Revision$
Last-Modified: $Date$
Author: Robert Hogan
Created: 14-Oct-2008
Status: Open
Target: 0.2.?

Motivation:
Tor clients that are behind extremely restrictive firewalls can end up
waiting a while for their first successful OR connection to a node on the
network.  Worse, the more restrictive their firewall the more susceptible
they are to an attacker guessing their entry nodes. Tor routers that
are behind extremely restrictive firewalls can only offer a limited,
'partitioned' service to other routers and clients on the network. Exit
nodes behind extremely restrictive firewalls may advertise ports that they
are actually not able to connect to, wasting network resources in circuit
constructions that are doomed to fail at the last hop on first use.

Proposal:

When a client attempts to connect to an entry guard it should avoid
further attempts on ports that fail once until it has connected to at
least one entry guard successfully. (Maybe it should wait for more than
one failure to reduce the skew on the first node selection.) Thereafter
it should select entry guards regardless of port and warn the user if
it observes that connections to a given port have failed every multiple
of 5 times without success or since the last success.

Tor should warn the operators of exit, middleman and entry nodes if it
observes that connections to a given port have failed a multiple of 5
times without success or since the last success. If attempts on a port
fail 20 or more times without or since success, Tor should add the port
to a 'blocked-ports' entry in its descriptor's extra-info. Some thought
needs to be given to what the authorities might do with this information.

Related TODO item:
    "- Automatically determine what ports are reachable and start using
      those, if circuits aren't working and it's a pattern we
      recognize ("port 443 worked once and port 9001 keeps not
      working")."


I've had a go at implementing all of this in the attached.

Addendum:
Just a note on the patch, storing the digest of each router that uses the port
is a bit of a memory hog, and its only real purpose is to provide a count of
routers using that port when warning the user. That could be achieved when
warning the user by iterating through the routerlist instead.

Index: src/or/connection_or.c
===================================================================
--- src/or/connection_or.c	(revision 17104)
+++ src/or/connection_or.c	(working copy)
@@ -502,6 +502,9 @@
 connection_or_connect_failed(or_connection_t *conn,
                              int reason, const char *msg)
 {
+  if ((reason == END_OR_CONN_REASON_NO_ROUTE) ||
+      (reason == END_OR_CONN_REASON_REFUSED))
+    or_port_hist_failure(conn->identity_digest,TO_CONN(conn)->port);
   control_event_or_conn_status(conn, OR_CONN_EVENT_FAILED, reason);
   if (!authdir_mode_tests_reachability(get_options()))
     control_event_bootstrap_problem(msg, reason);
@@ -580,6 +583,7 @@
     /* already marked for close */
     return NULL;
   }
+
   return conn;
 }
 
@@ -909,6 +913,7 @@
   control_event_or_conn_status(conn, OR_CONN_EVENT_CONNECTED, 0);
 
   if (started_here) {
+    or_port_hist_success(TO_CONN(conn)->port);
     rep_hist_note_connect_succeeded(conn->identity_digest, now);
     if (entry_guard_register_connect_status(conn->identity_digest,
                                             1, now) < 0) {
Index: src/or/rephist.c
===================================================================
--- src/or/rephist.c	(revision 17104)
+++ src/or/rephist.c	(working copy)
@@ -18,6 +18,7 @@
 static void bw_arrays_init(void);
 static void predicted_ports_init(void);
 static void hs_usage_init(void);
+static void or_port_hist_init(void);
 
 /** Total number of bytes currently allocated in fields used by rephist.c. */
 uint64_t rephist_total_alloc=0;
@@ -89,6 +90,25 @@
   digestmap_t *link_history_map;
 } or_history_t;
 
+/** or_port_hist_t contains our router/client's knowledge of
+    all OR ports offered on the network, and how many servers with each port we
+    have succeeded or failed to connect to. */
+typedef struct {
+  /** The port this entry is tracking. */
+  uint16_t or_port;
+  /** Have we ever connected to this port on another OR?. */
+  unsigned int success:1;
+  /** The ORs using this port. */
+  digestmap_t *ids;
+  /** The ORs using this port we have failed to connect to. */
+  digestmap_t *failure_ids;
+  /** Are we excluding ORs with this port during entry selection?*/
+  unsigned int excluded;
+} or_port_hist_t;
+
+static unsigned int still_searching = 0;
+static smartlist_t *or_port_hists;
+
 /** When did we last multiply all routers' weighted_run_length and
  * total_run_weights by STABILITY_ALPHA? */
 static time_t stability_last_downrated = 0;
@@ -164,6 +184,16 @@
   tor_free(hist);
 }
 
+/** Helper: free storage held by a single OR port history entry. */
+static void
+or_port_hist_free(or_port_hist_t *p)
+{
+  tor_assert(p);
+  digestmap_free(p->ids,NULL);
+  digestmap_free(p->failure_ids,NULL);
+  tor_free(p);
+}
+
 /** Update an or_history_t object <b>hist</b> so that its uptime/downtime
  * count is up-to-date as of <b>when</b>.
  */
@@ -1639,7 +1669,7 @@
     tmp_time = smartlist_get(predicted_ports_times, i);
     if (*tmp_time + PREDICTED_CIRCS_RELEVANCE_TIME < now) {
       tmp_port = smartlist_get(predicted_ports_list, i);
-      log_debug(LD_CIRC, "Expiring predicted port %d", *tmp_port);
+      log_debug(LD_HIST, "Expiring predicted port %d", *tmp_port);
       smartlist_del(predicted_ports_list, i);
       smartlist_del(predicted_ports_times, i);
       rephist_total_alloc -= sizeof(uint16_t)+sizeof(time_t);
@@ -1821,6 +1851,12 @@
   tor_free(last_stability_doc);
   built_last_stability_doc_at = 0;
   predicted_ports_free();
+  if (or_port_hists) {
+    SMARTLIST_FOREACH(or_port_hists, or_port_hist_t *, p,
+                      or_port_hist_free(p));
+    smartlist_free(or_port_hists);
+    or_port_hists = NULL;
+  }
 }
 
 /****************** hidden service usage statistics ******************/
@@ -2356,3 +2392,225 @@
   tor_free(fname);
 }
 
+/** Create a new entry in the port tracking cache for the or_port in
+  * <b>ri</b>. */
+void
+or_port_hist_new(const routerinfo_t *ri)
+{
+  or_port_hist_t *result;
+  const char *id=ri->cache_info.identity_digest;
+
+  if (!or_port_hists)
+    or_port_hist_init();
+
+  SMARTLIST_FOREACH(or_port_hists, or_port_hist_t *, tp,
+    {
+      /* Cope with routers that change their advertised OR port or are
+         dropped from the networkstatus. We don't discard the failures of
+         dropped routers because they are still valid when counting
+         consecutive failures on a port.*/
+      if (digestmap_get(tp->ids, id) && (tp->or_port != ri->or_port)) {
+        digestmap_remove(tp->ids, id);
+      }
+      if (tp->or_port == ri->or_port) {
+        if (!(digestmap_get(tp->ids, id)))
+          digestmap_set(tp->ids, id, (void*)1);
+        return;
+      }
+    });
+
+  result = tor_malloc_zero(sizeof(or_port_hist_t));
+  result->or_port=ri->or_port;
+  result->success=0;
+  result->ids=digestmap_new();
+  digestmap_set(result->ids, id, (void*)1);
+  result->failure_ids=digestmap_new();
+  result->excluded=0;
+  smartlist_add(or_port_hists, result);
+}
+
+/** Create the port tracking cache. */
+/*XXX: need to call this when we rebuild/update our network status */
+static void
+or_port_hist_init(void)
+{
+  routerlist_t *rl = router_get_routerlist();
+
+  if (!or_port_hists)
+    or_port_hists=smartlist_create();
+
+  if (rl && rl->routers) {
+    SMARTLIST_FOREACH(rl->routers, routerinfo_t *, ri,
+    {
+      or_port_hist_new(ri);
+    });
+  }
+}
+
+#define NOT_BLOCKED 0
+#define FAILURES_OBSERVED 1
+#define POSSIBLY_BLOCKED 5
+#define PROBABLY_BLOCKED 10
+/** Return the list of blocked ports for our router's extra-info.*/
+char *
+or_port_hist_get_blocked_ports(void)
+{
+  char blocked_ports[2048];
+  char *bp;
+  
+  tor_snprintf(blocked_ports,sizeof(blocked_ports),"blocked-ports");
+  SMARTLIST_FOREACH(or_port_hists, or_port_hist_t *, tp,
+    {
+      if (digestmap_size(tp->failure_ids) >= PROBABLY_BLOCKED)
+        tor_snprintf(blocked_ports+strlen(blocked_ports),
+                     sizeof(blocked_ports)," %u,",tp->or_port);
+    });
+  if (strlen(blocked_ports) == 13)
+    return NULL;
+  bp=tor_strdup(blocked_ports);
+  bp[strlen(bp)-1]='\n';
+  bp[strlen(bp)]='\0';
+  return bp;
+}
+
+/** Revert to client-only mode if we have seen to many failures on a port or
+  * range of ports.*/
+static void
+or_port_hist_report_block(unsigned int min_severity)
+{
+  or_options_t *options=get_options();
+  char failures_observed[2048],possibly_blocked[2048],probably_blocked[2048];
+  char port[1024];
+
+  memset(failures_observed,0,sizeof(failures_observed));
+  memset(possibly_blocked,0,sizeof(possibly_blocked));
+  memset(probably_blocked,0,sizeof(probably_blocked));
+
+  SMARTLIST_FOREACH(or_port_hists, or_port_hist_t *, tp,
+    {
+      unsigned int failures = digestmap_size(tp->failure_ids);
+      if (failures >= min_severity) {
+        tor_snprintf(port, sizeof(port), " %u (%u failures %s out of %u on the"
+                     " network)",tp->or_port,failures,
+                     (!tp->success)?"and no successes": "since last success",
+                     digestmap_size(tp->ids));
+        if (failures >= PROBABLY_BLOCKED) {
+          strlcat(probably_blocked, port, sizeof(probably_blocked));
+        } else if (failures >= POSSIBLY_BLOCKED)
+          strlcat(possibly_blocked, port, sizeof(possibly_blocked));
+        else if (failures >= FAILURES_OBSERVED)
+          strlcat(failures_observed, port, sizeof(failures_observed));
+      }
+    });
+
+  log_warn(LD_HIST,"%s%s%s%s%s%s%s%s",
+           server_mode(options) &&
+           ((min_severity==FAILURES_OBSERVED) || strlen(probably_blocked))?
+           "You should consider disabling your Tor server.":"",
+           (min_severity==FAILURES_OBSERVED)?
+           "Tor appears to be blocked from connecting to a range of ports "
+           "with the result that it cannot connect to one tenth of the Tor "
+           "network. ":"",
+           strlen(failures_observed)?
+           "Tor has observed failures on the following ports: ":"",
+           failures_observed,
+           strlen(possibly_blocked)?
+           "Tor is possibly blocked on the following ports: ":"",
+           possibly_blocked,
+           strlen(probably_blocked)?
+           "Tor is almost certainly blocked on the following ports: ":"",
+           probably_blocked);
+
+}
+
+/** Record the success of our connection to <b>digest</b>'s
+  * OR port. */
+void
+or_port_hist_success(uint16_t or_port)
+{
+  SMARTLIST_FOREACH(or_port_hists, or_port_hist_t *, tp,
+    {
+      if (tp->or_port != or_port)
+        continue;
+      /*Reset our failure stats so we can notice if this port ever gets
+        blocked again.*/
+      tp->success=1;
+      if (digestmap_size(tp->failure_ids)) {
+        digestmap_free(tp->failure_ids,NULL);
+        tp->failure_ids=digestmap_new();
+      }
+      if (still_searching) {
+        still_searching=0;
+        SMARTLIST_FOREACH(or_port_hists,or_port_hist_t *,t,t->excluded=0;);
+      }
+      return;
+    });
+}
+/** Record the failure of our connection to <b>digest</b>'s
+  * OR port. Warn, exclude the port from future entry guard selection, or
+  * add port to blocked-ports in our server's extra-info as appropriate. */
+void
+or_port_hist_failure(const char *digest, uint16_t or_port)
+{
+  int total_failures=0, ports_excluded=0, report_block=0;
+  int total_routers=smartlist_len(router_get_routerlist()->routers);
+
+  SMARTLIST_FOREACH(or_port_hists, or_port_hist_t *, tp,
+    {
+      ports_excluded += tp->excluded;
+      total_failures+=digestmap_size(tp->failure_ids);
+      if (tp->or_port != or_port)
+        continue;
+      /* We're only interested in unique failures */
+      if (digestmap_get(tp->failure_ids, digest))
+        return;
+
+      total_failures++;
+      digestmap_set(tp->failure_ids, digest, (void*)1);
+      if (still_searching && !tp->success) {
+        tp->excluded=1;
+        ports_excluded++;
+      }
+      if ((digestmap_size(tp->ids) >= POSSIBLY_BLOCKED) &&
+         !(digestmap_size(tp->failure_ids) % POSSIBLY_BLOCKED))
+        report_block=POSSIBLY_BLOCKED;
+    });
+
+  if (total_failures >= (int)(total_routers/10))
+    or_port_hist_report_block(FAILURES_OBSERVED);
+  else if (report_block)
+    or_port_hist_report_block(report_block);
+
+  if (ports_excluded >= smartlist_len(or_port_hists)) {
+    log_warn(LD_HIST,"During entry node selection Tor tried every port "
+             "offered on the network on at least one server "
+             "and didn't manage a single "
+             "successful connection. This suggests you are behind an "
+             "extremely restrictive firewall. Tor will keep trying to find "
+             "a reachable entry node.");
+    SMARTLIST_FOREACH(or_port_hists, or_port_hist_t *, tp, tp->excluded=0;);
+  }
+}
+
+/** Add any ports marked as excluded in or_port_hist_t to <b>rt</b> */
+void
+or_port_hist_exclude(routerset_t *rt)
+{
+  SMARTLIST_FOREACH(or_port_hists, or_port_hist_t *, tp,
+    {
+      char portpolicy[9];
+      if (tp->excluded) {
+        tor_snprintf(portpolicy,sizeof(portpolicy),"*:%u", tp->or_port);
+        log_warn(LD_HIST,"Port %u may be blocked, excluding it temporarily "
+                          "from entry guard selection.", tp->or_port);
+        routerset_parse(rt, portpolicy, "Ports");
+      }
+    });
+}
+
+/** Allow the exclusion of ports during our search for an entry node. */
+void
+or_port_hist_search_again(void)
+{
+    still_searching=1;
+}
Index: src/or/or.h
===================================================================
--- src/or/or.h	(revision 17104)
+++ src/or/or.h	(working copy)
@@ -3864,6 +3864,13 @@
 int any_predicted_circuits(time_t now);
 int rep_hist_circbuilding_dormant(time_t now);
 
+void or_port_hist_failure(const char *digest, uint16_t or_port);
+void or_port_hist_success(uint16_t or_port);
+void or_port_hist_new(const routerinfo_t *ri);
+void or_port_hist_exclude(routerset_t *rt);
+void or_port_hist_search_again(void);
+char *or_port_hist_get_blocked_ports(void);
+
 /** Possible public/private key operations in Tor: used to keep track of where
  * we're spending our time. */
 typedef enum {
Index: src/or/routerparse.c
===================================================================
--- src/or/routerparse.c	(revision 17104)
+++ src/or/routerparse.c	(working copy)
@@ -1401,6 +1401,8 @@
     goto err;
   }
 
+  or_port_hist_new(router);
+
   if (!router->platform) {
     router->platform = tor_strdup("<unknown>");
   }
Index: src/or/router.c
===================================================================
--- src/or/router.c	(revision 17104)
+++ src/or/router.c	(working copy)
@@ -1818,6 +1818,7 @@
   char published[ISO_TIME_LEN+1];
   char digest[DIGEST_LEN];
   char *bandwidth_usage;
+  char *blocked_ports;
   int result;
   size_t len;
 
@@ -1825,7 +1826,6 @@
                 extrainfo->cache_info.identity_digest, DIGEST_LEN);
   format_iso_time(published, extrainfo->cache_info.published_on);
   bandwidth_usage = rep_hist_get_bandwidth_lines(1);
-
   result = tor_snprintf(s, maxlen,
                         "extra-info %s %s\n"
                         "published %s\n%s",
@@ -1835,6 +1835,16 @@
   if (result<0)
     return -1;
 
+  blocked_ports = or_port_hist_get_blocked_ports();
+  if (blocked_ports) {
+      result = tor_snprintf(s+strlen(s), maxlen-strlen(s),
+                            "%s",
+                            blocked_ports);
+      tor_free(blocked_ports);
+      if (result<0)
+        return -1;
+  }
+
   if (should_record_bridge_info(options)) {
     static time_t last_purged_at = 0;
     char *geoip_summary;
Index: src/or/circuitbuild.c
===================================================================
--- src/or/circuitbuild.c	(revision 17104)
+++ src/or/circuitbuild.c	(working copy)
@@ -62,6 +62,7 @@
 
 static void entry_guards_changed(void);
 static time_t start_of_month(time_t when);
+static int num_live_entry_guards(void);
 
 /** Iterate over values of circ_id, starting from conn-\>next_circ_id,
  * and with the high bit specified by conn-\>circ_id_type, until we get
@@ -1627,12 +1628,14 @@
   smartlist_t *excluded;
   or_options_t *options = get_options();
   router_crn_flags_t flags = 0;
+  routerset_t *_ExcludeNodes;
 
   if (state && options->UseEntryGuards &&
       (purpose != CIRCUIT_PURPOSE_TESTING || options->BridgeRelay)) {
     return choose_random_entry(state);
   }
 
+  _ExcludeNodes = routerset_new();
   excluded = smartlist_create();
 
   if (state && (r = build_state_get_exit_router(state))) {
@@ -1670,12 +1673,18 @@
   if (options->_AllowInvalid & ALLOW_INVALID_ENTRY)
     flags |= CRN_ALLOW_INVALID;
 
+  if (options->ExcludeNodes)
+    routerset_union(_ExcludeNodes,options->ExcludeNodes);
+
+  or_port_hist_exclude(_ExcludeNodes);
+
   choice = router_choose_random_node(
            NULL,
            excluded,
-           options->ExcludeNodes,
+           _ExcludeNodes,
            flags);
   smartlist_free(excluded);
+  routerset_free(_ExcludeNodes);
   return choice;
 }
 
@@ -2727,6 +2736,7 @@
 entry_guards_update_state(or_state_t *state)
 {
   config_line_t **next, *line;
+  unsigned int have_reachable_entry=0;
   if (! entry_guards_dirty)
     return;
 
@@ -2740,6 +2750,7 @@
       char dbuf[HEX_DIGEST_LEN+1];
       if (!e->made_contact)
         continue; /* don't write this one to disk */
+      have_reachable_entry=1;
       *next = line = tor_malloc_zero(sizeof(config_line_t));
       line->key = tor_strdup("EntryGuard");
       line->value = tor_malloc(HEX_DIGEST_LEN+MAX_NICKNAME_LEN+2);
@@ -2785,6 +2796,11 @@
   if (!get_options()->AvoidDiskWrites)
     or_state_mark_dirty(get_or_state(), 0);
   entry_guards_dirty = 0;
+
+  /* XXX: Is this the place to decide that we no longer have any reachable
+    guards? */
+  if (!have_reachable_entry)
+    or_port_hist_search_again();
 }
 
 /** If <b>question</b> is the string "entry-guards", then dump