Add patch 4 from Karsten for proposal 121, slightly modified. Karsten should definitely re-review the bits I changed.

svn:r16955

11 files changed, 661 insertions, 236 deletions

diff --git a/ChangeLog b/ChangeLog
index 7f477fb64b..f9f5095384 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,4 +1,13 @@
 Changes in version 0.2.1.6-alpha - 2008-09-xx
+  o Major features:
+    - Implement proposal 121: make it possible to build hidden services
+      that only certain clients are allowed to connect to.  This is
+      enforced at several points, so that unauthorized clients are
+      unable to send INTRODUCE cells to the service, or even (depending
+      on the type of authentication) to learn introduction points.  This
+      feature raises the bar for certain kinds of active attacks against
+      hidden services.
+
   o Major bugfixes:
     - Fix a bug when parsing ports in tor_addr_port_parse() that caused
       Tor to fail to start if you had it configured to use a bridge
@@ -63,6 +72,8 @@ Changes in version 0.2.1.6-alpha - 2008-09-xx
       actual mistakes  we're making here.
     - Refactor unit testing logic so that dmalloc can be used sensibly with
       unit tests to check for memory leaks.
+    - Move all hidden-service related fields from connection and circuit
+      structure to substructures: this way they won't eat so much memory.
 
 
 Changes in version 0.2.0.31 - 2008-09-03
diff --git a/doc/tor.1.in b/doc/tor.1.in
index 388a5c9e07..13f3be471d 100644
--- a/doc/tor.1.in
+++ b/doc/tor.1.in
@@ -472,6 +472,15 @@ used when \fBFascistFirewall\fR is set. This option is deprecated; use
 ReachableAddresses instead. (Default: 80, 443)
 .LP
 .TP
+\fBHidServAuth \fR\fIonion-address\fR \fIauth-cookie\fP \fIservice-name\fR 
+Client authorization for a hidden service. Valid onion addresses contain 16
+characters in a-z2-7 plus ".onion", and valid auth cookies contain 22
+characters in A-Za-z0-9+/. The service name is only used for internal
+purposes, e.g., for Tor controllers. This option may be used multiple times
+for different hidden services. If a hidden service uses authorization and
+this option is not set, the hidden service is not accessible.
+.LP
+.TP
 \fBReachableAddresses \fR\fIADDR\fP[\fB/\fP\fIMASK\fP][:\fIPORT\fP]...\fP
 A comma-separated list of IP addresses and ports that your firewall allows you
 to connect to. The format is as
@@ -1269,6 +1278,18 @@ A list of rendezvous service descriptor versions to publish for the hidden
 service. Possible version numbers are 0 and 2. (Default: 0, 2)
 .LP
 .TP
+\fBHiddenServiceAuthorizeClient \fR\fIauth-type\fR \fR\fIclient-name\fR,\fIclient-name\fR,\fI...\fP
+If configured, the hidden service is accessible for authorized clients
+only. The auth-type can either be 'basic' for a general-purpose
+authorization protocol or 'stealth' for a less scalable protocol that also
+hides service activity from unauthorized clients. Only clients that are
+listed here are authorized to access the hidden service. Valid client names
+are 1 to 19 characters long and only use characters in A-Za-z0-9+-_
+(no spaces). If this option is set, the hidden service is not accessible
+for clients without authorization any more. Generated authorization data
+can be found in the hostname file.
+.LP
+.TP
 \fBRendPostPeriod \fR\fIN\fR \fBseconds\fR|\fBminutes\fR|\fBhours\fR|\fBdays\fR|\fBweeks\fP
 Every time the specified period elapses, Tor uploads any rendezvous
 service descriptors to the directory servers.  This information is also
@@ -1453,10 +1474,17 @@ Only used by authoritative directory servers.  Tracks measurements for router me
 .TP
 .B \fIHiddenServiceDirectory\fP/hostname 
 The <base32-encoded-fingerprint>.onion domain name for this hidden service.
+If the hidden service is restricted to authorized clients only, this file
+also contains authorization data for all clients.
 .LP
 .TP
 .B \fIHiddenServiceDirectory\fP/private_key 
 The private key for this hidden service.
+.LP
+.TP
+.B \fIHiddenServiceDirectory\fP/client_keys 
+Authorization data for a hidden service that is only accessible by authorized
+clients.
 .SH SEE ALSO
 .BR privoxy (1),
 .BR tsocks (1),
diff --git a/src/or/circuitlist.c b/src/or/circuitlist.c
index 2f19bbf2c6..29dd1fd50a 100644
--- a/src/or/circuitlist.c
+++ b/src/or/circuitlist.c
@@ -401,7 +401,8 @@ circuit_free(circuit_t *circ)
     circuit_free_cpath(ocirc->cpath);
     if (ocirc->intro_key)
       crypto_free_pk_env(ocirc->intro_key);
-
+    if (ocirc->rend_data)
+      rend_data_free(ocirc->rend_data);
   } else {
     or_circuit_t *ocirc = TO_OR_CIRCUIT(circ);
     mem = ocirc;
@@ -720,7 +721,7 @@ circuit_unlink_all_from_or_conn(or_connection_t *conn, int reason)
 }
 
 /** Return a circ such that:
- *  - circ-\>rend_query is equal to <b>rend_query</b>, and
+ *  - circ-\>rend_data-\>query is equal to <b>rend_query</b>, and
  *  - circ-\>purpose is equal to <b>purpose</b>.
  *
  * Return NULL if no such circuit exists.
@@ -734,9 +735,13 @@ circuit_get_by_rend_query_and_purpose(const char *rend_query, uint8_t purpose)
 
   for (circ = global_circuitlist; circ; circ = circ->next) {
     if (!circ->marked_for_close &&
-        circ->purpose == purpose &&
-        !rend_cmp_service_ids(rend_query, TO_ORIGIN_CIRCUIT(circ)->rend_query))
-      return TO_ORIGIN_CIRCUIT(circ);
+        circ->purpose == purpose) {
+      origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
+      if (ocirc->rend_data &&
+          !rend_cmp_service_ids(rend_query,
+                                ocirc->rend_data->onion_address))
+        return ocirc;
+    }
   }
   return NULL;
 }
@@ -764,7 +769,8 @@ circuit_get_next_by_pk_and_purpose(origin_circuit_t *start,
       continue;
     if (!digest)
       return TO_ORIGIN_CIRCUIT(circ);
-    else if (!memcmp(TO_ORIGIN_CIRCUIT(circ)->rend_pk_digest,
+    else if (TO_ORIGIN_CIRCUIT(circ)->rend_data &&
+             !memcmp(TO_ORIGIN_CIRCUIT(circ)->rend_data->rend_pk_digest,
                      digest, DIGEST_LEN))
       return TO_ORIGIN_CIRCUIT(circ);
   }
@@ -1020,13 +1026,14 @@ _circuit_mark_for_close(circuit_t *circ, int reason, int line,
     origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
     tor_assert(circ->state == CIRCUIT_STATE_OPEN);
     tor_assert(ocirc->build_state->chosen_exit);
+    tor_assert(ocirc->rend_data);
     /* treat this like getting a nack from it */
     log_info(LD_REND, "Failed intro circ %s to %s (awaiting ack). "
              "Removing from descriptor.",
-             safe_str(ocirc->rend_query),
+             safe_str(ocirc->rend_data->onion_address),
              safe_str(build_state_get_exit_nickname(ocirc->build_state)));
     rend_client_remove_intro_point(ocirc->build_state->chosen_exit,
-                                   ocirc->rend_query);
+                                   ocirc->rend_data);
   }
   if (circ->n_conn)
     connection_or_send_destroy(circ->n_circ_id, circ->n_conn, reason);
diff --git a/src/or/circuituse.c b/src/or/circuituse.c
index 2b34f7e6ee..e0c855407a 100644
--- a/src/or/circuituse.c
+++ b/src/or/circuituse.c
@@ -121,8 +121,12 @@ circuit_is_acceptable(circuit_t *circ, edge_connection_t *conn,
       return 0;
     }
   } else { /* not general */
-    if (rend_cmp_service_ids(conn->rend_query,
-                             TO_ORIGIN_CIRCUIT(circ)->rend_query)) {
+    origin_circuit_t *ocirc = TO_ORIGIN_CIRCUIT(circ);
+    if ((conn->rend_data && !ocirc->rend_data) ||
+        (!conn->rend_data && ocirc->rend_data) ||
+        (conn->rend_data && ocirc->rend_data &&
+         rend_cmp_service_ids(conn->rend_data->onion_address,
+                              ocirc->rend_data->onion_address))) {
       /* this circ is not for this conn */
       return 0;
     }
@@ -300,7 +304,7 @@ circuit_expire_building(time_t now)
           /* c_rend_ready circs measure age since timestamp_dirty,
            * because that's set when they switch purposes
            */
-          if (TO_ORIGIN_CIRCUIT(victim)->rend_query[0] ||
+          if (TO_ORIGIN_CIRCUIT(victim)->rend_data ||
               victim->timestamp_dirty > cutoff)
             continue;
           break;
@@ -1076,18 +1080,24 @@ circuit_get_open_circ_or_launch(edge_connection_t *conn,
 
     if (desired_circuit_purpose == CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT) {
       /* need to pick an intro point */
-      extend_info = rend_client_get_random_intro(conn->rend_query);
+      tor_assert(conn->rend_data);
+      extend_info = rend_client_get_random_intro(conn->rend_data);
       if (!extend_info) {
         log_info(LD_REND,
                  "No intro points for '%s': refetching service descriptor.",
-                 safe_str(conn->rend_query));
-        rend_client_refetch_renddesc(conn->rend_query);
-        rend_client_refetch_v2_renddesc(conn->rend_query);
+                 safe_str(conn->rend_data->onion_address));
+        /* Fetch both, v0 and v2 rend descriptors in parallel. Use whichever
+         * arrives first. Exception: When using client authorization, only
+         * fetch v2 descriptors.*/
+        rend_client_refetch_v2_renddesc(conn->rend_data);
+        if (conn->rend_data->auth_type == REND_NO_AUTH)
+          rend_client_refetch_renddesc(conn->rend_data->onion_address);
         conn->_base.state = AP_CONN_STATE_RENDDESC_WAIT;
         return 0;
       }
       log_info(LD_REND,"Chose '%s' as intro point for '%s'.",
-               extend_info->nickname, safe_str(conn->rend_query));
+               extend_info->nickname,
+               safe_str(conn->rend_data->onion_address));
     }
 
     /* If we have specified a particular exit node for our
@@ -1163,7 +1173,7 @@ circuit_get_open_circ_or_launch(edge_connection_t *conn,
       rep_hist_note_used_internal(time(NULL), need_uptime, 1);
       if (circ) {
         /* write the service_id into circ */
-        strlcpy(circ->rend_query, conn->rend_query, sizeof(circ->rend_query));
+        circ->rend_data = rend_data_dup(conn->rend_data);
         if (circ->_base.purpose == CIRCUIT_PURPOSE_C_ESTABLISH_REND &&
             circ->_base.state == CIRCUIT_STATE_OPEN)
           rend_client_rendcirc_has_opened(circ);
diff --git a/src/or/connection.c b/src/or/connection.c
index 6a34694de3..963c64e5b6 100644
--- a/src/or/connection.c
+++ b/src/or/connection.c
@@ -385,6 +385,8 @@ _connection_free(connection_t *conn)
       memset(edge_conn->socks_request, 0xcc, sizeof(socks_request_t));
       tor_free(edge_conn->socks_request);
     }
+    if (edge_conn->rend_data)
+      rend_data_free(edge_conn->rend_data);
   }
   if (conn->type == CONN_TYPE_CONTROL) {
     control_connection_t *control_conn = TO_CONTROL_CONN(conn);
@@ -405,6 +407,8 @@ _connection_free(connection_t *conn)
     }
     if (dir_conn->cached_dir)
       cached_dir_decref(dir_conn->cached_dir);
+    if (dir_conn->rend_data)
+      rend_data_free(dir_conn->rend_data);
   }
 
   if (conn->s >= 0) {
@@ -523,21 +527,22 @@ connection_about_to_close_connection(connection_t *conn)
          * failed: forget about this router, and maybe try again. */
         connection_dir_request_failed(dir_conn);
       }
-      if (conn->purpose == DIR_PURPOSE_FETCH_RENDDESC) {
+      if (conn->purpose == DIR_PURPOSE_FETCH_RENDDESC && dir_conn->rend_data) {
         /* Give it a try. However, there is no re-fetching for v0 rend
          * descriptors; if the response is empty or the descriptor is
          * unusable, close pending connections (unless a v2 request is
          * still in progress). */
-        rend_client_desc_trynow(dir_conn->rend_query, 0);
+        rend_client_desc_trynow(dir_conn->rend_data->onion_address, 0);
       }
       /* If we were trying to fetch a v2 rend desc and did not succeed,
        * retry as needed. (If a fetch is successful, the connection state
        * is changed to DIR_PURPOSE_HAS_FETCHED_RENDDESC to mark that
        * refetching is unnecessary.) */
       if (conn->purpose == DIR_PURPOSE_FETCH_RENDDESC_V2 &&
-          dir_conn->rend_query &&
-          strlen(dir_conn->rend_query) == REND_SERVICE_ID_LEN_BASE32)
-        rend_client_refetch_v2_renddesc(dir_conn->rend_query);
+          dir_conn->rend_data &&
+          strlen(dir_conn->rend_data->onion_address) ==
+              REND_SERVICE_ID_LEN_BASE32)
+        rend_client_refetch_v2_renddesc(dir_conn->rend_data);
       break;
     case CONN_TYPE_OR:
       or_conn = TO_OR_CONN(conn);
@@ -2565,6 +2570,7 @@ connection_get_by_type_state_rendquery(int type, int state,
 
   tor_assert(type == CONN_TYPE_DIR ||
              type == CONN_TYPE_AP || type == CONN_TYPE_EXIT);
+  tor_assert(rendquery);
 
   SMARTLIST_FOREACH(conns, connection_t *, conn,
   {
@@ -2572,12 +2578,16 @@ connection_get_by_type_state_rendquery(int type, int state,
         !conn->marked_for_close &&
         (!state || state == conn->state)) {
       if (type == CONN_TYPE_DIR &&
+          TO_DIR_CONN(conn)->rend_data &&
           (rendversion < 0 ||
-           rendversion == TO_DIR_CONN(conn)->rend_version) &&
-          !rend_cmp_service_ids(rendquery, TO_DIR_CONN(conn)->rend_query))
+           rendversion == TO_DIR_CONN(conn)->rend_data->rend_desc_version) &&
+          !rend_cmp_service_ids(rendquery,
+                                TO_DIR_CONN(conn)->rend_data->onion_address))
         return conn;
       else if (CONN_IS_EDGE(conn) &&
-              !rend_cmp_service_ids(rendquery, TO_EDGE_CONN(conn)->rend_query))
+               TO_EDGE_CONN(conn)->rend_data &&
+               !rend_cmp_service_ids(rendquery,
+                            TO_EDGE_CONN(conn)->rend_data->onion_address))
         return conn;
     }
   });
diff --git a/src/or/connection_edge.c b/src/or/connection_edge.c
index 6b4c691474..fe05aed521 100644
--- a/src/or/connection_edge.c
+++ b/src/or/connection_edge.c
@@ -1587,6 +1587,7 @@ connection_ap_handshake_rewrite_and_attach(edge_connection_t *conn,
     /* it's a hidden-service request */
     rend_cache_entry_t *entry;
     int r;
+    rend_service_authorization_t *client_auth;
     tor_assert(!automap);
     if (SOCKS_COMMAND_IS_RESOLVE(socks->command)) {
       /* if it's a resolve request, fail it right now, rather than
@@ -1608,14 +1609,16 @@ connection_ap_handshake_rewrite_and_attach(edge_connection_t *conn,
       return -1;
     }
 
-    strlcpy(conn->rend_query, socks->address, sizeof(conn->rend_query));
+    conn->rend_data = tor_malloc_zero(sizeof(rend_data_t));
+    strlcpy(conn->rend_data->onion_address, socks->address,
+            sizeof(conn->rend_data->onion_address));
     log_info(LD_REND,"Got a hidden service request for ID '%s'",
-             safe_str(conn->rend_query));
+             safe_str(conn->rend_data->onion_address));
     /* see if we already have it cached */
-    r = rend_cache_lookup_entry(conn->rend_query, -1, &entry);
+    r = rend_cache_lookup_entry(conn->rend_data->onion_address, -1, &entry);
     if (r<0) {
       log_warn(LD_BUG,"Invalid service name '%s'",
-               safe_str(conn->rend_query));
+               safe_str(conn->rend_data->onion_address));
       connection_mark_unattached_ap(conn, END_STREAM_REASON_TORPROTOCOL);
       return -1;
     }
@@ -1624,14 +1627,26 @@ connection_ap_handshake_rewrite_and_attach(edge_connection_t *conn,
      * a stable circuit yet, but we know we'll need *something*. */
     rep_hist_note_used_internal(now, 0, 1);
 
+    /* Look up if we have client authorization for it. */
+    client_auth = rend_client_lookup_service_authorization(
+                                          conn->rend_data->onion_address);
+    if (client_auth) {
+      log_info(LD_REND, "Using previously configured client authorization "
+                        "for hidden service request.");
+      memcpy(conn->rend_data->descriptor_cookie,
+             client_auth->descriptor_cookie, REND_DESC_COOKIE_LEN);
+      conn->rend_data->auth_type = client_auth->auth_type;
+    }
     if (r==0) {
       conn->_base.state = AP_CONN_STATE_RENDDESC_WAIT;
       log_info(LD_REND, "Unknown descriptor %s. Fetching.",
-               safe_str(conn->rend_query));
+               safe_str(conn->rend_data->onion_address));
       /* Fetch both, v0 and v2 rend descriptors in parallel. Use whichever
-       * arrives first. */
-      rend_client_refetch_v2_renddesc(conn->rend_query);
-      rend_client_refetch_renddesc(conn->rend_query);
+       * arrives first. Exception: When using client authorization, only
+       * fetch v2 descriptors.*/
+      rend_client_refetch_v2_renddesc(conn->rend_data);
+      if (conn->rend_data->auth_type == REND_NO_AUTH)
+        rend_client_refetch_renddesc(conn->rend_data->onion_address);
     } else { /* r > 0 */
 /** How long after we receive a hidden service descriptor do we consider
  * it valid? */
@@ -1647,11 +1662,13 @@ connection_ap_handshake_rewrite_and_attach(edge_connection_t *conn,
       } else {
         conn->_base.state = AP_CONN_STATE_RENDDESC_WAIT;
         log_info(LD_REND, "Stale descriptor %s. Refetching.",
-                 safe_str(conn->rend_query));
+                 safe_str(conn->rend_data->onion_address));
         /* Fetch both, v0 and v2 rend descriptors in parallel. Use whichever
-         * arrives first. */
-        rend_client_refetch_v2_renddesc(conn->rend_query);
-        rend_client_refetch_renddesc(conn->rend_query);
+         * arrives first. Exception: When using client authorization, only
+         * fetch v2 descriptors.*/
+        rend_client_refetch_v2_renddesc(conn->rend_data);
+        if (conn->rend_data->auth_type == REND_NO_AUTH)
+          rend_client_refetch_renddesc(conn->rend_data->onion_address);
       }
     }
     return 0;
@@ -2531,8 +2548,7 @@ connection_exit_begin_conn(cell_t *cell, circuit_t *circ)
     log_info(LD_REND,"begin is for rendezvous. configuring stream.");
     n_stream->_base.address = tor_strdup("(rendezvous)");
     n_stream->_base.state = EXIT_CONN_STATE_CONNECTING;
-    strlcpy(n_stream->rend_query, origin_circ->rend_query,
-            sizeof(n_stream->rend_query));
+    n_stream->rend_data = rend_data_dup(origin_circ->rend_data);
     tor_assert(connection_edge_is_rendezvous_stream(n_stream));
     assert_circuit_ok(circ);
     if (rend_service_set_connection_addr_port(n_stream, origin_circ) < 0) {
@@ -2815,7 +2831,7 @@ int
 connection_edge_is_rendezvous_stream(edge_connection_t *conn)
 {
   tor_assert(conn);
-  if (*conn->rend_query) /* XXX */ /* XXXX Why is this XXX? -NM */
+  if (conn->rend_data) /* XXX */ /* XXXX Why is this XXX? -NM */
     return 1;
   return 0;
 }
diff --git a/src/or/directory.c b/src/or/directory.c
index 2e00088c2b..8e4c6d4d3d 100644
--- a/src/or/directory.c
+++ b/src/or/directory.c
@@ -60,6 +60,22 @@ static void dir_routerdesc_download_failed(smartlist_t *failed,
 static void note_client_request(int purpose, int compressed, size_t bytes);
 static int client_likes_consensus(networkstatus_t *v, const char *want_url);
 
+static void directory_initiate_command_rend(const char *address,
+                                            const tor_addr_t *addr,
+                                            uint16_t or_port,
+                                            uint16_t dir_port,
+                                            int supports_conditional_consensus,
+                                            int supports_begindir,
+                                            const char *digest,
+                                            uint8_t dir_purpose,
+                                            uint8_t router_purpose,
+                                            int anonymized_connection,
+                                            const char *resource,
+                                            const char *payload,
+                                            size_t payload_len,
+                                            time_t if_modified_since,
+                                            const rend_data_t *rend_query);
+
 /********* START VARIABLES **********/
 
 /** How far in the future do we allow a directory server to tell us it is
@@ -434,29 +450,18 @@ directory_get_from_all_authorities(uint8_t dir_purpose,
     });
 }
 
-/** Launch a new connection to the directory server <b>status</b> to
- * upload or download a server or rendezvous
- * descriptor. <b>dir_purpose</b> determines what
- * kind of directory connection we're launching, and must be one of
- * DIR_PURPOSE_{FETCH|UPLOAD}_{DIR|RENDDESC|RENDDESC_V2}. <b>router_purpose</b>
- * specifies the descriptor purposes we have in mind (currently only
- * used for FETCH_DIR).
- *
- * When uploading, <b>payload</b> and <b>payload_len</b> determine the content
- * of the HTTP post.  Otherwise, <b>payload</b> should be NULL.
- *
- * When fetching a rendezvous descriptor, <b>resource</b> is the service ID we
- * want to fetch.
- */
+/** Same as directory_initiate_command_routerstatus(), but accepts
+ * rendezvous data to fetch a hidden service descriptor. */
 void
-directory_initiate_command_routerstatus(routerstatus_t *status,
-                                        uint8_t dir_purpose,
-                                        uint8_t router_purpose,
-                                        int anonymized_connection,
-                                        const char *resource,
-                                        const char *payload,
-                                        size_t payload_len,
-                                        time_t if_modified_since)
+directory_initiate_command_routerstatus_rend(routerstatus_t *status,
+                                             uint8_t dir_purpose,
+                                             uint8_t router_purpose,
+                                             int anonymized_connection,
+                                             const char *resource,
+                                             const char *payload,
+                                             size_t payload_len,
+                                             time_t if_modified_since,
+                                             const rend_data_t *rend_query)
 {
   routerinfo_t *router;
   char address_buf[INET_NTOA_BUF_LEN+1];
@@ -476,14 +481,46 @@ directory_initiate_command_routerstatus(routerstatus_t *status,
     address = address_buf;
   }
   tor_addr_from_ipv4h(&addr, status->addr);
-  directory_initiate_command(address, &addr,
+  directory_initiate_command_rend(address, &addr,
                              status->or_port, status->dir_port,
                              status->version_supports_conditional_consensus,
                              status->version_supports_begindir,
                              status->identity_digest,
                              dir_purpose, router_purpose,
                              anonymized_connection, resource,
-                             payload, payload_len, if_modified_since);
+                             payload, payload_len, if_modified_since,
+                             rend_query);
+}
+
+/** Launch a new connection to the directory server <b>status</b> to
+ * upload or download a server or rendezvous
+ * descriptor. <b>dir_purpose</b> determines what
+ * kind of directory connection we're launching, and must be one of
+ * DIR_PURPOSE_{FETCH|UPLOAD}_{DIR|RENDDESC|RENDDESC_V2}. <b>router_purpose</b>
+ * specifies the descriptor purposes we have in mind (currently only
+ * used for FETCH_DIR).
+ *
+ * When uploading, <b>payload</b> and <b>payload_len</b> determine the content
+ * of the HTTP post.  Otherwise, <b>payload</b> should be NULL.
+ *
+ * When fetching a rendezvous descriptor, <b>resource</b> is the service ID we
+ * want to fetch.
+ */
+void
+directory_initiate_command_routerstatus(routerstatus_t *status,
+                                        uint8_t dir_purpose,
+                                        uint8_t router_purpose,
+                                        int anonymized_connection,
+                                        const char *resource,
+                                        const char *payload,
+                                        size_t payload_len,
+                                        time_t if_modified_since)
+{
+  directory_initiate_command_routerstatus_rend(status, dir_purpose,
+                                          router_purpose,
+                                          anonymized_connection, resource,
+                                          payload, payload_len,
+                                          if_modified_since, NULL);
 }
 
 /** Return true iff <b>conn</b> is the client side of a directory connection
@@ -668,6 +705,28 @@ directory_initiate_command(const char *address, const tor_addr_t *_addr,
                            const char *payload, size_t payload_len,
                            time_t if_modified_since)
 {
+  directory_initiate_command_rend(address, _addr, or_port, dir_port,
+                             supports_conditional_consensus,
+                             supports_begindir, digest, dir_purpose,
+                             router_purpose, anonymized_connection,
+                             resource, payload, payload_len,
+                             if_modified_since, NULL);
+}
+
+/** Same as directory_initiate_command(), but accepts rendezvous data to
+ * fetch a hidden service descriptor. */
+static void
+directory_initiate_command_rend(const char *address, const tor_addr_t *_addr,
+                                uint16_t or_port, uint16_t dir_port,
+                                int supports_conditional_consensus,
+                                int supports_begindir, const char *digest,
+                                uint8_t dir_purpose, uint8_t router_purpose,
+                                int anonymized_connection,
+                                const char *resource,
+                                const char *payload, size_t payload_len,
+                                time_t if_modified_since,
+                                const rend_data_t *rend_query)
+{
   dir_connection_t *conn;
   or_options_t *options = get_options();
   int socket_error = 0;
@@ -705,6 +764,10 @@ directory_initiate_command(const char *address, const tor_addr_t *_addr,
   /* decide whether we can learn our IP address from this conn */
   conn->dirconn_direct = !anonymized_connection;
 
+  /* copy rendezvous data, if any */
+  if (rend_query)
+    conn->rend_data = rend_data_dup(rend_query);
+
   if (!anonymized_connection && !use_begindir) {
     /* then we want to connect to dirport directly */
 
@@ -1005,8 +1068,10 @@ directory_send_command(dir_connection_t *conn,
       /* this must be true or we wouldn't be doing the lookup */
       tor_assert(strlen(resource) <= REND_SERVICE_ID_LEN_BASE32);
       /* This breaks the function abstraction. */
-      strlcpy(conn->rend_query, resource, sizeof(conn->rend_query));
-      conn->rend_version = 0;
+      conn->rend_data = tor_malloc_zero(sizeof(rend_data_t));
+      strlcpy(conn->rend_data->onion_address, resource,
+              sizeof(conn->rend_data->onion_address));
+      conn->rend_data->rend_desc_version = 0;
 
       httpcommand = "GET";
       /* Request the most recent versioned descriptor. */
@@ -1019,10 +1084,8 @@ directory_send_command(dir_connection_t *conn,
     case DIR_PURPOSE_FETCH_RENDDESC_V2:
       tor_assert(resource);
       tor_assert(strlen(resource) <= REND_DESC_ID_V2_LEN_BASE32);
-      /* Remember the query to refer to it when a response arrives. */
-      strlcpy(conn->rend_query, payload, sizeof(conn->rend_query));
-      conn->rend_version = 2;
-      payload = NULL;
+      tor_assert(!payload);
+      conn->rend_data->rend_desc_version = 2;
       httpcommand = "GET";
       len = strlen(resource) + 32;
       url = tor_malloc(len);
@@ -1877,6 +1940,7 @@ connection_dir_client_reached_eof(dir_connection_t *conn)
   }
 
   if (conn->_base.purpose == DIR_PURPOSE_FETCH_RENDDESC) {
+    tor_assert(conn->rend_data);
     log_info(LD_REND,"Received rendezvous descriptor (size %d, status %d "
              "(%s))",
              (int)body_len, status_code, escaped(reason));
@@ -1892,7 +1956,7 @@ connection_dir_client_reached_eof(dir_connection_t *conn)
         } else {
           /* success. notify pending connections about this. */
           conn->_base.purpose = DIR_PURPOSE_HAS_FETCHED_RENDDESC;
-          rend_client_desc_trynow(conn->rend_query, -1);
+          rend_client_desc_trynow(conn->rend_data->onion_address, -1);
         }
         break;
       case 404:
@@ -1914,12 +1978,13 @@ connection_dir_client_reached_eof(dir_connection_t *conn)
   }
 
   if (conn->_base.purpose == DIR_PURPOSE_FETCH_RENDDESC_V2) {
+    tor_assert(conn->rend_data);
     log_info(LD_REND,"Received rendezvous descriptor (size %d, status %d "
              "(%s))",
              (int)body_len, status_code, escaped(reason));
     switch (status_code) {
       case 200:
-        switch (rend_cache_store_v2_desc_as_client(body, NULL)) {
+        switch (rend_cache_store_v2_desc_as_client(body, conn->rend_data)) {
           case -2:
             log_warn(LD_REND,"Fetching v2 rendezvous descriptor failed. "
                      "Retrying at another directory.");
@@ -1938,7 +2003,7 @@ connection_dir_client_reached_eof(dir_connection_t *conn)
             log_info(LD_REND, "Successfully fetched v2 rendezvous "
                      "descriptor.");
             conn->_base.purpose = DIR_PURPOSE_HAS_FETCHED_RENDDESC;
-            rend_client_desc_trynow(conn->rend_query, -1);
+            rend_client_desc_trynow(conn->rend_data->onion_address, -1);
             break;
         }
         break;
diff --git a/src/or/or.h b/src/or/or.h
index c14b08f4d6..e4fc7c2909 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -676,6 +676,55 @@ typedef enum {
 /** Maximum length of authorized client names for a hidden service. */
 #define REND_CLIENTNAME_MAX_LEN 16
 
+/** Length of the rendezvous cookie that is used to connect circuits at the
+ * rendezvous point. */
+#define REND_COOKIE_LEN DIGEST_LEN
+
+/** Client authorization type that a hidden service performs. */
+typedef enum rend_auth_type_t {
+  REND_NO_AUTH      = 0,
+  REND_BASIC_AUTH   = 1,
+  REND_STEALTH_AUTH = 2,
+} rend_auth_type_t;
+
+/** Client-side configuration of authorization for a hidden service. */
+typedef struct rend_service_authorization_t {
+  char descriptor_cookie[REND_DESC_COOKIE_LEN];
+  char onion_address[REND_SERVICE_ADDRESS_LEN+1];
+  rend_auth_type_t auth_type;
+} rend_service_authorization_t;
+
+/** Client- and server-side data that is used for hidden service connection
+ * establishment. Not all fields contain data depending on where this struct
+ * is used. */
+typedef struct rend_data_t {
+  /** Onion address (without the .onion part) that a client requests. */
+  char onion_address[REND_SERVICE_ID_LEN_BASE32+1];
+
+  /** (Optional) descriptor cookie that is used by a client. */
+  char descriptor_cookie[REND_DESC_COOKIE_LEN];
+
+  /** Authorization type for accessing a service used by a client. */
+  rend_auth_type_t auth_type;
+
+  /** Hash of the hidden service's PK used by a service. */
+  char rend_pk_digest[DIGEST_LEN];
+
+  /** Rendezvous cookie used by both, client and service. */
+  char rend_cookie[REND_COOKIE_LEN];
+
+  /** Rendezvous descriptor version that is used by a service. Used to
+   * distinguish introduction and rendezvous points belonging to the same
+   * rendezvous service ID, but different descriptor versions.
+   */
+  uint8_t rend_desc_version;
+} rend_data_t;
+
+/** Time interval for tracking possible replays of INTRODUCE2 cells.
+ * Incoming cells with timestamps half of this interval in the past or
+ * future are dropped immediately. */
+#define REND_REPLAY_TIME_INTERVAL (60 * 60)
+
 #define CELL_DIRECTION_IN 1
 #define CELL_DIRECTION_OUT 2
 
@@ -1025,7 +1074,7 @@ typedef struct edge_connection_t {
   uint32_t n_written;
 
   /** What rendezvous service are we querying for? (AP only) */
-  char rend_query[REND_SERVICE_ID_LEN_BASE32+1];
+  rend_data_t *rend_data;
 
   /** Number of times we've reassigned this application connection to
    * a new circuit. We keep track because the timeout is longer if we've
@@ -1078,11 +1127,8 @@ typedef struct dir_connection_t {
   /** The zlib object doing on-the-fly compression for spooled data. */
   tor_zlib_state_t *zlib_state;
 
-  /** What hidden service descriptor are we fetching, if any? */
-  int rend_version;
-
   /** What rendezvous service are we querying for? */
-  char rend_query[REND_SERVICE_ID_LEN_BASE32+1];
+  rend_data_t *rend_data;
 
   char identity_digest[DIGEST_LEN]; /**< Hash of the public RSA key for
                                      * the directory server's signing key. */
@@ -1747,7 +1793,6 @@ typedef struct crypt_path_t {
                                  CIPHER_KEY_LEN+\
                                  DH_KEY_LEN)
 #define ONIONSKIN_REPLY_LEN (DH_KEY_LEN+DIGEST_LEN)
-#define REND_COOKIE_LEN DIGEST_LEN
 
 /** Information used to build a circuit. */
 typedef struct {
@@ -1883,28 +1928,8 @@ typedef struct origin_circuit_t {
    */
   crypt_path_t *cpath;
 
-  /** The rend_pk_digest field holds a hash of location-hidden service's
-   * PK if purpose is S_ESTABLISH_INTRO or S_RENDEZVOUSING.
-   */
-  char rend_pk_digest[DIGEST_LEN];
-
-  /** Holds rendezvous cookie if purpose is C_ESTABLISH_REND. Filled with
-   * zeroes otherwise.
-   */
-  char rend_cookie[REND_COOKIE_LEN];
-
-  /**
-   * The rend_query field holds the y portion of y.onion (nul-terminated)
-   * if purpose is C_INTRODUCING or C_ESTABLISH_REND, or is a C_GENERAL
-   * for a hidden service, or is S_*.
-   */
-  char rend_query[REND_SERVICE_ID_LEN_BASE32+1];
-
-  /** Stores the rendezvous descriptor version if purpose is S_*. Used to
-   * distinguish introduction and rendezvous points belonging to the same
-   * rendezvous service ID, but different descriptor versions.
-   */
-  uint8_t rend_desc_version;
+  /** Holds all rendezvous data on either client or service side. */
+  rend_data_t *rend_data;
 
   /** How many more relay_early cells can we send on this circuit, according
    * to the specification? */
@@ -3179,6 +3204,15 @@ void directory_initiate_command_routerstatus(routerstatus_t *status,
                                              const char *payload,
                                              size_t payload_len,
                                              time_t if_modified_since);
+void directory_initiate_command_routerstatus_rend(routerstatus_t *status,
+                                                  uint8_t dir_purpose,
+                                                  uint8_t router_purpose,
+                                                  int anonymized_connection,
+                                                  const char *resource,
+                                                  const char *payload,
+                                                  size_t payload_len,
+                                                  time_t if_modified_since,
+                                                const rend_data_t *rend_query);
 
 int parse_http_response(const char *headers, int *code, time_t *date,
                         compress_method_t *compression, char **response);
@@ -3835,39 +3869,25 @@ void rend_client_rendcirc_has_opened(origin_circuit_t *circ);
 int rend_client_introduction_acked(origin_circuit_t *circ, const char *request,
                                    size_t request_len);
 void rend_client_refetch_renddesc(const char *query);
-void rend_client_refetch_v2_renddesc(const char *query);
+void rend_client_refetch_v2_renddesc(const rend_data_t *rend_query);
 int rend_client_remove_intro_point(extend_info_t *failed_intro,
-                                   const char *query);
+                                   const rend_data_t *rend_query);
 int rend_client_rendezvous_acked(origin_circuit_t *circ, const char *request,
                                  size_t request_len);
 int rend_client_receive_rendezvous(origin_circuit_t *circ, const char *request,
                                    size_t request_len);
 void rend_client_desc_trynow(const char *query, int rend_version);
 
-extend_info_t *rend_client_get_random_intro(const char *query);
+extend_info_t *rend_client_get_random_intro(const rend_data_t *rend_query);
 
 int rend_client_send_introduction(origin_circuit_t *introcirc,
                                   origin_circuit_t *rendcirc);
-
-/** Client authorization type that a hidden service performs. */
-typedef enum rend_auth_type_t {
-  REND_NO_AUTH      = 0,
-  REND_BASIC_AUTH   = 1,
-  REND_STEALTH_AUTH = 2,
-} rend_auth_type_t;
-
-/** Client-side configuration of authorization for a hidden service. */
-typedef struct rend_service_authorization_t {
-  char descriptor_cookie[REND_DESC_COOKIE_LEN];
-  char onion_address[REND_SERVICE_ADDRESS_LEN+1];
-  rend_auth_type_t auth_type;
-} rend_service_authorization_t;
-
 int rend_parse_service_authorization(or_options_t *options,
                                      int validate_only);
 rend_service_authorization_t *rend_client_lookup_service_authorization(
                                                 const char *onion_address);
 void rend_service_authorization_free_all(void);
+rend_data_t *rend_data_dup(const rend_data_t *request);
 
 /********************************* rendcommon.c ***************************/
 
@@ -3910,6 +3930,13 @@ typedef struct rend_service_descriptor_t {
   smartlist_t *successful_uploads;
 } rend_service_descriptor_t;
 
+/** Free all storage associated with <b>data</b> */
+static INLINE void
+rend_data_free(rend_data_t *data)
+{
+  tor_free(data);
+}
+
 int rend_cmp_service_ids(const char *one, const char *two);
 
 void rend_process_relay_cell(circuit_t *circ, int command, size_t length,
@@ -3947,7 +3974,7 @@ int rend_cache_lookup_entry(const char *query, int version,
 int rend_cache_lookup_v2_desc_as_dir(const char *query, const char **desc);
 int rend_cache_store(const char *desc, size_t desc_len, int published);
 int rend_cache_store_v2_desc_as_client(const char *desc,
-                               const char *descriptor_cookie);
+                                       const rend_data_t *rend_query);
 int rend_cache_store_v2_desc_as_dir(const char *desc);
 int rend_cache_size(void);
 int rend_encode_v2_descriptors(smartlist_t *descs_out,
diff --git a/src/or/rendclient.c b/src/or/rendclient.c
index 7623831d5e..d3c8523c4c 100644
--- a/src/or/rendclient.c
+++ b/src/or/rendclient.c
@@ -31,16 +31,18 @@ static int
 rend_client_send_establish_rendezvous(origin_circuit_t *circ)
 {
   tor_assert(circ->_base.purpose == CIRCUIT_PURPOSE_C_ESTABLISH_REND);
+  tor_assert(circ->rend_data);
   log_info(LD_REND, "Sending an ESTABLISH_RENDEZVOUS cell");
 
-  if (crypto_rand(circ->rend_cookie, REND_COOKIE_LEN) < 0) {
+  if (crypto_rand(circ->rend_data->rend_cookie, REND_COOKIE_LEN) < 0) {
     log_warn(LD_BUG, "Internal error: Couldn't produce random cookie.");
     circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_INTERNAL);
     return -1;
   }
   if (relay_send_command_from_edge(0, TO_CIRCUIT(circ),
                                    RELAY_COMMAND_ESTABLISH_RENDEZVOUS,
-                                   circ->rend_cookie, REND_COOKIE_LEN,
+                                   circ->rend_data->rend_cookie,
+                                   REND_COOKIE_LEN,
                                    circ->cpath->prev)<0) {
     /* circ is already marked for close */
     log_warn(LD_GENERAL, "Couldn't send ESTABLISH_RENDEZVOUS cell");
@@ -58,7 +60,7 @@ rend_client_send_introduction(origin_circuit_t *introcirc,
                               origin_circuit_t *rendcirc)
 {
   size_t payload_len;
-  int r;
+  int r, v3_shift = 0;
   char payload[RELAY_PAYLOAD_SIZE];
   char tmp[RELAY_PAYLOAD_SIZE];
   rend_cache_entry_t *entry;
@@ -68,13 +70,16 @@ rend_client_send_introduction(origin_circuit_t *introcirc,
 
   tor_assert(introcirc->_base.purpose == CIRCUIT_PURPOSE_C_INTRODUCING);
   tor_assert(rendcirc->_base.purpose == CIRCUIT_PURPOSE_C_REND_READY);
-  tor_assert(!rend_cmp_service_ids(introcirc->rend_query,
-                                   rendcirc->rend_query));
+  tor_assert(introcirc->rend_data);
+  tor_assert(rendcirc->rend_data);
+  tor_assert(!rend_cmp_service_ids(introcirc->rend_data->onion_address,
+                                   rendcirc->rend_data->onion_address));
 
-  if (rend_cache_lookup_entry(introcirc->rend_query, -1, &entry) < 1) {
+  if (rend_cache_lookup_entry(introcirc->rend_data->onion_address, -1,
+                              &entry) < 1) {
     log_warn(LD_REND,
              "query %s didn't have valid rend desc in cache. Failing.",
-             escaped_safe_str(introcirc->rend_query));
+             escaped_safe_str(introcirc->rend_data->onion_address));
     goto err;
   }
 
@@ -117,27 +122,45 @@ rend_client_send_introduction(origin_circuit_t *introcirc,
     }
   }
 
+  /* If version is 3, write (optional) auth data and timestamp. */
+  if (entry->parsed->protocols & (1<<3)) {
+    tmp[0] = 3; /* version 3 of the cell format */
+    tmp[1] = (uint8_t)introcirc->rend_data->auth_type; /* auth type, if any */
+    v3_shift = 1;
+    if (introcirc->rend_data->auth_type != REND_NO_AUTH) {
+      set_uint16(tmp+2, htons(REND_DESC_COOKIE_LEN));
+      memcpy(tmp+4, introcirc->rend_data->descriptor_cookie,
+             REND_DESC_COOKIE_LEN);
+      v3_shift += 2+REND_DESC_COOKIE_LEN;
+    }
+    set_uint32(tmp+v3_shift+1, htonl(time(NULL)));
+    v3_shift += 4;
+  } /* if version 2 only write version number */
+  else if (entry->parsed->protocols & (1<<2)) {
+    tmp[0] = 2; /* version 2 of the cell format */
+  }
+
   /* write the remaining items into tmp */
-  if (entry->parsed->protocols & (1<<2)) {
+  if (entry->parsed->protocols & (1<<3) || entry->parsed->protocols & (1<<2)) {
     /* version 2 format */
     extend_info_t *extend_info = rendcirc->build_state->chosen_exit;
     int klen;
-    tmp[0] = 2; /* version 2 of the cell format */
     /* nul pads */
-    set_uint32(tmp+1, tor_addr_to_ipv4h(&extend_info->addr));
-    set_uint16(tmp+5, htons(extend_info->port));
-    memcpy(tmp+7, extend_info->identity_digest, DIGEST_LEN);
-    klen = crypto_pk_asn1_encode(extend_info->onion_key, tmp+7+DIGEST_LEN+2,
-                                 sizeof(tmp)-(7+DIGEST_LEN+2));
-    set_uint16(tmp+7+DIGEST_LEN, htons(klen));
-    memcpy(tmp+7+DIGEST_LEN+2+klen, rendcirc->rend_cookie,
+    set_uint32(tmp+v3_shift+1, tor_addr_to_ipv4h(&extend_info->addr));
+    set_uint16(tmp+v3_shift+5, htons(extend_info->port));
+    memcpy(tmp+v3_shift+7, extend_info->identity_digest, DIGEST_LEN);
+    klen = crypto_pk_asn1_encode(extend_info->onion_key,
+                                 tmp+v3_shift+7+DIGEST_LEN+2,
+                                 sizeof(tmp)-(v3_shift+7+DIGEST_LEN+2));
+    set_uint16(tmp+v3_shift+7+DIGEST_LEN, htons(klen));
+    memcpy(tmp+v3_shift+7+DIGEST_LEN+2+klen, rendcirc->rend_data->rend_cookie,
            REND_COOKIE_LEN);
-    dh_offset = 7+DIGEST_LEN+2+klen+REND_COOKIE_LEN;
+    dh_offset = v3_shift+7+DIGEST_LEN+2+klen+REND_COOKIE_LEN;
   } else {
     /* Version 0. */
     strncpy(tmp, rendcirc->build_state->chosen_exit->nickname,
             (MAX_NICKNAME_LEN+1)); /* nul pads */
-    memcpy(tmp+MAX_NICKNAME_LEN+1, rendcirc->rend_cookie,
+    memcpy(tmp+MAX_NICKNAME_LEN+1, rendcirc->rend_data->rend_cookie,
            REND_COOKIE_LEN);
     dh_offset = MAX_NICKNAME_LEN+1+REND_COOKIE_LEN;
   }
@@ -216,6 +239,7 @@ rend_client_introduction_acked(origin_circuit_t *circ,
   }
 
   tor_assert(circ->build_state->chosen_exit);
+  tor_assert(circ->rend_data);
 
   if (request_len == 0) {
     /* It's an ACK; the introduction point relayed our introduction request. */
@@ -224,7 +248,7 @@ rend_client_introduction_acked(origin_circuit_t *circ,
      */
     log_info(LD_REND,"Received ack. Telling rend circ...");
     rendcirc = circuit_get_by_rend_query_and_purpose(
-               circ->rend_query, CIRCUIT_PURPOSE_C_REND_READY);
+               circ->rend_data->onion_address, CIRCUIT_PURPOSE_C_REND_READY);
     if (rendcirc) { /* remember the ack */
       rendcirc->_base.purpose = CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED;
     } else {
@@ -241,22 +265,22 @@ rend_client_introduction_acked(origin_circuit_t *circ,
      * If none remain, refetch the service descriptor.
      */
     if (rend_client_remove_intro_point(circ->build_state->chosen_exit,
-                                       circ->rend_query) > 0) {
+                                       circ->rend_data) > 0) {
       /* There are introduction points left. Re-extend the circuit to
        * another intro point and try again. */
       extend_info_t *extend_info;
       int result;
-      extend_info = rend_client_get_random_intro(circ->rend_query);
+      extend_info = rend_client_get_random_intro(circ->rend_data);
       if (!extend_info) {
         log_warn(LD_REND, "No introduction points left for %s. Closing.",
-                 escaped_safe_str(circ->rend_query));
+                 escaped_safe_str(circ->rend_data->onion_address));
         circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_INTERNAL);
         return -1;
       }
       log_info(LD_REND,
                "Got nack for %s from %s. Re-extending circ %d, "
                "this time to %s.",
-               escaped_safe_str(circ->rend_query),
+               escaped_safe_str(circ->rend_data->onion_address),
                circ->build_state->chosen_exit->nickname, circ->_base.n_circ_id,
                extend_info->nickname);
       result = circuit_extend_to_new_exit(circ, extend_info);
@@ -337,15 +361,15 @@ directory_clean_last_hid_serv_requests(void)
  * descriptor, return 0, and in case of a failure -1. <b>query</b> is only
  * passed for pretty log statements. */
 static int
-directory_get_from_hs_dir(const char *desc_id, const char *query)
+directory_get_from_hs_dir(const char *desc_id, const rend_data_t *rend_query)
 {
   smartlist_t *responsible_dirs = smartlist_create();
   routerstatus_t *hs_dir;
   char desc_id_base32[REND_DESC_ID_V2_LEN_BASE32 + 1];
   time_t now = time(NULL);
+  char descriptor_cookie_base64[3*REND_DESC_COOKIE_LEN_BASE64];
   tor_assert(desc_id);
-  tor_assert(query);
-  tor_assert(strlen(query) == REND_SERVICE_ID_LEN_BASE32);
+  tor_assert(rend_query);
   /* Determine responsible dirs. Even if we can't get all we want,
    * work with the ones we have. If it's empty, we'll notice below. */
   (int) hid_serv_get_responsible_directories(responsible_dirs, desc_id);
@@ -377,17 +401,33 @@ directory_get_from_hs_dir(const char *desc_id, const char *query)
    * directory now. */
   lookup_last_hid_serv_request(hs_dir, desc_id_base32, now, 1);
 
-  /* Send fetch request. (Pass query as payload to write it to the directory
-   * connection so that it can be referred to when the response arrives.) */
-  directory_initiate_command_routerstatus(hs_dir,
+  /* Encode descriptor cookie for logging purposes. */
+  if (rend_query->auth_type != REND_NO_AUTH &&
+      base64_encode(descriptor_cookie_base64, 3*REND_DESC_COOKIE_LEN_BASE64,
+                    rend_query->descriptor_cookie, REND_DESC_COOKIE_LEN) < 0) {
+    log_warn(LD_BUG, "Could not base64-encode descriptor cookie.");
+    return 0;
+  }
+  /* Remove == signs and newline. */
+  descriptor_cookie_base64[strlen(descriptor_cookie_base64)-3] = '\0';
+
+  /* Send fetch request. (Pass query and possibly descriptor cookie so that
+   * they can be written to the directory connection and be referred to when
+   * the response arrives. */
+  directory_initiate_command_routerstatus_rend(hs_dir,
                                           DIR_PURPOSE_FETCH_RENDDESC_V2,
                                           ROUTER_PURPOSE_GENERAL,
-                                          1, desc_id_base32, query, 0, 0);
+                                          1, desc_id_base32, NULL, 0, 0,
+                                          rend_query);
   log_info(LD_REND, "Sending fetch request for v2 descriptor for "
-                    "service '%s' with descriptor ID '%s' to hidden "
-                    "service directory '%s' on port %d.",
-           safe_str(query), safe_str(desc_id_base32), hs_dir->nickname,
-           hs_dir->dir_port);
+                    "service '%s' with descriptor ID '%s', auth type %d, "
+                    "and descriptor cookie '%s' to hidden service "
+                    "directory '%s' on port %d.",
+           rend_query->onion_address, desc_id_base32,
+           rend_query->auth_type,
+           (rend_query->auth_type == REND_NO_AUTH ? "NULL" :
+           escaped_safe_str(descriptor_cookie_base64)),
+           hs_dir->nickname, hs_dir->dir_port);
   return 1;
 }
 
@@ -417,14 +457,13 @@ rend_client_refetch_renddesc(const char *query)
  * <b>query</b>.
  */
 void
-rend_client_refetch_v2_renddesc(const char *query)
+rend_client_refetch_v2_renddesc(const rend_data_t *rend_query)
 {
   char descriptor_id[DIGEST_LEN];
   int replicas_left_to_try[REND_NUMBER_OF_NON_CONSECUTIVE_REPLICAS];
   int i, tries_left;
   rend_cache_entry_t *e = NULL;
-  tor_assert(query);
-  tor_assert(strlen(query) == REND_SERVICE_ID_LEN_BASE32);
+  tor_assert(rend_query);
   /* Are we configured to fetch descriptors? */
   if (!get_options()->FetchHidServDescriptors) {
     log_warn(LD_REND, "We received an onion address for a v2 rendezvous "
@@ -432,13 +471,13 @@ rend_client_refetch_v2_renddesc(const char *query)
     return;
   }
   /* Before fetching, check if we already have the descriptor here. */
-  if (rend_cache_lookup_entry(query, -1, &e) > 0) {
+  if (rend_cache_lookup_entry(rend_query->onion_address, -1, &e) > 0) {
     log_info(LD_REND, "We would fetch a v2 rendezvous descriptor, but we "
                       "already have that descriptor here. Not fetching.");
     return;
   }
   log_debug(LD_REND, "Fetching v2 rendezvous descriptor for service %s",
-            safe_str(query));
+            safe_str(rend_query->onion_address));
   /* Randomly iterate over the replicas until a descriptor can be fetched
    * from one of the consecutive nodes, or no options are left. */
   tries_left = REND_NUMBER_OF_NON_CONSECUTIVE_REPLICAS;
@@ -449,13 +488,15 @@ rend_client_refetch_v2_renddesc(const char *query)
     int chosen_replica = replicas_left_to_try[rand];
     replicas_left_to_try[rand] = replicas_left_to_try[--tries_left];
 
-    if (rend_compute_v2_desc_id(descriptor_id, query, NULL, time(NULL),
-                                chosen_replica) < 0) {
+    if (rend_compute_v2_desc_id(descriptor_id, rend_query->onion_address,
+                                rend_query->auth_type == REND_STEALTH_AUTH ?
+                                    rend_query->descriptor_cookie : NULL,
+                                time(NULL), chosen_replica) < 0) {
       log_warn(LD_REND, "Internal error: Computing v2 rendezvous "
                         "descriptor ID did not succeed.");
       return;
     }
-    if (directory_get_from_hs_dir(descriptor_id, query) != 0)
+    if (directory_get_from_hs_dir(descriptor_id, rend_query) != 0)
       return; /* either success or failure, but we're done */
   }
   /* If we come here, there are no hidden service directories left. */
@@ -463,7 +504,7 @@ rend_client_refetch_v2_renddesc(const char *query)
                     "service directories to fetch descriptors, because "
                     "we already tried them all unsuccessfully.");
   /* Close pending connections (unless a v0 request is still going on). */
-  rend_client_desc_trynow(query, 2);
+  rend_client_desc_trynow(rend_query->onion_address, 2);
   return;
 }
 
@@ -474,24 +515,28 @@ rend_client_refetch_v2_renddesc(const char *query)
  * unrecognized, 1 if recognized and some intro points remain.
  */
 int
-rend_client_remove_intro_point(extend_info_t *failed_intro, const char *query)
+rend_client_remove_intro_point(extend_info_t *failed_intro,
+                               const rend_data_t *rend_query)
 {
   int i, r;
   rend_cache_entry_t *ent;
   connection_t *conn;
 
-  r = rend_cache_lookup_entry(query, -1, &ent);
+  r = rend_cache_lookup_entry(rend_query->onion_address, -1, &ent);
   if (r<0) {
-    log_warn(LD_BUG, "Malformed service ID %s.", escaped_safe_str(query));
+    log_warn(LD_BUG, "Malformed service ID %s.",
+             escaped_safe_str(rend_query->onion_address));
     return -1;
   }
   if (r==0) {
     log_info(LD_REND, "Unknown service %s. Re-fetching descriptor.",
-             escaped_safe_str(query));
+             escaped_safe_str(rend_query->onion_address));
     /* Fetch both, v0 and v2 rend descriptors in parallel. Use whichever
-     * arrives first. */
-    rend_client_refetch_v2_renddesc(query);
-    rend_client_refetch_renddesc(query);
+     * arrives first. Exception: When using client authorization, only
+     * fetch v2 descriptors.*/
+    rend_client_refetch_v2_renddesc(rend_query);
+    if (rend_query->auth_type == REND_NO_AUTH)
+      rend_client_refetch_renddesc(rend_query->onion_address);
     return 0;
   }
 
@@ -508,22 +553,26 @@ rend_client_remove_intro_point(extend_info_t *failed_intro, const char *query)
   if (smartlist_len(ent->parsed->intro_nodes) == 0) {
     log_info(LD_REND,
              "No more intro points remain for %s. Re-fetching descriptor.",
-             escaped_safe_str(query));
+             escaped_safe_str(rend_query->onion_address));
     /* Fetch both, v0 and v2 rend descriptors in parallel. Use whichever
-     * arrives first. */
-    rend_client_refetch_v2_renddesc(query);
-    rend_client_refetch_renddesc(query);
+     * arrives first. Exception: When using client authorization, only
+     * fetch v2 descriptors.*/
+    rend_client_refetch_v2_renddesc(rend_query);
+    if (rend_query->auth_type == REND_NO_AUTH)
+      rend_client_refetch_renddesc(rend_query->onion_address);
 
     /* move all pending streams back to renddesc_wait */
     while ((conn = connection_get_by_type_state_rendquery(CONN_TYPE_AP,
-                                   AP_CONN_STATE_CIRCUIT_WAIT, query, -1))) {
+                                   AP_CONN_STATE_CIRCUIT_WAIT,
+                                   rend_query->onion_address, -1))) {
       conn->state = AP_CONN_STATE_RENDDESC_WAIT;
     }
 
     return 0;
   }
   log_info(LD_REND,"%d options left for %s.",
-           smartlist_len(ent->parsed->intro_nodes), escaped_safe_str(query));
+           smartlist_len(ent->parsed->intro_nodes),
+           escaped_safe_str(rend_query->onion_address));
   return 1;
 }
 
@@ -648,10 +697,13 @@ rend_client_desc_trynow(const char *query, int rend_version)
         _conn->marked_for_close)
       continue;
     conn = TO_EDGE_CONN(_conn);
-    if (rend_cmp_service_ids(query, conn->rend_query))
+    if (!conn->rend_data)
+      continue;
+    if (rend_cmp_service_ids(query, conn->rend_data->onion_address))
       continue;
     assert_connection_ok(TO_CONN(conn), now);
-    if (rend_cache_lookup_entry(conn->rend_query, -1, &entry) == 1 &&
+    if (rend_cache_lookup_entry(conn->rend_data->onion_address, -1,
+                                &entry) == 1 &&
         smartlist_len(entry->parsed->intro_nodes) > 0) {
       /* either this fetch worked, or it failed but there was a
        * valid entry from before which we should reuse */
@@ -689,17 +741,17 @@ rend_client_desc_trynow(const char *query, int rend_version)
  * have been tried and failed.
  */
 extend_info_t *
-rend_client_get_random_intro(const char *query)
+rend_client_get_random_intro(const rend_data_t *rend_query)
 {
   int i;
   rend_cache_entry_t *entry;
   rend_intro_point_t *intro;
   routerinfo_t *router;
 
-  if (rend_cache_lookup_entry(query, -1, &entry) < 1) {
+  if (rend_cache_lookup_entry(rend_query->onion_address, -1, &entry) < 1) {
     log_warn(LD_REND,
              "Query '%s' didn't have valid rend desc in cache. Failing.",
-             safe_str(query));
+             safe_str(rend_query->onion_address));
     return NULL;
   }
 
diff --git a/src/or/rendcommon.c b/src/or/rendcommon.c
index 49a21f63ae..343c43d7d6 100644
--- a/src/or/rendcommon.c
+++ b/src/or/rendcommon.c
@@ -1243,7 +1243,7 @@ rend_cache_store_v2_desc_as_dir(const char *desc)
  */
 int
 rend_cache_store_v2_desc_as_client(const char *desc,
-                                   const char *descriptor_cookie)
+                                   const rend_data_t *rend_query)
 {
   /*XXXX this seems to have a bit of duplicate code with
    * rend_cache_store_v2_desc_as_dir().  Fix that. */
@@ -1272,7 +1272,6 @@ rend_cache_store_v2_desc_as_client(const char *desc,
   rend_cache_entry_t *e;
   tor_assert(rend_cache);
   tor_assert(desc);
-  (void) descriptor_cookie; /* We don't use it, yet. */
   /* Parse the descriptor. */
   if (rend_parse_v2_service_descriptor(&parsed, desc_id, &intro_content,
                                        &intro_size, &encoded_size,
@@ -1291,14 +1290,37 @@ rend_cache_store_v2_desc_as_client(const char *desc,
   }
   /* Decode/decrypt introduction points. */
   if (intro_content) {
+    if (rend_query->auth_type != REND_NO_AUTH &&
+        rend_query->descriptor_cookie) {
+      char *ipos_decrypted;
+      size_t ipos_decrypted_size;
+      if (rend_decrypt_introduction_points(&ipos_decrypted,
+                                           &ipos_decrypted_size,
+                                           rend_query->descriptor_cookie,
+                                           intro_content,
+                                           intro_size) < 0) {
+        log_warn(LD_REND, "Failed to decrypt introduction points. We are "
+                 "probably unable to parse the encoded introduction points.");
+      } else {
+        /* Replace encrypted with decrypted introduction points. */
+        log_info(LD_REND, "Successfully decrypted introduction points.");
+        tor_free(intro_content);
+        intro_content = ipos_decrypted;
+        intro_size = ipos_decrypted_size;
+      }
+    }
     if (rend_parse_introduction_points(parsed, intro_content,
-                                       intro_size) < 0) {
-      log_warn(LD_PROTOCOL,"Couldn't decode/decrypt introduction points.");
-      rend_service_descriptor_free(parsed);
+                                       intro_size) <= 0) {
+      log_warn(LD_REND, "Failed to parse introduction points. Either the "
+               "service has published a corrupt descriptor or you have "
+               "provided invalid authorization data.");
+      if (parsed)
+        rend_service_descriptor_free(parsed);
       tor_free(intro_content);
       return -2;
     }
   } else {
+    log_info(LD_REND, "Descriptor does not contain any introduction points.");
     parsed->intro_nodes = smartlist_create();
   }
   /* We don't need the encoded/encrypted introduction points any longer. */
@@ -1426,3 +1448,12 @@ rend_cache_size(void)
   return strmap_size(rend_cache);
 }
 
+/** Allocate and return a new rend_data_t with the same
+ * contents as <b>query</b>. */
+rend_data_t *
+rend_data_dup(const rend_data_t *data)
+{
+  tor_assert(data);
+  return tor_memdup(data, sizeof(rend_data_t));
+}
+
diff --git a/src/or/rendservice.c b/src/or/rendservice.c
index 8f224e81de..878fe0227d 100644
--- a/src/or/rendservice.c
+++ b/src/or/rendservice.c
@@ -69,6 +69,11 @@ 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; used to prevent replays. */
+  digestmap_t *accepted_intros;
+  /** Time at which we last removed expired values from accepted_intros. */
+  time_t last_cleaned_accepted_intros;
 } rend_service_t;
 
 /** A list of rend_service_t's for services run on this OP.
@@ -125,6 +130,8 @@ rend_service_free(rend_service_t *service)
       rend_authorized_client_free(c););
     smartlist_free(service->clients);
   }
+  if (service->accepted_intros)
+    digestmap_free(service->accepted_intros, _tor_free);
   tor_free(service);
 }
 
@@ -360,7 +367,7 @@ rend_config_services(or_options_t *options, int validate_only)
       if (smartlist_len(type_names_split) < 2) {
         log_warn(LD_CONFIG, "HiddenServiceAuthorizeClient contains "
                             "auth-type '%s', but no client names.",
-                 service->auth_type == 1 ? "basic" : "stealth");
+                 service->auth_type == REND_BASIC_AUTH ? "basic" : "stealth");
         SMARTLIST_FOREACH(type_names_split, char *, cp, tor_free(cp));
         smartlist_free(type_names_split);
         continue;
@@ -423,7 +430,7 @@ rend_config_services(or_options_t *options, int validate_only)
                             "authorization type '%s'.",
                  smartlist_len(service->clients),
                  service->auth_type == REND_BASIC_AUTH ? 512 : 16,
-                 service->auth_type == 1 ? "basic" : "stealth");
+                 service->auth_type == REND_BASIC_AUTH ? "basic" : "stealth");
         rend_service_free(service);
         return -1;
       }
@@ -720,8 +727,10 @@ rend_service_load_keys(void)
       tor_free(client_keys_str);
       strmap_free(parsed_clients, rend_authorized_client_strmap_item_free);
       if (r<0) {
-        abort_writing_to_file(open_cfile);
-        abort_writing_to_file(open_hfile);
+        if (open_cfile)
+          abort_writing_to_file(open_cfile);
+        if (open_hfile)
+          abort_writing_to_file(open_hfile);
         return r;
       } else {
         finish_writing_to_file(open_cfile);
@@ -764,6 +773,64 @@ rend_service_requires_uptime(rend_service_t *service)
   return 0;
 }
 
+/** Check client authorization of a given <b>descriptor_cookie</b> for
+ * <b>service</b>. Return 1 for success and 0 for failure. */
+static int
+rend_check_authorization(rend_service_t *service,
+                         const char *descriptor_cookie)
+{
+  rend_authorized_client_t *auth_client = NULL;
+  tor_assert(service);
+  tor_assert(descriptor_cookie);
+  if (!service->clients) {
+    log_warn(LD_BUG, "Can't check authorization for a service that has no "
+                     "authorized clients configured.");
+    return 0;
+  }
+
+  /* Look up client authorization by descriptor cookie. */
+  SMARTLIST_FOREACH(service->clients, rend_authorized_client_t *, client, {
+    if (!memcmp(client->descriptor_cookie, descriptor_cookie,
+                REND_DESC_COOKIE_LEN)) {
+      auth_client = client;
+      break;
+    }
+  });
+  if (!auth_client) {
+    char descriptor_cookie_base64[3*REND_DESC_COOKIE_LEN_BASE64];
+    base64_encode(descriptor_cookie_base64, sizeof(descriptor_cookie_base64),
+                  descriptor_cookie, REND_DESC_COOKIE_LEN);
+    log_info(LD_REND, "No authorization found for descriptor cookie '%s'! "
+                      "Dropping cell!",
+             descriptor_cookie_base64);
+    return 0;
+  }
+
+  /* Allow the request. */
+  log_debug(LD_REND, "Client %s authorized for service %s.",
+            auth_client->client_name, service->service_id);
+  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_intros(rend_service_t *service, time_t now)
+{
+  const time_t cutoff = now - REND_REPLAY_TIME_INTERVAL;
+
+  service->last_cleaned_accepted_intros = now;
+  if (!service->accepted_intros)
+    return;
+
+  DIGESTMAP_FOREACH_MODIFY(service->accepted_intros, digest, time_t *, t) {
+    if (*t < cutoff) {
+      tor_free(t);
+      MAP_DEL_CURRENT(digest);
+    }
+  } DIGESTMAP_FOREACH_END;
+}
+
 /******
  * Handle cells
  ******/
@@ -780,7 +847,7 @@ rend_service_introduce(origin_circuit_t *circuit, const char *request,
   char buf[RELAY_PAYLOAD_SIZE];
   char keys[DIGEST_LEN+CPATH_KEY_MATERIAL_LEN]; /* Holds KH, Df, Db, Kf, Kb */
   rend_service_t *service;
-  int r, i;
+  int r, i, v3_shift = 0;
   size_t len, keylen;
   crypto_dh_env_t *dh = NULL;
   origin_circuit_t *launched = NULL;
@@ -791,9 +858,17 @@ rend_service_introduce(origin_circuit_t *circuit, const char *request,
   int reason = END_CIRC_REASON_TORPROTOCOL;
   crypto_pk_env_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_env_t *digest = NULL;
+  time_t now = time(NULL);
+  char diffie_hellman_hash[DIGEST_LEN];
+  time_t *access_time;
+  tor_assert(circuit->rend_data);
 
   base32_encode(serviceid, REND_SERVICE_ID_LEN_BASE32+1,
-                circuit->rend_pk_digest, REND_SERVICE_ID_LEN);
+                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);
 
@@ -814,7 +889,8 @@ rend_service_introduce(origin_circuit_t *circuit, const char *request,
 
   /* look up service depending on circuit. */
   service = rend_service_get_by_pk_digest_and_version(
-              circuit->rend_pk_digest, circuit->rend_desc_version);
+              circuit->rend_data->rend_pk_digest,
+              circuit->rend_data->rend_desc_version);
   if (!service) {
     log_warn(LD_REND, "Got an INTRODUCE2 cell for an unrecognized service %s.",
              escaped(serviceid));
@@ -822,7 +898,7 @@ rend_service_introduce(origin_circuit_t *circuit, const char *request,
   }
 
   /* if descriptor version is 2, use intro key instead of service key. */
-  if (circuit->rend_desc_version == 0) {
+  if (circuit->rend_data->rend_desc_version == 0) {
     intro_key = service->private_key;
   } else {
     intro_key = circuit->intro_key;
@@ -854,33 +930,70 @@ rend_service_introduce(origin_circuit_t *circuit, const char *request,
     return -1;
   }
   len = r;
-  if (*buf == 2) {
+  if (*buf == 3) {
+    /* Version 3 INTRODUCE2 cell. */
+    time_t ts = 0, now = time(NULL);
+    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);
+          return -1;
+        }
+        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);
+    }
+
+    /* Check timestamp. */
+    memcpy((char*)&ts, buf+1+v3_shift, sizeof(uint32_t));
+    v3_shift += 4;
+    ts = ntohl(ts);
+    if ((now - ts) < -1 * REND_REPLAY_TIME_INTERVAL / 2 ||
+        (now - ts) > REND_REPLAY_TIME_INTERVAL / 2) {
+      log_warn(LD_REND, "INTRODUCE2 cell is too %s. Discarding.",
+          (now - ts) < 0 ? "old" : "new");
+      return -1;
+    }
+  }
+  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+1));
-    extend_info->port = ntohs(get_uint16(buf+5));
-    memcpy(extend_info->identity_digest, buf+7, DIGEST_LEN);
+    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+7+DIGEST_LEN));
-    if ((int)len != 7+DIGEST_LEN+2+klen+20+128) {
-      log_warn(LD_PROTOCOL, "Bad length %u for version 2 INTRODUCE2 cell.",
-               (int)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+7+DIGEST_LEN+2, klen);
+    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 2 INTRODUCE2 cell.");
+      log_warn(LD_PROTOCOL, "Error decoding onion key in version %d "
+                            "INTRODUCE2 cell.", *buf);
       reason = END_CIRC_REASON_TORPROTOCOL;
       goto err;
     }
-    ptr = buf+7+DIGEST_LEN+2+klen;
-    len -= 7+DIGEST_LEN+2+klen;
+    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;
@@ -932,6 +1045,54 @@ rend_service_introduce(origin_circuit_t *circuit, const char *request,
   r_cookie = ptr;
   base16_encode(hexcookie,9,r_cookie,4);
 
+  /* Determine hash of Diffie-Hellman, part 1 to detect replays. */
+  digest = crypto_new_digest_env();
+  crypto_digest_add_bytes(digest, ptr+REND_COOKIE_LEN, DH_KEY_LEN);
+  crypto_digest_get_digest(digest, diffie_hellman_hash, DIGEST_LEN);
+  crypto_free_digest_env(digest);
+
+  /* Iterate over past requests, remove those which are older than one hour,
+   * and check whether there is one with same Diffie-Hellman, part 1. */
+  if (!service->accepted_intros)
+    service->accepted_intros = digestmap_new();
+
+  access_time = digestmap_get(service->accepted_intros, diffie_hellman_hash);
+  if (access_time != NULL) {
+    log_warn(LD_REND, "Possible replay detected! We received an "
+             "INTRODUCE2 cell with same first part of "
+             "Diffie-Hellman handshake %d seconds ago. Dropping "
+             "cell.",
+             (int) (now - *access_time));
+    goto err;
+  }
+
+  /* Add request to access history, including time and hash of
+   * Diffie-Hellman, part 1. */
+  access_time = tor_malloc(sizeof(time_t));
+  *access_time = now;
+  digestmap_set(service->accepted_intros, diffie_hellman_hash, access_time);
+  if (service->last_cleaned_accepted_intros + REND_REPLAY_TIME_INTERVAL < now)
+    clean_accepted_intros(service, now);
+
+  /* If the service performs client authorization, check included auth data. */
+  if (service->clients) {
+    if (auth_len > 0) {
+      if (rend_check_authorization(service, auth_data)) {
+        log_info(LD_REND, "Authorization data in INTRODUCE2 cell are valid.");
+      } else {
+        log_info(LD_REND, "The authorization data that are contained in "
+                 "the INTRODUCE2 cell are invalid. Dropping cell.");
+        reason = END_CIRC_REASON_CONNECTFAILED;
+        goto err;
+      }
+    } else {
+      log_info(LD_REND, "INTRODUCE2 cell does not contain authentication "
+               "data, but we require client authorization. Dropping cell.");
+      reason = END_CIRC_REASON_CONNECTFAILED;
+      goto err;
+    }
+  }
+
   /* Try DH handshake... */
   dh = crypto_dh_new();
   if (!dh || crypto_dh_generate_public(dh)<0) {
@@ -976,12 +1137,14 @@ rend_service_introduce(origin_circuit_t *circuit, const char *request,
            escaped_safe_str(extend_info->nickname), hexcookie, serviceid);
   tor_assert(launched->build_state);
   /* Fill in the circuit's state. */
-  memcpy(launched->rend_pk_digest, circuit->rend_pk_digest,
+  launched->rend_data = tor_malloc_zero(sizeof(rend_data_t));
+  memcpy(launched->rend_data->rend_pk_digest,
+         circuit->rend_data->rend_pk_digest,
          DIGEST_LEN);
-  memcpy(launched->rend_cookie, r_cookie, REND_COOKIE_LEN);
-  strlcpy(launched->rend_query, service->service_id,
-          sizeof(launched->rend_query));
-  launched->rend_desc_version = service->descriptor_version;
+  memcpy(launched->rend_data->rend_cookie, r_cookie, REND_COOKIE_LEN);
+  strlcpy(launched->rend_data->onion_address, service->service_id,
+          sizeof(launched->rend_data->onion_address));
+  launched->rend_data->rend_desc_version = service->descriptor_version;
   launched->build_state->pending_final_cpath = cpath =
     tor_malloc_zero(sizeof(crypt_path_t));
   cpath->magic = CRYPT_PATH_MAGIC;
@@ -1053,13 +1216,7 @@ rend_service_relaunch_rendezvous(origin_circuit_t *oldcirc)
   newstate->pending_final_cpath = oldstate->pending_final_cpath;
   oldstate->pending_final_cpath = NULL;
 
-  memcpy(newcirc->rend_query, oldcirc->rend_query,
-         REND_SERVICE_ID_LEN_BASE32+1);
-  memcpy(newcirc->rend_pk_digest, oldcirc->rend_pk_digest,
-         DIGEST_LEN);
-  memcpy(newcirc->rend_cookie, oldcirc->rend_cookie,
-         REND_COOKIE_LEN);
-  newcirc->rend_desc_version = oldcirc->rend_desc_version;
+  newcirc->rend_data = rend_data_dup(oldcirc->rend_data);
 }
 
 /** Launch a circuit to serve as an introduction point for the service
@@ -1105,10 +1262,11 @@ rend_service_launch_establish_intro(rend_service_t *service,
     intro->extend_info = extend_info_dup(launched->build_state->chosen_exit);
   }
 
-  strlcpy(launched->rend_query, service->service_id,
-          sizeof(launched->rend_query));
-  memcpy(launched->rend_pk_digest, service->pk_digest, DIGEST_LEN);
-  launched->rend_desc_version = service->descriptor_version;
+  launched->rend_data = tor_malloc_zero(sizeof(rend_data_t));
+  strlcpy(launched->rend_data->onion_address, service->service_id,
+          sizeof(launched->rend_data->onion_address));
+  memcpy(launched->rend_data->rend_pk_digest, service->pk_digest, DIGEST_LEN);
+  launched->rend_data->rend_desc_version = service->descriptor_version;
   if (service->descriptor_version == 2)
     launched->intro_key = crypto_pk_dup_key(intro->intro_key);
   if (launched->_base.state == CIRCUIT_STATE_OPEN)
@@ -1133,12 +1291,14 @@ rend_service_intro_has_opened(origin_circuit_t *circuit)
 
   tor_assert(circuit->_base.purpose == CIRCUIT_PURPOSE_S_ESTABLISH_INTRO);
   tor_assert(circuit->cpath);
+  tor_assert(circuit->rend_data);
 
   base32_encode(serviceid, REND_SERVICE_ID_LEN_BASE32+1,
-                circuit->rend_pk_digest, REND_SERVICE_ID_LEN);
+                circuit->rend_data->rend_pk_digest, REND_SERVICE_ID_LEN);
 
   service = rend_service_get_by_pk_digest_and_version(
-              circuit->rend_pk_digest, circuit->rend_desc_version);
+              circuit->rend_data->rend_pk_digest,
+              circuit->rend_data->rend_desc_version);
   if (!service) {
     log_warn(LD_REND, "Unrecognized service ID %s on introduction circuit %d.",
              serviceid, circuit->_base.n_circ_id);
@@ -1214,8 +1374,10 @@ rend_service_intro_established(origin_circuit_t *circuit, const char *request,
              "received INTRO_ESTABLISHED cell on non-intro circuit.");
     goto err;
   }
+  tor_assert(circuit->rend_data);
   service = rend_service_get_by_pk_digest_and_version(
-              circuit->rend_pk_digest, circuit->rend_desc_version);
+              circuit->rend_data->rend_pk_digest,
+              circuit->rend_data->rend_desc_version);
   if (!service) {
     log_warn(LD_REND, "Unknown service on introduction circuit %d.",
              circuit->_base.n_circ_id);
@@ -1225,7 +1387,7 @@ rend_service_intro_established(origin_circuit_t *circuit, const char *request,
   circuit->_base.purpose = CIRCUIT_PURPOSE_S_INTRO;
 
   base32_encode(serviceid, REND_SERVICE_ID_LEN_BASE32 + 1,
-                circuit->rend_pk_digest, REND_SERVICE_ID_LEN);
+                circuit->rend_data->rend_pk_digest, REND_SERVICE_ID_LEN);
   log_info(LD_REND,
            "Received INTRO_ESTABLISHED cell on circuit %d for service %s",
            circuit->_base.n_circ_id, serviceid);
@@ -1252,12 +1414,13 @@ rend_service_rendezvous_has_opened(origin_circuit_t *circuit)
   tor_assert(circuit->_base.purpose == CIRCUIT_PURPOSE_S_CONNECT_REND);
   tor_assert(circuit->cpath);
   tor_assert(circuit->build_state);
+  tor_assert(circuit->rend_data);
   hop = circuit->build_state->pending_final_cpath;
   tor_assert(hop);
 
-  base16_encode(hexcookie,9,circuit->rend_cookie,4);
+  base16_encode(hexcookie,9,circuit->rend_data->rend_cookie,4);
   base32_encode(serviceid, REND_SERVICE_ID_LEN_BASE32+1,
-                circuit->rend_pk_digest, REND_SERVICE_ID_LEN);
+                circuit->rend_data->rend_pk_digest, REND_SERVICE_ID_LEN);
 
   log_info(LD_REND,
            "Done building circuit %d to rendezvous with "
@@ -1265,7 +1428,8 @@ rend_service_rendezvous_has_opened(origin_circuit_t *circuit)
            circuit->_base.n_circ_id, hexcookie, serviceid);
 
   service = rend_service_get_by_pk_digest_and_version(
-              circuit->rend_pk_digest, circuit->rend_desc_version);
+              circuit->rend_data->rend_pk_digest,
+              circuit->rend_data->rend_desc_version);
   if (!service) {
     log_warn(LD_GENERAL, "Internal error: unrecognized service ID on "
              "introduction circuit.");
@@ -1274,7 +1438,7 @@ rend_service_rendezvous_has_opened(origin_circuit_t *circuit)
   }
 
   /* All we need to do is send a RELAY_RENDEZVOUS1 cell... */
-  memcpy(buf, circuit->rend_cookie, REND_COOKIE_LEN);
+  memcpy(buf, circuit->rend_data->rend_cookie, REND_COOKIE_LEN);
   if (crypto_dh_get_public(hop->dh_handshake_state,
                            buf+REND_COOKIE_LEN, DH_KEY_LEN)<0) {
     log_warn(LD_GENERAL,"Couldn't get DH public key.");
@@ -1336,7 +1500,8 @@ find_intro_circuit(rend_intro_point_t *intro, const char *pk_digest,
                                                   CIRCUIT_PURPOSE_S_INTRO))) {
     if (!memcmp(circ->build_state->chosen_exit->identity_digest,
                 intro->extend_info->identity_digest, DIGEST_LEN) &&
-        circ->rend_desc_version == desc_version) {
+        circ->rend_data &&
+        circ->rend_data->rend_desc_version == desc_version) {
       return circ;
     }
   }
@@ -1346,7 +1511,8 @@ find_intro_circuit(rend_intro_point_t *intro, const char *pk_digest,
                                         CIRCUIT_PURPOSE_S_ESTABLISH_INTRO))) {
     if (!memcmp(circ->build_state->chosen_exit->identity_digest,
                 intro->extend_info->identity_digest, DIGEST_LEN) &&
-        circ->rend_desc_version == desc_version) {
+        circ->rend_data &&
+        circ->rend_data->rend_desc_version == desc_version) {
       return circ;
     }
   }
@@ -1827,11 +1993,13 @@ rend_service_set_connection_addr_port(edge_connection_t *conn,
   rend_service_port_config_t *chosen_port;
 
   tor_assert(circ->_base.purpose == CIRCUIT_PURPOSE_S_REND_JOINED);
+  tor_assert(circ->rend_data);
   log_debug(LD_REND,"beginning to hunt for addr/port");
   base32_encode(serviceid, REND_SERVICE_ID_LEN_BASE32+1,
-                circ->rend_pk_digest, REND_SERVICE_ID_LEN);
-  service = rend_service_get_by_pk_digest_and_version(circ->rend_pk_digest,
-                                                      circ->rend_desc_version);
+                circ->rend_data->rend_pk_digest, REND_SERVICE_ID_LEN);
+  service = rend_service_get_by_pk_digest_and_version(
+                circ->rend_data->rend_pk_digest,
+                circ->rend_data->rend_desc_version);
   if (!service) {
     log_warn(LD_REND, "Couldn't find any service associated with pk %s on "
              "rendezvous circuit %d; closing.",