Merge branch 'ntor-resquashed'

Conflicts:
	src/or/cpuworker.c
	src/or/or.h
	src/test/bench.c

34 files changed, 2467 insertions, 546 deletions

diff --git a/src/or/channeltls.c b/src/or/channeltls.c
index ede245894e..f6069e0037 100644
--- a/src/or/channeltls.c
+++ b/src/or/channeltls.c
@@ -914,6 +914,8 @@ channel_tls_handle_cell(cell_t *cell, or_connection_t *conn)
     case CELL_RELAY:
     case CELL_RELAY_EARLY:
     case CELL_DESTROY:
+    case CELL_CREATE2:
+    case CELL_CREATED2:
       /*
        * These are all transport independent and we pass them up through the
        * channel_t mechanism.  They are ultimately handled in command.c.
diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c
index 55f746177b..12d6ea357f 100644
--- a/src/or/circuitbuild.c
+++ b/src/or/circuitbuild.c
@@ -28,6 +28,8 @@
 #include "networkstatus.h"
 #include "nodelist.h"
 #include "onion.h"
+#include "onion_tap.h"
+#include "onion_fast.h"
 #include "policies.h"
 #include "transports.h"
 #include "relay.h"
@@ -53,7 +55,8 @@ static channel_t * channel_connect_for_circuit(const tor_addr_t *addr,
                                                uint16_t port,
                                                const char *id_digest);
 static int circuit_deliver_create_cell(circuit_t *circ,
-                                       uint8_t cell_type, const char *payload);
+                                       const create_cell_t *create_cell,
+                                       int relayed);
 static int onion_pick_cpath_exit(origin_circuit_t *circ, extend_info_t *exit);
 static crypt_path_t *onion_next_hop_in_cpath(crypt_path_t *cpath);
 static int onion_extend_cpath(origin_circuit_t *circ);
@@ -473,14 +476,13 @@ circuit_n_chan_done(channel_t *chan, int status)
            *     died? */
         }
       } else {
-        /* pull the create cell out of circ->onionskin, and send it */
-        tor_assert(circ->n_chan_onionskin);
-        if (circuit_deliver_create_cell(circ,CELL_CREATE,
-                                        circ->n_chan_onionskin)<0) {
+        /* pull the create cell out of circ->n_chan_create_cell, and send it */
+        tor_assert(circ->n_chan_create_cell);
+        if (circuit_deliver_create_cell(circ, circ->n_chan_create_cell, 1)<0) {
           circuit_mark_for_close(circ, END_CIRC_REASON_RESOURCELIMIT);
           continue;
         }
-        tor_free(circ->n_chan_onionskin);
+        tor_free(circ->n_chan_create_cell);
         circuit_set_state(circ, CIRCUIT_STATE_OPEN);
       }
     }
@@ -491,22 +493,25 @@ circuit_n_chan_done(channel_t *chan, int status)
 
 /** Find a new circid that isn't currently in use on the circ->n_chan
  * for the outgoing
- * circuit <b>circ</b>, and deliver a cell of type <b>cell_type</b>
- * (either CELL_CREATE or CELL_CREATE_FAST) with payload <b>payload</b>
- * to this circuit.
- * Return -1 if we failed to find a suitable circid, else return 0.
+ * circuit <b>circ</b>, and deliver the cell <b>create_cell</b> to this
+ * circuit.  If <b>relayed</b> is true, this is a create cell somebody
+ * gave us via an EXTEND cell, so we shouldn't worry if we don't understand
+ * it. Return -1 if we failed to find a suitable circid, else return 0.
  */
 static int
-circuit_deliver_create_cell(circuit_t *circ, uint8_t cell_type,
-                            const char *payload)
+circuit_deliver_create_cell(circuit_t *circ, const create_cell_t *create_cell,
+                            int relayed)
 {
   cell_t cell;
   circid_t id;
+  int r;
 
   tor_assert(circ);
   tor_assert(circ->n_chan);
-  tor_assert(payload);
-  tor_assert(cell_type == CELL_CREATE || cell_type == CELL_CREATE_FAST);
+  tor_assert(create_cell);
+  tor_assert(create_cell->cell_type == CELL_CREATE ||
+             create_cell->cell_type == CELL_CREATE_FAST ||
+             create_cell->cell_type == CELL_CREATE2);
 
   id = get_unique_circ_id_by_chan(circ->n_chan);
   if (!id) {
@@ -517,10 +522,14 @@ circuit_deliver_create_cell(circuit_t *circ, uint8_t cell_type,
   circuit_set_n_circid_chan(circ, id, circ->n_chan);
 
   memset(&cell, 0, sizeof(cell_t));
-  cell.command = cell_type;
+  r = relayed ? create_cell_format_relayed(&cell, create_cell)
+              : create_cell_format(&cell, create_cell);
+  if (r < 0) {
+    log_warn(LD_CIRC,"Couldn't format create cell");
+    return -1;
+  }
   cell.circ_id = circ->n_circ_id;
 
-  memcpy(cell.payload, payload, ONIONSKIN_CHALLENGE_LEN);
   append_cell_to_circuit_queue(circ, circ->n_chan, &cell,
                                CELL_DIRECTION_OUT, 0);
 
@@ -610,6 +619,73 @@ circuit_timeout_want_to_count_circ(origin_circuit_t *circ)
           && circ->build_state->desired_path_len == DEFAULT_ROUTE_LEN;
 }
 
+#ifdef CURVE25519_ENABLED
+/** Return true if the ntor handshake is enabled in the configuration, or if
+ * it's been set to "auto" in the configuration and it's enabled in the
+ * consensus. */
+static int
+circuits_can_use_ntor(void)
+{
+  const or_options_t *options = get_options();
+  if (options->UseNTorHandshake != -1)
+    return options->UseNTorHandshake;
+  return networkstatus_get_param(NULL, "UseNTorHandshake", 0, 0, 1);
+}
+#endif
+
+/** Decide whether to use a TAP or ntor handshake for connecting to <b>ei</b>
+ * directly, and set *<b>cell_type_out</b> and *<b>handshake_type_out</b>
+ * accordingly. */
+static void
+circuit_pick_create_handshake(uint8_t *cell_type_out,
+                              uint16_t *handshake_type_out,
+                              const extend_info_t *ei)
+{
+#ifdef CURVE25519_ENABLED
+  if (!tor_mem_is_zero((const char*)ei->curve25519_onion_key.public_key,
+                       CURVE25519_PUBKEY_LEN) &&
+      circuits_can_use_ntor()) {
+    *cell_type_out = CELL_CREATE2;
+    *handshake_type_out = ONION_HANDSHAKE_TYPE_NTOR;
+    return;
+  }
+#else
+  (void) ei;
+#endif
+
+  *cell_type_out = CELL_CREATE;
+  *handshake_type_out = ONION_HANDSHAKE_TYPE_TAP;
+}
+
+/** Decide whether to use a TAP or ntor handshake for connecting to <b>ei</b>
+ * directly, and set *<b>handshake_type_out</b> accordingly. Decide whether,
+ * in extending through <b>node</b> to do so, we should use an EXTEND2 or an
+ * EXTEND cell to do so, and set *<b>cell_type_out</b> and
+ * *<b>create_cell_type_out</b> accordingly. */
+static void
+circuit_pick_extend_handshake(uint8_t *cell_type_out,
+                              uint8_t *create_cell_type_out,
+                              uint16_t *handshake_type_out,
+                              const node_t *node_prev,
+                              const extend_info_t *ei)
+{
+  uint8_t t;
+  circuit_pick_create_handshake(&t, handshake_type_out, ei);
+  /* XXXX024 The check for whether the node has a curve25519 key is a bad
+   * proxy for whether it can do extend2 cells; once a version that
+   * handles extend2 cells is out, remove it. */
+  if (node_prev &&
+      *handshake_type_out != ONION_HANDSHAKE_TYPE_TAP &&
+      (node_has_curve25519_onion_key(node_prev) ||
+       (node_prev->rs && node_prev->rs->version_supports_extend2_cells))) {
+    *cell_type_out = RELAY_COMMAND_EXTEND2;
+    *create_cell_type_out = CELL_CREATE2;
+  } else {
+    *cell_type_out = RELAY_COMMAND_EXTEND;
+    *create_cell_type_out = CELL_CREATE;
+  }
+}
+
 /** This is the backbone function for building circuits.
  *
  * If circ's first hop is closed, then we need to build a create
@@ -625,16 +701,16 @@ circuit_send_next_onion_skin(origin_circuit_t *circ)
 {
   crypt_path_t *hop;
   const node_t *node;
-  char payload[2+4+DIGEST_LEN+ONIONSKIN_CHALLENGE_LEN];
-  char *onionskin;
-  size_t payload_len;
 
   tor_assert(circ);
 
   if (circ->cpath->state == CPATH_STATE_CLOSED) {
+    /* This is the first hop. */
+    create_cell_t cc;
     int fast;
-    uint8_t cell_type;
+    int len;
     log_debug(LD_CIRC,"First skin; sending create cell.");
+    memset(&cc, 0, sizeof(cc));
     if (circ->build_state->onehop_tunnel)
       control_event_bootstrap(BOOTSTRAP_STATUS_ONEHOP_CREATE, 0);
     else
@@ -644,30 +720,31 @@ circuit_send_next_onion_skin(origin_circuit_t *circ)
     fast = should_use_create_fast_for_circuit(circ);
     if (!fast) {
       /* We are an OR and we know the right onion key: we should
-       * send an old slow create cell.
+       * send a create cell.
        */
-      cell_type = CELL_CREATE;
-      if (onion_skin_create(circ->cpath->extend_info->onion_key,
-                            &(circ->cpath->dh_handshake_state),
-                            payload) < 0) {
-        log_warn(LD_CIRC,"onion_skin_create (first hop) failed.");
-        return - END_CIRC_REASON_INTERNAL;
-      }
+      circuit_pick_create_handshake(&cc.cell_type, &cc.handshake_type,
+                                    circ->cpath->extend_info);
       note_request("cell: create", 1);
     } else {
       /* We are not an OR, and we're building the first hop of a circuit to a
        * new OR: we can be speedy and use CREATE_FAST to save an RSA operation
        * and a DH operation. */
-      cell_type = CELL_CREATE_FAST;
-      memset(payload, 0, sizeof(payload));
-      crypto_rand((char*) circ->cpath->fast_handshake_state,
-                  sizeof(circ->cpath->fast_handshake_state));
-      memcpy(payload, circ->cpath->fast_handshake_state,
-             sizeof(circ->cpath->fast_handshake_state));
+      cc.cell_type = CELL_CREATE_FAST;
+      cc.handshake_type = ONION_HANDSHAKE_TYPE_FAST;
       note_request("cell: create fast", 1);
     }
 
-    if (circuit_deliver_create_cell(TO_CIRCUIT(circ), cell_type, payload) < 0)
+    len = onion_skin_create(cc.handshake_type,
+                            circ->cpath->extend_info,
+                            &circ->cpath->handshake_state,
+                            cc.onionskin);
+    if (len < 0) {
+      log_warn(LD_CIRC,"onion_skin_create (first hop) failed.");
+      return - END_CIRC_REASON_INTERNAL;
+    }
+    cc.handshake_len = len;
+
+    if (circuit_deliver_create_cell(TO_CIRCUIT(circ), &cc, 0) < 0)
       return - END_CIRC_REASON_RESOURCELIMIT;
 
     circ->cpath->state = CPATH_STATE_AWAITING_KEYS;
@@ -676,10 +753,13 @@ circuit_send_next_onion_skin(origin_circuit_t *circ)
              fast ? "CREATE_FAST" : "CREATE",
              node ? node_describe(node) : "<unnamed>");
   } else {
+    extend_cell_t ec;
+    int len;
     tor_assert(circ->cpath->state == CPATH_STATE_OPEN);
     tor_assert(circ->base_.state == CIRCUIT_STATE_BUILDING);
     log_debug(LD_CIRC,"starting to send subsequent skin.");
     hop = onion_next_hop_in_cpath(circ->cpath);
+    memset(&ec, 0, sizeof(ec));
     if (!hop) {
       /* done building the circuit. whew. */
       circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_OPEN);
@@ -753,29 +833,50 @@ circuit_send_next_onion_skin(origin_circuit_t *circ)
       return - END_CIRC_REASON_INTERNAL;
     }
 
-    set_uint32(payload, tor_addr_to_ipv4n(&hop->extend_info->addr));
-    set_uint16(payload+4, htons(hop->extend_info->port));
+    {
+      const node_t *prev_node;
+      prev_node = node_get_by_id(hop->prev->extend_info->identity_digest);
+      circuit_pick_extend_handshake(&ec.cell_type,
+                                    &ec.create_cell.cell_type,
+                                    &ec.create_cell.handshake_type,
+                                    prev_node,
+                                    hop->extend_info);
+    }
 
-    onionskin = payload+2+4;
-    memcpy(payload+2+4+ONIONSKIN_CHALLENGE_LEN,
-           hop->extend_info->identity_digest, DIGEST_LEN);
-    payload_len = 2+4+ONIONSKIN_CHALLENGE_LEN+DIGEST_LEN;
+    tor_addr_copy(&ec.orport_ipv4.addr, &hop->extend_info->addr);
+    ec.orport_ipv4.port = hop->extend_info->port;
+    tor_addr_make_unspec(&ec.orport_ipv6.addr);
+    memcpy(ec.node_id, hop->extend_info->identity_digest, DIGEST_LEN);
 
-    if (onion_skin_create(hop->extend_info->onion_key,
-                          &(hop->dh_handshake_state), onionskin) < 0) {
+    len = onion_skin_create(ec.create_cell.handshake_type,
+                            hop->extend_info,
+                            &hop->handshake_state,
+                            ec.create_cell.onionskin);
+    if (len < 0) {
       log_warn(LD_CIRC,"onion_skin_create failed.");
       return - END_CIRC_REASON_INTERNAL;
     }
+    ec.create_cell.handshake_len = len;
 
     log_info(LD_CIRC,"Sending extend relay cell.");
     note_request("cell: extend", 1);
-    /* send it to hop->prev, because it will transfer
-     * it to a create cell and then send to hop */
-    if (relay_send_command_from_edge(0, TO_CIRCUIT(circ),
-                                     RELAY_COMMAND_EXTEND,
-                                     payload, payload_len, hop->prev) < 0)
-      return 0; /* circuit is closed */
+    {
+      uint8_t command = 0;
+      uint16_t payload_len=0;
+      uint8_t payload[RELAY_PAYLOAD_SIZE];
+      if (extend_cell_format(&command, &payload_len, payload, &ec)<0) {
+        log_warn(LD_CIRC,"Couldn't format extend cell");
+        return -END_CIRC_REASON_INTERNAL;
+      }
 
+      /* send it to hop->prev, because it will transfer
+       * it to a create cell and then send to hop */
+      if (relay_send_command_from_edge(0, TO_CIRCUIT(circ),
+                                       command,
+                                       (char*)payload, payload_len,
+                                       hop->prev) < 0)
+        return 0; /* circuit is closed */
+    }
     hop->state = CPATH_STATE_AWAITING_KEYS;
   }
   return 0;
@@ -814,11 +915,7 @@ circuit_extend(cell_t *cell, circuit_t *circ)
 {
   channel_t *n_chan;
   relay_header_t rh;
-  char *onionskin;
-  char *id_digest=NULL;
-  uint32_t n_addr32;
-  uint16_t n_port;
-  tor_addr_t n_addr;
+  extend_cell_t ec;
   const char *msg = NULL;
   int should_launch = 0;
 
@@ -841,27 +938,21 @@ circuit_extend(cell_t *cell, circuit_t *circ)
 
   relay_header_unpack(&rh, cell->payload);
 
-  if (rh.length < 4+2+ONIONSKIN_CHALLENGE_LEN+DIGEST_LEN) {
+  if (extend_cell_parse(&ec, rh.command,
+                        cell->payload+RELAY_HEADER_SIZE,
+                        rh.length) < 0) {
     log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
-           "Wrong length %d on extend cell. Closing circuit.",
-           rh.length);
+           "Can't parse extend cell. Closing circuit.");
     return -1;
   }
 
-  n_addr32 = ntohl(get_uint32(cell->payload+RELAY_HEADER_SIZE));
-  n_port = ntohs(get_uint16(cell->payload+RELAY_HEADER_SIZE+4));
-  onionskin = (char*) cell->payload+RELAY_HEADER_SIZE+4+2;
-  id_digest = (char*) cell->payload+RELAY_HEADER_SIZE+4+2+
-    ONIONSKIN_CHALLENGE_LEN;
-  tor_addr_from_ipv4h(&n_addr, n_addr32);
-
-  if (!n_port || !n_addr32) {
+  if (!ec.orport_ipv4.port || tor_addr_is_null(&ec.orport_ipv4.addr)) {
     log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
            "Client asked me to extend to zero destination port or addr.");
     return -1;
   }
 
-  if (tor_addr_is_internal(&n_addr, 0) &&
+  if (tor_addr_is_internal(&ec.orport_ipv4.addr, 0) &&
       !get_options()->ExtendAllowPrivateAddresses) {
     log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
            "Client asked me to extend to a private address");
@@ -874,7 +965,7 @@ circuit_extend(cell_t *cell, circuit_t *circ)
    * fingerprints -- a) because it opens the user up to a mitm attack,
    * and b) because it lets an attacker force the relay to hold open a
    * new TLS connection for each extend request. */
-  if (tor_digest_is_zero(id_digest)) {
+  if (tor_digest_is_zero((const char*)ec.node_id)) {
     log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
            "Client asked me to extend without specifying an id_digest.");
     return -1;
@@ -883,7 +974,7 @@ circuit_extend(cell_t *cell, circuit_t *circ)
   /* Next, check if we're being asked to connect to the hop that the
    * extend cell came from. There isn't any reason for that, and it can
    * assist circular-path attacks. */
-  if (tor_memeq(id_digest,
+  if (tor_memeq(ec.node_id,
                 TO_OR_CIRCUIT(circ)->p_chan->identity_digest,
                 DIGEST_LEN)) {
     log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
@@ -891,27 +982,33 @@ circuit_extend(cell_t *cell, circuit_t *circ)
     return -1;
   }
 
-  n_chan = channel_get_for_extend(id_digest,
-                                  &n_addr,
+  n_chan = channel_get_for_extend((const char*)ec.node_id,
+                                  &ec.orport_ipv4.addr,
                                   &msg,
                                   &should_launch);
 
   if (!n_chan) {
     log_debug(LD_CIRC|LD_OR,"Next router (%s): %s",
-              fmt_addrport(&n_addr, n_port), msg?msg:"????");
+              fmt_addrport(&ec.orport_ipv4.addr,ec.orport_ipv4.port),
+              msg?msg:"????");
 
     circ->n_hop = extend_info_new(NULL /*nickname*/,
-                                    id_digest,
-                                    NULL /*onion_key*/,
-                                    &n_addr, n_port);
+                                  (const char*)ec.node_id,
+                                  NULL /*onion_key*/,
+                                  NULL /*curve25519_key*/,
+                                  &ec.orport_ipv4.addr,
+                                  ec.orport_ipv4.port);
+
+    circ->n_chan_create_cell = tor_memdup(&ec.create_cell,
+                                          sizeof(ec.create_cell));
 
-    circ->n_chan_onionskin = tor_malloc(ONIONSKIN_CHALLENGE_LEN);
-    memcpy(circ->n_chan_onionskin, onionskin, ONIONSKIN_CHALLENGE_LEN);
     circuit_set_state(circ, CIRCUIT_STATE_CHAN_WAIT);
 
     if (should_launch) {
       /* we should try to open a connection */
-      n_chan = channel_connect_for_circuit(&n_addr, n_port, id_digest);
+      n_chan = channel_connect_for_circuit(&ec.orport_ipv4.addr,
+                                           ec.orport_ipv4.port,
+                                           (const char*)ec.node_id);
       if (!n_chan) {
         log_info(LD_CIRC,"Launching n_chan failed. Closing circuit.");
         circuit_mark_for_close(circ, END_CIRC_REASON_CONNECTFAILED);
@@ -932,8 +1029,9 @@ circuit_extend(cell_t *cell, circuit_t *circ)
             "n_chan is %s",
             channel_get_canonical_remote_descr(n_chan));
 
-  if (circuit_deliver_create_cell(circ, CELL_CREATE, onionskin) < 0)
+  if (circuit_deliver_create_cell(circ, &ec.create_cell, 1) < 0)
     return -1;
+
   return 0;
 }
 
@@ -1785,7 +1883,7 @@ entry_guard_inc_circ_attempt_count(entry_guard_t *guard)
 }
 
 /** A created or extended cell came back to us on the circuit, and it included
- * <b>reply</b> as its body.  (If <b>reply_type</b> is CELL_CREATED, the body
+ * reply_cell as its body.  (If <b>reply_type</b> is CELL_CREATED, the body
  * contains (the second DH key, plus KH).  If <b>reply_type</b> is
  * CELL_CREATED_FAST, the body contains a secret y and a hash H(x|y).)
  *
@@ -1795,8 +1893,8 @@ entry_guard_inc_circ_attempt_count(entry_guard_t *guard)
  * Return - reason if we want to mark circ for close, else return 0.
  */
 int
-circuit_finish_handshake(origin_circuit_t *circ, uint8_t reply_type,
-                         const uint8_t *reply)
+circuit_finish_handshake(origin_circuit_t *circ,
+                         const created_cell_t *reply)
 {
   char keys[CPATH_KEY_MATERIAL_LEN];
   crypt_path_t *hop;
@@ -1816,39 +1914,25 @@ circuit_finish_handshake(origin_circuit_t *circ, uint8_t reply_type,
   }
   tor_assert(hop->state == CPATH_STATE_AWAITING_KEYS);
 
-  if (reply_type == CELL_CREATED && hop->dh_handshake_state) {
-    if (onion_skin_client_handshake(hop->dh_handshake_state, (char*)reply,keys,
-                                    DIGEST_LEN*2+CIPHER_KEY_LEN*2) < 0) {
+  {
+    if (onion_skin_client_handshake(hop->handshake_state.tag,
+                                    &hop->handshake_state,
+                                    reply->reply, reply->handshake_len,
+                                    (uint8_t*)keys, sizeof(keys),
+                                    (uint8_t*)hop->rend_circ_nonce) < 0) {
       log_warn(LD_CIRC,"onion_skin_client_handshake failed.");
       return -END_CIRC_REASON_TORPROTOCOL;
     }
-    /* Remember hash of g^xy */
-    memcpy(hop->handshake_digest, reply+DH_KEY_LEN, DIGEST_LEN);
-  } else if (reply_type == CELL_CREATED_FAST && !hop->dh_handshake_state) {
-    if (fast_client_handshake(hop->fast_handshake_state, reply,
-                              (uint8_t*)keys,
-                              DIGEST_LEN*2+CIPHER_KEY_LEN*2) < 0) {
-      log_warn(LD_CIRC,"fast_client_handshake failed.");
-      return -END_CIRC_REASON_TORPROTOCOL;
-    }
-    memcpy(hop->handshake_digest, reply+DIGEST_LEN, DIGEST_LEN);
-  } else {
-    log_warn(LD_PROTOCOL,"CREATED cell type did not match CREATE cell type.");
-    return -END_CIRC_REASON_TORPROTOCOL;
   }
 
-  crypto_dh_free(hop->dh_handshake_state); /* don't need it anymore */
-  hop->dh_handshake_state = NULL;
-
-  memset(hop->fast_handshake_state, 0, sizeof(hop->fast_handshake_state));
+  onion_handshake_state_release(&hop->handshake_state);
 
   if (circuit_init_cpath_crypto(hop, keys, 0)<0) {
     return -END_CIRC_REASON_TORPROTOCOL;
   }
 
   hop->state = CPATH_STATE_OPEN;
-  log_info(LD_CIRC,"Finished building %scircuit hop:",
-           (reply_type == CELL_CREATED_FAST) ? "fast " : "");
+  log_info(LD_CIRC,"Finished building circuit hop:");
   circuit_log_path(LOG_INFO,LD_CIRC,circ);
   control_event_circuit_status(circ, CIRC_EVENT_EXTENDED, 0);
 
@@ -1908,24 +1992,25 @@ circuit_truncated(origin_circuit_t *circ, crypt_path_t *layer, int reason)
  * cell back.
  */
 int
-onionskin_answer(or_circuit_t *circ, uint8_t cell_type, const char *payload,
-                 const char *keys)
+onionskin_answer(or_circuit_t *circ,
+                 const created_cell_t *created_cell,
+                 const char *keys,
+                 const uint8_t *rend_circ_nonce)
 {
   cell_t cell;
   crypt_path_t *tmp_cpath;
 
+  if (created_cell_format(&cell, created_cell) < 0) {
+    log_warn(LD_BUG,"couldn't format created cell");
+    return -1;
+  }
+  cell.circ_id = circ->p_circ_id;
+
   tmp_cpath = tor_malloc_zero(sizeof(crypt_path_t));
   tmp_cpath->magic = CRYPT_PATH_MAGIC;
 
-  memset(&cell, 0, sizeof(cell_t));
-  cell.command = cell_type;
-  cell.circ_id = circ->p_circ_id;
-
   circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_OPEN);
 
-  memcpy(cell.payload, payload,
-         cell_type == CELL_CREATED ? ONIONSKIN_REPLY_LEN : DIGEST_LEN*2);
-
   log_debug(LD_CIRC,"init digest forward 0x%.8x, backward 0x%.8x.",
             (unsigned int)get_uint32(keys),
             (unsigned int)get_uint32(keys+20));
@@ -1941,12 +2026,9 @@ onionskin_answer(or_circuit_t *circ, uint8_t cell_type, const char *payload,
   tmp_cpath->magic = 0;
   tor_free(tmp_cpath);
 
-  if (cell_type == CELL_CREATED)
-    memcpy(circ->handshake_digest, cell.payload+DH_KEY_LEN, DIGEST_LEN);
-  else
-    memcpy(circ->handshake_digest, cell.payload+DIGEST_LEN, DIGEST_LEN);
+  memcpy(circ->rend_circ_nonce, rend_circ_nonce, DIGEST_LEN);
 
-  circ->is_first_hop = (cell_type == CELL_CREATED_FAST);
+  circ->is_first_hop = (created_cell->cell_type == CELL_CREATED_FAST);
 
   append_cell_to_circuit_queue(TO_CIRCUIT(circ),
                                circ->p_chan, &cell, CELL_DIRECTION_IN, 0);
@@ -2751,8 +2833,9 @@ onion_append_hop(crypt_path_t **head_ptr, extend_info_t *choice)
 /** Allocate a new extend_info object based on the various arguments. */
 extend_info_t *
 extend_info_new(const char *nickname, const char *digest,
-                  crypto_pk_t *onion_key,
-                  const tor_addr_t *addr, uint16_t port)
+                crypto_pk_t *onion_key,
+                const curve25519_public_key_t *curve25519_key,
+                const tor_addr_t *addr, uint16_t port)
 {
   extend_info_t *info = tor_malloc_zero(sizeof(extend_info_t));
   memcpy(info->identity_digest, digest, DIGEST_LEN);
@@ -2760,6 +2843,13 @@ extend_info_new(const char *nickname, const char *digest,
     strlcpy(info->nickname, nickname, sizeof(info->nickname));
   if (onion_key)
     info->onion_key = crypto_pk_dup_key(onion_key);
+#ifdef CURVE25519_ENABLED
+  if (curve25519_key)
+    memcpy(&info->curve25519_onion_key, curve25519_key,
+           sizeof(curve25519_public_key_t));
+#else
+  (void)curve25519_key;
+#endif
   tor_addr_copy(&info->addr, addr);
   info->port = port;
   return info;
@@ -2794,12 +2884,14 @@ extend_info_from_node(const node_t *node, int for_direct_connect)
     return extend_info_new(node->ri->nickname,
                              node->identity,
                              node->ri->onion_pkey,
+                             node->ri->onion_curve25519_pkey,
                              &ap.addr,
                              ap.port);
   else if (node->rs && node->md)
     return extend_info_new(node->rs->nickname,
                              node->identity,
                              node->md->onion_pkey,
+                             node->md->onion_curve25519_pkey,
                              &ap.addr,
                              ap.port);
   else
diff --git a/src/or/circuitbuild.h b/src/or/circuitbuild.h
index 8cd61fae2d..029bdaa47d 100644
--- a/src/or/circuitbuild.h
+++ b/src/or/circuitbuild.h
@@ -30,12 +30,15 @@ void circuit_note_clock_jumped(int seconds_elapsed);
 int circuit_extend(cell_t *cell, circuit_t *circ);
 int circuit_init_cpath_crypto(crypt_path_t *cpath, const char *key_data,
                               int reverse);
-int circuit_finish_handshake(origin_circuit_t *circ, uint8_t cell_type,
-                             const uint8_t *reply);
+struct created_cell_t;
+int circuit_finish_handshake(origin_circuit_t *circ,
+                             const struct created_cell_t *created_cell);
 int circuit_truncated(origin_circuit_t *circ, crypt_path_t *layer,
                       int reason);
-int onionskin_answer(or_circuit_t *circ, uint8_t cell_type,
-                     const char *payload, const char *keys);
+int onionskin_answer(or_circuit_t *circ,
+                     const struct created_cell_t *created_cell,
+                     const char *keys,
+                     const uint8_t *rend_circ_nonce);
 int circuit_all_predicted_ports_handled(time_t now, int *need_uptime,
                                         int *need_capacity);
 
@@ -43,8 +46,9 @@ int circuit_append_new_exit(origin_circuit_t *circ, extend_info_t *info);
 int circuit_extend_to_new_exit(origin_circuit_t *circ, extend_info_t *info);
 void onion_append_to_cpath(crypt_path_t **head_ptr, crypt_path_t *new_hop);
 extend_info_t *extend_info_new(const char *nickname, const char *digest,
-                                 crypto_pk_t *onion_key,
-                                 const tor_addr_t *addr, uint16_t port);
+                               crypto_pk_t *onion_key,
+                               const curve25519_public_key_t *curve25519_key,
+                               const tor_addr_t *addr, uint16_t port);
 extend_info_t *extend_info_from_node(const node_t *r, int for_direct_connect);
 extend_info_t *extend_info_dup(extend_info_t *info);
 void extend_info_free(extend_info_t *info);
diff --git a/src/or/circuitlist.c b/src/or/circuitlist.c
index 0ee29000ed..1a7306292f 100644
--- a/src/or/circuitlist.c
+++ b/src/or/circuitlist.c
@@ -23,6 +23,7 @@
 #include "networkstatus.h"
 #include "nodelist.h"
 #include "onion.h"
+#include "onion_fast.h"
 #include "relay.h"
 #include "rendclient.h"
 #include "rendcommon.h"
@@ -251,7 +252,7 @@ circuit_set_state(circuit_t *circ, uint8_t state)
     smartlist_add(circuits_pending_chans, circ);
   }
   if (state == CIRCUIT_STATE_OPEN)
-    tor_assert(!circ->n_chan_onionskin);
+    tor_assert(!circ->n_chan_create_cell);
   circ->state = state;
 }
 
@@ -678,7 +679,7 @@ circuit_free(circuit_t *circ)
   }
 
   extend_info_free(circ->n_hop);
-  tor_free(circ->n_chan_onionskin);
+  tor_free(circ->n_chan_create_cell);
 
   /* Remove from map. */
   circuit_set_n_circid_chan(circ, 0, NULL);
@@ -748,7 +749,8 @@ circuit_free_cpath_node(crypt_path_t *victim)
   crypto_cipher_free(victim->b_crypto);
   crypto_digest_free(victim->f_digest);
   crypto_digest_free(victim->b_digest);
-  crypto_dh_free(victim->dh_handshake_state);
+  onion_handshake_state_release(&victim->handshake_state);
+  crypto_dh_free(victim->rend_dh_handshake_state);
   extend_info_free(victim->extend_info);
 
   memwipe(victim, 0xBB, sizeof(crypt_path_t)); /* poison memory */
@@ -1505,7 +1507,8 @@ assert_cpath_layer_ok(const crypt_path_t *cp)
       tor_assert(cp->b_crypto);
       /* fall through */
     case CPATH_STATE_CLOSED:
-      tor_assert(!cp->dh_handshake_state);
+      /*XXXX Assert that there's no handshake_state either. */
+      tor_assert(!cp->rend_dh_handshake_state);
       break;
     case CPATH_STATE_AWAITING_KEYS:
       /* tor_assert(cp->dh_handshake_state); */
@@ -1592,7 +1595,7 @@ assert_circuit_ok(const circuit_t *c)
   tor_assert(c->deliver_window >= 0);
   tor_assert(c->package_window >= 0);
   if (c->state == CIRCUIT_STATE_OPEN) {
-    tor_assert(!c->n_chan_onionskin);
+    tor_assert(!c->n_chan_create_cell);
     if (or_circ) {
       tor_assert(or_circ->n_crypto);
       tor_assert(or_circ->p_crypto);
diff --git a/src/or/circuituse.c b/src/or/circuituse.c
index c3495b4402..e414df1026 100644
--- a/src/or/circuituse.c
+++ b/src/or/circuituse.c
@@ -1697,8 +1697,8 @@ circuit_get_open_circ_or_launch(entry_connection_t *conn,
               return -1;
             }
             extend_info = extend_info_new(conn->chosen_exit_name+1,
-                                            digest, NULL, &addr,
-                                            conn->socks_request->port);
+                                          digest, NULL, NULL, &addr,
+                                          conn->socks_request->port);
           } else {
             /* We will need an onion key for the router, and we
              * don't have one. Refuse or relax requirements. */
diff --git a/src/or/command.c b/src/or/command.c
index 39eccdf82d..7d1f53a879 100644
--- a/src/or/command.c
+++ b/src/or/command.c
@@ -133,11 +133,13 @@ command_process_cell(channel_t *chan, cell_t *cell)
   switch (cell->command) {
     case CELL_CREATE:
     case CELL_CREATE_FAST:
+    case CELL_CREATE2:
       ++stats_n_create_cells_processed;
       PROCESS_CELL(create, cell, chan);
       break;
     case CELL_CREATED:
     case CELL_CREATED_FAST:
+    case CELL_CREATED2:
       ++stats_n_created_cells_processed;
       PROCESS_CELL(created, cell, chan);
       break;
@@ -187,6 +189,7 @@ command_process_create_cell(cell_t *cell, channel_t *chan)
   or_circuit_t *circ;
   const or_options_t *options = get_options();
   int id_is_high;
+  create_cell_t *create_cell;
 
   tor_assert(cell);
   tor_assert(chan);
@@ -252,12 +255,18 @@ command_process_create_cell(cell_t *cell, channel_t *chan)
   circ = or_circuit_new(cell->circ_id, chan);
   circ->base_.purpose = CIRCUIT_PURPOSE_OR;
   circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_ONIONSKIN_PENDING);
-  if (cell->command == CELL_CREATE) {
-    char *onionskin = tor_malloc(ONIONSKIN_CHALLENGE_LEN);
-    memcpy(onionskin, cell->payload, ONIONSKIN_CHALLENGE_LEN);
+  create_cell = tor_malloc_zero(sizeof(create_cell_t));
+  if (create_cell_parse(create_cell, cell) < 0) {
+    tor_free(create_cell);
+    log_fn(LOG_PROTOCOL_WARN, LD_OR,
+           "Bogus/unrecognized create cell; closing.");
+    circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_TORPROTOCOL);
+    return;
+  }
 
+  if (create_cell->handshake_type != ONION_HANDSHAKE_TYPE_FAST) {
     /* hand it off to the cpuworkers, and then return. */
-    if (assign_onionskin_to_cpuworker(NULL, circ, onionskin) < 0) {
+    if (assign_onionskin_to_cpuworker(NULL, circ, create_cell) < 0) {
       log_debug(LD_GENERAL,"Failed to hand off onionskin. Closing.");
       circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_RESOURCELIMIT);
       return;
@@ -266,26 +275,40 @@ command_process_create_cell(cell_t *cell, channel_t *chan)
   } else {
     /* This is a CREATE_FAST cell; we can handle it immediately without using
      * a CPU worker. */
-    char keys[CPATH_KEY_MATERIAL_LEN];
-    char reply[DIGEST_LEN*2];
-
-    tor_assert(cell->command == CELL_CREATE_FAST);
+    uint8_t keys[CPATH_KEY_MATERIAL_LEN];
+    uint8_t rend_circ_nonce[DIGEST_LEN];
+    int len;
+    created_cell_t created_cell;
 
     /* Make sure we never try to use the OR connection on which we
      * received this cell to satisfy an EXTEND request,  */
     channel_mark_client(chan);
 
-    if (fast_server_handshake(cell->payload, (uint8_t*)reply,
-                              (uint8_t*)keys, sizeof(keys))<0) {
+    memset(&created_cell, 0, sizeof(created_cell));
+    len = onion_skin_server_handshake(ONION_HANDSHAKE_TYPE_FAST,
+                                       create_cell->onionskin,
+                                       create_cell->handshake_len,
+                                       NULL,
+                                       created_cell.reply,
+                                       keys, CPATH_KEY_MATERIAL_LEN,
+                                       rend_circ_nonce);
+    tor_free(create_cell);
+    if (len < 0) {
       log_warn(LD_OR,"Failed to generate key material. Closing.");
       circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_INTERNAL);
+      tor_free(create_cell);
       return;
     }
-    if (onionskin_answer(circ, CELL_CREATED_FAST, reply, keys)<0) {
+    created_cell.cell_type = CELL_CREATED_FAST;
+    created_cell.handshake_len = len;
+
+    if (onionskin_answer(circ, &created_cell,
+                         (const char *)keys, rend_circ_nonce)<0) {
       log_warn(LD_OR,"Failed to reply to CREATE_FAST cell. Closing.");
       circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_INTERNAL);
       return;
     }
+    memwipe(keys, 0, sizeof(keys));
   }
 }
 
@@ -301,6 +324,7 @@ static void
 command_process_created_cell(cell_t *cell, channel_t *chan)
 {
   circuit_t *circ;
+  extended_cell_t extended_cell;
 
   circ = circuit_get_by_circid_channel(cell->circ_id, chan);
 
@@ -318,12 +342,18 @@ command_process_created_cell(cell_t *cell, channel_t *chan)
     return;
   }
 
+  if (created_cell_parse(&extended_cell.created_cell, cell) < 0) {
+    log_fn(LOG_PROTOCOL_WARN, LD_OR, "Unparseable created cell.");
+    circuit_mark_for_close(circ, END_CIRC_REASON_TORPROTOCOL);
+    return;
+  }
+
   if (CIRCUIT_IS_ORIGIN(circ)) { /* we're the OP. Handshake this. */
     origin_circuit_t *origin_circ = TO_ORIGIN_CIRCUIT(circ);
     int err_reason = 0;
     log_debug(LD_OR,"at OP. Finishing handshake.");
-    if ((err_reason = circuit_finish_handshake(origin_circ, cell->command,
-                                               cell->payload)) < 0) {
+    if ((err_reason = circuit_finish_handshake(origin_circ,
+                                        &extended_cell.created_cell)) < 0) {
       log_warn(LD_OR,"circuit_finish_handshake failed.");
       circuit_mark_for_close(circ, -err_reason);
       return;
@@ -336,11 +366,24 @@ command_process_created_cell(cell_t *cell, channel_t *chan)
       return;
     }
   } else { /* pack it into an extended relay cell, and send it. */
+    uint8_t command=0;
+    uint16_t len=0;
+    uint8_t payload[RELAY_PAYLOAD_SIZE];
     log_debug(LD_OR,
               "Converting created cell to extended relay cell, sending.");
-    relay_send_command_from_edge(0, circ, RELAY_COMMAND_EXTENDED,
-                                 (char*)cell->payload, ONIONSKIN_REPLY_LEN,
-                                 NULL);
+    memset(payload, 0, sizeof(payload));
+    if (extended_cell.created_cell.cell_type == CELL_CREATED2)
+      extended_cell.cell_type = RELAY_COMMAND_EXTENDED2;
+    else
+      extended_cell.cell_type = RELAY_COMMAND_EXTENDED;
+    if (extended_cell_format(&command, &len, payload, &extended_cell) < 0) {
+      log_fn(LOG_PROTOCOL_WARN, LD_OR, "Can't format extended cell.");
+      circuit_mark_for_close(circ, END_CIRC_REASON_TORPROTOCOL);
+      return;
+    }
+
+    relay_send_command_from_edge(0, circ, command,
+                                 (const char*)payload, len, NULL);
   }
 }
 
diff --git a/src/or/config.c b/src/or/config.c
index 60866218c5..9905a94fda 100644
--- a/src/or/config.c
+++ b/src/or/config.c
@@ -390,6 +390,7 @@ static config_var_t option_vars_[] = {
   V(UseEntryGuards,              BOOL,     "1"),
   V(UseEntryGuardsAsDirGuards,   BOOL,     "1"),
   V(UseMicrodescriptors,         AUTOBOOL, "auto"),
+  V(UseNTorHandshake,            AUTOBOOL, "auto"),
   V(User,                        STRING,   NULL),
   V(UserspaceIOCPBuffers,        BOOL,     "0"),
   VAR("V1AuthoritativeDirectory",BOOL, V1AuthoritativeDir,   "0"),
diff --git a/src/or/cpuworker.c b/src/or/cpuworker.c
index 2164e52a41..3f8fc947b3 100644
--- a/src/or/cpuworker.c
+++ b/src/or/cpuworker.c
@@ -32,9 +32,6 @@
 
 /** The tag specifies which circuit this onionskin was from. */
 #define TAG_LEN 10
-/** How many bytes are sent from the cpuworker back to tor? */
-#define LEN_ONION_RESPONSE \
-  (1+TAG_LEN+ONIONSKIN_REPLY_LEN+CPATH_KEY_MATERIAL_LEN)
 
 /** How many cpuworkers we have running right now. */
 static int num_cpuworkers=0;
@@ -70,7 +67,7 @@ connection_cpu_finished_flushing(connection_t *conn)
 /** Pack global_id and circ_id; set *tag to the result. (See note on
  * cpuworker_main for wire format.) */
 static void
-tag_pack(char *tag, uint64_t chan_id, circid_t circ_id)
+tag_pack(uint8_t *tag, uint64_t chan_id, circid_t circ_id)
 {
   /*XXXX RETHINK THIS WHOLE MESS !!!! !NM NM NM NM*/
   /*XXXX DOUBLEPLUSTHIS!!!! AS AS AS AS*/
@@ -81,12 +78,53 @@ tag_pack(char *tag, uint64_t chan_id, circid_t circ_id)
 /** Unpack <b>tag</b> into addr, port, and circ_id.
  */
 static void
-tag_unpack(const char *tag, uint64_t *chan_id, circid_t *circ_id)
+tag_unpack(const uint8_t *tag, uint64_t *chan_id, circid_t *circ_id)
 {
   *chan_id = get_uint64(tag);
   *circ_id = get_uint16(tag+8);
 }
 
+/** Magic numbers to make sure our cpuworker_requests don't grow any
+ * mis-framing bugs. */
+#define CPUWORKER_REQUEST_MAGIC 0xda4afeed
+#define CPUWORKER_REPLY_MAGIC 0x5eedf00d
+
+/** A request sent to a cpuworker. */
+typedef struct cpuworker_request_t {
+  /** Magic number; must be CPUWORKER_REQUEST_MAGIC. */
+  uint32_t magic;
+  /** Opaque tag to identify the job */
+  uint8_t tag[TAG_LEN];
+  /** Task code. Must be one of CPUWORKER_TASK_* */
+  uint8_t task;
+
+  /** A create cell for the cpuworker to process. */
+  create_cell_t create_cell;
+
+  /* Turn the above into a tagged union if needed. */
+} cpuworker_request_t;
+
+/** A reply sent by a cpuworker. */
+typedef struct cpuworker_reply_t {
+  /** Magic number; must be CPUWORKER_REPLY_MAGIC. */
+  uint32_t magic;
+  /** Opaque tag to identify the job; matches the request's tag.*/
+  uint8_t tag[TAG_LEN];
+  /** True iff we got a successful request. */
+  uint8_t success;
+
+  /** Output of processing a create cell
+   *
+   * @{
+   */
+  /** The created cell to send back. */
+  created_cell_t created_cell;
+  /** The keys to use on this circuit. */
+  uint8_t keys[CPATH_KEY_MATERIAL_LEN];
+  /** Input to use for authenticating introduce1 cells. */
+  uint8_t rend_auth_material[DIGEST_LEN];
+} cpuworker_reply_t;
+
 /** Called when the onion key has changed and we need to spawn new
  * cpuworkers.  Close all currently idle cpuworkers, and mark the last
  * rotation time as now.
@@ -132,8 +170,6 @@ connection_cpu_reached_eof(connection_t *conn)
 int
 connection_cpu_process_inbuf(connection_t *conn)
 {
-  char success;
-  char buf[LEN_ONION_RESPONSE];
   uint64_t chan_id;
   circid_t circ_id;
   channel_t *p_chan = NULL;
@@ -146,15 +182,16 @@ connection_cpu_process_inbuf(connection_t *conn)
     return 0;
 
   if (conn->state == CPUWORKER_STATE_BUSY_ONION) {
-    if (connection_get_inbuf_len(conn) < LEN_ONION_RESPONSE)
+    cpuworker_reply_t rpl;
+    if (connection_get_inbuf_len(conn) < sizeof(cpuworker_reply_t))
       return 0; /* not yet */
-    tor_assert(connection_get_inbuf_len(conn) == LEN_ONION_RESPONSE);
+    tor_assert(connection_get_inbuf_len(conn) == sizeof(cpuworker_reply_t));
 
-    connection_fetch_from_buf(&success,1,conn);
-    connection_fetch_from_buf(buf,LEN_ONION_RESPONSE-1,conn);
+    connection_fetch_from_buf((void*)&rpl,sizeof(cpuworker_reply_t),conn);
 
+    tor_assert(rpl.magic == CPUWORKER_REPLY_MAGIC);
     /* parse out the circ it was talking about */
-    tag_unpack(buf, &chan_id, &circ_id);
+    tag_unpack(rpl.tag, &chan_id, &circ_id);
     circ = NULL;
     log_debug(LD_OR,
               "Unpacking cpuworker reply, chan_id is " U64_FORMAT
@@ -165,7 +202,7 @@ connection_cpu_process_inbuf(connection_t *conn)
     if (p_chan)
       circ = circuit_get_by_circid_channel(circ_id, p_chan);
 
-    if (success == 0) {
+    if (rpl.success == 0) {
       log_debug(LD_OR,
                 "decoding onionskin failed. "
                 "(Old key or bad software.) Closing.");
@@ -183,8 +220,10 @@ connection_cpu_process_inbuf(connection_t *conn)
       goto done_processing;
     }
     tor_assert(! CIRCUIT_IS_ORIGIN(circ));
-    if (onionskin_answer(TO_OR_CIRCUIT(circ), CELL_CREATED, buf+TAG_LEN,
-                         buf+TAG_LEN+ONIONSKIN_REPLY_LEN) < 0) {
+    if (onionskin_answer(TO_OR_CIRCUIT(circ),
+                         &rpl.created_cell,
+                         (const char*)rpl.keys,
+                         rpl.rend_auth_material) < 0) {
       log_warn(LD_OR,"onionskin_answer failed. Closing.");
       circuit_mark_for_close(circ, END_CIRC_REASON_INTERNAL);
       goto done_processing;
@@ -211,32 +250,21 @@ connection_cpu_process_inbuf(connection_t *conn)
  * Read and writes from fdarray[1].  Reads requests, writes answers.
  *
  *   Request format:
- *          Task type           [1 byte, always CPUWORKER_TASK_ONION]
- *          Opaque tag          TAG_LEN
- *          Onionskin challenge ONIONSKIN_CHALLENGE_LEN
+ *          cpuworker_request_t.
  *   Response format:
- *          Success/failure     [1 byte, boolean.]
- *          Opaque tag          TAG_LEN
- *          Onionskin challenge ONIONSKIN_REPLY_LEN
- *          Negotiated keys     KEY_LEN*2+DIGEST_LEN*2
- *
- *  (Note: this _should_ be by addr/port, since we're concerned with specific
- * connections, not with routers (where we'd use identity).)
+ *          cpuworker_reply_t
  */
 static void
 cpuworker_main(void *data)
 {
-  char question[ONIONSKIN_CHALLENGE_LEN];
-  uint8_t question_type;
+  /* For talking to the parent thread/process */
   tor_socket_t *fdarray = data;
   tor_socket_t fd;
 
   /* variables for onion processing */
-  char keys[CPATH_KEY_MATERIAL_LEN];
-  char reply_to_proxy[ONIONSKIN_REPLY_LEN];
-  char buf[LEN_ONION_RESPONSE];
-  char tag[TAG_LEN];
-  crypto_pk_t *onion_key = NULL, *last_onion_key = NULL;
+  server_onion_keys_t onion_keys;
+  cpuworker_request_t req;
+  cpuworker_reply_t rpl;
 
   fd = fdarray[1]; /* this side is ours */
 #ifndef TOR_IS_MULTITHREADED
@@ -247,68 +275,68 @@ cpuworker_main(void *data)
 #endif
   tor_free(data);
 
-  dup_onion_keys(&onion_key, &last_onion_key);
+  setup_server_onion_keys(&onion_keys);
 
   for (;;) {
-    ssize_t r;
-
-    if ((r = recv(fd, (void *)&question_type, 1, 0)) != 1) {
-//      log_fn(LOG_ERR,"read type failed. Exiting.");
-      if (r == 0) {
-        log_info(LD_OR,
-                 "CPU worker exiting because Tor process closed connection "
-                 "(either rotated keys or died).");
-      } else {
-        log_info(LD_OR,
-                 "CPU worker exiting because of error on connection to Tor "
-                 "process.");
-        log_info(LD_OR,"(Error on "TOR_SOCKET_T_FORMAT" was %s)",
-                 fd, tor_socket_strerror(tor_socket_errno(fd)));
-      }
-      goto end;
-    }
-    tor_assert(question_type == CPUWORKER_TASK_ONION);
-
-    if (read_all(fd, tag, TAG_LEN, 1) != TAG_LEN) {
-      log_err(LD_BUG,"read tag failed. Exiting.");
+    if (read_all(fd, (void *)&req, sizeof(req), 1) != sizeof(req)) {
+      log_info(LD_OR, "read request failed. Exiting.");
       goto end;
     }
-
-    if (read_all(fd, question, ONIONSKIN_CHALLENGE_LEN, 1) !=
-        ONIONSKIN_CHALLENGE_LEN) {
-      log_err(LD_BUG,"read question failed. Exiting.");
-      goto end;
-    }
-
-    if (question_type == CPUWORKER_TASK_ONION) {
-      if (onion_skin_server_handshake(question, onion_key, last_onion_key,
-          reply_to_proxy, keys, CPATH_KEY_MATERIAL_LEN) < 0) {
+    tor_assert(req.magic == CPUWORKER_REQUEST_MAGIC);
+
+    memset(&rpl, 0, sizeof(rpl));
+
+    if (req.task == CPUWORKER_TASK_ONION) {
+      const create_cell_t *cc = &req.create_cell;
+      created_cell_t *cell_out = &rpl.created_cell;
+      int n;
+      n = onion_skin_server_handshake(cc->handshake_type,
+                                      cc->onionskin, cc->handshake_len,
+                                      &onion_keys,
+                                      cell_out->reply,
+                                      rpl.keys, CPATH_KEY_MATERIAL_LEN,
+                                      rpl.rend_auth_material);
+      if (n < 0) {
         /* failure */
         log_debug(LD_OR,"onion_skin_server_handshake failed.");
-        *buf = 0; /* indicate failure in first byte */
-        memcpy(buf+1,tag,TAG_LEN);
-        /* send all zeros as answer */
-        memset(buf+1+TAG_LEN, 0, LEN_ONION_RESPONSE-(1+TAG_LEN));
+        memset(&rpl, 0, sizeof(rpl));
+        memcpy(rpl.tag, req.tag, TAG_LEN);
+        rpl.success = 0;
       } else {
         /* success */
         log_debug(LD_OR,"onion_skin_server_handshake succeeded.");
-        buf[0] = 1; /* 1 means success */
-        memcpy(buf+1,tag,TAG_LEN);
-        memcpy(buf+1+TAG_LEN,reply_to_proxy,ONIONSKIN_REPLY_LEN);
-        memcpy(buf+1+TAG_LEN+ONIONSKIN_REPLY_LEN,keys,CPATH_KEY_MATERIAL_LEN);
+        memcpy(rpl.tag, req.tag, TAG_LEN);
+        cell_out->handshake_len = n;
+        switch (cc->cell_type) {
+        case CELL_CREATE:
+          cell_out->cell_type = CELL_CREATED; break;
+        case CELL_CREATE2:
+          cell_out->cell_type = CELL_CREATED2; break;
+        case CELL_CREATE_FAST:
+          cell_out->cell_type = CELL_CREATED_FAST; break;
+        default:
+          tor_assert(0);
+          goto end;
+        }
+        rpl.success = 1;
       }
-      if (write_all(fd, buf, LEN_ONION_RESPONSE, 1) != LEN_ONION_RESPONSE) {
+      rpl.magic = CPUWORKER_REPLY_MAGIC;
+      if (write_all(fd, (void*)&rpl, sizeof(rpl), 1) != sizeof(rpl)) {
         log_err(LD_BUG,"writing response buf failed. Exiting.");
         goto end;
       }
       log_debug(LD_OR,"finished writing response.");
+    } else if (req.task == CPUWORKER_TASK_SHUTDOWN) {
+      log_info(LD_OR,"Clean shutdown: exiting");
+      goto end;
     }
+    memwipe(&req, 0, sizeof(req));
+    memwipe(&rpl, 0, sizeof(req));
   }
  end:
-  if (onion_key)
-    crypto_pk_free(onion_key);
-  if (last_onion_key)
-    crypto_pk_free(last_onion_key);
+  memwipe(&req, 0, sizeof(req));
+  memwipe(&rpl, 0, sizeof(req));
+  release_server_onion_keys(&onion_keys);
   tor_close_socket(fd);
   crypto_thread_cleanup();
   spawn_exit();
@@ -391,7 +419,7 @@ static void
 process_pending_task(connection_t *cpuworker)
 {
   or_circuit_t *circ;
-  char *onionskin = NULL;
+  create_cell_t *onionskin = NULL;
 
   tor_assert(cpuworker);
 
@@ -444,10 +472,10 @@ cull_wedged_cpuworkers(void)
  */
 int
 assign_onionskin_to_cpuworker(connection_t *cpuworker,
-                              or_circuit_t *circ, char *onionskin)
+                              or_circuit_t *circ,
+                              create_cell_t *onionskin)
 {
-  char qbuf[1];
-  char tag[TAG_LEN];
+  cpuworker_request_t req;
   time_t now = approx_time();
   static time_t last_culled_cpuworkers = 0;
 
@@ -483,7 +511,10 @@ assign_onionskin_to_cpuworker(connection_t *cpuworker,
       tor_free(onionskin);
       return -1;
     }
-    tag_pack(tag, circ->p_chan->global_identifier,
+
+    memset(&req, 0, sizeof(req));
+    req.magic = CPUWORKER_REQUEST_MAGIC;
+    tag_pack(req.tag, circ->p_chan->global_identifier,
              circ->p_circ_id);
 
     cpuworker->state = CPUWORKER_STATE_BUSY_ONION;
@@ -493,11 +524,13 @@ assign_onionskin_to_cpuworker(connection_t *cpuworker,
     cpuworker->timestamp_lastwritten = time(NULL);
     num_cpuworkers_busy++;
 
-    qbuf[0] = CPUWORKER_TASK_ONION;
-    connection_write_to_buf(qbuf, 1, cpuworker);
-    connection_write_to_buf(tag, sizeof(tag), cpuworker);
-    connection_write_to_buf(onionskin, ONIONSKIN_CHALLENGE_LEN, cpuworker);
+    req.task = CPUWORKER_TASK_ONION;
+    memcpy(&req.create_cell, onionskin, sizeof(create_cell_t));
+
     tor_free(onionskin);
+
+    connection_write_to_buf((void*)&req, sizeof(req), cpuworker);
+    memwipe(&req, 0, sizeof(req));
   }
   return 0;
 }
diff --git a/src/or/cpuworker.h b/src/or/cpuworker.h
index 73c7eefd4c..f607e7d484 100644
--- a/src/or/cpuworker.h
+++ b/src/or/cpuworker.h
@@ -17,9 +17,10 @@ void cpuworkers_rotate(void);
 int connection_cpu_finished_flushing(connection_t *conn);
 int connection_cpu_reached_eof(connection_t *conn);
 int connection_cpu_process_inbuf(connection_t *conn);
+struct create_cell_t;
 int assign_onionskin_to_cpuworker(connection_t *cpuworker,
                                   or_circuit_t *circ,
-                                  char *onionskin);
+                                  struct create_cell_t *onionskin);
 
 #endif
 
diff --git a/src/or/dirserv.c b/src/or/dirserv.c
index d080fe7b1e..7ffd753524 100644
--- a/src/or/dirserv.c
+++ b/src/or/dirserv.c
@@ -74,7 +74,8 @@ static const struct consensus_method_range_t {
 } microdesc_consensus_methods[] = {
   {MIN_METHOD_FOR_MICRODESC, MIN_METHOD_FOR_A_LINES - 1},
   {MIN_METHOD_FOR_A_LINES, MIN_METHOD_FOR_P6_LINES - 1},
-  {MIN_METHOD_FOR_P6_LINES, MAX_SUPPORTED_CONSENSUS_METHOD},
+  {MIN_METHOD_FOR_P6_LINES, MIN_METHOD_FOR_NTOR_KEY - 1},
+  {MIN_METHOD_FOR_NTOR_KEY, MAX_SUPPORTED_CONSENSUS_METHOD},
   {-1, -1}
 };
 
diff --git a/src/or/dirvote.c b/src/or/dirvote.c
index 3000ee26e5..ef1e506f45 100644
--- a/src/or/dirvote.c
+++ b/src/or/dirvote.c
@@ -3554,6 +3554,15 @@ dirvote_create_microdescriptor(const routerinfo_t *ri, int consensus_method)
 
   smartlist_add_asprintf(chunks, "onion-key\n%s", key);
 
+  if (consensus_method >= MIN_METHOD_FOR_NTOR_KEY &&
+      ri->onion_curve25519_pkey) {
+    char kbuf[128];
+    base64_encode(kbuf, sizeof(kbuf),
+                  (const char*)ri->onion_curve25519_pkey->public_key,
+                  CURVE25519_PUBKEY_LEN);
+    smartlist_add_asprintf(chunks, "ntor-onion-key %s", kbuf);
+  }
+
   if (consensus_method >= MIN_METHOD_FOR_A_LINES &&
       !tor_addr_is_null(&ri->ipv6_addr) && ri->ipv6_orport)
     smartlist_add_asprintf(chunks, "a %s\n",
diff --git a/src/or/dirvote.h b/src/or/dirvote.h
index d14a375161..19444c370c 100644
--- a/src/or/dirvote.h
+++ b/src/or/dirvote.h
@@ -20,7 +20,7 @@
 #define MIN_VOTE_INTERVAL 300
 
 /** The highest consensus method that we currently support. */
-#define MAX_SUPPORTED_CONSENSUS_METHOD 15
+#define MAX_SUPPORTED_CONSENSUS_METHOD 16
 
 /** Lowest consensus method that contains a 'directory-footer' marker */
 #define MIN_METHOD_FOR_FOOTER 9
@@ -48,6 +48,10 @@
 /** Lowest consensus method where microdescs may include a "p6" line. */
 #define MIN_METHOD_FOR_P6_LINES 15
 
+/** Lowest consensus method where microdescs may include an onion-key-ntor
+ * line */
+#define MIN_METHOD_FOR_NTOR_KEY 16
+
 void dirvote_free_all(void);
 
 /* vote manipulation */
diff --git a/src/or/entrynodes.c b/src/or/entrynodes.c
index 84c1af4a1a..e583b881e5 100644
--- a/src/or/entrynodes.c
+++ b/src/or/entrynodes.c
@@ -1611,7 +1611,7 @@ routerset_contains_bridge(const routerset_t *routerset,
     return 0;
 
   extinfo = extend_info_new(
-         NULL, bridge->identity, NULL, &bridge->addr, bridge->port);
+         NULL, bridge->identity, NULL, NULL, &bridge->addr, bridge->port);
   result = routerset_contains_extendinfo(routerset, extinfo);
   extend_info_free(extinfo);
   return result;
diff --git a/src/or/include.am b/src/or/include.am
index 405cbd071f..08a27e17b2 100644
--- a/src/or/include.am
+++ b/src/or/include.am
@@ -15,6 +15,12 @@ else
 evdns_source=src/ext/eventdns.c
 endif
 
+if CURVE25519_ENABLED
+onion_ntor_source=src/or/onion_ntor.c
+else
+onion_ntor_source=
+endif
+
 src_or_libtor_a_SOURCES = \
 	src/or/addressmap.c				\
 	src/or/buffers.c				\
@@ -47,6 +53,8 @@ src_or_libtor_a_SOURCES = \
 	src/or/networkstatus.c				\
 	src/or/nodelist.c				\
 	src/or/onion.c					\
+	src/or/onion_fast.c				\
+	src/or/onion_tap.c				\
 	src/or/transports.c				\
 	src/or/policies.c				\
 	src/or/reasons.c				\
@@ -65,6 +73,7 @@ src_or_libtor_a_SOURCES = \
 	src/or/status.c					\
 	$(evdns_source)					\
 	$(tor_platform_source)				\
+	$(onion_ntor_source)				\
 	src/or/config_codedigest.c
 
 #libtor_a_LIBADD = ../common/libor.a ../common/libor-crypto.a \
@@ -86,7 +95,8 @@ AM_CPPFLAGS += -DSHARE_DATADIR="\"$(datadir)\"" \
 
 
 src_or_tor_LDFLAGS = @TOR_LDFLAGS_zlib@ @TOR_LDFLAGS_openssl@ @TOR_LDFLAGS_libevent@
-src_or_tor_LDADD = src/or/libtor.a src/common/libor.a src/common/libor-crypto.a \
+src_or_tor_LDADD = src/or/libtor.a src/common/libor.a \
+	src/common/libor-crypto.a $(LIBDONNA) \
 	src/common/libor-event.a \
 	@TOR_ZLIB_LIBS@ @TOR_LIB_MATH@ @TOR_LIBEVENT_LIBS@ @TOR_OPENSSL_LIBS@ \
 	@TOR_LIB_WS32@ @TOR_LIB_GDI@
@@ -125,6 +135,9 @@ ORHEADERS = \
 	src/or/nodelist.h				\
 	src/or/ntmain.h					\
 	src/or/onion.h					\
+	src/or/onion_fast.h				\
+	src/or/onion_ntor.h				\
+	src/or/onion_tap.h				\
 	src/or/or.h					\
 	src/or/transports.h				\
 	src/or/policies.h				\
diff --git a/src/or/microdesc.c b/src/or/microdesc.c
index 788a7b1e16..a48429913a 100644
--- a/src/or/microdesc.c
+++ b/src/or/microdesc.c
@@ -575,6 +575,7 @@ microdesc_free(microdesc_t *md)
 
   if (md->onion_pkey)
     crypto_pk_free(md->onion_pkey);
+  tor_free(md->onion_curve25519_pkey);
   if (md->body && md->saved_location != SAVED_IN_CACHE)
     tor_free(md->body);
 
diff --git a/src/or/nodelist.c b/src/or/nodelist.c
index 4f1e95064d..d71372bcd2 100644
--- a/src/or/nodelist.c
+++ b/src/or/nodelist.c
@@ -916,6 +916,18 @@ node_get_pref_ipv6_orport(const node_t *node, tor_addr_port_t *ap_out)
   }
 }
 
+/** Return true iff <b>node</b> has a curve25519 onion key. */
+int
+node_has_curve25519_onion_key(const node_t *node)
+{
+  if (node->ri)
+    return node->ri->onion_curve25519_pkey != NULL;
+  else if (node->md)
+    return node->md->onion_curve25519_pkey != NULL;
+  else
+    return 0;
+}
+
 /** Refresh the country code of <b>ri</b>.  This function MUST be called on
  * each router when the GeoIP database is reloaded, and on all new routers. */
 void
diff --git a/src/or/nodelist.h b/src/or/nodelist.h
index 13a3847414..39f0948779 100644
--- a/src/or/nodelist.h
+++ b/src/or/nodelist.h
@@ -54,6 +54,7 @@ int node_ipv6_preferred(const node_t *node);
 int node_get_prim_orport(const node_t *node, tor_addr_port_t *ap_out);
 void node_get_pref_orport(const node_t *node, tor_addr_port_t *ap_out);
 void node_get_pref_ipv6_orport(const node_t *node, tor_addr_port_t *ap_out);
+int node_has_curve25519_onion_key(const node_t *node);
 
 smartlist_t *nodelist_get_list(void);
 
diff --git a/src/or/onion.c b/src/or/onion.c
index cce4bdf73c..fc3e621f73 100644
--- a/src/or/onion.c
+++ b/src/or/onion.c
@@ -6,21 +6,26 @@
 
 /**
  * \file onion.c
- * \brief Functions to queue create cells, and handle onionskin
- * parsing and creation.
+ * \brief Functions to queue create cells, wrap the various onionskin types,
+ * and parse and create the CREATE cell and its allies.
  **/
 
 #include "or.h"
 #include "circuitlist.h"
 #include "config.h"
 #include "onion.h"
+#include "onion_fast.h"
+#include "onion_ntor.h"
+#include "onion_tap.h"
+#include "relay.h"
 #include "rephist.h"
+#include "router.h"
 
 /** Type for a linked list of circuits that are waiting for a free CPU worker
  * to process a waiting onion handshake. */
 typedef struct onion_queue_t {
   or_circuit_t *circ;
-  char *onionskin;
+  create_cell_t *onionskin;
   time_t when_added;
   struct onion_queue_t *next;
 } onion_queue_t;
@@ -37,11 +42,13 @@ static onion_queue_t *ol_tail=NULL;
 /** Length of ol_list */
 static int ol_length=0;
 
+/* XXXX Check lengths vs MAX_ONIONSKIN_{CHALLENGE,REPLY}_LEN */
+
 /** Add <b>circ</b> to the end of ol_list and return 0, except
  * if ol_list is too long, in which case do nothing and return -1.
  */
 int
-onion_pending_add(or_circuit_t *circ, char *onionskin)
+onion_pending_add(or_circuit_t *circ, create_cell_t *onionskin)
 {
   onion_queue_t *tmp;
   time_t now = time(NULL);
@@ -98,7 +105,7 @@ onion_pending_add(or_circuit_t *circ, char *onionskin)
  * NULL if the list is empty.
  */
 or_circuit_t *
-onion_next_task(char **onionskin_out)
+onion_next_task(create_cell_t **onionskin_out)
 {
   or_circuit_t *circ;
 
@@ -157,292 +164,843 @@ onion_pending_remove(or_circuit_t *circ)
   tor_free(victim);
 }
 
-/*----------------------------------------------------------------------*/
+/** Remove all circuits from the pending list.  Called from tor_free_all. */
+void
+clear_pending_onions(void)
+{
+  while (ol_list) {
+    onion_queue_t *victim = ol_list;
+    ol_list = victim->next;
+    tor_free(victim->onionskin);
+    tor_free(victim);
+  }
+  ol_list = ol_tail = NULL;
+  ol_length = 0;
+}
+
+/* ============================================================ */
 
-/** Given a router's 128 byte public key,
- * stores the following in onion_skin_out:
- *   - [42 bytes] OAEP padding
- *   - [16 bytes] Symmetric key for encrypting blob past RSA
- *   - [70 bytes] g^x part 1 (inside the RSA)
- *   - [58 bytes] g^x part 2 (symmetrically encrypted)
- *
- * Stores the DH private key into handshake_state_out for later completion
- * of the handshake.
- *
- * The meeting point/cookies and auth are zeroed out for now.
+/** Fill in a server_onion_keys_t object at <b>keys</b> with all of the keys
+ * and other info we might need to do onion handshakes.  (We make a copy of
+ * our keys for each cpuworker to avoid race conditions with the main thread,
+ * and to avoid locking) */
+void
+setup_server_onion_keys(server_onion_keys_t *keys)
+{
+  memset(keys, 0, sizeof(server_onion_keys_t));
+  memcpy(keys->my_identity, router_get_my_id_digest(), DIGEST_LEN);
+  dup_onion_keys(&keys->onion_key, &keys->last_onion_key);
+#ifdef CURVE25519_ENABLED
+  keys->curve25519_key_map = construct_ntor_key_map();
+  keys->junk_keypair = tor_malloc_zero(sizeof(curve25519_keypair_t));
+  curve25519_keypair_generate(keys->junk_keypair, 0);
+#endif
+}
+
+/** Release all storage held in <b>keys</b>, but do not free <b>keys</b>
+ * itself (as it's likely to be stack-allocated.) */
+void
+release_server_onion_keys(server_onion_keys_t *keys)
+{
+  if (! keys)
+    return;
+
+  crypto_pk_free(keys->onion_key);
+  crypto_pk_free(keys->last_onion_key);
+#ifdef CURVE25519_ENABLED
+  ntor_key_map_free(keys->curve25519_key_map);
+  tor_free(keys->junk_keypair);
+#endif
+  memset(keys, 0, sizeof(server_onion_keys_t));
+}
+
+/** Release whatever storage is held in <b>state</b>, depending on its
+ * type, and clear its pointer. */
+void
+onion_handshake_state_release(onion_handshake_state_t *state)
+{
+  switch (state->tag) {
+  case ONION_HANDSHAKE_TYPE_TAP:
+    crypto_dh_free(state->u.tap);
+    state->u.tap = NULL;
+    break;
+  case ONION_HANDSHAKE_TYPE_FAST:
+    fast_handshake_state_free(state->u.fast);
+    state->u.fast = NULL;
+    break;
+#ifdef CURVE25519_ENABLED
+  case ONION_HANDSHAKE_TYPE_NTOR:
+    ntor_handshake_state_free(state->u.ntor);
+    state->u.ntor = NULL;
+    break;
+#endif
+  default:
+    log_warn(LD_BUG, "called with unknown handshake state type %d",
+             (int)state->tag);
+    tor_fragile_assert();
+  }
+}
+
+/** Perform the first step of a circuit-creation handshake of type <b>type</b>
+ * (one of ONION_HANDSHAKE_TYPE_*): generate the initial "onion skin" in
+ * <b>onion_skin_out</b>, and store any state information in <b>state_out</b>.
+ * Return -1 on failure, and the length of the onionskin on acceptance.
  */
 int
-onion_skin_create(crypto_pk_t *dest_router_key,
-                  crypto_dh_t **handshake_state_out,
-                  char *onion_skin_out) /* ONIONSKIN_CHALLENGE_LEN bytes */
+onion_skin_create(int type,
+                  const extend_info_t *node,
+                  onion_handshake_state_t *state_out,
+                  uint8_t *onion_skin_out)
 {
-  char challenge[DH_KEY_LEN];
-  crypto_dh_t *dh = NULL;
-  int dhbytes, pkbytes;
+  int r = -1;
+
+  switch (type) {
+  case ONION_HANDSHAKE_TYPE_TAP:
+    if (!node->onion_key)
+      return -1;
+
+    if (onion_skin_TAP_create(node->onion_key,
+                              &state_out->u.tap,
+                              (char*)onion_skin_out) < 0)
+      return -1;
+
+    r = TAP_ONIONSKIN_CHALLENGE_LEN;
+    break;
+  case ONION_HANDSHAKE_TYPE_FAST:
+    if (fast_onionskin_create(&state_out->u.fast, onion_skin_out) < 0)
+      return -1;
+
+    r = CREATE_FAST_LEN;
+    break;
+  case ONION_HANDSHAKE_TYPE_NTOR:
+#ifdef CURVE25519_ENABLED
+    if (tor_mem_is_zero((const char*)node->curve25519_onion_key.public_key,
+                        CURVE25519_PUBKEY_LEN))
+      return -1;
+    if (onion_skin_ntor_create((const uint8_t*)node->identity_digest,
+                               &node->curve25519_onion_key,
+                               &state_out->u.ntor,
+                               onion_skin_out) < 0)
+      return -1;
+
+    r = NTOR_ONIONSKIN_LEN;
+#else
+    return -1;
+#endif
+    break;
+  default:
+    log_warn(LD_BUG, "called with unknown handshake state type %d", type);
+    tor_fragile_assert();
+    r = -1;
+  }
+
+  if (r > 0)
+    state_out->tag = (uint16_t) type;
+
+  return r;
+}
+
+/** Perform the second (server-side) step of a circuit-creation handshake of
+ * type <b>type</b>, responding to the client request in <b>onion_skin</b>
+ * using the keys in <b>keys</b>.  On success, write our response into
+ * <b>reply_out</b>, generate <b>keys_out_len</b> bytes worth of key material
+ * in <b>keys_out_len</b>, a hidden service nonce to <b>rend_nonce_out</b>,
+ * and return the length of the reply. On failure, return -1.
+ */
+int
+onion_skin_server_handshake(int type,
+                      const uint8_t *onion_skin, size_t onionskin_len,
+                      const server_onion_keys_t *keys,
+                      uint8_t *reply_out,
+                      uint8_t *keys_out, size_t keys_out_len,
+                      uint8_t *rend_nonce_out)
+{
+  int r = -1;
 
-  tor_assert(dest_router_key);
-  tor_assert(handshake_state_out);
-  tor_assert(onion_skin_out);
-  *handshake_state_out = NULL;
-  memset(onion_skin_out, 0, ONIONSKIN_CHALLENGE_LEN);
+  switch (type) {
+  case ONION_HANDSHAKE_TYPE_TAP:
+    if (onionskin_len != TAP_ONIONSKIN_CHALLENGE_LEN)
+      return -1;
+    if (onion_skin_TAP_server_handshake((const char*)onion_skin,
+                                        keys->onion_key, keys->last_onion_key,
+                                        (char*)reply_out,
+                                        (char*)keys_out, keys_out_len)<0)
+      return -1;
+    r = TAP_ONIONSKIN_REPLY_LEN;
+    memcpy(rend_nonce_out, reply_out+DH_KEY_LEN, DIGEST_LEN);
+    break;
+  case ONION_HANDSHAKE_TYPE_FAST:
+    if (onionskin_len != CREATE_FAST_LEN)
+      return -1;
+    if (fast_server_handshake(onion_skin, reply_out, keys_out, keys_out_len)<0)
+      return -1;
+    r = CREATED_FAST_LEN;
+    memcpy(rend_nonce_out, reply_out+DIGEST_LEN, DIGEST_LEN);
+    break;
+  case ONION_HANDSHAKE_TYPE_NTOR:
+#ifdef CURVE25519_ENABLED
+    if (onionskin_len < NTOR_ONIONSKIN_LEN)
+      return -1;
+    {
+      size_t keys_tmp_len = keys_out_len + DIGEST_LEN;
+      uint8_t *keys_tmp = tor_malloc(keys_out_len + DIGEST_LEN);
+
+      if (onion_skin_ntor_server_handshake(
+                                   onion_skin, keys->curve25519_key_map,
+                                   keys->junk_keypair,
+                                   keys->my_identity,
+                                   reply_out, keys_tmp, keys_tmp_len)<0) {
+        tor_free(keys_tmp);
+        return -1;
+      }
+      memcpy(keys_out, keys_tmp, keys_out_len);
+      memcpy(rend_nonce_out, keys_tmp+keys_out_len, DIGEST_LEN);
+      memwipe(keys_tmp, 0, keys_tmp_len);
+      tor_free(keys_tmp);
+      r = NTOR_REPLY_LEN;
+    }
+#else
+    return -1;
+#endif
+    break;
+  default:
+    log_warn(LD_BUG, "called with unknown handshake state type %d", type);
+    tor_fragile_assert();
+    return -1;
+  }
 
-  if (!(dh = crypto_dh_new(DH_TYPE_CIRCUIT)))
-    goto err;
+  return r;
+}
 
-  dhbytes = crypto_dh_get_bytes(dh);
-  pkbytes = (int) crypto_pk_keysize(dest_router_key);
-  tor_assert(dhbytes == 128);
-  tor_assert(pkbytes == 128);
+/** Perform the final (client-side) step of a circuit-creation handshake of
+ * type <b>type</b>, using our state in <b>handshake_state</b> and the
+ * server's response in <b>reply</b> On success, generate <b>keys_out_len</b>
+ * bytes worth of key material in <b>keys_out_len</b>, set
+ * <b>rend_authenticator_out</b> to the "KH" field that can be used to
+ * establish introduction points at this hop, and return 0.  On failure,
+ * return -1. */
+int
+onion_skin_client_handshake(int type,
+                      const onion_handshake_state_t *handshake_state,
+                      const uint8_t *reply, size_t reply_len,
+                      uint8_t *keys_out, size_t keys_out_len,
+                      uint8_t *rend_authenticator_out)
+{
+  if (handshake_state->tag != type)
+    return -1;
 
-  if (crypto_dh_get_public(dh, challenge, dhbytes))
-    goto err;
+  switch (type) {
+  case ONION_HANDSHAKE_TYPE_TAP:
+    if (reply_len != TAP_ONIONSKIN_REPLY_LEN)
+      return -1;
+    if (onion_skin_TAP_client_handshake(handshake_state->u.tap,
+                                        (const char*)reply,
+                                        (char *)keys_out, keys_out_len) < 0)
+      return -1;
 
-  note_crypto_pk_op(ENC_ONIONSKIN);
+    memcpy(rend_authenticator_out, reply+DH_KEY_LEN, DIGEST_LEN);
+
+    return 0;
+  case ONION_HANDSHAKE_TYPE_FAST:
+    if (reply_len != CREATED_FAST_LEN)
+      return -1;
+    if (fast_client_handshake(handshake_state->u.fast, reply,
+                              keys_out, keys_out_len) < 0)
+      return -1;
+
+    memcpy(rend_authenticator_out, reply+DIGEST_LEN, DIGEST_LEN);
+    return 0;
+#ifdef CURVE25519_ENABLED
+  case ONION_HANDSHAKE_TYPE_NTOR:
+    if (reply_len < NTOR_REPLY_LEN)
+      return -1;
+    {
+      size_t keys_tmp_len = keys_out_len + DIGEST_LEN;
+      uint8_t *keys_tmp = tor_malloc(keys_tmp_len);
+      if (onion_skin_ntor_client_handshake(handshake_state->u.ntor,
+                                           reply,
+                                           keys_tmp, keys_tmp_len) < 0) {
+        tor_free(keys_tmp);
+        return -1;
+      }
+      memcpy(keys_out, keys_tmp, keys_out_len);
+      memcpy(rend_authenticator_out, keys_tmp + keys_out_len, DIGEST_LEN);
+      memwipe(keys_tmp, 0, keys_tmp_len);
+      tor_free(keys_tmp);
+    }
+    return 0;
+#endif
+  default:
+    log_warn(LD_BUG, "called with unknown handshake state type %d", type);
+    tor_fragile_assert();
+    return -1;
+  }
+}
 
-  /* set meeting point, meeting cookie, etc here. Leave zero for now. */
-  if (crypto_pk_public_hybrid_encrypt(dest_router_key, onion_skin_out,
-                                      ONIONSKIN_CHALLENGE_LEN,
-                                      challenge, DH_KEY_LEN,
-                                      PK_PKCS1_OAEP_PADDING, 1)<0)
-    goto err;
+/** Helper: return 0 if <b>cell</b> appears valid, -1 otherwise. If
+ * <b>unknown_ok</b> is true, allow cells with handshake types we don't
+ * recognize. */
+static int
+check_create_cell(const create_cell_t *cell, int unknown_ok)
+{
+  switch (cell->cell_type) {
+  case CELL_CREATE:
+    if (cell->handshake_type != ONION_HANDSHAKE_TYPE_TAP &&
+        cell->handshake_type != ONION_HANDSHAKE_TYPE_NTOR)
+      return -1;
+    break;
+  case CELL_CREATE_FAST:
+    if (cell->handshake_type != ONION_HANDSHAKE_TYPE_FAST)
+      return -1;
+    break;
+  case CELL_CREATE2:
+    break;
+  default:
+    return -1;
+  }
 
-  memwipe(challenge, 0, sizeof(challenge));
-  *handshake_state_out = dh;
+  switch (cell->handshake_type) {
+  case ONION_HANDSHAKE_TYPE_TAP:
+    if (cell->handshake_len != TAP_ONIONSKIN_CHALLENGE_LEN)
+      return -1;
+    break;
+  case ONION_HANDSHAKE_TYPE_FAST:
+    if (cell->handshake_len != CREATE_FAST_LEN)
+      return -1;
+    break;
+#ifdef CURVE25519_ENABLED
+  case ONION_HANDSHAKE_TYPE_NTOR:
+    if (cell->handshake_len != NTOR_ONIONSKIN_LEN)
+      return -1;
+    break;
+#endif
+  default:
+    if (! unknown_ok)
+      return -1;
+  }
 
   return 0;
- err:
-  memwipe(challenge, 0, sizeof(challenge));
-  if (dh) crypto_dh_free(dh);
-  return -1;
 }
 
-/** Given an encrypted DH public key as generated by onion_skin_create,
- * and the private key for this onion router, generate the reply (128-byte
- * DH plus the first 20 bytes of shared key material), and store the
- * next key_out_len bytes of key material in key_out.
+/** Helper: parse the CREATE2 payload at <b>p</b>, which could be up to
+ * <b>p_len</b> bytes long, and use it to fill the fields of
+ * <b>cell_out</b>. Return 0 on success and -1 on failure.
+ *
+ * Note that part of the body of an EXTEND2 cell is a CREATE2 payload, so
+ * this function is also used for parsing those.
  */
+static int
+parse_create2_payload(create_cell_t *cell_out, const uint8_t *p, size_t p_len)
+{
+  if (p_len < 4)
+    return -1;
+  cell_out->cell_type = CELL_CREATE2;
+  cell_out->handshake_type = ntohs(get_uint16(p));
+  cell_out->handshake_len = ntohs(get_uint16(p+2));
+  if (cell_out->handshake_len > CELL_PAYLOAD_SIZE - 4 ||
+      cell_out->handshake_len > p_len - 4)
+    return -1;
+  if (cell_out->handshake_type == ONION_HANDSHAKE_TYPE_FAST)
+    return -1;
+  memcpy(cell_out->onionskin, p+4, cell_out->handshake_len);
+  return 0;
+}
+
+/** Magic string which, in a CREATE or EXTEND cell, indicates that a seeming
+ * TAP payload is really an ntor payload.  We'd do away with this if every
+ * relay supported EXTEND2, but we want to be able to extend from A to B with
+ * ntor even when A doesn't understand EXTEND2 and so can't generate a
+ * CREATE2 cell.
+ **/
+#define NTOR_CREATE_MAGIC "ntorNTORntorNTOR"
+
+/** Parse a CREATE, CREATE_FAST, or CREATE2 cell from <b>cell_in</b> into
+ * <b>cell_out</b>. Return 0 on success, -1 on failure. (We reject some
+ * syntactically valid CREATE2 cells that we can't generate or react to.) */
 int
-onion_skin_server_handshake(const char *onion_skin, /*ONIONSKIN_CHALLENGE_LEN*/
-                            crypto_pk_t *private_key,
-                            crypto_pk_t *prev_private_key,
-                            char *handshake_reply_out, /*ONIONSKIN_REPLY_LEN*/
-                            char *key_out,
-                            size_t key_out_len)
+create_cell_parse(create_cell_t *cell_out, const cell_t *cell_in)
 {
-  char challenge[ONIONSKIN_CHALLENGE_LEN];
-  crypto_dh_t *dh = NULL;
-  ssize_t len;
-  char *key_material=NULL;
-  size_t key_material_len=0;
-  int i;
-  crypto_pk_t *k;
-
-  len = -1;
-  for (i=0;i<2;++i) {
-    k = i==0?private_key:prev_private_key;
-    if (!k)
-      break;
-    note_crypto_pk_op(DEC_ONIONSKIN);
-    len = crypto_pk_private_hybrid_decrypt(k, challenge,
-                                           ONIONSKIN_CHALLENGE_LEN,
-                                           onion_skin, ONIONSKIN_CHALLENGE_LEN,
-                                           PK_PKCS1_OAEP_PADDING,0);
-    if (len>0)
-      break;
-  }
-  if (len<0) {
-    log_info(LD_PROTOCOL,
-             "Couldn't decrypt onionskin: client may be using old onion key");
-    goto err;
-  } else if (len != DH_KEY_LEN) {
-    log_warn(LD_PROTOCOL, "Unexpected onionskin length after decryption: %ld",
-             (long)len);
-    goto err;
+  memset(cell_out, 0, sizeof(*cell_out));
+
+  switch (cell_in->command) {
+  case CELL_CREATE:
+    cell_out->cell_type = CELL_CREATE;
+    if (tor_memeq(cell_in->payload, NTOR_CREATE_MAGIC, 16)) {
+      cell_out->handshake_type = ONION_HANDSHAKE_TYPE_NTOR;
+      cell_out->handshake_len = NTOR_ONIONSKIN_LEN;
+      memcpy(cell_out->onionskin, cell_in->payload+16, NTOR_ONIONSKIN_LEN);
+    } else {
+      cell_out->handshake_type = ONION_HANDSHAKE_TYPE_TAP;
+      cell_out->handshake_len = TAP_ONIONSKIN_CHALLENGE_LEN;
+      memcpy(cell_out->onionskin, cell_in->payload,
+             TAP_ONIONSKIN_CHALLENGE_LEN);
+    }
+    break;
+  case CELL_CREATE_FAST:
+    cell_out->cell_type = CELL_CREATE_FAST;
+    cell_out->handshake_type = ONION_HANDSHAKE_TYPE_FAST;
+    cell_out->handshake_len = CREATE_FAST_LEN;
+    memcpy(cell_out->onionskin, cell_in->payload, CREATE_FAST_LEN);
+    break;
+  case CELL_CREATE2:
+    if (parse_create2_payload(cell_out, cell_in->payload,
+                              CELL_PAYLOAD_SIZE) < 0)
+      return -1;
+    break;
+  default:
+    return -1;
   }
 
-  dh = crypto_dh_new(DH_TYPE_CIRCUIT);
-  if (!dh) {
-    log_warn(LD_BUG, "Couldn't allocate DH key");
-    goto err;
+  return check_create_cell(cell_out, 0);
+}
+
+/** Helper: return 0 if <b>cell</b> appears valid, -1 otherwise. */
+static int
+check_created_cell(const created_cell_t *cell)
+{
+  switch (cell->cell_type) {
+  case CELL_CREATED:
+    if (cell->handshake_len != TAP_ONIONSKIN_REPLY_LEN)
+      return -1;
+    break;
+  case CELL_CREATED_FAST:
+    if (cell->handshake_len != CREATED_FAST_LEN)
+      return -1;
+    break;
+  case CELL_CREATED2:
+    if (cell->handshake_len > RELAY_PAYLOAD_SIZE-2)
+      return -1;
+    break;
   }
-  if (crypto_dh_get_public(dh, handshake_reply_out, DH_KEY_LEN)) {
-    log_info(LD_GENERAL, "crypto_dh_get_public failed.");
-    goto err;
+
+  return 0;
+}
+
+/** Parse a CREATED, CREATED_FAST, or CREATED2 cell from <b>cell_in</b> into
+ * <b>cell_out</b>. Return 0 on success, -1 on failure. */
+int
+created_cell_parse(created_cell_t *cell_out, const cell_t *cell_in)
+{
+  memset(cell_out, 0, sizeof(*cell_out));
+
+  switch (cell_in->command) {
+  case CELL_CREATED:
+    cell_out->cell_type = CELL_CREATED;
+    cell_out->handshake_len = TAP_ONIONSKIN_REPLY_LEN;
+    memcpy(cell_out->reply, cell_in->payload, TAP_ONIONSKIN_REPLY_LEN);
+    break;
+  case CELL_CREATED_FAST:
+    cell_out->cell_type = CELL_CREATED_FAST;
+    cell_out->handshake_len = CREATED_FAST_LEN;
+    memcpy(cell_out->reply, cell_in->payload, CREATED_FAST_LEN);
+    break;
+  case CELL_CREATED2:
+    {
+      const uint8_t *p = cell_in->payload;
+      cell_out->cell_type = CELL_CREATED2;
+      cell_out->handshake_len = ntohs(get_uint16(p));
+      if (cell_out->handshake_len > CELL_PAYLOAD_SIZE - 2)
+        return -1;
+      memcpy(cell_out->reply, p+2, cell_out->handshake_len);
+      break;
+    }
   }
 
-  key_material_len = DIGEST_LEN+key_out_len;
-  key_material = tor_malloc(key_material_len);
-  len = crypto_dh_compute_secret(LOG_PROTOCOL_WARN, dh, challenge,
-                                 DH_KEY_LEN, key_material,
-                                 key_material_len);
-  if (len < 0) {
-    log_info(LD_GENERAL, "crypto_dh_compute_secret failed.");
-    goto err;
+  return check_created_cell(cell_out);
+}
+
+/** Helper: return 0 if <b>cell</b> appears valid, -1 otherwise. */
+static int
+check_extend_cell(const extend_cell_t *cell)
+{
+  if (tor_digest_is_zero((const char*)cell->node_id))
+    return -1;
+  /* We don't currently allow EXTEND2 cells without an IPv4 address */
+  if (tor_addr_family(&cell->orport_ipv4.addr) == AF_UNSPEC)
+    return -1;
+  if (cell->create_cell.cell_type == CELL_CREATE) {
+    if (cell->cell_type != RELAY_COMMAND_EXTEND)
+      return -1;
+  } else if (cell->create_cell.cell_type == CELL_CREATE2) {
+    if (cell->cell_type != RELAY_COMMAND_EXTEND2 &&
+        cell->cell_type != RELAY_COMMAND_EXTEND)
+      return -1;
+  } else {
+    /* In particular, no CREATE_FAST cells are allowed */
+    return -1;
   }
+  if (cell->create_cell.handshake_type == ONION_HANDSHAKE_TYPE_FAST)
+    return -1;
 
-  /* send back H(K|0) as proof that we learned K. */
-  memcpy(handshake_reply_out+DH_KEY_LEN, key_material, DIGEST_LEN);
+  return check_create_cell(&cell->create_cell, 1);
+}
 
-  /* use the rest of the key material for our shared keys, digests, etc */
-  memcpy(key_out, key_material+DIGEST_LEN, key_out_len);
+/** Protocol constants for specifier types in EXTEND2
+ * @{
+ */
+#define SPECTYPE_IPV4 0
+#define SPECTYPE_IPV6 1
+#define SPECTYPE_LEGACY_ID 2
+/** @} */
+
+/** Parse an EXTEND or EXTEND2 cell (according to <b>command</b>) from the
+ * <b>payload_length</b> bytes of <b>payload</b> into <b>cell_out</b>. Return
+ * 0 on success, -1 on failure. */
+int
+extend_cell_parse(extend_cell_t *cell_out, const uint8_t command,
+                  const uint8_t *payload, size_t payload_length)
+{
+  const uint8_t *eop;
 
-  memwipe(challenge, 0, sizeof(challenge));
-  memwipe(key_material, 0, key_material_len);
-  tor_free(key_material);
-  crypto_dh_free(dh);
-  return 0;
- err:
-  memwipe(challenge, 0, sizeof(challenge));
-  if (key_material) {
-    memwipe(key_material, 0, key_material_len);
-    tor_free(key_material);
+  memset(cell_out, 0, sizeof(*cell_out));
+  if (payload_length > RELAY_PAYLOAD_SIZE)
+    return -1;
+  eop = payload + payload_length;
+
+  switch (command) {
+  case RELAY_COMMAND_EXTEND:
+    {
+      if (payload_length != 6 + TAP_ONIONSKIN_CHALLENGE_LEN + DIGEST_LEN)
+        return -1;
+
+      cell_out->cell_type = RELAY_COMMAND_EXTEND;
+      tor_addr_from_ipv4n(&cell_out->orport_ipv4.addr, get_uint32(payload));
+      cell_out->orport_ipv4.port = ntohs(get_uint16(payload+4));
+      tor_addr_make_unspec(&cell_out->orport_ipv6.addr);
+      if (tor_memeq(payload + 6, NTOR_CREATE_MAGIC, 16)) {
+        cell_out->create_cell.cell_type = CELL_CREATE2;
+        cell_out->create_cell.handshake_type = ONION_HANDSHAKE_TYPE_NTOR;
+        cell_out->create_cell.handshake_len = NTOR_ONIONSKIN_LEN;
+        memcpy(cell_out->create_cell.onionskin, payload + 22,
+               NTOR_ONIONSKIN_LEN);
+      } else {
+        cell_out->create_cell.cell_type = CELL_CREATE;
+        cell_out->create_cell.handshake_type = ONION_HANDSHAKE_TYPE_TAP;
+        cell_out->create_cell.handshake_len = TAP_ONIONSKIN_CHALLENGE_LEN;
+        memcpy(cell_out->create_cell.onionskin, payload + 6,
+               TAP_ONIONSKIN_CHALLENGE_LEN);
+      }
+      memcpy(cell_out->node_id, payload + 6 + TAP_ONIONSKIN_CHALLENGE_LEN,
+             DIGEST_LEN);
+      break;
+    }
+  case RELAY_COMMAND_EXTEND2:
+    {
+      uint8_t n_specs = *payload, spectype, speclen;
+      int i;
+      int found_ipv4 = 0, found_ipv6 = 0, found_id = 0;
+      tor_addr_make_unspec(&cell_out->orport_ipv4.addr);
+      tor_addr_make_unspec(&cell_out->orport_ipv6.addr);
+
+      cell_out->cell_type = RELAY_COMMAND_EXTEND2;
+      ++payload;
+      /* Parse the specifiers. We'll only take the first IPv4 and first IPv6
+       * addres, and the node ID, and ignore everything else */
+      for (i = 0; i < n_specs; ++i) {
+        if (eop - payload < 2)
+          return -1;
+        spectype = payload[0];
+        speclen = payload[1];
+        payload += 2;
+        if (eop - payload < speclen)
+          return -1;
+        switch (spectype) {
+        case SPECTYPE_IPV4:
+          if (speclen != 6)
+            return -1;
+          if (!found_ipv4) {
+            tor_addr_from_ipv4n(&cell_out->orport_ipv4.addr,
+                                get_uint32(payload));
+            cell_out->orport_ipv4.port = ntohs(get_uint16(payload+4));
+            found_ipv4 = 1;
+          }
+          break;
+        case SPECTYPE_IPV6:
+          if (speclen != 18)
+            return -1;
+          if (!found_ipv6) {
+            tor_addr_from_ipv6_bytes(&cell_out->orport_ipv6.addr,
+                                     (const char*)payload);
+            cell_out->orport_ipv6.port = ntohs(get_uint16(payload+16));
+            found_ipv6 = 1;
+          }
+          break;
+        case SPECTYPE_LEGACY_ID:
+          if (speclen != 20)
+            return -1;
+          if (found_id)
+            return -1;
+          memcpy(cell_out->node_id, payload, 20);
+          found_id = 1;
+          break;
+        }
+        payload += speclen;
+      }
+      if (!found_id || !found_ipv4)
+        return -1;
+      if (parse_create2_payload(&cell_out->create_cell,payload,eop-payload)<0)
+        return -1;
+      break;
+    }
+  default:
+    return -1;
   }
-  if (dh) crypto_dh_free(dh);
 
-  return -1;
+  return check_extend_cell(cell_out);
 }
 
-/** Finish the client side of the DH handshake.
- * Given the 128 byte DH reply + 20 byte hash as generated by
- * onion_skin_server_handshake and the handshake state generated by
- * onion_skin_create, verify H(K) with the first 20 bytes of shared
- * key material, then generate key_out_len more bytes of shared key
- * material and store them in key_out.
- *
- * After the invocation, call crypto_dh_free on handshake_state.
- */
+/** Helper: return 0 if <b>cell</b> appears valid, -1 otherwise. */
+static int
+check_extended_cell(const extended_cell_t *cell)
+{
+  if (cell->created_cell.cell_type == CELL_CREATED) {
+    if (cell->cell_type != RELAY_COMMAND_EXTENDED)
+      return -1;
+  } else if (cell->created_cell.cell_type == CELL_CREATED2) {
+    if (cell->cell_type != RELAY_COMMAND_EXTENDED2)
+      return -1;
+  } else {
+    return -1;
+  }
+
+  return check_created_cell(&cell->created_cell);
+}
+
+/** Parse an EXTENDED or EXTENDED2 cell (according to <b>command</b>) from the
+ * <b>payload_length</b> bytes of <b>payload</b> into <b>cell_out</b>. Return
+ * 0 on success, -1 on failure. */
 int
-onion_skin_client_handshake(crypto_dh_t *handshake_state,
-            const char *handshake_reply, /* ONIONSKIN_REPLY_LEN bytes */
-            char *key_out,
-            size_t key_out_len)
+extended_cell_parse(extended_cell_t *cell_out,
+                    const uint8_t command, const uint8_t *payload,
+                    size_t payload_len)
 {
-  ssize_t len;
-  char *key_material=NULL;
-  size_t key_material_len;
-  tor_assert(crypto_dh_get_bytes(handshake_state) == DH_KEY_LEN);
-
-  key_material_len = DIGEST_LEN + key_out_len;
-  key_material = tor_malloc(key_material_len);
-  len = crypto_dh_compute_secret(LOG_PROTOCOL_WARN, handshake_state,
-                                 handshake_reply, DH_KEY_LEN, key_material,
-                                 key_material_len);
-  if (len < 0)
-    goto err;
-
-  if (tor_memneq(key_material, handshake_reply+DH_KEY_LEN, DIGEST_LEN)) {
-    /* H(K) does *not* match. Something fishy. */
-    log_warn(LD_PROTOCOL,"Digest DOES NOT MATCH on onion handshake. "
-             "Bug or attack.");
-    goto err;
+  memset(cell_out, 0, sizeof(*cell_out));
+  if (payload_len > RELAY_PAYLOAD_SIZE)
+    return -1;
+
+  switch (command) {
+  case RELAY_COMMAND_EXTENDED:
+    if (payload_len != TAP_ONIONSKIN_REPLY_LEN)
+      return -1;
+    cell_out->cell_type = RELAY_COMMAND_EXTENDED;
+    cell_out->created_cell.cell_type = CELL_CREATED;
+    cell_out->created_cell.handshake_len = TAP_ONIONSKIN_REPLY_LEN;
+    memcpy(cell_out->created_cell.reply, payload, TAP_ONIONSKIN_REPLY_LEN);
+    break;
+  case RELAY_COMMAND_EXTENDED2:
+    {
+      cell_out->cell_type = RELAY_COMMAND_EXTENDED2;
+      cell_out->created_cell.cell_type = CELL_CREATED2;
+      cell_out->created_cell.handshake_len = ntohs(get_uint16(payload));
+      if (cell_out->created_cell.handshake_len > RELAY_PAYLOAD_SIZE - 2 ||
+          cell_out->created_cell.handshake_len > payload_len - 2)
+        return -1;
+      memcpy(cell_out->created_cell.reply, payload+2,
+             cell_out->created_cell.handshake_len);
+    }
+    break;
+  default:
+    return -1;
   }
 
-  /* use the rest of the key material for our shared keys, digests, etc */
-  memcpy(key_out, key_material+DIGEST_LEN, key_out_len);
+  return check_extended_cell(cell_out);
+}
+
+/** Fill <b>cell_out</b> with a correctly formatted version of the
+ * CREATE{,_FAST,2} cell in <b>cell_in</b>. Return 0 on success, -1 on
+ * failure.  This is a cell we didn't originate if <b>relayed</b> is true. */
+static int
+create_cell_format_impl(cell_t *cell_out, const create_cell_t *cell_in,
+                        int relayed)
+{
+  uint8_t *p;
+  size_t space;
+  if (check_create_cell(cell_in, relayed) < 0)
+    return -1;
+
+  memset(cell_out->payload, 0, sizeof(cell_out->payload));
+  cell_out->command = cell_in->cell_type;
+
+  p = cell_out->payload;
+  space = sizeof(cell_out->payload);
+
+  switch (cell_in->cell_type) {
+  case CELL_CREATE:
+    if (cell_in->handshake_type == ONION_HANDSHAKE_TYPE_NTOR) {
+      memcpy(p, NTOR_CREATE_MAGIC, 16);
+      p += 16;
+      space -= 16;
+    }
+    /* Fall through */
+  case CELL_CREATE_FAST:
+    tor_assert(cell_in->handshake_len <= space);
+    memcpy(p, cell_in->onionskin, cell_in->handshake_len);
+    break;
+  case CELL_CREATE2:
+    tor_assert(cell_in->handshake_len <= sizeof(cell_out->payload)-4);
+    set_uint16(cell_out->payload, htons(cell_in->handshake_type));
+    set_uint16(cell_out->payload+2, htons(cell_in->handshake_len));
+    memcpy(cell_out->payload + 4, cell_in->onionskin, cell_in->handshake_len);
+    break;
+  default:
+    return -1;
+  }
 
-  memwipe(key_material, 0, key_material_len);
-  tor_free(key_material);
   return 0;
- err:
-  memwipe(key_material, 0, key_material_len);
-  tor_free(key_material);
-  return -1;
 }
 
-/** Implement the server side of the CREATE_FAST abbreviated handshake.  The
- * client has provided DIGEST_LEN key bytes in <b>key_in</b> ("x").  We
- * generate a reply of DIGEST_LEN*2 bytes in <b>key_out</b>, consisting of a
- * new random "y", followed by H(x|y) to check for correctness.  We set
- * <b>key_out_len</b> bytes of key material in <b>key_out</b>.
- * Return 0 on success, &lt;0 on failure.
- **/
 int
-fast_server_handshake(const uint8_t *key_in, /* DIGEST_LEN bytes */
-                      uint8_t *handshake_reply_out, /* DIGEST_LEN*2 bytes */
-                      uint8_t *key_out,
-                      size_t key_out_len)
+create_cell_format(cell_t *cell_out, const create_cell_t *cell_in)
 {
-  char tmp[DIGEST_LEN+DIGEST_LEN];
-  char *out = NULL;
-  size_t out_len;
-  int r = -1;
+  return create_cell_format_impl(cell_out, cell_in, 0);
+}
 
-  if (crypto_rand((char*)handshake_reply_out, DIGEST_LEN)<0)
+int
+create_cell_format_relayed(cell_t *cell_out, const create_cell_t *cell_in)
+{
+  return create_cell_format_impl(cell_out, cell_in, 1);
+}
+
+/** Fill <b>cell_out</b> with a correctly formatted version of the
+ * CREATED{,_FAST,2} cell in <b>cell_in</b>. Return 0 on success, -1 on
+ * failure. */
+int
+created_cell_format(cell_t *cell_out, const created_cell_t *cell_in)
+{
+  if (check_created_cell(cell_in) < 0)
     return -1;
 
-  memcpy(tmp, key_in, DIGEST_LEN);
-  memcpy(tmp+DIGEST_LEN, handshake_reply_out, DIGEST_LEN);
-  out_len = key_out_len+DIGEST_LEN;
-  out = tor_malloc(out_len);
-  if (crypto_expand_key_material(tmp, sizeof(tmp), out, out_len)) {
-    goto done;
+  memset(cell_out->payload, 0, sizeof(cell_out->payload));
+  cell_out->command = cell_in->cell_type;
+
+  switch (cell_in->cell_type) {
+  case CELL_CREATED:
+  case CELL_CREATED_FAST:
+    tor_assert(cell_in->handshake_len <= sizeof(cell_out->payload));
+    memcpy(cell_out->payload, cell_in->reply, cell_in->handshake_len);
+    break;
+  case CELL_CREATED2:
+    tor_assert(cell_in->handshake_len <= sizeof(cell_out->payload)-2);
+    set_uint16(cell_out->payload, htons(cell_in->handshake_len));
+    memcpy(cell_out->payload + 2, cell_in->reply, cell_in->handshake_len);
+    break;
+  default:
+    return -1;
   }
-  memcpy(handshake_reply_out+DIGEST_LEN, out, DIGEST_LEN);
-  memcpy(key_out, out+DIGEST_LEN, key_out_len);
-  r = 0;
- done:
-  memwipe(tmp, 0, sizeof(tmp));
-  memwipe(out, 0, out_len);
-  tor_free(out);
-  return r;
+  return 0;
 }
 
-/** Implement the second half of the client side of the CREATE_FAST handshake.
- * We sent the server <b>handshake_state</b> ("x") already, and the server
- * told us <b>handshake_reply_out</b> (y|H(x|y)).  Make sure that the hash is
- * correct, and generate key material in <b>key_out</b>.  Return 0 on success,
- * true on failure.
- *
- * NOTE: The "CREATE_FAST" handshake path is distinguishable from regular
- * "onionskin" handshakes, and is not secure if an adversary can see or modify
- * the messages.  Therefore, it should only be used by clients, and only as
- * the first hop of a circuit (since the first hop is already authenticated
- * and protected by TLS).
- */
+/** Format the EXTEND{,2} cell in <b>cell_in</b>, storing its relay payload in
+ * <b>payload_out</b>, the number of bytes used in *<b>len_out</b>, and the
+ * relay command in *<b>command_out</b>. The <b>payload_out</b> must have
+ * RELAY_PAYLOAD_SIZE bytes available.  Return 0 on success, -1 on failure. */
 int
-fast_client_handshake(const uint8_t *handshake_state,/*DIGEST_LEN bytes*/
-                      const uint8_t *handshake_reply_out,/*DIGEST_LEN*2 bytes*/
-                      uint8_t *key_out,
-                      size_t key_out_len)
+extend_cell_format(uint8_t *command_out, uint16_t *len_out,
+                   uint8_t *payload_out, const extend_cell_t *cell_in)
 {
-  char tmp[DIGEST_LEN+DIGEST_LEN];
-  char *out;
-  size_t out_len;
-  int r = -1;
+  uint8_t *p, *eop;
+  if (check_extend_cell(cell_in) < 0)
+    return -1;
 
-  memcpy(tmp, handshake_state, DIGEST_LEN);
-  memcpy(tmp+DIGEST_LEN, handshake_reply_out, DIGEST_LEN);
-  out_len = key_out_len+DIGEST_LEN;
-  out = tor_malloc(out_len);
-  if (crypto_expand_key_material(tmp, sizeof(tmp), out, out_len)) {
-    goto done;
-  }
-  if (tor_memneq(out, handshake_reply_out+DIGEST_LEN, DIGEST_LEN)) {
-    /* H(K) does *not* match. Something fishy. */
-    log_warn(LD_PROTOCOL,"Digest DOES NOT MATCH on fast handshake. "
-             "Bug or attack.");
-    goto done;
+  p = payload_out;
+  eop = payload_out + RELAY_PAYLOAD_SIZE;
+
+  memset(p, 0, RELAY_PAYLOAD_SIZE);
+
+  switch (cell_in->cell_type) {
+  case RELAY_COMMAND_EXTEND:
+    {
+      *command_out = RELAY_COMMAND_EXTEND;
+      *len_out = 6 + TAP_ONIONSKIN_CHALLENGE_LEN + DIGEST_LEN;
+      set_uint32(p, tor_addr_to_ipv4n(&cell_in->orport_ipv4.addr));
+      set_uint16(p+4, ntohs(cell_in->orport_ipv4.port));
+      if (cell_in->create_cell.handshake_type == ONION_HANDSHAKE_TYPE_NTOR) {
+        memcpy(p+6, NTOR_CREATE_MAGIC, 16);
+        memcpy(p+22, cell_in->create_cell.onionskin, NTOR_ONIONSKIN_LEN);
+      } else {
+        memcpy(p+6, cell_in->create_cell.onionskin,
+               TAP_ONIONSKIN_CHALLENGE_LEN);
+      }
+      memcpy(p+6+TAP_ONIONSKIN_CHALLENGE_LEN, cell_in->node_id, DIGEST_LEN);
+    }
+    break;
+  case RELAY_COMMAND_EXTEND2:
+    {
+      uint8_t n = 2;
+      *command_out = RELAY_COMMAND_EXTEND2;
+
+      *p++ = n; /* 2 identifiers */
+      *p++ = SPECTYPE_IPV4; /* First is IPV4. */
+      *p++ = 6; /* It's 6 bytes long. */
+      set_uint32(p, tor_addr_to_ipv4n(&cell_in->orport_ipv4.addr));
+      set_uint16(p+4, htons(cell_in->orport_ipv4.port));
+      p += 6;
+      *p++ = SPECTYPE_LEGACY_ID; /* Next is an identity digest. */
+      *p++ = 20; /* It's 20 bytes long */
+      memcpy(p, cell_in->node_id, DIGEST_LEN);
+      p += 20;
+
+      /* Now we can send the handshake */
+      set_uint16(p, htons(cell_in->create_cell.handshake_type));
+      set_uint16(p+2, htons(cell_in->create_cell.handshake_len));
+      p += 4;
+
+      if (cell_in->create_cell.handshake_len > eop - p)
+        return -1;
+
+      memcpy(p, cell_in->create_cell.onionskin,
+             cell_in->create_cell.handshake_len);
+
+      p += cell_in->create_cell.handshake_len;
+      *len_out = p - payload_out;
+    }
+    break;
+  default:
+    return -1;
   }
-  memcpy(key_out, out+DIGEST_LEN, key_out_len);
-  r = 0;
- done:
-  memwipe(tmp, 0, sizeof(tmp));
-  memwipe(out, 0, out_len);
-  tor_free(out);
-  return r;
+
+  return 0;
 }
 
-/** Remove all circuits from the pending list.  Called from tor_free_all. */
-void
-clear_pending_onions(void)
+/** Format the EXTENDED{,2} cell in <b>cell_in</b>, storing its relay payload
+ * in <b>payload_out</b>, the number of bytes used in *<b>len_out</b>, and the
+ * relay command in *<b>command_out</b>. The <b>payload_out</b> must have
+ * RELAY_PAYLOAD_SIZE bytes available.  Return 0 on success, -1 on failure. */
+int
+extended_cell_format(uint8_t *command_out, uint16_t *len_out,
+                     uint8_t *payload_out, const extended_cell_t *cell_in)
 {
-  while (ol_list) {
-    onion_queue_t *victim = ol_list;
-    ol_list = victim->next;
-    tor_free(victim->onionskin);
-    tor_free(victim);
+  uint8_t *p;
+  if (check_extended_cell(cell_in) < 0)
+    return -1;
+
+  p = payload_out;
+  memset(p, 0, RELAY_PAYLOAD_SIZE);
+
+  switch (cell_in->cell_type) {
+  case RELAY_COMMAND_EXTENDED:
+    {
+      *command_out = RELAY_COMMAND_EXTENDED;
+      *len_out = TAP_ONIONSKIN_REPLY_LEN;
+      memcpy(payload_out, cell_in->created_cell.reply,
+             TAP_ONIONSKIN_REPLY_LEN);
+    }
+    break;
+  case RELAY_COMMAND_EXTENDED2:
+    {
+      *command_out = RELAY_COMMAND_EXTENDED2;
+      *len_out = 2 + cell_in->created_cell.handshake_len;
+      set_uint16(payload_out, htons(cell_in->created_cell.handshake_len));
+      if (2+cell_in->created_cell.handshake_len > RELAY_PAYLOAD_SIZE)
+        return -1;
+      memcpy(payload_out+2, cell_in->created_cell.reply,
+             cell_in->created_cell.handshake_len);
+    }
+    break;
+  default:
+    return -1;
   }
-  ol_list = ol_tail = NULL;
-  ol_length = 0;
+
+  return 0;
 }
 
diff --git a/src/or/onion.h b/src/or/onion.h
index e7626f9709..33bf341bbc 100644
--- a/src/or/onion.h
+++ b/src/or/onion.h
@@ -12,37 +12,107 @@
 #ifndef TOR_ONION_H
 #define TOR_ONION_H
 
-int onion_pending_add(or_circuit_t *circ, char *onionskin);
-or_circuit_t *onion_next_task(char **onionskin_out);
+struct create_cell_t;
+int onion_pending_add(or_circuit_t *circ, struct create_cell_t *onionskin);
+or_circuit_t *onion_next_task(struct create_cell_t **onionskin_out);
 void onion_pending_remove(or_circuit_t *circ);
+void clear_pending_onions(void);
+
+typedef struct server_onion_keys_t {
+  uint8_t my_identity[DIGEST_LEN];
+  crypto_pk_t *onion_key;
+  crypto_pk_t *last_onion_key;
+#ifdef CURVE25519_ENABLED
+  di_digest256_map_t *curve25519_key_map;
+  curve25519_keypair_t *junk_keypair;
+#endif
+} server_onion_keys_t;
 
-int onion_skin_create(crypto_pk_t *router_key,
-                      crypto_dh_t **handshake_state_out,
-                      char *onion_skin_out);
+#define MAX_ONIONSKIN_CHALLENGE_LEN 255
+#define MAX_ONIONSKIN_REPLY_LEN 255
 
-int onion_skin_server_handshake(const char *onion_skin,
-                                crypto_pk_t *private_key,
-                                crypto_pk_t *prev_private_key,
-                                char *handshake_reply_out,
-                                char *key_out,
-                                size_t key_out_len);
+void setup_server_onion_keys(server_onion_keys_t *keys);
+void release_server_onion_keys(server_onion_keys_t *keys);
 
-int onion_skin_client_handshake(crypto_dh_t *handshake_state,
-                                const char *handshake_reply,
-                                char *key_out,
-                                size_t key_out_len);
+void onion_handshake_state_release(onion_handshake_state_t *state);
 
-int fast_server_handshake(const uint8_t *key_in,
-                          uint8_t *handshake_reply_out,
-                          uint8_t *key_out,
-                          size_t key_out_len);
+int onion_skin_create(int type,
+                      const extend_info_t *node,
+                      onion_handshake_state_t *state_out,
+                      uint8_t *onion_skin_out);
+int onion_skin_server_handshake(int type,
+                      const uint8_t *onion_skin, size_t onionskin_len,
+                      const server_onion_keys_t *keys,
+                      uint8_t *reply_out,
+                      uint8_t *keys_out, size_t key_out_len,
+                      uint8_t *rend_nonce_out);
+int onion_skin_client_handshake(int type,
+                      const onion_handshake_state_t *handshake_state,
+                      const uint8_t *reply, size_t reply_len,
+                      uint8_t *keys_out, size_t key_out_len,
+                      uint8_t *rend_authenticator_out);
 
-int fast_client_handshake(const uint8_t *handshake_state,
-                          const uint8_t *handshake_reply_out,
-                          uint8_t *key_out,
-                          size_t key_out_len);
+/** A parsed CREATE, CREATE_FAST, or CREATE2 cell. */
+typedef struct create_cell_t {
+  /** The cell command. One of CREATE{,_FAST,2} */
+  uint8_t cell_type;
+  /** One of the ONION_HANDSHAKE_TYPE_* values */
+  uint16_t handshake_type;
+  /** The number of bytes used in <b>onionskin</b>. */
+  uint16_t handshake_len;
+  /** The client-side message for the circuit creation handshake. */
+  uint8_t onionskin[CELL_PAYLOAD_SIZE - 4];
+} create_cell_t;
 
-void clear_pending_onions(void);
+/** A parsed CREATED, CREATED_FAST, or CREATED2 cell. */
+typedef struct created_cell_t {
+  /** The cell command. One of CREATED{,_FAST,2} */
+  uint8_t cell_type;
+  /** The number of bytes used in <b>reply</b>. */
+  uint16_t handshake_len;
+  /** The server-side message for the circuit creation handshake. */
+  uint8_t reply[CELL_PAYLOAD_SIZE - 2];
+} created_cell_t;
+
+/** A parsed RELAY_EXTEND or RELAY_EXTEND2 cell */
+typedef struct extend_cell_t {
+  /** One of RELAY_EXTEND or RELAY_EXTEND2 */
+  uint8_t cell_type;
+  /** An IPv4 address and port for the node we're connecting to. */
+  tor_addr_port_t orport_ipv4;
+  /** An IPv6 address and port for the node we're connecting to. Not currently
+   * used. */
+  tor_addr_port_t orport_ipv6;
+  /** Identity fingerprint of the node we're conecting to.*/
+  uint8_t node_id[DIGEST_LEN];
+  /** The "create cell" embedded in this extend cell. Note that unlike the
+   * create cells we generate ourself, this once can have a handshake type we
+   * don't recognize. */
+  create_cell_t create_cell;
+} extend_cell_t;
+
+/** A parsed RELAY_EXTEND or RELAY_EXTEND2 cell */
+typedef struct extended_cell_t {
+  /** One of RELAY_EXTENDED or RELAY_EXTENDED2. */
+  uint8_t cell_type;
+  /** The "created cell" embedded in this extended cell. */
+  created_cell_t created_cell;
+} extended_cell_t;
+
+int create_cell_parse(create_cell_t *cell_out, const cell_t *cell_in);
+int created_cell_parse(created_cell_t *cell_out, const cell_t *cell_in);
+int extend_cell_parse(extend_cell_t *cell_out, uint8_t command,
+                      const uint8_t *payload_in, size_t payload_len);
+int extended_cell_parse(extended_cell_t *cell_out, uint8_t command,
+                        const uint8_t *payload_in, size_t payload_len);
+
+int create_cell_format(cell_t *cell_out, const create_cell_t *cell_in);
+int create_cell_format_relayed(cell_t *cell_out, const create_cell_t *cell_in);
+int created_cell_format(cell_t *cell_out, const created_cell_t *cell_in);
+int extend_cell_format(uint8_t *command_out, uint16_t *len_out,
+                       uint8_t *payload_out, const extend_cell_t *cell_in);
+int extended_cell_format(uint8_t *command_out, uint16_t *len_out,
+                         uint8_t *payload_out, const extended_cell_t *cell_in);
 
 #endif
 
diff --git a/src/or/onion_fast.c b/src/or/onion_fast.c
new file mode 100644
index 0000000000..c1a05233e0
--- /dev/null
+++ b/src/or/onion_fast.c
@@ -0,0 +1,123 @@
+/* Copyright (c) 2001 Matej Pfajfar.
+ * Copyright (c) 2001-2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2012, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file onion_fast.c
+ * \brief Functions implement the CREATE_FAST circuit handshake.
+ **/
+
+#include "or.h"
+#include "onion_fast.h"
+
+/** Release all state held in <b>victim</b>. */
+void
+fast_handshake_state_free(fast_handshake_state_t *victim)
+{
+  if (! victim)
+    return;
+  memwipe(victim, 0, sizeof(fast_handshake_state_t));
+  tor_free(victim);
+}
+
+/** Create the state needed to perform a CREATE_FAST hasnshake. Return 0
+ * on success, -1 on failure. */
+int
+fast_onionskin_create(fast_handshake_state_t **handshake_state_out,
+                      uint8_t *handshake_out)
+{
+  fast_handshake_state_t *s;
+  *handshake_state_out = s = tor_malloc(sizeof(fast_handshake_state_t));
+  if (crypto_rand((char*)s->state, sizeof(s->state)) < 0) {
+    tor_free(s);
+    return -1;
+  }
+  memcpy(handshake_out, s->state, DIGEST_LEN);
+  return 0;
+}
+
+/** Implement the server side of the CREATE_FAST abbreviated handshake.  The
+ * client has provided DIGEST_LEN key bytes in <b>key_in</b> ("x").  We
+ * generate a reply of DIGEST_LEN*2 bytes in <b>key_out</b>, consisting of a
+ * new random "y", followed by H(x|y) to check for correctness.  We set
+ * <b>key_out_len</b> bytes of key material in <b>key_out</b>.
+ * Return 0 on success, &lt;0 on failure.
+ **/
+int
+fast_server_handshake(const uint8_t *key_in, /* DIGEST_LEN bytes */
+                      uint8_t *handshake_reply_out, /* DIGEST_LEN*2 bytes */
+                      uint8_t *key_out,
+                      size_t key_out_len)
+{
+  uint8_t tmp[DIGEST_LEN+DIGEST_LEN];
+  uint8_t *out = NULL;
+  size_t out_len;
+  int r = -1;
+
+  if (crypto_rand((char*)handshake_reply_out, DIGEST_LEN)<0)
+    return -1;
+
+  memcpy(tmp, key_in, DIGEST_LEN);
+  memcpy(tmp+DIGEST_LEN, handshake_reply_out, DIGEST_LEN);
+  out_len = key_out_len+DIGEST_LEN;
+  out = tor_malloc(out_len);
+  if (crypto_expand_key_material_TAP(tmp, sizeof(tmp), out, out_len)) {
+    goto done;
+  }
+  memcpy(handshake_reply_out+DIGEST_LEN, out, DIGEST_LEN);
+  memcpy(key_out, out+DIGEST_LEN, key_out_len);
+  r = 0;
+ done:
+  memwipe(tmp, 0, sizeof(tmp));
+  memwipe(out, 0, out_len);
+  tor_free(out);
+  return r;
+}
+
+/** Implement the second half of the client side of the CREATE_FAST handshake.
+ * We sent the server <b>handshake_state</b> ("x") already, and the server
+ * told us <b>handshake_reply_out</b> (y|H(x|y)).  Make sure that the hash is
+ * correct, and generate key material in <b>key_out</b>.  Return 0 on success,
+ * true on failure.
+ *
+ * NOTE: The "CREATE_FAST" handshake path is distinguishable from regular
+ * "onionskin" handshakes, and is not secure if an adversary can see or modify
+ * the messages.  Therefore, it should only be used by clients, and only as
+ * the first hop of a circuit (since the first hop is already authenticated
+ * and protected by TLS).
+ */
+int
+fast_client_handshake(const fast_handshake_state_t *handshake_state,
+                      const uint8_t *handshake_reply_out,/*DIGEST_LEN*2 bytes*/
+                      uint8_t *key_out,
+                      size_t key_out_len)
+{
+  uint8_t tmp[DIGEST_LEN+DIGEST_LEN];
+  uint8_t *out;
+  size_t out_len;
+  int r = -1;
+
+  memcpy(tmp, handshake_state->state, DIGEST_LEN);
+  memcpy(tmp+DIGEST_LEN, handshake_reply_out, DIGEST_LEN);
+  out_len = key_out_len+DIGEST_LEN;
+  out = tor_malloc(out_len);
+  if (crypto_expand_key_material_TAP(tmp, sizeof(tmp), out, out_len)) {
+    goto done;
+  }
+  if (tor_memneq(out, handshake_reply_out+DIGEST_LEN, DIGEST_LEN)) {
+    /* H(K) does *not* match. Something fishy. */
+    log_warn(LD_PROTOCOL,"Digest DOES NOT MATCH on fast handshake. "
+             "Bug or attack.");
+    goto done;
+  }
+  memcpy(key_out, out+DIGEST_LEN, key_out_len);
+  r = 0;
+ done:
+  memwipe(tmp, 0, sizeof(tmp));
+  memwipe(out, 0, out_len);
+  tor_free(out);
+  return r;
+}
+
diff --git a/src/or/onion_fast.h b/src/or/onion_fast.h
new file mode 100644
index 0000000000..2d652cc530
--- /dev/null
+++ b/src/or/onion_fast.h
@@ -0,0 +1,38 @@
+/* Copyright (c) 2001 Matej Pfajfar.
+ * Copyright (c) 2001-2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2012, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file onion_fast.h
+ * \brief Header file for onion_fast.c.
+ **/
+
+#ifndef TOR_ONION_FAST_H
+#define TOR_ONION_FAST_H
+
+#define CREATE_FAST_LEN DIGEST_LEN
+#define CREATED_FAST_LEN DIGEST_LEN*2
+
+typedef struct fast_handshake_state_t {
+  uint8_t state[DIGEST_LEN];
+} fast_handshake_state_t;
+
+void fast_handshake_state_free(fast_handshake_state_t *victim);
+
+int fast_onionskin_create(fast_handshake_state_t **handshake_state_out,
+                          uint8_t *handshake_out);
+
+int fast_server_handshake(const uint8_t *message_in,
+                          uint8_t *handshake_reply_out,
+                          uint8_t *key_out,
+                          size_t key_out_len);
+
+int fast_client_handshake(const fast_handshake_state_t *handshake_state,
+                          const uint8_t *handshake_reply_out,
+                          uint8_t *key_out,
+                          size_t key_out_len);
+
+#endif
+
diff --git a/src/or/onion_ntor.c b/src/or/onion_ntor.c
new file mode 100644
index 0000000000..58ab107f1b
--- /dev/null
+++ b/src/or/onion_ntor.c
@@ -0,0 +1,295 @@
+/* Copyright (c) 2012, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#include "orconfig.h"
+
+#include "crypto.h"
+#define ONION_NTOR_PRIVATE
+#include "onion_ntor.h"
+#include "torlog.h"
+#include "util.h"
+
+/** Free storage held in an ntor handshake state. */
+void
+ntor_handshake_state_free(ntor_handshake_state_t *state)
+{
+  if (!state)
+    return;
+  memwipe(state, 0, sizeof(*state));
+  tor_free(state);
+}
+
+/** Convenience function to represent HMAC_SHA256 as our instantiation of
+ * ntor's "tweaked hash'.  Hash the <b>inp_len</b> bytes at <b>inp</b> into
+ * a DIGEST256_LEN-byte digest at <b>out</b>, with the hash changing
+ * depending on the value of <b>tweak</b>. */
+static void
+h_tweak(uint8_t *out,
+        const uint8_t *inp, size_t inp_len,
+        const char *tweak)
+{
+  size_t tweak_len = strlen(tweak);
+  crypto_hmac_sha256((char*)out, tweak, tweak_len, (const char*)inp, inp_len);
+}
+
+/** Wrapper around a set of tweak-values for use with the ntor handshake. */
+typedef struct tweakset_t {
+  const char *t_mac;
+  const char *t_key;
+  const char *t_verify;
+  const char *m_expand;
+} tweakset_t;
+
+/** The tweaks to be used with our handshake. */
+const tweakset_t proto1_tweaks = {
+#define PROTOID "ntor-curve25519-sha256-1"
+#define PROTOID_LEN 24
+  PROTOID ":mac",
+  PROTOID ":key_extract",
+  PROTOID ":verify",
+  PROTOID ":key_expand"
+};
+
+/** Convenience macro: copy <b>len</b> bytes from <b>inp</b> to <b>ptr</b>,
+ * and advance <b>ptr</b> by the number of bytes copied. */
+#define APPEND(ptr, inp, len)                   \
+  STMT_BEGIN {                                  \
+    memcpy(ptr, (inp), (len));                  \
+    ptr += len;                                 \
+  } STMT_END
+
+/**
+ * Compute the first client-side step of the ntor handshake for communicating
+ * with a server whose DIGEST_LEN-byte server identity is <b>router_id</b>,
+ * and whose onion key is <b>router_key</b>. Store the NTOR_ONIONSKIN_LEN-byte
+ * message in <b>onion_skin_out</b>, and store the handshake state in
+ * *<b>handshake_state_out</b>.  Return 0 on success, -1 on failure.
+ */
+int
+onion_skin_ntor_create(const uint8_t *router_id,
+                       const curve25519_public_key_t *router_key,
+                       ntor_handshake_state_t **handshake_state_out,
+                       uint8_t *onion_skin_out)
+{
+  ntor_handshake_state_t *state;
+  uint8_t *op;
+
+  state = tor_malloc_zero(sizeof(ntor_handshake_state_t));
+
+  memcpy(state->router_id, router_id, DIGEST_LEN);
+  memcpy(&state->pubkey_B, router_key, sizeof(curve25519_public_key_t));
+  if (curve25519_secret_key_generate(&state->seckey_x, 0) < 0) {
+    tor_free(state);
+    return -1;
+  }
+  curve25519_public_key_generate(&state->pubkey_X, &state->seckey_x);
+
+  op = onion_skin_out;
+  APPEND(op, router_id, DIGEST_LEN);
+  APPEND(op, router_key->public_key, CURVE25519_PUBKEY_LEN);
+  APPEND(op, state->pubkey_X.public_key, CURVE25519_PUBKEY_LEN);
+  tor_assert(op == onion_skin_out + NTOR_ONIONSKIN_LEN);
+
+  *handshake_state_out = state;
+
+  return 0;
+}
+
+#define SERVER_STR "Server"
+#define SERVER_STR_LEN 6
+
+#define SECRET_INPUT_LEN (CURVE25519_PUBKEY_LEN * 3 +   \
+                          CURVE25519_OUTPUT_LEN * 2 +   \
+                          DIGEST_LEN + PROTOID_LEN)
+#define AUTH_INPUT_LEN (DIGEST256_LEN + DIGEST_LEN +    \
+                        CURVE25519_PUBKEY_LEN*3 +       \
+                        PROTOID_LEN + SERVER_STR_LEN)
+
+/**
+ * Perform the server side of an ntor handshake. Given an
+ * NTOR_ONIONSKIN_LEN-byte message in <b>onion_skin</b>, our own identity
+ * fingerprint as <b>my_node_id</b>, and an associative array mapping public
+ * onion keys to curve25519_keypair_t in <b>private_keys</b>, attempt to
+ * perform the handshake.  Use <b>junk_keys</b> if present if the handshake
+ * indicates an unrecognized public key.  Write an NTOR_REPLY_LEN-byte
+ * message to send back to the client into <b>handshake_reply_out</b>, and
+ * generate <b>key_out_len</b> bytes of key material in <b>key_out</b>. Return
+ * 0 on success, -1 on failure.
+ */
+int
+onion_skin_ntor_server_handshake(const uint8_t *onion_skin,
+                                 const di_digest256_map_t *private_keys,
+                                 const curve25519_keypair_t *junk_keys,
+                                 const uint8_t *my_node_id,
+                                 uint8_t *handshake_reply_out,
+                                 uint8_t *key_out,
+                                 size_t key_out_len)
+{
+  const tweakset_t *T = &proto1_tweaks;
+  /* Sensitive stack-allocated material. Kept in an anonymous struct to make
+   * it easy to wipe. */
+  struct {
+    uint8_t secret_input[SECRET_INPUT_LEN];
+    uint8_t auth_input[AUTH_INPUT_LEN];
+    curve25519_public_key_t pubkey_X;
+    curve25519_secret_key_t seckey_y;
+    curve25519_public_key_t pubkey_Y;
+    uint8_t verify[DIGEST256_LEN];
+  } s;
+  uint8_t *si = s.secret_input, *ai = s.auth_input;
+  const curve25519_keypair_t *keypair_bB;
+  int bad;
+
+  /* Decode the onion skin */
+  /* XXXX Does this possible early-return business threaten our security? */
+  if (tor_memneq(onion_skin, my_node_id, DIGEST_LEN))
+    return -1;
+  /* Note that on key-not-found, we go through with this operation anyway,
+   * using "junk_keys". This will result in failed authentication, but won't
+   * leak whether we recognized the key. */
+  keypair_bB = dimap_search(private_keys, onion_skin + DIGEST_LEN,
+                            (void*)junk_keys);
+  if (!keypair_bB)
+    return -1;
+
+  memcpy(s.pubkey_X.public_key, onion_skin+DIGEST_LEN+DIGEST256_LEN,
+         CURVE25519_PUBKEY_LEN);
+
+  /* Make y, Y */
+  curve25519_secret_key_generate(&s.seckey_y, 0);
+  curve25519_public_key_generate(&s.pubkey_Y, &s.seckey_y);
+
+  /* NOTE: If we ever use a group other than curve25519, or a different
+   * representation for its points, we may need to perform different or
+   * additional checks on X here and on Y in the client handshake, or lose our
+   * security properties. What checks we need would depend on the properties
+   * of the group and its representation.
+   *
+   * In short: if you use anything other than curve25519, this aspect of the
+   * code will need to be reconsidered carefully. */
+
+  /* build secret_input */
+  curve25519_handshake(si, &s.seckey_y, &s.pubkey_X);
+  bad = safe_mem_is_zero(si, CURVE25519_OUTPUT_LEN);
+  si += CURVE25519_OUTPUT_LEN;
+  curve25519_handshake(si, &keypair_bB->seckey, &s.pubkey_X);
+  bad |= safe_mem_is_zero(si, CURVE25519_OUTPUT_LEN);
+  si += CURVE25519_OUTPUT_LEN;
+
+  APPEND(si, my_node_id, DIGEST_LEN);
+  APPEND(si, keypair_bB->pubkey.public_key, CURVE25519_PUBKEY_LEN);
+  APPEND(si, s.pubkey_X.public_key, CURVE25519_PUBKEY_LEN);
+  APPEND(si, s.pubkey_Y.public_key, CURVE25519_PUBKEY_LEN);
+  APPEND(si, PROTOID, PROTOID_LEN);
+  tor_assert(si == s.secret_input + sizeof(s.secret_input));
+
+  /* Compute hashes of secret_input */
+  h_tweak(s.verify, s.secret_input, sizeof(s.secret_input), T->t_verify);
+
+  /* Compute auth_input */
+  APPEND(ai, s.verify, DIGEST256_LEN);
+  APPEND(ai, my_node_id, DIGEST_LEN);
+  APPEND(ai, keypair_bB->pubkey.public_key, CURVE25519_PUBKEY_LEN);
+  APPEND(ai, s.pubkey_Y.public_key, CURVE25519_PUBKEY_LEN);
+  APPEND(ai, s.pubkey_X.public_key, CURVE25519_PUBKEY_LEN);
+  APPEND(ai, PROTOID, PROTOID_LEN);
+  APPEND(ai, SERVER_STR, SERVER_STR_LEN);
+  tor_assert(ai == s.auth_input + sizeof(s.auth_input));
+
+  /* Build the reply */
+  memcpy(handshake_reply_out, s.pubkey_Y.public_key, CURVE25519_PUBKEY_LEN);
+  h_tweak(handshake_reply_out+CURVE25519_PUBKEY_LEN,
+          s.auth_input, sizeof(s.auth_input),
+          T->t_mac);
+
+  /* Generate the key material */
+  crypto_expand_key_material_rfc5869_sha256(
+                           s.secret_input, sizeof(s.secret_input),
+                           (const uint8_t*)T->t_key, strlen(T->t_key),
+                           (const uint8_t*)T->m_expand, strlen(T->m_expand),
+                           key_out, key_out_len);
+
+  /* Wipe all of our local state */
+  memwipe(&s, 0, sizeof(s));
+
+  return bad ? -1 : 0;
+}
+
+/**
+ * Perform the final client side of the ntor handshake, using the state in
+ * <b>handshake_state</b> and the server's NTOR_REPLY_LEN-byte reply in
+ * <b>handshake_reply</b>.  Generate <b>key_out_len</b> bytes of key material
+ * in <b>key_out</b>. Return 0 on success, -1 on failure.
+ */
+int
+onion_skin_ntor_client_handshake(
+                             const ntor_handshake_state_t *handshake_state,
+                             const uint8_t *handshake_reply,
+                             uint8_t *key_out,
+                             size_t key_out_len)
+{
+  const tweakset_t *T = &proto1_tweaks;
+  /* Sensitive stack-allocated material. Kept in an anonymous struct to make
+   * it easy to wipe. */
+  struct {
+    curve25519_public_key_t pubkey_Y;
+    uint8_t secret_input[SECRET_INPUT_LEN];
+    uint8_t verify[DIGEST256_LEN];
+    uint8_t auth_input[AUTH_INPUT_LEN];
+    uint8_t auth[DIGEST256_LEN];
+  } s;
+  uint8_t *ai = s.auth_input, *si = s.secret_input;
+  const uint8_t *auth_candidate;
+  int bad;
+
+  /* Decode input */
+  memcpy(s.pubkey_Y.public_key, handshake_reply, CURVE25519_PUBKEY_LEN);
+  auth_candidate = handshake_reply + CURVE25519_PUBKEY_LEN;
+
+  /* See note in server_handshake above about checking points.  The
+   * circumstances under which we'd need to check Y for membership are
+   * different than those under which we'd be checking X. */
+
+  /* Compute secret_input */
+  curve25519_handshake(si, &handshake_state->seckey_x, &s.pubkey_Y);
+  bad = safe_mem_is_zero(si, CURVE25519_OUTPUT_LEN);
+  si += CURVE25519_OUTPUT_LEN;
+  curve25519_handshake(si, &handshake_state->seckey_x,
+                       &handshake_state->pubkey_B);
+  bad |= safe_mem_is_zero(si, CURVE25519_OUTPUT_LEN);
+  si += CURVE25519_OUTPUT_LEN;
+  APPEND(si, handshake_state->router_id, DIGEST_LEN);
+  APPEND(si, handshake_state->pubkey_B.public_key, CURVE25519_PUBKEY_LEN);
+  APPEND(si, handshake_state->pubkey_X.public_key, CURVE25519_PUBKEY_LEN);
+  APPEND(si, s.pubkey_Y.public_key, CURVE25519_PUBKEY_LEN);
+  APPEND(si, PROTOID, PROTOID_LEN);
+  tor_assert(si == s.secret_input + sizeof(s.secret_input));
+
+  /* Compute verify from secret_input */
+  h_tweak(s.verify, s.secret_input, sizeof(s.secret_input), T->t_verify);
+
+  /* Compute auth_input */
+  APPEND(ai, s.verify, DIGEST256_LEN);
+  APPEND(ai, handshake_state->router_id, DIGEST_LEN);
+  APPEND(ai, handshake_state->pubkey_B.public_key, CURVE25519_PUBKEY_LEN);
+  APPEND(ai, s.pubkey_Y.public_key, CURVE25519_PUBKEY_LEN);
+  APPEND(ai, handshake_state->pubkey_X.public_key, CURVE25519_PUBKEY_LEN);
+  APPEND(ai, PROTOID, PROTOID_LEN);
+  APPEND(ai, SERVER_STR, SERVER_STR_LEN);
+  tor_assert(ai == s.auth_input + sizeof(s.auth_input));
+
+  /* Compute auth */
+  h_tweak(s.auth, s.auth_input, sizeof(s.auth_input), T->t_mac);
+
+  bad |= tor_memneq(s.auth, auth_candidate, DIGEST256_LEN);
+
+  crypto_expand_key_material_rfc5869_sha256(
+                           s.secret_input, sizeof(s.secret_input),
+                           (const uint8_t*)T->t_key, strlen(T->t_key),
+                           (const uint8_t*)T->m_expand, strlen(T->m_expand),
+                           key_out, key_out_len);
+
+  memwipe(&s, 0, sizeof(s));
+  return bad ? -1 : 0;
+}
+
diff --git a/src/or/onion_ntor.h b/src/or/onion_ntor.h
new file mode 100644
index 0000000000..61ff5c0ad3
--- /dev/null
+++ b/src/or/onion_ntor.h
@@ -0,0 +1,63 @@
+/* Copyright (c) 2012, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#ifndef TOR_ONION_NTOR_H
+#define TOR_ONION_NTOR_H
+
+#include "torint.h"
+#include "crypto_curve25519.h"
+#include "di_ops.h"
+
+/** State to be maintained by a client between sending an ntor onionskin
+ * and receiving a reply. */
+typedef struct ntor_handshake_state_t ntor_handshake_state_t;
+
+/** Length of an ntor onionskin, as sent from the client to server. */
+#define NTOR_ONIONSKIN_LEN 84
+/** Length of an ntor reply, as sent from server to client. */
+#define NTOR_REPLY_LEN 64
+
+#ifdef CURVE25519_ENABLED
+void ntor_handshake_state_free(ntor_handshake_state_t *state);
+
+int onion_skin_ntor_create(const uint8_t *router_id,
+                           const curve25519_public_key_t *router_key,
+                           ntor_handshake_state_t **handshake_state_out,
+                           uint8_t *onion_skin_out);
+
+int onion_skin_ntor_server_handshake(const uint8_t *onion_skin,
+                                 const di_digest256_map_t *private_keys,
+                                 const curve25519_keypair_t *junk_keypair,
+                                 const uint8_t *my_node_id,
+                                 uint8_t *handshake_reply_out,
+                                 uint8_t *key_out,
+                                 size_t key_out_len);
+
+int onion_skin_ntor_client_handshake(
+                             const ntor_handshake_state_t *handshake_state,
+                             const uint8_t *handshake_reply,
+                             uint8_t *key_out,
+                             size_t key_out_len);
+
+#ifdef ONION_NTOR_PRIVATE
+
+/** Storage held by a client while waiting for an ntor reply from a server. */
+struct ntor_handshake_state_t {
+  /** Identity digest of the router we're talking to. */
+  uint8_t router_id[DIGEST_LEN];
+  /** Onion key of the router we're talking to. */
+  curve25519_public_key_t pubkey_B;
+
+  /**
+   * Short-lived keypair for use with this handshake.
+   * @{ */
+  curve25519_secret_key_t seckey_x;
+  curve25519_public_key_t pubkey_X;
+  /** @} */
+};
+#endif
+
+#endif
+
+#endif
+
diff --git a/src/or/onion_tap.c b/src/or/onion_tap.c
new file mode 100644
index 0000000000..0ec526cd02
--- /dev/null
+++ b/src/or/onion_tap.c
@@ -0,0 +1,218 @@
+/* Copyright (c) 2001 Matej Pfajfar.
+ * Copyright (c) 2001-2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2012, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file onion_tap.c
+ * \brief Functions to implement the original Tor circuit extension handshake
+ * (a.k.a TAP).
+ *
+ * We didn't call it "TAP" ourselves -- Ian Goldberg named it in "On the
+ * Security of the Tor Authentication Protocol".  (Spoiler: it's secure, but
+ * its security is kind of fragile and implementation dependent.  Never modify
+ * this implementation without reading and understanding that paper at least.)
+ **/
+
+#include "or.h"
+#include "config.h"
+#include "onion_tap.h"
+#include "rephist.h"
+
+/*----------------------------------------------------------------------*/
+
+/** Given a router's 128 byte public key,
+ * stores the following in onion_skin_out:
+ *   - [42 bytes] OAEP padding
+ *   - [16 bytes] Symmetric key for encrypting blob past RSA
+ *   - [70 bytes] g^x part 1 (inside the RSA)
+ *   - [58 bytes] g^x part 2 (symmetrically encrypted)
+ *
+ * Stores the DH private key into handshake_state_out for later completion
+ * of the handshake.
+ *
+ * The meeting point/cookies and auth are zeroed out for now.
+ */
+int
+onion_skin_TAP_create(crypto_pk_t *dest_router_key,
+                  crypto_dh_t **handshake_state_out,
+                  char *onion_skin_out) /* TAP_ONIONSKIN_CHALLENGE_LEN bytes */
+{
+  char challenge[DH_KEY_LEN];
+  crypto_dh_t *dh = NULL;
+  int dhbytes, pkbytes;
+
+  tor_assert(dest_router_key);
+  tor_assert(handshake_state_out);
+  tor_assert(onion_skin_out);
+  *handshake_state_out = NULL;
+  memset(onion_skin_out, 0, TAP_ONIONSKIN_CHALLENGE_LEN);
+
+  if (!(dh = crypto_dh_new(DH_TYPE_CIRCUIT)))
+    goto err;
+
+  dhbytes = crypto_dh_get_bytes(dh);
+  pkbytes = (int) crypto_pk_keysize(dest_router_key);
+  tor_assert(dhbytes == 128);
+  tor_assert(pkbytes == 128);
+
+  if (crypto_dh_get_public(dh, challenge, dhbytes))
+    goto err;
+
+  note_crypto_pk_op(ENC_ONIONSKIN);
+
+  /* set meeting point, meeting cookie, etc here. Leave zero for now. */
+  if (crypto_pk_public_hybrid_encrypt(dest_router_key, onion_skin_out,
+                                      TAP_ONIONSKIN_CHALLENGE_LEN,
+                                      challenge, DH_KEY_LEN,
+                                      PK_PKCS1_OAEP_PADDING, 1)<0)
+    goto err;
+
+  memwipe(challenge, 0, sizeof(challenge));
+  *handshake_state_out = dh;
+
+  return 0;
+ err:
+  memwipe(challenge, 0, sizeof(challenge));
+  if (dh) crypto_dh_free(dh);
+  return -1;
+}
+
+/** Given an encrypted DH public key as generated by onion_skin_create,
+ * and the private key for this onion router, generate the reply (128-byte
+ * DH plus the first 20 bytes of shared key material), and store the
+ * next key_out_len bytes of key material in key_out.
+ */
+int
+onion_skin_TAP_server_handshake(
+                            /*TAP_ONIONSKIN_CHALLENGE_LEN*/
+                            const char *onion_skin,
+                            crypto_pk_t *private_key,
+                            crypto_pk_t *prev_private_key,
+                            /*TAP_ONIONSKIN_REPLY_LEN*/
+                            char *handshake_reply_out,
+                            char *key_out,
+                            size_t key_out_len)
+{
+  char challenge[TAP_ONIONSKIN_CHALLENGE_LEN];
+  crypto_dh_t *dh = NULL;
+  ssize_t len;
+  char *key_material=NULL;
+  size_t key_material_len=0;
+  int i;
+  crypto_pk_t *k;
+
+  len = -1;
+  for (i=0;i<2;++i) {
+    k = i==0?private_key:prev_private_key;
+    if (!k)
+      break;
+    note_crypto_pk_op(DEC_ONIONSKIN);
+    len = crypto_pk_private_hybrid_decrypt(k, challenge,
+                                           TAP_ONIONSKIN_CHALLENGE_LEN,
+                                           onion_skin,
+                                           TAP_ONIONSKIN_CHALLENGE_LEN,
+                                           PK_PKCS1_OAEP_PADDING,0);
+    if (len>0)
+      break;
+  }
+  if (len<0) {
+    log_info(LD_PROTOCOL,
+             "Couldn't decrypt onionskin: client may be using old onion key");
+    goto err;
+  } else if (len != DH_KEY_LEN) {
+    log_warn(LD_PROTOCOL, "Unexpected onionskin length after decryption: %ld",
+             (long)len);
+    goto err;
+  }
+
+  dh = crypto_dh_new(DH_TYPE_CIRCUIT);
+  if (!dh) {
+    log_warn(LD_BUG, "Couldn't allocate DH key");
+    goto err;
+  }
+  if (crypto_dh_get_public(dh, handshake_reply_out, DH_KEY_LEN)) {
+    log_info(LD_GENERAL, "crypto_dh_get_public failed.");
+    goto err;
+  }
+
+  key_material_len = DIGEST_LEN+key_out_len;
+  key_material = tor_malloc(key_material_len);
+  len = crypto_dh_compute_secret(LOG_PROTOCOL_WARN, dh, challenge,
+                                 DH_KEY_LEN, key_material,
+                                 key_material_len);
+  if (len < 0) {
+    log_info(LD_GENERAL, "crypto_dh_compute_secret failed.");
+    goto err;
+  }
+
+  /* send back H(K|0) as proof that we learned K. */
+  memcpy(handshake_reply_out+DH_KEY_LEN, key_material, DIGEST_LEN);
+
+  /* use the rest of the key material for our shared keys, digests, etc */
+  memcpy(key_out, key_material+DIGEST_LEN, key_out_len);
+
+  memwipe(challenge, 0, sizeof(challenge));
+  memwipe(key_material, 0, key_material_len);
+  tor_free(key_material);
+  crypto_dh_free(dh);
+  return 0;
+ err:
+  memwipe(challenge, 0, sizeof(challenge));
+  if (key_material) {
+    memwipe(key_material, 0, key_material_len);
+    tor_free(key_material);
+  }
+  if (dh) crypto_dh_free(dh);
+
+  return -1;
+}
+
+/** Finish the client side of the DH handshake.
+ * Given the 128 byte DH reply + 20 byte hash as generated by
+ * onion_skin_server_handshake and the handshake state generated by
+ * onion_skin_create, verify H(K) with the first 20 bytes of shared
+ * key material, then generate key_out_len more bytes of shared key
+ * material and store them in key_out.
+ *
+ * After the invocation, call crypto_dh_free on handshake_state.
+ */
+int
+onion_skin_TAP_client_handshake(crypto_dh_t *handshake_state,
+            const char *handshake_reply, /* TAP_ONIONSKIN_REPLY_LEN bytes */
+            char *key_out,
+            size_t key_out_len)
+{
+  ssize_t len;
+  char *key_material=NULL;
+  size_t key_material_len;
+  tor_assert(crypto_dh_get_bytes(handshake_state) == DH_KEY_LEN);
+
+  key_material_len = DIGEST_LEN + key_out_len;
+  key_material = tor_malloc(key_material_len);
+  len = crypto_dh_compute_secret(LOG_PROTOCOL_WARN, handshake_state,
+                                 handshake_reply, DH_KEY_LEN, key_material,
+                                 key_material_len);
+  if (len < 0)
+    goto err;
+
+  if (tor_memneq(key_material, handshake_reply+DH_KEY_LEN, DIGEST_LEN)) {
+    /* H(K) does *not* match. Something fishy. */
+    log_warn(LD_PROTOCOL,"Digest DOES NOT MATCH on onion handshake. "
+             "Bug or attack.");
+    goto err;
+  }
+
+  /* use the rest of the key material for our shared keys, digests, etc */
+  memcpy(key_out, key_material+DIGEST_LEN, key_out_len);
+
+  memwipe(key_material, 0, key_material_len);
+  tor_free(key_material);
+  return 0;
+ err:
+  memwipe(key_material, 0, key_material_len);
+  tor_free(key_material);
+  return -1;
+}
+
diff --git a/src/or/onion_tap.h b/src/or/onion_tap.h
new file mode 100644
index 0000000000..deae1bf8c3
--- /dev/null
+++ b/src/or/onion_tap.h
@@ -0,0 +1,37 @@
+/* Copyright (c) 2001 Matej Pfajfar.
+ * Copyright (c) 2001-2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2012, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file onion_tap.h
+ * \brief Header file for onion_tap.c.
+ **/
+
+#ifndef TOR_ONION_TAP_H
+#define TOR_ONION_TAP_H
+
+#define TAP_ONIONSKIN_CHALLENGE_LEN (PKCS1_OAEP_PADDING_OVERHEAD+\
+                                 CIPHER_KEY_LEN+\
+                                 DH_KEY_LEN)
+#define TAP_ONIONSKIN_REPLY_LEN (DH_KEY_LEN+DIGEST_LEN)
+
+int onion_skin_TAP_create(crypto_pk_t *router_key,
+                      crypto_dh_t **handshake_state_out,
+                      char *onion_skin_out);
+
+int onion_skin_TAP_server_handshake(const char *onion_skin,
+                                crypto_pk_t *private_key,
+                                crypto_pk_t *prev_private_key,
+                                char *handshake_reply_out,
+                                char *key_out,
+                                size_t key_out_len);
+
+int onion_skin_TAP_client_handshake(crypto_dh_t *handshake_state,
+                                const char *handshake_reply,
+                                char *key_out,
+                                size_t key_out_len);
+
+#endif
+
diff --git a/src/or/or.h b/src/or/or.h
index bc2cdae6fe..7b8ff705a4 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -99,6 +99,7 @@
 #include "compat_libevent.h"
 #include "ht.h"
 #include "replaycache.h"
+#include "crypto_curve25519.h"
 
 /* These signals are defined to help handle_control_signal work.
  */
@@ -279,6 +280,7 @@ typedef enum {
 #define CPUWORKER_STATE_MAX_ 2
 
 #define CPUWORKER_TASK_ONION CPUWORKER_STATE_BUSY_ONION
+#define CPUWORKER_TASK_SHUTDOWN 255
 
 #define OR_CONN_STATE_MIN_ 1
 /** State for a connection to an OR: waiting for connect() to finish. */
@@ -560,6 +562,8 @@ typedef enum {
 #define RELAY_COMMAND_RESOLVE 11
 #define RELAY_COMMAND_RESOLVED 12
 #define RELAY_COMMAND_BEGIN_DIR 13
+#define RELAY_COMMAND_EXTEND2 14
+#define RELAY_COMMAND_EXTENDED2 15
 
 #define RELAY_COMMAND_ESTABLISH_INTRO 32
 #define RELAY_COMMAND_ESTABLISH_RENDEZVOUS 33
@@ -826,6 +830,8 @@ typedef enum {
 #define CELL_VERSIONS 7
 #define CELL_NETINFO 8
 #define CELL_RELAY_EARLY 9
+#define CELL_CREATE2 10
+#define CELL_CREATED2 11
 
 #define CELL_VPADDING 128
 #define CELL_CERTS 129
@@ -1398,6 +1404,7 @@ typedef struct or_connection_t {
 
   or_handshake_state_t *handshake_state; /**< If we are setting this connection
                                           * up, state information to do so. */
+
   time_t timestamp_lastempty; /**< When was the outbuf last completely empty?*/
   time_t timestamp_last_added_nonpadding; /** When did we last add a
                                            * non-padding cell to the outbuf? */
@@ -1929,6 +1936,8 @@ typedef struct {
 
   crypto_pk_t *onion_pkey; /**< Public RSA key for onions. */
   crypto_pk_t *identity_pkey;  /**< Public RSA key for signing. */
+  /** Public curve25519 key for onions */
+  curve25519_public_key_t *onion_curve25519_pkey;
 
   char *platform; /**< What software/operating system is this OR using? */
 
@@ -2052,6 +2061,9 @@ typedef struct routerstatus_t {
   /** True iff this router is a version that allows DATA cells to arrive on
    * a stream before it has sent a CONNECTED cell. */
   unsigned int version_supports_optimistic_data:1;
+  /** True iff this router has a version that allows it to accept EXTEND2
+   * cells */
+  unsigned int version_supports_extend2_cells:1;
 
   unsigned int has_bandwidth:1; /**< The vote/consensus had bw info */
   unsigned int has_exitsummary:1; /**< The vote/consensus had exit summaries */
@@ -2142,6 +2154,8 @@ typedef struct microdesc_t {
 
   /** As routerinfo_t.onion_pkey */
   crypto_pk_t *onion_pkey;
+  /** As routerinfo_t.onion_curve25519_pkey */
+  curve25519_public_key_t *onion_curve25519_pkey;
   /** As routerinfo_t.ipv6_add */
   tor_addr_t ipv6_addr;
   /** As routerinfo_t.ipv6_orport */
@@ -2501,6 +2515,9 @@ typedef struct extend_info_t {
   uint16_t port; /**< OR port. */
   tor_addr_t addr; /**< IP address. */
   crypto_pk_t *onion_key; /**< Current onionskin key. */
+#ifdef CURVE25519_ENABLED
+  curve25519_public_key_t curve25519_onion_key;
+#endif
 } extend_info_t;
 
 /** Certificate for v3 directory protocol: binds long-term authority identity
@@ -2557,6 +2574,20 @@ typedef enum {
 
 #define CRYPT_PATH_MAGIC 0x70127012u
 
+struct fast_handshake_state_t;
+struct ntor_handshake_state_t;
+#define ONION_HANDSHAKE_TYPE_TAP 0x0000
+#define ONION_HANDSHAKE_TYPE_FAST 0x0001
+#define ONION_HANDSHAKE_TYPE_NTOR 0x0002
+typedef struct {
+  uint16_t tag;
+  union {
+    struct fast_handshake_state_t *fast;
+    crypto_dh_t *tap;
+    struct ntor_handshake_state_t *ntor;
+  } u;
+} onion_handshake_state_t;
+
 /** Holds accounting information for a single step in the layered encryption
  * performed by a circuit.  Used only at the client edge of a circuit. */
 typedef struct crypt_path_t {
@@ -2575,17 +2606,15 @@ typedef struct crypt_path_t {
   /** Digest state for cells heading away from the OR at this step. */
   crypto_digest_t *b_digest;
 
-  /** Current state of Diffie-Hellman key negotiation with the OR at this
+  /** Current state of the handshake as performed with the OR at this
    * step. */
-  crypto_dh_t *dh_handshake_state;
-  /** Current state of 'fast' (non-PK) key negotiation with the OR at this
-   * step. Used to save CPU when TLS is already providing all the
-   * authentication, secrecy, and integrity we need, and we're already
-   * distinguishable from an OR.
-   */
-  uint8_t fast_handshake_state[DIGEST_LEN];
+  onion_handshake_state_t handshake_state;
+  /** Diffie-hellman handshake state for performing an introduction
+   * operations */
+  crypto_dh_t *rend_dh_handshake_state;
+
   /** Negotiated key material shared with the OR at this step. */
-  char handshake_digest[DIGEST_LEN];/* KH in tor-spec.txt */
+  char rend_circ_nonce[DIGEST_LEN];/* KH in tor-spec.txt */
 
   /** Information to extend to the OR at this step. */
   extend_info_t *extend_info;
@@ -2626,10 +2655,6 @@ typedef struct {
 #define CPATH_KEY_MATERIAL_LEN (20*2+16*2)
 
 #define DH_KEY_LEN DH_BYTES
-#define ONIONSKIN_CHALLENGE_LEN (PKCS1_OAEP_PADDING_OVERHEAD+\
-                                 CIPHER_KEY_LEN+\
-                                 DH_KEY_LEN)
-#define ONIONSKIN_REPLY_LEN (DH_KEY_LEN+DIGEST_LEN)
 
 /** Information used to build a circuit. */
 typedef struct {
@@ -2661,6 +2686,8 @@ typedef struct {
 #define ORIGIN_CIRCUIT_MAGIC 0x35315243u
 #define OR_CIRCUIT_MAGIC 0x98ABC04Fu
 
+struct create_cell_t;
+
 /**
  * A circuit is a path over the onion routing
  * network. Applications can connect to one end of the circuit, and can
@@ -2735,10 +2762,8 @@ typedef struct circuit_t {
    * more. */
   int deliver_window;
 
-  /** For storage while n_chan is pending
-    * (state CIRCUIT_STATE_CHAN_WAIT). When defined, it is always
-    * length ONIONSKIN_CHALLENGE_LEN. */
-  char *n_chan_onionskin;
+  /** For storage while n_chan is pending (state CIRCUIT_STATE_CHAN_WAIT). */
+  struct create_cell_t *n_chan_create_cell;
 
   /** When did circuit construction actually begin (ie send the
    * CREATE cell or begin cannibalization).
@@ -3026,7 +3051,8 @@ typedef struct or_circuit_t {
   char rend_token[REND_TOKEN_LEN];
 
   /* ???? move to a subtype or adjunct structure? Wastes 20 bytes -NM */
-  char handshake_digest[DIGEST_LEN]; /**< Stores KH for the handshake. */
+  /** Stores KH for the handshake. */
+  char rend_circ_nonce[DIGEST_LEN];/* KH in tor-spec.txt */
 
   /** How many more relay_early cells can we send on this circuit, according
    * to the specification? */
@@ -3877,6 +3903,8 @@ typedef struct {
 
   char *TLSECGroup; /**< One of "P256", "P224", or nil for auto */
 
+  /** Autobool: should we use the ntor handshake if we can? */
+  int UseNTorHandshake;
 } or_options_t;
 
 /** Persistent state for an onion router, as saved to disk. */
diff --git a/src/or/relay.c b/src/or/relay.c
index 696a411972..f58c5c9c55 100644
--- a/src/or/relay.c
+++ b/src/or/relay.c
@@ -27,6 +27,7 @@
 #include "mempool.h"
 #include "networkstatus.h"
 #include "nodelist.h"
+#include "onion.h"
 #include "policies.h"
 #include "reasons.h"
 #include "relay.h"
@@ -571,6 +572,7 @@ relay_send_command_from_edge(streamid_t stream_id, circuit_t *circ,
     origin_circuit_t *origin_circ = TO_ORIGIN_CIRCUIT(circ);
     if (origin_circ->remaining_relay_early_cells > 0 &&
         (relay_command == RELAY_COMMAND_EXTEND ||
+         relay_command == RELAY_COMMAND_EXTEND2 ||
          cpath_layer != origin_circ->cpath)) {
       /* If we've got any relay_early cells left and (we're sending
        * an extend cell or we're not talking to the first hop), use
@@ -584,7 +586,8 @@ relay_send_command_from_edge(streamid_t stream_id, circuit_t *circ,
        * task 878. */
       origin_circ->relay_early_commands[
           origin_circ->relay_early_cells_sent++] = relay_command;
-    } else if (relay_command == RELAY_COMMAND_EXTEND) {
+    } else if (relay_command == RELAY_COMMAND_EXTEND ||
+               relay_command == RELAY_COMMAND_EXTEND2) {
       /* If no RELAY_EARLY cells can be sent over this circuit, log which
        * commands have been sent as RELAY_EARLY cells before; helps debug
        * task 878. */
@@ -1282,7 +1285,8 @@ connection_edge_process_relay_cell(cell_t *cell, circuit_t *circ,
         connection_mark_and_flush(TO_CONN(conn));
       }
       return 0;
-    case RELAY_COMMAND_EXTEND: {
+    case RELAY_COMMAND_EXTEND:
+    case RELAY_COMMAND_EXTEND2: {
       static uint64_t total_n_extend=0, total_nonearly=0;
       total_n_extend++;
       if (rh.stream_id) {
@@ -1317,17 +1321,27 @@ connection_edge_process_relay_cell(cell_t *cell, circuit_t *circ,
       return circuit_extend(cell, circ);
     }
     case RELAY_COMMAND_EXTENDED:
+    case RELAY_COMMAND_EXTENDED2:
       if (!layer_hint) {
         log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
                "'extended' unsupported at non-origin. Dropping.");
         return 0;
       }
       log_debug(domain,"Got an extended cell! Yay.");
-      if ((reason = circuit_finish_handshake(TO_ORIGIN_CIRCUIT(circ),
-                                       CELL_CREATED,
-                                       cell->payload+RELAY_HEADER_SIZE)) < 0) {
-        log_warn(domain,"circuit_finish_handshake failed.");
-        return reason;
+      {
+        extended_cell_t extended_cell;
+        if (extended_cell_parse(&extended_cell, rh.command,
+                        (const uint8_t*)cell->payload+RELAY_HEADER_SIZE,
+                        rh.length)<0) {
+          log_warn(LD_PROTOCOL,
+                   "Can't parse EXTENDED cell; killing circuit.");
+          return -END_CIRC_REASON_TORPROTOCOL;
+        }
+        if ((reason = circuit_finish_handshake(TO_ORIGIN_CIRCUIT(circ),
+                                         &extended_cell.created_cell)) < 0) {
+          log_warn(domain,"circuit_finish_handshake failed.");
+          return reason;
+        }
       }
       if ((reason=circuit_send_next_onion_skin(TO_ORIGIN_CIRCUIT(circ)))<0) {
         log_info(domain,"circuit_send_next_onion_skin() failed.");
diff --git a/src/or/rendclient.c b/src/or/rendclient.c
index 88241a4b2c..0bed615b60 100644
--- a/src/or/rendclient.c
+++ b/src/or/rendclient.c
@@ -206,12 +206,12 @@ rend_client_send_introduction(origin_circuit_t *introcirc,
     cpath = rendcirc->build_state->pending_final_cpath =
       tor_malloc_zero(sizeof(crypt_path_t));
     cpath->magic = CRYPT_PATH_MAGIC;
-    if (!(cpath->dh_handshake_state = crypto_dh_new(DH_TYPE_REND))) {
+    if (!(cpath->rend_dh_handshake_state = crypto_dh_new(DH_TYPE_REND))) {
       log_warn(LD_BUG, "Internal error: couldn't allocate DH.");
       status = -2;
       goto perm_err;
     }
-    if (crypto_dh_generate_public(cpath->dh_handshake_state)<0) {
+    if (crypto_dh_generate_public(cpath->rend_dh_handshake_state)<0) {
       log_warn(LD_BUG, "Internal error: couldn't generate g^x.");
       status = -2;
       goto perm_err;
@@ -261,7 +261,7 @@ rend_client_send_introduction(origin_circuit_t *introcirc,
     dh_offset = MAX_NICKNAME_LEN+1+REND_COOKIE_LEN;
   }
 
-  if (crypto_dh_get_public(cpath->dh_handshake_state, tmp+dh_offset,
+  if (crypto_dh_get_public(cpath->rend_dh_handshake_state, tmp+dh_offset,
                            DH_KEY_LEN)<0) {
     log_warn(LD_BUG, "Internal error: couldn't extract g^x.");
     status = -2;
@@ -907,9 +907,9 @@ rend_client_receive_rendezvous(origin_circuit_t *circ, const uint8_t *request,
   tor_assert(circ->build_state);
   tor_assert(circ->build_state->pending_final_cpath);
   hop = circ->build_state->pending_final_cpath;
-  tor_assert(hop->dh_handshake_state);
+  tor_assert(hop->rend_dh_handshake_state);
   if (crypto_dh_compute_secret(LOG_PROTOCOL_WARN,
-                               hop->dh_handshake_state, (char*)request,
+                               hop->rend_dh_handshake_state, (char*)request,
                                DH_KEY_LEN,
                                keys, DIGEST_LEN+CPATH_KEY_MATERIAL_LEN)<0) {
     log_warn(LD_GENERAL, "Couldn't complete DH handshake.");
@@ -925,8 +925,8 @@ rend_client_receive_rendezvous(origin_circuit_t *circ, const uint8_t *request,
     goto err;
   }
 
-  crypto_dh_free(hop->dh_handshake_state);
-  hop->dh_handshake_state = NULL;
+  crypto_dh_free(hop->rend_dh_handshake_state);
+  hop->rend_dh_handshake_state = NULL;
 
   /* All is well. Extend the circuit. */
   circuit_change_purpose(TO_CIRCUIT(circ), CIRCUIT_PURPOSE_C_REND_JOINED);
diff --git a/src/or/rendmid.c b/src/or/rendmid.c
index dc2dc1d9e7..8234265ca5 100644
--- a/src/or/rendmid.c
+++ b/src/or/rendmid.c
@@ -56,8 +56,8 @@ rend_mid_establish_intro(or_circuit_t *circ, const uint8_t *request,
     goto err;
   }
 
-  /* Next 20 bytes: Hash of handshake_digest | "INTRODUCE" */
-  memcpy(buf, circ->handshake_digest, DIGEST_LEN);
+  /* Next 20 bytes: Hash of rend_circ_nonce | "INTRODUCE" */
+  memcpy(buf, circ->rend_circ_nonce, DIGEST_LEN);
   memcpy(buf+DIGEST_LEN, "INTRODUCE", 9);
   if (crypto_digest(expected_digest, buf, DIGEST_LEN+9) < 0) {
     log_warn(LD_BUG, "Internal error computing digest.");
diff --git a/src/or/rendservice.c b/src/or/rendservice.c
index e70f969e8f..fc76f5654a 100644
--- a/src/or/rendservice.c
+++ b/src/or/rendservice.c
@@ -1378,11 +1378,11 @@ rend_service_introduce(origin_circuit_t *circuit, const uint8_t *request,
   cpath->magic = CRYPT_PATH_MAGIC;
   launched->build_state->expiry_time = now + MAX_REND_TIMEOUT;
 
-  cpath->dh_handshake_state = dh;
+  cpath->rend_dh_handshake_state = dh;
   dh = NULL;
   if (circuit_init_cpath_crypto(cpath,keys+DIGEST_LEN,1)<0)
     goto err;
-  memcpy(cpath->handshake_digest, keys, DIGEST_LEN);
+  memcpy(cpath->rend_circ_nonce, keys, DIGEST_LEN);
 
   /* For path bias: This intro circuit was used successfully */
   circuit->path_state = PATH_STATE_USE_SUCCEEDED;
@@ -2486,7 +2486,7 @@ rend_service_intro_has_opened(origin_circuit_t *circuit)
   len = r;
   set_uint16(buf, htons((uint16_t)len));
   len += 2;
-  memcpy(auth, circuit->cpath->prev->handshake_digest, DIGEST_LEN);
+  memcpy(auth, circuit->cpath->prev->rend_circ_nonce, DIGEST_LEN);
   memcpy(auth+DIGEST_LEN, "INTRODUCE", 9);
   if (crypto_digest(buf+len, auth, DIGEST_LEN+9))
     goto err;
@@ -2632,13 +2632,13 @@ rend_service_rendezvous_has_opened(origin_circuit_t *circuit)
 
   /* All we need to do is send a RELAY_RENDEZVOUS1 cell... */
   memcpy(buf, circuit->rend_data->rend_cookie, REND_COOKIE_LEN);
-  if (crypto_dh_get_public(hop->dh_handshake_state,
+  if (crypto_dh_get_public(hop->rend_dh_handshake_state,
                            buf+REND_COOKIE_LEN, DH_KEY_LEN)<0) {
     log_warn(LD_GENERAL,"Couldn't get DH public key.");
     reason = END_CIRC_REASON_INTERNAL;
     goto err;
   }
-  memcpy(buf+REND_COOKIE_LEN+DH_KEY_LEN, hop->handshake_digest,
+  memcpy(buf+REND_COOKIE_LEN+DH_KEY_LEN, hop->rend_circ_nonce,
          DIGEST_LEN);
 
   /* Send the cell */
@@ -2651,8 +2651,8 @@ rend_service_rendezvous_has_opened(origin_circuit_t *circuit)
     goto err;
   }
 
-  crypto_dh_free(hop->dh_handshake_state);
-  hop->dh_handshake_state = NULL;
+  crypto_dh_free(hop->rend_dh_handshake_state);
+  hop->rend_dh_handshake_state = NULL;
 
   /* Append the cpath entry. */
   hop->state = CPATH_STATE_OPEN;
diff --git a/src/or/router.c b/src/or/router.c
index c7380cb444..29011c2536 100644
--- a/src/or/router.c
+++ b/src/or/router.c
@@ -13,6 +13,7 @@
 #include "config.h"
 #include "connection.h"
 #include "control.h"
+#include "crypto_curve25519.h"
 #include "directory.h"
 #include "dirserv.h"
 #include "dns.h"
@@ -54,6 +55,13 @@ static crypto_pk_t *onionkey=NULL;
 /** Previous private onionskin decryption key: used to decode CREATE cells
  * generated by clients that have an older version of our descriptor. */
 static crypto_pk_t *lastonionkey=NULL;
+#ifdef CURVE25519_ENABLED
+/** Current private ntor secret key: used to perform the ntor handshake. */
+static curve25519_keypair_t curve25519_onion_key;
+/** Previous private ntor secret key: used to perform the ntor handshake
+ * with clients that have an older version of our descriptor. */
+static curve25519_keypair_t last_curve25519_onion_key;
+#endif
 /** Private server "identity key": used to sign directory info and TLS
  * certificates. Never changes. */
 static crypto_pk_t *server_identitykey=NULL;
@@ -126,6 +134,55 @@ dup_onion_keys(crypto_pk_t **key, crypto_pk_t **last)
   tor_mutex_release(key_lock);
 }
 
+#ifdef CURVE25519_ENABLED
+/** Return the current secret onion key for the ntor handshake. Must only
+ * be called from the main thread. */
+static const curve25519_keypair_t *
+get_current_curve25519_keypair(void)
+{
+  return &curve25519_onion_key;
+}
+/** Return a map from KEYID (the key itself) to keypairs for use in the ntor
+ * handshake. Must only be called from the main thread. */
+di_digest256_map_t *
+construct_ntor_key_map(void)
+{
+  di_digest256_map_t *m = NULL;
+
+  dimap_add_entry(&m,
+                  curve25519_onion_key.pubkey.public_key,
+                  tor_memdup(&curve25519_onion_key,
+                             sizeof(curve25519_keypair_t)));
+  if (!tor_mem_is_zero((const char*)
+                          last_curve25519_onion_key.pubkey.public_key,
+                       CURVE25519_PUBKEY_LEN)) {
+    dimap_add_entry(&m,
+                    last_curve25519_onion_key.pubkey.public_key,
+                    tor_memdup(&last_curve25519_onion_key,
+                               sizeof(curve25519_keypair_t)));
+  }
+
+  return m;
+}
+/** Helper used to deallocate a di_digest256_map_t returned by
+ * construct_ntor_key_map. */
+static void
+ntor_key_map_free_helper(void *arg)
+{
+  curve25519_keypair_t *k = arg;
+  memwipe(k, 0, sizeof(*k));
+  tor_free(k);
+}
+/** Release all storage from a keymap returned by construct_ntor_key_map. */
+void
+ntor_key_map_free(di_digest256_map_t *map)
+{
+  if (!map)
+    return;
+  dimap_free(map, ntor_key_map_free_helper);
+}
+#endif
+
 /** Return the time when the onion key was last set.  This is either the time
  * when the process launched, or the time of the most recent key rotation since
  * the process launched.
@@ -253,11 +310,18 @@ void
 rotate_onion_key(void)
 {
   char *fname, *fname_prev;
-  crypto_pk_t *prkey;
+  crypto_pk_t *prkey = NULL;
   or_state_t *state = get_or_state();
+#ifdef CURVE25519_ENABLED
+  curve25519_keypair_t new_curve25519_keypair;
+#endif
   time_t now;
   fname = get_datadir_fname2("keys", "secret_onion_key");
   fname_prev = get_datadir_fname2("keys", "secret_onion_key.old");
+  if (file_status(fname) == FN_FILE) {
+    if (replace_file(fname, fname_prev))
+      goto error;
+  }
   if (!(prkey = crypto_pk_new())) {
     log_err(LD_GENERAL,"Error constructing rotated onion key");
     goto error;
@@ -266,19 +330,38 @@ rotate_onion_key(void)
     log_err(LD_BUG,"Error generating onion key");
     goto error;
   }
+  if (crypto_pk_write_private_key_to_filename(prkey, fname)) {
+    log_err(LD_FS,"Couldn't write generated onion key to \"%s\".", fname);
+    goto error;
+  }
+#ifdef CURVE25519_ENABLED
+  tor_free(fname);
+  tor_free(fname_prev);
+  fname = get_datadir_fname2("keys", "secret_onion_key_ntor");
+  fname_prev = get_datadir_fname2("keys", "secret_onion_key_ntor.old");
+  if (curve25519_keypair_generate(&new_curve25519_keypair, 1) < 0)
+    goto error;
   if (file_status(fname) == FN_FILE) {
     if (replace_file(fname, fname_prev))
       goto error;
   }
-  if (crypto_pk_write_private_key_to_filename(prkey, fname)) {
-    log_err(LD_FS,"Couldn't write generated onion key to \"%s\".", fname);
+  if (curve25519_keypair_write_to_file(&new_curve25519_keypair, fname,
+                                       "onion") < 0) {
+    log_err(LD_FS,"Couldn't write curve25519 onion key to \"%s\".",fname);
     goto error;
   }
+#endif
   log_info(LD_GENERAL, "Rotating onion key");
   tor_mutex_acquire(key_lock);
   crypto_pk_free(lastonionkey);
   lastonionkey = onionkey;
   onionkey = prkey;
+#ifdef CURVE25519_ENABLED
+  memcpy(&last_curve25519_onion_key, &curve25519_onion_key,
+         sizeof(curve25519_keypair_t));
+  memcpy(&curve25519_onion_key, &new_curve25519_keypair,
+         sizeof(curve25519_keypair_t));
+#endif
   now = time(NULL);
   state->LastRotatedOnionKey = onionkey_set_at = now;
   tor_mutex_release(key_lock);
@@ -290,6 +373,9 @@ rotate_onion_key(void)
   if (prkey)
     crypto_pk_free(prkey);
  done:
+#ifdef CURVE25519_ENABLED
+  memwipe(&new_curve25519_keypair, 0, sizeof(new_curve25519_keypair));
+#endif
   tor_free(fname);
   tor_free(fname_prev);
 }
@@ -363,6 +449,77 @@ init_key_from_file(const char *fname, int generate, int severity)
   return NULL;
 }
 
+#ifdef CURVE25519_ENABLED
+/** Load a curve25519 keypair from the file <b>fname</b>, writing it into
+ * <b>keys_out</b>.  If the file isn't found and <b>generate</b> is true,
+ * create a new keypair and write it into the file.  If there are errors, log
+ * them at level <b>severity</b>. Generate files using <b>tag</b> in their
+ * ASCII wrapper. */
+static int
+init_curve25519_keypair_from_file(curve25519_keypair_t *keys_out,
+                                  const char *fname,
+                                  int generate,
+                                  int severity,
+                                  const char *tag)
+{
+  switch (file_status(fname)) {
+    case FN_DIR:
+    case FN_ERROR:
+      log(severity, LD_FS,"Can't read key from \"%s\"", fname);
+      goto error;
+    case FN_NOENT:
+      if (generate) {
+        if (!have_lockfile()) {
+          if (try_locking(get_options(), 0)<0) {
+            /* Make sure that --list-fingerprint only creates new keys
+             * if there is no possibility for a deadlock. */
+            log(severity, LD_FS, "Another Tor process has locked \"%s\". Not "
+                "writing any new keys.", fname);
+            /*XXXX The 'other process' might make a key in a second or two;
+             * maybe we should wait for it. */
+            goto error;
+          }
+        }
+        log_info(LD_GENERAL, "No key found in \"%s\"; generating fresh key.",
+                 fname);
+        if (curve25519_keypair_generate(keys_out, 1) < 0)
+          goto error;
+        if (curve25519_keypair_write_to_file(keys_out, fname, tag)<0) {
+          log(severity, LD_FS,
+              "Couldn't write generated key to \"%s\".", fname);
+          memset(keys_out, 0, sizeof(*keys_out));
+          goto error;
+        }
+      } else {
+        log_info(LD_GENERAL, "No key found in \"%s\"", fname);
+      }
+      return 0;
+    case FN_FILE:
+      {
+        char *tag_in=NULL;
+        if (curve25519_keypair_read_from_file(keys_out, &tag_in, fname) < 0) {
+          log(severity, LD_GENERAL,"Error loading private key.");
+          tor_free(tag_in);
+          goto error;
+        }
+        if (!tag_in || strcmp(tag_in, tag)) {
+          log(severity, LD_GENERAL,"Unexpected tag %s on private key.",
+              escaped(tag_in));
+          tor_free(tag_in);
+          goto error;
+        }
+        tor_free(tag_in);
+        return 0;
+      }
+    default:
+      tor_assert(0);
+  }
+
+ error:
+  return -1;
+}
+#endif
+
 /** Try to load the vote-signing private key and certificate for being a v3
  * directory authority, and make sure they match.  If <b>legacy</b>, load a
  * legacy key/cert set for emergency key migration; otherwise load the regular
@@ -641,12 +798,35 @@ init_keys(void)
 
   keydir = get_datadir_fname2("keys", "secret_onion_key.old");
   if (!lastonionkey && file_status(keydir) == FN_FILE) {
-    prkey = init_key_from_file(keydir, 1, LOG_ERR);
+    prkey = init_key_from_file(keydir, 1, LOG_ERR); /* XXXX Why 1? */
     if (prkey)
       lastonionkey = prkey;
   }
   tor_free(keydir);
 
+#ifdef CURVE25519_ENABLED
+  {
+    /* 2b. Load curve25519 onion keys. */
+    int r;
+    keydir = get_datadir_fname2("keys", "secret_onion_key_ntor");
+    r = init_curve25519_keypair_from_file(&curve25519_onion_key,
+                                          keydir, 1, LOG_ERR, "onion");
+    tor_free(keydir);
+    if (r<0)
+      return -1;
+
+    keydir = get_datadir_fname2("keys", "secret_onion_key_ntor.old");
+    if (tor_mem_is_zero((const char *)
+                           last_curve25519_onion_key.pubkey.public_key,
+                        CURVE25519_PUBKEY_LEN) &&
+        file_status(keydir) == FN_FILE) {
+      init_curve25519_keypair_from_file(&last_curve25519_onion_key,
+                                        keydir, 0, LOG_ERR, "onion");
+    }
+    tor_free(keydir);
+  }
+#endif
+
   /* 3. Initialize link key and TLS context. */
   if (router_initialize_tls_context() < 0) {
     log_err(LD_GENERAL,"Error initializing TLS context");
@@ -905,7 +1085,8 @@ extend_info_from_router(const routerinfo_t *r)
 
   router_get_prim_orport(r, &ap);
   return extend_info_new(r->nickname, r->cache_info.identity_digest,
-                           r->onion_pkey, &ap.addr, ap.port);
+                         r->onion_pkey, r->onion_curve25519_pkey,
+                         &ap.addr, ap.port);
 }
 
 /** Some time has passed, or we just got new directory information.
@@ -1432,6 +1613,13 @@ router_digest_is_me(const char *digest)
           tor_memeq(server_identitykey_digest, digest, DIGEST_LEN));
 }
 
+/** Return my identity digest. */
+const uint8_t *
+router_get_my_id_digest(void)
+{
+  return (const uint8_t *)server_identitykey_digest;
+}
+
 /** Return true iff I'm a server and <b>digest</b> is equal to
  * my identity digest. */
 int
@@ -1578,6 +1766,11 @@ router_rebuild_descriptor(int force)
   ri->cache_info.published_on = time(NULL);
   ri->onion_pkey = crypto_pk_dup_key(get_onion_key()); /* must invoke from
                                                         * main thread */
+#ifdef CURVE25519_ENABLED
+  ri->onion_curve25519_pkey =
+    tor_memdup(&get_current_curve25519_keypair()->pubkey,
+               sizeof(curve25519_public_key_t));
+#endif
 
   /* For now, at most one IPv6 or-address is being advertised. */
   {
@@ -2158,6 +2351,22 @@ router_dump_router_to_string(char *s, size_t maxlen, routerinfo_t *router,
     written += result;
   }
 
+#ifdef CURVE25519_ENABLED
+  if (router->onion_curve25519_pkey) {
+    char kbuf[128];
+    base64_encode(kbuf, sizeof(kbuf),
+                  (const char *)router->onion_curve25519_pkey->public_key,
+                  CURVE25519_PUBKEY_LEN);
+    result = tor_snprintf(s+written,maxlen-written, "ntor-onion-key %s",
+                          kbuf);
+    if (result<0) {
+      log_warn(LD_BUG,"descriptor snprintf ran out of room!");
+      return -1;
+    }
+    written += result;
+  }
+#endif
+
   /* Write the exit policy to the end of 's'. */
   if (!router->exit_policy || !smartlist_len(router->exit_policy)) {
     strlcat(s+written, "reject *:*\n", maxlen-written);
@@ -2806,6 +3015,11 @@ router_free_all(void)
   crypto_pk_free(legacy_signing_key);
   authority_cert_free(legacy_key_certificate);
 
+#ifdef CURVE25519_ENABLED
+  memwipe(&curve25519_onion_key, 0, sizeof(curve25519_onion_key));
+  memwipe(&last_curve25519_onion_key, 0, sizeof(last_curve25519_onion_key));
+#endif
+
   if (warned_nonexistent_family) {
     SMARTLIST_FOREACH(warned_nonexistent_family, char *, cp, tor_free(cp));
     smartlist_free(warned_nonexistent_family);
diff --git a/src/or/router.h b/src/or/router.h
index b641c1cc6a..ea0b2ab4e3 100644
--- a/src/or/router.h
+++ b/src/or/router.h
@@ -30,6 +30,11 @@ crypto_pk_t *init_key_from_file(const char *fname, int generate,
                                     int severity);
 void v3_authority_check_key_expiry(void);
 
+#ifdef CURVE25519_ENABLED
+di_digest256_map_t *construct_ntor_key_map(void);
+void ntor_key_map_free(di_digest256_map_t *map);
+#endif
+
 int router_initialize_tls_context(void);
 int init_keys(void);
 
@@ -79,6 +84,7 @@ extrainfo_t *router_get_my_extrainfo(void);
 const char *router_get_my_descriptor(void);
 const char *router_get_descriptor_gen_reason(void);
 int router_digest_is_me(const char *digest);
+const uint8_t *router_get_my_id_digest(void);
 int router_extrainfo_digest_is_me(const char *digest);
 int router_is_me(const routerinfo_t *router);
 int router_fingerprint_is_me(const char *fp);
diff --git a/src/or/routerlist.c b/src/or/routerlist.c
index 898b9b5b98..a597c6bfca 100644
--- a/src/or/routerlist.c
+++ b/src/or/routerlist.c
@@ -2482,6 +2482,7 @@ routerinfo_free(routerinfo_t *router)
   tor_free(router->contact_info);
   if (router->onion_pkey)
     crypto_pk_free(router->onion_pkey);
+  tor_free(router->onion_curve25519_pkey);
   if (router->identity_pkey)
     crypto_pk_free(router->identity_pkey);
   if (router->declared_family) {
diff --git a/src/or/routerparse.c b/src/or/routerparse.c
index 1aee4e5332..c873784c0e 100644
--- a/src/or/routerparse.c
+++ b/src/or/routerparse.c
@@ -43,6 +43,7 @@ typedef enum {
   K_SIGNED_DIRECTORY,
   K_SIGNING_KEY,
   K_ONION_KEY,
+  K_ONION_KEY_NTOR,
   K_ROUTER_SIGNATURE,
   K_PUBLISHED,
   K_RUNNING_ROUTERS,
@@ -276,6 +277,7 @@ static token_rule_t routerdesc_token_table[] = {
   T01("ipv6-policy",         K_IPV6_POLICY,         CONCAT_ARGS, NO_OBJ),
   T1( "signing-key",         K_SIGNING_KEY,         NO_ARGS, NEED_KEY_1024 ),
   T1( "onion-key",           K_ONION_KEY,           NO_ARGS, NEED_KEY_1024 ),
+  T01("ntor-onion-key",      K_ONION_KEY_NTOR,      GE(1), NO_OBJ ),
   T1_END( "router-signature",    K_ROUTER_SIGNATURE,    NO_ARGS, NEED_OBJ ),
   T1( "published",           K_PUBLISHED,       CONCAT_ARGS, NO_OBJ ),
   T01("uptime",              K_UPTIME,              GE(1),   NO_OBJ ),
@@ -508,6 +510,7 @@ static token_rule_t networkstatus_detached_signature_token_table[] = {
 /** List of tokens recognized in microdescriptors */
 static token_rule_t microdesc_token_table[] = {
   T1_START("onion-key",        K_ONION_KEY,        NO_ARGS,     NEED_KEY_1024),
+  T01("ntor-onion-key",        K_ONION_KEY_NTOR,   GE(1),       NO_OBJ ),
   T0N("a",                     K_A,                GE(1),       NO_OBJ ),
   T01("family",                K_FAMILY,           ARGS,        NO_OBJ ),
   T01("p",                     K_P,                CONCAT_ARGS, NO_OBJ ),
@@ -1284,6 +1287,21 @@ router_parse_entry_from_string(const char *s, const char *end,
   router->onion_pkey = tok->key;
   tok->key = NULL; /* Prevent free */
 
+  if ((tok = find_opt_by_keyword(tokens, K_ONION_KEY_NTOR))) {
+    uint8_t k[CURVE25519_PUBKEY_LEN+32];
+    int r;
+    tor_assert(tok->n_args >= 1);
+    r = base64_decode((char*)k, sizeof(k), tok->args[0], strlen(tok->args[0]));
+    if (r != CURVE25519_PUBKEY_LEN) {
+      log_warn(LD_DIR, "Bogus onion-key-ntor in routerinfo");
+      goto err;
+    }
+    router->onion_curve25519_pkey =
+      tor_malloc(sizeof(curve25519_public_key_t));
+    memcpy(router->onion_curve25519_pkey->public_key,
+           k, CURVE25519_PUBKEY_LEN);
+  }
+
   tok = find_by_keyword(tokens, K_SIGNING_KEY);
   router->identity_pkey = tok->key;
   tok->key = NULL; /* Prevent free */
@@ -1938,6 +1956,8 @@ routerstatus_parse_entry_from_string(memarea_t *area,
         tor_version_supports_microdescriptors(tok->args[0]);
       rs->version_supports_optimistic_data =
         tor_version_as_new_as(tok->args[0], "0.2.3.1-alpha");
+      rs->version_supports_extend2_cells =
+        tor_version_as_new_as(tok->args[0], "0.2.4.7-alpha");
     }
     if (vote_rs) {
       vote_rs->version = tor_strdup(tok->args[0]);
@@ -4243,6 +4263,22 @@ microdescs_parse_from_string(const char *s, const char *eos,
     md->onion_pkey = tok->key;
     tok->key = NULL;
 
+    if ((tok = find_opt_by_keyword(tokens, K_ONION_KEY_NTOR))) {
+      uint8_t k[CURVE25519_PUBKEY_LEN+32];
+      int r;
+      tor_assert(tok->n_args >= 1);
+      r = base64_decode((char*)k, sizeof(k),
+                        tok->args[0], strlen(tok->args[0]));
+      if (r != CURVE25519_PUBKEY_LEN) {
+        log_warn(LD_DIR, "Bogus onion-key-ntor in microdesc");
+        goto next;
+      }
+      md->onion_curve25519_pkey =
+        tor_malloc(sizeof(curve25519_public_key_t));
+      memcpy(md->onion_curve25519_pkey->public_key,
+             k, CURVE25519_PUBKEY_LEN);
+    }
+
     {
       smartlist_t *a_lines = find_all_by_keyword(tokens, K_A);
       if (a_lines) {