Implement IPv6 sybil protection.

   [This is a squashed patch for ticket 7193, based on taking a "git
   diff" for the original branch, then applying it with "git apply
   -3".  I earlier attempted to squash the branch with "git rebase",
   but there were too many conflicts. --nickm]

4 files changed, 163 insertions, 53 deletions

diff --git a/src/feature/dirauth/dirvote.c b/src/feature/dirauth/dirvote.c
index 8676df76ab..c1ffa25672 100644
--- a/src/feature/dirauth/dirvote.c
+++ b/src/feature/dirauth/dirvote.c
@@ -4,6 +4,7 @@
 /* See LICENSE for licensing information */
 
 #define DIRVOTE_PRIVATE
+
 #include "core/or/or.h"
 #include "app/config/config.h"
 #include "app/config/resolve_addr.h"
@@ -4177,8 +4178,8 @@ dirvote_dirreq_get_status_vote(const char *url, smartlist_t *items,
 
 /** Get the best estimate of a router's bandwidth for dirauth purposes,
  * preferring measured to advertised values if available. */
-static uint32_t
-dirserv_get_bandwidth_for_router_kb(const routerinfo_t *ri)
+MOCK_IMPL(uint32_t,dirserv_get_bandwidth_for_router_kb,
+        (const routerinfo_t *ri))
 {
   uint32_t bw_kb = 0;
   /*
@@ -4207,33 +4208,65 @@ dirserv_get_bandwidth_for_router_kb(const routerinfo_t *ri)
   return bw_kb;
 }
 
-/** Helper for sorting: compares two routerinfos first by address, and then by
- * descending order of "usefulness".  (An authority is more useful than a
- * non-authority; a running router is more useful than a non-running router;
- * and a router with more bandwidth is more useful than one with less.)
+/** Helper for sorting: compares two ipv4 routerinfos first by ipv4 address,
+ * and then by descending order of "usefulness"
+ * (see compare_routerinfo_usefulness)
  **/
-static int
-compare_routerinfo_by_ip_and_bw_(const void **a, const void **b)
+STATIC int
+compare_routerinfo_by_ipv4(const void **a, const void **b)
+{
+  const routerinfo_t *first = *(routerinfo_t **)a;
+  const routerinfo_t *second = *(routerinfo_t **)b;
+  // If addresses are equal, use other comparison criterions
+  int addr_comparison = tor_addr_compare(&(first->ipv4_addr),
+                                         &(second->ipv4_addr), CMP_EXACT);
+  if (addr_comparison == 0) {
+    return compare_routerinfo_usefulness(first, second);
+  } else {
+    // Otherwise, compare the addresses
+    if (addr_comparison < 0 )
+      return -1;
+    else
+      return 1;
+  }
+}
+
+/** Helper for sorting: compares two ipv6 routerinfos first by ipv6 address,
+ * and then by descending order of "usefulness"
+ * (see compare_routerinfo_usefulness)
+ **/
+STATIC int
+compare_routerinfo_by_ipv6(const void **a, const void **b)
+{
+  const routerinfo_t *first = *(routerinfo_t **)a;
+  const routerinfo_t *second = *(routerinfo_t **)b;
+  const tor_addr_t *first_ipv6 = &(first->ipv6_addr);
+  const tor_addr_t *second_ipv6 = &(second->ipv6_addr);
+  int comparison = tor_addr_compare(first_ipv6, second_ipv6, CMP_EXACT);
+  // If addresses are equal, use other comparison criterions
+  if (comparison == 0)
+    return compare_routerinfo_usefulness(first, second);
+  else
+    return comparison;
+}
+
+/**
+* Compare routerinfos by descending order of "usefulness" :
+* An authority is more useful than a non-authority; a running router is
+* more useful than a non-running router; and a router with more bandwidth
+* is more useful than one with less.
+**/
+STATIC int
+compare_routerinfo_usefulness(const routerinfo_t *first,
+                              const routerinfo_t *second)
 {
-  routerinfo_t *first = *(routerinfo_t **)a, *second = *(routerinfo_t **)b;
   int first_is_auth, second_is_auth;
-  uint32_t bw_kb_first, bw_kb_second;
   const node_t *node_first, *node_second;
   int first_is_running, second_is_running;
-  uint32_t first_ipv4h = tor_addr_to_ipv4h(&first->ipv4_addr);
-  uint32_t second_ipv4h = tor_addr_to_ipv4h(&second->ipv4_addr);
-
-  /* we return -1 if first should appear before second... that is,
-   * if first is a better router. */
-  if (first_ipv4h < second_ipv4h)
-    return -1;
-  else if (first_ipv4h > second_ipv4h)
-    return 1;
-
+  uint32_t bw_kb_first, bw_kb_second;
   /* Potentially, this next bit could cause k n lg n memeq calls.  But in
    * reality, we will almost never get here, since addresses will usually be
    * different. */
-
   first_is_auth =
     router_digest_is_trusted_dir(first->cache_info.identity_digest);
   second_is_auth =
@@ -4248,7 +4281,6 @@ compare_routerinfo_by_ip_and_bw_(const void **a, const void **b)
   node_second = node_get_by_id(second->cache_info.identity_digest);
   first_is_running = node_first && node_first->is_running;
   second_is_running = node_second && node_second->is_running;
-
   if (first_is_running && !second_is_running)
     return -1;
   else if (!first_is_running && second_is_running)
@@ -4269,40 +4301,102 @@ compare_routerinfo_by_ip_and_bw_(const void **a, const void **b)
                      DIGEST_LEN);
 }
 
-/** Given a list of routerinfo_t in <b>routers</b>, return a new digestmap_t
- * whose keys are the identity digests of those routers that we're going to
- * exclude for Sybil-like appearance. */
-static digestmap_t *
-get_possible_sybil_list(const smartlist_t *routers)
+/** Given a list of routerinfo_t in <b>routers</b> that all use the same
+ * IP version, specified in <b>family</b>, return a new digestmap_t whose keys
+ * are the identity digests of those routers that we're going to exclude for
+ * Sybil-like appearance.
+ */
+STATIC digestmap_t *
+get_sybil_list_by_ip_version(const smartlist_t *routers, sa_family_t family)
 {
   const dirauth_options_t *options = dirauth_get_options();
-  digestmap_t *omit_as_sybil;
+  digestmap_t *omit_as_sybil = digestmap_new();
   smartlist_t *routers_by_ip = smartlist_new();
-  tor_addr_t last_addr = TOR_ADDR_NULL;
-  int addr_count;
+  int ipv4_addr_count = 0;
+  int ipv6_addr_count = 0;
+  tor_addr_t last_ipv6_addr, last_ipv4_addr;
+  int addr_comparison = 0;
   /* Allow at most this number of Tor servers on a single IP address, ... */
   int max_with_same_addr = options->AuthDirMaxServersPerAddr;
   if (max_with_same_addr <= 0)
     max_with_same_addr = INT_MAX;
 
   smartlist_add_all(routers_by_ip, routers);
-  smartlist_sort(routers_by_ip, compare_routerinfo_by_ip_and_bw_);
-  omit_as_sybil = digestmap_new();
+  if (family == AF_INET6)
+    smartlist_sort(routers_by_ip, compare_routerinfo_by_ipv6);
+  else
+    smartlist_sort(routers_by_ip, compare_routerinfo_by_ipv4);
 
-  addr_count = 0;
   SMARTLIST_FOREACH_BEGIN(routers_by_ip, routerinfo_t *, ri) {
-    if (!tor_addr_eq(&last_addr, &ri->ipv4_addr)) {
-      tor_addr_copy(&last_addr, &ri->ipv4_addr);
-      addr_count = 1;
-    } else if (++addr_count > max_with_same_addr) {
-      digestmap_set(omit_as_sybil, ri->cache_info.identity_digest, ri);
+    if (family == AF_INET6) {
+      addr_comparison = tor_addr_compare(&last_ipv6_addr, &(ri->ipv6_addr),
+              CMP_EXACT);
+      if (addr_comparison != 0) {
+        tor_addr_copy(&last_ipv6_addr, &(ri->ipv6_addr));
+        ipv6_addr_count = 1;
+      } else if (++ipv6_addr_count > max_with_same_addr) {
+        digestmap_set(omit_as_sybil, ri->cache_info.identity_digest, ri);
+      }
+    } else {
+      addr_comparison = tor_addr_compare(&last_ipv4_addr, &(ri->ipv4_addr),
+                                         CMP_EXACT);
+      if (addr_comparison != 0) {
+        tor_addr_copy(&last_ipv4_addr, &(ri->ipv4_addr));
+        ipv4_addr_count = 1;
+      } else if (++ipv4_addr_count > max_with_same_addr) {
+        digestmap_set(omit_as_sybil, ri->cache_info.identity_digest, ri);
+      }
     }
   } SMARTLIST_FOREACH_END(ri);
-
   smartlist_free(routers_by_ip);
   return omit_as_sybil;
 }
 
+/** Given a list of routerinfo_t in <b>routers</b>, return a new digestmap_t
+ * whose keys are the identity digests of those routers that we're going to
+ * exclude for Sybil-like appearance. */
+STATIC digestmap_t *
+get_all_possible_sybil(const smartlist_t *routers)
+{
+  smartlist_t  *routers_ipv6, *routers_ipv4;
+  routers_ipv6 = smartlist_new();
+  routers_ipv4 = smartlist_new();
+  digestmap_t *omit_as_sybil_ipv4 = digestmap_new();
+  digestmap_t *omit_as_sybil_ipv6 = digestmap_new();
+  digestmap_t *omit_as_sybil = digestmap_new();
+  // Sort the routers in two lists depending on their IP version
+  SMARTLIST_FOREACH(routers, routerinfo_t *, ri, {
+      // If the router is IPv6
+      if (tor_addr_family(&(ri->ipv6_addr)) == AF_INET6){
+        smartlist_add(routers_ipv6, ri);
+      }
+      // If the router is IPv4
+      if (tor_addr_family(&(ri->ipv4_addr)) == AF_INET){
+        smartlist_add(routers_ipv4, ri);
+      }
+  });
+  routers_sort_by_identity(routers_ipv4);
+  routers_sort_by_identity(routers_ipv6);
+  omit_as_sybil_ipv4 = get_sybil_list_by_ip_version(routers_ipv4, AF_INET);
+  omit_as_sybil_ipv6 = get_sybil_list_by_ip_version(routers_ipv6, AF_INET6);
+
+  // Add all possible sybils to the common digestmap
+    DIGESTMAP_FOREACH (omit_as_sybil_ipv4, sybil_id, routerinfo_t *, ri) {
+      digestmap_set(omit_as_sybil, ri->cache_info.identity_digest, ri);
+    }
+    DIGESTMAP_FOREACH_END
+    DIGESTMAP_FOREACH (omit_as_sybil_ipv6, sybil_id, routerinfo_t *, ri) {
+      digestmap_set(omit_as_sybil, ri->cache_info.identity_digest, ri);
+    }
+    DIGESTMAP_FOREACH_END
+  // Clean the temp variables
+  smartlist_free(routers_ipv4);
+  smartlist_free(routers_ipv6);
+  digestmap_free(omit_as_sybil_ipv4, NULL);
+  digestmap_free(omit_as_sybil_ipv6, NULL);
+  // Return the digestmap : it now contains all the possible sybils
+  return omit_as_sybil;
+}
 /** Given a platform string as in a routerinfo_t (possibly null), return a
  * newly allocated version string for a networkstatus document, or NULL if the
  * platform doesn't give a Tor version. */
@@ -4477,7 +4571,7 @@ dirserv_generate_networkstatus_vote_obj(crypto_pk_t *private_key,
   time_t cutoff = now - ROUTER_MAX_AGE_TO_PUBLISH;
   networkstatus_voter_info_t *voter = NULL;
   vote_timing_t timing;
-  digestmap_t *omit_as_sybil = NULL;
+  digestmap_t *omit_as_sybil = digestmap_new();
   const int vote_on_reachability = running_long_enough_to_decide_unreachable();
   smartlist_t *microdescriptors = NULL;
   smartlist_t *bw_file_headers = NULL;
@@ -4547,19 +4641,17 @@ dirserv_generate_networkstatus_vote_obj(crypto_pk_t *private_key,
   routers_make_ed_keys_unique(routers);
   /* After this point, don't use rl->routers; use 'routers' instead. */
   routers_sort_by_identity(routers);
-  omit_as_sybil = get_possible_sybil_list(routers);
-
-  DIGESTMAP_FOREACH(omit_as_sybil, sybil_id, void *, ignore) {
-    (void) ignore;
+  /* Get a digestmap of possible sybil routers, IPv4 or IPv6 */
+  omit_as_sybil = get_all_possible_sybil(routers);
+  DIGESTMAP_FOREACH (omit_as_sybil, sybil_id, void *, ignore) {
+    (void)ignore;
     rep_hist_make_router_pessimal(sybil_id, now);
-  } DIGESTMAP_FOREACH_END;
-
+  }
+  DIGESTMAP_FOREACH_END
   /* Count how many have measured bandwidths so we know how to assign flags;
    * this must come before dirserv_compute_performance_thresholds() */
   dirserv_count_measured_bws(routers);
-
   dirserv_compute_performance_thresholds(omit_as_sybil);
-
   routerstatuses = smartlist_new();
   microdescriptors = smartlist_new();
 
@@ -4587,7 +4679,6 @@ dirserv_generate_networkstatus_vote_obj(crypto_pk_t *private_key,
                ri->cache_info.signing_key_cert->signing_key.pubkey,
                ED25519_PUBKEY_LEN);
       }
-
       if (digestmap_get(omit_as_sybil, ri->cache_info.identity_digest))
         clear_status_flags_on_sybil(rs);
 
diff --git a/src/feature/dirauth/dirvote.h b/src/feature/dirauth/dirvote.h
index 9cc87489b4..a4f1b8bfe9 100644
--- a/src/feature/dirauth/dirvote.h
+++ b/src/feature/dirauth/dirvote.h
@@ -183,6 +183,8 @@ dirvote_add_signatures(const char *detached_signatures_body,
 /* Item access */
 MOCK_DECL(const char*, dirvote_get_pending_consensus,
           (consensus_flavor_t flav));
+MOCK_DECL(uint32_t,dirserv_get_bandwidth_for_router_kb,
+        (const routerinfo_t *ri));
 MOCK_DECL(const char*, dirvote_get_pending_detached_signatures, (void));
 const cached_dir_t *dirvote_get_vote(const char *fp, int flags);
 
@@ -234,6 +236,22 @@ int networkstatus_add_detached_signatures(networkstatus_t *target,
                                           const char *source,
                                           int severity,
                                           const char **msg_out);
+STATIC int
+compare_routerinfo_usefulness(const routerinfo_t *first,
+                              const routerinfo_t *second);
+STATIC
+int compare_routerinfo_by_ipv4(const void **a, const void **b);
+
+STATIC
+int compare_routerinfo_by_ipv6(const void **a, const void **b);
+
+STATIC
+digestmap_t * get_sybil_list_by_ip_version(
+    const smartlist_t *routers, sa_family_t family);
+
+STATIC
+digestmap_t * get_all_possible_sybil(const smartlist_t *routers);
+
 STATIC
 char *networkstatus_get_detached_signatures(smartlist_t *consensuses);
 STATIC microdesc_t *dirvote_create_microdescriptor(const routerinfo_t *ri,
diff --git a/src/feature/nodelist/dirlist.c b/src/feature/nodelist/dirlist.c
index cd2921e653..f6e4662a0f 100644
--- a/src/feature/nodelist/dirlist.c
+++ b/src/feature/nodelist/dirlist.c
@@ -236,8 +236,8 @@ mark_all_dirservers_up(smartlist_t *server_list)
 /** Return true iff <b>digest</b> is the digest of the identity key of a
  * trusted directory matching at least one bit of <b>type</b>.  If <b>type</b>
  * is zero (NO_DIRINFO), or ALL_DIRINFO, any authority is okay. */
-int
-router_digest_is_trusted_dir_type(const char *digest, dirinfo_type_t type)
+MOCK_IMPL(int, router_digest_is_trusted_dir_type,
+        (const char *digest, dirinfo_type_t type))
 {
   if (!trusted_dir_servers)
     return 0;
diff --git a/src/feature/nodelist/dirlist.h b/src/feature/nodelist/dirlist.h
index c9310ff357..ae3debf4e5 100644
--- a/src/feature/nodelist/dirlist.h
+++ b/src/feature/nodelist/dirlist.h
@@ -25,13 +25,14 @@ int router_digest_is_fallback_dir(const char *digest);
 MOCK_DECL(dir_server_t *, trusteddirserver_get_by_v3_auth_digest,
           (const char *d));
 
+MOCK_DECL(int, router_digest_is_trusted_dir_type,
+        (const char *digest, dirinfo_type_t type));
+
 bool router_addr_is_trusted_dir_type(const tor_addr_t *addr,
                                      dirinfo_type_t type);
 #define router_addr_is_trusted_dir(d) \
   router_addr_is_trusted_dir_type((d), NO_DIRINFO)
 
-int router_digest_is_trusted_dir_type(const char *digest,
-                                      dirinfo_type_t type);
 #define router_digest_is_trusted_dir(d) \
   router_digest_is_trusted_dir_type((d), NO_DIRINFO)