Merge branch 'bug6177_squashed'

12 files changed, 2101 insertions, 250 deletions

diff --git a/changes/bug6177 b/changes/bug6177
new file mode 100644
index 000000000..12ab43aa4
--- /dev/null
+++ b/changes/bug6177
@@ -0,0 +1,5 @@
+  o Code simplification and refactoring:
+    - Add replaycache_t structure, functions and unit tests, for future use
+      in refactoring rend_service_introduce() for bug 6177.
+    - Refactor rend_service_introduce() to be more clear to read, improve,
+      debug, and test. Bug 6177.
diff --git a/src/or/Makefile.am b/src/or/Makefile.am
index 3cc789a1b..27eb607cf 100644
--- a/src/or/Makefile.am
+++ b/src/or/Makefile.am
@@ -48,6 +48,7 @@ libtor_a_SOURCES = \
 	rendmid.c				\
 	rendservice.c				\
 	rephist.c				\
+	replaycache.c				\
 	router.c				\
 	routerlist.c				\
 	routerparse.c				\
@@ -114,6 +115,7 @@ noinst_HEADERS = \
 	rendmid.h				\
 	rendservice.h				\
 	rephist.h				\
+	replaycache.h				\
 	router.h				\
 	routerlist.h				\
 	routerparse.h				\
diff --git a/src/or/or.h b/src/or/or.h
index b6cffd4be..2ce95c661 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -98,6 +98,7 @@
 #include "address.h"
 #include "compat_libevent.h"
 #include "ht.h"
+#include "replaycache.h"
 
 /* These signals are defined to help handle_control_signal work.
  */
@@ -4214,12 +4215,15 @@ typedef struct rend_intro_point_t {
    * intro point. */
   unsigned int rend_service_note_removing_intro_point_called : 1;
 
-  /** (Service side only) A digestmap recording the INTRODUCE2 cells
-   * this intro point's circuit has received.  Each key is the digest
-   * of the RSA-encrypted part of a received INTRODUCE2 cell; each
-   * value is a pointer to the time_t at which the cell was received.
-   * This digestmap is used to prevent replay attacks. */
-  digestmap_t *accepted_intro_rsa_parts;
+  /** (Service side only) A replay cache recording the RSA-encrypted parts
+   * of INTRODUCE2 cells this intro point's circuit has received.  This is
+   * used to prevent replay attacks. */
+  replaycache_t *accepted_intro_rsa_parts;
+
+  /** (Service side only) Count of INTRODUCE2 cells accepted from this
+   * intro point.
+   */
+  int accepted_introduce2_count;
 
   /** (Service side only) The time at which this intro point was first
    * published, or -1 if this intro point has not yet been
diff --git a/src/or/rendcommon.c b/src/or/rendcommon.c
index 4722690c1..f6b1bf9f6 100644
--- a/src/or/rendcommon.c
+++ b/src/or/rendcommon.c
@@ -439,7 +439,7 @@ rend_intro_point_free(rend_intro_point_t *intro)
   crypto_pk_free(intro->intro_key);
 
   if (intro->accepted_intro_rsa_parts != NULL) {
-    digestmap_free(intro->accepted_intro_rsa_parts, _tor_free);
+    replaycache_free(intro->accepted_intro_rsa_parts);
   }
 
   tor_free(intro);
diff --git a/src/or/rendservice.c b/src/or/rendservice.c
index daa1651af..3c5d821d4 100644
--- a/src/or/rendservice.c
+++ b/src/or/rendservice.c
@@ -7,6 +7,8 @@
  * \brief The hidden-service side of rendezvous functionality.
  **/
 
+#define RENDSERVICE_PRIVATE
+
 #include "or.h"
 #include "circuitbuild.h"
 #include "circuitlist.h"
@@ -21,6 +23,7 @@
 #include "router.h"
 #include "relay.h"
 #include "rephist.h"
+#include "replaycache.h"
 #include "routerlist.h"
 #include "routerparse.h"
 
@@ -28,6 +31,10 @@ static origin_circuit_t *find_intro_circuit(rend_intro_point_t *intro,
                                             const char *pk_digest);
 static rend_intro_point_t *find_intro_point(origin_circuit_t *circ);
 
+static extend_info_t *find_rp_for_intro(
+    const rend_intro_cell_t *intro,
+    uint8_t *need_free_out, char **err_msg_out);
+
 static int intro_point_accepted_intro_count(rend_intro_point_t *intro);
 static int intro_point_should_expire_now(rend_intro_point_t *intro,
                                          time_t now);
@@ -36,6 +43,22 @@ static int rend_service_load_keys(struct rend_service_t *s);
 static int rend_service_load_auth_keys(struct rend_service_t *s,
                                        const char *hfname);
 
+static ssize_t rend_service_parse_intro_for_v0_or_v1(
+    rend_intro_cell_t *intro,
+    const uint8_t *buf,
+    size_t plaintext_len,
+    char **err_msg_out);
+static ssize_t rend_service_parse_intro_for_v2(
+    rend_intro_cell_t *intro,
+    const uint8_t *buf,
+    size_t plaintext_len,
+    char **err_msg_out);
+static ssize_t rend_service_parse_intro_for_v3(
+    rend_intro_cell_t *intro,
+    const uint8_t *buf,
+    size_t plaintext_len,
+    char **err_msg_out);
+
 /** Represents the mapping from a virtual port of a rendezvous service to
  * a real port on some IP.
  */
@@ -95,16 +118,12 @@ typedef struct rend_service_t {
                          * up-to-date. */
   time_t next_upload_time; /**< Scheduled next hidden service descriptor
                             * upload time. */
-  /** Map from digests of Diffie-Hellman values INTRODUCE2 to time_t
-   * of when they were received.  Clients may send INTRODUCE1 cells
-   * for the same rendezvous point through two or more different
-   * introduction points; when they do, this digestmap keeps us from
-   * launching multiple simultaneous attempts to connect to the same
-   * rend point. */
-  digestmap_t *accepted_intro_dh_parts;
-  /** Time at which we last removed expired values from
-   * accepted_intro_dh_parts. */
-  time_t last_cleaned_accepted_intro_dh_parts;
+  /** Replay cache for Diffie-Hellman values of INTRODUCE2 cells, to
+   * detect repeats.  Clients may send INTRODUCE1 cells for the same
+   * rendezvous point through two or more different introduction points;
+   * when they do, this keeps us from launching multiple simultaneous attempts
+   * to connect to the same rend point. */
+  replaycache_t *accepted_intro_dh_parts;
 } rend_service_t;
 
 /** A list of rend_service_t's for services run on this OP.
@@ -177,7 +196,9 @@ rend_service_free(rend_service_t *service)
       rend_authorized_client_free(c););
     smartlist_free(service->clients);
   }
-  digestmap_free(service->accepted_intro_dh_parts, _tor_free);
+  if (service->accepted_intro_dh_parts) {
+    replaycache_free(service->accepted_intro_dh_parts);
+  }
   tor_free(service);
 }
 
@@ -955,26 +976,6 @@ rend_check_authorization(rend_service_t *service,
   return 1;
 }
 
-/** Remove elements from <b>service</b>'s replay cache that are old enough to
- * be noticed by timestamp checking. */
-static void
-clean_accepted_intro_dh_parts(rend_service_t *service, time_t now)
-{
-  const time_t cutoff = now - REND_REPLAY_TIME_INTERVAL;
-
-  service->last_cleaned_accepted_intro_dh_parts = now;
-  if (!service->accepted_intro_dh_parts)
-    return;
-
-  DIGESTMAP_FOREACH_MODIFY(service->accepted_intro_dh_parts, digest,
-                           time_t *, t) {
-    if (*t < cutoff) {
-      tor_free(t);
-      MAP_DEL_CURRENT(digest);
-    }
-  } DIGESTMAP_FOREACH_END;
-}
-
 /** Called when <b>intro</b> will soon be removed from
  * <b>service</b>'s list of intro points. */
 static void
@@ -1082,38 +1083,50 @@ rend_service_note_removing_intro_point(rend_service_t *service,
 /** Respond to an INTRODUCE2 cell by launching a circuit to the chosen
  * rendezvous point.
  */
- /* XXXX024 this function sure could use some organizing. -RD */
 int
 rend_service_introduce(origin_circuit_t *circuit, const uint8_t *request,
                        size_t request_len)
 {
-  int status = 0;
-  char *ptr, *r_cookie;
-  extend_info_t *extend_info = NULL;
+  /* Global status stuff */
+  int status = 0, result;
+  const or_options_t *options = get_options();
+  char *err_msg = NULL;
+  const char *stage_descr = NULL;
+  int reason = END_CIRC_REASON_TORPROTOCOL;
+  /* Service/circuit/key stuff we can learn before parsing */
+  char serviceid[REND_SERVICE_ID_LEN_BASE32+1];
+  rend_service_t *service = NULL;
+  rend_intro_point_t *intro_point = NULL;
+  crypto_pk_t *intro_key = NULL;
+  /* Parsed cell */
+  rend_intro_cell_t *parsed_req = NULL;
+  /* Rendezvous point */
+  extend_info_t *rp = NULL;
+  /*
+   * We need to look up and construct the extend_info_t for v0 and v1,
+   * but all the info is in the cell and it's constructed by the parser
+   * for v2 and v3, so freeing it would be a double-free.  Use this to
+   * keep track of whether we should free it.
+   */
+  uint8_t need_rp_free = 0;
+  /* XXX not handled yet */
   char buf[RELAY_PAYLOAD_SIZE];
   char keys[DIGEST_LEN+CPATH_KEY_MATERIAL_LEN]; /* Holds KH, Df, Db, Kf, Kb */
-  rend_service_t *service;
-  rend_intro_point_t *intro_point;
-  int r, i, v3_shift = 0;
-  size_t len, keylen;
+  int i;
   crypto_dh_t *dh = NULL;
   origin_circuit_t *launched = NULL;
   crypt_path_t *cpath = NULL;
-  char serviceid[REND_SERVICE_ID_LEN_BASE32+1];
   char hexcookie[9];
   int circ_needs_uptime;
-  int reason = END_CIRC_REASON_TORPROTOCOL;
-  crypto_pk_t *intro_key;
   char intro_key_digest[DIGEST_LEN];
-  int auth_type;
   size_t auth_len = 0;
   char auth_data[REND_DESC_COOKIE_LEN];
-  crypto_digest_t *digest = NULL;
   time_t now = time(NULL);
   char diffie_hellman_hash[DIGEST_LEN];
-  time_t *access_time;
-  const or_options_t *options = get_options();
+  time_t elapsed;
+  int replay;
 
+  /* Do some initial validation and logging before we parse the cell */
   if (circuit->_base.purpose != CIRCUIT_PURPOSE_S_INTRO) {
     log_warn(LD_PROTOCOL,
              "Got an INTRODUCE2 over a non-introduction circuit %d.",
@@ -1126,218 +1139,139 @@ rend_service_introduce(origin_circuit_t *circuit, const uint8_t *request,
 #endif
   tor_assert(circuit->rend_data);
 
+  /* We'll use this in a bazillion log messages */
   base32_encode(serviceid, REND_SERVICE_ID_LEN_BASE32+1,
                 circuit->rend_data->rend_pk_digest, REND_SERVICE_ID_LEN);
-  log_info(LD_REND, "Received INTRODUCE2 cell for service %s on circ %d.",
-           escaped(serviceid), circuit->_base.n_circ_id);
-
-  /* min key length plus digest length plus nickname length */
-  if (request_len < DIGEST_LEN+REND_COOKIE_LEN+(MAX_NICKNAME_LEN+1)+
-      DH_KEY_LEN+42) {
-    log_warn(LD_PROTOCOL, "Got a truncated INTRODUCE2 cell on circ %d.",
-             circuit->_base.n_circ_id);
-    goto err;
-  }
 
   /* look up service depending on circuit. */
-  service = rend_service_get_by_pk_digest(
-                circuit->rend_data->rend_pk_digest);
+  service =
+    rend_service_get_by_pk_digest(circuit->rend_data->rend_pk_digest);
   if (!service) {
-    log_warn(LD_BUG, "Internal error: Got an INTRODUCE2 cell on an intro "
+    log_warn(LD_BUG,
+             "Internal error: Got an INTRODUCE2 cell on an intro "
              "circ for an unrecognized service %s.",
              escaped(serviceid));
     goto err;
   }
 
+  intro_point = find_intro_point(circuit);
+  if (intro_point == NULL) {
+    log_warn(LD_BUG,
+             "Internal error: Got an INTRODUCE2 cell on an "
+             "intro circ (for service %s) with no corresponding "
+             "rend_intro_point_t.",
+             escaped(serviceid));
+    goto err;
+  }
+
+  log_info(LD_REND, "Received INTRODUCE2 cell for service %s on circ %d.",
+           escaped(serviceid), circuit->_base.n_circ_id);
+
   /* use intro key instead of service key. */
   intro_key = circuit->intro_key;
 
-  /* first DIGEST_LEN bytes of request is intro or service pk digest */
-  crypto_pk_get_digest(intro_key, intro_key_digest);
-  if (tor_memneq(intro_key_digest, request, DIGEST_LEN)) {
-    base32_encode(serviceid, REND_SERVICE_ID_LEN_BASE32+1,
-                  (char*)request, REND_SERVICE_ID_LEN);
-    log_warn(LD_REND, "Got an INTRODUCE2 cell for the wrong service (%s).",
-             escaped(serviceid));
-    goto err;
+  tor_free(err_msg);
+  stage_descr = NULL;
+
+  stage_descr = "early parsing";
+  /* Early parsing pass (get pk, ciphertext); type 2 is INTRODUCE2 */
+  parsed_req =
+    rend_service_begin_parse_intro(request, request_len, 2, &err_msg);
+  if (!parsed_req) goto err;
+  else if (err_msg) {
+    log_info(LD_REND, "%s on circ %d.", err_msg, circuit->_base.n_circ_id);
+    tor_free(err_msg);
   }
 
-  keylen = crypto_pk_keysize(intro_key);
-  if (request_len < keylen+DIGEST_LEN) {
-    log_warn(LD_PROTOCOL,
-             "PK-encrypted portion of INTRODUCE2 cell was truncated.");
-    goto err;
+  stage_descr = "early validation";
+  /* Early validation of pk/ciphertext part */
+  result = rend_service_validate_intro_early(parsed_req, &err_msg);
+  if (result < 0) goto err;
+  else if (err_msg) {
+    log_info(LD_REND, "%s on circ %d.", err_msg, circuit->_base.n_circ_id);
+    tor_free(err_msg);
   }
 
-  intro_point = find_intro_point(circuit);
-  if (intro_point == NULL) {
-    log_warn(LD_BUG, "Internal error: Got an INTRODUCE2 cell on an intro circ "
-             "(for service %s) with no corresponding rend_intro_point_t.",
-             escaped(serviceid));
-    goto err;
+  /* make sure service replay caches are present */
+  if (!service->accepted_intro_dh_parts) {
+    service->accepted_intro_dh_parts =
+      replaycache_new(REND_REPLAY_TIME_INTERVAL,
+                      REND_REPLAY_TIME_INTERVAL);
   }
 
-  if (!service->accepted_intro_dh_parts)
-    service->accepted_intro_dh_parts = digestmap_new();
+  if (!intro_point->accepted_intro_rsa_parts) {
+    intro_point->accepted_intro_rsa_parts = replaycache_new(0, 0);
+  }
 
-  if (!intro_point->accepted_intro_rsa_parts)
-    intro_point->accepted_intro_rsa_parts = digestmap_new();
+  /* check for replay of PK-encrypted portion. */
+  replay = replaycache_add_test_and_elapsed(
+    intro_point->accepted_intro_rsa_parts,
+    parsed_req->ciphertext, parsed_req->ciphertext_len,
+    &elapsed);
 
-  {
-    char pkpart_digest[DIGEST_LEN];
-    /* Check for replay of PK-encrypted portion. */
-    crypto_digest(pkpart_digest, (char*)request+DIGEST_LEN, keylen);
-    access_time = digestmap_get(intro_point->accepted_intro_rsa_parts,
-                                pkpart_digest);
-    if (access_time != NULL) {
-      log_warn(LD_REND, "Possible replay detected! We received an "
-               "INTRODUCE2 cell with same PK-encrypted part %d seconds ago. "
-               "Dropping cell.", (int)(now-*access_time));
-      goto err;
-    }
-    access_time = tor_malloc(sizeof(time_t));
-    *access_time = now;
-    digestmap_set(intro_point->accepted_intro_rsa_parts,
-                  pkpart_digest, access_time);
+  if (replay) {
+    log_warn(LD_REND,
+             "Possible replay detected! We received an "
+             "INTRODUCE2 cell with same PK-encrypted part %d "
+             "seconds ago.  Dropping cell.",
+             (int)elapsed);
+     goto err;
   }
 
-  /* Next N bytes is encrypted with service key */
-  note_crypto_pk_op(REND_SERVER);
-  r = crypto_pk_private_hybrid_decrypt(
-       intro_key,buf,sizeof(buf),
-       (char*)(request+DIGEST_LEN),request_len-DIGEST_LEN,
-       PK_PKCS1_OAEP_PADDING,1);
-  if (r<0) {
-    log_warn(LD_PROTOCOL, "Couldn't decrypt INTRODUCE2 cell.");
-    goto err;
+  stage_descr = "decryption";
+  /* Now try to decrypt it */
+  result = rend_service_decrypt_intro(parsed_req, intro_key, &err_msg);
+  if (result < 0) goto err;
+  else if (err_msg) {
+    log_info(LD_REND, "%s on circ %d.", err_msg, circuit->_base.n_circ_id);
+    tor_free(err_msg);
   }
-  len = r;
-  if (*buf == 3) {
-    /* Version 3 INTRODUCE2 cell. */
-    v3_shift = 1;
-    auth_type = buf[1];
-    switch (auth_type) {
-      case REND_BASIC_AUTH:
-        /* fall through */
-      case REND_STEALTH_AUTH:
-        auth_len = ntohs(get_uint16(buf+2));
-        if (auth_len != REND_DESC_COOKIE_LEN) {
-          log_info(LD_REND, "Wrong auth data size %d, should be %d.",
-                   (int)auth_len, REND_DESC_COOKIE_LEN);
-          goto err;
-        }
-        memcpy(auth_data, buf+4, sizeof(auth_data));
-        v3_shift += 2+REND_DESC_COOKIE_LEN;
-        break;
-      case REND_NO_AUTH:
-        break;
-      default:
-        log_info(LD_REND, "Unknown authorization type '%d'", auth_type);
-    }
-
-    /* Skip the timestamp field.  We no longer use it. */
-    v3_shift += 4;
-  }
-  if (*buf == 2 || *buf == 3) {
-    /* Version 2 INTRODUCE2 cell. */
-    int klen;
-    extend_info = tor_malloc_zero(sizeof(extend_info_t));
-    tor_addr_from_ipv4n(&extend_info->addr, get_uint32(buf+v3_shift+1));
-    extend_info->port = ntohs(get_uint16(buf+v3_shift+5));
-    memcpy(extend_info->identity_digest, buf+v3_shift+7,
-           DIGEST_LEN);
-    extend_info->nickname[0] = '$';
-    base16_encode(extend_info->nickname+1, sizeof(extend_info->nickname)-1,
-                  extend_info->identity_digest, DIGEST_LEN);
-
-    klen = ntohs(get_uint16(buf+v3_shift+7+DIGEST_LEN));
-    if ((int)len != v3_shift+7+DIGEST_LEN+2+klen+20+128) {
-      log_warn(LD_PROTOCOL, "Bad length %u for version %d INTRODUCE2 cell.",
-               (int)len, *buf);
-      reason = END_CIRC_REASON_TORPROTOCOL;
-      goto err;
-    }
-    extend_info->onion_key =
-        crypto_pk_asn1_decode(buf+v3_shift+7+DIGEST_LEN+2, klen);
-    if (!extend_info->onion_key) {
-      log_warn(LD_PROTOCOL, "Error decoding onion key in version %d "
-                            "INTRODUCE2 cell.", *buf);
-      reason = END_CIRC_REASON_TORPROTOCOL;
-      goto err;
-    }
-    ptr = buf+v3_shift+7+DIGEST_LEN+2+klen;
-    len -= v3_shift+7+DIGEST_LEN+2+klen;
-  } else {
-    char *rp_nickname;
-    size_t nickname_field_len;
-    const node_t *node;
-    int version;
-    if (*buf == 1) {
-      rp_nickname = buf+1;
-      nickname_field_len = MAX_HEX_NICKNAME_LEN+1;
-      version = 1;
-    } else {
-      nickname_field_len = MAX_NICKNAME_LEN+1;
-      rp_nickname = buf;
-      version = 0;
-    }
-    ptr=memchr(rp_nickname,0,nickname_field_len);
-    if (!ptr || ptr == rp_nickname) {
-      log_warn(LD_PROTOCOL,
-               "Couldn't find a nul-padded nickname in INTRODUCE2 cell.");
-      goto err;
-    }
-    if ((version == 0 && !is_legal_nickname(rp_nickname)) ||
-        (version == 1 && !is_legal_nickname_or_hexdigest(rp_nickname))) {
-      log_warn(LD_PROTOCOL, "Bad nickname in INTRODUCE2 cell.");
-      goto err;
-    }
-    /* Okay, now we know that a nickname is at the start of the buffer. */
-    ptr = rp_nickname+nickname_field_len;
-    len -= nickname_field_len;
-    len -= rp_nickname - buf; /* also remove header space used by version, if
-                               * any */
-    node = node_get_by_nickname(rp_nickname, 0);
-    if (!node) {
-      log_info(LD_REND, "Couldn't find router %s named in introduce2 cell.",
-               escaped_safe_str_client(rp_nickname));
-      /* XXXX Add a no-such-router reason? */
-      reason = END_CIRC_REASON_TORPROTOCOL;
-      goto err;
-    }
 
-    extend_info = extend_info_from_node(node, 0);
+  stage_descr = "late parsing";
+  /* Parse the plaintext */
+  result = rend_service_parse_intro_plaintext(parsed_req, &err_msg);
+  if (result < 0) goto err;
+  else if (err_msg) {
+    log_info(LD_REND, "%s on circ %d.", err_msg, circuit->_base.n_circ_id);
+    tor_free(err_msg);
   }
 
-  if (len != REND_COOKIE_LEN+DH_KEY_LEN) {
-    log_warn(LD_PROTOCOL, "Bad length %u for INTRODUCE2 cell.", (int)len);
-    reason = END_CIRC_REASON_TORPROTOCOL;
-    goto err;
+  stage_descr = "late validation";
+  /* Validate the parsed plaintext parts */
+  result = rend_service_validate_intro_late(parsed_req, &err_msg);
+  if (result < 0) goto err;
+  else if (err_msg) {
+    log_info(LD_REND, "%s on circ %d.", err_msg, circuit->_base.n_circ_id);
+    tor_free(err_msg);
   }
+  stage_descr = NULL;
+
+  /* Increment INTRODUCE2 counter */
+  ++(intro_point->accepted_introduce2_count);
+
+  /* Find the rendezvous point */
+  rp = find_rp_for_intro(parsed_req, &need_rp_free, &err_msg);
+  if (!rp) goto err;
 
   /* Check if we'd refuse to talk to this router */
   if (options->StrictNodes &&
-      routerset_contains_extendinfo(options->ExcludeNodes, extend_info)) {
+      routerset_contains_extendinfo(options->ExcludeNodes, rp)) {
     log_warn(LD_REND, "Client asked to rendezvous at a relay that we "
              "exclude, and StrictNodes is set. Refusing service.");
     reason = END_CIRC_REASON_INTERNAL; /* XXX might leak why we refused */
     goto err;
   }
 
-  r_cookie = ptr;
-  base16_encode(hexcookie,9,r_cookie,4);
-
-  /* Determine hash of Diffie-Hellman, part 1 to detect replays. */
-  digest = crypto_digest_new();
-  crypto_digest_add_bytes(digest, ptr+REND_COOKIE_LEN, DH_KEY_LEN);
-  crypto_digest_get_digest(digest, diffie_hellman_hash, DIGEST_LEN);
-  crypto_digest_free(digest);
+  base16_encode(hexcookie, 9, (const char *)(parsed_req->rc), 4);
 
   /* Check whether there is a past request with the same Diffie-Hellman,
    * part 1. */
-  access_time = digestmap_get(service->accepted_intro_dh_parts,
-                              diffie_hellman_hash);
-  if (access_time != NULL) {
+  replay = replaycache_add_test_and_elapsed(
+      service->accepted_intro_dh_parts,
+      parsed_req->dh, DH_KEY_LEN,
+      &elapsed);
+
+  if (replay) {
     /* A Tor client will send a new INTRODUCE1 cell with the same rend
      * cookie and DH public key as its previous one if its intro circ
      * times out while in state CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT .
@@ -1349,21 +1283,10 @@ rend_service_introduce(origin_circuit_t *circuit, const uint8_t *request,
              "INTRODUCE2 cell with same first part of "
              "Diffie-Hellman handshake %d seconds ago. Dropping "
              "cell.",
-             (int) (now - *access_time));
+             (int) elapsed);
     goto err;
   }
 
-  /* Add request to access history, including time and hash of Diffie-Hellman,
-   * part 1, and possibly remove requests from the history that are older than
-   * one hour. */
-  access_time = tor_malloc(sizeof(time_t));
-  *access_time = now;
-  digestmap_set(service->accepted_intro_dh_parts,
-                diffie_hellman_hash, access_time);
-  if (service->last_cleaned_accepted_intro_dh_parts + REND_REPLAY_TIME_INTERVAL
-      < now)
-    clean_accepted_intro_dh_parts(service, now);
-
   /* If the service performs client authorization, check included auth data. */
   if (service->clients) {
     if (auth_len > 0) {
@@ -1391,7 +1314,8 @@ rend_service_introduce(origin_circuit_t *circuit, const uint8_t *request,
     reason = END_CIRC_REASON_INTERNAL;
     goto err;
   }
-  if (crypto_dh_compute_secret(LOG_PROTOCOL_WARN, dh, ptr+REND_COOKIE_LEN,
+  if (crypto_dh_compute_secret(LOG_PROTOCOL_WARN, dh,
+                               (char *)(parsed_req->dh),
                                DH_KEY_LEN, keys,
                                DIGEST_LEN+CPATH_KEY_MATERIAL_LEN)<0) {
     log_warn(LD_BUG, "Internal error: couldn't complete DH handshake");
@@ -1410,7 +1334,7 @@ rend_service_introduce(origin_circuit_t *circuit, const uint8_t *request,
     int flags = CIRCLAUNCH_NEED_CAPACITY | CIRCLAUNCH_IS_INTERNAL;
     if (circ_needs_uptime) flags |= CIRCLAUNCH_NEED_UPTIME;
     launched = circuit_launch_by_extend_info(
-                        CIRCUIT_PURPOSE_S_CONNECT_REND, extend_info, flags);
+                        CIRCUIT_PURPOSE_S_CONNECT_REND, rp, flags);
 
     if (launched)
       break;
@@ -1418,7 +1342,7 @@ rend_service_introduce(origin_circuit_t *circuit, const uint8_t *request,
   if (!launched) { /* give up */
     log_warn(LD_REND, "Giving up launching first hop of circuit to rendezvous "
              "point %s for service %s.",
-             safe_str_client(extend_info_describe(extend_info)),
+             safe_str_client(extend_info_describe(rp)),
              serviceid);
     reason = END_CIRC_REASON_CONNECTFAILED;
     goto err;
@@ -1426,7 +1350,7 @@ rend_service_introduce(origin_circuit_t *circuit, const uint8_t *request,
   log_info(LD_REND,
            "Accepted intro; launching circuit to %s "
            "(cookie %s) for service %s.",
-           safe_str_client(extend_info_describe(extend_info)),
+           safe_str_client(extend_info_describe(rp)),
            hexcookie, serviceid);
   tor_assert(launched->build_state);
   /* Fill in the circuit's state. */
@@ -1434,7 +1358,7 @@ rend_service_introduce(origin_circuit_t *circuit, const uint8_t *request,
   memcpy(launched->rend_data->rend_pk_digest,
          circuit->rend_data->rend_pk_digest,
          DIGEST_LEN);
-  memcpy(launched->rend_data->rend_cookie, r_cookie, REND_COOKIE_LEN);
+  memcpy(launched->rend_data->rend_cookie, parsed_req->rc, REND_COOKIE_LEN);
   strlcpy(launched->rend_data->onion_address, service->service_id,
           sizeof(launched->rend_data->onion_address));
 
@@ -1452,16 +1376,26 @@ rend_service_introduce(origin_circuit_t *circuit, const uint8_t *request,
   if (circuit_init_cpath_crypto(cpath,keys+DIGEST_LEN,1)<0)
     goto err;
   memcpy(cpath->handshake_digest, keys, DIGEST_LEN);
-  if (extend_info) extend_info_free(extend_info);
 
   goto done;
 
  err:
   status = -1;
+  if (!err_msg) {
+    if (stage_descr) {
+      tor_asprintf(&err_msg,
+                   "unknown %s error for INTRODUCE2", stage_descr);
+     } else {
+      err_msg = tor_strdup("unknown error for INTRODUCE2");
+     }
+  }
   if (dh) crypto_dh_free(dh);
-  if (launched)
+  if (launched) {
     circuit_mark_for_close(TO_CIRCUIT(launched), reason);
-  if (extend_info) extend_info_free(extend_info);
+  }
+  log_warn(LD_REND, "%s on circ %d", err_msg, circuit->_base.n_circ_id);
+  tor_free(err_msg);
+
  done:
   memset(keys, 0, sizeof(keys));
   memset(buf, 0, sizeof(buf));
@@ -1471,6 +1405,844 @@ rend_service_introduce(origin_circuit_t *circuit, const uint8_t *request,
   memset(auth_data, 0, sizeof(auth_data));
   memset(diffie_hellman_hash, 0, sizeof(diffie_hellman_hash));
 
+  /* Free the parsed cell */
+  if (parsed_req) {
+    rend_service_free_intro(parsed_req);
+    parsed_req = NULL;
+  }
+
+  /* Free rp if we must */
+  if (need_rp_free) extend_info_free(rp);
+
+  return status;
+}
+
+/** Given a parsed and decrypted INTRODUCE2, find the rendezvous point or
+ * return NULL and an error string if we can't.
+ */
+
+static extend_info_t *
+find_rp_for_intro(const rend_intro_cell_t *intro,
+                  uint8_t *need_free_out, char **err_msg_out)
+{
+  extend_info_t *rp = NULL;
+  char *err_msg = NULL;
+  const char *rp_nickname = NULL;
+  const node_t *node = NULL;
+  uint8_t need_free = 0;
+
+  if (!intro || !need_free_out) {
+    if (err_msg_out)
+      err_msg = tor_strdup("Bad parameters to find_rp_for_intro()");
+
+    goto err;
+  }
+
+  if (intro->version == 0 || intro->version == 1) {
+    if (intro->version == 1) rp_nickname = (const char *)(intro->u.v1.rp);
+    else rp_nickname = (const char *)(intro->u.v0.rp);
+
+    node = node_get_by_nickname(rp_nickname, 0);
+    if (!node) {
+      if (err_msg_out) {
+        tor_asprintf(&err_msg,
+                     "Couldn't find router %s named in INTRODUCE2 cell",
+                     escaped_safe_str_client(rp_nickname));
+      }
+
+      goto err;
+    }
+
+    rp = extend_info_from_node(node, 0);
+    if (!rp) {
+      if (err_msg_out) {
+        tor_asprintf(&err_msg,
+                     "Could build extend_info_t for router %s named "
+                     "in INTRODUCE2 cell",
+                     escaped_safe_str_client(rp_nickname));
+      }
+
+      goto err;
+    } else {
+      need_free = 1;
+    }
+  } else if (intro->version == 2) {
+    rp = intro->u.v2.extend_info;
+  } else if (intro->version == 3) {
+    rp = intro->u.v3.extend_info;
+  } else {
+    if (err_msg_out) {
+      tor_asprintf(&err_msg,
+                   "Unknown version %d in INTRODUCE2 cell",
+                   (int)(intro->version));
+    }
+
+    goto err;
+  }
+
+  goto done;
+
+ err:
+  if (err_msg_out) *err_msg_out = err_msg;
+  else tor_free(err_msg);
+
+ done:
+  if (rp && need_free_out) *need_free_out = need_free;
+
+  return rp;
+}
+
+/** Remove unnecessary parts from a rend_intro_cell_t - the ciphertext if
+ * already decrypted, the plaintext too if already parsed
+ */
+
+void
+rend_service_compact_intro(rend_intro_cell_t *request)
+{
+  if (!request) return;
+
+  if ((request->plaintext && request->plaintext_len > 0) ||
+       request->parsed) {
+    tor_free(request->ciphertext);
+    request->ciphertext_len = 0;
+  }
+
+  if (request->parsed) {
+    tor_free(request->plaintext);
+    request->plaintext_len = 0;
+  }
+}
+
+/** Free a parsed INTRODUCE1 or INTRODUCE2 cell that was allocated by
+ * rend_service_parse_intro().
+ */
+void
+rend_service_free_intro(rend_intro_cell_t *request)
+{
+  if (!request) {
+    log_info(LD_BUG, "rend_service_free_intro() called with NULL request!");
+    return;
+  }
+
+  /* Free ciphertext */
+  tor_free(request->ciphertext);
+  request->ciphertext_len = 0;
+
+  /* Have plaintext? */
+  if (request->plaintext) {
+    /* Zero it out just to be safe */
+    memset(request->plaintext, 0, request->plaintext_len);
+    tor_free(request->plaintext);
+    request->plaintext_len = 0;
+  }
+
+  /* Have parsed plaintext? */
+  if (request->parsed) {
+    switch (request->version) {
+      case 0:
+      case 1:
+        /*
+         * Nothing more to do; these formats have no further pointers
+         * in them.
+         */
+        break;
+      case 2:
+        extend_info_free(request->u.v2.extend_info);
+        request->u.v2.extend_info = NULL;
+        break;
+      case 3:
+        if (request->u.v3.auth_data) {
+          memset(request->u.v3.auth_data, 0, request->u.v3.auth_len);
+          tor_free(request->u.v3.auth_data);
+        }
+
+        extend_info_free(request->u.v3.extend_info);
+        request->u.v3.extend_info = NULL;
+        break;
+      default:
+        log_info(LD_BUG,
+                 "rend_service_free_intro() saw unknown protocol "
+                 "version %d.",
+                 request->version);
+    }
+  }
+
+  /* Zero it out to make sure sensitive stuff doesn't hang around in memory */
+  memset(request, 0, sizeof(*request));
+
+  tor_free(request);
+}
+
+/** Parse an INTRODUCE1 or INTRODUCE2 cell into a newly allocated
+ * rend_intro_cell_t structure.  Free it with rend_service_free_intro()
+ * when finished.  The type parameter should be 1 or 2 to indicate whether
+ * this is INTRODUCE1 or INTRODUCE2.  This parses only the non-encrypted
+ * parts; after this, call rend_service_decrypt_intro() with a key, then
+ * rend_service_parse_intro_plaintext() to finish parsing.  The optional
+ * err_msg_out parameter is set to a string suitable for log output
+ * if parsing fails.  This function does some validation, but only
+ * that which depends solely on the contents of the cell and the
+ * key; it can be unit-tested.  Further validation is done in
+ * rend_service_validate_intro().
+ */
+
+rend_intro_cell_t *
+rend_service_begin_parse_intro(const uint8_t *request,
+                               size_t request_len,
+                               uint8_t type,
+                               char **err_msg_out)
+{
+  rend_intro_cell_t *rv = NULL;
+  char *err_msg = NULL;
+
+  if (!request || request_len <= 0) goto err;
+  if (!(type == 1 || type == 2)) goto err;
+
+  /* First, check that the cell is long enough to be a sensible INTRODUCE */
+
+  /* min key length plus digest length plus nickname length */
+  if (request_len <
+        (DIGEST_LEN + REND_COOKIE_LEN + (MAX_NICKNAME_LEN + 1) +
+         DH_KEY_LEN + 42)) {
+    if (err_msg_out) {
+      tor_asprintf(&err_msg,
+                   "got a truncated INTRODUCE%d cell",
+                   (int)type);
+    }
+    goto err;
+  }
+
+  /* Allocate a new parsed cell structure */
+  rv = tor_malloc_zero(sizeof(*rv));
+
+  /* Set the type */
+  rv->type = type;
+
+  /* Copy in the ID */
+  memcpy(rv->pk, request, DIGEST_LEN);
+
+  /* Copy in the ciphertext */
+  rv->ciphertext = tor_malloc(request_len - DIGEST_LEN);
+  memcpy(rv->ciphertext, request + DIGEST_LEN, request_len - DIGEST_LEN);
+  rv->ciphertext_len = request_len - DIGEST_LEN;
+
+  goto done;
+
+ err:
+  if (rv) rend_service_free_intro(rv);
+  rv = NULL;
+  if (err_msg_out && !err_msg) {
+    tor_asprintf(&err_msg,
+                 "unknown INTRODUCE%d error",
+                 (int)type);
+  }
+
+ done:
+  if (err_msg_out) *err_msg_out = err_msg;
+  else tor_free(err_msg);
+
+  return rv;
+}
+
+/** Parse the version-specific parts of a v0 or v1 INTRODUCE1 or INTRODUCE2
+ * cell
+ */
+
+static ssize_t
+rend_service_parse_intro_for_v0_or_v1(
+    rend_intro_cell_t *intro,
+    const uint8_t *buf,
+    size_t plaintext_len,
+    char **err_msg_out)
+{
+  const char *rp_nickname, *endptr;
+  size_t nickname_field_len, ver_specific_len;
+
+  if (intro->version == 1) {
+    ver_specific_len = MAX_HEX_NICKNAME_LEN + 2;
+    rp_nickname = ((const char *)buf) + 1;
+    nickname_field_len = MAX_HEX_NICKNAME_LEN + 1;
+  } else if (intro->version == 0) {
+    ver_specific_len = MAX_NICKNAME_LEN + 1;
+    rp_nickname = (const char *)buf;
+    nickname_field_len = MAX_NICKNAME_LEN + 1;
+  } else {
+    if (err_msg_out)
+      tor_asprintf(err_msg_out,
+                   "rend_service_parse_intro_for_v0_or_v1() called with "
+                   "bad version %d on INTRODUCE%d cell (this is a bug)",
+                   intro->version,
+                   (int)(intro->type));
+    goto err;
+  }
+
+  if (plaintext_len < ver_specific_len) {
+    if (err_msg_out)
+      tor_asprintf(err_msg_out,
+                   "short plaintext of encrypted part in v1 INTRODUCE%d "
+                   "cell (%lu bytes, needed %lu)",
+                   (int)(intro->type),
+                   (unsigned long)plaintext_len,
+                   (unsigned long)ver_specific_len);
+    goto err;
+  }
+
+  endptr = memchr(rp_nickname, 0, nickname_field_len);
+  if (!endptr || endptr == rp_nickname) {
+    if (err_msg_out) {
+      tor_asprintf(err_msg_out,
+                   "couldn't find a nul-padded nickname in "
+                   "INTRODUCE%d cell",
+                   (int)(intro->type));
+    }
+    goto err;
+  }
+
+  if ((intro->version == 0 &&
+       !is_legal_nickname(rp_nickname)) ||
+      (intro->version == 1 &&
+       !is_legal_nickname_or_hexdigest(rp_nickname))) {
+    if (err_msg_out) {
+      tor_asprintf(err_msg_out,
+                   "bad nickname in INTRODUCE%d cell",
+                   (int)(intro->type));
+    }
+    goto err;
+  }
+
+  if (intro->version == 1) {
+    memcpy(intro->u.v1.rp, rp_nickname, endptr - rp_nickname + 1);
+  } else {
+    memcpy(intro->u.v0.rp, rp_nickname, endptr - rp_nickname + 1);
+  }
+
+  return ver_specific_len;
+
+ err:
+  return -1;
+}
+
+/** Parse the version-specific parts of a v2 INTRODUCE1 or INTRODUCE2 cell
+ */
+
+static ssize_t
+rend_service_parse_intro_for_v2(
+    rend_intro_cell_t *intro,
+    const uint8_t *buf,
+    size_t plaintext_len,
+    char **err_msg_out)
+{
+  unsigned int klen;
+  extend_info_t *extend_info = NULL;
+  ssize_t ver_specific_len;
+
+  /*
+   * We accept version 3 too so that the v3 parser can call this with
+   * and adjusted buffer for the latter part of a v3 cell, which is
+   * identical to a v2 cell.
+   */
+  if (!(intro->version == 2 ||
+        intro->version == 3)) {
+    if (err_msg_out)
+      tor_asprintf(err_msg_out,
+                   "rend_service_parse_intro_for_v2() called with "
+                   "bad version %d on INTRODUCE%d cell (this is a bug)",
+                   intro->version,
+                   (int)(intro->type));
+    goto err;
+  }
+
+  /* 7 == version, IP and port, DIGEST_LEN == id, 2 == key length */
+  if (plaintext_len < 7 + DIGEST_LEN + 2) {
+    if (err_msg_out) {
+      tor_asprintf(err_msg_out,
+                   "truncated plaintext of encrypted parted of "
+                   "version %d INTRODUCE%d cell",
+                   intro->version,
+                   (int)(intro->type));
+    }
+
+    goto err;
+  }
+
+  extend_info = tor_malloc_zero(sizeof(extend_info_t));
+  tor_addr_from_ipv4n(&extend_info->addr, get_uint32(buf + 1));
+  extend_info->port = ntohs(get_uint16(buf + 5));
+  memcpy(extend_info->identity_digest, buf + 7, DIGEST_LEN);
+  extend_info->nickname[0] = '$';
+  base16_encode(extend_info->nickname + 1, sizeof(extend_info->nickname) - 1,
+                extend_info->identity_digest, DIGEST_LEN);
+  klen = ntohs(get_uint16(buf + 7 + DIGEST_LEN));
+
+  /* 7 == version, IP and port, DIGEST_LEN == id, 2 == key length */
+  if (plaintext_len < 7 + DIGEST_LEN + 2 + klen) {
+    if (err_msg_out) {
+      tor_asprintf(err_msg_out,
+                   "truncated plaintext of encrypted parted of "
+                   "version %d INTRODUCE%d cell",
+                   intro->version,
+                   (int)(intro->type));
+    }
+
+    goto err;
+  }
+
+  extend_info->onion_key =
+    crypto_pk_asn1_decode((const char *)(buf + 7 + DIGEST_LEN + 2), klen);
+  if (!extend_info->onion_key) {
+    if (err_msg_out) {
+      tor_asprintf(err_msg_out,
+                   "error decoding onion key in version %d "
+                   "INTRODUCE%d cell",
+                   intro->version,
+                   (intro->type));
+    }
+
+    goto err;
+  }
+
+  ver_specific_len = 7+DIGEST_LEN+2+klen;
+
+  if (intro->version == 2) intro->u.v2.extend_info = extend_info;
+  else intro->u.v3.extend_info = extend_info;
+
+  return ver_specific_len;
+
+ err:
+  extend_info_free(extend_info);
+
+  return -1;
+}
+
+/** Parse the version-specific parts of a v3 INTRODUCE1 or INTRODUCE2 cell
+ */
+
+static ssize_t
+rend_service_parse_intro_for_v3(
+    rend_intro_cell_t *intro,
+    const uint8_t *buf,
+    size_t plaintext_len,
+    char **err_msg_out)
+{
+  ssize_t adjust, v2_ver_specific_len, ts_offset;
+
+  /* This should only be called on v3 cells */
+  if (intro->version != 3) {
+    if (err_msg_out)
+      tor_asprintf(err_msg_out,
+                   "rend_service_parse_intro_for_v3() called with "
+                   "bad version %d on INTRODUCE%d cell (this is a bug)",
+                   intro->version,
+                   (int)(intro->type));
+    goto err;
+  }
+
+  /*
+   * Check that we have at least enough to get auth_len:
+   *
+   * 1 octet for version, 1 for auth_type, 2 for auth_len
+   */
+  if (plaintext_len < 4) {
+    if (err_msg_out) {
+      tor_asprintf(err_msg_out,
+                   "truncated plaintext of encrypted parted of "
+                   "version %d INTRODUCE%d cell",
+                   intro->version,
+                   (int)(intro->type));
+    }
+
+    goto err;
+  }
+
+  /*
+   * The rend_client_send_introduction() function over in rendclient.c is
+   * broken (i.e., fails to match the spec) in such a way that we can't
+   * change it without breaking the protocol.  Specifically, it doesn't
+   * emit auth_len when auth-type is REND_NO_AUTH, so everything is off
+   * by two bytes after that.  Calculate ts_offset and do everything from
+   * the timestamp on relative to that to handle this dain bramage.
+   */
+
+  intro->u.v3.auth_type = buf[1];
+  if (intro->u.v3.auth_type != REND_NO_AUTH) {
+    intro->u.v3.auth_len = ntohs(get_uint16(buf + 2));
+    ts_offset = 4 + intro->u.v3.auth_len;
+  } else {
+    intro->u.v3.auth_len = 0;
+    ts_offset = 2;
+  }
+
+  /* Check that auth len makes sense for this auth type */
+  if (intro->u.v3.auth_type == REND_BASIC_AUTH ||
+      intro->u.v3.auth_type == REND_STEALTH_AUTH) {
+      if (intro->u.v3.auth_len != REND_DESC_COOKIE_LEN) {
+        if (err_msg_out) {
+          tor_asprintf(err_msg_out,
+                       "wrong auth data size %d for INTRODUCE%d cell, "
+                       "should be %d",
+                       (int)(intro->u.v3.auth_len),
+                       (int)(intro->type),
+                       REND_DESC_COOKIE_LEN);
+        }
+
+        goto err;
+      }
+  }
+
+  /* Check that we actually have everything up to the timestamp */
+  if (plaintext_len < (size_t)(ts_offset)) {
+    if (err_msg_out) {
+      tor_asprintf(err_msg_out,
+                   "truncated plaintext of encrypted parted of "
+                   "version %d INTRODUCE%d cell",
+                   intro->version,
+                   (int)(intro->type));
+    }
+
+    goto err;
+  }
+
+  if (intro->u.v3.auth_type != REND_NO_AUTH &&
+      intro->u.v3.auth_len > 0) {
+    /* Okay, we can go ahead and copy auth_data */
+    intro->u.v3.auth_data = tor_malloc(intro->u.v3.auth_len);
+    /*
+     * We know we had an auth_len field in this case, so 4 is
+     * always right.
+     */
+    memcpy(intro->u.v3.auth_data, buf + 4, intro->u.v3.auth_len);
+  }
+
+  /*
+   * Apparently we don't use the timestamp any more, but might as well copy
+   * over just in case we ever care about it.
+   */
+  intro->u.v3.timestamp = ntohl(get_uint32(buf + ts_offset));
+
+  /*
+   * From here on, the format is as in v2, so we call the v2 parser with
+   * adjusted buffer and length.  We are 4 + ts_offset octets in, but the
+   * v2 parser expects to skip over a version byte at the start, so we
+   * adjust by 3 + ts_offset.
+   */
+  adjust = 3 + ts_offset;
+
+  v2_ver_specific_len =
+    rend_service_parse_intro_for_v2(intro,
+                                    buf + adjust, plaintext_len - adjust,
+                                    err_msg_out);
+
+  /* Success in v2 parser */
+  if (v2_ver_specific_len >= 0) return v2_ver_specific_len + adjust;
+  /* Failure in v2 parser; it will have provided an err_msg */
+  else return v2_ver_specific_len;
+
+ err:
+  return -1;
+}
+
+/** Table of parser functions for version-specific parts of an INTRODUCE2
+ * cell.
+ */
+
+static ssize_t
+  (*intro_version_handlers[])(
+    rend_intro_cell_t *,
+    const uint8_t *,
+    size_t,
+    char **) =
+{ rend_service_parse_intro_for_v0_or_v1,
+  rend_service_parse_intro_for_v0_or_v1,
+  rend_service_parse_intro_for_v2,
+  rend_service_parse_intro_for_v3 };
+
+/** Decrypt the encrypted part of an INTRODUCE1 or INTRODUCE2 cell,
+ * return 0 if successful, or < 0 and write an error message to
+ * *err_msg_out if provided.
+ */
+
+int
+rend_service_decrypt_intro(
+    rend_intro_cell_t *intro,
+    crypto_pk_t *key,
+    char **err_msg_out)
+{
+  char *err_msg = NULL;
+  uint8_t key_digest[DIGEST_LEN];
+  char service_id[REND_SERVICE_ID_LEN_BASE32+1];
+  ssize_t key_len;
+  uint8_t buf[RELAY_PAYLOAD_SIZE];
+  int result, status = 0;
+
+  if (!intro || !key) {
+    if (err_msg_out) {
+      err_msg =
+        tor_strdup("rend_service_decrypt_intro() called with bad "
+                   "parameters");
+    }
+
+    status = -2;
+    goto err;
+  }
+
+  /* Make sure we have ciphertext */
+  if (!(intro->ciphertext) || intro->ciphertext_len <= 0) {
+    if (err_msg_out) {
+      tor_asprintf(&err_msg,
+                   "rend_intro_cell_t was missing ciphertext for "
+                   "INTRODUCE%d cell",
+                   (int)(intro->type));
+    }
+    status = -3;
+    goto err;
+  }
+
+  /* Check that this cell actually matches this service key */
+
+  /* first DIGEST_LEN bytes of request is intro or service pk digest */
+  crypto_pk_get_digest(key, (char *)key_digest);
+  if (tor_memneq(key_digest, intro->pk, DIGEST_LEN)) {
+    if (err_msg_out) {
+      base32_encode(service_id, REND_SERVICE_ID_LEN_BASE32 + 1,
+                    (char*)(intro->pk), REND_SERVICE_ID_LEN);
+      tor_asprintf(&err_msg,
+                   "got an INTRODUCE%d cell for the wrong service (%s)",
+                   (int)(intro->type),
+                   escaped(service_id));
+    }
+
+    status = -4;
+    goto err;
+  }
+
+  /* Make sure the encrypted part is long enough to decrypt */
+
+  key_len = crypto_pk_keysize(key);
+  if (intro->ciphertext_len < key_len) {
+    if (err_msg_out) {
+      tor_asprintf(&err_msg,
+                   "got an INTRODUCE%d cell with a truncated PK-encrypted "
+                   "part",
+                   (int)(intro->type));
+    }
+
+    status = -5;
+    goto err;
+  }
+
+  /* Decrypt the encrypted part */
+
+  note_crypto_pk_op(REND_SERVER);
+  result =
+    crypto_pk_private_hybrid_decrypt(
+       key, (char *)buf, sizeof(buf),
+       (const char *)(intro->ciphertext), intro->ciphertext_len,
+       PK_PKCS1_OAEP_PADDING, 1);
+  if (result < 0) {
+    if (err_msg_out) {
+      tor_asprintf(&err_msg,
+                   "couldn't decrypt INTRODUCE%d cell",
+                   (int)(intro->type));
+    }
+    status = -6;
+    goto err;
+  }
+  intro->plaintext_len = result;
+  intro->plaintext = tor_malloc(intro->plaintext_len);
+  memcpy(intro->plaintext, buf, intro->plaintext_len);
+
+  goto done;
+
+ err:
+  if (err_msg_out && !err_msg) {
+    tor_asprintf(&err_msg,
+                 "unknown INTRODUCE%d error decrypting encrypted part",
+                 (int)(intro->type));
+  }
+  if (status >= 0) status = -1;
+
+ done:
+  if (err_msg_out) *err_msg_out = err_msg;
+  else tor_free(err_msg);
+
+  /* clean up potentially sensitive material */
+  memset(buf, 0, sizeof(buf));
+  memset(key_digest, 0, sizeof(key_digest));
+  memset(service_id, 0, sizeof(service_id));
+
+  return status;
+}
+
+/** Parse the plaintext of the encrypted part of an INTRODUCE1 or
+ * INTRODUCE2 cell, return 0 if successful, or < 0 and write an error
+ * message to *err_msg_out if provided.
+ */
+
+int
+rend_service_parse_intro_plaintext(
+    rend_intro_cell_t *intro,
+    char **err_msg_out)
+{
+  char *err_msg = NULL;
+  ssize_t ver_specific_len, ver_invariant_len;
+  uint8_t version;
+  int status = 0;
+
+  if (!intro) {
+    if (err_msg_out) {
+      err_msg =
+        tor_strdup("rend_service_parse_intro_plaintext() called with NULL "
+                   "rend_intro_cell_t");
+    }
+
+    status = -2;
+    goto err;
+  }
+
+  /* Check that we have plaintext */
+  if (!(intro->plaintext) || intro->plaintext_len <= 0) {
+    if (err_msg_out) {
+      err_msg = tor_strdup("rend_intro_cell_t was missing plaintext");
+    }
+    status = -3;
+    goto err;
+  }
+
+  /* In all formats except v0, the first byte is a version number */
+  version = intro->plaintext[0];
+
+  /* v0 has no version byte (stupid...), so handle it as a fallback */
+  if (version > 3) version = 0;
+
+  /* Copy the version into the parsed cell structure */
+  intro->version = version;
+
+  /* Call the version-specific parser from the table */
+  ver_specific_len =
+    intro_version_handlers[version](intro,
+                                    intro->plaintext, intro->plaintext_len,
+                                    &err_msg);
+  if (ver_specific_len < 0) {
+    status = -4;
+    goto err;
+  }
+
+  /** The rendezvous cookie and Diffie-Hellman stuff are version-invariant
+   * and at the end of the plaintext of the encrypted part of the cell.
+   */
+
+  ver_invariant_len = intro->plaintext_len - ver_specific_len;
+  if (ver_invariant_len < REND_COOKIE_LEN + DH_KEY_LEN) {
+    tor_asprintf(&err_msg,
+        "decrypted plaintext of INTRODUCE%d cell was truncated (%ld bytes)",
+        (int)(intro->type),
+        (long)(intro->plaintext_len));
+    status = -5;
+    goto err;
+  } else if (ver_invariant_len > REND_COOKIE_LEN + DH_KEY_LEN) {
+    tor_asprintf(&err_msg,
+        "decrypted plaintext of INTRODUCE%d cell was too long (%ld bytes)",
+        (int)(intro->type),
+        (long)(intro->plaintext_len));
+    status = -6;
+  } else {
+    memcpy(intro->rc,
+           intro->plaintext + ver_specific_len,
+           REND_COOKIE_LEN);
+    memcpy(intro->dh,
+           intro->plaintext + ver_specific_len + REND_COOKIE_LEN,
+           DH_KEY_LEN);
+  }
+
+  /* Flag it as being fully parsed */
+  intro->parsed = 1;
+
+  goto done;
+
+ err:
+  if (err_msg_out && !err_msg) {
+    tor_asprintf(&err_msg,
+                 "unknown INTRODUCE%d error parsing encrypted part",
+                 (int)(intro->type));
+  }
+  if (status >= 0) status = -1;
+
+ done:
+  if (err_msg_out) *err_msg_out = err_msg;
+  else tor_free(err_msg);
+
+  return status;
+}
+
+/** Do validity checks on a parsed intro cell before decryption; some of
+ * these are not done in rend_service_begin_parse_intro() itself because
+ * they depend on a lot of other state and would make it hard to unit test.
+ * Returns >= 0 if successful or < 0 if the intro cell is invalid, and
+ * optionally writes out an error message for logging.  If an err_msg
+ * pointer is provided, it is the caller's responsibility to free any
+ * provided message.
+ */
+
+int
+rend_service_validate_intro_early(const rend_intro_cell_t *intro,
+                                  char **err_msg_out)
+{
+  int status = 0;
+
+  if (!intro) {
+    if (err_msg_out)
+      *err_msg_out =
+        tor_strdup("NULL intro cell passed to "
+                   "rend_service_validate_intro_early()");
+
+    status = -1;
+    goto err;
+  }
+
+  /* TODO */
+
+ err:
+  return status;
+}
+
+/** Do validity checks on a parsed intro cell after decryption; some of
+ * these are not done in rend_service_parse_intro_plaintext() itself because
+ * they depend on a lot of other state and would make it hard to unit test.
+ * Returns >= 0 if successful or < 0 if the intro cell is invalid, and
+ * optionally writes out an error message for logging.  If an err_msg
+ * pointer is provided, it is the caller's responsibility to free any
+ * provided message.
+ */
+
+int
+rend_service_validate_intro_late(const rend_intro_cell_t *intro,
+                                 char **err_msg_out)
+{
+  int status = 0;
+
+  if (!intro) {
+    if (err_msg_out)
+      *err_msg_out =
+        tor_strdup("NULL intro cell passed to "
+                   "rend_service_validate_intro_late()");
+
+    status = -1;
+    goto err;
+  }
+
+  if (intro->version == 3 && intro->parsed) {
+    if (!(intro->u.v3.auth_type == REND_NO_AUTH ||
+          intro->u.v3.auth_type == REND_BASIC_AUTH ||
+          intro->u.v3.auth_type == REND_STEALTH_AUTH)) {
+      /* This is an informative message, not an error, as in the old code */
+      if (err_msg_out)
+        tor_asprintf(err_msg_out,
+                     "unknown authorization type %d",
+                     intro->u.v3.auth_type);
+    }
+  }
+
+ err:
   return status;
 }
 
@@ -2164,11 +2936,7 @@ upload_service_descriptor(rend_service_t *service)
 static int
 intro_point_accepted_intro_count(rend_intro_point_t *intro)
 {
-  if (intro->accepted_intro_rsa_parts == NULL) {
-    return 0;
-  } else {
-    return digestmap_size(intro->accepted_intro_rsa_parts);
-  }
+  return intro->accepted_introduce2_count;
 }
 
 /** Return non-zero iff <b>intro</b> should 'expire' now (i.e. we
diff --git a/src/or/rendservice.h b/src/or/rendservice.h
index baf8d5fb4..0d6eddaee 100644
--- a/src/or/rendservice.h
+++ b/src/or/rendservice.h
@@ -12,6 +12,64 @@
 #ifndef _TOR_RENDSERVICE_H
 #define _TOR_RENDSERVICE_H
 
+#include "or.h"
+
+typedef struct rend_intro_cell_s rend_intro_cell_t;
+
+#ifdef RENDSERVICE_PRIVATE
+
+/* This can be used for both INTRODUCE1 and INTRODUCE2 */
+
+struct rend_intro_cell_s {
+  /* Is this an INTRODUCE1 or INTRODUCE2? (set to 1 or 2) */
+  uint8_t type;
+  /* Public key digest */
+  uint8_t pk[DIGEST_LEN];
+  /* Optionally, store ciphertext here */
+  uint8_t *ciphertext;
+  ssize_t ciphertext_len;
+  /* Optionally, store plaintext */
+  uint8_t *plaintext;
+  ssize_t plaintext_len;
+  /* Have we parsed the plaintext? */
+  uint8_t parsed;
+  /* intro protocol version (0, 1, 2 or 3) */
+  uint8_t version;
+  /* Version-specific parts */
+  union {
+    struct {
+      /* Rendezvous point nickname */
+      uint8_t rp[20];
+    } v0;
+    struct {
+      /* Rendezvous point nickname or hex-encoded key digest */
+      uint8_t rp[42];
+    } v1;
+    struct {
+      /* The extend_info_t struct has everything v2 uses */
+      extend_info_t *extend_info;
+    } v2;
+    struct {
+      /* Auth type used */
+      uint8_t auth_type;
+      /* Length of auth data */
+      uint16_t auth_len;
+      /* Auth data */
+      uint8_t *auth_data;
+      /* timestamp */
+      uint32_t timestamp;
+      /* Rendezvous point's IP address/port, identity digest and onion key */
+      extend_info_t *extend_info;
+    } v3;
+  } u;
+  /* Rendezvous cookie */
+  uint8_t rc[REND_COOKIE_LEN];
+  /* Diffie-Hellman data */
+  uint8_t dh[DH_KEY_LEN];
+};
+
+#endif
+
 int num_rend_services(void);
 int rend_config_services(const or_options_t *options, int validate_only);
 int rend_service_load_all_keys(void);
@@ -27,6 +85,21 @@ int rend_service_intro_established(origin_circuit_t *circuit,
 void rend_service_rendezvous_has_opened(origin_circuit_t *circuit);
 int rend_service_introduce(origin_circuit_t *circuit, const uint8_t *request,
                            size_t request_len);
+void rend_service_compact_intro(rend_intro_cell_t *request);
+int rend_service_decrypt_intro(rend_intro_cell_t *request,
+                               crypto_pk_t *key,
+                               char **err_msg_out);
+void rend_service_free_intro(rend_intro_cell_t *request);
+rend_intro_cell_t * rend_service_begin_parse_intro(const uint8_t *request,
+                                                   size_t request_len,
+                                                   uint8_t type,
+                                                   char **err_msg_out);
+int rend_service_parse_intro_plaintext(rend_intro_cell_t *intro,
+                                       char **err_msg_out);
+int rend_service_validate_intro_early(const rend_intro_cell_t *intro,
+                                      char **err_msg_out);
+int rend_service_validate_intro_late(const rend_intro_cell_t *intro,
+                                     char **err_msg_out);
 void rend_service_relaunch_rendezvous(origin_circuit_t *oldcirc);
 int rend_service_set_connection_addr_port(edge_connection_t *conn,
                                           origin_circuit_t *circ);
diff --git a/src/or/replaycache.c b/src/or/replaycache.c
new file mode 100644
index 000000000..09104a937
--- /dev/null
+++ b/src/or/replaycache.c
@@ -0,0 +1,215 @@
+ /* Copyright (c) 2012, The Tor Project, Inc. */
+ /* See LICENSE for licensing information */
+
+/*
+ * \file replaycache.c
+ *
+ * \brief Self-scrubbing replay cache for rendservice.c
+ */
+
+#define REPLAYCACHE_PRIVATE
+
+#include "or.h"
+#include "replaycache.h"
+
+/** Free the replaycache r and all of its entries.
+ */
+
+void
+replaycache_free(replaycache_t *r)
+{
+  if (!r) {
+    log_info(LD_BUG, "replaycache_free() called on NULL");
+    return;
+  }
+
+  if (r->digests_seen) digestmap_free(r->digests_seen, _tor_free);
+
+  tor_free(r);
+}
+
+/** Allocate a new, empty replay detection cache, where horizon is the time
+ * for entries to age out and interval is the time after which the cache
+ * should be scrubbed for old entries.
+ */
+
+replaycache_t *
+replaycache_new(time_t horizon, time_t interval)
+{
+  replaycache_t *r = NULL;
+
+  if (horizon < 0) {
+    log_info(LD_BUG, "replaycache_new() called with negative"
+        " horizon parameter");
+    goto err;
+  }
+
+  if (interval < 0) {
+    log_info(LD_BUG, "replaycache_new() called with negative interval"
+        " parameter");
+    interval = 0;
+  }
+
+  r = tor_malloc(sizeof(*r));
+  r->scrub_interval = interval;
+  r->scrubbed = 0;
+  r->horizon = horizon;
+  r->digests_seen = digestmap_new();
+
+ err:
+  return r;
+}
+
+/** See documentation for replaycache_add_and_test()
+ */
+
+int
+replaycache_add_and_test_internal(
+    time_t present, replaycache_t *r, const void *data, int len,
+    time_t *elapsed)
+{
+  int rv = 0;
+  char digest[DIGEST_LEN];
+  time_t *access_time;
+
+  /* sanity check */
+  if (present <= 0 || !r || !data || len <= 0) {
+    log_info(LD_BUG, "replaycache_add_and_test_internal() called with stupid"
+        " parameters; please fix this.");
+    goto done;
+  }
+
+  /* compute digest */
+  crypto_digest(digest, (const char *)data, len);
+
+  /* check map */
+  access_time = digestmap_get(r->digests_seen, digest);
+
+  /* seen before? */
+  if (access_time != NULL) {
+    /*
+     * If it's far enough in the past, no hit.  If the horizon is zero, we
+     * never expire.
+     */
+    if (*access_time >= present - r->horizon || r->horizon == 0) {
+      /* replay cache hit, return 1 */
+      rv = 1;
+      /* If we want to output an elapsed time, do so */
+      if (elapsed) {
+        if (present >= *access_time) {
+          *elapsed = present - *access_time;
+        } else {
+          /* We shouldn't really be seeing hits from the future, but... */
+          *elapsed = 0;
+        }
+      }
+    }
+    /*
+     * If it's ahead of the cached time, update
+     */
+    if (*access_time < present) {
+      *access_time = present;
+    }
+  } else {
+    /* No, so no hit and update the digest map with the current time */
+    access_time = tor_malloc(sizeof(*access_time));
+    *access_time = present;
+    digestmap_set(r->digests_seen, digest, access_time);
+  }
+
+  /* now scrub the cache if it's time */
+  replaycache_scrub_if_needed_internal(present, r);
+
+ done:
+  return rv;
+}
+
+/** See documentation for replaycache_scrub_if_needed()
+ */
+
+void
+replaycache_scrub_if_needed_internal(time_t present, replaycache_t *r)
+{
+  digestmap_iter_t *itr = NULL;
+  const char *digest;
+  void *valp;
+  time_t *access_time;
+  char scrub_this;
+
+  /* sanity check */
+  if (!r || !(r->digests_seen)) {
+    log_info(LD_BUG, "replaycache_scrub_if_needed_internal() called with"
+        " stupid parameters; please fix this.");
+    return;
+  }
+
+  /* scrub time yet? (scrubbed == 0 indicates never scrubbed before) */
+  if (present - r->scrubbed < r->scrub_interval && r->scrubbed > 0) return;
+
+  /* if we're never expiring, don't bother scrubbing */
+  if (r->horizon == 0) return;
+
+  /* okay, scrub time */
+  itr = digestmap_iter_init(r->digests_seen);
+  while (!digestmap_iter_done(itr)) {
+    scrub_this = 0;
+    digestmap_iter_get(itr, &digest, &valp);
+    access_time = (time_t *)valp;
+    if (access_time) {
+      /* aged out yet? */
+      if (*access_time < present - r->horizon) scrub_this = 1;
+    } else {
+      /* Buh? Get rid of it, anyway */
+      log_info(LD_BUG, "replaycache_scrub_if_needed_internal() saw a NULL"
+          " entry in the digestmap.");
+      scrub_this = 1;
+    }
+
+    if (scrub_this) {
+      /* Advance the iterator and remove this one */
+      itr = digestmap_iter_next_rmv(r->digests_seen, itr);
+      /* Free the value removed */
+      tor_free(access_time);
+    } else {
+      /* Just advance the iterator */
+      itr = digestmap_iter_next(r->digests_seen, itr);
+    }
+  }
+
+  /* update scrubbed timestamp */
+  if (present > r->scrubbed) r->scrubbed = present;
+}
+
+/** Test the buffer of length len point to by data against the replay cache r;
+ * the digest of the buffer will be added to the cache at the current time,
+ * and the function will return 1 if it was already seen within the cache's
+ * horizon, or 0 otherwise.
+ */
+
+int
+replaycache_add_and_test(replaycache_t *r, const void *data, int len)
+{
+  return replaycache_add_and_test_internal(time(NULL), r, data, len, NULL);
+}
+
+/** Like replaycache_add_and_test(), but if it's a hit also return the time
+ * elapsed since this digest was last seen.
+ */
+
+int
+replaycache_add_test_and_elapsed(
+    replaycache_t *r, const void *data, int len, time_t *elapsed)
+{
+  return replaycache_add_and_test_internal(time(NULL), r, data, len, elapsed);
+}
+
+/** Scrub aged entries out of r if sufficiently long has elapsed since r was
+ * last scrubbed.
+ */
+
+void
+replaycache_scrub_if_needed(replaycache_t *r)
+{
+  replaycache_scrub_if_needed_internal(time(NULL), r);
+}
+
diff --git a/src/or/replaycache.h b/src/or/replaycache.h
new file mode 100644
index 000000000..9f3107c51
--- /dev/null
+++ b/src/or/replaycache.h
@@ -0,0 +1,66 @@
+/* Copyright (c) 2012, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file replaycache.h
+ * \brief Header file for replaycache.c.
+ **/
+
+#ifndef _TOR_REPLAYCACHE_H
+#define _TOR_REPLAYCACHE_H
+
+typedef struct replaycache_s replaycache_t;
+
+#ifdef REPLAYCACHE_PRIVATE
+
+struct replaycache_s {
+  /* Scrub interval */
+  time_t scrub_interval;
+  /* Last scrubbed */
+  time_t scrubbed;
+  /*
+   * Horizon
+   * (don't return true on digests in the cache but older than this)
+   */
+  time_t horizon;
+  /*
+   * Digest map: keys are digests, values are times the digest was last seen
+   */
+  digestmap_t *digests_seen;
+};
+
+#endif /* REPLAYCACHE_PRIVATE */
+
+/* replaycache_t free/new */
+
+void replaycache_free(replaycache_t *r);
+replaycache_t * replaycache_new(time_t horizon, time_t interval);
+
+#ifdef REPLAYCACHE_PRIVATE
+
+/*
+ * replaycache_t internal functions:
+ *
+ * These take the time to treat as the present as an argument for easy unit
+ * testing.  For everything else, use the wrappers below instead.
+ */
+
+int replaycache_add_and_test_internal(
+    time_t present, replaycache_t *r, const void *data, int len,
+    time_t *elapsed);
+void replaycache_scrub_if_needed_internal(
+    time_t present, replaycache_t *r);
+
+#endif /* REPLAYCACHE_PRIVATE */
+
+/*
+ * replaycache_t methods
+ */
+
+int replaycache_add_and_test(replaycache_t *r, const void *data, int len);
+int replaycache_add_test_and_elapsed(
+    replaycache_t *r, const void *data, int len, time_t *elapsed);
+void replaycache_scrub_if_needed(replaycache_t *r);
+
+#endif
+
diff --git a/src/test/Makefile.am b/src/test/Makefile.am
index 31a464ee7..f3efdcc24 100644
--- a/src/test/Makefile.am
+++ b/src/test/Makefile.am
@@ -18,8 +18,10 @@ test_SOURCES = \
 	test_crypto.c \
 	test_data.c \
 	test_dir.c \
+	test_introduce.c \
 	test_microdesc.c \
 	test_pt.c \
+	test_replay.c \
 	test_util.c \
 	test_config.c \
 	tinytest.c
diff --git a/src/test/test.c b/src/test/test.c
index 6bf2d28d9..81172795f 100644
--- a/src/test/test.c
+++ b/src/test/test.c
@@ -1863,6 +1863,8 @@ extern struct testcase_t dir_tests[];
 extern struct testcase_t microdesc_tests[];
 extern struct testcase_t pt_tests[];
 extern struct testcase_t config_tests[];
+extern struct testcase_t introduce_tests[];
+extern struct testcase_t replaycache_tests[];
 
 static struct testgroup_t testgroups[] = {
   { "", test_array },
@@ -1875,6 +1877,8 @@ static struct testgroup_t testgroups[] = {
   { "dir/md/", microdesc_tests },
   { "pt/", pt_tests },
   { "config/", config_tests },
+  { "replaycache/", replaycache_tests },
+  { "introduce/", introduce_tests },
   END_OF_GROUPS
 };
 
diff --git a/src/test/test_introduce.c b/src/test/test_introduce.c
new file mode 100644
index 000000000..4fbfd1801
--- /dev/null
+++ b/src/test/test_introduce.c
@@ -0,0 +1,528 @@
+/* Copyright (c) 2012, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#include "orconfig.h"
+#include "crypto.h"
+#include "or.h"
+#include "test.h"
+
+#define RENDSERVICE_PRIVATE
+#include "rendservice.h"
+
+extern const char AUTHORITY_SIGNKEY_1[];
+
+static uint8_t v0_test_plaintext[] =
+    /* 20 bytes of rendezvous point nickname */
+  { 0x4e, 0x69, 0x63, 0x6b, 0x6e, 0x61, 0x6d, 0x65,
+    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
+    0x00, 0x00, 0x00, 0x00,
+    /* 20 bytes dummy rendezvous cookie */
+    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
+    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
+    0x10, 0x11, 0x12, 0x13,
+    /* 128 bytes dummy DH handshake data */
+    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
+    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
+    0x0f, 0x0e, 0x0d, 0x0c, 0x0b, 0x0a, 0x09, 0x08,
+    0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x01, 0x00,
+    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
+    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
+    0x0f, 0x0e, 0x0d, 0x0c, 0x0b, 0x0a, 0x09, 0x08,
+    0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x01, 0x00,
+    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
+    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
+    0x0f, 0x0e, 0x0d, 0x0c, 0x0b, 0x0a, 0x09, 0x08,
+    0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x01, 0x00,
+    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
+    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
+    0x0f, 0x0e, 0x0d, 0x0c, 0x0b, 0x0a, 0x09, 0x08,
+    0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x01, 0x00 };
+
+static uint8_t v1_test_plaintext[] =
+    /* Version byte */
+  { 0x01,
+    /* 42 bytes of dummy rendezvous point hex digest */
+    0x24, 0x30, 0x30, 0x30, 0x31, 0x30, 0x32, 0x30,
+    0x33, 0x30, 0x34, 0x30, 0x35, 0x30, 0x36, 0x30,
+    0x37, 0x30, 0x38, 0x30, 0x39, 0x30, 0x41, 0x30,
+    0x42, 0x30, 0x43, 0x30, 0x44, 0x30, 0x45, 0x30,
+    0x46, 0x31, 0x30, 0x31, 0x31, 0x31, 0x32, 0x31,
+    0x33, 0x00,
+    /* 20 bytes dummy rendezvous cookie */
+    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
+    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
+    0x10, 0x11, 0x12, 0x13,
+    /* 128 bytes dummy DH handshake data */
+    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
+    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
+    0x0f, 0x0e, 0x0d, 0x0c, 0x0b, 0x0a, 0x09, 0x08,
+    0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x01, 0x00,
+    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
+    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
+    0x0f, 0x0e, 0x0d, 0x0c, 0x0b, 0x0a, 0x09, 0x08,
+    0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x01, 0x00,
+    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
+    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
+    0x0f, 0x0e, 0x0d, 0x0c, 0x0b, 0x0a, 0x09, 0x08,
+    0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x01, 0x00,
+    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
+    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
+    0x0f, 0x0e, 0x0d, 0x0c, 0x0b, 0x0a, 0x09, 0x08,
+    0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x01, 0x00 };
+
+static uint8_t v2_test_plaintext[] =
+    /* Version byte */
+  { 0x02,
+    /* 4 bytes rendezvous point's IP address */
+    0xc0, 0xa8, 0x00, 0x01,
+    /* 2 bytes rendezvous point's OR port */
+    0x23, 0x5a,
+    /* 20 bytes dummy rendezvous point's identity digest */
+    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
+    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
+    0x10, 0x11, 0x12, 0x13,
+    /* 2 bytes length of onion key */
+    0x00, 0x8c,
+    /* Onion key (140 bytes taken from live test) */
+    0x30, 0x81, 0x89, 0x02, 0x81, 0x81, 0x00, 0xb1,
+    0xcd, 0x46, 0xa9, 0x18, 0xd2, 0x0f, 0x01, 0xf8,
+    0xb2, 0xad, 0xa4, 0x79, 0xb4, 0xbb, 0x4b, 0xf4,
+    0x54, 0x1e, 0x3f, 0x03, 0x54, 0xcf, 0x7c, 0xb6,
+    0xb5, 0xf0, 0xfe, 0xed, 0x4b, 0x7d, 0xd7, 0x61,
+    0xdb, 0x6d, 0xd9, 0x19, 0xe2, 0x72, 0x04, 0xaa,
+    0x3e, 0x89, 0x26, 0x14, 0x62, 0x9a, 0x6c, 0x11,
+    0x0b, 0x35, 0x99, 0x2c, 0x9f, 0x2c, 0x64, 0xa1,
+    0xd9, 0xe2, 0x88, 0xce, 0xf6, 0x54, 0xfe, 0x1d,
+    0x37, 0x5e, 0x6d, 0x73, 0x95, 0x54, 0x90, 0xf0,
+    0x7b, 0xfa, 0xd4, 0x44, 0xac, 0xb2, 0x23, 0x9f,
+    0x75, 0x36, 0xe2, 0x78, 0x62, 0x82, 0x80, 0xa4,
+    0x23, 0x22, 0xc9, 0xbf, 0xc4, 0x36, 0xd1, 0x31,
+    0x33, 0x8e, 0x64, 0xb4, 0xa9, 0x74, 0xa1, 0xcb,
+    0x42, 0x8d, 0x60, 0xc7, 0xbb, 0x8e, 0x6e, 0x0f,
+    0x36, 0x74, 0x8e, 0xf4, 0x08, 0x99, 0x06, 0x92,
+    0xb1, 0x3f, 0xb3, 0xdd, 0xed, 0xf7, 0xc9, 0x02,
+    0x03, 0x01, 0x00, 0x01,
+    /* 20 bytes dummy rendezvous cookie */
+    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
+    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
+    0x10, 0x11, 0x12, 0x13,
+    /* 128 bytes dummy DH handshake data */
+    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
+    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
+    0x0f, 0x0e, 0x0d, 0x0c, 0x0b, 0x0a, 0x09, 0x08,
+    0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x01, 0x00,
+    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
+    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
+    0x0f, 0x0e, 0x0d, 0x0c, 0x0b, 0x0a, 0x09, 0x08,
+    0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x01, 0x00,
+    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
+    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
+    0x0f, 0x0e, 0x0d, 0x0c, 0x0b, 0x0a, 0x09, 0x08,
+    0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x01, 0x00,
+    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
+    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
+    0x0f, 0x0e, 0x0d, 0x0c, 0x0b, 0x0a, 0x09, 0x08,
+    0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x01, 0x00 };
+
+static uint8_t v3_no_auth_test_plaintext[] =
+    /* Version byte */
+  { 0x03,
+    /* Auth type (0 for no auth len/auth data) */
+    0x00,
+    /* Timestamp */
+    0x50, 0x0b, 0xb5, 0xaa,
+    /* 4 bytes rendezvous point's IP address */
+    0xc0, 0xa8, 0x00, 0x01,
+    /* 2 bytes rendezvous point's OR port */
+    0x23, 0x5a,
+    /* 20 bytes dummy rendezvous point's identity digest */
+    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
+    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
+    0x10, 0x11, 0x12, 0x13,
+    /* 2 bytes length of onion key */
+    0x00, 0x8c,
+    /* Onion key (140 bytes taken from live test) */
+    0x30, 0x81, 0x89, 0x02, 0x81, 0x81, 0x00, 0xb1,
+    0xcd, 0x46, 0xa9, 0x18, 0xd2, 0x0f, 0x01, 0xf8,
+    0xb2, 0xad, 0xa4, 0x79, 0xb4, 0xbb, 0x4b, 0xf4,
+    0x54, 0x1e, 0x3f, 0x03, 0x54, 0xcf, 0x7c, 0xb6,
+    0xb5, 0xf0, 0xfe, 0xed, 0x4b, 0x7d, 0xd7, 0x61,
+    0xdb, 0x6d, 0xd9, 0x19, 0xe2, 0x72, 0x04, 0xaa,
+    0x3e, 0x89, 0x26, 0x14, 0x62, 0x9a, 0x6c, 0x11,
+    0x0b, 0x35, 0x99, 0x2c, 0x9f, 0x2c, 0x64, 0xa1,
+    0xd9, 0xe2, 0x88, 0xce, 0xf6, 0x54, 0xfe, 0x1d,
+    0x37, 0x5e, 0x6d, 0x73, 0x95, 0x54, 0x90, 0xf0,
+    0x7b, 0xfa, 0xd4, 0x44, 0xac, 0xb2, 0x23, 0x9f,
+    0x75, 0x36, 0xe2, 0x78, 0x62, 0x82, 0x80, 0xa4,
+    0x23, 0x22, 0xc9, 0xbf, 0xc4, 0x36, 0xd1, 0x31,
+    0x33, 0x8e, 0x64, 0xb4, 0xa9, 0x74, 0xa1, 0xcb,
+    0x42, 0x8d, 0x60, 0xc7, 0xbb, 0x8e, 0x6e, 0x0f,
+    0x36, 0x74, 0x8e, 0xf4, 0x08, 0x99, 0x06, 0x92,
+    0xb1, 0x3f, 0xb3, 0xdd, 0xed, 0xf7, 0xc9, 0x02,
+    0x03, 0x01, 0x00, 0x01,
+    /* 20 bytes dummy rendezvous cookie */
+    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
+    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
+    0x10, 0x11, 0x12, 0x13,
+    /* 128 bytes dummy DH handshake data */
+    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
+    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
+    0x0f, 0x0e, 0x0d, 0x0c, 0x0b, 0x0a, 0x09, 0x08,
+    0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x01, 0x00,
+    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
+    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
+    0x0f, 0x0e, 0x0d, 0x0c, 0x0b, 0x0a, 0x09, 0x08,
+    0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x01, 0x00,
+    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
+    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
+    0x0f, 0x0e, 0x0d, 0x0c, 0x0b, 0x0a, 0x09, 0x08,
+    0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x01, 0x00,
+    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
+    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
+    0x0f, 0x0e, 0x0d, 0x0c, 0x0b, 0x0a, 0x09, 0x08,
+    0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x01, 0x00 };
+
+static uint8_t v3_basic_auth_test_plaintext[] =
+    /* Version byte */
+  { 0x03,
+    /* Auth type (1 for REND_BASIC_AUTH) */
+    0x01,
+    /* Auth len (must be 16 bytes for REND_BASIC_AUTH) */
+    0x00, 0x10,
+    /* Auth data (a 16-byte dummy descriptor cookie) */
+    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
+    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
+    /* Timestamp */
+    0x50, 0x0b, 0xb5, 0xaa,
+    /* 4 bytes rendezvous point's IP address */
+    0xc0, 0xa8, 0x00, 0x01,
+    /* 2 bytes rendezvous point's OR port */
+    0x23, 0x5a,
+    /* 20 bytes dummy rendezvous point's identity digest */
+    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
+    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
+    0x10, 0x11, 0x12, 0x13,
+    /* 2 bytes length of onion key */
+    0x00, 0x8c,
+    /* Onion key (140 bytes taken from live test) */
+    0x30, 0x81, 0x89, 0x02, 0x81, 0x81, 0x00, 0xb1,
+    0xcd, 0x46, 0xa9, 0x18, 0xd2, 0x0f, 0x01, 0xf8,
+    0xb2, 0xad, 0xa4, 0x79, 0xb4, 0xbb, 0x4b, 0xf4,
+    0x54, 0x1e, 0x3f, 0x03, 0x54, 0xcf, 0x7c, 0xb6,
+    0xb5, 0xf0, 0xfe, 0xed, 0x4b, 0x7d, 0xd7, 0x61,
+    0xdb, 0x6d, 0xd9, 0x19, 0xe2, 0x72, 0x04, 0xaa,
+    0x3e, 0x89, 0x26, 0x14, 0x62, 0x9a, 0x6c, 0x11,
+    0x0b, 0x35, 0x99, 0x2c, 0x9f, 0x2c, 0x64, 0xa1,
+    0xd9, 0xe2, 0x88, 0xce, 0xf6, 0x54, 0xfe, 0x1d,
+    0x37, 0x5e, 0x6d, 0x73, 0x95, 0x54, 0x90, 0xf0,
+    0x7b, 0xfa, 0xd4, 0x44, 0xac, 0xb2, 0x23, 0x9f,
+    0x75, 0x36, 0xe2, 0x78, 0x62, 0x82, 0x80, 0xa4,
+    0x23, 0x22, 0xc9, 0xbf, 0xc4, 0x36, 0xd1, 0x31,
+    0x33, 0x8e, 0x64, 0xb4, 0xa9, 0x74, 0xa1, 0xcb,
+    0x42, 0x8d, 0x60, 0xc7, 0xbb, 0x8e, 0x6e, 0x0f,
+    0x36, 0x74, 0x8e, 0xf4, 0x08, 0x99, 0x06, 0x92,
+    0xb1, 0x3f, 0xb3, 0xdd, 0xed, 0xf7, 0xc9, 0x02,
+    0x03, 0x01, 0x00, 0x01,
+    /* 20 bytes dummy rendezvous cookie */
+    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
+    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
+    0x10, 0x11, 0x12, 0x13,
+    /* 128 bytes dummy DH handshake data */
+    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
+    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
+    0x0f, 0x0e, 0x0d, 0x0c, 0x0b, 0x0a, 0x09, 0x08,
+    0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x01, 0x00,
+    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
+    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
+    0x0f, 0x0e, 0x0d, 0x0c, 0x0b, 0x0a, 0x09, 0x08,
+    0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x01, 0x00,
+    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
+    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
+    0x0f, 0x0e, 0x0d, 0x0c, 0x0b, 0x0a, 0x09, 0x08,
+    0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x01, 0x00,
+    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07,
+    0x08, 0x09, 0x0a, 0x0b, 0x0c, 0x0d, 0x0e, 0x0f,
+    0x0f, 0x0e, 0x0d, 0x0c, 0x0b, 0x0a, 0x09, 0x08,
+    0x07, 0x06, 0x05, 0x04, 0x03, 0x02, 0x01, 0x00 };
+
+static void do_decrypt_test(uint8_t *plaintext, size_t plaintext_len);
+static void do_early_parse_test(uint8_t *plaintext, size_t plaintext_len);
+static void do_late_parse_test(uint8_t *plaintext, size_t plaintext_len);
+static void do_parse_test(uint8_t *plaintext, size_t plaintext_len, int phase);
+static ssize_t make_intro_from_plaintext(
+    void *buf, size_t len, crypto_pk_t *key, void **cell_out);
+
+#define EARLY_PARSE_ONLY 1
+#define DECRYPT_ONLY 2
+#define ALL_PARSING 3
+
+static void
+do_early_parse_test(uint8_t *plaintext, size_t plaintext_len)
+{
+  do_parse_test(plaintext, plaintext_len, EARLY_PARSE_ONLY);
+}
+
+static void
+do_decrypt_test(uint8_t *plaintext, size_t plaintext_len)
+{
+  do_parse_test(plaintext, plaintext_len, DECRYPT_ONLY);
+}
+
+static void
+do_late_parse_test(uint8_t *plaintext, size_t plaintext_len)
+{
+  do_parse_test(plaintext, plaintext_len, ALL_PARSING);
+}
+
+/** Test utility function: checks that the <b>plaintext_len</b>-byte string at
+ * <b>plaintext</b> is at least superficially parseable.
+ */
+static void
+do_parse_test(uint8_t *plaintext, size_t plaintext_len, int phase)
+{
+  crypto_pk_t *k = NULL;
+  int r;
+  uint8_t *cell = NULL;
+  size_t cell_len;
+  rend_intro_cell_t *parsed_req = NULL;
+  char *err_msg = NULL;
+  char digest[DIGEST_LEN];
+
+  /* Get a key */
+  k = crypto_pk_new();
+  test_assert(k);
+  r = crypto_pk_read_private_key_from_string(k, AUTHORITY_SIGNKEY_1, -1);
+  test_assert(!r);
+
+  /* Get digest for future comparison */
+  r = crypto_pk_get_digest(k, digest);
+  test_assert(r >= 0);
+
+  /* Make a cell out of it */
+  r = make_intro_from_plaintext(
+      plaintext, plaintext_len,
+      k, (void **)(&cell));
+  test_assert(r > 0);
+  test_assert(cell);
+  cell_len = r;
+
+  /* Do early parsing */
+  parsed_req = rend_service_begin_parse_intro(cell, cell_len, 2, &err_msg);
+  test_assert(parsed_req);
+  test_assert(!err_msg);
+  test_memeq(parsed_req->pk, digest, DIGEST_LEN);
+  test_assert(parsed_req->ciphertext);
+  test_assert(parsed_req->ciphertext_len > 0);
+
+  if (phase == EARLY_PARSE_ONLY)
+    goto done;
+
+  /* Do decryption */
+  r = rend_service_decrypt_intro(parsed_req, k, &err_msg);
+  test_assert(!r);
+  test_assert(!err_msg);
+  test_assert(parsed_req->plaintext);
+  test_assert(parsed_req->plaintext_len > 0);
+
+  if (phase == DECRYPT_ONLY)
+    goto done;
+
+  /* Do late parsing */
+  r = rend_service_parse_intro_plaintext(parsed_req, &err_msg);
+  test_assert(!r);
+  test_assert(!err_msg);
+  test_assert(parsed_req->parsed);
+
+ done:
+  tor_free(cell);
+  crypto_pk_free(k);
+  rend_service_free_intro(parsed_req);
+  tor_free(err_msg);
+}
+
+/** Given the plaintext of the encrypted part of an INTRODUCE1/2 and a key,
+ * construct the encrypted cell for testing.
+ */
+
+static ssize_t
+make_intro_from_plaintext(
+    void *buf, size_t len, crypto_pk_t *key, void **cell_out)
+{
+  char *cell = NULL;
+  ssize_t cell_len = -1, r;
+  /* Assemble key digest and ciphertext, then construct the cell */
+  ssize_t ciphertext_size;
+
+  if (!(buf && key && len > 0 && cell_out)) goto done;
+
+  /*
+   * Figure out an upper bound on how big the ciphertext will be
+   * (see crypto_pk_public_hybrid_encrypt())
+   */
+  ciphertext_size = PKCS1_OAEP_PADDING_OVERHEAD;
+  ciphertext_size += crypto_pk_keysize(key);
+  ciphertext_size += CIPHER_KEY_LEN;
+  ciphertext_size += len;
+
+  /*
+   * Allocate space for the cell
+   */
+  cell = tor_malloc(DIGEST_LEN + ciphertext_size);
+
+  /* Compute key digest (will be first DIGEST_LEN octets of cell) */
+  r = crypto_pk_get_digest(key, cell);
+  test_assert(r >= 0);
+
+  /* Do encryption */
+  r = crypto_pk_public_hybrid_encrypt(
+      key, cell + DIGEST_LEN, ciphertext_size,
+      buf, len,
+      PK_PKCS1_OAEP_PADDING, 0);
+  test_assert(r >= 0);
+
+  /* Figure out cell length */
+  cell_len = DIGEST_LEN + r;
+
+  /* Output the cell */
+  *cell_out = cell;
+
+ done:
+  return cell_len;
+}
+
+/** Test v0 INTRODUCE2 parsing through decryption only
+ */
+
+static void
+test_introduce_decrypt_v0(void)
+{
+  do_decrypt_test(v0_test_plaintext, sizeof(v0_test_plaintext));
+}
+
+/** Test v1 INTRODUCE2 parsing through decryption only
+ */
+
+static void
+test_introduce_decrypt_v1(void)
+{
+  do_decrypt_test(v1_test_plaintext, sizeof(v1_test_plaintext));
+}
+
+/** Test v2 INTRODUCE2 parsing through decryption only
+ */
+
+static void
+test_introduce_decrypt_v2(void)
+{
+  do_decrypt_test(v2_test_plaintext, sizeof(v2_test_plaintext));
+}
+
+/** Test v3 INTRODUCE2 parsing through decryption only
+ */
+
+static void
+test_introduce_decrypt_v3(void)
+{
+  do_decrypt_test(
+      v3_no_auth_test_plaintext, sizeof(v3_no_auth_test_plaintext));
+  do_decrypt_test(
+      v3_basic_auth_test_plaintext, sizeof(v3_basic_auth_test_plaintext));
+}
+
+/** Test v0 INTRODUCE2 parsing through early parsing only
+ */
+
+static void
+test_introduce_early_parse_v0(void)
+{
+  do_early_parse_test(v0_test_plaintext, sizeof(v0_test_plaintext));
+}
+
+/** Test v1 INTRODUCE2 parsing through early parsing only
+ */
+
+static void
+test_introduce_early_parse_v1(void)
+{
+  do_early_parse_test(v1_test_plaintext, sizeof(v1_test_plaintext));
+}
+
+/** Test v2 INTRODUCE2 parsing through early parsing only
+ */
+
+static void
+test_introduce_early_parse_v2(void)
+{
+  do_early_parse_test(v2_test_plaintext, sizeof(v2_test_plaintext));
+}
+
+/** Test v3 INTRODUCE2 parsing through early parsing only
+ */
+
+static void
+test_introduce_early_parse_v3(void)
+{
+  do_early_parse_test(
+      v3_no_auth_test_plaintext, sizeof(v3_no_auth_test_plaintext));
+  do_early_parse_test(
+      v3_basic_auth_test_plaintext, sizeof(v3_basic_auth_test_plaintext));
+}
+
+/** Test v0 INTRODUCE2 parsing
+ */
+
+static void
+test_introduce_late_parse_v0(void)
+{
+  do_late_parse_test(v0_test_plaintext, sizeof(v0_test_plaintext));
+}
+
+/** Test v1 INTRODUCE2 parsing
+ */
+
+static void
+test_introduce_late_parse_v1(void)
+{
+  do_late_parse_test(v1_test_plaintext, sizeof(v1_test_plaintext));
+}
+
+/** Test v2 INTRODUCE2 parsing
+ */
+
+static void
+test_introduce_late_parse_v2(void)
+{
+  do_late_parse_test(v2_test_plaintext, sizeof(v2_test_plaintext));
+}
+
+/** Test v3 INTRODUCE2 parsing
+ */
+
+static void
+test_introduce_late_parse_v3(void)
+{
+  do_late_parse_test(
+      v3_no_auth_test_plaintext, sizeof(v3_no_auth_test_plaintext));
+  do_late_parse_test(
+      v3_basic_auth_test_plaintext, sizeof(v3_basic_auth_test_plaintext));
+}
+
+#define INTRODUCE_LEGACY(name) \
+  { #name, legacy_test_helper, 0, &legacy_setup, test_introduce_ ## name }
+
+struct testcase_t introduce_tests[] = {
+  INTRODUCE_LEGACY(early_parse_v0),
+  INTRODUCE_LEGACY(early_parse_v1),
+  INTRODUCE_LEGACY(early_parse_v2),
+  INTRODUCE_LEGACY(early_parse_v3),
+  INTRODUCE_LEGACY(decrypt_v0),
+  INTRODUCE_LEGACY(decrypt_v1),
+  INTRODUCE_LEGACY(decrypt_v2),
+  INTRODUCE_LEGACY(decrypt_v3),
+  INTRODUCE_LEGACY(late_parse_v0),
+  INTRODUCE_LEGACY(late_parse_v1),
+  INTRODUCE_LEGACY(late_parse_v2),
+  INTRODUCE_LEGACY(late_parse_v3),
+  END_OF_TESTCASES
+};
+
diff --git a/src/test/test_replay.c b/src/test/test_replay.c
new file mode 100644
index 000000000..217b5554d
--- /dev/null
+++ b/src/test/test_replay.c
@@ -0,0 +1,184 @@
+/* Copyright (c) 2012, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#define REPLAYCACHE_PRIVATE
+
+#include "orconfig.h"
+#include "or.h"
+#include "replaycache.h"
+#include "test.h"
+
+static const char *test_buffer =
+  "Lorem ipsum dolor sit amet, consectetur adipisici elit, sed do eiusmod"
+  " tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim"
+  " veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea"
+  " commodo consequat. Duis aute irure dolor in reprehenderit in voluptate"
+  " velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint"
+  " occaecat cupidatat non proident, sunt in culpa qui officia deserunt"
+  " mollit anim id est laborum.";
+
+static void
+test_replaycache_alloc(void)
+{
+  replaycache_t *r = NULL;
+
+  r = replaycache_new(600, 300);
+  test_assert(r != NULL);
+  if (!r) goto done;
+
+ done:
+  if (r) replaycache_free(r);
+
+  return;
+}
+
+static void
+test_replaycache_miss(void)
+{
+  replaycache_t *r = NULL;
+  int result;
+
+  r = replaycache_new(600, 300);
+  test_assert(r != NULL);
+  if (!r) goto done;
+
+  result =
+    replaycache_add_and_test_internal(1200, r, test_buffer,
+        strlen(test_buffer), NULL);
+  test_eq(result, 0);
+
+ done:
+  if (r) replaycache_free(r);
+
+  return;
+}
+
+static void
+test_replaycache_hit(void)
+{
+  replaycache_t *r = NULL;
+  int result;
+
+  r = replaycache_new(600, 300);
+  test_assert(r != NULL);
+  if (!r) goto done;
+
+  result =
+    replaycache_add_and_test_internal(1200, r, test_buffer,
+        strlen(test_buffer), NULL);
+  test_eq(result, 0);
+
+  result =
+    replaycache_add_and_test_internal(1300, r, test_buffer,
+        strlen(test_buffer), NULL);
+  test_eq(result, 1);
+
+ done:
+  if (r) replaycache_free(r);
+
+  return;
+}
+
+static void
+test_replaycache_age(void)
+{
+  replaycache_t *r = NULL;
+  int result;
+
+  r = replaycache_new(600, 300);
+  test_assert(r != NULL);
+  if (!r) goto done;
+
+  result =
+    replaycache_add_and_test_internal(1200, r, test_buffer,
+        strlen(test_buffer), NULL);
+  test_eq(result, 0);
+
+  result =
+    replaycache_add_and_test_internal(1300, r, test_buffer,
+        strlen(test_buffer), NULL);
+  test_eq(result, 1);
+
+  result =
+    replaycache_add_and_test_internal(3000, r, test_buffer,
+        strlen(test_buffer), NULL);
+  test_eq(result, 0);
+
+ done:
+  if (r) replaycache_free(r);
+
+  return;
+}
+
+static void
+test_replaycache_elapsed(void)
+{
+  replaycache_t *r = NULL;
+  int result;
+  time_t elapsed;
+
+  r = replaycache_new(600, 300);
+  test_assert(r != NULL);
+  if (!r) goto done;
+
+  result =
+    replaycache_add_and_test_internal(1200, r, test_buffer,
+        strlen(test_buffer), NULL);
+  test_eq(result, 0);
+
+  result =
+    replaycache_add_and_test_internal(1300, r, test_buffer,
+        strlen(test_buffer), &elapsed);
+  test_eq(result, 1);
+  test_eq(elapsed, 100);
+
+ done:
+  if (r) replaycache_free(r);
+
+  return;
+}
+
+static void
+test_replaycache_noexpire(void)
+{
+  replaycache_t *r = NULL;
+  int result;
+
+  r = replaycache_new(0, 0);
+  test_assert(r != NULL);
+  if (!r) goto done;
+
+  result =
+    replaycache_add_and_test_internal(1200, r, test_buffer,
+        strlen(test_buffer), NULL);
+  test_eq(result, 0);
+
+  result =
+    replaycache_add_and_test_internal(1300, r, test_buffer,
+        strlen(test_buffer), NULL);
+  test_eq(result, 1);
+
+  result =
+    replaycache_add_and_test_internal(3000, r, test_buffer,
+        strlen(test_buffer), NULL);
+  test_eq(result, 1);
+
+ done:
+  if (r) replaycache_free(r);
+
+  return;
+}
+
+#define REPLAYCACHE_LEGACY(name) \
+  { #name, legacy_test_helper, 0, &legacy_setup, test_replaycache_ ## name }
+
+struct testcase_t replaycache_tests[] = {
+  REPLAYCACHE_LEGACY(alloc),
+  REPLAYCACHE_LEGACY(miss),
+  REPLAYCACHE_LEGACY(hit),
+  REPLAYCACHE_LEGACY(age),
+  REPLAYCACHE_LEGACY(elapsed),
+  REPLAYCACHE_LEGACY(noexpire),
+  END_OF_TESTCASES
+};
+