r16236@catbus: nickm | 2007-10-28 14:36:30 -0400

 Patch from Karsten Loesing: encode and parse v2 rendezvous descriptors.


svn:r12254

6 files changed, 923 insertions, 4 deletions

diff --git a/doc/spec/rend-spec.txt b/doc/spec/rend-spec.txt
index d55103e3b..44aefe7e0 100644
--- a/doc/spec/rend-spec.txt
+++ b/doc/spec/rend-spec.txt
@@ -271,7 +271,7 @@ $Id$
 
            [At start, exactly once]
 
-           The identifier of this introduction point: the base-16 encoded
+           The identifier of this introduction point: the base-32 encoded
            hash of this introduction point's identity key.
 
          "ip-address" ip-address NL
diff --git a/src/or/or.h b/src/or/or.h
index fbc7e9fae..00b6fca6e 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -587,6 +587,27 @@ typedef enum {
 /** Length of 'y' portion of 'y.onion' URL. */
 #define REND_SERVICE_ID_LEN 16
 
+/** Time period for which a v2 descriptor will be valid. */
+#define REND_TIME_PERIOD_V2_DESC_VALIDITY (24*60*60)
+
+/** Time period within which two sets of v2 descriptors will be uploaded in
+ * parallel. */
+#define REND_TIME_PERIOD_OVERLAPPING_V2_DESCS (60*60)
+
+/** Number of non-consecutive replicas (i.e. distributed somewhere
+ * in the ring) for a descriptor. */
+#define REND_NUMBER_OF_NON_CONSECUTIVE_REPLICAS 2
+
+/** Maximum time that an onion router may not respond unless taken
+ * from the list of hidden service directories. */
+#define REND_HS_DIR_REACHABLE_TIMEOUT (45*60)
+
+/** Number of consecutive replicas for a descriptor. */
+#define REND_NUMBER_OF_CONSECUTIVE_REPLICAS 3
+
+/** Length of v2 descriptor ID (32 base32 chars = 160 bits). */
+#define REND_DESC_ID_V2_BASE32 32
+
 #define CELL_DIRECTION_IN 1
 #define CELL_DIRECTION_OUT 2
 
@@ -3351,7 +3372,7 @@ int rend_client_send_introduction(origin_circuit_t *introcirc,
 /** Information used to connect to a hidden service. */
 typedef struct rend_service_descriptor_t {
   crypto_pk_env_t *pk; /**< This service's public key. */
-  int version; /**< 0. */
+  int version; /**< 0 or 2. */
   time_t timestamp; /**< Time when the descriptor was generated. */
   uint16_t protocols; /**< Bitmask: which rendezvous protocols are supported?
                        * (We allow bits '0', '1', and '2' to be set.) */
@@ -3365,6 +3386,8 @@ typedef struct rend_service_descriptor_t {
    * from this array if introduction attempts fail.  If this array is present,
    * its elements correspond to the elements of intro_points. */
   extend_info_t **intro_point_extend_info;
+  strmap_t *intro_keys; /**< map from intro node hexdigest to key; only
+                         * used for versioned hidden service descriptors. */
 } rend_service_descriptor_t;
 
 int rend_cmp_service_ids(const char *one, const char *two);
@@ -3399,6 +3422,17 @@ int rend_cache_lookup_entry(const char *query, int version,
                             rend_cache_entry_t **entry_out);
 int rend_cache_store(const char *desc, size_t desc_len, int published);
 int rend_cache_size(void);
+int rend_encode_v2_descriptors(smartlist_t *desc_strs_out,
+                               smartlist_t *desc_ids_out,
+                               rend_service_descriptor_t *desc, time_t now,
+                               const char *descriptor_cookie, uint8_t period);
+int rend_compute_v2_desc_id(char *desc_id_out, const char *service_id,
+                            const char *descriptor_cookie,
+                            time_t now, uint8_t replica);
+int rend_id_is_in_interval(const char *a, const char *b, const char *c);
+void rend_get_descriptor_id_bytes(char *descriptor_id_out,
+                                  const char *service_id,
+                                  const char *secret_id_part);
 
 /********************************* rendservice.c ***************************/
 
@@ -3728,6 +3762,16 @@ ns_detached_signatures_t *networkstatus_parse_detached_signatures(
 
 authority_cert_t *authority_cert_parse_from_string(const char *s,
                                                    const char **end_of_string);
+int rend_parse_v2_service_descriptor(rend_service_descriptor_t **parsed_out,
+                                     char *desc_id_out,
+                                     char **intro_points_encrypted_out,
+                                     size_t *intro_points_encrypted_size_out,
+                                     size_t *encoded_size_out,
+                                     const char **next_out, const char *desc);
+int rend_decrypt_introduction_points(rend_service_descriptor_t *parsed,
+                                     const char *descriptor_cookie,
+                                     const char *intro_content,
+                                     size_t intro_size);
 
 #endif
 
diff --git a/src/or/rendcommon.c b/src/or/rendcommon.c
index e7b975a68..c89b7e791 100644
--- a/src/or/rendcommon.c
+++ b/src/or/rendcommon.c
@@ -43,7 +43,429 @@ rend_service_descriptor_free(rend_service_descriptor_t *desc)
   tor_free(desc);
 }
 
-/** Encode a V0 service descriptor for <b>desc</b>, and sign it with
+/* Length of a binary-encoded rendezvous service ID. */
+#define REND_SERVICE_ID_BINARY 10
+
+/* Length of the time period that is used to encode the secret ID part of
+ * versioned hidden service descriptors. */
+#define REND_TIME_PERIOD_BINARY 4
+
+/* Length of the descriptor cookie that is used for versioned hidden
+ * service descriptors. */
+#define REND_DESC_COOKIE_BINARY 16
+
+/* Length of the replica number that is used to determine the secret ID
+ * part of versioned hidden service descriptors. */
+#define REND_REPLICA_BINARY 1
+
+/* Length of the base32-encoded secret ID part of versioned hidden service
+ * descriptors. */
+#define REND_SECRET_ID_PART_BASE32 32
+
+/* Compute the descriptor ID for <b>service_id</b> of length
+ * <b>REND_SERVICE_ID_BINARY</b> and <b>secret_id_part</b> of length
+ * <b>DIGEST_LEN</b>, and write it to <b>descriptor_id_out</b> of length
+ * <b>DIGEST_LEN</b>. */
+void
+rend_get_descriptor_id_bytes(char *descriptor_id_out,
+                             const char *service_id,
+                             const char *secret_id_part)
+{
+  crypto_digest_env_t *digest = crypto_new_digest_env();
+  crypto_digest_add_bytes(digest, service_id, REND_SERVICE_ID_BINARY);
+  crypto_digest_add_bytes(digest, secret_id_part, DIGEST_LEN);
+  crypto_digest_get_digest(digest, descriptor_id_out, DIGEST_LEN);
+  crypto_free_digest_env(digest);
+}
+
+/* Compute the secret ID part for <b>time_period</b> of length
+ * <b>REND_TIME_PERIOD_BINARY</b>, <b>descriptor_cookie</b> of length
+ * <b>REND_DESC_COOKIE_BINARY</b> which may also be <b>NULL</b> if no
+ * descriptor_cookie shall be used, and <b>replica</b>, and write it to
+ * <b>secret_id_part</b> of length DIGEST_LEN. */
+static void
+get_secret_id_part_bytes(char *secret_id_part, const char *time_period,
+                         const char *descriptor_cookie, uint8_t replica)
+{
+  crypto_digest_env_t *digest = crypto_new_digest_env();
+  crypto_digest_add_bytes(digest, time_period, REND_TIME_PERIOD_BINARY);
+  if (descriptor_cookie) {
+    crypto_digest_add_bytes(digest, descriptor_cookie,
+                            REND_DESC_COOKIE_BINARY);
+  }
+  crypto_digest_add_bytes(digest, (const char *)&replica, REND_REPLICA_BINARY);
+  crypto_digest_get_digest(digest, secret_id_part, DIGEST_LEN);
+  crypto_free_digest_env(digest);
+}
+
+/* Compute the time period bytes for time <b>now</b> plus a potentially
+ * intended <b>deviation</b> of one or more periods, and the first byte of
+ * <b>service_id</b>, and write it to <b>time_period</b> of length 4. */
+static void
+get_time_period_bytes(char *time_period, time_t now, uint8_t deviation,
+                      const char *service_id)
+{
+  uint32_t host_order =
+    (uint32_t)
+    (now + ((uint8_t) *service_id) * REND_TIME_PERIOD_V2_DESC_VALIDITY / 256)
+    / REND_TIME_PERIOD_V2_DESC_VALIDITY + deviation;
+  uint32_t network_order = htonl(host_order);
+  set_uint32(time_period, network_order);
+}
+
+/* Compute the time in seconds that a descriptor that is generated
+ * <b>now</b> for <b>service_id</b> will be valid. */
+static uint32_t
+get_seconds_valid(time_t now, const char *service_id)
+{
+  uint32_t result = REND_TIME_PERIOD_V2_DESC_VALIDITY -
+    (uint32_t)
+    (now + ((uint8_t) *service_id) * REND_TIME_PERIOD_V2_DESC_VALIDITY / 256)
+    % REND_TIME_PERIOD_V2_DESC_VALIDITY;
+  return result;
+}
+
+/* Compute the binary <b>desc_id</b> for a given base32-encoded
+ * <b>service_id</b> and binary encoded <b>descriptor_cookie</b> of length
+ * 16 that may be <b>NULL</b> at time <b>now</b> for replica number
+ * <b>replica</b>. <b>desc_id</b> needs to have <b>DIGEST_LEN</b> bytes
+ * free. Return 0 for success, -1 otherwise. */
+int
+rend_compute_v2_desc_id(char *desc_id_out, const char *service_id,
+                        const char *descriptor_cookie, time_t now,
+                        uint8_t replica)
+{
+  char service_id_binary[REND_SERVICE_ID_BINARY];
+  char time_period[REND_TIME_PERIOD_BINARY];
+  char secret_id_part[DIGEST_LEN];
+  if (!service_id ||
+      strlen(service_id) != REND_SERVICE_ID_LEN) {
+    log_warn(LD_REND, "Could not compute v2 descriptor ID: "
+                      "Illegal service ID: %s", service_id);
+    return -1;
+  }
+  if (replica >= REND_NUMBER_OF_NON_CONSECUTIVE_REPLICAS) {
+    log_warn(LD_REND, "Could not compute v2 descriptor ID: "
+                      "Replica number out of range: %d", replica);
+    return -1;
+  }
+  /* Convert service ID to binary. */
+  if (base32_decode(service_id_binary, REND_SERVICE_ID_BINARY,
+                    service_id, REND_SERVICE_ID_LEN) < 0) {
+    log_warn(LD_REND, "Could not compute v2 descriptor ID: "
+                      "Illegal characters in service ID: %s",
+             service_id);
+    return -1;
+  }
+  /* Calculate current time-period. */
+  get_time_period_bytes(time_period, now, 0, service_id_binary);
+  /* Calculate secret-id-part = h(time-period + replica). */
+  get_secret_id_part_bytes(secret_id_part, time_period, descriptor_cookie,
+                           replica);
+  /* Calculate descriptor ID. */
+  rend_get_descriptor_id_bytes(desc_id_out, service_id_binary, secret_id_part);
+  return 0;
+}
+
+/* Encode the introduction points in <b>desc</b>, optionally encrypt them
+ * with <b>descriptor_cookie</b> of length 16 that may also be <b>NULL</b>,
+ * write them to a newly allocated string, and write a pointer to it to
+ * <b>ipos_base64</b>. Return 0 for success, -1 otherwise. */
+static int
+rend_encode_v2_intro_points(char **ipos_base64,
+                            rend_service_descriptor_t *desc,
+                            const char *descriptor_cookie)
+{
+  size_t unenc_len;
+  char *unenc;
+  size_t unenc_written = 0;
+  char *enc;
+  int enclen;
+  int i;
+  crypto_cipher_env_t *cipher;
+  /* Assemble unencrypted list of introduction points. */
+  unenc_len = desc->n_intro_points * 1000; /* too long, but ok. */
+  unenc = tor_malloc_zero(unenc_len);
+  for (i = 0; i < desc->n_intro_points; i++) {
+    char id_base32[32 + 1];
+    char *onion_key;
+    size_t onion_key_len;
+    crypto_pk_env_t *intro_key;
+    char *service_key;
+    size_t service_key_len;
+    int res;
+    char hex_digest[HEX_DIGEST_LEN+2];
+    /* Obtain extend info with introduction point details. */
+    extend_info_t *info = desc->intro_point_extend_info[i];
+    /* Encode introduction point ID. */
+    base32_encode(id_base32, 32 + 1, info->identity_digest, DIGEST_LEN);
+    /* Encode onion key. */
+    if (crypto_pk_write_public_key_to_string(info->onion_key, &onion_key,
+                                             &onion_key_len) < 0) {
+      log_warn(LD_REND, "Could not write onion key.");
+      if (onion_key) tor_free(onion_key);
+      tor_free(unenc);
+      return -1;
+    }
+    /* Encode intro key. */
+    hex_digest[0] = '$';
+    base16_encode(hex_digest+1, HEX_DIGEST_LEN+1,
+                  info->identity_digest,
+                  DIGEST_LEN);
+    intro_key = strmap_get(desc->intro_keys, hex_digest);
+    if (!intro_key ||
+      crypto_pk_write_public_key_to_string(intro_key, &service_key,
+                                           &service_key_len) < 0) {
+      log_warn(LD_REND, "Could not write intro key.");
+      if (service_key) tor_free(service_key);
+      tor_free(onion_key);
+      tor_free(unenc);
+      return -1;
+    }
+    /* Assemble everything for this introduction point. */
+    res = tor_snprintf(unenc + unenc_written, unenc_len - unenc_written,
+                         "introduction-point %s\n"
+                         "ip-address %s\n"
+                         "onion-port %d\n"
+                         "onion-key\n%s"
+                         "service-key\n%s",
+                       id_base32,
+                       tor_dup_addr(info->addr),
+                       info->port,
+                       onion_key,
+                       service_key);
+    tor_free(onion_key);
+    tor_free(service_key);
+    if (res < 0) {
+      log_warn(LD_REND, "Not enough space for writing introduction point "
+                        "string.");
+      tor_free(unenc);
+      return -1;
+    }
+    /* Update total number of written bytes for unencrypted intro points. */
+    unenc_written += res;
+  }
+  /* Finalize unencrypted introduction points. */
+  if (unenc_len < unenc_written + 2) {
+    log_warn(LD_REND, "Not enough space for finalizing introduction point "
+                      "string.");
+    tor_free(unenc);
+    return -1;
+  }
+  unenc[unenc_written++] = '\n';
+  unenc[unenc_written++] = 0;
+  /* If a descriptor cookie is passed, encrypt introduction points. */
+  if (descriptor_cookie) {
+    enc = tor_malloc_zero(unenc_written + 16);
+    cipher = crypto_create_init_cipher(descriptor_cookie, 1);
+    enclen = crypto_cipher_encrypt_with_iv(cipher, enc, unenc_written + 16,
+                                           unenc, unenc_written);
+    crypto_free_cipher_env(cipher);
+    tor_free(unenc);
+    if (enclen < 0) {
+      log_warn(LD_REND, "Could not encrypt introduction point string.");
+      if (enc) tor_free(enc);
+      return -1;
+    }
+    /* Replace original string by encrypted one. */
+    unenc = enc;
+    unenc_written = enclen;
+  }
+  /* Base64-encode introduction points. */
+  *ipos_base64 = tor_malloc_zero(unenc_written * 2);
+  if (base64_encode(*ipos_base64, unenc_written * 2, unenc, unenc_written)
+      < 0) {
+    log_warn(LD_REND, "Could not encode introduction point string to "
+                      "base64.");
+    tor_free(unenc);
+    tor_free(ipos_base64);
+    return -1;
+  }
+  tor_free(unenc);
+  return 0;
+}
+
+/** Attempt to parse the given <b>desc_str</b> and return true if this
+ * succeeds, false otherwise. */
+static int
+rend_desc_v2_is_parsable(const char *desc_str)
+{
+  rend_service_descriptor_t *test_parsed;
+  char test_desc_id[DIGEST_LEN];
+  char *test_intro_content;
+  size_t test_intro_size;
+  size_t test_encoded_size;
+  const char *test_next;
+  int res = rend_parse_v2_service_descriptor(&test_parsed, test_desc_id,
+                                         &test_intro_content,
+                                         &test_intro_size,
+                                         &test_encoded_size,
+                                         &test_next, desc_str);
+  tor_free(test_parsed);
+  tor_free(test_intro_content);
+  return (res >= 0);
+}
+
+/** Encode a set of new service descriptors for <b>desc</b> at time
+ * <b>now</b> using <b>descriptor_cookie</b> (may be <b>NULL</b> if
+ * introduction points shall not be encrypted) and <b>period</b> (e.g. 0
+ * for the current period, 1 for the next period, etc.), write the
+ * ASCII-encoded outputs to newly allocated strings and add them to the
+ * existing <b>desc_strs</b>, and write the descriptor IDs to newly
+ * allocated strings and add them to the existing <b>desc_ids</b>; return
+ * the number of seconds that the descriptors will be found under those
+ * <b>desc_ids</b> by clients, or -1 if the encoding was not successful. */
+int
+rend_encode_v2_descriptors(smartlist_t *desc_strs_out,
+                           smartlist_t *desc_ids_out,
+                           rend_service_descriptor_t *desc, time_t now,
+                           const char *descriptor_cookie, uint8_t period)
+{
+  char service_id[DIGEST_LEN];
+  char time_period[REND_TIME_PERIOD_BINARY];
+  char *ipos_base64 = NULL;
+  int k;
+  uint32_t seconds_valid;
+  if (!desc) {
+    log_warn(LD_REND, "Could not encode v2 descriptor: No desc given.");
+    return -1;
+  }
+  /* Obtain service_id from public key. */
+  crypto_pk_get_digest(desc->pk, service_id);
+  /* Calculate current time-period. */
+  get_time_period_bytes(time_period, now, period, service_id);
+  /* Determine how many seconds the descriptor will be valid. */
+  seconds_valid = period * REND_TIME_PERIOD_V2_DESC_VALIDITY +
+                  get_seconds_valid(now, service_id);
+  /* Assemble, possibly encrypt, and encode introduction points. */
+  if (rend_encode_v2_intro_points(&ipos_base64, desc, descriptor_cookie) < 0) {
+    log_warn(LD_REND, "Encoding of introduction points did not succeed.");
+    if (ipos_base64) tor_free(ipos_base64);
+    return -1;
+  }
+  /* Encode REND_NUMBER_OF_NON_CONSECUTIVE_REPLICAS descriptors. */
+  for (k = 0; k < REND_NUMBER_OF_NON_CONSECUTIVE_REPLICAS; k++) {
+    char secret_id_part[DIGEST_LEN];
+    char secret_id_part_base32[REND_SECRET_ID_PART_BASE32 + 1];
+    char *desc_id;
+    char desc_id_base32[REND_DESC_ID_V2_BASE32 + 1];
+    char *permanent_key;
+    size_t permanent_key_len;
+    char published[ISO_TIME_LEN+1];
+    int i;
+    char protocol_versions_string[16]; /* max len: "0,1,2,3,4,5,6,7\0" */
+    size_t protocol_versions_written;
+    size_t desc_len;
+    char *desc_str;
+    int result = 0;
+    size_t written = 0;
+    char desc_digest[DIGEST_LEN];
+    /* Calculate secret-id-part = h(time-period + cookie + replica). */
+    get_secret_id_part_bytes(secret_id_part, time_period, descriptor_cookie,
+                             k);
+    base32_encode(secret_id_part_base32, REND_SECRET_ID_PART_BASE32 + 1,
+                  secret_id_part, DIGEST_LEN);
+    /* Calculate descriptor ID. */
+    desc_id = tor_malloc_zero(DIGEST_LEN);
+    rend_get_descriptor_id_bytes(desc_id, service_id, secret_id_part);
+    smartlist_add(desc_ids_out, desc_id);
+    base32_encode(desc_id_base32, REND_DESC_ID_V2_BASE32 + 1,
+                  desc_id, DIGEST_LEN);
+    /* PEM-encode the public key */
+    if (crypto_pk_write_public_key_to_string(desc->pk, &permanent_key,
+                                             &permanent_key_len) < 0) {
+      log_warn(LD_BUG, "Could not write public key to string.");
+      if (permanent_key) tor_free(permanent_key);
+      goto err;
+    }
+    /* Encode timestamp. */
+    format_iso_time(published, desc->timestamp);
+    /* Write protocol-versions bitmask to comma-separated value string. */
+    protocol_versions_written = 0;
+    for (i = 0; i < 8; i++) {
+      if (desc->protocols & 1 << i) {
+        tor_snprintf(protocol_versions_string + protocol_versions_written,
+                     16 - protocol_versions_written, "%d,", i);
+        protocol_versions_written += 2;
+      }
+    }
+    protocol_versions_string[protocol_versions_written - 1] = 0;
+    /* Assemble complete descriptor. */
+    desc_len = 2000 + desc->n_intro_points * 1000; /* far too long, but ok. */
+    desc_str = tor_malloc_zero(desc_len);
+    result = tor_snprintf(desc_str, desc_len,
+             "rendezvous-service-descriptor %s\n"
+             "version 2\n"
+             "permanent-key\n%s"
+             "secret-id-part %s\n"
+             "publication-time %s\n"
+             "protocol-versions %s\n"
+             "introduction-points\n"
+             "-----BEGIN MESSAGE-----\n%s"
+             "-----END MESSAGE-----\n",
+        desc_id_base32,
+        permanent_key,
+        secret_id_part_base32,
+        published,
+        protocol_versions_string,
+        ipos_base64);
+    tor_free(permanent_key);
+    if (result < 0) {
+      log_warn(LD_BUG, "Descriptor ran out of room.");
+      if (desc_str) tor_free(desc_str);
+      goto err;
+    }
+    written = result;
+    /* Add signature. */
+    strlcpy(desc_str + written, "signature\n", desc_len - written);
+    written += strlen(desc_str + written);
+    desc_str[written] = '\0';
+    if (crypto_digest(desc_digest, desc_str, written) < 0) {
+      log_warn(LD_BUG, "could not create digest.");
+      tor_free(desc_str);
+      goto err;
+    }
+    if (router_append_dirobj_signature(desc_str + written,
+                                       desc_len - written,
+                                       desc_digest, desc->pk) < 0) {
+      log_warn(LD_BUG, "Couldn't sign desc.");
+      tor_free(desc_str);
+      goto err;
+    }
+    written += strlen(desc_str+written);
+    if (written+2 > desc_len) {
+        log_warn(LD_BUG, "Could not finish desc.");
+        tor_free(desc_str);
+        goto err;
+    }
+    desc_str[written++] = '\n';
+    desc_str[written++] = 0;
+    /* Check if we can parse our own descriptor. */
+    if (!rend_desc_v2_is_parsable(desc_str)) {
+      log_warn(LD_BUG, "Could not parse my own descriptor: %s", desc_str);
+      tor_free(desc_str);
+      goto err;
+    }
+    smartlist_add(desc_strs_out, desc_str);
+  }
+
+  log_info(LD_REND, "Successfully encoded a v2 descriptor and "
+                      "confirmed that it is parsable.");
+  goto done;
+
+ err:
+  SMARTLIST_FOREACH(desc_ids_out, void *, id, tor_free(id));
+  smartlist_clear(desc_ids_out);
+  SMARTLIST_FOREACH(desc_strs_out, void *, str, tor_free(str));
+  smartlist_clear(desc_strs_out);
+  seconds_valid = -1;
+
+ done:
+  tor_free(ipos_base64);
+  return seconds_valid;
+}
+
+/** Encode a service descriptor for <b>desc</b>, and sign it with
  * <b>key</b>. Store the descriptor in *<b>str_out</b>, and set
  * *<b>len_out</b> to its length.
  */
diff --git a/src/or/rendservice.c b/src/or/rendservice.c
index c769f11ba..3f5afcde1 100644
--- a/src/or/rendservice.c
+++ b/src/or/rendservice.c
@@ -51,6 +51,8 @@ typedef struct rend_service_t {
   char pk_digest[DIGEST_LEN];
   smartlist_t *intro_nodes; /**< list of hexdigests for intro points we have,
                              * or are trying to establish. */
+  strmap_t *intro_keys; /**< map from intro node hexdigest to key; only
+                          * used for versioned hidden service descriptors. */
   time_t intro_period_started;
   int n_intro_circuits_launched; /**< count of intro circuits we have
                                   * established in this period. */
@@ -72,6 +74,15 @@ num_rend_services(void)
   return smartlist_len(rend_service_list);
 }
 
+/** Release the storage held by the intro key in <b>_ent</b>.
+ */
+static void
+intro_key_free(void *_ent)
+{
+  crypto_pk_env_t *ent = _ent;
+  crypto_free_pk_env(ent);
+}
+
 /** Release the storage held by <b>service</b>.
  */
 static void
@@ -83,6 +94,8 @@ rend_service_free(rend_service_t *service)
   smartlist_free(service->ports);
   if (service->private_key)
     crypto_free_pk_env(service->private_key);
+  if (service->intro_keys)
+    strmap_free(service->intro_keys, intro_key_free);
   tor_free(service->intro_prefer_nodes);
   tor_free(service->intro_exclude_nodes);
   SMARTLIST_FOREACH(service->intro_nodes, void*, p, tor_free(p));
@@ -119,6 +132,7 @@ add_service(rend_service_t *service)
     service->intro_prefer_nodes = tor_strdup("");
   if (!service->intro_exclude_nodes)
     service->intro_exclude_nodes = tor_strdup("");
+  service->intro_keys = strmap_new();
 
   if (!smartlist_len(service->ports)) {
     log_warn(LD_CONFIG, "Hidden service with no ports configured; ignoring.");
@@ -303,6 +317,7 @@ rend_service_update_descriptor(rend_service_t *service)
   d->intro_point_extend_info = tor_malloc_zero(sizeof(extend_info_t*)*n);
   /* We support intro protocol 2 and protocol 0. */
   d->protocols = (1<<2) | (1<<0);
+  d->intro_keys = service->intro_keys;
   for (i=0; i < n; ++i) {
     const char *name = smartlist_get(service->intro_nodes, i);
     router = router_get_by_nickname(name, 1);
diff --git a/src/or/routerparse.c b/src/or/routerparse.c
index 10d043650..98e46c8e4 100644
--- a/src/or/routerparse.c
+++ b/src/or/routerparse.c
@@ -80,6 +80,21 @@ typedef enum {
   A_PURPOSE,
   _A_UNKNOWN,
 
+  R_RENDEZVOUS_SERVICE_DESCRIPTOR,
+  R_VERSION,
+  R_PERMANENT_KEY,
+  R_SECRET_ID_PART,
+  R_PUBLICATION_TIME,
+  R_PROTOCOL_VERSIONS,
+  R_INTRODUCTION_POINTS,
+  R_SIGNATURE,
+
+  R_IPO_IDENTIFIER,
+  R_IPO_IP_ADDRESS,
+  R_IPO_ONION_PORT,
+  R_IPO_ONION_KEY,
+  R_IPO_SERVICE_KEY,
+
   _UNRECOGNIZED,
   _ERR,
   _EOF,
@@ -298,6 +313,31 @@ static token_rule_t dir_key_certificate_table[] = {
   END_OF_TABLE
 };
 
+/** List of tokens allowable in rendezvous service descriptors */
+static token_rule_t desc_token_table[] = {
+  T1("rendezvous-service-descriptor", R_RENDEZVOUS_SERVICE_DESCRIPTOR, EQ(1), \
+     NO_OBJ),
+  T1("version", R_VERSION, EQ(1), NO_OBJ),
+  T1("permanent-key", R_PERMANENT_KEY, NO_ARGS, NEED_KEY_1024),
+  T1("secret-id-part", R_SECRET_ID_PART, EQ(1), NO_OBJ),
+  T1("publication-time", R_PUBLICATION_TIME, CONCAT_ARGS, NO_OBJ),
+  T1("protocol-versions", R_PROTOCOL_VERSIONS, EQ(1), NO_OBJ),
+  T1("introduction-points", R_INTRODUCTION_POINTS, NO_ARGS, NEED_OBJ),
+  T1("signature", R_SIGNATURE, NO_ARGS, NEED_OBJ),
+  END_OF_TABLE
+};
+
+/** List of tokens allowed in the (encrypted) list of introduction points of
+ * rendezvous service descriptors */
+static token_rule_t ipo_token_table[] = {
+  T1("introduction-point", R_IPO_IDENTIFIER, EQ(1), NO_OBJ),
+  T1("ip-address", R_IPO_IP_ADDRESS, EQ(1), NO_OBJ),
+  T1("onion-port", R_IPO_ONION_PORT, EQ(1), NO_OBJ),
+  T1("onion-key", R_IPO_ONION_KEY, NO_ARGS, NEED_KEY_1024),
+  T1("service-key", R_IPO_SERVICE_KEY, NO_ARGS, NEED_KEY_1024),
+  END_OF_TABLE
+};
+
 static token_rule_t networkstatus_vote_token_table[] = {
   T1("network-status-version", K_NETWORK_STATUS_VERSION,
                                                    GE(1),       NO_OBJ ),
@@ -3125,3 +3165,309 @@ sort_version_list(smartlist_t *versions, int remove_duplicates)
     smartlist_uniq(versions, _compare_tor_version_str_ptr, _tor_free);
 }
 
+/** Parse and validate the ASCII-encoded v2 descriptor in <b>desc</b>,
+ * write the parsed descriptor to the newly allocated <b>parsed</b>, the
+ * binary descriptor ID of length DIGEST_LEN to <b>desc_id</b>, the
+ * encrypted introduction points to the newly allocated
+ * <b>intro_points_encrypted</b>, their encrypted size to
+ * <b>intro_points_encrypted_size</b>, the size of the encoded descriptor
+ * to <b>encoded_size</b>, and a pointer to the possibly next
+ * descriptor to <b>next</b>; return 0 for success (including validation)
+ * and -1 for failure.
+ */
+int
+rend_parse_v2_service_descriptor(rend_service_descriptor_t **parsed_out,
+                                 char *desc_id_out,
+                                 char **intro_points_encrypted_out,
+                                 size_t *intro_points_encrypted_size_out,
+                                 size_t *encoded_size_out,
+                                 const char **next_out, const char *desc)
+{
+  rend_service_descriptor_t *result =
+                            tor_malloc_zero(sizeof(rend_service_descriptor_t));
+  char desc_hash[DIGEST_LEN];
+  const char *eos;
+  smartlist_t *tokens = smartlist_create();
+  directory_token_t *tok;
+  char secret_id_part[DIGEST_LEN];
+  int i, version;
+  smartlist_t *versions;
+  char public_key_hash[DIGEST_LEN];
+  char test_desc_id[DIGEST_LEN];
+  tor_assert(desc);
+  /* Check if desc starts correctly. */
+  if (strncmp(desc, "rendezvous-service-descriptor ",
+              strlen("rendezvous-service-descriptor "))) {
+    log_info(LD_REND, "Descriptor does not start correctly.");
+    goto err;
+  }
+  /* Compute descriptor hash for later validation. */
+  if (router_get_hash_impl(desc, desc_hash,
+                           "rendezvous-service-descriptor ",
+                           "\nsignature", '\n') < 0) {
+    log_warn(LD_REND, "Couldn't compute descriptor hash.");
+    goto err;
+  }
+  /* Determine end of string. */
+  eos = strstr(desc, "\nrendezvous-service-descriptor ");
+  if (!eos)
+    eos = desc + strlen(desc);
+  else
+    eos = eos + 1;
+  /* Tokenize descriptor. */
+  if (tokenize_string(desc, eos, tokens, desc_token_table, 0)) {
+    log_warn(LD_REND, "Error tokenizing descriptor.");
+    goto err;
+  }
+  /* Set next to next descriptor, if available. */
+  *next_out = eos;
+  /* Set length of encoded descriptor. */
+  *encoded_size_out = eos - desc;
+  /* Check min allowed length of token list. */
+  if (smartlist_len(tokens) < 8) {
+    log_warn(LD_REND, "Impossibly short descriptor.");
+    goto err;
+  }
+  /* Check whether descriptor starts correctly. */
+  tok = smartlist_get(tokens, 0);
+  if (tok->tp != R_RENDEZVOUS_SERVICE_DESCRIPTOR) {
+    log_warn(LD_REND, "Entry does not start with "
+             "\"rendezvous-service-descriptor\"");
+    goto err;
+  }
+  /* Parse base32-encoded descriptor ID. */
+  tok = find_first_by_keyword(tokens, R_RENDEZVOUS_SERVICE_DESCRIPTOR);
+  tor_assert(tok);
+  tor_assert(tok->n_args == 1);
+  if (strlen(tok->args[0]) != 32 ||
+      strspn(tok->args[0], BASE32_CHARS) != 32) {
+    log_warn(LD_REND, "Invalid descriptor ID: '%s'", tok->args[0]);
+    goto err;
+  }
+  if (base32_decode(desc_id_out, DIGEST_LEN,
+                    tok->args[0], REND_DESC_ID_V2_BASE32) < 0) {
+    log_warn(LD_REND, "Descriptor ID contains illegal characters: %s",
+             tok->args[0]);
+    goto err;
+  }
+  /* Parse descriptor version. */
+  tok = find_first_by_keyword(tokens, R_VERSION);
+  tor_assert(tok);
+  tor_assert(tok->n_args == 1);
+  result->version = atoi(tok->args[0]);
+  if (result->version < 2) {
+    log_warn(LD_REND, "Wrong descriptor version: %d", result->version);
+    goto err;
+  }
+  /* Parse public key. */
+  tok = find_first_by_keyword(tokens, R_PERMANENT_KEY);
+  tor_assert(tok);
+  result->pk = tok->key;
+  tok->key = NULL; /* Prevent free */
+  /* Parse secret ID part. */
+  tok = find_first_by_keyword(tokens, R_SECRET_ID_PART);
+  tor_assert(tok);
+  tor_assert(tok->n_args == 1);
+  if (strlen(tok->args[0]) != 32 ||
+      strspn(tok->args[0], BASE32_CHARS) != 32) {
+    log_warn(LD_REND, "Invalid secret ID part: '%s'", tok->args[0]);
+    goto err;
+  }
+  if (base32_decode(secret_id_part, DIGEST_LEN, tok->args[0], 32) < 0) {
+    log_warn(LD_REND, "Secret ID part contains illegal characters: %s",
+             tok->args[0]);
+    goto err;
+  }
+  /* Parse publication time -- up-to-date check is done when storing the
+   * descriptor. */
+  tok = find_first_by_keyword(tokens, R_PUBLICATION_TIME);
+  tor_assert(tok);
+  tor_assert(tok->n_args == 1);
+  if (parse_iso_time(tok->args[0], &result->timestamp) < 0) {
+    log_warn(LD_REND, "Invalid publication time: '%s'", tok->args[0]);
+    goto err;
+  }
+  /* Parse protocol versions. */
+  tok = find_first_by_keyword(tokens, R_PROTOCOL_VERSIONS);
+  tor_assert(tok);
+  tor_assert(tok->n_args == 1);
+  versions = smartlist_create();
+  smartlist_split_string(versions, tok->args[0], ",",
+                         SPLIT_SKIP_SPACE|SPLIT_IGNORE_BLANK, 0);
+  for (i = 0; i < smartlist_len(versions); i++) {
+    version = atoi(smartlist_get(versions, i));
+    result->protocols |= 1 << version;
+  }
+  smartlist_free(versions);
+  /* Parse encrypted introduction points. Don't verify. */
+  tok = find_first_by_keyword(tokens, R_INTRODUCTION_POINTS);
+  tor_assert(tok);
+  *intro_points_encrypted_out = tor_malloc_zero(tok->object_size);
+  memcpy(*intro_points_encrypted_out, tok->object_body, tok->object_size);
+  *intro_points_encrypted_size_out = tok->object_size;
+  /* Parse and verify signature. */
+  tok = find_first_by_keyword(tokens, R_SIGNATURE);
+  tor_assert(tok);
+  note_crypto_pk_op(VERIFY_RTR);
+  if (check_signature_token(desc_hash, tok, result->pk, 0,
+                            "v2 rendezvous service descriptor") < 0)
+    goto err;
+  /* Verify that descriptor ID belongs to public key and secret ID part. */
+  crypto_pk_get_digest(result->pk, public_key_hash);
+  rend_get_descriptor_id_bytes(test_desc_id, public_key_hash,
+                               secret_id_part);
+  if (memcmp(desc_id_out, test_desc_id, DIGEST_LEN)) {
+    log_warn(LD_REND, "Parsed descriptor ID does not match "
+             "computed descriptor ID.");
+    goto err;
+  }
+  goto done;
+ err:
+  if (result)
+    rend_service_descriptor_free(result);
+  result = NULL;
+ done:
+  if (tokens) {
+    SMARTLIST_FOREACH(tokens, directory_token_t *, t, token_free(t));
+    smartlist_free(tokens);
+  }
+  *parsed_out = result;
+  if (result)
+    return 0;
+  return -1;
+}
+
+/** Decrypt and decode the introduction points in
+ * <b>intro_points_encrypted</b> of length
+ * <b>intro_points_encrypted_size</b> using <b>descriptor_cookie</b>
+ * (which may also be <b>NULL</b> if no decryption, but only parsing is
+ * required), parse the introduction points, and write the result to
+ * <b>parsed</b>; return the number of successfully parsed introduction
+ * points or -1 in case of a failure.
+ */
+int
+rend_decrypt_introduction_points(rend_service_descriptor_t *parsed,
+                                 const char *descriptor_cookie,
+                                 const char *intro_points_encrypted,
+                                 size_t intro_points_encrypted_size)
+{
+  char *ipos_decrypted;
+  const char **current_ipo;
+  smartlist_t *intropoints;
+  smartlist_t *tokens;
+  int i;
+  directory_token_t *tok;
+  extend_info_t *info;
+  struct in_addr ip;
+  int result;
+  tor_assert(parsed);
+  tor_assert(intro_points_encrypted);
+  tor_assert(intro_points_encrypted_size > 0);
+  /* Decrypt introduction points, if required. */
+  if (descriptor_cookie) {
+    crypto_cipher_env_t *cipher;
+    int unenclen;
+    ipos_decrypted = tor_malloc_zero(intro_points_encrypted_size - 16);
+    cipher = crypto_create_init_cipher(descriptor_cookie, 0);
+    unenclen = crypto_cipher_decrypt_with_iv(cipher, ipos_decrypted,
+                                             intro_points_encrypted_size - 16,
+                                             intro_points_encrypted,
+                                             intro_points_encrypted_size);
+    crypto_free_cipher_env(cipher);
+    if (unenclen < 0) {
+      if (ipos_decrypted) tor_free(ipos_decrypted);
+      return -1;
+    }
+    intro_points_encrypted = ipos_decrypted;
+    intro_points_encrypted_size = unenclen;
+  }
+  /* Consider one intro point after the other. */
+  current_ipo = (const char **)&intro_points_encrypted;
+  intropoints = smartlist_create();
+  tokens = smartlist_create();
+  parsed->intro_keys = strmap_new();
+  while (!strcmpstart(*current_ipo, "introduction-point ")) {
+    /* Determine end of string. */
+    const char *eos = strstr(*current_ipo, "\nintroduction-point ");
+    if (!eos)
+      eos = *current_ipo+strlen(*current_ipo);
+    else
+      eos = eos+1;
+    /* Free tokens and clear token list. */
+    SMARTLIST_FOREACH(tokens, directory_token_t *, t, token_free(t));
+    smartlist_clear(tokens);
+    /* Tokenize string. */
+    if (tokenize_string(*current_ipo, eos, tokens, ipo_token_table, 0)) {
+      log_warn(LD_REND, "Error tokenizing introduction point.");
+      goto err;
+    }
+    /* Advance to next introduction point, if available. */
+    *current_ipo = eos;
+    /* Check minimum allowed length of introduction point. */
+    if (smartlist_len(tokens) < 5) {
+      log_warn(LD_REND, "Impossibly short introduction point.");
+      goto err;
+    }
+    /* Allocate new extend info. */
+    info = tor_malloc_zero(sizeof(extend_info_t));
+    /* Parse identifier. */
+    tok = find_first_by_keyword(tokens, R_IPO_IDENTIFIER);
+    tor_assert(tok);
+    if (base32_decode(info->identity_digest, DIGEST_LEN,
+                      tok->args[0], 32) < 0) {
+      log_warn(LD_REND, "Identity digest contains illegal characters: %s",
+               tok->args[0]);
+      tor_free(info);
+      goto err;
+    }
+    /* Write identifier to nickname. */
+    info->nickname[0] = '$';
+    base16_encode(info->nickname + 1, sizeof(info->nickname) - 1,
+                  info->identity_digest, DIGEST_LEN);
+    /* Parse IP address. */
+    tok = find_first_by_keyword(tokens, R_IPO_IP_ADDRESS);
+    if (tor_inet_aton(tok->args[0], &ip) == 0) {
+      log_warn(LD_REND, "Could not parse IP address.");
+      tor_free(info);
+      goto err;
+    }
+    info->addr = ntohl(ip.s_addr);
+    /* Parse onion port. */
+    tok = find_first_by_keyword(tokens, R_IPO_ONION_PORT);
+    info->port = (uint16_t) atoi(tok->args[0]);
+    /* Parse onion key. */
+    tok = find_first_by_keyword(tokens, R_IPO_ONION_KEY);
+    info->onion_key = tok->key;
+    tok->key = NULL; /* Prevent free */
+    /* Parse service key. */
+    tok = find_first_by_keyword(tokens, R_IPO_SERVICE_KEY);
+    strmap_set(parsed->intro_keys, info->nickname, tok->key);
+    tok->key = NULL; /* Prevent free */
+    /* Add extend info to list of introduction points. */
+    smartlist_add(intropoints, info);
+  }
+  /* Write extend infos to descriptor. */
+  parsed->n_intro_points = smartlist_len(intropoints);
+  parsed->intro_point_extend_info =
+    tor_malloc_zero(sizeof(extend_info_t *) * parsed->n_intro_points);
+  parsed->intro_points =
+    tor_malloc_zero(sizeof(char *) * parsed->n_intro_points);
+  i = 0;
+  SMARTLIST_FOREACH(intropoints, extend_info_t *, ipo, {
+      parsed->intro_points[i] = tor_strdup(ipo->nickname);
+      parsed->intro_point_extend_info[i++] = ipo;
+  });
+  result = parsed->n_intro_points;
+  goto done;
+
+ err:
+  result = -1;
+
+ done:
+  /* Free tokens and clear token list. */
+  SMARTLIST_FOREACH(tokens, directory_token_t *, t, token_free(t));
+  smartlist_free(tokens);
+
+  return result;
+}
+
diff --git a/src/or/test.c b/src/or/test.c
index 6e774be66..a8dcb053d 100644
--- a/src/or/test.c
+++ b/src/or/test.c
@@ -99,7 +99,7 @@ remove_directory(void)
 static crypto_pk_env_t *
 pk_generate(int idx)
 {
-  static crypto_pk_env_t *pregen[3] = {NULL, NULL, NULL};
+  static crypto_pk_env_t *pregen[5] = {NULL, NULL, NULL, NULL, NULL};
   tor_assert(idx < (int)(sizeof(pregen)/sizeof(pregen[0])));
   if (! pregen[idx]) {
     pregen[idx] = crypto_new_pk_env();
@@ -3216,6 +3216,97 @@ test_crypto_base32_decode(void)
   test_memneq(plain, decoded, 60);
 }
 
+/* Test encoding and parsing of v2 rendezvous service descriptors. */
+static void
+test_rend_fns_v2(void)
+{
+  rend_service_descriptor_t *generated, *parsed;
+  char service_id[DIGEST_LEN];
+  char service_id_base32[REND_SERVICE_ID_LEN+1];
+  const char *next_desc;
+  smartlist_t *desc_strs = smartlist_create();
+  smartlist_t *desc_ids = smartlist_create();
+  char computed_desc_id[DIGEST_LEN];
+  char parsed_desc_id[DIGEST_LEN];
+  crypto_pk_env_t *pk1, *pk2;
+  time_t now;
+  char *intro_points_encrypted;
+  size_t intro_points_size;
+  size_t encoded_size;
+  int i;
+  pk1 = pk_generate(0);
+  pk2 = pk_generate(1);
+  generated = tor_malloc_zero(sizeof(rend_service_descriptor_t));
+  generated->pk = crypto_pk_dup_key(pk1);
+  crypto_pk_get_digest(generated->pk, service_id);
+  base32_encode(service_id_base32, REND_SERVICE_ID_LEN+1, service_id, 10);
+  now = time(NULL);
+  generated->timestamp = now;
+  generated->n_intro_points = 3;
+  generated->version = 2;
+  generated->protocols = 42;
+  generated->intro_point_extend_info =
+    tor_malloc_zero(sizeof(extend_info_t *) * generated->n_intro_points);
+  generated->intro_points =
+    tor_malloc_zero(sizeof(char *) * generated->n_intro_points);
+  generated->intro_keys = strmap_new();
+  for (i = 0; i < generated->n_intro_points; i++) {
+    extend_info_t *info = tor_malloc_zero(sizeof(extend_info_t));
+    crypto_pk_env_t *okey = pk_generate(2 + i);
+    info->onion_key = crypto_pk_dup_key(okey);
+    crypto_pk_get_digest(info->onion_key, info->identity_digest);
+    //crypto_rand(info->identity_digest, DIGEST_LEN); /* Would this work? */
+    info->nickname[0] = '$';
+    base16_encode(info->nickname + 1, sizeof(info->nickname) - 1,
+                  info->identity_digest, DIGEST_LEN);
+    info->addr = crypto_rand_int(65536); /* Does not cover all IP addresses. */
+    info->port = crypto_rand_int(65536);
+    generated->intro_points[i] = tor_strdup(info->nickname);
+    generated->intro_point_extend_info[i] = info;
+    strmap_set(generated->intro_keys, info->nickname, pk2);
+  }
+  test_assert(rend_encode_v2_descriptors(desc_strs, desc_ids, generated, now,
+                                         NULL, 0) > 0);
+  test_assert(rend_compute_v2_desc_id(computed_desc_id, service_id_base32,
+                                      NULL, now, 0) == 0);
+  test_assert(smartlist_digest_isin(desc_ids, computed_desc_id));
+  test_assert(rend_parse_v2_service_descriptor(&parsed, parsed_desc_id,
+                                               &intro_points_encrypted,
+                                               &intro_points_size,
+                                               &encoded_size,
+                                               &next_desc,
+                                               desc_strs->list[0]) == 0);
+  test_assert(parsed);
+  test_assert(smartlist_digest_isin(desc_ids, parsed_desc_id));
+  test_assert(rend_decrypt_introduction_points(parsed, NULL,
+                                               intro_points_encrypted,
+                                               intro_points_size) == 3);
+  test_assert(!crypto_pk_cmp_keys(generated->pk, parsed->pk));
+  test_eq(parsed->timestamp, now);
+  test_eq(parsed->version, 2);
+  test_eq(parsed->protocols, 42);
+  test_eq(parsed->n_intro_points, 3);
+  for (i = 0; i < parsed->n_intro_points; i++) {
+    extend_info_t *par_info = parsed->intro_point_extend_info[i];
+    extend_info_t *gen_info = generated->intro_point_extend_info[i];
+    test_assert(!crypto_pk_cmp_keys(gen_info->onion_key, par_info->onion_key));
+    test_memeq(gen_info->identity_digest, par_info->identity_digest,
+               DIGEST_LEN);
+    test_streq(gen_info->nickname, par_info->nickname);
+    test_streq(generated->intro_points[i], parsed->intro_points[i]);
+    test_eq(gen_info->addr, par_info->addr);
+    test_eq(gen_info->port, par_info->port);
+  }
+  tor_free(intro_points_encrypted);
+  /*for (i = 0; i < REND_NUMBER_OF_NON_CONSECUTIVE_REPLICAS; i++)
+    tor_free(desc_strs[i]);*/
+  smartlist_free(desc_strs);
+  for (i = 0; i < parsed->n_intro_points; i++) {
+    tor_free(parsed->intro_point_extend_info[i]->onion_key);
+    tor_free(generated->intro_point_extend_info[i]->onion_key);
+  }
+}
+
 #define ENT(x) { #x, test_ ## x, 0, 0 }
 #define SUBENT(x,y) { #x "/" #y, test_ ## x ## _ ## y, 1, 0 }
 
@@ -3249,6 +3340,7 @@ static struct {
   ENT(v3_networkstatus),
   ENT(policies),
   ENT(rend_fns),
+  SUBENT(rend_fns, v2),
   { NULL, NULL, 0, 0 },
 };