Merge branch 'prop176-v2'

6 files changed, 1294 insertions, 123 deletions

diff --git a/src/or/buffers.c b/src/or/buffers.c
index 1025cedad2..c589fbaefa 100644
--- a/src/or/buffers.c
+++ b/src/or/buffers.c
@@ -1005,6 +1005,32 @@ fetch_from_buf(char *string, size_t string_len, buf_t *buf)
   return (int)buf->datalen;
 }
 
+/** True iff the cell command <b>command</b> is one that implies a variable-length
+ * cell in Tor link protocol <b>linkproto</b>. */
+static inline int
+cell_command_is_var_length(uint8_t command, int linkproto)
+{
+  /* If linkproto is v2 (2), CELL_VERSIONS is the only variable-length cells work as
+   * implemented here. If it's 1, there are no variable-length cells.  Tor
+   * does not support other versions right now, and so can't negotiate them.
+   */
+  switch (linkproto) {
+  case 1:
+    /* Link protocol version 1 has no variable-length cells. */
+    return 0;
+  case 2:
+    /* In link protocol version 2, VERSIONS is the only variable-length cell */
+    return command == CELL_VERSIONS;
+  case 0:
+  case 3:
+  default:
+    /* In link protocol version 3 and later, and in version "unknown",
+     * commands 128 and higher indicate variable-length. VERSIONS is
+     * grandfathered in. */
+    return command == CELL_VERSIONS || command >= 128;
+  }
+}
+
 /** Check <b>buf</b> for a variable-length cell according to the rules of link
  * protocol version <b>linkproto</b>.  If one is found, pull it off the buffer
  * and assign a newly allocated var_cell_t to *<b>out</b>, and return 1.
@@ -1019,12 +1045,6 @@ fetch_var_cell_from_buf(buf_t *buf, var_cell_t **out, int linkproto)
   var_cell_t *result;
   uint8_t command;
   uint16_t length;
-  /* If linkproto is unknown (0) or v2 (2), variable-length cells work as
-   * implemented here. If it's 1, there are no variable-length cells.  Tor
-   * does not support other versions right now, and so can't negotiate them.
-   */
-  if (linkproto == 1)
-    return 0;
   check();
   *out = NULL;
   if (buf->datalen < VAR_CELL_HEADER_SIZE)
@@ -1032,7 +1052,7 @@ fetch_var_cell_from_buf(buf_t *buf, var_cell_t **out, int linkproto)
   peek_from_buf(hdr, sizeof(hdr), buf);
 
   command = get_uint8(hdr+2);
-  if (!(CELL_COMMAND_IS_VAR_LENGTH(command)))
+  if (!(cell_command_is_var_length(command, linkproto)))
     return 0;
 
   length = ntohs(get_uint16(hdr+3));
@@ -1101,8 +1121,6 @@ fetch_var_cell_from_evbuffer(struct evbuffer *buf, var_cell_t **out,
   uint16_t cell_length;
   var_cell_t *cell;
   int result = 0;
-  if (linkproto == 1)
-    return 0;
 
   *out = NULL;
   buf_len = evbuffer_get_length(buf);
@@ -1113,7 +1131,7 @@ fetch_var_cell_from_evbuffer(struct evbuffer *buf, var_cell_t **out,
   tor_assert(n >= VAR_CELL_HEADER_SIZE);
 
   command = get_uint8(hdr+2);
-  if (!(CELL_COMMAND_IS_VAR_LENGTH(command))) {
+  if (!(cell_command_is_var_length(command, linkproto))) {
     goto done;
   }
 
diff --git a/src/or/command.c b/src/or/command.c
index d24373eec8..a511156318 100644
--- a/src/or/command.c
+++ b/src/or/command.c
@@ -46,6 +46,15 @@ uint64_t stats_n_versions_cells_processed = 0;
 /** How many CELL_NETINFO cells have we received, ever? */
 uint64_t stats_n_netinfo_cells_processed = 0;
 
+/** How many CELL_VPADDING cells have we received, ever? */
+uint64_t stats_n_vpadding_cells_processed = 0;
+/** How many CELL_CERTS cells have we received, ever? */
+uint64_t stats_n_cert_cells_processed = 0;
+/** How many CELL_AUTH_CHALLENGE cells have we received, ever? */
+uint64_t stats_n_auth_challenge_cells_processed = 0;
+/** How many CELL_AUTHENTICATE cells have we received, ever? */
+uint64_t stats_n_authenticate_cells_processed = 0;
+
 /* These are the main functions for processing cells */
 static void command_process_create_cell(cell_t *cell, or_connection_t *conn);
 static void command_process_created_cell(cell_t *cell, or_connection_t *conn);
@@ -54,6 +63,12 @@ static void command_process_destroy_cell(cell_t *cell, or_connection_t *conn);
 static void command_process_versions_cell(var_cell_t *cell,
                                           or_connection_t *conn);
 static void command_process_netinfo_cell(cell_t *cell, or_connection_t *conn);
+static void command_process_cert_cell(var_cell_t *cell,
+                                      or_connection_t *conn);
+static void command_process_auth_challenge_cell(var_cell_t *cell,
+                                          or_connection_t *conn);
+static void command_process_authenticate_cell(var_cell_t *cell,
+                                          or_connection_t *conn);
 
 #ifdef KEEP_TIMING_STATS
 /** This is a wrapper function around the actual function that processes the
@@ -93,7 +108,7 @@ command_time_process_cell(cell_t *cell, or_connection_t *conn, int *time,
 void
 command_process_cell(cell_t *cell, or_connection_t *conn)
 {
-  int handshaking = (conn->_base.state == OR_CONN_STATE_OR_HANDSHAKING);
+  int handshaking = (conn->_base.state != OR_CONN_STATE_OPEN);
 #ifdef KEEP_TIMING_STATS
   /* how many of each cell have we seen so far this second? needs better
    * name. */
@@ -134,9 +149,18 @@ command_process_cell(cell_t *cell, or_connection_t *conn)
 #endif
 
   /* Reject all but VERSIONS and NETINFO when handshaking. */
+  /* (VERSIONS should actually be impossible; it's variable-length.) */
   if (handshaking && cell->command != CELL_VERSIONS &&
-      cell->command != CELL_NETINFO)
+      cell->command != CELL_NETINFO) {
+    log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
+           "Received unexpected cell command %d in state %s; ignoring it.",
+           (int)cell->command,
+           conn_state_to_string(CONN_TYPE_OR,conn->_base.state));
     return;
+  }
+
+  if (conn->_base.state == OR_CONN_STATE_OR_HANDSHAKING_V3)
+    or_handshake_state_record_cell(conn->handshake_state, cell, 1);
 
   switch (cell->command) {
     case CELL_PADDING:
@@ -206,20 +230,79 @@ command_process_var_cell(var_cell_t *cell, or_connection_t *conn)
   }
 #endif
 
-  /* reject all when not handshaking. */
-  if (conn->_base.state != OR_CONN_STATE_OR_HANDSHAKING)
-    return;
+  switch (conn->_base.state)
+  {
+    case OR_CONN_STATE_OR_HANDSHAKING_V2:
+      if (cell->command != CELL_VERSIONS)
+        return;
+      break;
+    case OR_CONN_STATE_TLS_HANDSHAKING:
+      /* If we're using bufferevents, it's entirely possible for us to
+       * notice "hey, data arrived!" before we notice "hey, the handshake
+       * finished!" And we need to be accepting both at once to handle both
+       * the v2 and v3 handshakes. */
+
+      /* fall through */
+    case OR_CONN_STATE_TLS_SERVER_RENEGOTIATING:
+      if (cell->command != CELL_VERSIONS) {
+        log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
+               "Received a non-VERSIONS cell with command %d in state %s; "
+               "ignoring it.",
+               (int)cell->command,
+               conn_state_to_string(CONN_TYPE_OR,conn->_base.state));
+        return;
+      }
+      break;
+    case OR_CONN_STATE_OR_HANDSHAKING_V3:
+      if (cell->command != CELL_AUTHENTICATE)
+        or_handshake_state_record_var_cell(conn->handshake_state, cell, 1);
+      break; /* Everything is allowed */
+    case OR_CONN_STATE_OPEN:
+      if (conn->link_proto < 3) {
+        log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
+               "Received a variable-length cell with command %d in state %s "
+               "with link protocol %d; ignoring it.",
+               (int)cell->command,
+               conn_state_to_string(CONN_TYPE_OR,conn->_base.state),
+               (int)conn->link_proto);
+        return;
+      }
+      break;
+    default:
+      log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
+             "Received var-length cell with command %d in unexpected state "
+             "%s [%d]; ignoring it.",
+             (int)cell->command,
+             conn_state_to_string(CONN_TYPE_OR,conn->_base.state),
+             (int)conn->_base.state);
+      return;
+  }
 
   switch (cell->command) {
     case CELL_VERSIONS:
       ++stats_n_versions_cells_processed;
       PROCESS_CELL(versions, cell, conn);
       break;
+    case CELL_VPADDING:
+      ++stats_n_vpadding_cells_processed;
+      PROCESS_CELL(versions, cell, conn);
+      break;
+    case CELL_CERT:
+      ++stats_n_cert_cells_processed;
+      PROCESS_CELL(cert, cell, conn);
+      break;
+    case CELL_AUTH_CHALLENGE:
+      ++stats_n_auth_challenge_cells_processed;
+      PROCESS_CELL(auth_challenge, cell, conn);
+      break;
+    case CELL_AUTHENTICATE:
+      ++stats_n_authenticate_cells_processed;
+      PROCESS_CELL(authenticate, cell, conn);
+      break;
     default:
-      log_warn(LD_BUG,
+      log_fn(LOG_INFO, LD_PROTOCOL,
                "Variable-length cell of unknown type (%d) received.",
                cell->command);
-      tor_fragile_assert();
       break;
   }
 }
@@ -505,14 +588,40 @@ command_process_versions_cell(var_cell_t *cell, or_connection_t *conn)
 {
   int highest_supported_version = 0;
   const uint8_t *cp, *end;
+  const int started_here = connection_or_nonopen_was_started_here(conn);
   if (conn->link_proto != 0 ||
-      conn->_base.state != OR_CONN_STATE_OR_HANDSHAKING ||
       (conn->handshake_state && conn->handshake_state->received_versions)) {
     log_fn(LOG_PROTOCOL_WARN, LD_OR,
            "Received a VERSIONS cell on a connection with its version "
            "already set to %d; dropping", (int) conn->link_proto);
     return;
   }
+  switch (conn->_base.state)
+    {
+    case OR_CONN_STATE_OR_HANDSHAKING_V2:
+      break;
+    case OR_CONN_STATE_TLS_HANDSHAKING:
+    case OR_CONN_STATE_TLS_SERVER_RENEGOTIATING:
+      if (started_here) {
+        log_fn(LOG_PROTOCOL_WARN, LD_OR,
+               "Received a versions cell while TLS-handshaking not in "
+               "OR_HANDSHAKING_V3 on a connection we originated.");
+      }
+      conn->_base.state = OR_CONN_STATE_OR_HANDSHAKING_V3;
+      if (connection_init_or_handshake_state(conn, started_here) < 0) {
+        connection_mark_for_close(TO_CONN(conn));
+        return;
+      }
+      or_handshake_state_record_var_cell(conn->handshake_state, cell, 1);
+      break;
+    case OR_CONN_STATE_OR_HANDSHAKING_V3:
+      break;
+    default:
+      log_fn(LOG_PROTOCOL_WARN, LD_OR,
+             "VERSIONS cell while in unexpected state");
+      return;
+  }
+
   tor_assert(conn->handshake_state);
   end = cell->payload + cell->payload_len;
   for (cp = cell->payload; cp+1 < end; ++cp) {
@@ -534,19 +643,87 @@ command_process_versions_cell(var_cell_t *cell, or_connection_t *conn)
            "That's crazily non-compliant. Closing connection.");
     connection_mark_for_close(TO_CONN(conn));
     return;
+  } else if (highest_supported_version < 3 &&
+             conn->_base.state ==  OR_CONN_STATE_OR_HANDSHAKING_V3) {
+    log_fn(LOG_PROTOCOL_WARN, LD_OR,
+           "Negotiated link protocol 2 or lower after doing a v3 TLS "
+           "handshake. Closing connection.");
+    connection_mark_for_close(TO_CONN(conn));
+    return;
   }
+
   conn->link_proto = highest_supported_version;
   conn->handshake_state->received_versions = 1;
 
-  log_info(LD_OR, "Negotiated version %d with %s:%d; sending NETINFO.",
-           highest_supported_version,
-           safe_str_client(conn->_base.address),
-           conn->_base.port);
-  tor_assert(conn->link_proto >= 2);
+  if (conn->link_proto == 2) {
+    log_info(LD_OR, "Negotiated version %d with %s:%d; sending NETINFO.",
+             highest_supported_version,
+             safe_str_client(conn->_base.address),
+             conn->_base.port);
 
-  if (connection_or_send_netinfo(conn) < 0) {
-    connection_mark_for_close(TO_CONN(conn));
-    return;
+    if (connection_or_send_netinfo(conn) < 0) {
+      connection_mark_for_close(TO_CONN(conn));
+      return;
+    }
+  } else {
+    const int send_versions = !started_here;
+    /* If we want to authenticate, send a CERTS cell */
+    const int send_certs = !started_here || public_server_mode(get_options());
+    /* If we're a relay that got a connection, ask for authentication. */
+    const int send_chall = !started_here && public_server_mode(get_options());
+    /* If our certs cell will authenticate us, or if we have no intention of
+     * authenticating, send a netinfo cell right now. */
+    const int send_netinfo =
+      !(started_here && public_server_mode(get_options()));
+    const int send_any =
+      send_versions || send_certs || send_chall || send_netinfo;
+    tor_assert(conn->link_proto >= 3);
+
+    log_info(LD_OR, "Negotiated version %d with %s:%d; %s%s%s%s%s",
+             highest_supported_version,
+             safe_str_client(conn->_base.address),
+             conn->_base.port,
+             send_any ? "Sending cells:" : "Waiting for CERTS cell",
+             send_versions ? " VERSIONS" : "",
+             send_certs ? " CERTS" : "",
+             send_chall ? " AUTH_CHALLENGE" : "",
+             send_netinfo ? " NETINFO" : "");
+
+#ifdef DISABLE_V3_LINKPROTO_SERVERSIDE
+    if (1) {
+      connection_mark_for_close(TO_CONN(conn));
+      return;
+    }
+#endif
+
+    if (send_versions) {
+      if (connection_or_send_versions(conn, 1) < 0) {
+        log_warn(LD_OR, "Couldn't send versions cell");
+        connection_mark_for_close(TO_CONN(conn));
+        return;
+      }
+    }
+    if (send_certs) {
+      if (connection_or_send_cert_cell(conn) < 0) {
+        log_warn(LD_OR, "Couldn't send cert cell");
+        connection_mark_for_close(TO_CONN(conn));
+        return;
+      }
+    }
+    if (send_chall) {
+      if (connection_or_send_auth_challenge_cell(conn) < 0) {
+        log_warn(LD_OR, "Couldn't send auth_challenge cell");
+        connection_mark_for_close(TO_CONN(conn));
+        return;
+      }
+    }
+    if (send_netinfo) {
+      if (connection_or_send_netinfo(conn) < 0) {
+        log_warn(LD_OR, "Couldn't send netinfo cell");
+        connection_mark_for_close(TO_CONN(conn));
+        return;
+      }
+    }
   }
 }
 
@@ -572,13 +749,41 @@ command_process_netinfo_cell(cell_t *cell, or_connection_t *conn)
            conn->link_proto == 0 ? "non-versioned" : "a v1");
     return;
   }
-  if (conn->_base.state != OR_CONN_STATE_OR_HANDSHAKING) {
+  if (conn->_base.state != OR_CONN_STATE_OR_HANDSHAKING_V2 &&
+      conn->_base.state != OR_CONN_STATE_OR_HANDSHAKING_V3) {
     log_fn(LOG_PROTOCOL_WARN, LD_OR,
            "Received a NETINFO cell on non-handshaking connection; dropping.");
     return;
   }
   tor_assert(conn->handshake_state &&
              conn->handshake_state->received_versions);
+
+  if (conn->_base.state == OR_CONN_STATE_OR_HANDSHAKING_V3) {
+    tor_assert(conn->link_proto >= 3);
+    if (conn->handshake_state->started_here) {
+      if (!conn->handshake_state->authenticated) {
+        log_fn(LOG_PROTOCOL_WARN, LD_OR, "Got a NETINFO cell from server, "
+               "but no authentication.  Closing the connection.");
+        connection_mark_for_close(TO_CONN(conn));
+        return;
+      }
+    } else {
+      /* we're the server.  If the client never authenticated, we have
+         some housekeeping to do.*/
+      if (!conn->handshake_state->authenticated) {
+        tor_assert(tor_digest_is_zero(
+                  (const char*)conn->handshake_state->authenticated_peer_id));
+        connection_or_set_circid_type(conn, NULL);
+
+        connection_or_init_conn_from_address(conn,
+                  &conn->_base.addr,
+                  conn->_base.port,
+                  (const char*)conn->handshake_state->authenticated_peer_id,
+                  0);
+      }
+    }
+  }
+
   /* Decode the cell. */
   timestamp = ntohl(get_uint32(cell->payload));
   if (labs(now - conn->handshake_state->sent_versions_at) < 180) {
@@ -651,13 +856,386 @@ command_process_netinfo_cell(cell_t *cell, or_connection_t *conn)
    * trustworthy. */
   (void)my_apparent_addr;
 
-  if (connection_or_set_state_open(conn)<0)
+  if (connection_or_set_state_open(conn)<0) {
+    log_fn(LOG_PROTOCOL_WARN, LD_OR, "Got good NETINFO cell from %s:%d; but "
+           "was unable to make the OR connection become open.",
+           safe_str_client(conn->_base.address),
+           conn->_base.port);
     connection_mark_for_close(TO_CONN(conn));
-  else
+  } else {
     log_info(LD_OR, "Got good NETINFO cell from %s:%d; OR connection is now "
-             "open, using protocol version %d",
+             "open, using protocol version %d. Its ID digest is %s",
              safe_str_client(conn->_base.address),
-             conn->_base.port, (int)conn->link_proto);
+             conn->_base.port, (int)conn->link_proto,
+             hex_str(conn->identity_digest, DIGEST_LEN));
+  }
   assert_connection_ok(TO_CONN(conn),time(NULL));
 }
 
+/** Process a CERT cell from an OR connection.
+ *
+ * If the other side should not have sent us a CERT cell, or the cell is
+ * malformed, or it is supposed to authenticate the TLS key but it doesn't,
+ * then mark the connection.
+ *
+ * If the cell has a good cert chain and we're doing a v3 handshake, then
+ * store the certificates in or_handshake_state.  If this is the client side
+ * of the connection, we then authenticate the server or mark the connection.
+ * If it's the server side, wait for an AUTHENTICATE cell.
+ */
+static void
+command_process_cert_cell(var_cell_t *cell, or_connection_t *conn)
+{
+#define ERR(s)                                                  \
+  do {                                                          \
+    log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,                      \
+           "Received a bad CERT cell from %s:%d: %s",           \
+           safe_str(conn->_base.address), conn->_base.port, (s)); \
+    connection_mark_for_close(TO_CONN(conn));                   \
+    goto err;                                                   \
+  } while (0)
+
+  tor_cert_t *link_cert = NULL;
+  tor_cert_t *id_cert = NULL;
+  tor_cert_t *auth_cert = NULL;
+
+  uint8_t *ptr;
+  int n_certs, i;
+
+  if (conn->_base.state != OR_CONN_STATE_OR_HANDSHAKING_V3)
+    ERR("We're not doing a v3 handshake!");
+  if (conn->link_proto < 3)
+    ERR("We're not using link protocol >= 3");
+  if (conn->handshake_state->received_cert_cell)
+    ERR("We already got one");
+  if (conn->handshake_state->authenticated) {
+    /* Should be unreachable, but let's make sure. */
+    ERR("We're already authenticated!");
+  }
+  if (cell->payload_len < 1)
+    ERR("It had no body");
+  if (cell->circ_id)
+    ERR("It had a nonzero circuit ID");
+
+  n_certs = cell->payload[0];
+  ptr = cell->payload + 1;
+  for (i = 0; i < n_certs; ++i) {
+    uint8_t cert_type;
+    uint16_t cert_len;
+    if (ptr + 3 > cell->payload + cell->payload_len) {
+      goto truncated;
+    }
+    cert_type = *ptr;
+    cert_len = ntohs(get_uint16(ptr+1));
+    if (ptr + 3 + cert_len > cell->payload + cell->payload_len) {
+      goto truncated;
+    }
+    if (cert_type == OR_CERT_TYPE_TLS_LINK ||
+        cert_type == OR_CERT_TYPE_ID_1024 ||
+        cert_type == OR_CERT_TYPE_AUTH_1024) {
+      tor_cert_t *cert = tor_cert_decode(ptr + 3, cert_len);
+      if (!cert) {
+        log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
+               "Received undecodable certificate in CERT cell from %s:%d",
+               safe_str(conn->_base.address), conn->_base.port);
+      } else {
+        if (cert_type == OR_CERT_TYPE_TLS_LINK) {
+          if (link_cert) {
+            tor_cert_free(cert);
+            ERR("Too many TLS_LINK certificates");
+          }
+          link_cert = cert;
+        } else if (cert_type == OR_CERT_TYPE_ID_1024) {
+          if (id_cert) {
+            tor_cert_free(cert);
+            ERR("Too many ID_1024 certificates");
+          }
+          id_cert = cert;
+        } else if (cert_type == OR_CERT_TYPE_AUTH_1024) {
+          if (auth_cert) {
+            tor_cert_free(cert);
+            ERR("Too many AUTH_1024 certificates");
+          }
+          auth_cert = cert;
+        } else {
+          tor_cert_free(cert);
+        }
+      }
+    }
+    ptr += 3 + cert_len;
+    continue;
+
+  truncated:
+    ERR("It ends in the middle of a certificate");
+  }
+
+  if (conn->handshake_state->started_here) {
+    if (! (id_cert && link_cert))
+      ERR("The certs we wanted were missing");
+    /* Okay. We should be able to check the certificates now. */
+    if (! tor_tls_cert_matches_key(conn->tls, link_cert)) {
+      ERR("The link certificate didn't match the TLS public key");
+    }
+    if (! tor_tls_cert_is_valid(link_cert, id_cert, 0))
+      ERR("The link certificate was not valid");
+    if (! tor_tls_cert_is_valid(id_cert, id_cert, 1))
+      ERR("The ID certificate was not valid");
+
+    conn->handshake_state->authenticated = 1;
+    {
+      const digests_t *id_digests = tor_cert_get_id_digests(id_cert);
+      crypto_pk_env_t *identity_rcvd;
+      if (!id_digests)
+        ERR("Couldn't compute digests for key in ID cert");
+
+      identity_rcvd = tor_tls_cert_get_key(id_cert);
+      memcpy(conn->handshake_state->authenticated_peer_id,
+             id_digests->d[DIGEST_SHA1], DIGEST_LEN);
+      connection_or_set_circid_type(conn, identity_rcvd);
+      crypto_free_pk_env(identity_rcvd);
+    }
+
+    if (connection_or_client_learned_peer_id(conn,
+                      conn->handshake_state->authenticated_peer_id) < 0)
+      ERR("Problem setting or checking peer id");
+
+    log_info(LD_OR, "Got some good certificates from %s:%d: Authenticated it.",
+             safe_str(conn->_base.address), conn->_base.port);
+
+    conn->handshake_state->id_cert = id_cert;
+    id_cert = NULL;
+  } else {
+    if (! (id_cert && auth_cert))
+      ERR("The certs we wanted were missing");
+
+    /* Remember these certificates so we can check an AUTHENTICATE cell */
+    conn->handshake_state->id_cert = id_cert;
+    conn->handshake_state->auth_cert = auth_cert;
+    if (! tor_tls_cert_is_valid(auth_cert, id_cert, 1))
+      ERR("The authentication certificate was not valid");
+    if (! tor_tls_cert_is_valid(id_cert, id_cert, 1))
+      ERR("The ID certificate was not valid");
+
+
+    log_info(LD_OR, "Got some good certificates from %s:%d: "
+             "Waiting for AUTHENTICATE.",
+             safe_str(conn->_base.address), conn->_base.port);
+    /* XXXX check more stuff? */
+
+    id_cert = auth_cert = NULL;
+  }
+
+  conn->handshake_state->received_cert_cell = 1;
+err:
+  tor_cert_free(id_cert);
+  tor_cert_free(link_cert);
+  tor_cert_free(auth_cert);
+#undef ERR
+}
+
+/** Process an AUTH_CHALLENGE cell from an OR connection.
+ *
+ * If we weren't supposed to get one (for example, because we're not the
+ * originator of the connection), or it's ill-formed, or we aren't doing a v3
+ * handshake, mark the connection.  If the cell is well-formed but we don't
+ * want to authenticate, just drop it.  If the cell is well-formed *and* we
+ * want to authenticate, send an AUTHENTICATE cell. */
+static void
+command_process_auth_challenge_cell(var_cell_t *cell, or_connection_t *conn)
+{
+  int n_types, i, use_type = -1;
+  uint8_t *cp;
+
+#define ERR(s)                                                  \
+  do {                                                          \
+    log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,                      \
+           "Received a bad AUTH_CHALLENGE cell from %s:%d: %s", \
+           safe_str(conn->_base.address), conn->_base.port, (s));       \
+    connection_mark_for_close(TO_CONN(conn));                   \
+    return;                                                     \
+  } while (0)
+
+  if (conn->_base.state != OR_CONN_STATE_OR_HANDSHAKING_V3)
+    ERR("We're not currently doing a v3 handshake");
+  if (conn->link_proto < 3)
+    ERR("We're not using link protocol >= 3");
+  if (! conn->handshake_state->started_here)
+    ERR("We didn't originate this connection");
+  if (conn->handshake_state->received_auth_challenge)
+    ERR("We already received one");
+  if (! conn->handshake_state->received_cert_cell)
+    ERR("We haven't gotten a CERTS cell yet");
+  if (cell->payload_len < OR_AUTH_CHALLENGE_LEN + 2)
+    ERR("It was too short");
+  if (cell->circ_id)
+    ERR("It had a nonzero circuit ID");
+
+  n_types = ntohs(get_uint16(cell->payload + OR_AUTH_CHALLENGE_LEN));
+  if (cell->payload_len < OR_AUTH_CHALLENGE_LEN + 2 + 2*n_types)
+    ERR("It looks truncated");
+
+  /* Now see if there is an authentication type we can use */
+  cp=cell->payload+OR_AUTH_CHALLENGE_LEN+2;
+  for (i=0; i < n_types; ++i, cp += 2) {
+    uint16_t authtype = ntohs(get_uint16(cp));
+    if (authtype == AUTHTYPE_RSA_SHA256_TLSSECRET)
+      use_type = authtype;
+  }
+
+  conn->handshake_state->received_auth_challenge = 1;
+
+  if (use_type && public_server_mode(get_options())) {
+    log_info(LD_OR, "Got an AUTH_CHALLENGE cell from %s:%d: Sending "
+             "authentication",
+             safe_str(conn->_base.address), conn->_base.port);
+
+    if (connection_or_send_authenticate_cell(conn, use_type) < 0) {
+      log_warn(LD_OR, "Couldn't send authenticate cell");
+      connection_mark_for_close(TO_CONN(conn));
+      return;
+    }
+    if (connection_or_send_netinfo(conn) < 0) {
+      log_warn(LD_OR, "Couldn't send netinfo cell");
+      connection_mark_for_close(TO_CONN(conn));
+      return;
+    }
+  } else {
+    log_info(LD_OR, "Got an AUTH_CHALLENGE cell from %s:%d: Not authenticating",
+             safe_str(conn->_base.address), conn->_base.port);
+  }
+#undef ERR
+}
+
+/** Process an AUTHENTICATE cell from an OR connection.
+ *
+ * If it's ill-formed or we weren't supposed to get one or we're not doing a
+ * v3 handshake, then mark the connection.  If it does not authenticate the
+ * other side of the connection successfully (because it isn't signed right,
+ * we didn't get a CERT cell, etc) mark the connection.  Otherwise, accept
+ * the identity of the router on the other side of the connection.
+ */
+static void
+command_process_authenticate_cell(var_cell_t *cell, or_connection_t *conn)
+{
+  uint8_t expected[V3_AUTH_FIXED_PART_LEN];
+  const uint8_t *auth;
+  int authlen;
+
+#define ERR(s)                                                  \
+  do {                                                          \
+    log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,                      \
+           "Received a bad AUTHETNICATE cell from %s:%d: %s",   \
+           safe_str(conn->_base.address), conn->_base.port, (s));       \
+    connection_mark_for_close(TO_CONN(conn));                   \
+    return;                                                     \
+  } while (0)
+
+  if (conn->_base.state != OR_CONN_STATE_OR_HANDSHAKING_V3)
+    ERR("We're not doing a v3 handshake");
+  if (conn->link_proto < 3)
+    ERR("We're not using link protocol >= 3");
+  if (conn->handshake_state->started_here)
+    ERR("We originated this connection");
+  if (conn->handshake_state->received_authenticate)
+    ERR("We already got one!");
+  if (conn->handshake_state->authenticated) {
+    /* Should be impossible given other checks */
+    ERR("The peer is already authenticated");
+  }
+  if (! conn->handshake_state->received_cert_cell)
+    ERR("We never got a cert cell");
+  if (conn->handshake_state->auth_cert == NULL)
+    ERR("We never got an authentication certificate");
+  if (conn->handshake_state->id_cert == NULL)
+    ERR("We never got an identity certificate");
+  if (cell->payload_len < 4)
+    ERR("Cell was way too short");
+
+  auth = cell->payload;
+  {
+    uint16_t type = ntohs(get_uint16(auth));
+    uint16_t len = ntohs(get_uint16(auth+2));
+    if (4 + len > cell->payload_len)
+      ERR("Authenticator was truncated");
+
+    if (type != AUTHTYPE_RSA_SHA256_TLSSECRET)
+      ERR("Authenticator type was not recognized");
+
+    auth += 4;
+    authlen = len;
+  }
+
+  if (authlen < V3_AUTH_BODY_LEN + 1)
+    ERR("Authenticator was too short");
+
+  if (connection_or_compute_authenticate_cell_body(
+                        conn, expected, sizeof(expected), NULL, 1) < 0)
+    ERR("Couldn't compute expected AUTHENTICATE cell body");
+
+  if (tor_memneq(expected, auth, sizeof(expected)))
+    ERR("Some field in the AUTHENTICATE cell body was not as expected");
+
+  {
+    crypto_pk_env_t *pk = tor_tls_cert_get_key(
+                                   conn->handshake_state->auth_cert);
+    char d[DIGEST256_LEN];
+    char *signed_data;
+    size_t keysize;
+    int signed_len;
+
+    crypto_digest256(d, (char*)auth, V3_AUTH_BODY_LEN, DIGEST_SHA256);
+
+    keysize = crypto_pk_keysize(pk);
+    signed_data = tor_malloc(keysize);
+    signed_len = crypto_pk_public_checksig(pk, signed_data, keysize,
+                                           (char*)auth + V3_AUTH_BODY_LEN,
+                                           authlen - V3_AUTH_BODY_LEN);
+    if (signed_len < 0) {
+      tor_free(signed_data);
+      ERR("Signature wasn't valid");
+    }
+    if (signed_len < DIGEST256_LEN) {
+      tor_free(signed_data);
+      ERR("Not enough data was signed");
+    }
+    /* Note that we deliberately allow *more* than DIGEST256_LEN bytes here,
+     * in case they're later used to hold a SHA3 digest or something. */
+    if (tor_memneq(signed_data, d, DIGEST256_LEN)) {
+      tor_free(signed_data);
+      ERR("Signature did not match data to be signed.");
+    }
+    tor_free(signed_data);
+  }
+
+  /* Okay, we are authenticated. */
+  conn->handshake_state->received_authenticate = 1;
+  conn->handshake_state->authenticated = 1;
+  conn->handshake_state->digest_received_data = 0;
+  {
+    crypto_pk_env_t *identity_rcvd =
+      tor_tls_cert_get_key(conn->handshake_state->id_cert);
+    const digests_t *id_digests =
+      tor_cert_get_id_digests(conn->handshake_state->id_cert);
+
+    /* This must exist; we checked key type when reading the cert. */
+    tor_assert(id_digests);
+
+    memcpy(conn->handshake_state->authenticated_peer_id,
+           id_digests->d[DIGEST_SHA1], DIGEST_LEN);
+
+    connection_or_set_circid_type(conn, identity_rcvd);
+    crypto_free_pk_env(identity_rcvd);
+
+    connection_or_init_conn_from_address(conn,
+                  &conn->_base.addr,
+                  conn->_base.port,
+                  (const char*)conn->handshake_state->authenticated_peer_id,
+                  0);
+
+    log_info(LD_OR, "Got an AUTHENTICATE cell from %s:%d: Looks good.",
+             safe_str(conn->_base.address), conn->_base.port);
+  }
+
+#undef ERR
+}
+
diff --git a/src/or/connection.c b/src/or/connection.c
index 45a12715a3..2bd2d07e94 100644
--- a/src/or/connection.c
+++ b/src/or/connection.c
@@ -140,10 +140,13 @@ conn_state_to_string(int type, int state)
         case OR_CONN_STATE_PROXY_HANDSHAKING: return "handshaking (proxy)";
         case OR_CONN_STATE_TLS_HANDSHAKING: return "handshaking (TLS)";
         case OR_CONN_STATE_TLS_CLIENT_RENEGOTIATING:
-          return "renegotiating (TLS)";
+          return "renegotiating (TLS, v2 handshake)";
         case OR_CONN_STATE_TLS_SERVER_RENEGOTIATING:
-          return "waiting for renegotiation (TLS)";
-        case OR_CONN_STATE_OR_HANDSHAKING: return "handshaking (Tor)";
+          return "waiting for renegotiation or V3 handshake";
+        case OR_CONN_STATE_OR_HANDSHAKING_V2:
+          return "handshaking (Tor, v2 handshake)";
+        case OR_CONN_STATE_OR_HANDSHAKING_V3:
+          return "handshaking (Tor, v3 handshake)";
         case OR_CONN_STATE_OPEN: return "open";
       }
       break;
diff --git a/src/or/connection_or.c b/src/or/connection_or.c
index 29f0f8de72..bcae075c56 100644
--- a/src/or/connection_or.c
+++ b/src/or/connection_or.c
@@ -35,10 +35,8 @@
 #endif
 
 static int connection_tls_finish_handshake(or_connection_t *conn);
+static int connection_or_launch_v3_or_handshake(or_connection_t *conn);
 static int connection_or_process_cells_from_inbuf(or_connection_t *conn);
-static int connection_or_send_versions(or_connection_t *conn);
-static int connection_init_or_handshake_state(or_connection_t *conn,
-                                              int started_here);
 static int connection_or_check_valid_tls_handshake(or_connection_t *conn,
                                                    int started_here,
                                                    char *digest_rcvd_out);
@@ -378,8 +376,8 @@ connection_or_process_inbuf(or_connection_t *conn)
       }
 
       return ret;
-#ifdef USE_BUFFEREVENTS
     case OR_CONN_STATE_TLS_SERVER_RENEGOTIATING:
+#ifdef USE_BUFFEREVENTS
       if (tor_tls_server_got_renegotiate(conn->tls))
         connection_or_tls_renegotiated_cb(conn->tls, conn);
       if (conn->_base.marked_for_close)
@@ -387,7 +385,8 @@ connection_or_process_inbuf(or_connection_t *conn)
       /* fall through. */
 #endif
     case OR_CONN_STATE_OPEN:
-    case OR_CONN_STATE_OR_HANDSHAKING:
+    case OR_CONN_STATE_OR_HANDSHAKING_V2:
+    case OR_CONN_STATE_OR_HANDSHAKING_V3:
       return connection_or_process_cells_from_inbuf(conn);
     default:
       return 0; /* don't do anything */
@@ -439,7 +438,8 @@ connection_or_finished_flushing(or_connection_t *conn)
   switch (conn->_base.state) {
     case OR_CONN_STATE_PROXY_HANDSHAKING:
     case OR_CONN_STATE_OPEN:
-    case OR_CONN_STATE_OR_HANDSHAKING:
+    case OR_CONN_STATE_OR_HANDSHAKING_V2:
+    case OR_CONN_STATE_OR_HANDSHAKING_V3:
       break;
     default:
       log_err(LD_BUG,"Called in unexpected state %d.", conn->_base.state);
@@ -627,7 +627,7 @@ connection_or_update_token_buckets(smartlist_t *conns,
 /** If we don't necessarily know the router we're connecting to, but we
  * have an addr/port/id_digest, then fill in as much as we can. Start
  * by checking to see if this describes a router we know. */
-static void
+void
 connection_or_init_conn_from_address(or_connection_t *conn,
                                      const tor_addr_t *addr, uint16_t port,
                                      const char *id_digest,
@@ -1180,16 +1180,22 @@ connection_tls_continue_handshake(or_connection_t *conn)
       if (! tor_tls_used_v1_handshake(conn->tls)) {
         if (!tor_tls_is_server(conn->tls)) {
           if (conn->_base.state == OR_CONN_STATE_TLS_HANDSHAKING) {
-            log_debug(LD_OR, "Done with initial SSL handshake (client-side). "
-                             "Requesting renegotiation.");
-            conn->_base.state = OR_CONN_STATE_TLS_CLIENT_RENEGOTIATING;
-            goto again;
+            if (tor_tls_received_v3_certificate(conn->tls)) {
+              log_info(LD_OR, "Client got a v3 cert!  Moving on to v3 "
+                         "handshake.");
+              return connection_or_launch_v3_or_handshake(conn);
+            } else {
+              log_debug(LD_OR, "Done with initial SSL handshake (client-side). "
+                        "Requesting renegotiation.");
+              conn->_base.state = OR_CONN_STATE_TLS_CLIENT_RENEGOTIATING;
+              goto again;
+            }
           }
           // log_notice(LD_OR,"Done. state was %d.", conn->_base.state);
         } else {
-          /* improved handshake, but not a client. */
+          /* v2/v3 handshake, but not a client. */
           log_debug(LD_OR, "Done with initial SSL handshake (server-side). "
-                           "Expecting renegotiation.");
+                           "Expecting renegotiation or VERSIONS cell");
           tor_tls_set_renegotiate_callback(conn->tls,
                                            connection_or_tls_renegotiated_cb,
                                            conn);
@@ -1234,17 +1240,24 @@ connection_or_handle_event_cb(struct bufferevent *bufev, short event,
     if (! tor_tls_used_v1_handshake(conn->tls)) {
       if (!tor_tls_is_server(conn->tls)) {
         if (conn->_base.state == OR_CONN_STATE_TLS_HANDSHAKING) {
-          conn->_base.state = OR_CONN_STATE_TLS_CLIENT_RENEGOTIATING;
-          tor_tls_unblock_renegotiation(conn->tls);
-          if (bufferevent_ssl_renegotiate(conn->_base.bufev)<0) {
-            log_warn(LD_OR, "Start_renegotiating went badly.");
-            connection_mark_for_close(TO_CONN(conn));
+          if (tor_tls_received_v3_certificate(conn->tls)) {
+            log_info(LD_OR, "Client got a v3 cert!");
+            if (connection_or_launch_v3_or_handshake(conn) < 0)
+              connection_mark_for_close(TO_CONN(conn));
+            return;
+          } else {
+            conn->_base.state = OR_CONN_STATE_TLS_CLIENT_RENEGOTIATING;
+            tor_tls_unblock_renegotiation(conn->tls);
+            if (bufferevent_ssl_renegotiate(conn->_base.bufev)<0) {
+              log_warn(LD_OR, "Start_renegotiating went badly.");
+              connection_mark_for_close(TO_CONN(conn));
+            }
+            tor_tls_unblock_renegotiation(conn->tls);
+            return; /* ???? */
           }
-          tor_tls_unblock_renegotiation(conn->tls);
-          return; /* ???? */
         }
       } else if (tor_tls_get_num_server_handshakes(conn->tls) == 1) {
-        /* improved handshake, as a server. Only got one handshake, so
+        /* v2 or v3 handshake, as a server. Only got one handshake, so
          * wait for the next one. */
         tor_tls_set_renegotiate_callback(conn->tls,
                                          connection_or_tls_renegotiated_cb,
@@ -1256,7 +1269,7 @@ connection_or_handle_event_cb(struct bufferevent *bufev, short event,
         const int handshakes = tor_tls_get_num_server_handshakes(conn->tls);
         tor_assert(handshakes >= 2);
         if (handshakes == 2) {
-          /* improved handshake, as a server.  Two handshakes happened already,
+          /* v2 handshake, as a server.  Two handshakes happened already,
            * so we treat renegotiation as done.
            */
           connection_or_tls_renegotiated_cb(conn->tls, conn);
@@ -1300,6 +1313,29 @@ connection_or_nonopen_was_started_here(or_connection_t *conn)
   return !tor_tls_is_server(conn->tls);
 }
 
+/** Set the circid_type field of <b>conn</b> (which determines which part of
+ * the circuit ID space we're willing to use) based on comparing our ID to
+ * <b>identity_rcvd</b> */
+void
+connection_or_set_circid_type(or_connection_t *conn,
+                              crypto_pk_env_t *identity_rcvd)
+{
+  const int started_here = connection_or_nonopen_was_started_here(conn);
+  crypto_pk_env_t *our_identity =
+    started_here ? get_tlsclient_identity_key() :
+                   get_server_identity_key();
+
+  if (identity_rcvd) {
+    if (crypto_pk_cmp_keys(our_identity, identity_rcvd)<0) {
+      conn->circ_id_type = CIRC_ID_TYPE_LOWER;
+    } else {
+      conn->circ_id_type = CIRC_ID_TYPE_HIGHER;
+    }
+  } else {
+    conn->circ_id_type = CIRC_ID_TYPE_NEITHER;
+  }
+}
+
 /** <b>Conn</b> just completed its handshake. Return 0 if all is well, and
  * return -1 if he is lying, broken, or otherwise something is wrong.
  *
@@ -1337,10 +1373,7 @@ connection_or_check_valid_tls_handshake(or_connection_t *conn,
     started_here ? conn->_base.address :
                    safe_str_client(conn->_base.address);
   const char *conn_type = started_here ? "outgoing" : "incoming";
-  crypto_pk_env_t *our_identity =
-    started_here ? get_tlsclient_identity_key() :
-                   get_server_identity_key();
-  int has_cert = 0, has_identity=0;
+  int has_cert = 0;
 
   check_no_tls_errors();
   has_cert = tor_tls_peer_has_cert(conn->tls);
@@ -1375,21 +1408,46 @@ connection_or_check_valid_tls_handshake(or_connection_t *conn,
   }
 
   if (identity_rcvd) {
-    has_identity = 1;
     crypto_pk_get_digest(identity_rcvd, digest_rcvd_out);
-    if (crypto_pk_cmp_keys(our_identity, identity_rcvd)<0) {
-      conn->circ_id_type = CIRC_ID_TYPE_LOWER;
-    } else {
-      conn->circ_id_type = CIRC_ID_TYPE_HIGHER;
-    }
-    crypto_free_pk_env(identity_rcvd);
   } else {
     memset(digest_rcvd_out, 0, DIGEST_LEN);
-    conn->circ_id_type = CIRC_ID_TYPE_NEITHER;
   }
 
-  if (started_here && tor_digest_is_zero(conn->identity_digest)) {
-    connection_or_set_identity_digest(conn, digest_rcvd_out);
+  connection_or_set_circid_type(conn, identity_rcvd);
+  crypto_free_pk_env(identity_rcvd);
+
+  if (started_here)
+    return connection_or_client_learned_peer_id(conn,
+                                     (const uint8_t*)digest_rcvd_out);
+
+  return 0;
+}
+
+/** Called when we (as a connection initiator) have definitively,
+ * authenticatedly, learned that ID of the Tor instance on the other
+ * side of <b>conn</b> is <b>peer_id</b>.  For v1 and v2 handshakes,
+ * this is right after we get a certificate chain in a TLS handshake
+ * or renegotiation.  For v3 handshakes, this is right after we get a
+ * certificate chain in a CERT cell.
+ *
+ * If we want any particular ID before, record the one we got.
+ *
+ * If we wanted an ID, but we didn't get it, log a warning and return -1.
+ *
+ * If we're testing reachability, remember what we learned.
+ *
+ * Return 0 on success, -1 on failure.
+ */
+int
+connection_or_client_learned_peer_id(or_connection_t *conn,
+                                     const uint8_t *peer_id)
+{
+  int as_expected = 1;
+  const or_options_t *options = get_options();
+  int severity = server_mode(options) ? LOG_PROTOCOL_WARN : LOG_WARN;
+
+  if (tor_digest_is_zero(conn->identity_digest)) {
+    connection_or_set_identity_digest(conn, (const char*)peer_id);
     tor_free(conn->nickname);
     conn->nickname = tor_malloc(HEX_DIGEST_LEN+2);
     conn->nickname[0] = '$';
@@ -1401,43 +1459,39 @@ connection_or_check_valid_tls_handshake(or_connection_t *conn,
     /* if it's a bridge and we didn't know its identity fingerprint, now
      * we do -- remember it for future attempts. */
     learned_router_identity(&conn->_base.addr, conn->_base.port,
-                            digest_rcvd_out);
+                            (const char*)peer_id);
   }
 
-  if (started_here) {
-    int as_advertised = 1;
-    tor_assert(has_cert);
-    tor_assert(has_identity);
-    if (tor_memneq(digest_rcvd_out, conn->identity_digest, DIGEST_LEN)) {
-      /* I was aiming for a particular digest. I didn't get it! */
-      char seen[HEX_DIGEST_LEN+1];
-      char expected[HEX_DIGEST_LEN+1];
-      base16_encode(seen, sizeof(seen), digest_rcvd_out, DIGEST_LEN);
-      base16_encode(expected, sizeof(expected), conn->identity_digest,
-                    DIGEST_LEN);
-      log_fn(severity, LD_HANDSHAKE,
-             "Tried connecting to router at %s:%d, but identity key was not "
-             "as expected: wanted %s but got %s.",
-             conn->_base.address, conn->_base.port, expected, seen);
-      entry_guard_register_connect_status(conn->identity_digest, 0, 1,
-                                          time(NULL));
-      control_event_or_conn_status(conn, OR_CONN_EVENT_FAILED,
-              END_OR_CONN_REASON_OR_IDENTITY);
-      if (!authdir_mode_tests_reachability(options))
-        control_event_bootstrap_problem("foo", END_OR_CONN_REASON_OR_IDENTITY);
-      as_advertised = 0;
-    }
-    if (authdir_mode_tests_reachability(options)) {
-      dirserv_orconn_tls_done(conn->_base.address, conn->_base.port,
-                              digest_rcvd_out, as_advertised);
-    }
-    if (!as_advertised)
-      return -1;
+  if (tor_memneq(peer_id, conn->identity_digest, DIGEST_LEN)) {
+    /* I was aiming for a particular digest. I didn't get it! */
+    char seen[HEX_DIGEST_LEN+1];
+    char expected[HEX_DIGEST_LEN+1];
+    base16_encode(seen, sizeof(seen), (const char*)peer_id, DIGEST_LEN);
+    base16_encode(expected, sizeof(expected), conn->identity_digest,
+                  DIGEST_LEN);
+    log_fn(severity, LD_HANDSHAKE,
+           "Tried connecting to router at %s:%d, but identity key was not "
+           "as expected: wanted %s but got %s.",
+           conn->_base.address, conn->_base.port, expected, seen);
+    entry_guard_register_connect_status(conn->identity_digest, 0, 1,
+                                        time(NULL));
+    control_event_or_conn_status(conn, OR_CONN_EVENT_FAILED,
+                                 END_OR_CONN_REASON_OR_IDENTITY);
+    if (!authdir_mode_tests_reachability(options))
+      control_event_bootstrap_problem("foo", END_OR_CONN_REASON_OR_IDENTITY);
+    as_expected = 0;
   }
+  if (authdir_mode_tests_reachability(options)) {
+    dirserv_orconn_tls_done(conn->_base.address, conn->_base.port,
+                            (const char*)peer_id, as_expected);
+  }
+  if (!as_expected)
+    return -1;
+
   return 0;
 }
 
-/** The tls handshake is finished.
+/** The v1/v2 TLS handshake is finished.
  *
  * Make sure we are happy with the person we just handshaked with.
  *
@@ -1447,6 +1501,8 @@ connection_or_check_valid_tls_handshake(or_connection_t *conn,
  * If all is successful, call circuit_n_conn_done() to handle events
  * that have been pending on the <tls handshake completion. Also set the
  * directory to be dirty (only matters if I'm an authdirserver).
+ *
+ * If this is a v2 TLS handshake, send a versions cell.
  */
 static int
 connection_tls_finish_handshake(or_connection_t *conn)
@@ -1476,25 +1532,49 @@ connection_tls_finish_handshake(or_connection_t *conn)
     tor_tls_block_renegotiation(conn->tls);
     return connection_or_set_state_open(conn);
   } else {
-    conn->_base.state = OR_CONN_STATE_OR_HANDSHAKING;
+    conn->_base.state = OR_CONN_STATE_OR_HANDSHAKING_V2;
     if (connection_init_or_handshake_state(conn, started_here) < 0)
       return -1;
     if (!started_here) {
       connection_or_init_conn_from_address(conn, &conn->_base.addr,
                                            conn->_base.port, digest_rcvd, 0);
     }
-    return connection_or_send_versions(conn);
+    return connection_or_send_versions(conn, 0);
   }
 }
 
+/**
+ * Called as client when initial TLS handshake is done, and we notice
+ * that we got a v3-handshake signalling certificate from the server.
+ * Set up structures, do bookkeeping, and send the versions cell.
+ * Return 0 on success and -1 on failure.
+ */
+static int
+connection_or_launch_v3_or_handshake(or_connection_t *conn)
+{
+  tor_assert(connection_or_nonopen_was_started_here(conn));
+  tor_assert(tor_tls_received_v3_certificate(conn->tls));
+
+  circuit_build_times_network_is_live(&circ_times);
+
+  conn->_base.state = OR_CONN_STATE_OR_HANDSHAKING_V3;
+  if (connection_init_or_handshake_state(conn, 1) < 0)
+    return -1;
+
+  return connection_or_send_versions(conn, 1);
+}
+
+
 /** Allocate a new connection handshake state for the connection
  * <b>conn</b>.  Return 0 on success, -1 on failure. */
-static int
+int
 connection_init_or_handshake_state(or_connection_t *conn, int started_here)
 {
   or_handshake_state_t *s;
   s = conn->handshake_state = tor_malloc_zero(sizeof(or_handshake_state_t));
   s->started_here = started_here ? 1 : 0;
+  s->digest_sent_data = 1;
+  s->digest_received_data = 1;
   return 0;
 }
 
@@ -1504,10 +1584,89 @@ or_handshake_state_free(or_handshake_state_t *state)
 {
   if (!state)
     return;
+  crypto_free_digest_env(state->digest_sent);
+  crypto_free_digest_env(state->digest_received);
+  tor_cert_free(state->auth_cert);
+  tor_cert_free(state->id_cert);
   memset(state, 0xBE, sizeof(or_handshake_state_t));
   tor_free(state);
 }
 
+/**
+ * Remember that <b>cell</b> has been transmitted (if <b>incoming</b> is
+ * false) or received (if <b>incoming is true) during a V3 handshake using
+ * <b>state</b>.
+ *
+ * (We don't record the cell, but we keep a digest of everything sent or
+ * received during the v3 handshake, and the client signs it in an
+ * authenticate cell.)
+ */
+void
+or_handshake_state_record_cell(or_handshake_state_t *state,
+                               const cell_t *cell,
+                               int incoming)
+{
+  crypto_digest_env_t *d, **dptr;
+  packed_cell_t packed;
+  if (incoming) {
+    if (!state->digest_received_data)
+      return;
+  } else {
+    if (!state->digest_sent_data)
+      return;
+  }
+  if (!incoming) {
+    log_warn(LD_BUG, "We shouldn't be sending any non-variable-length cells "
+             "while making a handshake digest.  But we think we are sending "
+             "one with type %d.", (int)cell->command);
+  }
+  dptr = incoming ? &state->digest_received : &state->digest_sent;
+  if (! *dptr)
+    *dptr = crypto_new_digest256_env(DIGEST_SHA256);
+
+  d = *dptr;
+  /* Re-packing like this is a little inefficient, but we don't have to do
+     this very often at all. */
+  cell_pack(&packed, cell);
+  crypto_digest_add_bytes(d, packed.body, sizeof(packed.body));
+  memset(&packed, 0, sizeof(packed));
+}
+
+/** Remember that a variable-length <b>cell</b> has been transmitted (if
+ * <b>incoming</b> is false) or received (if <b>incoming is true) during a V3
+ * handshake using <b>state</b>.
+ *
+ * (We don't record the cell, but we keep a digest of everything sent or
+ * received during the v3 handshake, and the client signs it in an
+ * authenticate cell.)
+ */
+void
+or_handshake_state_record_var_cell(or_handshake_state_t *state,
+                                   const var_cell_t *cell,
+                                   int incoming)
+{
+  crypto_digest_env_t *d, **dptr;
+  char buf[VAR_CELL_HEADER_SIZE];
+  if (incoming) {
+    if (!state->digest_received_data)
+      return;
+  } else {
+    if (!state->digest_sent_data)
+      return;
+  }
+  dptr = incoming ? &state->digest_received : &state->digest_sent;
+  if (! *dptr)
+    *dptr = crypto_new_digest256_env(DIGEST_SHA256);
+
+  d = *dptr;
+
+  var_cell_pack_header(cell, buf);
+  crypto_digest_add_bytes(d, buf, sizeof(buf));
+  crypto_digest_add_bytes(d, (const char *)cell->payload, cell->payload_len);
+
+  memset(buf, 0, sizeof(buf));
+}
+
 /** Set <b>conn</b>'s state to OR_CONN_STATE_OPEN, and tell other subsystems
  * as appropriate.  Called when we are done with all TLS and OR handshaking.
  */
@@ -1575,6 +1734,9 @@ connection_or_write_cell_to_buf(const cell_t *cell, or_connection_t *conn)
 
   connection_write_to_buf(networkcell.body, CELL_NETWORK_SIZE, TO_CONN(conn));
 
+  if (conn->_base.state == OR_CONN_STATE_OR_HANDSHAKING_V3)
+    or_handshake_state_record_cell(conn->handshake_state, cell, 0);
+
   if (cell->command != CELL_PADDING)
     conn->timestamp_last_added_nonpadding = approx_time();
 }
@@ -1594,6 +1756,8 @@ connection_or_write_var_cell_to_buf(const var_cell_t *cell,
   connection_write_to_buf(hdr, sizeof(hdr), TO_CONN(conn));
   connection_write_to_buf((char*)cell->payload,
                           cell->payload_len, TO_CONN(conn));
+  if (conn->_base.state == OR_CONN_STATE_OR_HANDSHAKING_V3)
+    or_handshake_state_record_var_cell(conn->handshake_state, cell, 0);
   if (cell->command != CELL_PADDING)
     conn->timestamp_last_added_nonpadding = approx_time();
 }
@@ -1678,7 +1842,7 @@ connection_or_send_destroy(circid_t circ_id, or_connection_t *conn, int reason)
 }
 
 /** Array of recognized link protocol versions. */
-static const uint16_t or_protocol_versions[] = { 1, 2 };
+static const uint16_t or_protocol_versions[] = { 1, 2, 3 };
 /** Number of versions in <b>or_protocol_versions</b>. */
 static const int n_or_protocol_versions =
   (int)( sizeof(or_protocol_versions)/sizeof(uint16_t) );
@@ -1697,20 +1861,33 @@ is_or_protocol_version_known(uint16_t v)
 }
 
 /** Send a VERSIONS cell on <b>conn</b>, telling the other host about the
- * link protocol versions that this Tor can support. */
-static int
-connection_or_send_versions(or_connection_t *conn)
+ * link protocol versions that this Tor can support.
+ *
+ * If <b>v3_plus</b>, this is part of a V3 protocol handshake, so only
+ * allow protocol version v3 or later.  If not <b>v3_plus</b>, this is
+ * not part of a v3 protocol handshake, so don't allow protocol v3 or
+ * later.
+ **/
+int
+connection_or_send_versions(or_connection_t *conn, int v3_plus)
 {
   var_cell_t *cell;
   int i;
+  int n_versions = 0;
+  const int min_version = v3_plus ? 3 : 0;
+  const int max_version = v3_plus ? UINT16_MAX : 2;
   tor_assert(conn->handshake_state &&
              !conn->handshake_state->sent_versions_at);
   cell = var_cell_new(n_or_protocol_versions * 2);
   cell->command = CELL_VERSIONS;
   for (i = 0; i < n_or_protocol_versions; ++i) {
     uint16_t v = or_protocol_versions[i];
-    set_uint16(cell->payload+(2*i), htons(v));
+    if (v < min_version || v > max_version)
+      continue;
+    set_uint16(cell->payload+(2*n_versions), htons(v));
+    ++n_versions;
   }
+  cell->payload_len = n_versions * 2;
 
   connection_or_write_var_cell_to_buf(cell, conn);
   conn->handshake_state->sent_versions_at = time(NULL);
@@ -1730,6 +1907,8 @@ connection_or_send_netinfo(or_connection_t *conn)
   int len;
   uint8_t *out;
 
+  tor_assert(conn->handshake_state);
+
   memset(&cell, 0, sizeof(cell_t));
   cell.command = CELL_NETINFO;
 
@@ -1756,8 +1935,284 @@ connection_or_send_netinfo(or_connection_t *conn)
     *out = 0;
   }
 
+  conn->handshake_state->digest_sent_data = 0;
   connection_or_write_cell_to_buf(&cell, conn);
 
   return 0;
 }
 
+/** Send a CERT cell on the connection <b>conn</b>.  Return 0 on success, -1
+ * on failure. */
+int
+connection_or_send_cert_cell(or_connection_t *conn)
+{
+  const tor_cert_t *link_cert = NULL, *id_cert = NULL;
+  const uint8_t *link_encoded = NULL, *id_encoded = NULL;
+  size_t link_len, id_len;
+  var_cell_t *cell;
+  size_t cell_len;
+  ssize_t pos;
+  int server_mode;
+
+  tor_assert(conn->_base.state == OR_CONN_STATE_OR_HANDSHAKING_V3);
+
+  if (! conn->handshake_state)
+    return -1;
+  server_mode = ! conn->handshake_state->started_here;
+  if (tor_tls_get_my_certs(server_mode, &link_cert, &id_cert) < 0)
+    return -1;
+  tor_cert_get_der(link_cert, &link_encoded, &link_len);
+  tor_cert_get_der(id_cert, &id_encoded, &id_len);
+
+  cell_len = 1 /* 1 octet: num certs in cell */ +
+             2 * ( 1 + 2 ) /* For each cert: 1 octet for type, 2 for length */ +
+             link_len + id_len;
+  cell = var_cell_new(cell_len);
+  cell->command = CELL_CERT;
+  cell->payload[0] = 2;
+  pos = 1;
+
+  if (server_mode)
+    cell->payload[pos] = OR_CERT_TYPE_TLS_LINK; /* Link cert  */
+  else
+    cell->payload[pos] = OR_CERT_TYPE_AUTH_1024; /* client authentication */
+  set_uint16(&cell->payload[pos+1], htons(link_len));
+  memcpy(&cell->payload[pos+3], link_encoded, link_len);
+  pos += 3 + link_len;
+
+  cell->payload[pos] = OR_CERT_TYPE_ID_1024; /* ID cert */
+  set_uint16(&cell->payload[pos+1], htons(id_len));
+  memcpy(&cell->payload[pos+3], id_encoded, id_len);
+  pos += 3 + id_len;
+
+  tor_assert(pos == (int)cell_len); /* Otherwise we just smashed the heap */
+
+  connection_or_write_var_cell_to_buf(cell, conn);
+  var_cell_free(cell);
+
+  return 0;
+}
+
+/** Send an AUTH_CHALLENGE cell on the connection <b>conn</b>. Return 0
+ * on success, -1 on failure. */
+int
+connection_or_send_auth_challenge_cell(or_connection_t *conn)
+{
+  var_cell_t *cell;
+  uint8_t *cp;
+  uint8_t challenge[OR_AUTH_CHALLENGE_LEN];
+  tor_assert(conn->_base.state == OR_CONN_STATE_OR_HANDSHAKING_V3);
+
+  if (! conn->handshake_state)
+    return -1;
+
+  if (crypto_rand((char*)challenge, OR_AUTH_CHALLENGE_LEN) < 0)
+    return -1;
+  cell = var_cell_new(OR_AUTH_CHALLENGE_LEN + 4);
+  cell->command = CELL_AUTH_CHALLENGE;
+  memcpy(cell->payload, challenge, OR_AUTH_CHALLENGE_LEN);
+  cp = cell->payload + OR_AUTH_CHALLENGE_LEN;
+  set_uint16(cp, htons(1)); /* We recognize one authentication type. */
+  set_uint16(cp+2, htons(AUTHTYPE_RSA_SHA256_TLSSECRET));
+
+  connection_or_write_var_cell_to_buf(cell, conn);
+  var_cell_free(cell);
+  memset(challenge, 0, sizeof(challenge));
+
+  return 0;
+}
+
+/** Compute the main body of an AUTHENTICATE cell that a client can use
+ * to authenticate itself on a v3 handshake for <b>conn</b>.  Write it to the
+ * <b>outlen</b>-byte buffer at <b>out</b>.
+ *
+ * If <b>server</b> is true, only calculate the first
+ * V3_AUTH_FIXED_PART_LEN bytes -- the part of the authenticator that's
+ * determined by the rest of the handshake, and which match the provided value
+ * exactly.
+ *
+ * If <b>server</b> is false and <b>signing_key</b> is NULL, calculate the
+ * first V3_AUTH_BODY_LEN bytes of the authenticator (that is, everything
+ * that should be signed), but don't actually sign it.
+ *
+ * If <b>server</b> is false and <b>signing_key</b> is provided, calculate the
+ * entire authenticator, signed with <b>signing_key</b>.
+ * DOCDOC return value
+ */
+int
+connection_or_compute_authenticate_cell_body(or_connection_t *conn,
+                                             uint8_t *out, size_t outlen,
+                                             crypto_pk_env_t *signing_key,
+                                             int server)
+{
+  uint8_t *ptr;
+
+  /* assert state is reasonable XXXX */
+
+  if (outlen < V3_AUTH_FIXED_PART_LEN ||
+      (!server && outlen < V3_AUTH_BODY_LEN))
+    return -1;
+
+  ptr = out;
+
+  /* Type: 8 bytes. */
+  memcpy(ptr, "AUTH0001", 8);
+  ptr += 8;
+
+  {
+    const tor_cert_t *id_cert=NULL, *link_cert=NULL;
+    const digests_t *my_digests, *their_digests;
+    const uint8_t *my_id, *their_id, *client_id, *server_id;
+    if (tor_tls_get_my_certs(0, &link_cert, &id_cert))
+      return -1;
+    my_digests = tor_cert_get_id_digests(id_cert);
+    their_digests = tor_cert_get_id_digests(conn->handshake_state->id_cert);
+    tor_assert(my_digests);
+    tor_assert(their_digests);
+    my_id = (uint8_t*)my_digests->d[DIGEST_SHA256];
+    their_id = (uint8_t*)their_digests->d[DIGEST_SHA256];
+
+    client_id = server ? their_id : my_id;
+    server_id = server ? my_id : their_id;
+
+    /* Client ID digest: 32 octets. */
+    memcpy(ptr, client_id, 32);
+    ptr += 32;
+
+    /* Server ID digest: 32 octets. */
+    memcpy(ptr, server_id, 32);
+    ptr += 32;
+  }
+
+  {
+    crypto_digest_env_t *server_d, *client_d;
+    if (server) {
+      server_d = conn->handshake_state->digest_sent;
+      client_d = conn->handshake_state->digest_received;
+    } else {
+      client_d = conn->handshake_state->digest_sent;
+      server_d = conn->handshake_state->digest_received;
+    }
+
+    /* Server log digest : 32 octets */
+    crypto_digest_get_digest(server_d, (char*)ptr, 32);
+    ptr += 32;
+
+    /* Client log digest : 32 octets */
+    crypto_digest_get_digest(client_d, (char*)ptr, 32);
+    ptr += 32;
+  }
+
+  {
+    /* Digest of cert used on TLS link : 32 octets. */
+    const tor_cert_t *cert = NULL;
+    tor_cert_t *freecert = NULL;
+    if (server) {
+      tor_tls_get_my_certs(1, &cert, NULL);
+    } else {
+      freecert = tor_tls_get_peer_cert(conn->tls);
+      cert = freecert;
+    }
+    if (!cert)
+      return -1;
+    memcpy(ptr, tor_cert_get_cert_digests(cert)->d[DIGEST_SHA256], 32);
+
+    if (freecert)
+      tor_cert_free(freecert);
+    ptr += 32;
+  }
+
+  /* HMAC of clientrandom and serverrandom using master key : 32 octets */
+  tor_tls_get_tlssecrets(conn->tls, ptr);
+  ptr += 32;
+
+  tor_assert(ptr - out == V3_AUTH_FIXED_PART_LEN);
+
+  if (server)
+    return V3_AUTH_FIXED_PART_LEN; // ptr-out
+
+  /* Time: 8 octets. */
+  {
+    uint64_t now = time(NULL);
+    if ((time_t)now < 0)
+      return -1;
+    set_uint32(ptr, htonl((uint32_t)(now>>32)));
+    set_uint32(ptr+4, htonl((uint32_t)now));
+    ptr += 8;
+  }
+
+  /* Nonce: 16 octets. */
+  crypto_rand((char*)ptr, 16);
+  ptr += 16;
+
+  tor_assert(ptr - out == V3_AUTH_BODY_LEN);
+
+  if (!signing_key)
+    return V3_AUTH_BODY_LEN; // ptr - out
+
+  {
+    int siglen;
+    char d[32];
+    crypto_digest256(d, (char*)out, ptr-out, DIGEST_SHA256);
+    siglen = crypto_pk_private_sign(signing_key,
+                                    (char*)ptr, outlen - (ptr-out),
+                                    d, 32);
+    if (siglen < 0)
+      return -1;
+
+    ptr += siglen;
+    tor_assert(ptr <= out+outlen);
+    return (int)(ptr - out);
+  }
+}
+
+/** Send an AUTHENTICATE cell on the connection <b>conn</b>.  Return 0 on
+ * success, -1 on failure */
+int
+connection_or_send_authenticate_cell(or_connection_t *conn, int authtype)
+{
+  var_cell_t *cell;
+  crypto_pk_env_t *pk = tor_tls_get_my_client_auth_key();
+  int authlen;
+  size_t cell_maxlen;
+  /* XXXX make sure we're actually supposed to send this! */
+
+  if (!pk) {
+    log_warn(LD_BUG, "Unable to compute authenticate cell: no client auth key");
+    return -1;
+  }
+  if (authtype != AUTHTYPE_RSA_SHA256_TLSSECRET) {
+    log_warn(LD_BUG, "Tried to send authenticate cell with unknown "
+             "authentication type %d", authtype);
+    return -1;
+  }
+
+  cell_maxlen = 4 + /* overhead */
+    V3_AUTH_BODY_LEN + /* Authentication body */
+    crypto_pk_keysize(pk) + /* Max signature length */
+    16 /* add a few extra bytes just in case. */;
+
+  cell = var_cell_new(cell_maxlen);
+  cell->command = CELL_AUTHENTICATE;
+  set_uint16(cell->payload, htons(AUTHTYPE_RSA_SHA256_TLSSECRET));
+  /* skip over length ; we don't know that yet. */
+
+  authlen = connection_or_compute_authenticate_cell_body(conn,
+                                                         cell->payload+4,
+                                                         cell_maxlen-4,
+                                                         pk,
+                                                         0 /* not server */);
+  if (authlen < 0) {
+    log_warn(LD_BUG, "Unable to compute authenticate cell!");
+    var_cell_free(cell);
+    return -1;
+  }
+  tor_assert(authlen + 4 <= cell->payload_len);
+  set_uint16(cell->payload+2, htons(authlen));
+  cell->payload_len = authlen + 4;
+
+  connection_or_write_var_cell_to_buf(cell, conn);
+  var_cell_free(cell);
+
+  return 0;
+}
diff --git a/src/or/connection_or.h b/src/or/connection_or.h
index 072edbd8cf..de3a989a60 100644
--- a/src/or/connection_or.h
+++ b/src/or/connection_or.h
@@ -41,7 +41,23 @@ void connection_or_report_broken_states(int severity, int domain);
 int connection_tls_start_handshake(or_connection_t *conn, int receiving);
 int connection_tls_continue_handshake(or_connection_t *conn);
 
+int connection_init_or_handshake_state(or_connection_t *conn, int started_here);
+void connection_or_init_conn_from_address(or_connection_t *conn,
+                                          const tor_addr_t *addr, uint16_t port,
+                                          const char *id_digest,
+                                          int started_here);
+int connection_or_client_learned_peer_id(or_connection_t *conn,
+                                         const uint8_t *peer_id);
+void connection_or_set_circid_type(or_connection_t *conn,
+                                   crypto_pk_env_t *identity_rcvd);
 void or_handshake_state_free(or_handshake_state_t *state);
+void or_handshake_state_record_cell(or_handshake_state_t *state,
+                                    const cell_t *cell,
+                                    int incoming);
+void or_handshake_state_record_var_cell(or_handshake_state_t *state,
+                                        const var_cell_t *cell,
+                                        int incoming);
+
 int connection_or_set_state_open(or_connection_t *conn);
 void connection_or_write_cell_to_buf(const cell_t *cell,
                                      or_connection_t *conn);
@@ -49,7 +65,16 @@ void connection_or_write_var_cell_to_buf(const var_cell_t *cell,
                                          or_connection_t *conn);
 int connection_or_send_destroy(circid_t circ_id, or_connection_t *conn,
                                int reason);
+int connection_or_send_versions(or_connection_t *conn, int v3_plus);
 int connection_or_send_netinfo(or_connection_t *conn);
+int connection_or_send_cert_cell(or_connection_t *conn);
+int connection_or_send_auth_challenge_cell(or_connection_t *conn);
+int connection_or_compute_authenticate_cell_body(or_connection_t *conn,
+                                                 uint8_t *out, size_t outlen,
+                                                 crypto_pk_env_t *signing_key,
+                                                 int server);
+int connection_or_send_authenticate_cell(or_connection_t *conn, int type);
+
 int is_or_protocol_version_known(uint16_t version);
 
 void cell_pack(packed_cell_t *dest, const cell_t *src);
diff --git a/src/or/or.h b/src/or/or.h
index d6eaeb6f17..6969a9cff7 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -283,22 +283,27 @@ typedef enum {
 #define OR_CONN_STATE_CONNECTING 1
 /** State for a connection to an OR: waiting for proxy handshake to complete */
 #define OR_CONN_STATE_PROXY_HANDSHAKING 2
-/** State for a connection to an OR or client: SSL is handshaking, not done
+/** State for an OR connection client: SSL is handshaking, not done
  * yet. */
 #define OR_CONN_STATE_TLS_HANDSHAKING 3
 /** State for a connection to an OR: We're doing a second SSL handshake for
- * renegotiation purposes. */
+ * renegotiation purposes. (V2 handshake only.) */
 #define OR_CONN_STATE_TLS_CLIENT_RENEGOTIATING 4
 /** State for a connection at an OR: We're waiting for the client to
- * renegotiate. */
+ * renegotiate (to indicate a v2 handshake) or send a versions cell (to
+ * indicate a v3 handshake) */
 #define OR_CONN_STATE_TLS_SERVER_RENEGOTIATING 5
-/** State for a connection to an OR: We're done with our SSL handshake, but we
- * haven't yet negotiated link protocol versions and sent a netinfo cell.
- */
-#define OR_CONN_STATE_OR_HANDSHAKING 6
-/** State for a connection to an OR: Ready to send/receive cells. */
-#define OR_CONN_STATE_OPEN 7
-#define _OR_CONN_STATE_MAX 7
+/** State for an OR connection: We're done with our SSL handshake, we've done
+ * renegotiation, but we haven't yet negotiated link protocol versions and
+ * sent a netinfo cell. */
+#define OR_CONN_STATE_OR_HANDSHAKING_V2 6
+/** State for an OR connection: We're done with our SSL handshake, but we
+ * haven't yet negotiated link protocol versions, done a V3 handshake, and
+ * sent a netinfo cell. */
+#define OR_CONN_STATE_OR_HANDSHAKING_V3 7
+/** State for an OR connection: Ready to send/receive cells. */
+#define OR_CONN_STATE_OPEN 8
+#define _OR_CONN_STATE_MAX 8
 
 #define _EXIT_CONN_STATE_MIN 1
 /** State for an exit connection: waiting for response from DNS farm. */
@@ -820,9 +825,10 @@ typedef enum {
 #define CELL_NETINFO 8
 #define CELL_RELAY_EARLY 9
 
-/** True iff the cell command <b>x</b> is one that implies a variable-length
- * cell. */
-#define CELL_COMMAND_IS_VAR_LENGTH(x) ((x) == CELL_VERSIONS)
+#define CELL_VPADDING 128
+#define CELL_CERT 129
+#define CELL_AUTH_CHALLENGE 130
+#define CELL_AUTHENTICATE 131
 
 /** How long to test reachability before complaining to the user. */
 #define TIMEOUT_UNTIL_UNREACHABILITY_COMPLAINT (20*60)
@@ -1078,7 +1084,47 @@ typedef struct listener_connection_t {
 
 } listener_connection_t;
 
-/** Stores flags and information related to the portion of a v2 Tor OR
+/** Minimum length of the random part of an AUTH_CHALLENGE cell. */
+#define OR_AUTH_CHALLENGE_LEN 32
+
+/**
+ * @name Certificate types for CERT cells.
+ *
+ * These values are defined by the protocol, and affect how an X509
+ * certificate in a CERT cell is interpreted and used.
+ *
+ * @{ */
+/** A certificate that authenticates a TLS link key.  The subject key
+ * must match the key used in the TLS handshake; it must be signed by
+ * the identity key. */
+#define OR_CERT_TYPE_TLS_LINK 1
+/** A self-signed identity certificate. The subject key must be a
+ * 1024-bit RSA key. */
+#define OR_CERT_TYPE_ID_1024 2
+/** A certificate that authenticates a key used in an AUTHENTICATE cell
+ * in the v3 handshake.  The subject key must be a 1024-bit RSA key; it
+ * must be signed by the identity key */
+#define OR_CERT_TYPE_AUTH_1024 3
+/**@}*/
+
+/** The one currently supported type of AUTHENTICATE cell.  It contains
+ * a bunch of structures signed with an RSA1024 key.  The signed
+ * structures include a HMAC using negotiated TLS secrets, and a digest
+ * of all cells sent or received before the AUTHENTICATE cell (including
+ * the random server-generated AUTH_CHALLENGE cell).
+ */
+#define AUTHTYPE_RSA_SHA256_TLSSECRET 1
+
+/** The length of the part of the AUTHENTICATE cell body that the client and
+ * server can generate independently (when using RSA_SHA256_TLSSECRET). It
+ * contains everything except the client's timestamp, the client's randomly
+ * generated nonce, and the signature. */
+#define V3_AUTH_FIXED_PART_LEN (8+(32*6))
+/** The length of the part of the AUTHENTICATE cell body that the client
+ * signs. */
+#define V3_AUTH_BODY_LEN (V3_AUTH_FIXED_PART_LEN + 8 + 16)
+
+/** Stores flags and information related to the portion of a v2/v3 Tor OR
  * connection handshake that happens after the TLS handshake is finished.
  */
 typedef struct or_handshake_state_t {
@@ -1089,6 +1135,52 @@ typedef struct or_handshake_state_t {
   unsigned int started_here : 1;
   /** True iff we have received and processed a VERSIONS cell. */
   unsigned int received_versions : 1;
+  /** True iff we have received and processed an AUTH_CHALLENGE cell */
+  unsigned int received_auth_challenge : 1;
+  /** True iff we have received and processed a CERT cell. */
+  unsigned int received_cert_cell : 1;
+  /** True iff we have received and processed an AUTHENTICATE cell */
+  unsigned int received_authenticate : 1;
+
+  /* True iff we've received valid authentication to some identity. */
+  unsigned int authenticated : 1;
+
+  /** True iff we should feed outgoing cells into digest_sent and
+   * digest_received respectively.
+   *
+   * From the server's side of the v3 handshake, we want to capture everything
+   * from the VERSIONS cell through and including the AUTH_CHALLENGE cell.
+   * From the client's, we want to capture everything from the VERSIONS cell
+   * through but *not* including the AUTHENTICATE cell.
+   *
+   * @{ */
+  unsigned int digest_sent_data : 1;
+  unsigned int digest_received_data : 1;
+  /**@}*/
+
+  /** Identity digest that we have received and authenticated for our peer
+   * on this connection. */
+  uint8_t authenticated_peer_id[DIGEST_LEN];
+
+  /** Digests of the cells that we have sent or received as part of a V3
+   * handshake.  Used for making and checking AUTHENTICATE cells.
+   *
+   * @{
+   */
+  crypto_digest_env_t *digest_sent;
+  crypto_digest_env_t *digest_received;
+  /** @} */
+
+  /** Certificates that a connection initiator sent us in a CERT cell; we're
+   * holding on to them until we get an AUTHENTICATE cell.
+   *
+   * @{
+   */
+  /** The cert for the key that's supposed to sign the AUTHENTICATE cell */
+  tor_cert_t *auth_cert;
+  /** A self-signed identity certificate */
+  tor_cert_t *id_cert;
+  /**@}*/
 } or_handshake_state_t;
 
 /** Subtype of connection_t for an "OR connection" -- that is, one that speaks