Merge branch 'prop176-v2'

12 files changed, 1976 insertions, 154 deletions

diff --git a/changes/prop176 b/changes/prop176
new file mode 100644
index 000000000..faedc1adf
--- /dev/null
+++ b/changes/prop176
@@ -0,0 +1,8 @@
+  o Major features
+    - Implement a new handshake protocol for authenticating Tors to
+      each other over TLS. It should be more resistant to fingerprinting
+      than previous protocols, and should require less TLS hacking for
+      future Tor implementations.  Implements Proposal 185.
+    - Allow variable-length padding cells to disguise the length of
+      Tor's TLS records.  Implements part of Proposal 184.
+
diff --git a/src/common/crypto.c b/src/common/crypto.c
index 9ad7575a7..0076c1d35 100644
--- a/src/common/crypto.c
+++ b/src/common/crypto.c
@@ -1206,9 +1206,6 @@ crypto_pk_asn1_decode(const char *str, size_t len)
 {
   RSA *rsa;
   unsigned char *buf;
-  /* This ifdef suppresses a type warning.  Take out the first case once
-   * everybody is using OpenSSL 0.9.7 or later.
-   */
   const unsigned char *cp;
   cp = buf = tor_malloc(len);
   memcpy(buf,str,len);
@@ -1249,6 +1246,32 @@ crypto_pk_get_digest(crypto_pk_env_t *pk, char *digest_out)
   return 0;
 }
 
+/** Compute all digests of the DER encoding of <b>pk</b>, and store them
+ * in <b>digests_out</b>.  Return 0 on success, -1 on failure. */
+int
+crypto_pk_get_all_digests(crypto_pk_env_t *pk, digests_t *digests_out)
+{
+  unsigned char *buf, *bufp;
+  int len;
+
+  len = i2d_RSAPublicKey(pk->key, NULL);
+  if (len < 0)
+    return -1;
+  buf = bufp = tor_malloc(len+1);
+  len = i2d_RSAPublicKey(pk->key, &bufp);
+  if (len < 0) {
+    crypto_log_errors(LOG_WARN,"encoding public key");
+    tor_free(buf);
+    return -1;
+  }
+  if (crypto_digest_all(digests_out, (char*)buf, len) < 0) {
+    tor_free(buf);
+    return -1;
+  }
+  tor_free(buf);
+  return 0;
+}
+
 /** Copy <b>in</b> to the <b>outlen</b>-byte buffer <b>out</b>, adding spaces
  * every four spaces. */
 /* static */ void
@@ -1714,6 +1737,74 @@ crypto_hmac_sha1(char *hmac_out,
        (unsigned char*)hmac_out, NULL);
 }
 
+/** Compute the HMAC-SHA-256 of the <b>msg_len</b> bytes in <b>msg</b>, using
+ * the <b>key</b> of length <b>key_len</b>.  Store the DIGEST_LEN-byte result
+ * in <b>hmac_out</b>.
+ */
+void
+crypto_hmac_sha256(char *hmac_out,
+                   const char *key, size_t key_len,
+                   const char *msg, size_t msg_len)
+{
+#if (OPENSSL_VERSION_NUMBER >= 0x00908000l)
+  /* If we've got OpenSSL >=0.9.8 we can use its hmac implementation. */
+  tor_assert(key_len < INT_MAX);
+  tor_assert(msg_len < INT_MAX);
+  HMAC(EVP_sha256(), key, (int)key_len, (unsigned char*)msg, (int)msg_len,
+       (unsigned char*)hmac_out, NULL);
+#else
+  /* OpenSSL doesn't have an EVP implementation for SHA256. We'll need
+     to do HMAC on our own.
+
+     HMAC isn't so hard: To compute HMAC(key, msg):
+      1. If len(key) > blocksize, key = H(key).
+      2. If len(key) < blocksize, right-pad key up to blocksize with 0 bytes.
+      3. let ipad = key xor 0x363636363636....36
+         let opad = key xor 0x5c5c5c5c5c5c....5c
+         The result is H(opad | H( ipad | msg ) )
+  */
+#define BLOCKSIZE 64
+#define DIGESTSIZE 32
+  uint8_t k[BLOCKSIZE];
+  uint8_t pad[BLOCKSIZE];
+  uint8_t d[DIGESTSIZE];
+  int i;
+  SHA256_CTX st;
+
+  tor_assert(key_len < INT_MAX);
+  tor_assert(msg_len < INT_MAX);
+
+  if (key_len <= BLOCKSIZE) {
+    memset(k, 0, sizeof(k));
+    memcpy(k, key, key_len); /* not time invariant in key_len */
+  } else {
+    SHA256((const uint8_t *)key, key_len, k);
+    memset(k+DIGESTSIZE, 0, sizeof(k)-DIGESTSIZE);
+  }
+  for (i = 0; i < BLOCKSIZE; ++i)
+    pad[i] = k[i] ^ 0x36;
+  SHA256_Init(&st);
+  SHA256_Update(&st, pad, BLOCKSIZE);
+  SHA256_Update(&st, (uint8_t*)msg, msg_len);
+  SHA256_Final(d, &st);
+
+  for (i = 0; i < BLOCKSIZE; ++i)
+    pad[i] = k[i] ^ 0x5c;
+  SHA256_Init(&st);
+  SHA256_Update(&st, pad, BLOCKSIZE);
+  SHA256_Update(&st, d, DIGESTSIZE);
+  SHA256_Final((uint8_t*)hmac_out, &st);
+
+  /* Now clear everything. */
+  memset(k, 0, sizeof(k));
+  memset(pad, 0, sizeof(pad));
+  memset(d, 0, sizeof(d));
+  memset(&st, 0, sizeof(st));
+#undef BLOCKSIZE
+#undef DIGESTSIZE
+#endif
+}
+
 /* DH */
 
 /** Shared P parameter for our circuit-crypto DH key exchanges. */
diff --git a/src/common/crypto.h b/src/common/crypto.h
index 9b4eee622..80c10296a 100644
--- a/src/common/crypto.h
+++ b/src/common/crypto.h
@@ -150,6 +150,7 @@ int crypto_pk_private_hybrid_decrypt(crypto_pk_env_t *env, char *to,
 int crypto_pk_asn1_encode(crypto_pk_env_t *pk, char *dest, size_t dest_len);
 crypto_pk_env_t *crypto_pk_asn1_decode(const char *str, size_t len);
 int crypto_pk_get_digest(crypto_pk_env_t *pk, char *digest_out);
+int crypto_pk_get_all_digests(crypto_pk_env_t *pk, digests_t *digests_out);
 int crypto_pk_get_fingerprint(crypto_pk_env_t *pk, char *fp_out,int add_space);
 int crypto_pk_check_fingerprint_syntax(const char *s);
 
@@ -195,6 +196,9 @@ void crypto_digest_assign(crypto_digest_env_t *into,
 void crypto_hmac_sha1(char *hmac_out,
                       const char *key, size_t key_len,
                       const char *msg, size_t msg_len);
+void crypto_hmac_sha256(char *hmac_out,
+                        const char *key, size_t key_len,
+                        const char *msg, size_t msg_len);
 
 /* Key negotiation */
 #define DH_TYPE_CIRCUIT 1
diff --git a/src/common/tortls.c b/src/common/tortls.c
index 1bb9c74ef..9a3c02b5b 100644
--- a/src/common/tortls.c
+++ b/src/common/tortls.c
@@ -97,15 +97,27 @@ static int use_unsafe_renegotiation_op = 0;
  * SSL3_FLAGS_ALLOW_UNSAFE_LEGACY_RENEGOTIATION? */
 static int use_unsafe_renegotiation_flag = 0;
 
+/** Structure that we use for a single certificate. */
+struct tor_cert_t {
+  X509 *cert;
+  uint8_t *encoded;
+  size_t encoded_len;
+  unsigned pkey_digests_set : 1;
+  digests_t cert_digests;
+  digests_t pkey_digests;
+};
+
 /** Holds a SSL_CTX object and related state used to configure TLS
  * connections.
  */
 typedef struct tor_tls_context_t {
   int refcnt;
   SSL_CTX *ctx;
-  X509 *my_cert;
-  X509 *my_id_cert;
-  crypto_pk_env_t *key;
+  tor_cert_t *my_link_cert;
+  tor_cert_t *my_id_cert;
+  tor_cert_t *my_auth_cert;
+  crypto_pk_env_t *link_key;
+  crypto_pk_env_t *auth_key;
 } tor_tls_context_t;
 
 #define TOR_TLS_MAGIC 0x71571571
@@ -198,6 +210,7 @@ static int tor_tls_context_init_one(tor_tls_context_t **ppcontext,
                                     unsigned int key_lifetime);
 static tor_tls_context_t *tor_tls_context_new(crypto_pk_env_t *identity,
                                               unsigned int key_lifetime);
+static int check_cert_lifetime_internal(const X509 *cert, int tolerance);
 
 /** Global TLS contexts. We keep them here because nobody else needs
  * to touch them. */
@@ -670,6 +683,137 @@ static const int N_CLIENT_CIPHERS =
                              SSL3_TXT_EDH_RSA_DES_192_CBC3_SHA)
 #endif
 
+/** Free all storage held in <b>cert</b> */
+void
+tor_cert_free(tor_cert_t *cert)
+{
+  if (! cert)
+    return;
+  if (cert->cert)
+    X509_free(cert->cert);
+  tor_free(cert->encoded);
+  memset(cert, 0x03, sizeof(cert));
+  tor_free(cert);
+}
+
+/**
+ * Allocate a new tor_cert_t to hold the certificate "x509_cert".
+ *
+ * Steals a reference to x509_cert.
+ */
+static tor_cert_t *
+tor_cert_new(X509 *x509_cert)
+{
+  tor_cert_t *cert;
+  EVP_PKEY *pkey;
+  RSA *rsa;
+  int length, length2;
+  unsigned char *cp;
+
+  if (!x509_cert)
+    return NULL;
+
+  length = i2d_X509(x509_cert, NULL);
+  cert = tor_malloc_zero(sizeof(tor_cert_t));
+  if (length <= 0) {
+    tor_free(cert);
+    log_err(LD_CRYPTO, "Couldn't get length of encoded x509 certificate");
+    X509_free(x509_cert);
+    return NULL;
+  }
+  cert->encoded_len = (size_t) length;
+  cp = cert->encoded = tor_malloc(length);
+  length2 = i2d_X509(x509_cert, &cp);
+  tor_assert(length2 == length);
+
+  cert->cert = x509_cert;
+
+  crypto_digest_all(&cert->cert_digests,
+                    (char*)cert->encoded, cert->encoded_len);
+
+  if ((pkey = X509_get_pubkey(x509_cert)) &&
+      (rsa = EVP_PKEY_get1_RSA(pkey))) {
+    crypto_pk_env_t *pk = _crypto_new_pk_env_rsa(rsa);
+    crypto_pk_get_all_digests(pk, &cert->pkey_digests);
+    cert->pkey_digests_set = 1;
+    crypto_free_pk_env(pk);
+    EVP_PKEY_free(pkey);
+  }
+
+  return cert;
+}
+
+/** Read a DER-encoded X509 cert, of length exactly <b>certificate_len</b>,
+ * from a <b>certificate</b>.  Return a newly allocated tor_cert_t on success
+ * and NULL on failure. */
+tor_cert_t *
+tor_cert_decode(const uint8_t *certificate, size_t certificate_len)
+{
+  X509 *x509;
+  const unsigned char *cp = (const unsigned char *)certificate;
+  tor_cert_t *newcert;
+  tor_assert(certificate);
+
+  if (certificate_len > INT_MAX)
+    return NULL;
+
+#if OPENSSL_VERSION_NUMBER < 0x00908000l
+  /* This ifdef suppresses a type warning.  Take out this case once everybody
+   * is using OpenSSL 0.9.8 or later. */
+  x509 = d2i_X509(NULL, (unsigned char**)&cp, (int)certificate_len);
+#else
+  x509 = d2i_X509(NULL, &cp, (int)certificate_len);
+#endif
+  if (!x509)
+    return NULL; /* Couldn't decode */
+  if (cp - certificate != (int)certificate_len) {
+    X509_free(x509);
+    return NULL; /* Didn't use all the bytes */
+  }
+  newcert = tor_cert_new(x509);
+  if (!newcert) {
+    return NULL;
+  }
+  if (newcert->encoded_len != certificate_len ||
+      fast_memneq(newcert->encoded, certificate, certificate_len)) {
+    /* Cert wasn't in DER */
+    tor_cert_free(newcert);
+    return NULL;
+  }
+  return newcert;
+}
+
+/** Set *<b>encoded_out</b> and *<b>size_out/b> to <b>cert</b>'s encoded DER
+ * representation and length, respectively. */
+void
+tor_cert_get_der(const tor_cert_t *cert,
+                 const uint8_t **encoded_out, size_t *size_out)
+{
+  tor_assert(cert);
+  tor_assert(encoded_out);
+  tor_assert(size_out);
+  *encoded_out = cert->encoded;
+  *size_out = cert->encoded_len;
+}
+
+/** Return a set of digests for the public key in <b>cert</b>, or NULL if this
+ * cert's public key is not one we know how to take the digest of. */
+const digests_t *
+tor_cert_get_id_digests(const tor_cert_t *cert)
+{
+  if (cert->pkey_digests_set)
+    return &cert->pkey_digests;
+  else
+    return NULL;
+}
+
+/** Return a set of digests for the public key in <b>cert</b>. */
+const digests_t *
+tor_cert_get_cert_digests(const tor_cert_t *cert)
+{
+  return &cert->cert_digests;
+}
+
 /** Remove a reference to <b>ctx</b>, and free it if it has no more
  * references. */
 static void
@@ -678,13 +822,171 @@ tor_tls_context_decref(tor_tls_context_t *ctx)
   tor_assert(ctx);
   if (--ctx->refcnt == 0) {
     SSL_CTX_free(ctx->ctx);
-    X509_free(ctx->my_cert);
-    X509_free(ctx->my_id_cert);
-    crypto_free_pk_env(ctx->key);
+    tor_cert_free(ctx->my_link_cert);
+    tor_cert_free(ctx->my_id_cert);
+    tor_cert_free(ctx->my_auth_cert);
+    crypto_free_pk_env(ctx->link_key);
+    crypto_free_pk_env(ctx->auth_key);
     tor_free(ctx);
   }
 }
 
+/** Set *<b>link_cert_out</b> and *<b>id_cert_out</b> to the link certificate
+ * and ID certificate that we're currently using for our V3 in-protocol
+ * handshake's certificate chain.  If <b>server</b> is true, provide the certs
+ * that we use in server mode; otherwise, provide the certs that we use in
+ * client mode. */
+int
+tor_tls_get_my_certs(int server,
+                     const tor_cert_t **link_cert_out,
+                     const tor_cert_t **id_cert_out)
+{
+  tor_tls_context_t *ctx = server ? server_tls_context : client_tls_context;
+  if (! ctx)
+    return -1;
+  if (link_cert_out)
+    *link_cert_out = server ? ctx->my_link_cert : ctx->my_auth_cert;
+  if (id_cert_out)
+    *id_cert_out = ctx->my_id_cert;
+  return 0;
+}
+
+/**
+ * Return the authentication key that we use to authenticate ourselves as a
+ * client in the V3 in-protocol handshake.
+ */
+crypto_pk_env_t *
+tor_tls_get_my_client_auth_key(void)
+{
+  if (! client_tls_context)
+    return NULL;
+  return client_tls_context->auth_key;
+}
+
+/**
+ * Return the public key that a cetificate certifies.  Return NULL if the
+ * cert's key is not RSA.
+ */
+crypto_pk_env_t *
+tor_tls_cert_get_key(tor_cert_t *cert)
+{
+  crypto_pk_env_t *result = NULL;
+  EVP_PKEY *pkey = X509_get_pubkey(cert->cert);
+  RSA *rsa;
+  if (!pkey)
+    return NULL;
+  rsa = EVP_PKEY_get1_RSA(pkey);
+  if (!rsa) {
+    EVP_PKEY_free(pkey);
+    return NULL;
+  }
+  result = _crypto_new_pk_env_rsa(rsa);
+  EVP_PKEY_free(pkey);
+  return result;
+}
+
+/** Return true iff <b>a</b> and <b>b</b> represent the same public key. */
+static int
+pkey_eq(EVP_PKEY *a, EVP_PKEY *b)
+{
+  /* We'd like to do this, but openssl 0.9.7 doesn't have it:
+     return EVP_PKEY_cmp(a,b) == 1;
+  */
+  unsigned char *a_enc=NULL, *b_enc=NULL, *a_ptr, *b_ptr;
+  int a_len1, b_len1, a_len2, b_len2, result;
+  a_len1 = i2d_PublicKey(a, NULL);
+  b_len1 = i2d_PublicKey(b, NULL);
+  if (a_len1 != b_len1)
+    return 0;
+  a_ptr = a_enc = tor_malloc(a_len1);
+  b_ptr = b_enc = tor_malloc(b_len1);
+  a_len2 = i2d_PublicKey(a, &a_ptr);
+  b_len2 = i2d_PublicKey(b, &b_ptr);
+  tor_assert(a_len2 == a_len1);
+  tor_assert(b_len2 == b_len1);
+  result = tor_memeq(a_enc, b_enc, a_len1);
+  tor_free(a_enc);
+  tor_free(b_enc);
+  return result;
+}
+
+/** Return true iff the other side of <b>tls</b> has authenticated to us, and
+ * the key certified in <b>cert</b> is the same as the key they used to do it.
+ */
+int
+tor_tls_cert_matches_key(const tor_tls_t *tls, const tor_cert_t *cert)
+{
+  X509 *peercert = SSL_get_peer_certificate(tls->ssl);
+  EVP_PKEY *link_key = NULL, *cert_key = NULL;
+  int result;
+
+  if (!peercert)
+    return 0;
+  link_key = X509_get_pubkey(peercert);
+  cert_key = X509_get_pubkey(cert->cert);
+
+  result = link_key && cert_key && pkey_eq(cert_key, link_key);
+
+  X509_free(peercert);
+  if (link_key)
+    EVP_PKEY_free(link_key);
+  if (cert_key)
+    EVP_PKEY_free(cert_key);
+
+  return result;
+}
+
+/** Check whether <b>cert</b> is well-formed, currently live, and correctly
+ * signed by the public key in <b>signing_cert</b>.  If <b>check_rsa_1024</b>,
+ * make sure that it has an RSA key with 1024 bits; otherwise, just check that
+ * the key is long enough. Return 1 if the cert is good, and 0 if it's bad or
+ * we couldn't check it. */
+int
+tor_tls_cert_is_valid(const tor_cert_t *cert,
+                      const tor_cert_t *signing_cert,
+                      int check_rsa_1024)
+{
+  EVP_PKEY *cert_key;
+  EVP_PKEY *signing_key = X509_get_pubkey(signing_cert->cert);
+  int r, key_ok = 0;
+  if (!signing_key)
+    return 0;
+  r = X509_verify(cert->cert, signing_key);
+  EVP_PKEY_free(signing_key);
+  if (r <= 0)
+    return 0;
+
+  /* okay, the signature checked out right.  Now let's check the check the
+   * lifetime. */
+  /*XXXX tolerance might be iffy here */
+  if (check_cert_lifetime_internal(cert->cert, 60*60) < 0)
+    return 0;
+
+  cert_key = X509_get_pubkey(cert->cert);
+  if (check_rsa_1024 && cert_key) {
+    RSA *rsa = EVP_PKEY_get1_RSA(cert_key);
+    if (rsa && BN_num_bits(rsa->n) == 1024)
+      key_ok = 1;
+    if (rsa)
+      RSA_free(rsa);
+  } else if (cert_key) {
+    int min_bits = 1024;
+#ifdef EVP_PKEY_EC
+    if (EVP_PKEY_type(cert_key->type) == EVP_PKEY_EC)
+      min_bits = 128;
+#endif
+    if (EVP_PKEY_bits(cert_key) >= min_bits)
+      key_ok = 1;
+  }
+  EVP_PKEY_free(cert_key);
+  if (!key_ok)
+    return 0;
+
+  /* XXXX compare DNs or anything? */
+
+  return 1;
+}
+
 /** Increase the reference count of <b>ctx</b>. */
 static void
 tor_tls_context_incref(tor_tls_context_t *ctx)
@@ -785,37 +1087,54 @@ tor_tls_context_init_one(tor_tls_context_t **ppcontext,
 static tor_tls_context_t *
 tor_tls_context_new(crypto_pk_env_t *identity, unsigned int key_lifetime)
 {
-  crypto_pk_env_t *rsa = NULL;
+  crypto_pk_env_t *rsa = NULL, *rsa_auth = NULL;
   EVP_PKEY *pkey = NULL;
   tor_tls_context_t *result = NULL;
-  X509 *cert = NULL, *idcert = NULL;
+  X509 *cert = NULL, *idcert = NULL, *authcert = NULL;
   char *nickname = NULL, *nn2 = NULL;
 
   tor_tls_init();
   nickname = crypto_random_hostname(8, 20, "www.", ".net");
+#ifdef DISABLE_V3_LINKPROTO_SERVERSIDE
   nn2 = crypto_random_hostname(8, 20, "www.", ".net");
+#else
+  nn2 = crypto_random_hostname(8, 20, "www.", ".com");
+#endif
 
-  /* Generate short-term RSA key. */
+  /* Generate short-term RSA key for use with TLS. */
   if (!(rsa = crypto_new_pk_env()))
     goto error;
   if (crypto_pk_generate_key(rsa)<0)
     goto error;
-  /* Create certificate signed by identity key. */
+  /* Generate short-term RSA key for use in the in-protocol ("v3")
+   * authentication handshake. */
+  if (!(rsa_auth = crypto_new_pk_env()))
+    goto error;
+  if (crypto_pk_generate_key(rsa_auth)<0)
+    goto error;
+  /* Create a link certificate signed by identity key. */
   cert = tor_tls_create_certificate(rsa, identity, nickname, nn2,
                                     key_lifetime);
   /* Create self-signed certificate for identity key. */
   idcert = tor_tls_create_certificate(identity, identity, nn2, nn2,
                                       IDENTITY_CERT_LIFETIME);
-  if (!cert || !idcert) {
+  /* Create an authentication certificate signed by identity key. */
+  authcert = tor_tls_create_certificate(rsa_auth, identity, nickname, nn2,
+                                        key_lifetime);
+  if (!cert || !idcert || !authcert) {
     log(LOG_WARN, LD_CRYPTO, "Error creating certificate");
     goto error;
   }
 
   result = tor_malloc_zero(sizeof(tor_tls_context_t));
   result->refcnt = 1;
-  result->my_cert = X509_dup(cert);
-  result->my_id_cert = X509_dup(idcert);
-  result->key = crypto_pk_dup_key(rsa);
+  result->my_link_cert = tor_cert_new(X509_dup(cert));
+  result->my_id_cert = tor_cert_new(X509_dup(idcert));
+  result->my_auth_cert = tor_cert_new(X509_dup(authcert));
+  if (!result->my_link_cert || !result->my_id_cert || !result->my_auth_cert)
+    goto error;
+  result->link_key = crypto_pk_dup_key(rsa);
+  result->auth_key = crypto_pk_dup_key(rsa_auth);
 
 #ifdef EVERYONE_HAS_AES
   /* Tell OpenSSL to only use TLS1 */
@@ -881,6 +1200,9 @@ tor_tls_context_new(crypto_pk_env_t *identity, unsigned int key_lifetime)
 
   if (rsa)
     crypto_free_pk_env(rsa);
+  if (rsa_auth)
+    crypto_free_pk_env(rsa_auth);
+  X509_free(authcert);
   tor_free(nickname);
   tor_free(nn2);
   return result;
@@ -893,12 +1215,16 @@ tor_tls_context_new(crypto_pk_env_t *identity, unsigned int key_lifetime)
     EVP_PKEY_free(pkey);
   if (rsa)
     crypto_free_pk_env(rsa);
+  if (rsa_auth)
+    crypto_free_pk_env(rsa_auth);
   if (result)
     tor_tls_context_decref(result);
   if (cert)
     X509_free(cert);
   if (idcert)
     X509_free(idcert);
+  if (authcert)
+    X509_free(authcert);
   return NULL;
 }
 
@@ -1569,9 +1895,21 @@ tor_tls_peer_has_cert(tor_tls_t *tls)
   return 1;
 }
 
+/** Return the peer certificate, or NULL if there isn't one. */
+tor_cert_t *
+tor_tls_get_peer_cert(tor_tls_t *tls)
+{
+  X509 *cert;
+  cert = SSL_get_peer_certificate(tls->ssl);
+  tls_log_errors(tls, LOG_WARN, LD_HANDSHAKE, "getting peer certificate");
+  if (!cert)
+    return NULL;
+  return tor_cert_new(cert);
+}
+
 /** Warn that a certificate lifetime extends through a certain range. */
 static void
-log_cert_lifetime(X509 *cert, const char *problem)
+log_cert_lifetime(const X509 *cert, const char *problem)
 {
   BIO *bio = NULL;
   BUF_MEM *buf;
@@ -1718,25 +2056,14 @@ tor_tls_verify(int severity, tor_tls_t *tls, crypto_pk_env_t **identity_key)
 int
 tor_tls_check_lifetime(tor_tls_t *tls, int tolerance)
 {
-  time_t now, t;
   X509 *cert;
   int r = -1;
 
-  now = time(NULL);
-
   if (!(cert = SSL_get_peer_certificate(tls->ssl)))
     goto done;
 
-  t = now + tolerance;
-  if (X509_cmp_time(X509_get_notBefore(cert), &t) > 0) {
-    log_cert_lifetime(cert, "not yet valid");
+  if (check_cert_lifetime_internal(cert, tolerance) < 0)
     goto done;
-  }
-  t = now - tolerance;
-  if (X509_cmp_time(X509_get_notAfter(cert), &t) < 0) {
-    log_cert_lifetime(cert, "already expired");
-    goto done;
-  }
 
   r = 0;
  done:
@@ -1748,6 +2075,30 @@ tor_tls_check_lifetime(tor_tls_t *tls, int tolerance)
   return r;
 }
 
+/** Helper: check whether <b>cert</b> is currently live, give or take
+ * <b>tolerance</b> seconds.  If it is live, return 0.  If it is not live,
+ * log a message and return -1. */
+static int
+check_cert_lifetime_internal(const X509 *cert, int tolerance)
+{
+  time_t now, t;
+
+  now = time(NULL);
+
+  t = now + tolerance;
+  if (X509_cmp_time(X509_get_notBefore(cert), &t) > 0) {
+    log_cert_lifetime(cert, "not yet valid");
+    return -1;
+  }
+  t = now - tolerance;
+  if (X509_cmp_time(X509_get_notAfter(cert), &t) < 0) {
+    log_cert_lifetime(cert, "already expired");
+    return -1;
+  }
+
+  return 0;
+}
+
 /** Return the number of bytes available for reading from <b>tls</b>.
  */
 int
@@ -1831,6 +2182,82 @@ tor_tls_used_v1_handshake(tor_tls_t *tls)
   return 1;
 }
 
+/** Return true iff <b>name</b> is a DN of a kind that could only
+ * occur in a v3-handshake-indicating certificate */
+static int
+dn_indicates_v3_cert(X509_NAME *name)
+{
+#ifdef DISABLE_V3_LINKPROTO_CLIENTSIDE
+  (void)name;
+  return 0;
+#else
+  X509_NAME_ENTRY *entry;
+  int n_entries;
+  ASN1_OBJECT *obj;
+  ASN1_STRING *str;
+  unsigned char *s;
+  int len, r;
+
+  n_entries = X509_NAME_entry_count(name);
+  if (n_entries != 1)
+    return 1; /* More than one entry in the DN. */
+  entry = X509_NAME_get_entry(name, 0);
+
+  obj = X509_NAME_ENTRY_get_object(entry);
+  if (OBJ_obj2nid(obj) != OBJ_txt2nid("commonName"))
+    return 1; /* The entry isn't a commonName. */
+
+  str = X509_NAME_ENTRY_get_data(entry);
+  len = ASN1_STRING_to_UTF8(&s, str);
+  if (len < 0)
+    return 0;
+  r = fast_memneq(s + len - 4, ".net", 4);
+  OPENSSL_free(s);
+  return r;
+#endif
+}
+
+/** Return true iff the peer certificate we're received on <b>tls</b>
+ * indicates that this connection should use the v3 (in-protocol)
+ * authentication handshake.
+ *
+ * Only the connection initiator should use this, and only once the initial
+ * handshake is done; the responder detects a v1 handshake by cipher types,
+ * and a v3/v2 handshake by Versions cell vs renegotiation.
+ */
+int
+tor_tls_received_v3_certificate(tor_tls_t *tls)
+{
+  X509 *cert = SSL_get_peer_certificate(tls->ssl);
+  EVP_PKEY *key;
+  X509_NAME *issuer_name, *subject_name;
+
+  if (!cert) {
+    log_warn(LD_BUG, "Called on a connection with no peer certificate");
+    return 0;
+  }
+
+  subject_name = X509_get_subject_name(cert);
+  issuer_name = X509_get_issuer_name(cert);
+
+  if (X509_name_cmp(subject_name, issuer_name) == 0)
+    return 1; /* purportedly self signed */
+
+  if (dn_indicates_v3_cert(subject_name) ||
+      dn_indicates_v3_cert(issuer_name))
+    return 1; /* DN is fancy */
+
+  key = X509_get_pubkey(cert);
+  if (EVP_PKEY_bits(key) != 1024 ||
+      EVP_PKEY_type(key->type) != EVP_PKEY_RSA) {
+    EVP_PKEY_free(key);
+    return 1; /* Key is fancy */
+  }
+
+  EVP_PKEY_free(key);
+  return 0;
+}
+
 /** Return the number of server handshakes that we've noticed doing on
  * <b>tls</b>. */
 int
@@ -1847,6 +2274,36 @@ tor_tls_server_got_renegotiate(tor_tls_t *tls)
   return tls->got_renegotiate;
 }
 
+/** Set the DIGEST256_LEN buffer at <b>secrets_out</b> to the value used in
+ * the v3 handshake to prove that the client knows the TLS secrets for the
+ * connection <b>tls</b>.  Return 0 on success, -1 on failure.
+ */
+int
+tor_tls_get_tlssecrets(tor_tls_t *tls, uint8_t *secrets_out)
+{
+#define TLSSECRET_MAGIC "Tor V3 handshake TLS cross-certification"
+  char buf[128];
+  size_t len;
+  tor_assert(tls);
+  tor_assert(tls->ssl);
+  tor_assert(tls->ssl->s3);
+  tor_assert(tls->ssl->session);
+  /*
+    The value is an HMAC, using the TLS master key as the HMAC key, of
+    client_random | server_random | TLSSECRET_MAGIC
+  */
+  memcpy(buf +  0, tls->ssl->s3->client_random, 32);
+  memcpy(buf + 32, tls->ssl->s3->server_random, 32);
+  memcpy(buf + 64, TLSSECRET_MAGIC, strlen(TLSSECRET_MAGIC) + 1);
+  len = 64 + strlen(TLSSECRET_MAGIC) + 1;
+  crypto_hmac_sha256((char*)secrets_out,
+                     (char*)tls->ssl->session->master_key,
+                     tls->ssl->session->master_key_length,
+                     buf, len);
+  memset(buf, 0, sizeof(buf));
+  return 0;
+}
+
 /** Examine the amount of memory used and available for buffers in <b>tls</b>.
  * Set *<b>rbuf_capacity</b> to the amount of storage allocated for the read
  * buffer and *<b>rbuf_bytes</b> to the amount actually used.
diff --git a/src/common/tortls.h b/src/common/tortls.h
index 9b8108b42..90e76e4a9 100644
--- a/src/common/tortls.h
+++ b/src/common/tortls.h
@@ -17,6 +17,9 @@
 /* Opaque structure to hold a TLS connection. */
 typedef struct tor_tls_t tor_tls_t;
 
+/* Opaque structure to hold an X509 certificate. */
+typedef struct tor_cert_t tor_cert_t;
+
 /* Possible return values for most tor_tls_* functions. */
 #define _MIN_TOR_TLS_ERROR_VAL     -9
 #define TOR_TLS_ERROR_MISC         -9
@@ -63,6 +66,7 @@ void tor_tls_set_renegotiate_callback(tor_tls_t *tls,
 int tor_tls_is_server(tor_tls_t *tls);
 void tor_tls_free(tor_tls_t *tls);
 int tor_tls_peer_has_cert(tor_tls_t *tls);
+tor_cert_t *tor_tls_get_peer_cert(tor_tls_t *tls);
 int tor_tls_verify(int severity, tor_tls_t *tls, crypto_pk_env_t **identity);
 int tor_tls_check_lifetime(tor_tls_t *tls, int tolerance);
 int tor_tls_read(tor_tls_t *tls, char *cp, size_t len);
@@ -85,8 +89,10 @@ void tor_tls_get_buffer_sizes(tor_tls_t *tls,
                               size_t *wbuf_capacity, size_t *wbuf_bytes);
 
 int tor_tls_used_v1_handshake(tor_tls_t *tls);
+int tor_tls_received_v3_certificate(tor_tls_t *tls);
 int tor_tls_get_num_server_handshakes(tor_tls_t *tls);
 int tor_tls_server_got_renegotiate(tor_tls_t *tls);
+int tor_tls_get_tlssecrets(tor_tls_t *tls, uint8_t *secrets_out);
 
 /* Log and abort if there are unhandled TLS errors in OpenSSL's error stack.
  */
@@ -104,5 +110,21 @@ struct bufferevent *tor_tls_init_bufferevent(tor_tls_t *tls,
                                      int filter);
 #endif
 
+void tor_cert_free(tor_cert_t *cert);
+tor_cert_t *tor_cert_decode(const uint8_t *certificate, size_t certificate_len);
+void tor_cert_get_der(const tor_cert_t *cert,
+                      const uint8_t **encoded_out, size_t *size_out);
+const digests_t *tor_cert_get_id_digests(const tor_cert_t *cert);
+const digests_t *tor_cert_get_cert_digests(const tor_cert_t *cert);
+int tor_tls_get_my_certs(int server,
+                         const tor_cert_t **link_cert_out,
+                         const tor_cert_t **id_cert_out);
+crypto_pk_env_t *tor_tls_get_my_client_auth_key(void);
+crypto_pk_env_t *tor_tls_cert_get_key(tor_cert_t *cert);
+int tor_tls_cert_matches_key(const tor_tls_t *tls, const tor_cert_t *cert);
+int tor_tls_cert_is_valid(const tor_cert_t *cert,
+                          const tor_cert_t *signing_cert,
+                          int check_rsa_1024);
+
 #endif
 
diff --git a/src/or/buffers.c b/src/or/buffers.c
index 1025cedad..c589fbaef 100644
--- a/src/or/buffers.c
+++ b/src/or/buffers.c
@@ -1005,6 +1005,32 @@ fetch_from_buf(char *string, size_t string_len, buf_t *buf)
   return (int)buf->datalen;
 }
 
+/** True iff the cell command <b>command</b> is one that implies a variable-length
+ * cell in Tor link protocol <b>linkproto</b>. */
+static inline int
+cell_command_is_var_length(uint8_t command, int linkproto)
+{
+  /* If linkproto is v2 (2), CELL_VERSIONS is the only variable-length cells work as
+   * implemented here. If it's 1, there are no variable-length cells.  Tor
+   * does not support other versions right now, and so can't negotiate them.
+   */
+  switch (linkproto) {
+  case 1:
+    /* Link protocol version 1 has no variable-length cells. */
+    return 0;
+  case 2:
+    /* In link protocol version 2, VERSIONS is the only variable-length cell */
+    return command == CELL_VERSIONS;
+  case 0:
+  case 3:
+  default:
+    /* In link protocol version 3 and later, and in version "unknown",
+     * commands 128 and higher indicate variable-length. VERSIONS is
+     * grandfathered in. */
+    return command == CELL_VERSIONS || command >= 128;
+  }
+}
+
 /** Check <b>buf</b> for a variable-length cell according to the rules of link
  * protocol version <b>linkproto</b>.  If one is found, pull it off the buffer
  * and assign a newly allocated var_cell_t to *<b>out</b>, and return 1.
@@ -1019,12 +1045,6 @@ fetch_var_cell_from_buf(buf_t *buf, var_cell_t **out, int linkproto)
   var_cell_t *result;
   uint8_t command;
   uint16_t length;
-  /* If linkproto is unknown (0) or v2 (2), variable-length cells work as
-   * implemented here. If it's 1, there are no variable-length cells.  Tor
-   * does not support other versions right now, and so can't negotiate them.
-   */
-  if (linkproto == 1)
-    return 0;
   check();
   *out = NULL;
   if (buf->datalen < VAR_CELL_HEADER_SIZE)
@@ -1032,7 +1052,7 @@ fetch_var_cell_from_buf(buf_t *buf, var_cell_t **out, int linkproto)
   peek_from_buf(hdr, sizeof(hdr), buf);
 
   command = get_uint8(hdr+2);
-  if (!(CELL_COMMAND_IS_VAR_LENGTH(command)))
+  if (!(cell_command_is_var_length(command, linkproto)))
     return 0;
 
   length = ntohs(get_uint16(hdr+3));
@@ -1101,8 +1121,6 @@ fetch_var_cell_from_evbuffer(struct evbuffer *buf, var_cell_t **out,
   uint16_t cell_length;
   var_cell_t *cell;
   int result = 0;
-  if (linkproto == 1)
-    return 0;
 
   *out = NULL;
   buf_len = evbuffer_get_length(buf);
@@ -1113,7 +1131,7 @@ fetch_var_cell_from_evbuffer(struct evbuffer *buf, var_cell_t **out,
   tor_assert(n >= VAR_CELL_HEADER_SIZE);
 
   command = get_uint8(hdr+2);
-  if (!(CELL_COMMAND_IS_VAR_LENGTH(command))) {
+  if (!(cell_command_is_var_length(command, linkproto))) {
     goto done;
   }
 
diff --git a/src/or/command.c b/src/or/command.c
index d24373eec..a51115631 100644
--- a/src/or/command.c
+++ b/src/or/command.c
@@ -46,6 +46,15 @@ uint64_t stats_n_versions_cells_processed = 0;
 /** How many CELL_NETINFO cells have we received, ever? */
 uint64_t stats_n_netinfo_cells_processed = 0;
 
+/** How many CELL_VPADDING cells have we received, ever? */
+uint64_t stats_n_vpadding_cells_processed = 0;
+/** How many CELL_CERTS cells have we received, ever? */
+uint64_t stats_n_cert_cells_processed = 0;
+/** How many CELL_AUTH_CHALLENGE cells have we received, ever? */
+uint64_t stats_n_auth_challenge_cells_processed = 0;
+/** How many CELL_AUTHENTICATE cells have we received, ever? */
+uint64_t stats_n_authenticate_cells_processed = 0;
+
 /* These are the main functions for processing cells */
 static void command_process_create_cell(cell_t *cell, or_connection_t *conn);
 static void command_process_created_cell(cell_t *cell, or_connection_t *conn);
@@ -54,6 +63,12 @@ static void command_process_destroy_cell(cell_t *cell, or_connection_t *conn);
 static void command_process_versions_cell(var_cell_t *cell,
                                           or_connection_t *conn);
 static void command_process_netinfo_cell(cell_t *cell, or_connection_t *conn);
+static void command_process_cert_cell(var_cell_t *cell,
+                                      or_connection_t *conn);
+static void command_process_auth_challenge_cell(var_cell_t *cell,
+                                          or_connection_t *conn);
+static void command_process_authenticate_cell(var_cell_t *cell,
+                                          or_connection_t *conn);
 
 #ifdef KEEP_TIMING_STATS
 /** This is a wrapper function around the actual function that processes the
@@ -93,7 +108,7 @@ command_time_process_cell(cell_t *cell, or_connection_t *conn, int *time,
 void
 command_process_cell(cell_t *cell, or_connection_t *conn)
 {
-  int handshaking = (conn->_base.state == OR_CONN_STATE_OR_HANDSHAKING);
+  int handshaking = (conn->_base.state != OR_CONN_STATE_OPEN);
 #ifdef KEEP_TIMING_STATS
   /* how many of each cell have we seen so far this second? needs better
    * name. */
@@ -134,9 +149,18 @@ command_process_cell(cell_t *cell, or_connection_t *conn)
 #endif
 
   /* Reject all but VERSIONS and NETINFO when handshaking. */
+  /* (VERSIONS should actually be impossible; it's variable-length.) */
   if (handshaking && cell->command != CELL_VERSIONS &&
-      cell->command != CELL_NETINFO)
+      cell->command != CELL_NETINFO) {
+    log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
+           "Received unexpected cell command %d in state %s; ignoring it.",
+           (int)cell->command,
+           conn_state_to_string(CONN_TYPE_OR,conn->_base.state));
     return;
+  }
+
+  if (conn->_base.state == OR_CONN_STATE_OR_HANDSHAKING_V3)
+    or_handshake_state_record_cell(conn->handshake_state, cell, 1);
 
   switch (cell->command) {
     case CELL_PADDING:
@@ -206,20 +230,79 @@ command_process_var_cell(var_cell_t *cell, or_connection_t *conn)
   }
 #endif
 
-  /* reject all when not handshaking. */
-  if (conn->_base.state != OR_CONN_STATE_OR_HANDSHAKING)
-    return;
+  switch (conn->_base.state)
+  {
+    case OR_CONN_STATE_OR_HANDSHAKING_V2:
+      if (cell->command != CELL_VERSIONS)
+        return;
+      break;
+    case OR_CONN_STATE_TLS_HANDSHAKING:
+      /* If we're using bufferevents, it's entirely possible for us to
+       * notice "hey, data arrived!" before we notice "hey, the handshake
+       * finished!" And we need to be accepting both at once to handle both
+       * the v2 and v3 handshakes. */
+
+      /* fall through */
+    case OR_CONN_STATE_TLS_SERVER_RENEGOTIATING:
+      if (cell->command != CELL_VERSIONS) {
+        log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
+               "Received a non-VERSIONS cell with command %d in state %s; "
+               "ignoring it.",
+               (int)cell->command,
+               conn_state_to_string(CONN_TYPE_OR,conn->_base.state));
+        return;
+      }
+      break;
+    case OR_CONN_STATE_OR_HANDSHAKING_V3:
+      if (cell->command != CELL_AUTHENTICATE)
+        or_handshake_state_record_var_cell(conn->handshake_state, cell, 1);
+      break; /* Everything is allowed */
+    case OR_CONN_STATE_OPEN:
+      if (conn->link_proto < 3) {
+        log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
+               "Received a variable-length cell with command %d in state %s "
+               "with link protocol %d; ignoring it.",
+               (int)cell->command,
+               conn_state_to_string(CONN_TYPE_OR,conn->_base.state),
+               (int)conn->link_proto);
+        return;
+      }
+      break;
+    default:
+      log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
+             "Received var-length cell with command %d in unexpected state "
+             "%s [%d]; ignoring it.",
+             (int)cell->command,
+             conn_state_to_string(CONN_TYPE_OR,conn->_base.state),
+             (int)conn->_base.state);
+      return;
+  }
 
   switch (cell->command) {
     case CELL_VERSIONS:
       ++stats_n_versions_cells_processed;
       PROCESS_CELL(versions, cell, conn);
       break;
+    case CELL_VPADDING:
+      ++stats_n_vpadding_cells_processed;
+      PROCESS_CELL(versions, cell, conn);
+      break;
+    case CELL_CERT:
+      ++stats_n_cert_cells_processed;
+      PROCESS_CELL(cert, cell, conn);
+      break;
+    case CELL_AUTH_CHALLENGE:
+      ++stats_n_auth_challenge_cells_processed;
+      PROCESS_CELL(auth_challenge, cell, conn);
+      break;
+    case CELL_AUTHENTICATE:
+      ++stats_n_authenticate_cells_processed;
+      PROCESS_CELL(authenticate, cell, conn);
+      break;
     default:
-      log_warn(LD_BUG,
+      log_fn(LOG_INFO, LD_PROTOCOL,
                "Variable-length cell of unknown type (%d) received.",
                cell->command);
-      tor_fragile_assert();
       break;
   }
 }
@@ -505,14 +588,40 @@ command_process_versions_cell(var_cell_t *cell, or_connection_t *conn)
 {
   int highest_supported_version = 0;
   const uint8_t *cp, *end;
+  const int started_here = connection_or_nonopen_was_started_here(conn);
   if (conn->link_proto != 0 ||
-      conn->_base.state != OR_CONN_STATE_OR_HANDSHAKING ||
       (conn->handshake_state && conn->handshake_state->received_versions)) {
     log_fn(LOG_PROTOCOL_WARN, LD_OR,
            "Received a VERSIONS cell on a connection with its version "
            "already set to %d; dropping", (int) conn->link_proto);
     return;
   }
+  switch (conn->_base.state)
+    {
+    case OR_CONN_STATE_OR_HANDSHAKING_V2:
+      break;
+    case OR_CONN_STATE_TLS_HANDSHAKING:
+    case OR_CONN_STATE_TLS_SERVER_RENEGOTIATING:
+      if (started_here) {
+        log_fn(LOG_PROTOCOL_WARN, LD_OR,
+               "Received a versions cell while TLS-handshaking not in "
+               "OR_HANDSHAKING_V3 on a connection we originated.");
+      }
+      conn->_base.state = OR_CONN_STATE_OR_HANDSHAKING_V3;
+      if (connection_init_or_handshake_state(conn, started_here) < 0) {
+        connection_mark_for_close(TO_CONN(conn));
+        return;
+      }
+      or_handshake_state_record_var_cell(conn->handshake_state, cell, 1);
+      break;
+    case OR_CONN_STATE_OR_HANDSHAKING_V3:
+      break;
+    default:
+      log_fn(LOG_PROTOCOL_WARN, LD_OR,
+             "VERSIONS cell while in unexpected state");
+      return;
+  }
+
   tor_assert(conn->handshake_state);
   end = cell->payload + cell->payload_len;
   for (cp = cell->payload; cp+1 < end; ++cp) {
@@ -534,19 +643,87 @@ command_process_versions_cell(var_cell_t *cell, or_connection_t *conn)
            "That's crazily non-compliant. Closing connection.");
     connection_mark_for_close(TO_CONN(conn));
     return;
+  } else if (highest_supported_version < 3 &&
+             conn->_base.state ==  OR_CONN_STATE_OR_HANDSHAKING_V3) {
+    log_fn(LOG_PROTOCOL_WARN, LD_OR,
+           "Negotiated link protocol 2 or lower after doing a v3 TLS "
+           "handshake. Closing connection.");
+    connection_mark_for_close(TO_CONN(conn));
+    return;
   }
+
   conn->link_proto = highest_supported_version;
   conn->handshake_state->received_versions = 1;
 
-  log_info(LD_OR, "Negotiated version %d with %s:%d; sending NETINFO.",
-           highest_supported_version,
-           safe_str_client(conn->_base.address),
-           conn->_base.port);
-  tor_assert(conn->link_proto >= 2);
+  if (conn->link_proto == 2) {
+    log_info(LD_OR, "Negotiated version %d with %s:%d; sending NETINFO.",
+             highest_supported_version,
+             safe_str_client(conn->_base.address),
+             conn->_base.port);
 
-  if (connection_or_send_netinfo(conn) < 0) {
-    connection_mark_for_close(TO_CONN(conn));
-    return;
+    if (connection_or_send_netinfo(conn) < 0) {
+      connection_mark_for_close(TO_CONN(conn));
+      return;
+    }
+  } else {
+    const int send_versions = !started_here;
+    /* If we want to authenticate, send a CERTS cell */
+    const int send_certs = !started_here || public_server_mode(get_options());
+    /* If we're a relay that got a connection, ask for authentication. */
+    const int send_chall = !started_here && public_server_mode(get_options());
+    /* If our certs cell will authenticate us, or if we have no intention of
+     * authenticating, send a netinfo cell right now. */
+    const int send_netinfo =
+      !(started_here && public_server_mode(get_options()));
+    const int send_any =
+      send_versions || send_certs || send_chall || send_netinfo;
+    tor_assert(conn->link_proto >= 3);
+
+    log_info(LD_OR, "Negotiated version %d with %s:%d; %s%s%s%s%s",
+             highest_supported_version,
+             safe_str_client(conn->_base.address),
+             conn->_base.port,
+             send_any ? "Sending cells:" : "Waiting for CERTS cell",
+             send_versions ? " VERSIONS" : "",
+             send_certs ? " CERTS" : "",
+             send_chall ? " AUTH_CHALLENGE" : "",
+             send_netinfo ? " NETINFO" : "");
+
+#ifdef DISABLE_V3_LINKPROTO_SERVERSIDE
+    if (1) {
+      connection_mark_for_close(TO_CONN(conn));
+      return;
+    }
+#endif
+
+    if (send_versions) {
+      if (connection_or_send_versions(conn, 1) < 0) {
+        log_warn(LD_OR, "Couldn't send versions cell");
+        connection_mark_for_close(TO_CONN(conn));
+        return;
+      }
+    }
+    if (send_certs) {
+      if (connection_or_send_cert_cell(conn) < 0) {
+        log_warn(LD_OR, "Couldn't send cert cell");
+        connection_mark_for_close(TO_CONN(conn));
+        return;
+      }
+    }
+    if (send_chall) {
+      if (connection_or_send_auth_challenge_cell(conn) < 0) {
+        log_warn(LD_OR, "Couldn't send auth_challenge cell");
+        connection_mark_for_close(TO_CONN(conn));
+        return;
+      }
+    }
+    if (send_netinfo) {
+      if (connection_or_send_netinfo(conn) < 0) {
+        log_warn(LD_OR, "Couldn't send netinfo cell");
+        connection_mark_for_close(TO_CONN(conn));
+        return;
+      }
+    }
   }
 }
 
@@ -572,13 +749,41 @@ command_process_netinfo_cell(cell_t *cell, or_connection_t *conn)
            conn->link_proto == 0 ? "non-versioned" : "a v1");
     return;
   }
-  if (conn->_base.state != OR_CONN_STATE_OR_HANDSHAKING) {
+  if (conn->_base.state != OR_CONN_STATE_OR_HANDSHAKING_V2 &&
+      conn->_base.state != OR_CONN_STATE_OR_HANDSHAKING_V3) {
     log_fn(LOG_PROTOCOL_WARN, LD_OR,
            "Received a NETINFO cell on non-handshaking connection; dropping.");
     return;
   }
   tor_assert(conn->handshake_state &&
              conn->handshake_state->received_versions);
+
+  if (conn->_base.state == OR_CONN_STATE_OR_HANDSHAKING_V3) {
+    tor_assert(conn->link_proto >= 3);
+    if (conn->handshake_state->started_here) {
+      if (!conn->handshake_state->authenticated) {
+        log_fn(LOG_PROTOCOL_WARN, LD_OR, "Got a NETINFO cell from server, "
+               "but no authentication.  Closing the connection.");
+        connection_mark_for_close(TO_CONN(conn));
+        return;
+      }
+    } else {
+      /* we're the server.  If the client never authenticated, we have
+         some housekeeping to do.*/
+      if (!conn->handshake_state->authenticated) {
+        tor_assert(tor_digest_is_zero(
+                  (const char*)conn->handshake_state->authenticated_peer_id));
+        connection_or_set_circid_type(conn, NULL);
+
+        connection_or_init_conn_from_address(conn,
+                  &conn->_base.addr,
+                  conn->_base.port,
+                  (const char*)conn->handshake_state->authenticated_peer_id,
+                  0);
+      }
+    }
+  }
+
   /* Decode the cell. */
   timestamp = ntohl(get_uint32(cell->payload));
   if (labs(now - conn->handshake_state->sent_versions_at) < 180) {
@@ -651,13 +856,386 @@ command_process_netinfo_cell(cell_t *cell, or_connection_t *conn)
    * trustworthy. */
   (void)my_apparent_addr;
 
-  if (connection_or_set_state_open(conn)<0)
+  if (connection_or_set_state_open(conn)<0) {
+    log_fn(LOG_PROTOCOL_WARN, LD_OR, "Got good NETINFO cell from %s:%d; but "
+           "was unable to make the OR connection become open.",
+           safe_str_client(conn->_base.address),
+           conn->_base.port);
     connection_mark_for_close(TO_CONN(conn));
-  else
+  } else {
     log_info(LD_OR, "Got good NETINFO cell from %s:%d; OR connection is now "
-             "open, using protocol version %d",
+             "open, using protocol version %d. Its ID digest is %s",
              safe_str_client(conn->_base.address),
-             conn->_base.port, (int)conn->link_proto);
+             conn->_base.port, (int)conn->link_proto,
+             hex_str(conn->identity_digest, DIGEST_LEN));
+  }
   assert_connection_ok(TO_CONN(conn),time(NULL));
 }
 
+/** Process a CERT cell from an OR connection.
+ *
+ * If the other side should not have sent us a CERT cell, or the cell is
+ * malformed, or it is supposed to authenticate the TLS key but it doesn't,
+ * then mark the connection.
+ *
+ * If the cell has a good cert chain and we're doing a v3 handshake, then
+ * store the certificates in or_handshake_state.  If this is the client side
+ * of the connection, we then authenticate the server or mark the connection.
+ * If it's the server side, wait for an AUTHENTICATE cell.
+ */
+static void
+command_process_cert_cell(var_cell_t *cell, or_connection_t *conn)
+{
+#define ERR(s)                                                  \
+  do {                                                          \
+    log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,                      \
+           "Received a bad CERT cell from %s:%d: %s",           \
+           safe_str(conn->_base.address), conn->_base.port, (s)); \
+    connection_mark_for_close(TO_CONN(conn));                   \
+    goto err;                                                   \
+  } while (0)
+
+  tor_cert_t *link_cert = NULL;
+  tor_cert_t *id_cert = NULL;
+  tor_cert_t *auth_cert = NULL;
+
+  uint8_t *ptr;
+  int n_certs, i;
+
+  if (conn->_base.state != OR_CONN_STATE_OR_HANDSHAKING_V3)
+    ERR("We're not doing a v3 handshake!");
+  if (conn->link_proto < 3)
+    ERR("We're not using link protocol >= 3");
+  if (conn->handshake_state->received_cert_cell)
+    ERR("We already got one");
+  if (conn->handshake_state->authenticated) {
+    /* Should be unreachable, but let's make sure. */
+    ERR("We're already authenticated!");
+  }
+  if (cell->payload_len < 1)
+    ERR("It had no body");
+  if (cell->circ_id)
+    ERR("It had a nonzero circuit ID");
+
+  n_certs = cell->payload[0];
+  ptr = cell->payload + 1;
+  for (i = 0; i < n_certs; ++i) {
+    uint8_t cert_type;
+    uint16_t cert_len;
+    if (ptr + 3 > cell->payload + cell->payload_len) {
+      goto truncated;
+    }
+    cert_type = *ptr;
+    cert_len = ntohs(get_uint16(ptr+1));
+    if (ptr + 3 + cert_len > cell->payload + cell->payload_len) {
+      goto truncated;
+    }
+    if (cert_type == OR_CERT_TYPE_TLS_LINK ||
+        cert_type == OR_CERT_TYPE_ID_1024 ||
+        cert_type == OR_CERT_TYPE_AUTH_1024) {
+      tor_cert_t *cert = tor_cert_decode(ptr + 3, cert_len);
+      if (!cert) {
+        log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
+               "Received undecodable certificate in CERT cell from %s:%d",
+               safe_str(conn->_base.address), conn->_base.port);
+      } else {
+        if (cert_type == OR_CERT_TYPE_TLS_LINK) {
+          if (link_cert) {
+            tor_cert_free(cert);
+            ERR("Too many TLS_LINK certificates");
+          }
+          link_cert = cert;
+        } else if (cert_type == OR_CERT_TYPE_ID_1024) {
+          if (id_cert) {
+            tor_cert_free(cert);
+            ERR("Too many ID_1024 certificates");
+          }
+          id_cert = cert;
+        } else if (cert_type == OR_CERT_TYPE_AUTH_1024) {
+          if (auth_cert) {
+            tor_cert_free(cert);
+            ERR("Too many AUTH_1024 certificates");
+          }
+          auth_cert = cert;
+        } else {
+          tor_cert_free(cert);
+        }
+      }
+    }
+    ptr += 3 + cert_len;
+    continue;
+
+  truncated:
+    ERR("It ends in the middle of a certificate");
+  }
+
+  if (conn->handshake_state->started_here) {
+    if (! (id_cert && link_cert))
+      ERR("The certs we wanted were missing");
+    /* Okay. We should be able to check the certificates now. */
+    if (! tor_tls_cert_matches_key(conn->tls, link_cert)) {
+      ERR("The link certificate didn't match the TLS public key");
+    }
+    if (! tor_tls_cert_is_valid(link_cert, id_cert, 0))
+      ERR("The link certificate was not valid");
+    if (! tor_tls_cert_is_valid(id_cert, id_cert, 1))
+      ERR("The ID certificate was not valid");
+
+    conn->handshake_state->authenticated = 1;
+    {
+      const digests_t *id_digests = tor_cert_get_id_digests(id_cert);
+      crypto_pk_env_t *identity_rcvd;
+      if (!id_digests)
+        ERR("Couldn't compute digests for key in ID cert");
+
+      identity_rcvd = tor_tls_cert_get_key(id_cert);
+      memcpy(conn->handshake_state->authenticated_peer_id,
+             id_digests->d[DIGEST_SHA1], DIGEST_LEN);
+      connection_or_set_circid_type(conn, identity_rcvd);
+      crypto_free_pk_env(identity_rcvd);
+    }
+
+    if (connection_or_client_learned_peer_id(conn,
+                      conn->handshake_state->authenticated_peer_id) < 0)
+      ERR("Problem setting or checking peer id");
+
+    log_info(LD_OR, "Got some good certificates from %s:%d: Authenticated it.",
+             safe_str(conn->_base.address), conn->_base.port);
+
+    conn->handshake_state->id_cert = id_cert;
+    id_cert = NULL;
+  } else {
+    if (! (id_cert && auth_cert))
+      ERR("The certs we wanted were missing");
+
+    /* Remember these certificates so we can check an AUTHENTICATE cell */
+    conn->handshake_state->id_cert = id_cert;
+    conn->handshake_state->auth_cert = auth_cert;
+    if (! tor_tls_cert_is_valid(auth_cert, id_cert, 1))
+      ERR("The authentication certificate was not valid");
+    if (! tor_tls_cert_is_valid(id_cert, id_cert, 1))
+      ERR("The ID certificate was not valid");
+
+
+    log_info(LD_OR, "Got some good certificates from %s:%d: "
+             "Waiting for AUTHENTICATE.",
+             safe_str(conn->_base.address), conn->_base.port);
+    /* XXXX check more stuff? */
+
+    id_cert = auth_cert = NULL;
+  }
+
+  conn->handshake_state->received_cert_cell = 1;
+err:
+  tor_cert_free(id_cert);
+  tor_cert_free(link_cert);
+  tor_cert_free(auth_cert);
+#undef ERR
+}
+
+/** Process an AUTH_CHALLENGE cell from an OR connection.
+ *
+ * If we weren't supposed to get one (for example, because we're not the
+ * originator of the connection), or it's ill-formed, or we aren't doing a v3
+ * handshake, mark the connection.  If the cell is well-formed but we don't
+ * want to authenticate, just drop it.  If the cell is well-formed *and* we
+ * want to authenticate, send an AUTHENTICATE cell. */
+static void
+command_process_auth_challenge_cell(var_cell_t *cell, or_connection_t *conn)
+{
+  int n_types, i, use_type = -1;
+  uint8_t *cp;
+
+#define ERR(s)                                                  \
+  do {                                                          \
+    log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,                      \
+           "Received a bad AUTH_CHALLENGE cell from %s:%d: %s", \
+           safe_str(conn->_base.address), conn->_base.port, (s));       \
+    connection_mark_for_close(TO_CONN(conn));                   \
+    return;                                                     \
+  } while (0)
+
+  if (conn->_base.state != OR_CONN_STATE_OR_HANDSHAKING_V3)
+    ERR("We're not currently doing a v3 handshake");
+  if (conn->link_proto < 3)
+    ERR("We're not using link protocol >= 3");
+  if (! conn->handshake_state->started_here)
+    ERR("We didn't originate this connection");
+  if (conn->handshake_state->received_auth_challenge)
+    ERR("We already received one");
+  if (! conn->handshake_state->received_cert_cell)
+    ERR("We haven't gotten a CERTS cell yet");
+  if (cell->payload_len < OR_AUTH_CHALLENGE_LEN + 2)
+    ERR("It was too short");
+  if (cell->circ_id)
+    ERR("It had a nonzero circuit ID");
+
+  n_types = ntohs(get_uint16(cell->payload + OR_AUTH_CHALLENGE_LEN));
+  if (cell->payload_len < OR_AUTH_CHALLENGE_LEN + 2 + 2*n_types)
+    ERR("It looks truncated");
+
+  /* Now see if there is an authentication type we can use */
+  cp=cell->payload+OR_AUTH_CHALLENGE_LEN+2;
+  for (i=0; i < n_types; ++i, cp += 2) {
+    uint16_t authtype = ntohs(get_uint16(cp));
+    if (authtype == AUTHTYPE_RSA_SHA256_TLSSECRET)
+      use_type = authtype;
+  }
+
+  conn->handshake_state->received_auth_challenge = 1;
+
+  if (use_type && public_server_mode(get_options())) {
+    log_info(LD_OR, "Got an AUTH_CHALLENGE cell from %s:%d: Sending "
+             "authentication",
+             safe_str(conn->_base.address), conn->_base.port);
+
+    if (connection_or_send_authenticate_cell(conn, use_type) < 0) {
+      log_warn(LD_OR, "Couldn't send authenticate cell");
+      connection_mark_for_close(TO_CONN(conn));
+      return;
+    }
+    if (connection_or_send_netinfo(conn) < 0) {
+      log_warn(LD_OR, "Couldn't send netinfo cell");
+      connection_mark_for_close(TO_CONN(conn));
+      return;
+    }
+  } else {
+    log_info(LD_OR, "Got an AUTH_CHALLENGE cell from %s:%d: Not authenticating",
+             safe_str(conn->_base.address), conn->_base.port);
+  }
+#undef ERR
+}
+
+/** Process an AUTHENTICATE cell from an OR connection.
+ *
+ * If it's ill-formed or we weren't supposed to get one or we're not doing a
+ * v3 handshake, then mark the connection.  If it does not authenticate the
+ * other side of the connection successfully (because it isn't signed right,
+ * we didn't get a CERT cell, etc) mark the connection.  Otherwise, accept
+ * the identity of the router on the other side of the connection.
+ */
+static void
+command_process_authenticate_cell(var_cell_t *cell, or_connection_t *conn)
+{
+  uint8_t expected[V3_AUTH_FIXED_PART_LEN];
+  const uint8_t *auth;
+  int authlen;
+
+#define ERR(s)                                                  \
+  do {                                                          \
+    log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,                      \
+           "Received a bad AUTHETNICATE cell from %s:%d: %s",   \
+           safe_str(conn->_base.address), conn->_base.port, (s));       \
+    connection_mark_for_close(TO_CONN(conn));                   \
+    return;                                                     \
+  } while (0)
+
+  if (conn->_base.state != OR_CONN_STATE_OR_HANDSHAKING_V3)
+    ERR("We're not doing a v3 handshake");
+  if (conn->link_proto < 3)
+    ERR("We're not using link protocol >= 3");
+  if (conn->handshake_state->started_here)
+    ERR("We originated this connection");
+  if (conn->handshake_state->received_authenticate)
+    ERR("We already got one!");
+  if (conn->handshake_state->authenticated) {
+    /* Should be impossible given other checks */
+    ERR("The peer is already authenticated");
+  }
+  if (! conn->handshake_state->received_cert_cell)
+    ERR("We never got a cert cell");
+  if (conn->handshake_state->auth_cert == NULL)
+    ERR("We never got an authentication certificate");
+  if (conn->handshake_state->id_cert == NULL)
+    ERR("We never got an identity certificate");
+  if (cell->payload_len < 4)
+    ERR("Cell was way too short");
+
+  auth = cell->payload;
+  {
+    uint16_t type = ntohs(get_uint16(auth));
+    uint16_t len = ntohs(get_uint16(auth+2));
+    if (4 + len > cell->payload_len)
+      ERR("Authenticator was truncated");
+
+    if (type != AUTHTYPE_RSA_SHA256_TLSSECRET)
+      ERR("Authenticator type was not recognized");
+
+    auth += 4;
+    authlen = len;
+  }
+
+  if (authlen < V3_AUTH_BODY_LEN + 1)
+    ERR("Authenticator was too short");
+
+  if (connection_or_compute_authenticate_cell_body(
+                        conn, expected, sizeof(expected), NULL, 1) < 0)
+    ERR("Couldn't compute expected AUTHENTICATE cell body");
+
+  if (tor_memneq(expected, auth, sizeof(expected)))
+    ERR("Some field in the AUTHENTICATE cell body was not as expected");
+
+  {
+    crypto_pk_env_t *pk = tor_tls_cert_get_key(
+                                   conn->handshake_state->auth_cert);
+    char d[DIGEST256_LEN];
+    char *signed_data;
+    size_t keysize;
+    int signed_len;
+
+    crypto_digest256(d, (char*)auth, V3_AUTH_BODY_LEN, DIGEST_SHA256);
+
+    keysize = crypto_pk_keysize(pk);
+    signed_data = tor_malloc(keysize);
+    signed_len = crypto_pk_public_checksig(pk, signed_data, keysize,
+                                           (char*)auth + V3_AUTH_BODY_LEN,
+                                           authlen - V3_AUTH_BODY_LEN);
+    if (signed_len < 0) {
+      tor_free(signed_data);
+      ERR("Signature wasn't valid");
+    }
+    if (signed_len < DIGEST256_LEN) {
+      tor_free(signed_data);
+      ERR("Not enough data was signed");
+    }
+    /* Note that we deliberately allow *more* than DIGEST256_LEN bytes here,
+     * in case they're later used to hold a SHA3 digest or something. */
+    if (tor_memneq(signed_data, d, DIGEST256_LEN)) {
+      tor_free(signed_data);
+      ERR("Signature did not match data to be signed.");
+    }
+    tor_free(signed_data);
+  }
+
+  /* Okay, we are authenticated. */
+  conn->handshake_state->received_authenticate = 1;
+  conn->handshake_state->authenticated = 1;
+  conn->handshake_state->digest_received_data = 0;
+  {
+    crypto_pk_env_t *identity_rcvd =
+      tor_tls_cert_get_key(conn->handshake_state->id_cert);
+    const digests_t *id_digests =
+      tor_cert_get_id_digests(conn->handshake_state->id_cert);
+
+    /* This must exist; we checked key type when reading the cert. */
+    tor_assert(id_digests);
+
+    memcpy(conn->handshake_state->authenticated_peer_id,
+           id_digests->d[DIGEST_SHA1], DIGEST_LEN);
+
+    connection_or_set_circid_type(conn, identity_rcvd);
+    crypto_free_pk_env(identity_rcvd);
+
+    connection_or_init_conn_from_address(conn,
+                  &conn->_base.addr,
+                  conn->_base.port,
+                  (const char*)conn->handshake_state->authenticated_peer_id,
+                  0);
+
+    log_info(LD_OR, "Got an AUTHENTICATE cell from %s:%d: Looks good.",
+             safe_str(conn->_base.address), conn->_base.port);
+  }
+
+#undef ERR
+}
+
diff --git a/src/or/connection.c b/src/or/connection.c
index 45a12715a..2bd2d07e9 100644
--- a/src/or/connection.c
+++ b/src/or/connection.c
@@ -140,10 +140,13 @@ conn_state_to_string(int type, int state)
         case OR_CONN_STATE_PROXY_HANDSHAKING: return "handshaking (proxy)";
         case OR_CONN_STATE_TLS_HANDSHAKING: return "handshaking (TLS)";
         case OR_CONN_STATE_TLS_CLIENT_RENEGOTIATING:
-          return "renegotiating (TLS)";
+          return "renegotiating (TLS, v2 handshake)";
         case OR_CONN_STATE_TLS_SERVER_RENEGOTIATING:
-          return "waiting for renegotiation (TLS)";
-        case OR_CONN_STATE_OR_HANDSHAKING: return "handshaking (Tor)";
+          return "waiting for renegotiation or V3 handshake";
+        case OR_CONN_STATE_OR_HANDSHAKING_V2:
+          return "handshaking (Tor, v2 handshake)";
+        case OR_CONN_STATE_OR_HANDSHAKING_V3:
+          return "handshaking (Tor, v3 handshake)";
         case OR_CONN_STATE_OPEN: return "open";
       }
       break;
diff --git a/src/or/connection_or.c b/src/or/connection_or.c
index 29f0f8de7..bcae075c5 100644
--- a/src/or/connection_or.c
+++ b/src/or/connection_or.c
@@ -35,10 +35,8 @@
 #endif
 
 static int connection_tls_finish_handshake(or_connection_t *conn);
+static int connection_or_launch_v3_or_handshake(or_connection_t *conn);
 static int connection_or_process_cells_from_inbuf(or_connection_t *conn);
-static int connection_or_send_versions(or_connection_t *conn);
-static int connection_init_or_handshake_state(or_connection_t *conn,
-                                              int started_here);
 static int connection_or_check_valid_tls_handshake(or_connection_t *conn,
                                                    int started_here,
                                                    char *digest_rcvd_out);
@@ -378,8 +376,8 @@ connection_or_process_inbuf(or_connection_t *conn)
       }
 
       return ret;
-#ifdef USE_BUFFEREVENTS
     case OR_CONN_STATE_TLS_SERVER_RENEGOTIATING:
+#ifdef USE_BUFFEREVENTS
       if (tor_tls_server_got_renegotiate(conn->tls))
         connection_or_tls_renegotiated_cb(conn->tls, conn);
       if (conn->_base.marked_for_close)
@@ -387,7 +385,8 @@ connection_or_process_inbuf(or_connection_t *conn)
       /* fall through. */
 #endif
     case OR_CONN_STATE_OPEN:
-    case OR_CONN_STATE_OR_HANDSHAKING:
+    case OR_CONN_STATE_OR_HANDSHAKING_V2:
+    case OR_CONN_STATE_OR_HANDSHAKING_V3:
       return connection_or_process_cells_from_inbuf(conn);
     default:
       return 0; /* don't do anything */
@@ -439,7 +438,8 @@ connection_or_finished_flushing(or_connection_t *conn)
   switch (conn->_base.state) {
     case OR_CONN_STATE_PROXY_HANDSHAKING:
     case OR_CONN_STATE_OPEN:
-    case OR_CONN_STATE_OR_HANDSHAKING:
+    case OR_CONN_STATE_OR_HANDSHAKING_V2:
+    case OR_CONN_STATE_OR_HANDSHAKING_V3:
       break;
     default:
       log_err(LD_BUG,"Called in unexpected state %d.", conn->_base.state);
@@ -627,7 +627,7 @@ connection_or_update_token_buckets(smartlist_t *conns,
 /** If we don't necessarily know the router we're connecting to, but we
  * have an addr/port/id_digest, then fill in as much as we can. Start
  * by checking to see if this describes a router we know. */
-static void
+void
 connection_or_init_conn_from_address(or_connection_t *conn,
                                      const tor_addr_t *addr, uint16_t port,
                                      const char *id_digest,
@@ -1180,16 +1180,22 @@ connection_tls_continue_handshake(or_connection_t *conn)
       if (! tor_tls_used_v1_handshake(conn->tls)) {
         if (!tor_tls_is_server(conn->tls)) {
           if (conn->_base.state == OR_CONN_STATE_TLS_HANDSHAKING) {
-            log_debug(LD_OR, "Done with initial SSL handshake (client-side). "
-                             "Requesting renegotiation.");
-            conn->_base.state = OR_CONN_STATE_TLS_CLIENT_RENEGOTIATING;
-            goto again;
+            if (tor_tls_received_v3_certificate(conn->tls)) {
+              log_info(LD_OR, "Client got a v3 cert!  Moving on to v3 "
+                         "handshake.");
+              return connection_or_launch_v3_or_handshake(conn);
+            } else {
+              log_debug(LD_OR, "Done with initial SSL handshake (client-side). "
+                        "Requesting renegotiation.");
+              conn->_base.state = OR_CONN_STATE_TLS_CLIENT_RENEGOTIATING;
+              goto again;
+            }
           }
           // log_notice(LD_OR,"Done. state was %d.", conn->_base.state);
         } else {
-          /* improved handshake, but not a client. */
+          /* v2/v3 handshake, but not a client. */
           log_debug(LD_OR, "Done with initial SSL handshake (server-side). "
-                           "Expecting renegotiation.");
+                           "Expecting renegotiation or VERSIONS cell");
           tor_tls_set_renegotiate_callback(conn->tls,
                                            connection_or_tls_renegotiated_cb,
                                            conn);
@@ -1234,17 +1240,24 @@ connection_or_handle_event_cb(struct bufferevent *bufev, short event,
     if (! tor_tls_used_v1_handshake(conn->tls)) {
       if (!tor_tls_is_server(conn->tls)) {
         if (conn->_base.state == OR_CONN_STATE_TLS_HANDSHAKING) {
-          conn->_base.state = OR_CONN_STATE_TLS_CLIENT_RENEGOTIATING;
-          tor_tls_unblock_renegotiation(conn->tls);
-          if (bufferevent_ssl_renegotiate(conn->_base.bufev)<0) {
-            log_warn(LD_OR, "Start_renegotiating went badly.");
-            connection_mark_for_close(TO_CONN(conn));
+          if (tor_tls_received_v3_certificate(conn->tls)) {
+            log_info(LD_OR, "Client got a v3 cert!");
+            if (connection_or_launch_v3_or_handshake(conn) < 0)
+              connection_mark_for_close(TO_CONN(conn));
+            return;
+          } else {
+            conn->_base.state = OR_CONN_STATE_TLS_CLIENT_RENEGOTIATING;
+            tor_tls_unblock_renegotiation(conn->tls);
+            if (bufferevent_ssl_renegotiate(conn->_base.bufev)<0) {
+              log_warn(LD_OR, "Start_renegotiating went badly.");
+              connection_mark_for_close(TO_CONN(conn));
+            }
+            tor_tls_unblock_renegotiation(conn->tls);
+            return; /* ???? */
           }
-          tor_tls_unblock_renegotiation(conn->tls);
-          return; /* ???? */
         }
       } else if (tor_tls_get_num_server_handshakes(conn->tls) == 1) {
-        /* improved handshake, as a server. Only got one handshake, so
+        /* v2 or v3 handshake, as a server. Only got one handshake, so
          * wait for the next one. */
         tor_tls_set_renegotiate_callback(conn->tls,
                                          connection_or_tls_renegotiated_cb,
@@ -1256,7 +1269,7 @@ connection_or_handle_event_cb(struct bufferevent *bufev, short event,
         const int handshakes = tor_tls_get_num_server_handshakes(conn->tls);
         tor_assert(handshakes >= 2);
         if (handshakes == 2) {
-          /* improved handshake, as a server.  Two handshakes happened already,
+          /* v2 handshake, as a server.  Two handshakes happened already,
            * so we treat renegotiation as done.
            */
           connection_or_tls_renegotiated_cb(conn->tls, conn);
@@ -1300,6 +1313,29 @@ connection_or_nonopen_was_started_here(or_connection_t *conn)
   return !tor_tls_is_server(conn->tls);
 }
 
+/** Set the circid_type field of <b>conn</b> (which determines which part of
+ * the circuit ID space we're willing to use) based on comparing our ID to
+ * <b>identity_rcvd</b> */
+void
+connection_or_set_circid_type(or_connection_t *conn,
+                              crypto_pk_env_t *identity_rcvd)
+{
+  const int started_here = connection_or_nonopen_was_started_here(conn);
+  crypto_pk_env_t *our_identity =
+    started_here ? get_tlsclient_identity_key() :
+                   get_server_identity_key();
+
+  if (identity_rcvd) {
+    if (crypto_pk_cmp_keys(our_identity, identity_rcvd)<0) {
+      conn->circ_id_type = CIRC_ID_TYPE_LOWER;
+    } else {
+      conn->circ_id_type = CIRC_ID_TYPE_HIGHER;
+    }
+  } else {
+    conn->circ_id_type = CIRC_ID_TYPE_NEITHER;
+  }
+}
+
 /** <b>Conn</b> just completed its handshake. Return 0 if all is well, and
  * return -1 if he is lying, broken, or otherwise something is wrong.
  *
@@ -1337,10 +1373,7 @@ connection_or_check_valid_tls_handshake(or_connection_t *conn,
     started_here ? conn->_base.address :
                    safe_str_client(conn->_base.address);
   const char *conn_type = started_here ? "outgoing" : "incoming";
-  crypto_pk_env_t *our_identity =
-    started_here ? get_tlsclient_identity_key() :
-                   get_server_identity_key();
-  int has_cert = 0, has_identity=0;
+  int has_cert = 0;
 
   check_no_tls_errors();
   has_cert = tor_tls_peer_has_cert(conn->tls);
@@ -1375,21 +1408,46 @@ connection_or_check_valid_tls_handshake(or_connection_t *conn,
   }
 
   if (identity_rcvd) {
-    has_identity = 1;
     crypto_pk_get_digest(identity_rcvd, digest_rcvd_out);
-    if (crypto_pk_cmp_keys(our_identity, identity_rcvd)<0) {
-      conn->circ_id_type = CIRC_ID_TYPE_LOWER;
-    } else {
-      conn->circ_id_type = CIRC_ID_TYPE_HIGHER;
-    }
-    crypto_free_pk_env(identity_rcvd);
   } else {
     memset(digest_rcvd_out, 0, DIGEST_LEN);
-    conn->circ_id_type = CIRC_ID_TYPE_NEITHER;
   }
 
-  if (started_here && tor_digest_is_zero(conn->identity_digest)) {
-    connection_or_set_identity_digest(conn, digest_rcvd_out);
+  connection_or_set_circid_type(conn, identity_rcvd);
+  crypto_free_pk_env(identity_rcvd);
+
+  if (started_here)
+    return connection_or_client_learned_peer_id(conn,
+                                     (const uint8_t*)digest_rcvd_out);
+
+  return 0;
+}
+
+/** Called when we (as a connection initiator) have definitively,
+ * authenticatedly, learned that ID of the Tor instance on the other
+ * side of <b>conn</b> is <b>peer_id</b>.  For v1 and v2 handshakes,
+ * this is right after we get a certificate chain in a TLS handshake
+ * or renegotiation.  For v3 handshakes, this is right after we get a
+ * certificate chain in a CERT cell.
+ *
+ * If we want any particular ID before, record the one we got.
+ *
+ * If we wanted an ID, but we didn't get it, log a warning and return -1.
+ *
+ * If we're testing reachability, remember what we learned.
+ *
+ * Return 0 on success, -1 on failure.
+ */
+int
+connection_or_client_learned_peer_id(or_connection_t *conn,
+                                     const uint8_t *peer_id)
+{
+  int as_expected = 1;
+  const or_options_t *options = get_options();
+  int severity = server_mode(options) ? LOG_PROTOCOL_WARN : LOG_WARN;
+
+  if (tor_digest_is_zero(conn->identity_digest)) {
+    connection_or_set_identity_digest(conn, (const char*)peer_id);
     tor_free(conn->nickname);
     conn->nickname = tor_malloc(HEX_DIGEST_LEN+2);
     conn->nickname[0] = '$';
@@ -1401,43 +1459,39 @@ connection_or_check_valid_tls_handshake(or_connection_t *conn,
     /* if it's a bridge and we didn't know its identity fingerprint, now
      * we do -- remember it for future attempts. */
     learned_router_identity(&conn->_base.addr, conn->_base.port,
-                            digest_rcvd_out);
+                            (const char*)peer_id);
   }
 
-  if (started_here) {
-    int as_advertised = 1;
-    tor_assert(has_cert);
-    tor_assert(has_identity);
-    if (tor_memneq(digest_rcvd_out, conn->identity_digest, DIGEST_LEN)) {
-      /* I was aiming for a particular digest. I didn't get it! */
-      char seen[HEX_DIGEST_LEN+1];
-      char expected[HEX_DIGEST_LEN+1];
-      base16_encode(seen, sizeof(seen), digest_rcvd_out, DIGEST_LEN);
-      base16_encode(expected, sizeof(expected), conn->identity_digest,
-                    DIGEST_LEN);
-      log_fn(severity, LD_HANDSHAKE,
-             "Tried connecting to router at %s:%d, but identity key was not "
-             "as expected: wanted %s but got %s.",
-             conn->_base.address, conn->_base.port, expected, seen);
-      entry_guard_register_connect_status(conn->identity_digest, 0, 1,
-                                          time(NULL));
-      control_event_or_conn_status(conn, OR_CONN_EVENT_FAILED,
-              END_OR_CONN_REASON_OR_IDENTITY);
-      if (!authdir_mode_tests_reachability(options))
-        control_event_bootstrap_problem("foo", END_OR_CONN_REASON_OR_IDENTITY);
-      as_advertised = 0;
-    }
-    if (authdir_mode_tests_reachability(options)) {
-      dirserv_orconn_tls_done(conn->_base.address, conn->_base.port,
-                              digest_rcvd_out, as_advertised);
-    }
-    if (!as_advertised)
-      return -1;
+  if (tor_memneq(peer_id, conn->identity_digest, DIGEST_LEN)) {
+    /* I was aiming for a particular digest. I didn't get it! */
+    char seen[HEX_DIGEST_LEN+1];
+    char expected[HEX_DIGEST_LEN+1];
+    base16_encode(seen, sizeof(seen), (const char*)peer_id, DIGEST_LEN);
+    base16_encode(expected, sizeof(expected), conn->identity_digest,
+                  DIGEST_LEN);
+    log_fn(severity, LD_HANDSHAKE,
+           "Tried connecting to router at %s:%d, but identity key was not "
+           "as expected: wanted %s but got %s.",
+           conn->_base.address, conn->_base.port, expected, seen);
+    entry_guard_register_connect_status(conn->identity_digest, 0, 1,
+                                        time(NULL));
+    control_event_or_conn_status(conn, OR_CONN_EVENT_FAILED,
+                                 END_OR_CONN_REASON_OR_IDENTITY);
+    if (!authdir_mode_tests_reachability(options))
+      control_event_bootstrap_problem("foo", END_OR_CONN_REASON_OR_IDENTITY);
+    as_expected = 0;
   }
+  if (authdir_mode_tests_reachability(options)) {
+    dirserv_orconn_tls_done(conn->_base.address, conn->_base.port,
+                            (const char*)peer_id, as_expected);
+  }
+  if (!as_expected)
+    return -1;
+
   return 0;
 }
 
-/** The tls handshake is finished.
+/** The v1/v2 TLS handshake is finished.
  *
  * Make sure we are happy with the person we just handshaked with.
  *
@@ -1447,6 +1501,8 @@ connection_or_check_valid_tls_handshake(or_connection_t *conn,
  * If all is successful, call circuit_n_conn_done() to handle events
  * that have been pending on the <tls handshake completion. Also set the
  * directory to be dirty (only matters if I'm an authdirserver).
+ *
+ * If this is a v2 TLS handshake, send a versions cell.
  */
 static int
 connection_tls_finish_handshake(or_connection_t *conn)
@@ -1476,25 +1532,49 @@ connection_tls_finish_handshake(or_connection_t *conn)
     tor_tls_block_renegotiation(conn->tls);
     return connection_or_set_state_open(conn);
   } else {
-    conn->_base.state = OR_CONN_STATE_OR_HANDSHAKING;
+    conn->_base.state = OR_CONN_STATE_OR_HANDSHAKING_V2;
     if (connection_init_or_handshake_state(conn, started_here) < 0)
       return -1;
     if (!started_here) {
       connection_or_init_conn_from_address(conn, &conn->_base.addr,
                                            conn->_base.port, digest_rcvd, 0);
     }
-    return connection_or_send_versions(conn);
+    return connection_or_send_versions(conn, 0);
   }
 }
 
+/**
+ * Called as client when initial TLS handshake is done, and we notice
+ * that we got a v3-handshake signalling certificate from the server.
+ * Set up structures, do bookkeeping, and send the versions cell.
+ * Return 0 on success and -1 on failure.
+ */
+static int
+connection_or_launch_v3_or_handshake(or_connection_t *conn)
+{
+  tor_assert(connection_or_nonopen_was_started_here(conn));
+  tor_assert(tor_tls_received_v3_certificate(conn->tls));
+
+  circuit_build_times_network_is_live(&circ_times);
+
+  conn->_base.state = OR_CONN_STATE_OR_HANDSHAKING_V3;
+  if (connection_init_or_handshake_state(conn, 1) < 0)
+    return -1;
+
+  return connection_or_send_versions(conn, 1);
+}
+
+
 /** Allocate a new connection handshake state for the connection
  * <b>conn</b>.  Return 0 on success, -1 on failure. */
-static int
+int
 connection_init_or_handshake_state(or_connection_t *conn, int started_here)
 {
   or_handshake_state_t *s;
   s = conn->handshake_state = tor_malloc_zero(sizeof(or_handshake_state_t));
   s->started_here = started_here ? 1 : 0;
+  s->digest_sent_data = 1;
+  s->digest_received_data = 1;
   return 0;
 }
 
@@ -1504,10 +1584,89 @@ or_handshake_state_free(or_handshake_state_t *state)
 {
   if (!state)
     return;
+  crypto_free_digest_env(state->digest_sent);
+  crypto_free_digest_env(state->digest_received);
+  tor_cert_free(state->auth_cert);
+  tor_cert_free(state->id_cert);
   memset(state, 0xBE, sizeof(or_handshake_state_t));
   tor_free(state);
 }
 
+/**
+ * Remember that <b>cell</b> has been transmitted (if <b>incoming</b> is
+ * false) or received (if <b>incoming is true) during a V3 handshake using
+ * <b>state</b>.
+ *
+ * (We don't record the cell, but we keep a digest of everything sent or
+ * received during the v3 handshake, and the client signs it in an
+ * authenticate cell.)
+ */
+void
+or_handshake_state_record_cell(or_handshake_state_t *state,
+                               const cell_t *cell,
+                               int incoming)
+{
+  crypto_digest_env_t *d, **dptr;
+  packed_cell_t packed;
+  if (incoming) {
+    if (!state->digest_received_data)
+      return;
+  } else {
+    if (!state->digest_sent_data)
+      return;
+  }
+  if (!incoming) {
+    log_warn(LD_BUG, "We shouldn't be sending any non-variable-length cells "
+             "while making a handshake digest.  But we think we are sending "
+             "one with type %d.", (int)cell->command);
+  }
+  dptr = incoming ? &state->digest_received : &state->digest_sent;
+  if (! *dptr)
+    *dptr = crypto_new_digest256_env(DIGEST_SHA256);
+
+  d = *dptr;
+  /* Re-packing like this is a little inefficient, but we don't have to do
+     this very often at all. */
+  cell_pack(&packed, cell);
+  crypto_digest_add_bytes(d, packed.body, sizeof(packed.body));
+  memset(&packed, 0, sizeof(packed));
+}
+
+/** Remember that a variable-length <b>cell</b> has been transmitted (if
+ * <b>incoming</b> is false) or received (if <b>incoming is true) during a V3
+ * handshake using <b>state</b>.
+ *
+ * (We don't record the cell, but we keep a digest of everything sent or
+ * received during the v3 handshake, and the client signs it in an
+ * authenticate cell.)
+ */
+void
+or_handshake_state_record_var_cell(or_handshake_state_t *state,
+                                   const var_cell_t *cell,
+                                   int incoming)
+{
+  crypto_digest_env_t *d, **dptr;
+  char buf[VAR_CELL_HEADER_SIZE];
+  if (incoming) {
+    if (!state->digest_received_data)
+      return;
+  } else {
+    if (!state->digest_sent_data)
+      return;
+  }
+  dptr = incoming ? &state->digest_received : &state->digest_sent;
+  if (! *dptr)
+    *dptr = crypto_new_digest256_env(DIGEST_SHA256);
+
+  d = *dptr;
+
+  var_cell_pack_header(cell, buf);
+  crypto_digest_add_bytes(d, buf, sizeof(buf));
+  crypto_digest_add_bytes(d, (const char *)cell->payload, cell->payload_len);
+
+  memset(buf, 0, sizeof(buf));
+}
+
 /** Set <b>conn</b>'s state to OR_CONN_STATE_OPEN, and tell other subsystems
  * as appropriate.  Called when we are done with all TLS and OR handshaking.
  */
@@ -1575,6 +1734,9 @@ connection_or_write_cell_to_buf(const cell_t *cell, or_connection_t *conn)
 
   connection_write_to_buf(networkcell.body, CELL_NETWORK_SIZE, TO_CONN(conn));
 
+  if (conn->_base.state == OR_CONN_STATE_OR_HANDSHAKING_V3)
+    or_handshake_state_record_cell(conn->handshake_state, cell, 0);
+
   if (cell->command != CELL_PADDING)
     conn->timestamp_last_added_nonpadding = approx_time();
 }
@@ -1594,6 +1756,8 @@ connection_or_write_var_cell_to_buf(const var_cell_t *cell,
   connection_write_to_buf(hdr, sizeof(hdr), TO_CONN(conn));
   connection_write_to_buf((char*)cell->payload,
                           cell->payload_len, TO_CONN(conn));
+  if (conn->_base.state == OR_CONN_STATE_OR_HANDSHAKING_V3)
+    or_handshake_state_record_var_cell(conn->handshake_state, cell, 0);
   if (cell->command != CELL_PADDING)
     conn->timestamp_last_added_nonpadding = approx_time();
 }
@@ -1678,7 +1842,7 @@ connection_or_send_destroy(circid_t circ_id, or_connection_t *conn, int reason)
 }
 
 /** Array of recognized link protocol versions. */
-static const uint16_t or_protocol_versions[] = { 1, 2 };
+static const uint16_t or_protocol_versions[] = { 1, 2, 3 };
 /** Number of versions in <b>or_protocol_versions</b>. */
 static const int n_or_protocol_versions =
   (int)( sizeof(or_protocol_versions)/sizeof(uint16_t) );
@@ -1697,20 +1861,33 @@ is_or_protocol_version_known(uint16_t v)
 }
 
 /** Send a VERSIONS cell on <b>conn</b>, telling the other host about the
- * link protocol versions that this Tor can support. */
-static int
-connection_or_send_versions(or_connection_t *conn)
+ * link protocol versions that this Tor can support.
+ *
+ * If <b>v3_plus</b>, this is part of a V3 protocol handshake, so only
+ * allow protocol version v3 or later.  If not <b>v3_plus</b>, this is
+ * not part of a v3 protocol handshake, so don't allow protocol v3 or
+ * later.
+ **/
+int
+connection_or_send_versions(or_connection_t *conn, int v3_plus)
 {
   var_cell_t *cell;
   int i;
+  int n_versions = 0;
+  const int min_version = v3_plus ? 3 : 0;
+  const int max_version = v3_plus ? UINT16_MAX : 2;
   tor_assert(conn->handshake_state &&
              !conn->handshake_state->sent_versions_at);
   cell = var_cell_new(n_or_protocol_versions * 2);
   cell->command = CELL_VERSIONS;
   for (i = 0; i < n_or_protocol_versions; ++i) {
     uint16_t v = or_protocol_versions[i];
-    set_uint16(cell->payload+(2*i), htons(v));
+    if (v < min_version || v > max_version)
+      continue;
+    set_uint16(cell->payload+(2*n_versions), htons(v));
+    ++n_versions;
   }
+  cell->payload_len = n_versions * 2;
 
   connection_or_write_var_cell_to_buf(cell, conn);
   conn->handshake_state->sent_versions_at = time(NULL);
@@ -1730,6 +1907,8 @@ connection_or_send_netinfo(or_connection_t *conn)
   int len;
   uint8_t *out;
 
+  tor_assert(conn->handshake_state);
+
   memset(&cell, 0, sizeof(cell_t));
   cell.command = CELL_NETINFO;
 
@@ -1756,8 +1935,284 @@ connection_or_send_netinfo(or_connection_t *conn)
     *out = 0;
   }
 
+  conn->handshake_state->digest_sent_data = 0;
   connection_or_write_cell_to_buf(&cell, conn);
 
   return 0;
 }
 
+/** Send a CERT cell on the connection <b>conn</b>.  Return 0 on success, -1
+ * on failure. */
+int
+connection_or_send_cert_cell(or_connection_t *conn)
+{
+  const tor_cert_t *link_cert = NULL, *id_cert = NULL;
+  const uint8_t *link_encoded = NULL, *id_encoded = NULL;
+  size_t link_len, id_len;
+  var_cell_t *cell;
+  size_t cell_len;
+  ssize_t pos;
+  int server_mode;
+
+  tor_assert(conn->_base.state == OR_CONN_STATE_OR_HANDSHAKING_V3);
+
+  if (! conn->handshake_state)
+    return -1;
+  server_mode = ! conn->handshake_state->started_here;
+  if (tor_tls_get_my_certs(server_mode, &link_cert, &id_cert) < 0)
+    return -1;
+  tor_cert_get_der(link_cert, &link_encoded, &link_len);
+  tor_cert_get_der(id_cert, &id_encoded, &id_len);
+
+  cell_len = 1 /* 1 octet: num certs in cell */ +
+             2 * ( 1 + 2 ) /* For each cert: 1 octet for type, 2 for length */ +
+             link_len + id_len;
+  cell = var_cell_new(cell_len);
+  cell->command = CELL_CERT;
+  cell->payload[0] = 2;
+  pos = 1;
+
+  if (server_mode)
+    cell->payload[pos] = OR_CERT_TYPE_TLS_LINK; /* Link cert  */
+  else
+    cell->payload[pos] = OR_CERT_TYPE_AUTH_1024; /* client authentication */
+  set_uint16(&cell->payload[pos+1], htons(link_len));
+  memcpy(&cell->payload[pos+3], link_encoded, link_len);
+  pos += 3 + link_len;
+
+  cell->payload[pos] = OR_CERT_TYPE_ID_1024; /* ID cert */
+  set_uint16(&cell->payload[pos+1], htons(id_len));
+  memcpy(&cell->payload[pos+3], id_encoded, id_len);
+  pos += 3 + id_len;
+
+  tor_assert(pos == (int)cell_len); /* Otherwise we just smashed the heap */
+
+  connection_or_write_var_cell_to_buf(cell, conn);
+  var_cell_free(cell);
+
+  return 0;
+}
+
+/** Send an AUTH_CHALLENGE cell on the connection <b>conn</b>. Return 0
+ * on success, -1 on failure. */
+int
+connection_or_send_auth_challenge_cell(or_connection_t *conn)
+{
+  var_cell_t *cell;
+  uint8_t *cp;
+  uint8_t challenge[OR_AUTH_CHALLENGE_LEN];
+  tor_assert(conn->_base.state == OR_CONN_STATE_OR_HANDSHAKING_V3);
+
+  if (! conn->handshake_state)
+    return -1;
+
+  if (crypto_rand((char*)challenge, OR_AUTH_CHALLENGE_LEN) < 0)
+    return -1;
+  cell = var_cell_new(OR_AUTH_CHALLENGE_LEN + 4);
+  cell->command = CELL_AUTH_CHALLENGE;
+  memcpy(cell->payload, challenge, OR_AUTH_CHALLENGE_LEN);
+  cp = cell->payload + OR_AUTH_CHALLENGE_LEN;
+  set_uint16(cp, htons(1)); /* We recognize one authentication type. */
+  set_uint16(cp+2, htons(AUTHTYPE_RSA_SHA256_TLSSECRET));
+
+  connection_or_write_var_cell_to_buf(cell, conn);
+  var_cell_free(cell);
+  memset(challenge, 0, sizeof(challenge));
+
+  return 0;
+}
+
+/** Compute the main body of an AUTHENTICATE cell that a client can use
+ * to authenticate itself on a v3 handshake for <b>conn</b>.  Write it to the
+ * <b>outlen</b>-byte buffer at <b>out</b>.
+ *
+ * If <b>server</b> is true, only calculate the first
+ * V3_AUTH_FIXED_PART_LEN bytes -- the part of the authenticator that's
+ * determined by the rest of the handshake, and which match the provided value
+ * exactly.
+ *
+ * If <b>server</b> is false and <b>signing_key</b> is NULL, calculate the
+ * first V3_AUTH_BODY_LEN bytes of the authenticator (that is, everything
+ * that should be signed), but don't actually sign it.
+ *
+ * If <b>server</b> is false and <b>signing_key</b> is provided, calculate the
+ * entire authenticator, signed with <b>signing_key</b>.
+ * DOCDOC return value
+ */
+int
+connection_or_compute_authenticate_cell_body(or_connection_t *conn,
+                                             uint8_t *out, size_t outlen,
+                                             crypto_pk_env_t *signing_key,
+                                             int server)
+{
+  uint8_t *ptr;
+
+  /* assert state is reasonable XXXX */
+
+  if (outlen < V3_AUTH_FIXED_PART_LEN ||
+      (!server && outlen < V3_AUTH_BODY_LEN))
+    return -1;
+
+  ptr = out;
+
+  /* Type: 8 bytes. */
+  memcpy(ptr, "AUTH0001", 8);
+  ptr += 8;
+
+  {
+    const tor_cert_t *id_cert=NULL, *link_cert=NULL;
+    const digests_t *my_digests, *their_digests;
+    const uint8_t *my_id, *their_id, *client_id, *server_id;
+    if (tor_tls_get_my_certs(0, &link_cert, &id_cert))
+      return -1;
+    my_digests = tor_cert_get_id_digests(id_cert);
+    their_digests = tor_cert_get_id_digests(conn->handshake_state->id_cert);
+    tor_assert(my_digests);
+    tor_assert(their_digests);
+    my_id = (uint8_t*)my_digests->d[DIGEST_SHA256];
+    their_id = (uint8_t*)their_digests->d[DIGEST_SHA256];
+
+    client_id = server ? their_id : my_id;
+    server_id = server ? my_id : their_id;
+
+    /* Client ID digest: 32 octets. */
+    memcpy(ptr, client_id, 32);
+    ptr += 32;
+
+    /* Server ID digest: 32 octets. */
+    memcpy(ptr, server_id, 32);
+    ptr += 32;
+  }
+
+  {
+    crypto_digest_env_t *server_d, *client_d;
+    if (server) {
+      server_d = conn->handshake_state->digest_sent;
+      client_d = conn->handshake_state->digest_received;
+    } else {
+      client_d = conn->handshake_state->digest_sent;
+      server_d = conn->handshake_state->digest_received;
+    }
+
+    /* Server log digest : 32 octets */
+    crypto_digest_get_digest(server_d, (char*)ptr, 32);
+    ptr += 32;
+
+    /* Client log digest : 32 octets */
+    crypto_digest_get_digest(client_d, (char*)ptr, 32);
+    ptr += 32;
+  }
+
+  {
+    /* Digest of cert used on TLS link : 32 octets. */
+    const tor_cert_t *cert = NULL;
+    tor_cert_t *freecert = NULL;
+    if (server) {
+      tor_tls_get_my_certs(1, &cert, NULL);
+    } else {
+      freecert = tor_tls_get_peer_cert(conn->tls);
+      cert = freecert;
+    }
+    if (!cert)
+      return -1;
+    memcpy(ptr, tor_cert_get_cert_digests(cert)->d[DIGEST_SHA256], 32);
+
+    if (freecert)
+      tor_cert_free(freecert);
+    ptr += 32;
+  }
+
+  /* HMAC of clientrandom and serverrandom using master key : 32 octets */
+  tor_tls_get_tlssecrets(conn->tls, ptr);
+  ptr += 32;
+
+  tor_assert(ptr - out == V3_AUTH_FIXED_PART_LEN);
+
+  if (server)
+    return V3_AUTH_FIXED_PART_LEN; // ptr-out
+
+  /* Time: 8 octets. */
+  {
+    uint64_t now = time(NULL);
+    if ((time_t)now < 0)
+      return -1;
+    set_uint32(ptr, htonl((uint32_t)(now>>32)));
+    set_uint32(ptr+4, htonl((uint32_t)now));
+    ptr += 8;
+  }
+
+  /* Nonce: 16 octets. */
+  crypto_rand((char*)ptr, 16);
+  ptr += 16;
+
+  tor_assert(ptr - out == V3_AUTH_BODY_LEN);
+
+  if (!signing_key)
+    return V3_AUTH_BODY_LEN; // ptr - out
+
+  {
+    int siglen;
+    char d[32];
+    crypto_digest256(d, (char*)out, ptr-out, DIGEST_SHA256);
+    siglen = crypto_pk_private_sign(signing_key,
+                                    (char*)ptr, outlen - (ptr-out),
+                                    d, 32);
+    if (siglen < 0)
+      return -1;
+
+    ptr += siglen;
+    tor_assert(ptr <= out+outlen);
+    return (int)(ptr - out);
+  }
+}
+
+/** Send an AUTHENTICATE cell on the connection <b>conn</b>.  Return 0 on
+ * success, -1 on failure */
+int
+connection_or_send_authenticate_cell(or_connection_t *conn, int authtype)
+{
+  var_cell_t *cell;
+  crypto_pk_env_t *pk = tor_tls_get_my_client_auth_key();
+  int authlen;
+  size_t cell_maxlen;
+  /* XXXX make sure we're actually supposed to send this! */
+
+  if (!pk) {
+    log_warn(LD_BUG, "Unable to compute authenticate cell: no client auth key");
+    return -1;
+  }
+  if (authtype != AUTHTYPE_RSA_SHA256_TLSSECRET) {
+    log_warn(LD_BUG, "Tried to send authenticate cell with unknown "
+             "authentication type %d", authtype);
+    return -1;
+  }
+
+  cell_maxlen = 4 + /* overhead */
+    V3_AUTH_BODY_LEN + /* Authentication body */
+    crypto_pk_keysize(pk) + /* Max signature length */
+    16 /* add a few extra bytes just in case. */;
+
+  cell = var_cell_new(cell_maxlen);
+  cell->command = CELL_AUTHENTICATE;
+  set_uint16(cell->payload, htons(AUTHTYPE_RSA_SHA256_TLSSECRET));
+  /* skip over length ; we don't know that yet. */
+
+  authlen = connection_or_compute_authenticate_cell_body(conn,
+                                                         cell->payload+4,
+                                                         cell_maxlen-4,
+                                                         pk,
+                                                         0 /* not server */);
+  if (authlen < 0) {
+    log_warn(LD_BUG, "Unable to compute authenticate cell!");
+    var_cell_free(cell);
+    return -1;
+  }
+  tor_assert(authlen + 4 <= cell->payload_len);
+  set_uint16(cell->payload+2, htons(authlen));
+  cell->payload_len = authlen + 4;
+
+  connection_or_write_var_cell_to_buf(cell, conn);
+  var_cell_free(cell);
+
+  return 0;
+}
diff --git a/src/or/connection_or.h b/src/or/connection_or.h
index 072edbd8c..de3a989a6 100644
--- a/src/or/connection_or.h
+++ b/src/or/connection_or.h
@@ -41,7 +41,23 @@ void connection_or_report_broken_states(int severity, int domain);
 int connection_tls_start_handshake(or_connection_t *conn, int receiving);
 int connection_tls_continue_handshake(or_connection_t *conn);
 
+int connection_init_or_handshake_state(or_connection_t *conn, int started_here);
+void connection_or_init_conn_from_address(or_connection_t *conn,
+                                          const tor_addr_t *addr, uint16_t port,
+                                          const char *id_digest,
+                                          int started_here);
+int connection_or_client_learned_peer_id(or_connection_t *conn,
+                                         const uint8_t *peer_id);
+void connection_or_set_circid_type(or_connection_t *conn,
+                                   crypto_pk_env_t *identity_rcvd);
 void or_handshake_state_free(or_handshake_state_t *state);
+void or_handshake_state_record_cell(or_handshake_state_t *state,
+                                    const cell_t *cell,
+                                    int incoming);
+void or_handshake_state_record_var_cell(or_handshake_state_t *state,
+                                        const var_cell_t *cell,
+                                        int incoming);
+
 int connection_or_set_state_open(or_connection_t *conn);
 void connection_or_write_cell_to_buf(const cell_t *cell,
                                      or_connection_t *conn);
@@ -49,7 +65,16 @@ void connection_or_write_var_cell_to_buf(const var_cell_t *cell,
                                          or_connection_t *conn);
 int connection_or_send_destroy(circid_t circ_id, or_connection_t *conn,
                                int reason);
+int connection_or_send_versions(or_connection_t *conn, int v3_plus);
 int connection_or_send_netinfo(or_connection_t *conn);
+int connection_or_send_cert_cell(or_connection_t *conn);
+int connection_or_send_auth_challenge_cell(or_connection_t *conn);
+int connection_or_compute_authenticate_cell_body(or_connection_t *conn,
+                                                 uint8_t *out, size_t outlen,
+                                                 crypto_pk_env_t *signing_key,
+                                                 int server);
+int connection_or_send_authenticate_cell(or_connection_t *conn, int type);
+
 int is_or_protocol_version_known(uint16_t version);
 
 void cell_pack(packed_cell_t *dest, const cell_t *src);
diff --git a/src/or/or.h b/src/or/or.h
index d6eaeb6f1..6969a9cff 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -283,22 +283,27 @@ typedef enum {
 #define OR_CONN_STATE_CONNECTING 1
 /** State for a connection to an OR: waiting for proxy handshake to complete */
 #define OR_CONN_STATE_PROXY_HANDSHAKING 2
-/** State for a connection to an OR or client: SSL is handshaking, not done
+/** State for an OR connection client: SSL is handshaking, not done
  * yet. */
 #define OR_CONN_STATE_TLS_HANDSHAKING 3
 /** State for a connection to an OR: We're doing a second SSL handshake for
- * renegotiation purposes. */
+ * renegotiation purposes. (V2 handshake only.) */
 #define OR_CONN_STATE_TLS_CLIENT_RENEGOTIATING 4
 /** State for a connection at an OR: We're waiting for the client to
- * renegotiate. */
+ * renegotiate (to indicate a v2 handshake) or send a versions cell (to
+ * indicate a v3 handshake) */
 #define OR_CONN_STATE_TLS_SERVER_RENEGOTIATING 5
-/** State for a connection to an OR: We're done with our SSL handshake, but we
- * haven't yet negotiated link protocol versions and sent a netinfo cell.
- */
-#define OR_CONN_STATE_OR_HANDSHAKING 6
-/** State for a connection to an OR: Ready to send/receive cells. */
-#define OR_CONN_STATE_OPEN 7
-#define _OR_CONN_STATE_MAX 7
+/** State for an OR connection: We're done with our SSL handshake, we've done
+ * renegotiation, but we haven't yet negotiated link protocol versions and
+ * sent a netinfo cell. */
+#define OR_CONN_STATE_OR_HANDSHAKING_V2 6
+/** State for an OR connection: We're done with our SSL handshake, but we
+ * haven't yet negotiated link protocol versions, done a V3 handshake, and
+ * sent a netinfo cell. */
+#define OR_CONN_STATE_OR_HANDSHAKING_V3 7
+/** State for an OR connection: Ready to send/receive cells. */
+#define OR_CONN_STATE_OPEN 8
+#define _OR_CONN_STATE_MAX 8
 
 #define _EXIT_CONN_STATE_MIN 1
 /** State for an exit connection: waiting for response from DNS farm. */
@@ -820,9 +825,10 @@ typedef enum {
 #define CELL_NETINFO 8
 #define CELL_RELAY_EARLY 9
 
-/** True iff the cell command <b>x</b> is one that implies a variable-length
- * cell. */
-#define CELL_COMMAND_IS_VAR_LENGTH(x) ((x) == CELL_VERSIONS)
+#define CELL_VPADDING 128
+#define CELL_CERT 129
+#define CELL_AUTH_CHALLENGE 130
+#define CELL_AUTHENTICATE 131
 
 /** How long to test reachability before complaining to the user. */
 #define TIMEOUT_UNTIL_UNREACHABILITY_COMPLAINT (20*60)
@@ -1078,7 +1084,47 @@ typedef struct listener_connection_t {
 
 } listener_connection_t;
 
-/** Stores flags and information related to the portion of a v2 Tor OR
+/** Minimum length of the random part of an AUTH_CHALLENGE cell. */
+#define OR_AUTH_CHALLENGE_LEN 32
+
+/**
+ * @name Certificate types for CERT cells.
+ *
+ * These values are defined by the protocol, and affect how an X509
+ * certificate in a CERT cell is interpreted and used.
+ *
+ * @{ */
+/** A certificate that authenticates a TLS link key.  The subject key
+ * must match the key used in the TLS handshake; it must be signed by
+ * the identity key. */
+#define OR_CERT_TYPE_TLS_LINK 1
+/** A self-signed identity certificate. The subject key must be a
+ * 1024-bit RSA key. */
+#define OR_CERT_TYPE_ID_1024 2
+/** A certificate that authenticates a key used in an AUTHENTICATE cell
+ * in the v3 handshake.  The subject key must be a 1024-bit RSA key; it
+ * must be signed by the identity key */
+#define OR_CERT_TYPE_AUTH_1024 3
+/**@}*/
+
+/** The one currently supported type of AUTHENTICATE cell.  It contains
+ * a bunch of structures signed with an RSA1024 key.  The signed
+ * structures include a HMAC using negotiated TLS secrets, and a digest
+ * of all cells sent or received before the AUTHENTICATE cell (including
+ * the random server-generated AUTH_CHALLENGE cell).
+ */
+#define AUTHTYPE_RSA_SHA256_TLSSECRET 1
+
+/** The length of the part of the AUTHENTICATE cell body that the client and
+ * server can generate independently (when using RSA_SHA256_TLSSECRET). It
+ * contains everything except the client's timestamp, the client's randomly
+ * generated nonce, and the signature. */
+#define V3_AUTH_FIXED_PART_LEN (8+(32*6))
+/** The length of the part of the AUTHENTICATE cell body that the client
+ * signs. */
+#define V3_AUTH_BODY_LEN (V3_AUTH_FIXED_PART_LEN + 8 + 16)
+
+/** Stores flags and information related to the portion of a v2/v3 Tor OR
  * connection handshake that happens after the TLS handshake is finished.
  */
 typedef struct or_handshake_state_t {
@@ -1089,6 +1135,52 @@ typedef struct or_handshake_state_t {
   unsigned int started_here : 1;
   /** True iff we have received and processed a VERSIONS cell. */
   unsigned int received_versions : 1;
+  /** True iff we have received and processed an AUTH_CHALLENGE cell */
+  unsigned int received_auth_challenge : 1;
+  /** True iff we have received and processed a CERT cell. */
+  unsigned int received_cert_cell : 1;
+  /** True iff we have received and processed an AUTHENTICATE cell */
+  unsigned int received_authenticate : 1;
+
+  /* True iff we've received valid authentication to some identity. */
+  unsigned int authenticated : 1;
+
+  /** True iff we should feed outgoing cells into digest_sent and
+   * digest_received respectively.
+   *
+   * From the server's side of the v3 handshake, we want to capture everything
+   * from the VERSIONS cell through and including the AUTH_CHALLENGE cell.
+   * From the client's, we want to capture everything from the VERSIONS cell
+   * through but *not* including the AUTHENTICATE cell.
+   *
+   * @{ */
+  unsigned int digest_sent_data : 1;
+  unsigned int digest_received_data : 1;
+  /**@}*/
+
+  /** Identity digest that we have received and authenticated for our peer
+   * on this connection. */
+  uint8_t authenticated_peer_id[DIGEST_LEN];
+
+  /** Digests of the cells that we have sent or received as part of a V3
+   * handshake.  Used for making and checking AUTHENTICATE cells.
+   *
+   * @{
+   */
+  crypto_digest_env_t *digest_sent;
+  crypto_digest_env_t *digest_received;
+  /** @} */
+
+  /** Certificates that a connection initiator sent us in a CERT cell; we're
+   * holding on to them until we get an AUTHENTICATE cell.
+   *
+   * @{
+   */
+  /** The cert for the key that's supposed to sign the AUTHENTICATE cell */
+  tor_cert_t *auth_cert;
+  /** A self-signed identity certificate */
+  tor_cert_t *id_cert;
+  /**@}*/
 } or_handshake_state_t;
 
 /** Subtype of connection_t for an "OR connection" -- that is, one that speaks
diff --git a/src/test/test_crypto.c b/src/test/test_crypto.c
index dca0d3a28..1b338a29a 100644
--- a/src/test/test_crypto.c
+++ b/src/test/test_crypto.c
@@ -231,7 +231,7 @@ test_crypto_sha(void)
 {
   crypto_digest_env_t *d1 = NULL, *d2 = NULL;
   int i;
-  char key[80];
+  char key[160];
   char digest[32];
   char data[50];
   char d_out1[DIGEST_LEN], d_out2[DIGEST256_LEN];
@@ -276,6 +276,75 @@ test_crypto_sha(void)
   test_streq(hex_str(digest, 20),
              "AA4AE5E15272D00E95705637CE8A3B55ED402112");
 
+  /* Test HMAC-SHA256 with test cases from wikipedia and RFC 4231 */
+
+  /* Case empty (wikipedia) */
+  crypto_hmac_sha256(digest, "", 0, "", 0);
+  test_streq(hex_str(digest, 32),
+           "B613679A0814D9EC772F95D778C35FC5FF1697C493715653C6C712144292C5AD");
+
+  /* Case quick-brown (wikipedia) */
+  crypto_hmac_sha256(digest, "key", 3,
+                     "The quick brown fox jumps over the lazy dog", 43);
+  test_streq(hex_str(digest, 32),
+           "F7BC83F430538424B13298E6AA6FB143EF4D59A14946175997479DBC2D1A3CD8");
+
+  /* "Test Case 1" from RFC 4231 */
+  memset(key, 0x0b, 20);
+  crypto_hmac_sha256(digest, key, 20, "Hi There", 8);
+  test_memeq_hex(digest,
+                 "b0344c61d8db38535ca8afceaf0bf12b"
+                 "881dc200c9833da726e9376c2e32cff7");
+
+  /* "Test Case 2" from RFC 4231 */
+  memset(key, 0x0b, 20);
+  crypto_hmac_sha256(digest, "Jefe", 4, "what do ya want for nothing?", 28);
+  test_memeq_hex(digest,
+                 "5bdcc146bf60754e6a042426089575c7"
+                 "5a003f089d2739839dec58b964ec3843");
+
+  /* "Test case 3" from RFC 4231 */
+  memset(key, 0xaa, 20);
+  memset(data, 0xdd, 50);
+  crypto_hmac_sha256(digest, key, 20, data, 50);
+  test_memeq_hex(digest,
+                 "773ea91e36800e46854db8ebd09181a7"
+                 "2959098b3ef8c122d9635514ced565fe");
+
+  /* "Test case 4" from RFC 4231 */
+  base16_decode(key, 25,
+                "0102030405060708090a0b0c0d0e0f10111213141516171819", 50);
+  memset(data, 0xcd, 50);
+  crypto_hmac_sha256(digest, key, 25, data, 50);
+  test_memeq_hex(digest,
+                 "82558a389a443c0ea4cc819899f2083a"
+                 "85f0faa3e578f8077a2e3ff46729665b");
+
+  /* "Test case 5" from RFC 4231 */
+  memset(key, 0x0c, 20);
+  crypto_hmac_sha256(digest, key, 20, "Test With Truncation", 20);
+  test_memeq_hex(digest,
+                 "a3b6167473100ee06e0c796c2955552b");
+
+  /* "Test case 6" from RFC 4231 */
+  memset(key, 0xaa, 131);
+  crypto_hmac_sha256(digest, key, 131,
+                     "Test Using Larger Than Block-Size Key - Hash Key First",
+                     54);
+  test_memeq_hex(digest,
+                 "60e431591ee0b67f0d8a26aacbf5b77f"
+                 "8e0bc6213728c5140546040f0ee37f54");
+
+  /* "Test case 7" from RFC 4231 */
+  memset(key, 0xaa, 131);
+  crypto_hmac_sha256(digest, key, 131,
+                     "This is a test using a larger than block-size key and a "
+                     "larger than block-size data. The key needs to be hashed "
+                     "before being used by the HMAC algorithm.", 152);
+  test_memeq_hex(digest,
+                 "9b09ffa71b942fcb27635fbcd5b0e944"
+                 "bfdc63644f0713938a7f51535c3a35e2");
+
   /* Incremental digest code. */
   d1 = crypto_new_digest_env();
   test_assert(d1);