Resolve a FIXME: use identity comparison, not nickname comparison, to

choose circuit ID types.  This is important because our view of "the
nickname of the router on the other side of this connection" is
skewed, and depends on whether we think the other rotuer is
verified--and there's no way to know whether another router thinks you
are verified.

For backward compatibility, we notice when the other router chooses
the same circuit ID type as us (because it's running an old version),
and switch our type to be polite.


svn:r2797

5 files changed, 48 insertions, 37 deletions

diff --git a/doc/tor-spec.txt b/doc/tor-spec.txt
index 95e724287a..7efcc87a7e 100644
--- a/doc/tor-spec.txt
+++ b/doc/tor-spec.txt
@@ -198,13 +198,19 @@ TODO: (very soon)
          DH data (g^y)                 [128 bytes]
          Derivative key data (KH)      [20 bytes]   <see 4.2 below>
 
-   The CircID for a CREATE cell is an arbitrarily chosen 2-byte
-   integer, selected by the node (OP or OR) that sends the CREATE
-   cell.  To prevent CircID collisions, when one OR sends a CREATE
-   cell to another, it chooses from only one half of the possible
-   values based on the ORs' nicknames: if the sending OR has a
-   lexicographically earlier nickname, it chooses a CircID with a high
-   bit of 0; otherwise, it chooses a CircID with a high bit of 1.
+   The CircID for a CREATE cell is an arbitrarily chosen 2-byte integer,
+   selected by the node (OP or OR) that sends the CREATE cell.  To prevent
+   CircID collisions, when one OR sends a CREATE cell to another, it chooses
+   from only one half of the possible values based on the ORs' public
+   identity keys: if the sending OR has a lower key, it chooses a CircID with
+   an MSB of 0; otherwise, it chooses a CircID with an MSB of 1.
+
+   Public keys are compared numerically by modulus.
+
+   (Older versions of Tor compared OR nicknames, and did it in a broken and
+   unreliable way.  To support versions of Tor earlier than 0.0.9pre6,
+   implementations should notice when the other side of a connection is
+   sending CREATE cells with the "wrong" MSG, and switch accordingly.)
 
 4.2. Setting circuit keys
 
diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c
index 12b109ceda..0bd8c01f57 100644
--- a/src/or/circuitbuild.c
+++ b/src/or/circuitbuild.c
@@ -35,14 +35,14 @@ static int count_acceptable_routers(smartlist_t *routers);
  *
  * Return it, or 0 if can't get a unique circ_id.
  */
-static uint16_t get_unique_circ_id_by_conn(connection_t *conn, int circ_id_type) {
+static uint16_t get_unique_circ_id_by_conn(connection_t *conn) {
   uint16_t test_circ_id;
   int attempts=0;
   uint16_t high_bit;
 
   tor_assert(conn);
   tor_assert(conn->type == CONN_TYPE_OR);
-  high_bit = (circ_id_type == CIRC_ID_TYPE_HIGHER) ? 1<<15 : 0;
+  high_bit = (conn->circ_id_type == CIRC_ID_TYPE_HIGHER) ? 1<<15 : 0;
   do {
     /* Sequentially iterate over test_circ_id=1...1<<15-1 until we find a
      * circID such that (high_bit|test_circ_id) is not already used. */
@@ -359,9 +359,7 @@ circuit_deliver_create_cell(circuit_t *circ, char *payload) {
    * Solution: switch to identity-based comparison, but if we get
    * any circuits in the wrong half of the space, switch.
    */
-  circ_id_type = decide_circ_id_type(get_options()->Nickname,
-                                     circ->n_conn->nickname);
-  circ->n_circ_id = get_unique_circ_id_by_conn(circ->n_conn, circ_id_type);
+  circ->n_circ_id = get_unique_circ_id_by_conn(circ->n_conn);
   if(!circ->n_circ_id) {
     log_fn(LOG_WARN,"failed to get unique circID.");
     return -1;
@@ -697,27 +695,6 @@ int circuit_truncated(circuit_t *circ, crypt_path_t *layer) {
 #endif
 }
 
-/** Decide whether the first bit of the circuit ID will be
- * 0 or 1, to avoid conflicts where each side randomly chooses
- * the same circuit ID.
- *
- * Return CIRC_ID_TYPE_LOWER if local_nick is NULL, or if
- * local_nick is lexographically smaller than remote_nick.
- * Else return CIRC_ID_TYPE_HIGHER.
- */
-static int decide_circ_id_type(char *local_nick, char *remote_nick) {
-  int result;
-
-  tor_assert(remote_nick);
-  if(!local_nick)
-    return CIRC_ID_TYPE_LOWER;
-  result = strcasecmp(local_nick, remote_nick);
-  tor_assert(result);
-  if(result < 0)
-    return CIRC_ID_TYPE_LOWER;
-  return CIRC_ID_TYPE_HIGHER;
-}
-
 /** Given a response payload and keys, initialize, then send a created
  * cell back.
  */
diff --git a/src/or/command.c b/src/or/command.c
index 5cc28b8d11..021e12a4fc 100644
--- a/src/or/command.c
+++ b/src/or/command.c
@@ -139,6 +139,22 @@ static void command_process_create_cell(cell_t *cell, connection_t *conn) {
     return;
   }
 
+  /* If the high bit of the circuit ID is not as expected, then switch
+   * which half of the space we'll use for our own CREATE cells.
+   *
+   * This can happen because Tor 0.0.9pre5 and earlier decide which
+   * half to use based on nickname, and we now use identity keys.
+   */
+  if ((cell->circ_id & (1<<15)) && conn->circ_id_type == CIRC_ID_TYPE_HIGHER) {
+    log_fn(LOG_INFO, "Got a high circuit ID from %s (%d); switching to low circuit IDs.",
+           conn->nickname, conn->s);
+    conn->circ_id_type = CIRC_ID_TYPE_LOWER;
+  } else if (!(cell->circ_id & (1<<15)) && conn->circ_id_type == CIRC_ID_TYPE_LOWER) {
+    log_fn(LOG_INFO, "Got a low circuit ID from %s (%d); switching to high circuit IDs.",
+           conn->nickname, conn->s);
+    conn->circ_id_type = CIRC_ID_TYPE_HIGHER;
+  }
+
   circ = circuit_new(cell->circ_id, conn);
   circ->state = CIRCUIT_STATE_ONIONSKIN_PENDING;
   circ->purpose = CIRCUIT_PURPOSE_OR;
diff --git a/src/or/connection_or.c b/src/or/connection_or.c
index 98dc8803bc..1b419e5570 100644
--- a/src/or/connection_or.c
+++ b/src/or/connection_or.c
@@ -339,7 +339,7 @@ connection_tls_finish_handshake(connection_t *conn) {
   conn->state = OR_CONN_STATE_OPEN;
   connection_watch_events(conn, POLLIN);
   log_fn(LOG_DEBUG,"tls handshake done. verifying.");
-  if (! tor_tls_peer_has_cert(conn->tls)) { /* It's an OP. */
+  if (! tor_tls_peer_has_cert(conn->tls)) { /* It's an old OP. */
     if (server_mode(options)) { /* I'm an OR; good. */
       conn->receiver_bucket = conn->bandwidth = DEFAULT_BANDWIDTH_OP;
       return 0;
@@ -348,7 +348,7 @@ connection_tls_finish_handshake(connection_t *conn) {
       return -1;
     }
   }
-  /* Okay; the other side is an OR. */
+  /* Okay; the other side is an OR or a post-0.0.8 OP (with a cert). */
   if (tor_tls_get_peer_cert_nickname(conn->tls, nickname, MAX_NICKNAME_LEN)) {
     log_fn(LOG_WARN,"Other side (%s:%d) has a cert without a valid nickname. Closing.",
            conn->address, conn->port);
@@ -366,6 +366,12 @@ connection_tls_finish_handshake(connection_t *conn) {
   crypto_pk_get_digest(identity_rcvd, digest_rcvd);
   crypto_free_pk_env(identity_rcvd);
 
+  if (crypto_pk_cmp_keys(get_identity_key(), identity_rcvd)<0) {
+    conn->circ_id_type = CIRC_ID_TYPE_LOWER;
+  } else {
+    conn->circ_id_type = CIRC_ID_TYPE_HIGHER;
+  }
+
   router = router_get_by_nickname(nickname);
   if(router && /* we know this nickname */
      router->is_verified && /* make sure it's the right guy */
@@ -394,6 +400,7 @@ connection_tls_finish_handshake(connection_t *conn) {
   if (!server_mode(options)) { /* If I'm an OP... */
     conn->receiver_bucket = conn->bandwidth = DEFAULT_BANDWIDTH_OP;
   }
+
   directory_set_dirty();
   circuit_n_conn_done(conn, 1); /* send the pending creates, if any. */
   /* Note the success */
diff --git a/src/or/or.h b/src/or/or.h
index f8eb0ab94a..b5cb1b639a 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -150,8 +150,10 @@
  * In seconds. */
 #define ROUTER_MAX_AGE (60*60*24)
 
-#define CIRC_ID_TYPE_LOWER 0
-#define CIRC_ID_TYPE_HIGHER 1
+typedef enum {
+  CIRC_ID_TYPE_LOWER=0,
+  CIRC_ID_TYPE_HIGHER=1
+} circ_id_type_t;
 
 #define _CONN_TYPE_MIN 3
 /** Type for sockets listening for OR connections. */
@@ -534,6 +536,9 @@ struct connection_t {
                         * add 'bandwidth' to this, capping it at 10*bandwidth.
                         * (OPEN ORs only)
                         */
+  circ_id_type_t circ_id_type; /**< When we send CREATE cells along this
+                                * connection, which half of the space should
+                                * we use? */
 
 /* Used only by DIR and AP connections: */
   char rend_query[REND_SERVICE_ID_LEN+1]; /**< What rendezvous service are we