Merge branch 'underpinning_squashed'

8 files changed, 127 insertions, 44 deletions

diff --git a/changes/bug17135 b/changes/bug17135
new file mode 100644
index 0000000000..0a0c57e074
--- /dev/null
+++ b/changes/bug17135
@@ -0,0 +1,7 @@
+  o Major features (Ed25519 keys, keypinning)
+    - The key-pinning option on directory authorities is now
+      advisory-only by default. In a future version, or when the
+      AuthDirPinKeys option is set, pins are enforced again.
+      Disabling key-pinning seemed like a good idea so that we can
+      survive the fallout of any usability problems associated with
+      ed25519 keys. Closes ticket 17135.
diff --git a/doc/tor.1.txt b/doc/tor.1.txt
index 14b13bc09e..954c8fa243 100644
--- a/doc/tor.1.txt
+++ b/doc/tor.1.txt
@@ -2081,6 +2081,13 @@ on the public Tor network.
     or more is always sufficient to satisfy the bandwidth requirement
     for the Guard flag. (Default: 250 KBytes)
 
+[[AuthDirPinKeys]] **AuthDirPinKeys** **0**|**1**::
+    Authoritative directories only. If non-zero, do not allow any relay to
+    publish a descriptor if any other relay has reserved its <Ed25519,RSA>
+    identity keypair. In all cases, Tor records every keypair it accepts
+    in a journal if it is new, or if it differs from the most recently
+    accepted pinning for one of the keys it contains. (Default: 0)
+
 [[BridgePassword]] **BridgePassword** __Password__::
     If set, contains an HTTP authenticator that tells a bridge authority to
     serve all requested bridge information. Used by the (only partially
diff --git a/src/or/config.c b/src/or/config.c
index 44fb4ecec6..fa860af337 100644
--- a/src/or/config.c
+++ b/src/or/config.c
@@ -162,6 +162,7 @@ static config_var_t option_vars_[] = {
   V(AuthDirInvalidCCs,           CSV,      ""),
   V(AuthDirFastGuarantee,        MEMUNIT,  "100 KB"),
   V(AuthDirGuardBWGuarantee,     MEMUNIT,  "2 MB"),
+  V(AuthDirPinKeys,              BOOL,     "0"),
   V(AuthDirReject,               LINELIST, NULL),
   V(AuthDirRejectCCs,            CSV,      ""),
   OBSOLETE("AuthDirRejectUnlisted"),
diff --git a/src/or/dirserv.c b/src/or/dirserv.c
index 53b450cef5..8d9f166556 100644
--- a/src/or/dirserv.c
+++ b/src/or/dirserv.c
@@ -248,6 +248,7 @@ dirserv_router_get_status(const routerinfo_t *router, const char **msg,
                           int severity)
 {
   char d[DIGEST_LEN];
+  const int key_pinning = get_options()->AuthDirPinKeys;
 
   if (crypto_pk_get_digest(router->identity_pkey, d)) {
     log_warn(LD_BUG,"Error computing fingerprint");
@@ -261,14 +262,16 @@ dirserv_router_get_status(const routerinfo_t *router, const char **msg,
     if (KEYPIN_MISMATCH ==
         keypin_check((const uint8_t*)router->cache_info.identity_digest,
                      router->signing_key_cert->signing_key.pubkey)) {
-      if (msg) {
-        *msg = "Ed25519 identity key or RSA identity key has changed.";
-      }
       log_fn(severity, LD_DIR,
              "Descriptor from router %s has an Ed25519 key, "
                "but the <rsa,ed25519> keys don't match what they were before.",
                router_describe(router));
-      return FP_REJECT;
+      if (key_pinning) {
+        if (msg) {
+          *msg = "Ed25519 identity key or RSA identity key has changed.";
+        }
+        return FP_REJECT;
+      }
     }
   } else {
     /* No ed25519 key */
@@ -277,13 +280,15 @@ dirserv_router_get_status(const routerinfo_t *router, const char **msg,
       log_fn(severity, LD_DIR,
                "Descriptor from router %s has no Ed25519 key, "
                "when we previously knew an Ed25519 for it. Ignoring for now, "
-               "since Tor 0.2.6 is under development.",
+               "since Ed25519 keys are fairly new.",
                router_describe(router));
 #ifdef DISABLE_DISABLING_ED25519
-      if (msg) {
-        *msg = "Ed25519 identity key has disappeared.";
+      if (key_pinning) {
+        if (msg) {
+          *msg = "Ed25519 identity key has disappeared.";
+        }
+        return FP_REJECT;
       }
-      return FP_REJECT;
 #endif
     }
   }
@@ -582,6 +587,7 @@ dirserv_add_descriptor(routerinfo_t *ri, const char **msg, const char *source)
   char *desc, *nickname;
   const size_t desclen = ri->cache_info.signed_descriptor_len +
       ri->cache_info.annotations_len;
+  const int key_pinning = get_options()->AuthDirPinKeys;
   *msg = NULL;
 
   /* If it's too big, refuse it now. Otherwise we'll cache it all over the
@@ -626,7 +632,8 @@ dirserv_add_descriptor(routerinfo_t *ri, const char **msg, const char *source)
   if (ri->signing_key_cert) {
     keypin_status = keypin_check_and_add(
       (const uint8_t*)ri->cache_info.identity_digest,
-      ri->signing_key_cert->signing_key.pubkey);
+      ri->signing_key_cert->signing_key.pubkey,
+      ! key_pinning);
   } else {
     keypin_status = keypin_check_lone_rsa(
       (const uint8_t*)ri->cache_info.identity_digest);
@@ -635,7 +642,7 @@ dirserv_add_descriptor(routerinfo_t *ri, const char **msg, const char *source)
       keypin_status = KEYPIN_NOT_FOUND;
 #endif
   }
-  if (keypin_status == KEYPIN_MISMATCH) {
+  if (keypin_status == KEYPIN_MISMATCH && key_pinning) {
     log_info(LD_DIRSERV, "Dropping descriptor from %s (source: %s) because "
              "its key did not match an older RSA/Ed25519 keypair",
              router_describe(ri), source);
diff --git a/src/or/keypin.c b/src/or/keypin.c
index ebe83b35d2..047d2b069b 100644
--- a/src/or/keypin.c
+++ b/src/or/keypin.c
@@ -48,7 +48,9 @@ static int keypin_journal_append_entry(const uint8_t *rsa_id_digest,
                                        const uint8_t *ed25519_id_key);
 static int keypin_check_and_add_impl(const uint8_t *rsa_id_digest,
                                      const uint8_t *ed25519_id_key,
-                                     int do_not_add);
+                                     const int do_not_add,
+                                     const int replace);
+static int keypin_add_or_replace_entry_in_map(keypin_ent_t *ent);
 
 static HT_HEAD(rsamap, keypin_ent_st) the_rsa_map = HT_INITIALIZER();
 static HT_HEAD(edmap, keypin_ent_st) the_ed_map = HT_INITIALIZER();
@@ -100,12 +102,17 @@ HT_GENERATE2(edmap, keypin_ent_st, edmap_node, keypin_ent_hash_ed,
  * return KEYPIN_FOUND. If we find an entry that matches one key but
  * not the other, return KEYPIN_MISMATCH.  If we have no entry for either
  * key, add such an entry to the table and return KEYPIN_ADDED.
+ *
+ * If <b>replace_existing_entry</b> is true, then any time we would have said
+ * KEYPIN_FOUND, we instead add this entry anyway and return KEYPIN_ADDED.
  */
 int
 keypin_check_and_add(const uint8_t *rsa_id_digest,
-                     const uint8_t *ed25519_id_key)
+                     const uint8_t *ed25519_id_key,
+                     const int replace_existing_entry)
 {
-  return keypin_check_and_add_impl(rsa_id_digest, ed25519_id_key, 0);
+  return keypin_check_and_add_impl(rsa_id_digest, ed25519_id_key, 0,
+                                   replace_existing_entry);
 }
 
 /**
@@ -116,7 +123,7 @@ int
 keypin_check(const uint8_t *rsa_id_digest,
              const uint8_t *ed25519_id_key)
 {
-  return keypin_check_and_add_impl(rsa_id_digest, ed25519_id_key, 1);
+  return keypin_check_and_add_impl(rsa_id_digest, ed25519_id_key, 1, 0);
 }
 
 /**
@@ -125,7 +132,8 @@ keypin_check(const uint8_t *rsa_id_digest,
 static int
 keypin_check_and_add_impl(const uint8_t *rsa_id_digest,
                           const uint8_t *ed25519_id_key,
-                          int do_not_add)
+                          const int do_not_add,
+                          const int replace)
 {
   keypin_ent_t search, *ent;
   memset(&search, 0, sizeof(search));
@@ -139,18 +147,21 @@ keypin_check_and_add_impl(const uint8_t *rsa_id_digest,
     if (tor_memeq(ent->ed25519_key, ed25519_id_key,sizeof(ent->ed25519_key))) {
       return KEYPIN_FOUND; /* Match on both keys. Great. */
     } else {
-      return KEYPIN_MISMATCH; /* Found RSA with different Ed key */
+      if (!replace)
+        return KEYPIN_MISMATCH; /* Found RSA with different Ed key */
     }
   }
 
   /* See if we know a different RSA key for this ed key */
-  ent = HT_FIND(edmap, &the_ed_map, &search);
-  if (ent) {
-    /* If we got here, then the ed key matches and the RSA doesn't */
-    tor_assert(fast_memeq(ent->ed25519_key, ed25519_id_key,
-                          sizeof(ent->ed25519_key)));
-    tor_assert(fast_memneq(ent->rsa_id, rsa_id_digest, sizeof(ent->rsa_id)));
-    return KEYPIN_MISMATCH;
+  if (! replace) {
+    ent = HT_FIND(edmap, &the_ed_map, &search);
+    if (ent) {
+      /* If we got here, then the ed key matches and the RSA doesn't */
+      tor_assert(fast_memeq(ent->ed25519_key, ed25519_id_key,
+                            sizeof(ent->ed25519_key)));
+      tor_assert(fast_memneq(ent->rsa_id, rsa_id_digest, sizeof(ent->rsa_id)));
+      return KEYPIN_MISMATCH;
+    }
   }
 
   /* Okay, this one is new to us. */
@@ -158,7 +169,12 @@ keypin_check_and_add_impl(const uint8_t *rsa_id_digest,
     return KEYPIN_NOT_FOUND;
 
   ent = tor_memdup(&search, sizeof(search));
-  keypin_add_entry_to_map(ent);
+  int r = keypin_add_or_replace_entry_in_map(ent);
+  if (! replace) {
+    tor_assert(r == 1);
+  } else {
+    tor_assert(r != 0);
+  }
   keypin_journal_append_entry(rsa_id_digest, ed25519_id_key);
   return KEYPIN_ADDED;
 }
@@ -174,6 +190,57 @@ keypin_add_entry_to_map, (keypin_ent_t *ent))
 }
 
 /**
+ * Helper: add 'ent' to the maps, replacing any entries that contradict it.
+ * Take ownership of 'ent', freeing it if needed.
+ *
+ * Return 0 if the entry was a duplicate, -1 if there was a conflict,
+ * and 1 if there was no conflict.
+ */
+static int
+keypin_add_or_replace_entry_in_map(keypin_ent_t *ent)
+{
+  int r = 1;
+  keypin_ent_t *ent2 = HT_FIND(rsamap, &the_rsa_map, ent);
+  keypin_ent_t *ent3 = HT_FIND(edmap, &the_ed_map, ent);
+  if (ent2 &&
+      fast_memeq(ent2->ed25519_key, ent->ed25519_key, DIGEST256_LEN)) {
+    /* We already have this mapping stored. Ignore it. */
+    tor_free(ent);
+    return 0;
+  } else if (ent2 || ent3) {
+    /* We have a conflict. (If we had no entry, we would have ent2 == ent3
+     * == NULL. If we had a non-conflicting duplicate, we would have found
+     * it above.)
+     *
+     * We respond by having this entry (ent) supersede all entries that it
+     * contradicts (ent2 and/or ent3). In other words, if we receive
+     * <rsa,ed>, we remove all <rsa,ed'> and all <rsa',ed>, for rsa'!=rsa
+     * and ed'!= ed.
+     */
+    const keypin_ent_t *t;
+    if (ent2) {
+      t = HT_REMOVE(rsamap, &the_rsa_map, ent2);
+      tor_assert(ent2 == t);
+      t = HT_REMOVE(edmap, &the_ed_map, ent2);
+      tor_assert(ent2 == t);
+    }
+    if (ent3 && ent2 != ent3) {
+      t = HT_REMOVE(rsamap, &the_rsa_map, ent3);
+      tor_assert(ent3 == t);
+      t = HT_REMOVE(edmap, &the_ed_map, ent3);
+      tor_assert(ent3 == t);
+      tor_free(ent3);
+    }
+    tor_free(ent2);
+    r = -1;
+    /* Fall through */
+  }
+
+  keypin_add_entry_to_map(ent);
+  return r;
+}
+
+/**
  * Check whether we already have an entry in the key pinning table for a
  * router with RSA ID digest <b>rsa_id_digest</b>.  If we have no such entry,
  * return KEYPIN_NOT_FOUND.  If we find an entry that matches the RSA key but
@@ -321,22 +388,13 @@ keypin_load_journal_impl(const char *data, size_t size)
       continue;
     }
 
-    const keypin_ent_t *ent2;
-    if ((ent2 = HT_FIND(rsamap, &the_rsa_map, ent))) {
-      if (fast_memeq(ent2->ed25519_key, ent->ed25519_key, DIGEST256_LEN)) {
-        ++n_duplicates;
-      } else {
-        ++n_conflicts;
-      }
-      tor_free(ent);
-      continue;
-    } else if (HT_FIND(edmap, &the_ed_map, ent)) {
-      tor_free(ent);
+    const int r = keypin_add_or_replace_entry_in_map(ent);
+    if (r == 0) {
+      ++n_duplicates;
+    } else if (r == -1) {
       ++n_conflicts;
-      continue;
     }
 
-    keypin_add_entry_to_map(ent);
     ++n_entries;
   }
 
diff --git a/src/or/keypin.h b/src/or/keypin.h
index 2a5b3f1786..798ac1fedb 100644
--- a/src/or/keypin.h
+++ b/src/or/keypin.h
@@ -7,7 +7,8 @@
 #include "testsupport.h"
 
 int keypin_check_and_add(const uint8_t *rsa_id_digest,
-                         const uint8_t *ed25519_id_key);
+                         const uint8_t *ed25519_id_key,
+                         const int replace_existing_entry);
 int keypin_check(const uint8_t *rsa_id_digest,
                  const uint8_t *ed25519_id_key);
 
diff --git a/src/or/or.h b/src/or/or.h
index bec39b2b37..4496cbcec3 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -3790,6 +3790,7 @@ typedef struct {
                                      * number of servers per IP address shared
                                      * with an authority. */
   int AuthDirHasIPv6Connectivity; /**< Boolean: are we on IPv6?  */
+  int AuthDirPinKeys; /**< Boolean: Do we enforce key-pinning? */
 
   /** If non-zero, always vote the Fast flag for any relay advertising
    * this amount of capacity or more. */
diff --git a/src/test/test_keypin.c b/src/test/test_keypin.c
index afd4ca201d..bd0f6fdd52 100644
--- a/src/test/test_keypin.c
+++ b/src/test/test_keypin.c
@@ -108,21 +108,21 @@ test_keypin_parse_file(void *arg)
     ;
 
   tt_int_op(0, ==, keypin_load_journal_impl(data2, strlen(data2)));
-  tt_int_op(11, ==, smartlist_len(mock_addent_got));
+  tt_int_op(13, ==, smartlist_len(mock_addent_got));
   ent = smartlist_get(mock_addent_got, 9);
   tt_mem_op(ent->rsa_id, ==, "\"You have made a goo", 20);
   tt_mem_op(ent->ed25519_key, ==, "d beginning.\" But no more. Wizar", 32);
 
-  ent = smartlist_get(mock_addent_got, 10);
+  ent = smartlist_get(mock_addent_got, 12);
   tt_mem_op(ent->rsa_id, ==, "ds speak truth, and ", 20);
-  tt_mem_op(ent->ed25519_key, ==, "it was true that all the master\n", 32);
+  tt_mem_op(ent->ed25519_key, ==, "it was tru\xa5 that all the master\n", 32);
 
   /* File truncated before NL */
   const char data3[] =
     "Tm8gZHJhZ29uIGNhbiByZXNpc3Q IHRoZSBmYXNjaW5hdGlvbiBvZiByaWRkbGluZyB0YWw";
   tt_int_op(0, ==, keypin_load_journal_impl(data3, strlen(data3)));
-  tt_int_op(12, ==, smartlist_len(mock_addent_got));
-  ent = smartlist_get(mock_addent_got, 11);
+  tt_int_op(14, ==, smartlist_len(mock_addent_got));
+  ent = smartlist_get(mock_addent_got, 13);
   tt_mem_op(ent->rsa_id, ==, "No dragon can resist", 20);
   tt_mem_op(ent->ed25519_key, ==, " the fascination of riddling tal", 32);
 
@@ -131,7 +131,8 @@ test_keypin_parse_file(void *arg)
   smartlist_free(mock_addent_got);
 }
 
-#define ADD(a,b) keypin_check_and_add((const uint8_t*)(a),(const uint8_t*)(b))
+#define ADD(a,b) keypin_check_and_add((const uint8_t*)(a),\
+                                      (const uint8_t*)(b),0)
 #define LONE_RSA(a) keypin_check_lone_rsa((const uint8_t*)(a))
 
 static void