New and frightening code to implement fast-path first-hop CREATE_FAST cells. Watch out when we bump the version to 0.1.0.6-rc!

svn:r4162

10 files changed, 201 insertions, 70 deletions

diff --git a/doc/tor-spec.txt b/doc/tor-spec.txt
index bf122a19bd..d165f8bc0e 100644
--- a/doc/tor-spec.txt
+++ b/doc/tor-spec.txt
@@ -214,7 +214,7 @@ TODO: (very soon)
    When initializing the first hop of a circuit, the OP has already
    established the OR's identity and negotiated a secret key using TLS.
    Because of this, it is not always necessary for the OP to perform the
-   an set of public key operations to create a circuit.  In this case, the
+   public key operations to create a circuit.  In this case, the
    OP SHOULD send a CREATE_FAST cell instead of a CREATE cell for the first
    hop only.  The OR responds with a CREATED_FAST cell, and the circuit is
    created.
@@ -228,7 +228,7 @@ TODO: (very soon)
        Key material (Y)    [20 bytes]
        Derivative key data [20 bytes]
 
-   [Versions of Tor before 0.1.???? did not support these cell types;
+   [Versions of Tor before 0.1.0.6-rc did not support these cell types;
     clients should not send CREATE_FAST cells to older Tor servers.]
 
 4.2. Setting circuit keys
diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c
index 32841f8b9c..102230e61c 100644
--- a/src/or/circuitbuild.c
+++ b/src/or/circuitbuild.c
@@ -19,7 +19,8 @@ extern circuit_t *global_circuitlist;
 
 /********* END VARIABLES ************/
 
-static int circuit_deliver_create_cell(circuit_t *circ, char *payload);
+static int circuit_deliver_create_cell(circuit_t *circ,
+                                       uint8_t cell_type, char *payload);
 static int onion_pick_cpath_exit(circuit_t *circ, routerinfo_t *exit);
 static crypt_path_t *onion_next_hop_in_cpath(crypt_path_t *cpath);
 static int onion_next_router_in_cpath(circuit_t *circ, routerinfo_t **router);
@@ -374,7 +375,7 @@ void circuit_n_conn_done(connection_t *or_conn, int status) {
         }
       } else {
         /* pull the create cell out of circ->onionskin, and send it */
-        if (circuit_deliver_create_cell(circ, circ->onionskin) < 0) {
+        if (circuit_deliver_create_cell(circ,CELL_CREATE,circ->onionskin) < 0) {
           circuit_mark_for_close(circ);
           continue;
         }
@@ -384,7 +385,7 @@ void circuit_n_conn_done(connection_t *or_conn, int status) {
 }
 
 static int
-circuit_deliver_create_cell(circuit_t *circ, char *payload) {
+circuit_deliver_create_cell(circuit_t *circ, uint8_t cell_type, char *payload) {
   cell_t cell;
   uint16_t id;
 
@@ -392,6 +393,7 @@ circuit_deliver_create_cell(circuit_t *circ, char *payload) {
   tor_assert(circ->n_conn);
   tor_assert(circ->n_conn->type == CONN_TYPE_OR);
   tor_assert(payload);
+  tor_assert(cell_type == CELL_CREATE || cell_type == CELL_CREATE_FAST);
 
   id = get_unique_circ_id_by_conn(circ->n_conn);
   if (!id) {
@@ -402,7 +404,7 @@ circuit_deliver_create_cell(circuit_t *circ, char *payload) {
   circuit_set_circid_orconn(circ, id, circ->n_conn, N_CONN_CHANGED);
 
   memset(&cell, 0, sizeof(cell_t));
-  cell.command = CELL_CREATE;
+  cell.command = cell_type;
   cell.circ_id = circ->n_circ_id;
 
   memcpy(cell.payload, payload, ONIONSKIN_CHALLENGE_LEN);
@@ -434,6 +436,7 @@ int circuit_send_next_onion_skin(circuit_t *circ) {
   tor_assert(CIRCUIT_IS_ORIGIN(circ));
 
   if (circ->cpath->state == CPATH_STATE_CLOSED) {
+    uint8_t cell_type;
     log_fn(LOG_DEBUG,"First skin; sending create cell.");
 
     router = router_get_by_digest(circ->n_conn->identity_digest);
@@ -443,14 +446,30 @@ int circuit_send_next_onion_skin(circuit_t *circ) {
       return -1;
     }
 
-    if (onion_skin_create(router->onion_pkey,
-                          &(circ->cpath->handshake_state),
-                          payload) < 0) {
-      log_fn(LOG_WARN,"onion_skin_create (first hop) failed.");
-      return -1;
+    if (get_options()->ORPort || !router->platform ||
+        !tor_version_as_new_as(router->platform, "0.1.0.6-rc")) {
+      /* We are an OR, or we are connecting to an old Tor: we should
+       * send an old slow create cell.
+       */
+      cell_type = CELL_CREATE;
+      if (onion_skin_create(router->onion_pkey,
+                            &(circ->cpath->dh_handshake_state),
+                            payload) < 0) {
+        log_fn(LOG_WARN,"onion_skin_create (first hop) failed.");
+        return -1;
+      }
+    } else {
+      /* We are not an OR, and we building the first hop of a circuit to
+       * a new OR: we can be speedy. */
+      cell_type = CELL_CREATE_FAST;
+      memset(payload, 0, sizeof(payload));
+      crypto_rand(circ->cpath->fast_handshake_state,
+                  sizeof(circ->cpath->fast_handshake_state));
+      memcpy(payload, circ->cpath->fast_handshake_state,
+             sizeof(circ->cpath->fast_handshake_state));
     }
 
-    if (circuit_deliver_create_cell(circ, payload) < 0)
+    if (circuit_deliver_create_cell(circ, cell_type, payload) < 0)
       return -1;
 
     circ->cpath->state = CPATH_STATE_AWAITING_KEYS;
@@ -491,7 +510,7 @@ int circuit_send_next_onion_skin(circuit_t *circ) {
     memcpy(payload+2+4+ONIONSKIN_CHALLENGE_LEN, hop->identity_digest, DIGEST_LEN);
     payload_len = 2+4+ONIONSKIN_CHALLENGE_LEN+DIGEST_LEN;
 
-    if (onion_skin_create(router->onion_pkey, &(hop->handshake_state), onionskin) < 0) {
+    if (onion_skin_create(router->onion_pkey, &(hop->dh_handshake_state), onionskin) < 0) {
       log_fn(LOG_WARN,"onion_skin_create failed.");
       return -1;
     }
@@ -589,7 +608,7 @@ int circuit_extend(cell_t *cell, circuit_t *circ) {
   memcpy(circ->n_conn_id_digest, n_conn->identity_digest, DIGEST_LEN);
   log_fn(LOG_DEBUG,"n_conn is %s:%u",n_conn->address,n_conn->port);
 
-  if (circuit_deliver_create_cell(circ, onionskin) < 0)
+  if (circuit_deliver_create_cell(circ, CELL_CREATE, onionskin) < 0)
     return -1;
   return 0;
 }
@@ -648,13 +667,14 @@ int circuit_init_cpath_crypto(crypt_path_t *cpath, char *key_data, int reverse)
 
 /** A created or extended cell came back to us on the circuit,
  * and it included <b>reply</b> (the second DH key, plus KH).
+ * DOCDOC reply_type.
  *
  * Calculate the appropriate keys and digests, make sure KH is
  * correct, and initialize this hop of the cpath.
  *
  * Return -1 if we want to mark circ for close, else return 0.
  */
-int circuit_finish_handshake(circuit_t *circ, char *reply) {
+int circuit_finish_handshake(circuit_t *circ, uint8_t reply_type, char *reply) {
   unsigned char keys[CPATH_KEY_MATERIAL_LEN];
   crypt_path_t *hop;
 
@@ -670,16 +690,31 @@ int circuit_finish_handshake(circuit_t *circ, char *reply) {
   }
   tor_assert(hop->state == CPATH_STATE_AWAITING_KEYS);
 
-  if (onion_skin_client_handshake(hop->handshake_state, reply, keys,
-                                  DIGEST_LEN*2+CIPHER_KEY_LEN*2) < 0) {
-    log_fn(LOG_WARN,"onion_skin_client_handshake failed.");
+  if (reply_type == CELL_CREATED && hop->dh_handshake_state) {
+    if (onion_skin_client_handshake(hop->dh_handshake_state, reply, keys,
+                                    DIGEST_LEN*2+CIPHER_KEY_LEN*2) < 0) {
+      log_fn(LOG_WARN,"onion_skin_client_handshake failed.");
+      return -1;
+    }
+    /* 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, keys,
+                              DIGEST_LEN*2+CIPHER_KEY_LEN*2) < 0) {
+      log_fn(LOG_WARN,"fast_client_handshake failed.");
+      return -1;
+    }
+    memcpy(hop->handshake_digest, reply+DIGEST_LEN, DIGEST_LEN);
+  } else {
+    log_fn(LOG_WARN,"CREATED cell type did not match CREATE cell type.");
     return -1;
   }
 
-  crypto_dh_free(hop->handshake_state); /* don't need it anymore */
-  hop->handshake_state = NULL;
-  /* Remember hash of g^xy */
-  memcpy(hop->handshake_digest, reply+DH_KEY_LEN, DIGEST_LEN);
+  if (hop->dh_handshake_state) {
+    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));
 
   if (circuit_init_cpath_crypto(hop, keys, 0)<0) {
     return -1;
@@ -742,7 +777,7 @@ int circuit_truncated(circuit_t *circ, crypt_path_t *layer) {
 /** Given a response payload and keys, initialize, then send a created
  * cell back.
  */
-int onionskin_answer(circuit_t *circ, unsigned char *payload, unsigned char *keys) {
+int onionskin_answer(circuit_t *circ, uint8_t cell_type, unsigned char *payload, unsigned char *keys) {
   cell_t cell;
   crypt_path_t *tmp_cpath;
 
@@ -750,14 +785,15 @@ int onionskin_answer(circuit_t *circ, unsigned char *payload, unsigned char *key
   tmp_cpath->magic = CRYPT_PATH_MAGIC;
 
   memset(&cell, 0, sizeof(cell_t));
-  cell.command = CELL_CREATED;
+  cell.command = cell_type;
   cell.circ_id = circ->p_circ_id;
 
   circ->state = CIRCUIT_STATE_OPEN;
 
   log_fn(LOG_DEBUG,"Entering.");
 
-  memcpy(cell.payload, payload, ONIONSKIN_REPLY_LEN);
+  memcpy(cell.payload, payload,
+         cell_type == CELL_CREATED ? ONIONSKIN_REPLY_LEN : DIGEST_LEN*2);
 
   log_fn(LOG_INFO,"init digest forward 0x%.8x, backward 0x%.8x.",
          (unsigned int)*(uint32_t*)(keys), (unsigned int)*(uint32_t*)(keys+20));
@@ -773,7 +809,10 @@ int onionskin_answer(circuit_t *circ, unsigned char *payload, unsigned char *key
   tmp_cpath->magic = 0;
   tor_free(tmp_cpath);
 
-  memcpy(circ->handshake_digest, cell.payload+DH_KEY_LEN, DIGEST_LEN);
+  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);
 
   connection_or_write_cell_to_buf(&cell, circ->p_conn);
   log_fn(LOG_DEBUG,"Finished sending 'created' cell.");
@@ -1457,4 +1496,3 @@ onion_append_hop(crypt_path_t **head_ptr, routerinfo_t *choice) {
 
   return 0;
 }
-
diff --git a/src/or/circuitlist.c b/src/or/circuitlist.c
index af54ae90d9..93df616922 100644
--- a/src/or/circuitlist.c
+++ b/src/or/circuitlist.c
@@ -274,8 +274,8 @@ circuit_free_cpath_node(crypt_path_t *victim) {
     crypto_free_digest_env(victim->f_digest);
   if (victim->b_digest)
     crypto_free_digest_env(victim->b_digest);
-  if (victim->handshake_state)
-    crypto_dh_free(victim->handshake_state);
+  if (victim->dh_handshake_state)
+    crypto_dh_free(victim->dh_handshake_state);
   victim->magic = 0xDEADBEEFu;
   tor_free(victim);
 }
@@ -613,10 +613,10 @@ void assert_cpath_layer_ok(const crypt_path_t *cp)
       tor_assert(cp->b_crypto);
       /* fall through */
     case CPATH_STATE_CLOSED:
-      tor_assert(!cp->handshake_state);
+      tor_assert(!cp->dh_handshake_state);
       break;
     case CPATH_STATE_AWAITING_KEYS:
-      tor_assert(cp->handshake_state);
+      /* tor_assert(cp->dh_handshake_state); */
       break;
     default:
       log_fn(LOG_ERR,"Unexpected state %d",cp->state);
diff --git a/src/or/command.c b/src/or/command.c
index 30b81b213b..5f5fd5f3ac 100644
--- a/src/or/command.c
+++ b/src/or/command.c
@@ -98,6 +98,7 @@ void command_process_cell(cell_t *cell, connection_t *conn) {
       /* do nothing */
       break;
     case CELL_CREATE:
+    case CELL_CREATE_FAST:
       ++stats_n_create_cells_processed;
 #ifdef KEEP_TIMING_STATS
       ++num_create;
@@ -108,6 +109,7 @@ void command_process_cell(cell_t *cell, connection_t *conn) {
 #endif
       break;
     case CELL_CREATED:
+    case CELL_CREATED_FAST:
       ++stats_n_created_cells_processed;
 #ifdef KEEP_TIMING_STATS
       ++num_created;
@@ -181,18 +183,33 @@ static void command_process_create_cell(cell_t *cell, connection_t *conn) {
   }
 
   circ = circuit_new(cell->circ_id, conn);
-  circ->state = CIRCUIT_STATE_ONIONSKIN_PENDING;
   circ->purpose = CIRCUIT_PURPOSE_OR;
+  circ->state = CIRCUIT_STATE_ONIONSKIN_PENDING;
+  if (cell->command == CELL_CREATE) {
+    memcpy(circ->onionskin, cell->payload, ONIONSKIN_CHALLENGE_LEN);
 
-  memcpy(circ->onionskin, cell->payload, ONIONSKIN_CHALLENGE_LEN);
-
-  /* hand it off to the cpuworkers, and then return */
-  if (assign_to_cpuworker(NULL, CPUWORKER_TASK_ONION, circ) < 0) {
-    log_fn(LOG_WARN,"Failed to hand off onionskin. Closing.");
-    circuit_mark_for_close(circ);
-    return;
+    /* hand it off to the cpuworkers, and then return */
+    if (assign_to_cpuworker(NULL, CPUWORKER_TASK_ONION, circ) < 0) {
+      log_fn(LOG_WARN,"Failed to hand off onionskin. Closing.");
+      circuit_mark_for_close(circ);
+      return;
+    }
+    log_fn(LOG_DEBUG,"success: handed off onionskin.");
+  } else {
+    unsigned char keys[CPATH_KEY_MATERIAL_LEN];
+    unsigned char reply[DIGEST_LEN*2];
+    tor_assert(cell->command == CELL_CREATE_FAST);
+    if (fast_server_handshake(cell->payload, reply, keys, sizeof(keys))<0) {
+      log_fn(LOG_WARN,"Failed to generate key material. Closing.");
+      circuit_mark_for_close(circ);
+      return;
+    }
+    if (onionskin_answer(circ, CELL_CREATED_FAST, reply, keys)<0) {
+      log_fn(LOG_WARN,"Failed to reply to CREATE_FAST cell. Closing.");
+      circuit_mark_for_close(circ);
+      return;
+    }
   }
-  log_fn(LOG_DEBUG,"success: handed off onionskin.");
 }
 
 /** Process a 'created' <b>cell</b> that just arrived from <b>conn</b>. Find the circuit
@@ -220,7 +237,7 @@ static void command_process_created_cell(cell_t *cell, connection_t *conn) {
 
   if (CIRCUIT_IS_ORIGIN(circ)) { /* we're the OP. Handshake this. */
     log_fn(LOG_DEBUG,"at OP. Finishing handshake.");
-    if (circuit_finish_handshake(circ, cell->payload) < 0) {
+    if (circuit_finish_handshake(circ, cell->command, cell->payload) < 0) {
       log_fn(LOG_WARN,"circuit_finish_handshake failed.");
       circuit_mark_for_close(circ);
       return;
@@ -318,4 +335,3 @@ static void command_process_destroy_cell(cell_t *cell, connection_t *conn) {
     }
   }
 }
-
diff --git a/src/or/cpuworker.c b/src/or/cpuworker.c
index 6a9005b25b..3a1a61a8ea 100644
--- a/src/or/cpuworker.c
+++ b/src/or/cpuworker.c
@@ -24,7 +24,7 @@ const char cpuworker_c_id[] = "$Id$";
 /** How many bytes are sent from tor to the cpuworker? */
 #define LEN_ONION_QUESTION (1+TAG_LEN+ONIONSKIN_CHALLENGE_LEN)
 /** How many bytes are sent from the cpuworker back to tor? */
-#define LEN_ONION_RESPONSE (1+TAG_LEN+ONIONSKIN_REPLY_LEN+40+32)
+#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;
@@ -159,7 +159,7 @@ int connection_cpu_process_inbuf(connection_t *conn) {
       goto done_processing;
     }
     tor_assert(circ->p_conn);
-    if (onionskin_answer(circ, buf+TAG_LEN, buf+TAG_LEN+ONIONSKIN_REPLY_LEN) < 0) {
+    if (onionskin_answer(circ, CELL_CREATED, buf+TAG_LEN, buf+TAG_LEN+ONIONSKIN_REPLY_LEN) < 0) {
       log_fn(LOG_WARN,"onionskin_answer failed. Closing.");
       circuit_mark_for_close(circ);
       goto done_processing;
@@ -205,7 +205,7 @@ static int cpuworker_main(void *data) {
   int fd;
 
   /* variables for onion processing */
-  unsigned char keys[40+32];
+  unsigned char keys[CPATH_KEY_MATERIAL_LEN];
   unsigned char reply_to_proxy[ONIONSKIN_REPLY_LEN];
   unsigned char buf[LEN_ONION_RESPONSE];
   char tag[TAG_LEN];
@@ -248,7 +248,7 @@ static int cpuworker_main(void *data) {
 
     if (question_type == CPUWORKER_TASK_ONION) {
       if (onion_skin_server_handshake(question, onion_key, last_onion_key,
-          reply_to_proxy, keys, 40+32) < 0) {
+          reply_to_proxy, keys, CPATH_KEY_MATERIAL_LEN) < 0) {
         /* failure */
         log_fn(LOG_INFO,"onion_skin_server_handshake failed.");
         memset(buf,0,LEN_ONION_RESPONSE); /* send all zeros for failure */
@@ -258,7 +258,7 @@ static int cpuworker_main(void *data) {
         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,40+32);
+        memcpy(buf+1+TAG_LEN+ONIONSKIN_REPLY_LEN,keys,CPATH_KEY_MATERIAL_LEN);
       }
       if (write_all(fd, buf, LEN_ONION_RESPONSE, 1) != LEN_ONION_RESPONSE) {
         log_fn(LOG_ERR,"writing response buf failed. Exiting.");
diff --git a/src/or/onion.c b/src/or/onion.c
index 4d354abbd7..c24612957f 100644
--- a/src/or/onion.c
+++ b/src/or/onion.c
@@ -199,7 +199,7 @@ onion_skin_create(crypto_pk_env_t *dest_router_key,
  * next key_out_len bytes of key material in key_out.
  */
 int
-onion_skin_server_handshake(char *onion_skin, /* ONIONSKIN_CHALLENGE_LEN bytes */
+onion_skin_server_handshake(const char *onion_skin, /* ONIONSKIN_CHALLENGE_LEN bytes */
                             crypto_pk_env_t *private_key,
                             crypto_pk_env_t *prev_private_key,
                             char *handshake_reply_out, /* ONIONSKIN_REPLY_LEN bytes */
@@ -287,9 +287,9 @@ onion_skin_server_handshake(char *onion_skin, /* ONIONSKIN_CHALLENGE_LEN bytes *
  */
 int
 onion_skin_client_handshake(crypto_dh_env_t *handshake_state,
-                            char *handshake_reply, /* Must be ONIONSKIN_REPLY_LEN bytes */
-                            char *key_out,
-                            size_t key_out_len)
+            const char *handshake_reply, /* Must be ONIONSKIN_REPLY_LEN bytes */
+            char *key_out,
+            size_t key_out_len)
 {
   int len;
   char *key_material=NULL;
@@ -329,6 +329,69 @@ onion_skin_client_handshake(crypto_dh_env_t *handshake_state,
   return 0;
 }
 
+int
+fast_server_handshake(const char *key_in, /* DIGEST_LEN bytes */
+                      char *handshake_reply_out, /* DIGEST_LEN*2 bytes */
+                      char *key_out,
+                      size_t key_out_len)
+{
+  char tmp[DIGEST_LEN+DIGEST_LEN+1];
+  char digest[DIGEST_LEN];
+  int i;
+
+  if (crypto_rand(handshake_reply_out, DIGEST_LEN)<0)
+    return -1;
+
+  memcpy(tmp, key_in, DIGEST_LEN);
+  memcpy(tmp+DIGEST_LEN, handshake_reply_out, DIGEST_LEN);
+  tmp[DIGEST_LEN+DIGEST_LEN] = 0;
+  crypto_digest(handshake_reply_out+DIGEST_LEN, tmp, sizeof(tmp));
+
+  for (i = 0; i*DIGEST_LEN < key_out_len; ++i) {
+    size_t len;
+    tmp[DIGEST_LEN+DIGEST_LEN] = i+1;
+    crypto_digest(digest, tmp, sizeof(tmp));
+    len = key_out_len - i*DIGEST_LEN;
+    if (len > DIGEST_LEN) len = DIGEST_LEN;
+    memcpy(key_out+i*DIGEST_LEN, digest, len);
+  }
+
+  return 0;
+}
+
+int
+fast_client_handshake(const char *handshake_state, /* DIGEST_LEN bytes */
+                      const char *handshake_reply_out, /* DIGEST_LEN*2 bytes */
+                      char *key_out,
+                      size_t key_out_len)
+{
+  char tmp[DIGEST_LEN+DIGEST_LEN+1];
+  char digest[DIGEST_LEN];
+  int i;
+
+  memcpy(tmp, handshake_state, DIGEST_LEN);
+  memcpy(tmp+DIGEST_LEN, handshake_reply_out, DIGEST_LEN);
+  tmp[DIGEST_LEN+DIGEST_LEN] = 0;
+  crypto_digest(digest, tmp, sizeof(tmp));
+
+  if (memcmp(digest, handshake_reply_out+DIGEST_LEN, DIGEST_LEN)) {
+    /* H(K) does *not* match. Something fishy. */
+    log_fn(LOG_WARN,"Digest DOES NOT MATCH on fast handshake. Bug or attack.");
+    return -1;
+  }
+
+  for (i = 0; i*DIGEST_LEN < key_out_len; ++i) {
+    size_t len;
+    tmp[DIGEST_LEN+DIGEST_LEN] = i+1;
+    crypto_digest(digest, tmp, sizeof(tmp));
+    len = key_out_len - i*DIGEST_LEN;
+    if (len > DIGEST_LEN) len = DIGEST_LEN;
+    memcpy(key_out+i*DIGEST_LEN, digest, len);
+  }
+
+  return 0;
+}
+
 /** Remove all circuits from the pending list.  Called from tor_free_all. */
 void
 clear_pending_onions(void)
diff --git a/src/or/or.h b/src/or/or.h
index c874e6ffdd..31922901ce 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -474,6 +474,8 @@ typedef enum {
 #define CELL_CREATED 2
 #define CELL_RELAY 3
 #define CELL_DESTROY 4
+#define CELL_CREATE_FAST 5
+#define CELL_CREATED_FAST 6
 
 /* people behind fascist firewalls use only these ports */
 #define REQUIRED_FIREWALL_DIRPORT 80
@@ -749,7 +751,8 @@ struct crypt_path_t {
 
   /** Current state of Diffie-Hellman key negotiation with the OR at this
    * step. */
-  crypto_dh_env_t *handshake_state;
+  crypto_dh_env_t *dh_handshake_state;
+  char fast_handshake_state[DIGEST_LEN];
   /** Negotiated key material shared with the OR at this step. */
   char handshake_digest[DIGEST_LEN];/* KH in tor-spec.txt */
 
@@ -1158,9 +1161,9 @@ int circuit_send_next_onion_skin(circuit_t *circ);
 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, char *key_data, int reverse);
-int circuit_finish_handshake(circuit_t *circ, char *reply);
+int circuit_finish_handshake(circuit_t *circ, uint8_t cell_type, char *reply);
 int circuit_truncated(circuit_t *circ, crypt_path_t *layer);
-int onionskin_answer(circuit_t *circ, unsigned char *payload, unsigned char *keys);
+int onionskin_answer(circuit_t *circ, uint8_t cell_type, unsigned char *payload, unsigned char *keys);
 int circuit_all_predicted_ports_handled(time_t now, int *need_uptime,
                                         int *need_capacity);
 
@@ -1552,7 +1555,7 @@ int onion_skin_create(crypto_pk_env_t *router_key,
                       crypto_dh_env_t **handshake_state_out,
                       char *onion_skin_out);
 
-int onion_skin_server_handshake(char *onion_skin,
+int onion_skin_server_handshake(const char *onion_skin,
                                 crypto_pk_env_t *private_key,
                                 crypto_pk_env_t *prev_private_key,
                                 char *handshake_reply_out,
@@ -1560,9 +1563,19 @@ int onion_skin_server_handshake(char *onion_skin,
                                 size_t key_out_len);
 
 int onion_skin_client_handshake(crypto_dh_env_t *handshake_state,
-                             char *handshake_reply,
-                             char *key_out,
-                             size_t key_out_len);
+                                const char *handshake_reply,
+                                char *key_out,
+                                size_t key_out_len);
+
+int fast_server_handshake(const char *key_in,
+                          char *handshake_reply_out,
+                          char *key_out,
+                          size_t key_out_len);
+
+int fast_client_handshake(const char *handshake_state,
+                          const char *handshake_reply_out,
+                          char *key_out,
+                          size_t key_out_len);
 
 void clear_pending_onions(void);
 
diff --git a/src/or/relay.c b/src/or/relay.c
index 0340d5b2a6..cd237e020a 100644
--- a/src/or/relay.c
+++ b/src/or/relay.c
@@ -882,7 +882,8 @@ connection_edge_process_relay_cell(cell_t *cell, circuit_t *circ,
         return 0;
       }
       log_fn(LOG_DEBUG,"Got an extended cell! Yay.");
-      if (circuit_finish_handshake(circ, cell->payload+RELAY_HEADER_SIZE) < 0) {
+      if (circuit_finish_handshake(circ, CELL_CREATED,
+                                   cell->payload+RELAY_HEADER_SIZE) < 0) {
         log_fn(LOG_WARN,"circuit_finish_handshake failed.");
         return -1;
       }
diff --git a/src/or/rendclient.c b/src/or/rendclient.c
index 8ef23710dd..4e87146d52 100644
--- a/src/or/rendclient.c
+++ b/src/or/rendclient.c
@@ -83,11 +83,11 @@ rend_client_send_introduction(circuit_t *introcirc, circuit_t *rendcirc) {
     cpath = rendcirc->build_state->pending_final_cpath =
       tor_malloc_zero(sizeof(crypt_path_t));
     cpath->magic = CRYPT_PATH_MAGIC;
-    if (!(cpath->handshake_state = crypto_dh_new())) {
+    if (!(cpath->dh_handshake_state = crypto_dh_new())) {
       log_fn(LOG_WARN, "Couldn't allocate DH");
       goto err;
     }
-    if (crypto_dh_generate_public(cpath->handshake_state)<0) {
+    if (crypto_dh_generate_public(cpath->dh_handshake_state)<0) {
       log_fn(LOG_WARN, "Couldn't generate g^x");
       goto err;
     }
@@ -103,7 +103,7 @@ rend_client_send_introduction(circuit_t *introcirc, circuit_t *rendcirc) {
   strncpy(tmp, rendcirc->build_state->chosen_exit_name, (MAX_NICKNAME_LEN+1)); /* nul pads */
   memcpy(tmp+MAX_NICKNAME_LEN+1, rendcirc->rend_cookie, REND_COOKIE_LEN);
 #endif
-  if (crypto_dh_get_public(cpath->handshake_state,
+  if (crypto_dh_get_public(cpath->dh_handshake_state,
 #if 0
                            tmp+1+MAX_HEX_NICKNAME_LEN+1+REND_COOKIE_LEN,
 #else
@@ -338,8 +338,8 @@ rend_client_receive_rendezvous(circuit_t *circ, const char *request, size_t requ
   tor_assert(circ->build_state);
   tor_assert(circ->build_state->pending_final_cpath);
   hop = circ->build_state->pending_final_cpath;
-  tor_assert(hop->handshake_state);
-  if (crypto_dh_compute_secret(hop->handshake_state, request, DH_KEY_LEN,
+  tor_assert(hop->dh_handshake_state);
+  if (crypto_dh_compute_secret(hop->dh_handshake_state, request, DH_KEY_LEN,
                                keys, DIGEST_LEN+CPATH_KEY_MATERIAL_LEN)<0) {
     log_fn(LOG_WARN, "Couldn't complete DH handshake");
     goto err;
@@ -354,8 +354,8 @@ rend_client_receive_rendezvous(circuit_t *circ, const char *request, size_t requ
     goto err;
   }
 
-  crypto_dh_free(hop->handshake_state);
-  hop->handshake_state = NULL;
+  crypto_dh_free(hop->dh_handshake_state);
+  hop->dh_handshake_state = NULL;
 
   /* All is well. Extend the circuit. */
   circ->purpose = CIRCUIT_PURPOSE_C_REND_JOINED;
diff --git a/src/or/rendservice.c b/src/or/rendservice.c
index aa39f76764..9432440eb7 100644
--- a/src/or/rendservice.c
+++ b/src/or/rendservice.c
@@ -511,7 +511,7 @@ rend_service_introduce(circuit_t *circuit, const char *request, size_t request_l
   cpath->magic = CRYPT_PATH_MAGIC;
   launched->build_state->expiry_time = time(NULL) + MAX_REND_TIMEOUT;
 
-  cpath->handshake_state = dh;
+  cpath->dh_handshake_state = dh;
   dh = NULL;
   if (circuit_init_cpath_crypto(cpath,keys+DIGEST_LEN,1)<0)
     goto err;
@@ -722,7 +722,7 @@ rend_service_rendezvous_has_opened(circuit_t *circuit)
 
   /* All we need to do is send a RELAY_RENDEZVOUS1 cell... */
   memcpy(buf, circuit->rend_cookie, REND_COOKIE_LEN);
-  if (crypto_dh_get_public(hop->handshake_state,
+  if (crypto_dh_get_public(hop->dh_handshake_state,
                            buf+REND_COOKIE_LEN, DH_KEY_LEN)<0) {
     log_fn(LOG_WARN,"Couldn't get DH public key");
     goto err;
@@ -738,8 +738,8 @@ rend_service_rendezvous_has_opened(circuit_t *circuit)
     goto err;
   }
 
-  crypto_dh_free(hop->handshake_state);
-  hop->handshake_state = NULL;
+  crypto_dh_free(hop->dh_handshake_state);
+  hop->dh_handshake_state = NULL;
 
   /* Append the cpath entry. */
   hop->state = CPATH_STATE_OPEN;