Merge branch 'feature_15055_v2'

14 files changed, 1141 insertions, 232 deletions

diff --git a/src/or/channel.c b/src/or/channel.c
index 75aab3cfef..939b7f93e4 100644
--- a/src/or/channel.c
+++ b/src/or/channel.c
@@ -3220,9 +3220,10 @@ channel_free_all(void)
 
 channel_t *
 channel_connect(const tor_addr_t *addr, uint16_t port,
-                const char *id_digest)
+                const char *id_digest,
+                const ed25519_public_key_t *ed_id)
 {
-  return channel_tls_connect(addr, port, id_digest);
+  return channel_tls_connect(addr, port, id_digest, ed_id);
 }
 
 /**
diff --git a/src/or/channel.h b/src/or/channel.h
index 44a3901991..7e7b2ec899 100644
--- a/src/or/channel.h
+++ b/src/or/channel.h
@@ -489,7 +489,8 @@ int channel_send_destroy(circid_t circ_id, channel_t *chan,
  */
 
 channel_t * channel_connect(const tor_addr_t *addr, uint16_t port,
-                            const char *id_digest);
+                            const char *id_digest,
+                            const ed25519_public_key_t *ed_id);
 
 channel_t * channel_get_for_extend(const char *digest,
                                    const tor_addr_t *target_addr,
diff --git a/src/or/channeltls.c b/src/or/channeltls.c
index 09cca95b64..1af75e6648 100644
--- a/src/or/channeltls.c
+++ b/src/or/channeltls.c
@@ -55,6 +55,7 @@
 #include "router.h"
 #include "routerlist.h"
 #include "scheduler.h"
+#include "torcert.h"
 
 /** How many CELL_PADDING cells have we received, ever? */
 uint64_t stats_n_padding_cells_processed = 0;
@@ -170,8 +171,10 @@ channel_tls_common_init(channel_tls_t *tlschan)
 
 channel_t *
 channel_tls_connect(const tor_addr_t *addr, uint16_t port,
-                    const char *id_digest)
+                    const char *id_digest,
+                    const ed25519_public_key_t *ed_id)
 {
+  (void) ed_id; // XXXX not fully used yet
   channel_tls_t *tlschan = tor_malloc_zero(sizeof(*tlschan));
   channel_t *chan = &(tlschan->base_);
 
@@ -198,7 +201,7 @@ channel_tls_connect(const tor_addr_t *addr, uint16_t port,
   channel_mark_outgoing(chan);
 
   /* Set up or_connection stuff */
-  tlschan->conn = connection_or_connect(addr, port, id_digest, tlschan);
+  tlschan->conn = connection_or_connect(addr, port, id_digest, ed_id, tlschan);
   /* connection_or_connect() will fill in tlschan->conn */
   if (!(tlschan->conn)) {
     chan->reason_for_closing = CHANNEL_CLOSE_FOR_ERROR;
@@ -1639,7 +1642,10 @@ channel_tls_process_netinfo_cell(cell_t *cell, channel_tls_t *chan)
       if (!(chan->conn->handshake_state->authenticated)) {
         tor_assert(tor_digest_is_zero(
                   (const char*)(chan->conn->handshake_state->
-                      authenticated_peer_id)));
+                      authenticated_rsa_peer_id)));
+        tor_assert(tor_mem_is_zero(
+                  (const char*)(chan->conn->handshake_state->
+                                authenticated_ed25519_peer_id.pubkey), 32));
         channel_set_circid_type(TLS_CHAN_TO_BASE(chan), NULL,
                chan->conn->link_proto < MIN_LINK_PROTO_FOR_WIDE_CIRC_IDS);
 
@@ -1647,7 +1653,8 @@ channel_tls_process_netinfo_cell(cell_t *cell, channel_tls_t *chan)
                   &(chan->conn->base_.addr),
                   chan->conn->base_.port,
                   (const char*)(chan->conn->handshake_state->
-                   authenticated_peer_id),
+                                authenticated_rsa_peer_id),
+                  NULL, // XXXX Ed key
                   0);
       }
     }
@@ -1744,6 +1751,41 @@ channel_tls_process_netinfo_cell(cell_t *cell, channel_tls_t *chan)
   assert_connection_ok(TO_CONN(chan->conn),time(NULL));
 }
 
+/** Types of certificates that we know how to parse from CERTS cells.  Each
+ * type corresponds to a different encoding format. */
+typedef enum cert_encoding_t {
+  CERT_ENCODING_UNKNOWN, /**< We don't recognize this. */
+  CERT_ENCODING_X509, /**< It's an RSA key, signed with RSA, encoded in x509.
+                   * (Actually, it might not be RSA. We test that later.) */
+  CERT_ENCODING_ED25519, /**< It's something signed with an Ed25519 key,
+                      * encoded asa a tor_cert_t.*/
+  CERT_ENCODING_RSA_CROSSCERT, /**< It's an Ed key signed with an RSA key. */
+} cert_encoding_t;
+
+/**
+ * Given one of the certificate type codes used in a CERTS cell,
+ * return the corresponding cert_encoding_t that we should use to parse
+ * the certificate.
+ */
+static cert_encoding_t
+certs_cell_typenum_to_cert_type(int typenum)
+{
+  switch (typenum) {
+  case CERTTYPE_RSA1024_ID_LINK:
+  case CERTTYPE_RSA1024_ID_ID:
+  case CERTTYPE_RSA1024_ID_AUTH:
+    return CERT_ENCODING_X509;
+  case CERTTYPE_ED_ID_SIGN:
+  case CERTTYPE_ED_SIGN_LINK:
+  case CERTTYPE_ED_SIGN_AUTH:
+    return CERT_ENCODING_ED25519;
+  case CERTTYPE_RSA1024_ID_EDID:
+    return CERT_ENCODING_RSA_CROSSCERT;
+  default:
+    return CERT_ENCODING_UNKNOWN;
+  }
+}
+
 /**
  * Process a CERTS cell from a channel.
  *
@@ -1763,14 +1805,21 @@ channel_tls_process_netinfo_cell(cell_t *cell, channel_tls_t *chan)
 STATIC void
 channel_tls_process_certs_cell(var_cell_t *cell, channel_tls_t *chan)
 {
-#define MAX_CERT_TYPE_WANTED OR_CERT_TYPE_AUTH_1024
-  tor_x509_cert_t *certs[MAX_CERT_TYPE_WANTED + 1];
+#define MAX_CERT_TYPE_WANTED CERTTYPE_RSA1024_ID_EDID
+  /* These arrays will be sparse, since a cert type can be at most one
+   * of ed/x509 */
+  tor_x509_cert_t *x509_certs[MAX_CERT_TYPE_WANTED + 1];
+  tor_cert_t *ed_certs[MAX_CERT_TYPE_WANTED + 1];
+  uint8_t *rsa_ed_cc_cert = NULL;
+  size_t rsa_ed_cc_cert_len = 0;
+
   int n_certs, i;
   certs_cell_t *cc = NULL;
 
   int send_netinfo = 0;
 
-  memset(certs, 0, sizeof(certs));
+  memset(x509_certs, 0, sizeof(x509_certs));
+  memset(ed_certs, 0, sizeof(ed_certs));
   tor_assert(cell);
   tor_assert(chan);
   tor_assert(chan->conn);
@@ -1814,77 +1863,145 @@ channel_tls_process_certs_cell(var_cell_t *cell, channel_tls_t *chan)
 
     if (cert_type > MAX_CERT_TYPE_WANTED)
       continue;
+    const cert_encoding_t ct = certs_cell_typenum_to_cert_type(cert_type);
+    switch (ct) {
+      default:
+      case CERT_ENCODING_UNKNOWN:
+        break;
+      case CERT_ENCODING_X509: {
+        tor_x509_cert_t *x509_cert = tor_x509_cert_decode(cert_body, cert_len);
+        if (!x509_cert) {
+          log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
+                 "Received undecodable certificate in CERTS cell from %s:%d",
+                 safe_str(chan->conn->base_.address),
+               chan->conn->base_.port);
+        } else {
+          if (x509_certs[cert_type]) {
+            tor_x509_cert_free(x509_cert);
+            ERR("Duplicate x509 certificate");
+          } else {
+            x509_certs[cert_type] = x509_cert;
+          }
+        }
+        break;
+      }
+      case CERT_ENCODING_ED25519: {
+        tor_cert_t *ed_cert = tor_cert_parse(cert_body, cert_len);
+        if (!ed_cert) {
+          log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
+                 "Received undecodable Ed certificate in CERTS cell from %s:%d",
+                 safe_str(chan->conn->base_.address),
+               chan->conn->base_.port);
+        } else {
+          if (ed_certs[cert_type]) {
+            tor_cert_free(ed_cert);
+            ERR("Duplicate Ed25519 certificate");
+          } else {
+            ed_certs[cert_type] = ed_cert;
+          }
+        }
+        break;
+      }
 
-    tor_x509_cert_t *cert = tor_x509_cert_decode(cert_body, cert_len);
-    if (!cert) {
-      log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
-             "Received undecodable certificate in CERTS cell from %s:%d",
-             safe_str(chan->conn->base_.address),
-             chan->conn->base_.port);
-    } else {
-      if (certs[cert_type]) {
-        tor_x509_cert_free(cert);
-        ERR("Duplicate x509 certificate");
-      } else {
-        certs[cert_type] = cert;
+     case CERT_ENCODING_RSA_CROSSCERT: {
+        if (rsa_ed_cc_cert) {
+          ERR("Duplicate RSA->Ed25519 crosscert");
+        } else {
+          rsa_ed_cc_cert = tor_memdup(cert_body, cert_len);
+          rsa_ed_cc_cert_len = cert_len;
+        }
+        break;
       }
     }
   }
 
-  tor_x509_cert_t *id_cert = certs[OR_CERT_TYPE_ID_1024];
-  tor_x509_cert_t *auth_cert = certs[OR_CERT_TYPE_AUTH_1024];
-  tor_x509_cert_t *link_cert = certs[OR_CERT_TYPE_TLS_LINK];
+  /* Move the certificates we (might) want into the handshake_state->certs
+   * structure. */
+  tor_x509_cert_t *id_cert = x509_certs[CERTTYPE_RSA1024_ID_ID];
+  tor_x509_cert_t *auth_cert = x509_certs[CERTTYPE_RSA1024_ID_AUTH];
+  tor_x509_cert_t *link_cert = x509_certs[CERTTYPE_RSA1024_ID_LINK];
+  chan->conn->handshake_state->certs->auth_cert = auth_cert;
+  chan->conn->handshake_state->certs->link_cert = link_cert;
+  chan->conn->handshake_state->certs->id_cert = id_cert;
+  x509_certs[CERTTYPE_RSA1024_ID_ID] =
+    x509_certs[CERTTYPE_RSA1024_ID_AUTH] =
+    x509_certs[CERTTYPE_RSA1024_ID_LINK] = NULL;
+
+  tor_cert_t *ed_id_sign = ed_certs[CERTTYPE_ED_ID_SIGN];
+  tor_cert_t *ed_sign_link = ed_certs[CERTTYPE_ED_SIGN_LINK];
+  tor_cert_t *ed_sign_auth = ed_certs[CERTTYPE_ED_SIGN_AUTH];
+  chan->conn->handshake_state->certs->ed_id_sign = ed_id_sign;
+  chan->conn->handshake_state->certs->ed_sign_link = ed_sign_link;
+  chan->conn->handshake_state->certs->ed_sign_auth = ed_sign_auth;
+  ed_certs[CERTTYPE_ED_ID_SIGN] =
+    ed_certs[CERTTYPE_ED_SIGN_LINK] =
+    ed_certs[CERTTYPE_ED_SIGN_AUTH] = NULL;
+
+  chan->conn->handshake_state->certs->ed_rsa_crosscert = rsa_ed_cc_cert;
+  chan->conn->handshake_state->certs->ed_rsa_crosscert_len =
+    rsa_ed_cc_cert_len;
+  rsa_ed_cc_cert = NULL;
+
+  int severity;
+  /* Note that this warns more loudly about time and validity if we were
+   * _trying_ to connect to an authority, not necessarily if we _did_ connect
+   * to one. */
+  if (chan->conn->handshake_state->started_here &&
+      router_digest_is_trusted_dir(TLS_CHAN_TO_BASE(chan)->identity_digest))
+    severity = LOG_WARN;
+  else
+    severity = LOG_PROTOCOL_WARN;
+
+  const ed25519_public_key_t *checked_ed_id = NULL;
+  const common_digests_t *checked_rsa_id = NULL;
+  or_handshake_certs_check_both(severity,
+                                chan->conn->handshake_state->certs,
+                                chan->conn->tls,
+                                time(NULL),
+                                &checked_ed_id,
+                                &checked_rsa_id);
+
+  if (!checked_rsa_id)
+    ERR("Invalid certificate chain!");
 
   if (chan->conn->handshake_state->started_here) {
-    int severity;
-    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(chan->conn->tls, link_cert)) {
-      ERR("The link certificate didn't match the TLS public key");
-    }
-    /* Note that this warns more loudly about time and validity if we were
-    * _trying_ to connect to an authority, not necessarily if we _did_ connect
-    * to one. */
-    if (router_digest_is_trusted_dir(
-          TLS_CHAN_TO_BASE(chan)->identity_digest))
-      severity = LOG_WARN;
-    else
-      severity = LOG_PROTOCOL_WARN;
-
-    if (! tor_tls_cert_is_valid(severity, link_cert, id_cert, 0))
-      ERR("The link certificate was not valid");
-    if (! tor_tls_cert_is_valid(severity, id_cert, id_cert, 1))
-      ERR("The ID certificate was not valid");
+    /* No more information is needed. */
 
     chan->conn->handshake_state->authenticated = 1;
+    chan->conn->handshake_state->authenticated_rsa = 1;
     {
-      const common_digests_t *id_digests =
-        tor_x509_cert_get_id_digests(id_cert);
+      const common_digests_t *id_digests = checked_rsa_id;
       crypto_pk_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);
-      if (!identity_rcvd)
-        ERR("Internal error: Couldn't get RSA key from ID cert.");
-      memcpy(chan->conn->handshake_state->authenticated_peer_id,
+      if (!identity_rcvd) {
+        ERR("Couldn't get RSA key from ID cert.");
+      }
+      memcpy(chan->conn->handshake_state->authenticated_rsa_peer_id,
              id_digests->d[DIGEST_SHA1], DIGEST_LEN);
       channel_set_circid_type(TLS_CHAN_TO_BASE(chan), identity_rcvd,
                 chan->conn->link_proto < MIN_LINK_PROTO_FOR_WIDE_CIRC_IDS);
       crypto_pk_free(identity_rcvd);
     }
 
+    if (checked_ed_id) {
+      chan->conn->handshake_state->authenticated_ed25519 = 1;
+      memcpy(&chan->conn->handshake_state->authenticated_ed25519_peer_id,
+             checked_ed_id, sizeof(ed25519_public_key_t));
+    }
+
     if (connection_or_client_learned_peer_id(chan->conn,
-            chan->conn->handshake_state->authenticated_peer_id) < 0)
+                  chan->conn->handshake_state->authenticated_rsa_peer_id,
+                  checked_ed_id) < 0)
       ERR("Problem setting or checking peer id");
 
     log_info(LD_OR,
-             "Got some good certificates from %s:%d: Authenticated it.",
-             safe_str(chan->conn->base_.address), chan->conn->base_.port);
-
-    chan->conn->handshake_state->id_cert = id_cert;
-    certs[OR_CERT_TYPE_ID_1024] = NULL;
+             "Got some good certificates from %s:%d: Authenticated it with "
+             "RSA%s",
+             safe_str(chan->conn->base_.address), chan->conn->base_.port,
+             checked_ed_id ? " and Ed25519" : "");
 
     if (!public_server_mode(get_options())) {
       /* If we initiated the connection and we are not a public server, we
@@ -1893,25 +2010,14 @@ channel_tls_process_certs_cell(var_cell_t *cell, channel_tls_t *chan)
       send_netinfo = 1;
     }
   } else {
-    if (! (id_cert && auth_cert))
-      ERR("The certs we wanted were missing");
-
-    /* Remember these certificates so we can check an AUTHENTICATE cell */
-    if (! tor_tls_cert_is_valid(LOG_PROTOCOL_WARN, auth_cert, id_cert, 1))
-      ERR("The authentication certificate was not valid");
-    if (! tor_tls_cert_is_valid(LOG_PROTOCOL_WARN, id_cert, id_cert, 1))
-      ERR("The ID certificate was not valid");
-
+    /* We can't call it authenticated till we see an AUTHENTICATE cell. */
     log_info(LD_OR,
-             "Got some good certificates from %s:%d: "
+             "Got some good RSA%s certificates from %s:%d. "
              "Waiting for AUTHENTICATE.",
+             checked_ed_id ? " and Ed25519" : "",
              safe_str(chan->conn->base_.address),
              chan->conn->base_.port);
     /* XXXX check more stuff? */
-
-    chan->conn->handshake_state->id_cert = id_cert;
-    chan->conn->handshake_state->auth_cert = auth_cert;
-    certs[OR_CERT_TYPE_ID_1024] = certs[OR_CERT_TYPE_AUTH_1024] = NULL;
   }
 
   chan->conn->handshake_state->received_certs_cell = 1;
@@ -1925,9 +2031,13 @@ channel_tls_process_certs_cell(var_cell_t *cell, channel_tls_t *chan)
   }
 
  err:
-  for (unsigned u = 0; u < ARRAY_LENGTH(certs); ++u) {
-    tor_x509_cert_free(certs[u]);
+  for (unsigned u = 0; u < ARRAY_LENGTH(x509_certs); ++u) {
+    tor_x509_cert_free(x509_certs[u]);
   }
+  for (unsigned u = 0; u < ARRAY_LENGTH(ed_certs); ++u) {
+    tor_cert_free(ed_certs[u]);
+  }
+  tor_free(rsa_ed_cc_cert);
   certs_cell_free(cc);
 #undef ERR
 }
@@ -1984,8 +2094,12 @@ channel_tls_process_auth_challenge_cell(var_cell_t *cell, channel_tls_t *chan)
   /* Now see if there is an authentication type we can use */
   for (i = 0; i < n_types; ++i) {
     uint16_t authtype = auth_challenge_cell_get_methods(ac, i);
-    if (authtype == AUTHTYPE_RSA_SHA256_TLSSECRET)
-      use_type = authtype;
+    if (authchallenge_type_is_supported(authtype)) {
+      if (use_type == -1 ||
+          authchallenge_type_is_better(authtype, use_type)) {
+        use_type = authtype;
+      }
+    }
   }
 
   chan->conn->handshake_state->received_auth_challenge = 1;
@@ -2000,9 +2114,10 @@ channel_tls_process_auth_challenge_cell(var_cell_t *cell, channel_tls_t *chan)
   if (use_type >= 0) {
     log_info(LD_OR,
              "Got an AUTH_CHALLENGE cell from %s:%d: Sending "
-             "authentication",
+             "authentication type %d",
              safe_str(chan->conn->base_.address),
-             chan->conn->base_.port);
+             chan->conn->base_.port,
+             use_type);
 
     if (connection_or_send_authenticate_cell(chan->conn, use_type) < 0) {
       log_warn(LD_OR,
@@ -2043,9 +2158,11 @@ channel_tls_process_auth_challenge_cell(var_cell_t *cell, channel_tls_t *chan)
 STATIC void
 channel_tls_process_authenticate_cell(var_cell_t *cell, channel_tls_t *chan)
 {
-  uint8_t expected[V3_AUTH_FIXED_PART_LEN+256];
+  var_cell_t *expected_cell = NULL;
   const uint8_t *auth;
   int authlen;
+  int authtype;
+  int bodylen;
 
   tor_assert(cell);
   tor_assert(chan);
@@ -2058,6 +2175,7 @@ channel_tls_process_authenticate_cell(var_cell_t *cell, channel_tls_t *chan)
            safe_str(chan->conn->base_.address),                 \
            chan->conn->base_.port, (s));                        \
     connection_or_close_for_error(chan->conn, 0);               \
+    var_cell_free(expected_cell);                               \
     return;                                                     \
   } while (0)
 
@@ -2075,9 +2193,7 @@ channel_tls_process_authenticate_cell(var_cell_t *cell, channel_tls_t *chan)
   }
   if (!(chan->conn->handshake_state->received_certs_cell))
     ERR("We never got a certs cell");
-  if (chan->conn->handshake_state->auth_cert == NULL)
-    ERR("We never got an authentication certificate");
-  if (chan->conn->handshake_state->id_cert == NULL)
+  if (chan->conn->handshake_state->certs->id_cert == NULL)
     ERR("We never got an identity certificate");
   if (cell->payload_len < 4)
     ERR("Cell was way too short");
@@ -2089,8 +2205,9 @@ channel_tls_process_authenticate_cell(var_cell_t *cell, channel_tls_t *chan)
     if (4 + len > cell->payload_len)
       ERR("Authenticator was truncated");
 
-    if (type != AUTHTYPE_RSA_SHA256_TLSSECRET)
+    if (! authchallenge_type_is_supported(type))
       ERR("Authenticator type was not recognized");
+    authtype = type;
 
     auth += 4;
     authlen = len;
@@ -2099,25 +2216,55 @@ channel_tls_process_authenticate_cell(var_cell_t *cell, channel_tls_t *chan)
   if (authlen < V3_AUTH_BODY_LEN + 1)
     ERR("Authenticator was too short");
 
-  ssize_t bodylen =
-    connection_or_compute_authenticate_cell_body(
-                        chan->conn, expected, sizeof(expected), NULL, 1);
-  if (bodylen < 0 || bodylen != V3_AUTH_FIXED_PART_LEN)
+  expected_cell = connection_or_compute_authenticate_cell_body(
+                chan->conn, authtype, NULL, NULL, 1);
+  if (! expected_cell)
     ERR("Couldn't compute expected AUTHENTICATE cell body");
 
-  if (tor_memneq(expected, auth, bodylen))
+  int sig_is_rsa;
+  if (authtype == AUTHTYPE_RSA_SHA256_TLSSECRET ||
+      authtype == AUTHTYPE_RSA_SHA256_RFC5705) {
+    bodylen = V3_AUTH_BODY_LEN;
+    sig_is_rsa = 1;
+  } else {
+    tor_assert(authtype == AUTHTYPE_ED25519_SHA256_RFC5705);
+    /* Our earlier check had better have made sure we had room
+     * for an ed25519 sig (inadvertently) */
+    tor_assert(V3_AUTH_BODY_LEN > ED25519_SIG_LEN);
+    bodylen = authlen - ED25519_SIG_LEN;
+    sig_is_rsa = 0;
+  }
+  if (expected_cell->payload_len != bodylen+4) {
+    ERR("Expected AUTHENTICATE cell body len not as expected.");
+  }
+
+  /* Length of random part. */
+  if (BUG(bodylen < 24)) {
+    // LCOV_EXCL_START
+    ERR("Bodylen is somehow less than 24, which should really be impossible");
+    // LCOV_EXCL_STOP
+  }
+
+  if (tor_memneq(expected_cell->payload+4, auth, bodylen-24))
     ERR("Some field in the AUTHENTICATE cell body was not as expected");
 
-  {
+  if (sig_is_rsa) {
+    if (chan->conn->handshake_state->certs->ed_id_sign != NULL)
+      ERR("RSA-signed AUTHENTICATE response provided with an ED25519 cert");
+
+    if (chan->conn->handshake_state->certs->auth_cert == NULL)
+      ERR("We never got an RSA authentication certificate");
+
     crypto_pk_t *pk = tor_tls_cert_get_key(
-                                   chan->conn->handshake_state->auth_cert);
+                             chan->conn->handshake_state->certs->auth_cert);
     char d[DIGEST256_LEN];
     char *signed_data;
     size_t keysize;
     int signed_len;
 
-    if (!pk)
-      ERR("Internal error: couldn't get RSA key from AUTH cert.");
+    if (! pk) {
+      ERR("Couldn't get RSA key from AUTH cert.");
+    }
     crypto_digest256(d, (char*)auth, V3_AUTH_BODY_LEN, DIGEST_SHA256);
 
     keysize = crypto_pk_keysize(pk);
@@ -2128,7 +2275,7 @@ channel_tls_process_authenticate_cell(var_cell_t *cell, channel_tls_t *chan)
     crypto_pk_free(pk);
     if (signed_len < 0) {
       tor_free(signed_data);
-      ERR("Signature wasn't valid");
+      ERR("RSA signature wasn't valid");
     }
     if (signed_len < DIGEST256_LEN) {
       tor_free(signed_data);
@@ -2141,22 +2288,46 @@ channel_tls_process_authenticate_cell(var_cell_t *cell, channel_tls_t *chan)
       ERR("Signature did not match data to be signed.");
     }
     tor_free(signed_data);
+  } else {
+    if (chan->conn->handshake_state->certs->ed_id_sign == NULL)
+      ERR("We never got an Ed25519 identity certificate.");
+    if (chan->conn->handshake_state->certs->ed_sign_auth == NULL)
+      ERR("We never got an Ed25519 authentication certificate.");
+
+    const ed25519_public_key_t *authkey =
+      &chan->conn->handshake_state->certs->ed_sign_auth->signed_key;
+    ed25519_signature_t sig;
+    tor_assert(authlen > ED25519_SIG_LEN);
+    memcpy(&sig.sig, auth + authlen - ED25519_SIG_LEN, ED25519_SIG_LEN);
+    if (ed25519_checksig(&sig, auth, authlen - ED25519_SIG_LEN, authkey)<0) {
+      ERR("Ed25519 signature wasn't valid.");
+    }
   }
 
   /* Okay, we are authenticated. */
   chan->conn->handshake_state->received_authenticate = 1;
   chan->conn->handshake_state->authenticated = 1;
+  chan->conn->handshake_state->authenticated_rsa = 1;
   chan->conn->handshake_state->digest_received_data = 0;
   {
     crypto_pk_t *identity_rcvd =
-      tor_tls_cert_get_key(chan->conn->handshake_state->id_cert);
+      tor_tls_cert_get_key(chan->conn->handshake_state->certs->id_cert);
     const common_digests_t *id_digests =
-      tor_x509_cert_get_id_digests(chan->conn->handshake_state->id_cert);
+      tor_x509_cert_get_id_digests(chan->conn->handshake_state->certs->id_cert);
+    const ed25519_public_key_t *ed_identity_received = NULL;
+
+    if (! sig_is_rsa) {
+      chan->conn->handshake_state->authenticated_ed25519 = 1;
+      ed_identity_received =
+        &chan->conn->handshake_state->certs->ed_id_sign->signing_key;
+      memcpy(&chan->conn->handshake_state->authenticated_ed25519_peer_id,
+             ed_identity_received, sizeof(ed25519_public_key_t));
+    }
 
     /* This must exist; we checked key type when reading the cert. */
     tor_assert(id_digests);
 
-    memcpy(chan->conn->handshake_state->authenticated_peer_id,
+    memcpy(chan->conn->handshake_state->authenticated_rsa_peer_id,
            id_digests->d[DIGEST_SHA1], DIGEST_LEN);
 
     channel_set_circid_type(TLS_CHAN_TO_BASE(chan), identity_rcvd,
@@ -2167,15 +2338,19 @@ channel_tls_process_authenticate_cell(var_cell_t *cell, channel_tls_t *chan)
                   &(chan->conn->base_.addr),
                   chan->conn->base_.port,
                   (const char*)(chan->conn->handshake_state->
-                    authenticated_peer_id),
+                    authenticated_rsa_peer_id),
+                  ed_identity_received,
                   0);
 
     log_info(LD_OR,
-             "Got an AUTHENTICATE cell from %s:%d: Looks good.",
+             "Got an AUTHENTICATE cell from %s:%d, type %d: Looks good.",
              safe_str(chan->conn->base_.address),
-             chan->conn->base_.port);
+             chan->conn->base_.port,
+             authtype);
   }
 
+  var_cell_free(expected_cell);
+
 #undef ERR
 }
 
diff --git a/src/or/channeltls.h b/src/or/channeltls.h
index 8b5863a461..729e595615 100644
--- a/src/or/channeltls.h
+++ b/src/or/channeltls.h
@@ -29,7 +29,8 @@ struct channel_tls_s {
 #endif /* TOR_CHANNEL_INTERNAL_ */
 
 channel_t * channel_tls_connect(const tor_addr_t *addr, uint16_t port,
-                                const char *id_digest);
+                                const char *id_digest,
+                                const ed25519_public_key_t *ed_id);
 channel_listener_t * channel_tls_get_listener(void);
 channel_listener_t * channel_tls_start_listener(void);
 channel_t * channel_tls_handle_incoming(or_connection_t *orconn);
diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c
index 50468b7158..b2fbd273a8 100644
--- a/src/or/circuitbuild.c
+++ b/src/or/circuitbuild.c
@@ -84,7 +84,10 @@ channel_connect_for_circuit(const tor_addr_t *addr, uint16_t port,
 {
   channel_t *chan;
 
-  chan = channel_connect(addr, port, id_digest);
+
+  chan = channel_connect(addr, port, id_digest,
+                         NULL // XXXX Ed25519 id.
+                         );
   if (chan) command_setup_channel(chan);
 
   return chan;
diff --git a/src/or/connection_or.c b/src/or/connection_or.c
index 267c32dda4..c6d5bb5250 100644
--- a/src/or/connection_or.c
+++ b/src/or/connection_or.c
@@ -49,9 +49,11 @@
 #include "relay.h"
 #include "rephist.h"
 #include "router.h"
+#include "routerkeys.h"
 #include "routerlist.h"
 #include "ext_orport.h"
 #include "scheduler.h"
+#include "torcert.h"
 
 static int connection_tls_finish_handshake(or_connection_t *conn);
 static int connection_or_launch_v3_or_handshake(or_connection_t *conn);
@@ -143,15 +145,18 @@ connection_or_clear_identity_map(void)
 /** Change conn->identity_digest to digest, and add conn into
  * orconn_digest_map. */
 static void
-connection_or_set_identity_digest(or_connection_t *conn, const char *digest)
+connection_or_set_identity_digest(or_connection_t *conn,
+                                  const char *rsa_digest,
+                                  const ed25519_public_key_t *ed_id)
 {
+  (void) ed_id; // DOCDOC // XXXX not implemented yet.
   or_connection_t *tmp;
   tor_assert(conn);
-  tor_assert(digest);
+  tor_assert(rsa_digest);
 
   if (!orconn_identity_map)
     orconn_identity_map = digestmap_new();
-  if (tor_memeq(conn->identity_digest, digest, DIGEST_LEN))
+  if (tor_memeq(conn->identity_digest, rsa_digest, DIGEST_LEN))
     return;
 
   /* If the identity was set previously, remove the old mapping. */
@@ -161,23 +166,23 @@ connection_or_set_identity_digest(or_connection_t *conn, const char *digest)
       channel_clear_identity_digest(TLS_CHAN_TO_BASE(conn->chan));
   }
 
-  memcpy(conn->identity_digest, digest, DIGEST_LEN);
+  memcpy(conn->identity_digest, rsa_digest, DIGEST_LEN);
 
   /* If we're setting the ID to zero, don't add a mapping. */
-  if (tor_digest_is_zero(digest))
+  if (tor_digest_is_zero(rsa_digest))
     return;
 
-  tmp = digestmap_set(orconn_identity_map, digest, conn);
+  tmp = digestmap_set(orconn_identity_map, rsa_digest, conn);
   conn->next_with_same_id = tmp;
 
   /* Deal with channels */
   if (conn->chan)
-    channel_set_identity_digest(TLS_CHAN_TO_BASE(conn->chan), digest);
+    channel_set_identity_digest(TLS_CHAN_TO_BASE(conn->chan), rsa_digest);
 
 #if 1
   /* Testing code to check for bugs in representation. */
   for (; tmp; tmp = tmp->next_with_same_id) {
-    tor_assert(tor_memeq(tmp->identity_digest, digest, DIGEST_LEN));
+    tor_assert(tor_memeq(tmp->identity_digest, rsa_digest, DIGEST_LEN));
     tor_assert(tmp != conn);
   }
 #endif
@@ -875,10 +880,12 @@ void
 connection_or_init_conn_from_address(or_connection_t *conn,
                                      const tor_addr_t *addr, uint16_t port,
                                      const char *id_digest,
+                                     const ed25519_public_key_t *ed_id,
                                      int started_here)
 {
+  (void) ed_id; // not fully used yet.
   const node_t *r = node_get_by_id(id_digest);
-  connection_or_set_identity_digest(conn, id_digest);
+  connection_or_set_identity_digest(conn, id_digest, ed_id);
   connection_or_update_token_buckets_helper(conn, 1, get_options());
 
   conn->base_.port = port;
@@ -1171,8 +1178,11 @@ connection_or_notify_error(or_connection_t *conn,
 
 MOCK_IMPL(or_connection_t *,
 connection_or_connect, (const tor_addr_t *_addr, uint16_t port,
-                        const char *id_digest, channel_tls_t *chan))
+                        const char *id_digest,
+                        const ed25519_public_key_t *ed_id,
+                        channel_tls_t *chan))
 {
+  (void) ed_id; // XXXX not fully used yet.
   or_connection_t *conn;
   const or_options_t *options = get_options();
   int socket_error = 0;
@@ -1203,7 +1213,7 @@ connection_or_connect, (const tor_addr_t *_addr, uint16_t port,
    */
   conn->chan = chan;
   chan->conn = conn;
-  connection_or_init_conn_from_address(conn, &addr, port, id_digest, 1);
+  connection_or_init_conn_from_address(conn, &addr, port, id_digest, ed_id, 1);
   connection_or_change_state(conn, OR_CONN_STATE_CONNECTING);
   control_event_or_conn_status(conn, OR_CONN_EVENT_LAUNCHED, 0);
 
@@ -1562,7 +1572,9 @@ connection_or_check_valid_tls_handshake(or_connection_t *conn,
 
   if (started_here)
     return connection_or_client_learned_peer_id(conn,
-                                     (const uint8_t*)digest_rcvd_out);
+                                        (const uint8_t*)digest_rcvd_out,
+                                        NULL // Ed25519 ID
+                                        );
 
   return 0;
 }
@@ -1592,12 +1604,16 @@ connection_or_check_valid_tls_handshake(or_connection_t *conn,
  */
 int
 connection_or_client_learned_peer_id(or_connection_t *conn,
-                                     const uint8_t *peer_id)
+                                     const uint8_t *rsa_peer_id,
+                                     const ed25519_public_key_t *ed_peer_id)
 {
+  (void) ed_peer_id; // not used yet.
+
   const or_options_t *options = get_options();
 
   if (tor_digest_is_zero(conn->identity_digest)) {
-    connection_or_set_identity_digest(conn, (const char*)peer_id);
+    connection_or_set_identity_digest(conn,
+                                      (const char*)rsa_peer_id, ed_peer_id);
     tor_free(conn->nickname);
     conn->nickname = tor_malloc(HEX_DIGEST_LEN+2);
     conn->nickname[0] = '$';
@@ -1609,14 +1625,14 @@ connection_or_client_learned_peer_id(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,
-                            (const char*)peer_id);
+                            (const char*)rsa_peer_id /*, ed_peer_id XXXX */);
   }
 
-  if (tor_memneq(peer_id, conn->identity_digest, DIGEST_LEN)) {
+  if (tor_memneq(rsa_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(seen, sizeof(seen), (const char*)rsa_peer_id, DIGEST_LEN);
     base16_encode(expected, sizeof(expected), conn->identity_digest,
                   DIGEST_LEN);
     const int using_hardcoded_fingerprints =
@@ -1669,7 +1685,7 @@ connection_or_client_learned_peer_id(or_connection_t *conn,
   }
   if (authdir_mode_tests_reachability(options)) {
     dirserv_orconn_tls_done(&conn->base_.addr, conn->base_.port,
-                            (const char*)peer_id);
+                            (const char*)rsa_peer_id /*, ed_id XXXX */);
   }
 
   return 0;
@@ -1725,7 +1741,8 @@ connection_tls_finish_handshake(or_connection_t *conn)
   if (tor_tls_used_v1_handshake(conn->tls)) {
     conn->link_proto = 1;
     connection_or_init_conn_from_address(conn, &conn->base_.addr,
-                                         conn->base_.port, digest_rcvd, 0);
+                                         conn->base_.port, digest_rcvd,
+                                         NULL, 0);
     tor_tls_block_renegotiation(conn->tls);
     rep_hist_note_negotiated_link_proto(1, started_here);
     return connection_or_set_state_open(conn);
@@ -1734,7 +1751,8 @@ connection_tls_finish_handshake(or_connection_t *conn)
     if (connection_init_or_handshake_state(conn, started_here) < 0)
       return -1;
     connection_or_init_conn_from_address(conn, &conn->base_.addr,
-                                         conn->base_.port, digest_rcvd, 0);
+                                         conn->base_.port, digest_rcvd,
+                                         NULL, 0);
     return connection_or_send_versions(conn, 0);
   }
 }
@@ -1773,6 +1791,8 @@ connection_init_or_handshake_state(or_connection_t *conn, int started_here)
   s->started_here = started_here ? 1 : 0;
   s->digest_sent_data = 1;
   s->digest_received_data = 1;
+  s->certs = or_handshake_certs_new();
+  s->certs->started_here = s->started_here;
   return 0;
 }
 
@@ -1784,8 +1804,7 @@ or_handshake_state_free(or_handshake_state_t *state)
     return;
   crypto_digest_free(state->digest_sent);
   crypto_digest_free(state->digest_received);
-  tor_x509_cert_free(state->auth_cert);
-  tor_x509_cert_free(state->id_cert);
+  or_handshake_certs_free(state->certs);
   memwipe(state, 0xBE, sizeof(or_handshake_state_t));
   tor_free(state);
 }
@@ -2132,57 +2151,171 @@ connection_or_send_netinfo,(or_connection_t *conn))
   return 0;
 }
 
+/** Helper used to add an encoded certs to a cert cell */
+static void
+add_certs_cell_cert_helper(certs_cell_t *certs_cell,
+                           uint8_t cert_type,
+                           const uint8_t *cert_encoded,
+                           size_t cert_len)
+{
+  tor_assert(cert_len <= UINT16_MAX);
+  certs_cell_cert_t *ccc = certs_cell_cert_new();
+  ccc->cert_type = cert_type;
+  ccc->cert_len = cert_len;
+  certs_cell_cert_setlen_body(ccc, cert_len);
+  memcpy(certs_cell_cert_getarray_body(ccc), cert_encoded, cert_len);
+
+  certs_cell_add_certs(certs_cell, ccc);
+}
+
+/** Add an encoded X509 cert (stored as <b>cert_len</b> bytes at
+ * <b>cert_encoded</b>) to the trunnel certs_cell_t object that we are
+ * building in <b>certs_cell</b>.  Set its type field to <b>cert_type</b>. */
+static void
+add_x509_cert(certs_cell_t *certs_cell,
+              uint8_t cert_type,
+              const tor_x509_cert_t *cert)
+{
+  if (NULL == cert)
+    return;
+
+  const uint8_t *cert_encoded = NULL;
+  size_t cert_len;
+  tor_x509_cert_get_der(cert, &cert_encoded, &cert_len);
+
+  add_certs_cell_cert_helper(certs_cell, cert_type, cert_encoded, cert_len);
+}
+
+/** Add an Ed25519 cert from <b>cert</b> to the trunnel certs_cell_t object
+ * that we are building in <b>certs_cell</b>.  Set its type field to
+ * <b>cert_type</b>. */
+static void
+add_ed25519_cert(certs_cell_t *certs_cell,
+                 uint8_t cert_type,
+                 const tor_cert_t *cert)
+{
+  if (NULL == cert)
+    return;
+
+  add_certs_cell_cert_helper(certs_cell, cert_type,
+                             cert->encoded, cert->encoded_len);
+}
+
 /** Send a CERTS cell on the connection <b>conn</b>.  Return 0 on success, -1
  * on failure. */
 int
 connection_or_send_certs_cell(or_connection_t *conn)
 {
   const tor_x509_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;
+
+  certs_cell_t *certs_cell = NULL;
 
   tor_assert(conn->base_.state == OR_CONN_STATE_OR_HANDSHAKING_V3);
 
   if (! conn->handshake_state)
     return -1;
+
   const int conn_in_server_mode = ! conn->handshake_state->started_here;
+
+  /* Get the encoded values of the X509 certificates */
   if (tor_tls_get_my_certs(conn_in_server_mode, &link_cert, &id_cert) < 0)
     return -1;
-  tor_x509_cert_get_der(link_cert, &link_encoded, &link_len);
-  tor_x509_cert_get_der(id_cert, &id_encoded, &id_len);
 
-  cell_len = 1 /* 1 byte: num certs in cell */ +
-             2 * ( 1 + 2 ) /* For each cert: 1 byte for type, 2 for length */ +
-             link_len + id_len;
-  cell = var_cell_new(cell_len);
-  cell->command = CELL_CERTS;
-  cell->payload[0] = 2;
-  pos = 1;
+  tor_assert(link_cert);
+  tor_assert(id_cert);
 
-  if (conn_in_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;
+  certs_cell = certs_cell_new();
 
-  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;
+  /* Start adding certs.  First the link cert or auth1024 cert. */
+  if (conn_in_server_mode) {
+    add_x509_cert(certs_cell,
+                  OR_CERT_TYPE_TLS_LINK, link_cert);
+  } else {
+    add_x509_cert(certs_cell,
+                  OR_CERT_TYPE_AUTH_1024, link_cert);
+  }
 
-  tor_assert(pos == (int)cell_len); /* Otherwise we just smashed the heap */
+  /* Next the RSA->RSA ID cert */
+  add_x509_cert(certs_cell,
+                OR_CERT_TYPE_ID_1024, id_cert);
+
+  /* Next the Ed25519 certs */
+  add_ed25519_cert(certs_cell,
+                   CERTTYPE_ED_ID_SIGN,
+                   get_master_signing_key_cert());
+  if (conn_in_server_mode) {
+    add_ed25519_cert(certs_cell,
+                     CERTTYPE_ED_SIGN_LINK,
+                     get_current_link_cert_cert());
+  } else {
+    add_ed25519_cert(certs_cell,
+                     CERTTYPE_ED_SIGN_AUTH,
+                     get_current_auth_key_cert());
+  }
+
+  /* And finally the crosscert. */
+  {
+    const uint8_t *crosscert=NULL;
+    size_t crosscert_len;
+    get_master_rsa_crosscert(&crosscert, &crosscert_len);
+    if (crosscert) {
+      add_certs_cell_cert_helper(certs_cell,
+                               CERTTYPE_RSA1024_ID_EDID,
+                               crosscert, crosscert_len);
+    }
+  }
+
+  /* We've added all the certs; make the cell. */
+  certs_cell->n_certs = certs_cell_getlen_certs(certs_cell);
+
+  ssize_t alloc_len = certs_cell_encoded_len(certs_cell);
+  tor_assert(alloc_len >= 0 && alloc_len <= UINT16_MAX);
+  cell = var_cell_new(alloc_len);
+  cell->command = CELL_CERTS;
+  ssize_t enc_len = certs_cell_encode(cell->payload, alloc_len, certs_cell);
+  tor_assert(enc_len > 0 && enc_len <= alloc_len);
+  cell->payload_len = enc_len;
 
   connection_or_write_var_cell_to_buf(cell, conn);
   var_cell_free(cell);
+  certs_cell_free(certs_cell);
 
   return 0;
 }
 
+/** Return true iff <b>challenge_type</b> is an AUTHCHALLENGE type that
+ * we can send and receive. */
+int
+authchallenge_type_is_supported(uint16_t challenge_type)
+{
+  switch (challenge_type) {
+     case AUTHTYPE_RSA_SHA256_TLSSECRET:
+     case AUTHTYPE_ED25519_SHA256_RFC5705:
+       return 1;
+     case AUTHTYPE_RSA_SHA256_RFC5705:
+     default:
+       return 0;
+  }
+}
+
+/** Return true iff <b>challenge_type_a</b> is one that we would rather
+ * use than <b>challenge_type_b</b>. */
+int
+authchallenge_type_is_better(uint16_t challenge_type_a,
+                             uint16_t challenge_type_b)
+{
+  /* Any supported type is better than an unsupported one;
+   * all unsupported types are equally bad. */
+  if (!authchallenge_type_is_supported(challenge_type_a))
+    return 0;
+  if (!authchallenge_type_is_supported(challenge_type_b))
+    return 1;
+  /* It happens that types are superior in numerically ascending order.
+   * If that ever changes, this must change too. */
+  return (challenge_type_a > challenge_type_b);
+}
+
 /** Send an AUTH_CHALLENGE cell on the connection <b>conn</b>. Return 0
  * on success, -1 on failure. */
 int
@@ -2197,17 +2330,26 @@ connection_or_send_auth_challenge_cell(or_connection_t *conn)
 
   auth_challenge_cell_t *ac = auth_challenge_cell_new();
 
+  tor_assert(sizeof(ac->challenge) == 32);
   crypto_rand((char*)ac->challenge, sizeof(ac->challenge));
 
   auth_challenge_cell_add_methods(ac, AUTHTYPE_RSA_SHA256_TLSSECRET);
+  /* Disabled, because everything that supports this method also supports
+   * the much-superior ED25519_SHA256_RFC5705 */
+  /* auth_challenge_cell_add_methods(ac, AUTHTYPE_RSA_SHA256_RFC5705); */
+  auth_challenge_cell_add_methods(ac, AUTHTYPE_ED25519_SHA256_RFC5705);
   auth_challenge_cell_set_n_methods(ac,
                                     auth_challenge_cell_getlen_methods(ac));
 
   cell = var_cell_new(auth_challenge_cell_encoded_len(ac));
   ssize_t len = auth_challenge_cell_encode(cell->payload, cell->payload_len,
                                            ac);
-  if (len != cell->payload_len)
+  if (len != cell->payload_len) {
+    /* LCOV_EXCL_START */
+    log_warn(LD_BUG, "Encoded auth challenge cell length not as expected");
     goto done;
+    /* LCOV_EXCL_STOP */
+  }
   cell->command = CELL_AUTH_CHALLENGE;
 
   connection_or_write_var_cell_to_buf(cell, conn);
@@ -2221,8 +2363,8 @@ connection_or_send_auth_challenge_cell(or_connection_t *conn)
 }
 
 /** 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>.
+ * to authenticate itself on a v3 handshake for <b>conn</b>.  Return it
+ * in a var_cell_t.
  *
  * If <b>server</b> is true, only calculate the first
  * V3_AUTH_FIXED_PART_LEN bytes -- the part of the authenticator that's
@@ -2238,24 +2380,44 @@ connection_or_send_auth_challenge_cell(or_connection_t *conn)
  *
  * Return the length of the cell body on success, and -1 on failure.
  */
-int
+var_cell_t *
 connection_or_compute_authenticate_cell_body(or_connection_t *conn,
-                                             uint8_t *out, size_t outlen,
+                                             const int authtype,
                                              crypto_pk_t *signing_key,
-                                             int server)
+                                      const ed25519_keypair_t *ed_signing_key,
+                                      int server)
 {
   auth1_t *auth = NULL;
   auth_ctx_t *ctx = auth_ctx_new();
-  int result;
+  var_cell_t *result = NULL;
+  int old_tlssecrets_algorithm = 0;
+  const char *authtype_str = NULL;
 
-  /* assert state is reasonable XXXX */
+  int is_ed = 0;
 
-  ctx->is_ed = 0;
+  /* assert state is reasonable XXXX */
+  switch (authtype) {
+  case AUTHTYPE_RSA_SHA256_TLSSECRET:
+    authtype_str = "AUTH0001";
+    old_tlssecrets_algorithm = 1;
+    break;
+  case AUTHTYPE_RSA_SHA256_RFC5705:
+    authtype_str = "AUTH0002";
+    break;
+  case AUTHTYPE_ED25519_SHA256_RFC5705:
+    authtype_str = "AUTH0003";
+    is_ed = 1;
+    break;
+  default:
+    tor_assert(0);
+    break;
+  }
 
   auth = auth1_new();
+  ctx->is_ed = is_ed;
 
   /* Type: 8 bytes. */
-  memcpy(auth1_getarray_type(auth), "AUTH0001", 8);
+  memcpy(auth1_getarray_type(auth), authtype_str, 8);
 
   {
     const tor_x509_cert_t *id_cert=NULL, *link_cert=NULL;
@@ -2265,7 +2427,7 @@ connection_or_compute_authenticate_cell_body(or_connection_t *conn,
       goto err;
     my_digests = tor_x509_cert_get_id_digests(id_cert);
     their_digests =
-      tor_x509_cert_get_id_digests(conn->handshake_state->id_cert);
+      tor_x509_cert_get_id_digests(conn->handshake_state->certs->id_cert);
     tor_assert(my_digests);
     tor_assert(their_digests);
     my_id = (uint8_t*)my_digests->d[DIGEST_SHA256];
@@ -2281,6 +2443,22 @@ connection_or_compute_authenticate_cell_body(or_connection_t *conn,
     memcpy(auth->sid, server_id, 32);
   }
 
+  if (is_ed) {
+    const ed25519_public_key_t *my_ed_id, *their_ed_id;
+    if (!conn->handshake_state->certs->ed_id_sign) {
+      log_warn(LD_OR, "Ed authenticate without Ed ID cert from peer.");
+      goto err;
+    }
+    my_ed_id = get_master_identity_key();
+    their_ed_id = &conn->handshake_state->certs->ed_id_sign->signing_key;
+
+    const uint8_t *cid_ed = (server ? their_ed_id : my_ed_id)->pubkey;
+    const uint8_t *sid_ed = (server ? my_ed_id : their_ed_id)->pubkey;
+
+    memcpy(auth->u1_cid_ed, cid_ed, ED25519_PUBKEY_LEN);
+    memcpy(auth->u1_sid_ed, sid_ed, ED25519_PUBKEY_LEN);
+  }
+
   {
     crypto_digest_t *server_d, *client_d;
     if (server) {
@@ -2309,7 +2487,8 @@ connection_or_compute_authenticate_cell_body(or_connection_t *conn,
       cert = freecert;
     }
     if (!cert) {
-      log_warn(LD_OR, "Unable to find cert when making AUTH1 data.");
+      log_warn(LD_OR, "Unable to find cert when making %s data.",
+               authtype_str);
       goto err;
     }
 
@@ -2321,36 +2500,79 @@ connection_or_compute_authenticate_cell_body(or_connection_t *conn,
   }
 
   /* HMAC of clientrandom and serverrandom using master key : 32 octets */
-  tor_tls_get_tlssecrets(conn->tls, auth->tlssecrets);
+  if (old_tlssecrets_algorithm) {
+    tor_tls_get_tlssecrets(conn->tls, auth->tlssecrets);
+  } else {
+    char label[128];
+    tor_snprintf(label, sizeof(label),
+                 "EXPORTER FOR TOR TLS CLIENT BINDING %s", authtype_str);
+    tor_tls_export_key_material(conn->tls, auth->tlssecrets,
+                                auth->cid, sizeof(auth->cid),
+                                label);
+  }
 
   /* 8 octets were reserved for the current time, but we're trying to get out
    * of the habit of sending time around willynilly.  Fortunately, nothing
    * checks it.  That's followed by 16 bytes of nonce. */
   crypto_rand((char*)auth->rand, 24);
 
+  ssize_t maxlen = auth1_encoded_len(auth, ctx);
+  if (ed_signing_key && is_ed) {
+    maxlen += ED25519_SIG_LEN;
+  } else if (signing_key && !is_ed) {
+    maxlen += crypto_pk_keysize(signing_key);
+  }
+
+  const int AUTH_CELL_HEADER_LEN = 4; /* 2 bytes of type, 2 bytes of length */
+  result = var_cell_new(AUTH_CELL_HEADER_LEN + maxlen);
+  uint8_t *const out = result->payload + AUTH_CELL_HEADER_LEN;
+  const size_t outlen = maxlen;
   ssize_t len;
+
+  result->command = CELL_AUTHENTICATE;
+  set_uint16(result->payload, htons(authtype));
+
   if ((len = auth1_encode(out, outlen, auth, ctx)) < 0) {
-    log_warn(LD_OR, "Unable to encode signed part of AUTH1 data.");
+    /* LCOV_EXCL_START */
+    log_warn(LD_BUG, "Unable to encode signed part of AUTH1 data.");
     goto err;
+    /* LCOV_EXCL_STOP */
   }
 
   if (server) {
     auth1_t *tmp = NULL;
     ssize_t len2 = auth1_parse(&tmp, out, len, ctx);
     if (!tmp) {
-      log_warn(LD_OR, "Unable to parse signed part of AUTH1 data.");
+      /* LCOV_EXCL_START */
+      log_warn(LD_BUG, "Unable to parse signed part of AUTH1 data that we just "
+               "encoded");
       goto err;
+      /* LCOV_EXCL_STOP */
     }
-    result = (int) (tmp->end_of_fixed_part - out);
+    result->payload_len = (tmp->end_of_signed - result->payload);
+
     auth1_free(tmp);
     if (len2 != len) {
-      log_warn(LD_OR, "Mismatched length when re-parsing AUTH1 data.");
+      /* LCOV_EXCL_START */
+      log_warn(LD_BUG, "Mismatched length when re-parsing AUTH1 data.");
       goto err;
+      /* LCOV_EXCL_STOP */
     }
     goto done;
   }
 
-  if (signing_key) {
+  if (ed_signing_key && is_ed) {
+    ed25519_signature_t sig;
+    if (ed25519_sign(&sig, out, len, ed_signing_key) < 0) {
+      /* LCOV_EXCL_START */
+      log_warn(LD_BUG, "Unable to sign ed25519 authentication data");
+      goto err;
+      /* LCOV_EXCL_STOP */
+    }
+    auth1_setlen_sig(auth, ED25519_SIG_LEN);
+    memcpy(auth1_getarray_sig(auth), sig.sig, ED25519_SIG_LEN);
+
+  } else if (signing_key && !is_ed) {
     auth1_setlen_sig(auth, crypto_pk_keysize(signing_key));
 
     char d[32];
@@ -2365,18 +2587,24 @@ connection_or_compute_authenticate_cell_body(or_connection_t *conn,
     }
 
     auth1_setlen_sig(auth, siglen);
+  }
 
-    len = auth1_encode(out, outlen, auth, ctx);
-    if (len < 0) {
-      log_warn(LD_OR, "Unable to encode signed AUTH1 data.");
-      goto err;
-    }
+  len = auth1_encode(out, outlen, auth, ctx);
+  if (len < 0) {
+    /* LCOV_EXCL_START */
+    log_warn(LD_BUG, "Unable to encode signed AUTH1 data.");
+    goto err;
+    /* LCOV_EXCL_STOP */
   }
-  result = (int) len;
+  tor_assert(len + AUTH_CELL_HEADER_LEN <= result->payload_len);
+  result->payload_len = len + AUTH_CELL_HEADER_LEN;
+  set_uint16(result->payload+2, htons(len));
+
   goto done;
 
  err:
-  result = -1;
+  var_cell_free(result);
+  result = NULL;
  done:
   auth1_free(auth);
   auth_ctx_free(ctx);
@@ -2390,44 +2618,29 @@ connection_or_send_authenticate_cell,(or_connection_t *conn, int authtype))
 {
   var_cell_t *cell;
   crypto_pk_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, "Can't compute authenticate cell: no client auth key");
     return -1;
   }
-  if (authtype != AUTHTYPE_RSA_SHA256_TLSSECRET) {
+  if (! authchallenge_type_is_supported(authtype)) {
     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) {
+  cell = connection_or_compute_authenticate_cell_body(conn,
+                                                 authtype,
+                                                 pk,
+                                                 get_current_auth_keypair(),
+                                                 0 /* not server */);
+  if (! cell) {
+    /* LCOV_EXCL_START */
     log_warn(LD_BUG, "Unable to compute authenticate cell!");
-    var_cell_free(cell);
     return -1;
+    /* LCOV_EXCL_STOP */
   }
-  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);
 
diff --git a/src/or/connection_or.h b/src/or/connection_or.h
index 2e8c6066cc..da95718ac9 100644
--- a/src/or/connection_or.h
+++ b/src/or/connection_or.h
@@ -40,7 +40,9 @@ void connection_or_notify_error(or_connection_t *conn,
 MOCK_DECL(or_connection_t *,
           connection_or_connect,
           (const tor_addr_t *addr, uint16_t port,
-           const char *id_digest, channel_tls_t *chan));
+           const char *id_digest,
+           const ed25519_public_key_t *ed_id,
+           channel_tls_t *chan));
 
 void connection_or_close_normally(or_connection_t *orconn, int flush);
 MOCK_DECL(void,connection_or_close_for_error,
@@ -59,10 +61,12 @@ int connection_init_or_handshake_state(or_connection_t *conn,
 void connection_or_init_conn_from_address(or_connection_t *conn,
                                           const tor_addr_t *addr,
                                           uint16_t port,
-                                          const char *id_digest,
+                                          const char *rsa_id_digest,
+                                          const ed25519_public_key_t *ed_id,
                                           int started_here);
 int connection_or_client_learned_peer_id(or_connection_t *conn,
-                                         const uint8_t *peer_id);
+                              const uint8_t *rsa_peer_id,
+                              const ed25519_public_key_t *ed_peer_id);
 time_t connection_or_client_used(or_connection_t *conn);
 MOCK_DECL(int, connection_or_get_num_circuits, (or_connection_t *conn));
 void or_handshake_state_free(or_handshake_state_t *state);
@@ -84,10 +88,14 @@ int connection_or_send_versions(or_connection_t *conn, int v3_plus);
 MOCK_DECL(int,connection_or_send_netinfo,(or_connection_t *conn));
 int connection_or_send_certs_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_t *signing_key,
-                                                 int server);
+int authchallenge_type_is_supported(uint16_t challenge_type);
+int authchallenge_type_is_better(uint16_t challenge_type_a,
+                                 uint16_t challenge_type_b);
+var_cell_t *connection_or_compute_authenticate_cell_body(or_connection_t *conn,
+                                       const int authtype,
+                                       crypto_pk_t *signing_key,
+                                       const ed25519_keypair_t *ed_signing_key,
+                                       int server);
 MOCK_DECL(int,connection_or_send_authenticate_cell,
           (or_connection_t *conn, int type));
 
diff --git a/src/or/dirserv.c b/src/or/dirserv.c
index 6e25323bf9..c797c9aa0e 100644
--- a/src/or/dirserv.c
+++ b/src/or/dirserv.c
@@ -3253,7 +3253,9 @@ dirserv_single_reachability_test(time_t now, routerinfo_t *router)
             router->nickname, fmt_addr32(router->addr), router->or_port);
   tor_addr_from_ipv4h(&router_addr, router->addr);
   chan = channel_tls_connect(&router_addr, router->or_port,
-                             router->cache_info.identity_digest);
+                             router->cache_info.identity_digest,
+                             NULL // XXXX Ed25519 ID.
+                             );
   if (chan) command_setup_channel(chan);
 
   /* Possible IPv6. */
@@ -3265,7 +3267,9 @@ dirserv_single_reachability_test(time_t now, routerinfo_t *router)
               tor_addr_to_str(addrstr, &router->ipv6_addr, sizeof(addrstr), 1),
               router->ipv6_orport);
     chan = channel_tls_connect(&router->ipv6_addr, router->ipv6_orport,
-                               router->cache_info.identity_digest);
+                               router->cache_info.identity_digest,
+                               NULL // XXXX Ed25519 ID.
+                               );
     if (chan) command_setup_channel(chan);
   }
 }
diff --git a/src/or/or.h b/src/or/or.h
index d0570a9249..1fc4b16e63 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -1348,13 +1348,34 @@ typedef struct listener_connection_t {
 #define OR_CERT_TYPE_RSA_ED_CROSSCERT 7
 /**@}*/
 
-/** The one currently supported type of AUTHENTICATE cell.  It contains
+/** The first 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
+/** As AUTHTYPE_RSA_SHA256_TLSSECRET, but instead of using the
+ * negotiated TLS secrets, uses exported keying material from the TLS
+ * session as described in RFC 5705.
+ *
+ * Not used by today's tors, since everything that supports this
+ * also supports ED25519_SHA3_5705, which is better.
+ **/
+#define AUTHTYPE_RSA_SHA256_RFC5705 2
+/** As AUTHTYPE_RSA_SHA256_RFC5705, but uses an Ed25519 identity key to
+ * authenticate.  */
+#define AUTHTYPE_ED25519_SHA256_RFC5705 3
+/*
+ * NOTE: authchallenge_type_is_better() relies on these AUTHTYPE codes
+ * being sorted in order of preference.  If we someday add one with
+ * a higher numerical value that we don't like as much, we should revise
+ * authchallenge_type_is_better().
+ */
+
+
+
+
 
 /** The length of the part of the AUTHENTICATE cell body that the client and
  * server can generate independently (when using RSA_SHA256_TLSSECRET). It
@@ -1365,6 +1386,34 @@ typedef struct listener_connection_t {
  * signs. */
 #define V3_AUTH_BODY_LEN (V3_AUTH_FIXED_PART_LEN + 8 + 16)
 
+/** Structure to hold all the certificates we've received on an OR connection
+ */
+typedef struct or_handshake_certs_t {
+  /** True iff we originated this connection. */
+  int started_here;
+  /** The cert for the 'auth' RSA key that's supposed to sign the AUTHENTICATE
+   * cell. Signed with the RSA identity key. */
+  tor_x509_cert_t *auth_cert;
+  /** The cert for the 'link' RSA key that was used to negotiate the TLS
+   *  connection.  Signed with the RSA identity key. */
+  tor_x509_cert_t *link_cert;
+  /** A self-signed identity certificate: the RSA identity key signed
+   * with itself.  */
+  tor_x509_cert_t *id_cert;
+  /** The Ed25519 signing key, signed with the Ed25519 identity key. */
+  struct tor_cert_st *ed_id_sign;
+  /** A digest of the X509 link certificate for the TLS connection, signed
+   * with the Ed25519 siging key. */
+  struct tor_cert_st *ed_sign_link;
+  /** The Ed25519 authentication key (that's supposed to sign an AUTHENTICATE
+   * cell) , signed with the Ed25519 siging key. */
+  struct tor_cert_st *ed_sign_auth;
+  /** The Ed25519 identity key, crosssigned with the RSA identity key. */
+  uint8_t *ed_rsa_crosscert;
+  /** The length of <b>ed_rsa_crosscert</b> in bytes */
+  size_t ed_rsa_crosscert_len;
+} or_handshake_certs_t;
+
 /** Stores flags and information related to the portion of a v2/v3 Tor OR
  * connection handshake that happens after the TLS handshake is finished.
  */
@@ -1385,6 +1434,8 @@ typedef struct or_handshake_state_t {
 
   /* True iff we've received valid authentication to some identity. */
   unsigned int authenticated : 1;
+  unsigned int authenticated_rsa : 1;
+  unsigned int authenticated_ed25519 : 1;
 
   /* True iff we have sent a netinfo cell */
   unsigned int sent_netinfo : 1;
@@ -1402,9 +1453,12 @@ typedef struct or_handshake_state_t {
   unsigned int digest_received_data : 1;
   /**@}*/
 
-  /** Identity digest that we have received and authenticated for our peer
+  /** Identity RSA digest that we have received and authenticated for our peer
    * on this connection. */
-  uint8_t authenticated_peer_id[DIGEST_LEN];
+  uint8_t authenticated_rsa_peer_id[DIGEST_LEN];
+  /** Identity Ed25519 public key that we have received and authenticated for
+   * our peer on this connection. */
+  ed25519_public_key_t authenticated_ed25519_peer_id;
 
   /** Digests of the cells that we have sent or received as part of a V3
    * handshake.  Used for making and checking AUTHENTICATE cells.
@@ -1417,14 +1471,8 @@ typedef struct or_handshake_state_t {
 
   /** Certificates that a connection initiator sent us in a CERTS 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_x509_cert_t *auth_cert;
-  /** A self-signed identity certificate */
-  tor_x509_cert_t *id_cert;
-  /**@}*/
+  or_handshake_certs_t *certs;
 } or_handshake_state_t;
 
 /** Length of Extended ORPort connection identifier. */
diff --git a/src/or/routerkeys.c b/src/or/routerkeys.c
index 7a1a2c9b2d..b6f20e6642 100644
--- a/src/or/routerkeys.c
+++ b/src/or/routerkeys.c
@@ -24,6 +24,7 @@
 #define ENC_KEY_HEADER "Boxed Ed25519 key"
 #define ENC_KEY_TAG "master"
 
+/* DOCDOC */
 static ssize_t
 do_getpass(const char *prompt, char *buf, size_t buflen,
            int twice, const or_options_t *options)
@@ -90,6 +91,7 @@ do_getpass(const char *prompt, char *buf, size_t buflen,
   return length;
 }
 
+/* DOCDOC */
 int
 read_encrypted_secret_key(ed25519_secret_key_t *out,
                           const char *fname)
@@ -162,6 +164,7 @@ read_encrypted_secret_key(ed25519_secret_key_t *out,
   return r;
 }
 
+/* DOCDOC */
 int
 write_encrypted_secret_key(const ed25519_secret_key_t *key,
                            const char *fname)
@@ -205,6 +208,7 @@ write_encrypted_secret_key(const ed25519_secret_key_t *key,
   return r;
 }
 
+/* DOCDOC */
 static int
 write_secret_key(const ed25519_secret_key_t *key, int encrypted,
                  const char *fname,
@@ -932,7 +936,18 @@ load_ed_keys(const or_options_t *options, time_t now)
   return -1;
 }
 
-/* DOCDOC */
+/**
+ * Retrieve our currently-in-use Ed25519 link certificate and id certificate,
+ * and, if they would expire soon (based on the time <b>now</b>, generate new
+ * certificates (without embedding the public part of the signing key inside).
+ *
+ * The signed_key from the expiring certificate will be used to sign the new
+ * key within newly generated X509 certificate.
+ *
+ * Returns -1 upon error.  Otherwise, returns 0 upon success (either when the
+ * current certificate is still valid, or when a new certificate was
+ * successfully generated).
+ */
 int
 generate_ed_link_cert(const or_options_t *options, time_t now)
 {
@@ -972,6 +987,17 @@ generate_ed_link_cert(const or_options_t *options, time_t now)
 #undef SET_KEY
 #undef SET_CERT
 
+/**
+ * Return 1 if any of the following are true:
+ *
+ *   - if one of our Ed25519 signing, auth, or link certificates would expire
+ *     soon w.r.t. the time <b>now</b>,
+ *   - if we do not currently have a link certificate, or
+ *   - if our cached Ed25519 link certificate is not same as the one we're
+ *     currently using.
+ *
+ * Otherwise, returns 0.
+ */
 int
 should_make_new_ed_keys(const or_options_t *options, const time_t now)
 {
@@ -1002,6 +1028,60 @@ should_make_new_ed_keys(const or_options_t *options, const time_t now)
 
 #undef EXPIRES_SOON
 
+#ifdef TOR_UNIT_TESTS
+/* Helper for unit tests: populate the ed25519 keys without saving or loading */
+void
+init_mock_ed_keys(const crypto_pk_t *rsa_identity_key)
+{
+  routerkeys_free_all();
+
+#define MAKEKEY(k)                                      \
+  k = tor_malloc_zero(sizeof(*k));                      \
+  if (ed25519_keypair_generate(k, 0) < 0) {             \
+    log_warn(LD_BUG, "Couldn't make a keypair");        \
+    goto err;                                           \
+  }
+  MAKEKEY(master_identity_key);
+  MAKEKEY(master_signing_key);
+  MAKEKEY(current_auth_key);
+#define MAKECERT(cert, signing, signed_, type, flags)            \
+  cert = tor_cert_create(signing,                                \
+                         type,                                   \
+                         &signed_->pubkey,                       \
+                         time(NULL), 86400,                      \
+                         flags);                                 \
+  if (!cert) {                                                   \
+    log_warn(LD_BUG, "Couldn't make a %s certificate!", #cert);  \
+    goto err;                                                    \
+  }
+
+  MAKECERT(signing_key_cert,
+           master_identity_key, master_signing_key, CERT_TYPE_ID_SIGNING,
+           CERT_FLAG_INCLUDE_SIGNING_KEY);
+  MAKECERT(auth_key_cert,
+           master_signing_key, current_auth_key, CERT_TYPE_SIGNING_AUTH, 0);
+
+  if (generate_ed_link_cert(get_options(), time(NULL)) < 0) {
+    log_warn(LD_BUG, "Couldn't make link certificate");
+    goto err;
+  }
+
+  rsa_ed_crosscert_len = tor_make_rsa_ed25519_crosscert(
+                                     &master_identity_key->pubkey,
+                                     rsa_identity_key,
+                                     time(NULL)+86400,
+                                     &rsa_ed_crosscert);
+
+  return;
+
+ err:
+  routerkeys_free_all();
+  tor_assert_nonfatal_unreached();
+}
+#undef MAKEKEY
+#undef MAKECERT
+#endif
+
 const ed25519_public_key_t *
 get_master_identity_key(void)
 {
@@ -1010,6 +1090,16 @@ get_master_identity_key(void)
   return &master_identity_key->pubkey;
 }
 
+#ifdef TOR_UNIT_TESTS
+/* only exists for the unit tests, since otherwise the identity key
+ * should be used to sign nothing but the signing key. */
+const ed25519_keypair_t *
+get_master_identity_keypair(void)
+{
+  return master_identity_key;
+}
+#endif
+
 const ed25519_keypair_t *
 get_master_signing_keypair(void)
 {
@@ -1144,9 +1234,12 @@ routerkeys_free_all(void)
   tor_cert_free(signing_key_cert);
   tor_cert_free(link_cert_cert);
   tor_cert_free(auth_key_cert);
+  tor_free(rsa_ed_crosscert);
 
   master_identity_key = master_signing_key = NULL;
   current_auth_key = NULL;
   signing_key_cert = link_cert_cert = auth_key_cert = NULL;
+  rsa_ed_crosscert = NULL; // redundant
+  rsa_ed_crosscert_len = 0;
 }
 
diff --git a/src/or/routerkeys.h b/src/or/routerkeys.h
index be9b19aea8..307a1cd234 100644
--- a/src/or/routerkeys.h
+++ b/src/or/routerkeys.h
@@ -73,5 +73,10 @@ int write_encrypted_secret_key(const ed25519_secret_key_t *out,
 
 void routerkeys_free_all(void);
 
+#ifdef TOR_UNIT_TESTS
+const ed25519_keypair_t *get_master_identity_keypair(void);
+void init_mock_ed_keys(const crypto_pk_t *rsa_identity_key);
+#endif
+
 #endif
 
diff --git a/src/or/routerparse.c b/src/or/routerparse.c
index 7f7d38234d..cb2bc72d0c 100644
--- a/src/or/routerparse.c
+++ b/src/or/routerparse.c
@@ -2100,12 +2100,13 @@ router_parse_entry_from_string(const char *s, const char *end,
 
       ed25519_checkable_t check[3];
       int check_ok[3];
-      if (tor_cert_get_checkable_sig(&check[0], cert, NULL) < 0) {
+      time_t expires = TIME_MAX;
+      if (tor_cert_get_checkable_sig(&check[0], cert, NULL, &expires) < 0) {
         log_err(LD_BUG, "Couldn't create 'checkable' for cert.");
         goto err;
       }
       if (tor_cert_get_checkable_sig(&check[1],
-                                     ntor_cc_cert, &ntor_cc_pk) < 0) {
+                               ntor_cc_cert, &ntor_cc_pk, &expires) < 0) {
         log_err(LD_BUG, "Couldn't create 'checkable' for ntor_cc_cert.");
         goto err;
       }
@@ -2135,10 +2136,7 @@ router_parse_entry_from_string(const char *s, const char *end,
       }
 
       /* We check this before adding it to the routerlist. */
-      if (cert->valid_until < ntor_cc_cert->valid_until)
-        router->cert_expiration_time = cert->valid_until;
-      else
-        router->cert_expiration_time = ntor_cc_cert->valid_until;
+      router->cert_expiration_time = expires;
     }
   }
 
@@ -2452,7 +2450,7 @@ extrainfo_parse_entry_from_string(const char *s, const char *end,
 
       ed25519_checkable_t check[2];
       int check_ok[2];
-      if (tor_cert_get_checkable_sig(&check[0], cert, NULL) < 0) {
+      if (tor_cert_get_checkable_sig(&check[0], cert, NULL, NULL) < 0) {
         log_err(LD_BUG, "Couldn't create 'checkable' for cert.");
         goto err;
       }
diff --git a/src/or/torcert.c b/src/or/torcert.c
index 37a201ea60..4259363f35 100644
--- a/src/or/torcert.c
+++ b/src/or/torcert.c
@@ -25,6 +25,8 @@
  * that one is authority_cert_t, and it's mostly handled in routerlist.c.
  */
 
+#include "or.h"
+#include "config.h"
 #include "crypto.h"
 #include "torcert.h"
 #include "ed25519_cert.h"
@@ -154,7 +156,11 @@ tor_cert_parse(const uint8_t *encoded, const size_t len)
   cert->encoded_len = len;
 
   memcpy(cert->signed_key.pubkey, parsed->certified_key, 32);
-  cert->valid_until = parsed->exp_field * 3600;
+  const int64_t valid_until_64 = ((int64_t)parsed->exp_field) * 3600;
+  if (valid_until_64 > TIME_MAX)
+    cert->valid_until = TIME_MAX - 1;
+  else
+    cert->valid_until = (time_t) valid_until_64;
   cert->cert_type = parsed->cert_type;
 
   for (unsigned i = 0; i < ed25519_cert_getlen_ext(parsed); ++i) {
@@ -181,11 +187,17 @@ tor_cert_parse(const uint8_t *encoded, const size_t len)
 }
 
 /** Fill in <b>checkable_out</b> with the information needed to check
- * the signature on <b>cert</b> with <b>pubkey</b>. */
+ * the signature on <b>cert</b> with <b>pubkey</b>.
+ *
+ * On success, if <b>expiration_out</b> is provided, and it is some time
+ * _after_ the expiration time of this certificate, set it to the
+ * expiration time of this certificate.
+ */
 int
 tor_cert_get_checkable_sig(ed25519_checkable_t *checkable_out,
                            const tor_cert_t *cert,
-                           const ed25519_public_key_t *pubkey)
+                           const ed25519_public_key_t *pubkey,
+                           time_t *expiration_out)
 {
   if (! pubkey) {
     if (cert->signing_key_included)
@@ -202,6 +214,10 @@ tor_cert_get_checkable_sig(ed25519_checkable_t *checkable_out,
   memcpy(checkable_out->signature.sig,
          cert->encoded + signed_len, ED25519_SIG_LEN);
 
+  if (expiration_out) {
+    *expiration_out = MIN(*expiration_out, cert->valid_until);
+  }
+
   return 0;
 }
 
@@ -216,14 +232,15 @@ tor_cert_checksig(tor_cert_t *cert,
 {
   ed25519_checkable_t checkable;
   int okay;
+  time_t expires = TIME_MAX;
 
-  if (now && now > cert->valid_until) {
-    cert->cert_expired = 1;
+  if (tor_cert_get_checkable_sig(&checkable, cert, pubkey, &expires) < 0)
     return -1;
-  }
 
-  if (tor_cert_get_checkable_sig(&checkable, cert, pubkey) < 0)
+  if (now && now > expires) {
+    cert->cert_expired = 1;
     return -1;
+  }
 
   if (ed25519_checksig_batch(&okay, &checkable, 1) < 0) {
     cert->sig_bad = 1;
@@ -272,6 +289,8 @@ tor_cert_opt_eq(const tor_cert_t *cert1, const tor_cert_t *cert2)
   return tor_cert_eq(cert1, cert2);
 }
 
+#define RSA_ED_CROSSCERT_PREFIX "Tor TLS RSA/Ed25519 cross-certificate"
+
 /** Create new cross-certification object to certify <b>ed_key</b> as the
  * master ed25519 identity key for the RSA identity key <b>rsa_key</b>.
  * Allocates and stores the encoded certificate in *<b>cert</b>, and returns
@@ -296,11 +315,21 @@ tor_make_rsa_ed25519_crosscert(const ed25519_public_key_t *ed_key,
   ssize_t sz = rsa_ed_crosscert_encode(res, alloc_sz, cc);
   tor_assert(sz > 0 && sz <= alloc_sz);
 
+  crypto_digest_t *d = crypto_digest256_new(DIGEST_SHA256);
+  crypto_digest_add_bytes(d, RSA_ED_CROSSCERT_PREFIX,
+                          strlen(RSA_ED_CROSSCERT_PREFIX));
+
   const int signed_part_len = 32 + 4;
+  crypto_digest_add_bytes(d, (char*)res, signed_part_len);
+
+  uint8_t digest[DIGEST256_LEN];
+  crypto_digest_get_digest(d, (char*)digest, sizeof(digest));
+  crypto_digest_free(d);
+
   int siglen = crypto_pk_private_sign(rsa_key,
                                       (char*)rsa_ed_crosscert_getarray_sig(cc),
                                       rsa_ed_crosscert_getlen_sig(cc),
-                                      (char*)res, signed_part_len);
+                                      (char*)digest, sizeof(digest));
   tor_assert(siglen > 0 && siglen <= (int)crypto_pk_keysize(rsa_key));
   tor_assert(siglen <= UINT8_MAX);
   cc->sig_len = siglen;
@@ -312,3 +341,310 @@ tor_make_rsa_ed25519_crosscert(const ed25519_public_key_t *ed_key,
   return sz;
 }
 
+/**
+ * Check whether the <b>crosscert_len</b> byte certificate in <b>crosscert</b>
+ * is in fact a correct cross-certification of <b>master_key</b> using
+ * the RSA key <b>rsa_id_key</b>.
+ *
+ * Also reject the certificate if it expired before
+ * <b>reject_if_expired_before</b>.
+ *
+ * Return 0 on success, negative on failure.
+ */
+int
+rsa_ed25519_crosscert_check(const uint8_t *crosscert,
+                            const size_t crosscert_len,
+                            const crypto_pk_t *rsa_id_key,
+                            const ed25519_public_key_t *master_key,
+                            const time_t reject_if_expired_before)
+{
+  rsa_ed_crosscert_t *cc = NULL;
+  int rv;
+
+#define ERR(code, s)                                            \
+  do {                                                          \
+    log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,                      \
+           "Received a bad RSA->Ed25519 crosscert: %s",         \
+           (s));                                                \
+    rv = (code);                                                \
+    goto err;                                                   \
+  } while (0)
+
+  if (BUG(crypto_pk_keysize(rsa_id_key) > PK_BYTES))
+    return -1;
+
+  if (BUG(!crosscert))
+    return -1;
+
+  ssize_t parsed_len = rsa_ed_crosscert_parse(&cc, crosscert, crosscert_len);
+  if (parsed_len < 0 || crosscert_len != (size_t)parsed_len) {
+    ERR(-2, "Unparseable or overlong crosscert");
+  }
+
+  if (tor_memneq(rsa_ed_crosscert_getarray_ed_key(cc),
+                 master_key->pubkey,
+                 ED25519_PUBKEY_LEN)) {
+    ERR(-3, "Crosscert did not match Ed25519 key");
+  }
+
+  const uint32_t expiration_date = rsa_ed_crosscert_get_expiration(cc);
+  const uint64_t expiration_time = expiration_date * 3600;
+
+  if (reject_if_expired_before < 0 ||
+      expiration_time < (uint64_t)reject_if_expired_before) {
+    ERR(-4, "Crosscert is expired");
+  }
+
+  const uint8_t *eos = rsa_ed_crosscert_get_end_of_signed(cc);
+  const uint8_t *sig = rsa_ed_crosscert_getarray_sig(cc);
+  const uint8_t siglen = rsa_ed_crosscert_get_sig_len(cc);
+  tor_assert(eos >= crosscert);
+  tor_assert((size_t)(eos - crosscert) <= crosscert_len);
+  tor_assert(siglen == rsa_ed_crosscert_getlen_sig(cc));
+
+  /* Compute the digest */
+  uint8_t digest[DIGEST256_LEN];
+  crypto_digest_t *d = crypto_digest256_new(DIGEST_SHA256);
+  crypto_digest_add_bytes(d, RSA_ED_CROSSCERT_PREFIX,
+                          strlen(RSA_ED_CROSSCERT_PREFIX));
+  crypto_digest_add_bytes(d, (char*)crosscert, eos-crosscert);
+  crypto_digest_get_digest(d, (char*)digest, sizeof(digest));
+  crypto_digest_free(d);
+
+  /* Now check the signature */
+  uint8_t signed_[PK_BYTES];
+  int signed_len = crypto_pk_public_checksig(rsa_id_key,
+                                          (char*)signed_, sizeof(signed_),
+                                          (char*)sig, siglen);
+  if (signed_len < DIGEST256_LEN) {
+    ERR(-5, "Bad signature, or length of signed data not as expected");
+  }
+
+  if (tor_memneq(digest, signed_, DIGEST256_LEN)) {
+    ERR(-6, "The signature was good, but it didn't match the data");
+  }
+
+  rv = 0;
+ err:
+  rsa_ed_crosscert_free(cc);
+  return rv;
+}
+
+/** Construct and return a new empty or_handshake_certs object */
+or_handshake_certs_t *
+or_handshake_certs_new(void)
+{
+  return tor_malloc_zero(sizeof(or_handshake_certs_t));
+}
+
+/** Release all storage held in <b>certs</b> */
+void
+or_handshake_certs_free(or_handshake_certs_t *certs)
+{
+  if (!certs)
+    return;
+
+  tor_x509_cert_free(certs->auth_cert);
+  tor_x509_cert_free(certs->link_cert);
+  tor_x509_cert_free(certs->id_cert);
+
+  tor_cert_free(certs->ed_id_sign);
+  tor_cert_free(certs->ed_sign_link);
+  tor_cert_free(certs->ed_sign_auth);
+  tor_free(certs->ed_rsa_crosscert);
+
+  memwipe(certs, 0xBD, sizeof(*certs));
+  tor_free(certs);
+}
+
+#undef ERR
+#define ERR(s)                                                  \
+  do {                                                          \
+    log_fn(severity, LD_PROTOCOL,                               \
+           "Received a bad CERTS cell: %s",                     \
+           (s));                                                \
+    return 0;                                                   \
+  } while (0)
+
+int
+or_handshake_certs_rsa_ok(int severity,
+                          or_handshake_certs_t *certs,
+                          tor_tls_t *tls,
+                          time_t now)
+{
+  tor_x509_cert_t *link_cert = certs->link_cert;
+  tor_x509_cert_t *auth_cert = certs->auth_cert;
+  tor_x509_cert_t *id_cert = certs->id_cert;
+
+  if (certs->started_here) {
+    if (! (id_cert && link_cert))
+      ERR("The certs we wanted (ID, Link) were missing");
+    if (! tor_tls_cert_matches_key(tls, link_cert))
+      ERR("The link certificate didn't match the TLS public key");
+    if (! tor_tls_cert_is_valid(severity, link_cert, id_cert, now, 0))
+      ERR("The link certificate was not valid");
+    if (! tor_tls_cert_is_valid(severity, id_cert, id_cert, now, 1))
+      ERR("The ID certificate was not valid");
+  } else {
+    if (! (id_cert && auth_cert))
+      ERR("The certs we wanted (ID, Auth) were missing");
+    if (! tor_tls_cert_is_valid(LOG_PROTOCOL_WARN, auth_cert, id_cert, now, 1))
+      ERR("The authentication certificate was not valid");
+    if (! tor_tls_cert_is_valid(LOG_PROTOCOL_WARN, id_cert, id_cert, now, 1))
+      ERR("The ID certificate was not valid");
+  }
+
+  return 1;
+}
+
+/** Check all the ed25519 certificates in <b>certs</b> against each other, and
+ * against the peer certificate in <b>tls</b> if appropriate.  On success,
+ * return 0; on failure, return a negative value and warn at level
+ * <b>severity</b> */
+int
+or_handshake_certs_ed25519_ok(int severity,
+                              or_handshake_certs_t *certs,
+                              tor_tls_t *tls,
+                              time_t now)
+{
+  ed25519_checkable_t check[10];
+  unsigned n_checkable = 0;
+  time_t expiration = TIME_MAX;
+
+#define ADDCERT(cert, pk)                                               \
+  do {                                                                  \
+    tor_assert(n_checkable < ARRAY_LENGTH(check));                      \
+    if (tor_cert_get_checkable_sig(&check[n_checkable++], cert, pk,     \
+                                   &expiration) < 0)                    \
+      ERR("Could not get checkable cert.");                             \
+  } while (0)
+
+  if (! certs->ed_id_sign || !certs->ed_id_sign->signing_key_included) {
+    ERR("No Ed25519 signing key");
+  }
+  ADDCERT(certs->ed_id_sign, NULL);
+
+  if (certs->started_here) {
+    if (! certs->ed_sign_link)
+      ERR("No Ed25519 link key");
+    {
+      /* check for a match with the TLS cert. */
+      tor_x509_cert_t *peer_cert = tor_tls_get_peer_cert(tls);
+      if (BUG(!peer_cert)) {
+        /* This is a bug, because if we got to this point, we are a connection
+         * that was initiated here, and we completed a TLS handshake. The
+         * other side *must* have given us a certificate! */
+        ERR("No x509 peer cert"); // LCOV_EXCL_LINE
+      }
+      const common_digests_t *peer_cert_digests =
+        tor_x509_cert_get_cert_digests(peer_cert);
+      int okay = tor_memeq(peer_cert_digests->d[DIGEST_SHA256],
+                           certs->ed_sign_link->signed_key.pubkey,
+                           DIGEST256_LEN);
+      tor_x509_cert_free(peer_cert);
+      if (!okay)
+        ERR("Link certificate does not match TLS certificate");
+    }
+
+    ADDCERT(certs->ed_sign_link, &certs->ed_id_sign->signed_key);
+
+  } else {
+    if (! certs->ed_sign_auth)
+      ERR("No Ed25519 link authentication key");
+    ADDCERT(certs->ed_sign_auth, &certs->ed_id_sign->signed_key);
+  }
+
+  if (expiration < now) {
+    ERR("At least one certificate expired.");
+  }
+
+  /* Okay, we've gotten ready to check all the Ed25519 certificates.
+   * Now, we are going to check the RSA certificate's cross-certification
+   * with the ED certificates.
+   *
+   * FFFF In the future, we might want to make this optional.
+   */
+
+  tor_x509_cert_t *rsa_id_cert = certs->id_cert;
+  if (!rsa_id_cert) {
+    ERR("Missing legacy RSA ID certificate");
+  }
+  if (! tor_tls_cert_is_valid(severity, rsa_id_cert, rsa_id_cert, now, 1)) {
+    ERR("The legacy RSA ID certificate was not valid");
+  }
+  if (! certs->ed_rsa_crosscert) {
+    ERR("Missing RSA->Ed25519 crosscert");
+  }
+  crypto_pk_t *rsa_id_key = tor_tls_cert_get_key(rsa_id_cert);
+  if (!rsa_id_key) {
+    ERR("RSA ID cert had no RSA key");
+  }
+
+  if (rsa_ed25519_crosscert_check(certs->ed_rsa_crosscert,
+                                  certs->ed_rsa_crosscert_len,
+                                  rsa_id_key,
+                                  &certs->ed_id_sign->signing_key,
+                                  now) < 0) {
+    crypto_pk_free(rsa_id_key);
+    ERR("Invalid RSA->Ed25519 crosscert");
+  }
+  crypto_pk_free(rsa_id_key);
+  rsa_id_key = NULL;
+
+  /* FFFF We could save a little time in the client case by queueing
+   * this batch to check it later, along with the signature from the
+   * AUTHENTICATE cell. That will change our data flow a bit, though,
+   * so I say "postpone". */
+
+  if (ed25519_checksig_batch(NULL, check, n_checkable) < 0) {
+    ERR("At least one Ed25519 certificate was badly signed");
+  }
+
+  return 1;
+}
+
+
+/**
+ * Check the Ed certificates and/or the RSA certificates, as appropriate.  If
+ * we obtained an Ed25519 identity, set *ed_id_out. If we obtained an RSA
+ * identity, set *rs_id_out. Otherwise, set them both to NULL.
+ */
+void
+or_handshake_certs_check_both(int severity,
+                              or_handshake_certs_t *certs,
+                              tor_tls_t *tls,
+                              time_t now,
+                              const ed25519_public_key_t **ed_id_out,
+                              const common_digests_t **rsa_id_out)
+{
+  tor_assert(ed_id_out);
+  tor_assert(rsa_id_out);
+
+  *ed_id_out = NULL;
+  *rsa_id_out = NULL;
+
+  if (certs->ed_id_sign) {
+    if (or_handshake_certs_ed25519_ok(severity, certs, tls, now)) {
+      tor_assert(certs->ed_id_sign);
+      tor_assert(certs->id_cert);
+
+      *ed_id_out = &certs->ed_id_sign->signing_key;
+      *rsa_id_out = tor_x509_cert_get_id_digests(certs->id_cert);
+
+      /* If we reached this point, we did not look at any of the
+       * subsidiary RSA certificates, so we'd better just remove them.
+       */
+      tor_x509_cert_free(certs->link_cert);
+      tor_x509_cert_free(certs->auth_cert);
+      certs->link_cert = certs->auth_cert = NULL;
+    }
+    /* We do _not_ fall through here.  If you provided us Ed25519
+     * certificates, we expect to verify them! */
+  } else {
+    /* No ed25519 keys given in the CERTS cell */
+    if (or_handshake_certs_rsa_ok(severity, certs, tls, now)) {
+      *rsa_id_out = tor_x509_cert_get_id_digests(certs->id_cert);
+    }
+  }
+
+}
diff --git a/src/or/torcert.h b/src/or/torcert.h
index 9c819c0abb..f7ca0ff521 100644
--- a/src/or/torcert.h
+++ b/src/or/torcert.h
@@ -57,8 +57,9 @@ tor_cert_t *tor_cert_parse(const uint8_t *cert, size_t certlen);
 void tor_cert_free(tor_cert_t *cert);
 
 int tor_cert_get_checkable_sig(ed25519_checkable_t *checkable_out,
-                                 const tor_cert_t *out,
-                                 const ed25519_public_key_t *pubkey);
+                               const tor_cert_t *out,
+                               const ed25519_public_key_t *pubkey,
+                               time_t *expiration_out);
 
 int tor_cert_checksig(tor_cert_t *cert,
                       const ed25519_public_key_t *pubkey, time_t now);
@@ -71,6 +72,28 @@ ssize_t tor_make_rsa_ed25519_crosscert(const ed25519_public_key_t *ed_key,
                                        const crypto_pk_t *rsa_key,
                                        time_t expires,
                                        uint8_t **cert);
+int rsa_ed25519_crosscert_check(const uint8_t *crosscert,
+                                const size_t crosscert_len,
+                                const crypto_pk_t *rsa_id_key,
+                                const ed25519_public_key_t *master_key,
+                                const time_t reject_if_expired_before);
+
+or_handshake_certs_t *or_handshake_certs_new(void);
+void or_handshake_certs_free(or_handshake_certs_t *certs);
+int or_handshake_certs_rsa_ok(int severity,
+                              or_handshake_certs_t *certs,
+                              tor_tls_t *tls,
+                              time_t now);
+int or_handshake_certs_ed25519_ok(int severity,
+                                  or_handshake_certs_t *certs,
+                                  tor_tls_t *tls,
+                                  time_t now);
+void or_handshake_certs_check_both(int severity,
+                              or_handshake_certs_t *certs,
+                              tor_tls_t *tls,
+                              time_t now,
+                              const ed25519_public_key_t **ed_id_out,
+                              const common_digests_t **rsa_id_out);
 
 #endif