prop220: Implement certificates and key storage/creation

For prop220, we have a new ed25519 certificate type. This patch
implements the code to create, parse, and validate those, along with
code for routers to maintain their own sets of certificates and
keys.  (Some parts of master identity key encryption are done, but
the implementation of that isn't finished)

9 files changed, 792 insertions, 4 deletions

diff --git a/src/or/config.h b/src/or/config.h
index b064f05321..e97248540c 100644
--- a/src/or/config.h
+++ b/src/or/config.h
@@ -61,6 +61,10 @@ char *options_get_datadir_fname2_suffix(const or_options_t *options,
  * get_datadir_fname2_suffix.  */
 #define get_datadir_fname2(sub1,sub2) \
   get_datadir_fname2_suffix((sub1), (sub2), NULL)
+/** Return a newly allocated string containing datadir/sub1/sub2 relative to
+ * opts.  See get_datadir_fname2_suffix.  */
+#define options_get_datadir_fname2(opts,sub1,sub2)                      \
+  options_get_datadir_fname2_suffix((opts),(sub1), (sub2), NULL)
 /** Return a newly allocated string containing datadir/sub1suffix.  See
  * get_datadir_fname2_suffix. */
 #define get_datadir_fname_suffix(sub1, suffix) \
diff --git a/src/or/include.am b/src/or/include.am
index b44e1099dc..a85b0dde05 100644
--- a/src/or/include.am
+++ b/src/or/include.am
@@ -71,12 +71,14 @@ LIBTOR_A_SOURCES = \
 	src/or/rephist.c				\
 	src/or/replaycache.c				\
 	src/or/router.c					\
+	src/or/routerkeys.c				\
 	src/or/routerlist.c				\
 	src/or/routerparse.c				\
 	src/or/routerset.c				\
 	src/or/scheduler.c				\
 	src/or/statefile.c				\
 	src/or/status.c					\
+	src/or/torcert.c				\
 	src/or/onion_ntor.c				\
 	$(evdns_source)					\
 	$(tor_platform_source)				\
@@ -87,7 +89,7 @@ src_or_libtor_testing_a_SOURCES = $(LIBTOR_A_SOURCES)
 
 #libtor_a_LIBADD = ../common/libor.a ../common/libor-crypto.a \
 #	../common/libor-event.a
-
+#src_or_libtor_a_LIBADD = src/trunnel/libor-trunnel.a
 
 src_or_tor_SOURCES = src/or/tor_main.c
 AM_CPPFLAGS += -I$(srcdir)/src/or -Isrc/or
@@ -109,7 +111,7 @@ src_or_libtor_testing_a_CFLAGS = $(AM_CFLAGS) $(TEST_CFLAGS)
 src_or_tor_LDFLAGS = @TOR_LDFLAGS_zlib@ @TOR_LDFLAGS_openssl@ @TOR_LDFLAGS_libevent@
 src_or_tor_LDADD = src/or/libtor.a src/common/libor.a \
 	src/common/libor-crypto.a $(LIBDONNA) \
-	src/common/libor-event.a \
+	src/common/libor-event.a src/trunnel/libor-trunnel.a \
 	@TOR_ZLIB_LIBS@ @TOR_LIB_MATH@ @TOR_LIBEVENT_LIBS@ @TOR_OPENSSL_LIBS@ \
 	@TOR_LIB_WS32@ @TOR_LIB_GDI@ @CURVE25519_LIBS@ @TOR_SYSTEMD_LIBS@
 
@@ -120,7 +122,7 @@ src_or_tor_cov_CFLAGS = $(AM_CFLAGS) $(TEST_CFLAGS)
 src_or_tor_cov_LDFLAGS = @TOR_LDFLAGS_zlib@ @TOR_LDFLAGS_openssl@ @TOR_LDFLAGS_libevent@
 src_or_tor_cov_LDADD = src/or/libtor-testing.a src/common/libor-testing.a \
 	src/common/libor-crypto-testing.a $(LIBDONNA) \
-	src/common/libor-event-testing.a \
+	src/common/libor-event-testing.a src/trunnel/libor-trunnel-testing.a \
 	@TOR_ZLIB_LIBS@ @TOR_LIB_MATH@ @TOR_LIBEVENT_LIBS@ @TOR_OPENSSL_LIBS@ \
 	@TOR_LIB_WS32@ @TOR_LIB_GDI@ @CURVE25519_LIBS@ @TOR_SYSTEMD_LIBS@
 TESTING_TOR_BINARY = ./src/or/tor-cov
@@ -180,12 +182,15 @@ ORHEADERS = \
 	src/or/rephist.h				\
 	src/or/replaycache.h				\
 	src/or/router.h					\
+	src/or/routerkeys.h				\
 	src/or/routerlist.h				\
+	src/or/routerkeys.h				\
 	src/or/routerset.h				\
 	src/or/routerparse.h				\
 	src/or/scheduler.h				\
 	src/or/statefile.h				\
-	src/or/status.h
+	src/or/status.h					\
+	src/or/torcert.h
 
 noinst_HEADERS+= $(ORHEADERS) micro-revision.i
 
diff --git a/src/or/main.c b/src/or/main.c
index bc89458e87..8b82a31d7a 100644
--- a/src/or/main.c
+++ b/src/or/main.c
@@ -51,6 +51,7 @@
 #include "rendservice.h"
 #include "rephist.h"
 #include "router.h"
+#include "routerkeys.h"
 #include "routerlist.h"
 #include "routerparse.h"
 #include "scheduler.h"
@@ -2648,6 +2649,7 @@ tor_free_all(int postfork)
     config_free_all();
     or_state_free_all();
     router_free_all();
+    routerkeys_free_all();
     policies_free_all();
   }
   if (!postfork) {
diff --git a/src/or/or.h b/src/or/or.h
index 19694a081f..2044e844c3 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -96,6 +96,7 @@
 #include "ht.h"
 #include "replaycache.h"
 #include "crypto_curve25519.h"
+#include "crypto_ed25519.h"
 #include "tor_queue.h"
 
 /* These signals are defined to help handle_control_signal work.
diff --git a/src/or/router.c b/src/or/router.c
index 2ddaa895fc..135561381f 100644
--- a/src/or/router.c
+++ b/src/or/router.c
@@ -26,6 +26,7 @@
 #include "relay.h"
 #include "rephist.h"
 #include "router.h"
+#include "routerkeys.h"
 #include "routerlist.h"
 #include "routerparse.h"
 #include "statefile.h"
@@ -861,6 +862,10 @@ init_keys(void)
     set_client_identity_key(prkey);
   }
 
+  /* 1d. Load all ed25519 keys */
+  if (load_ed_keys(options,now) < 0)
+    return -1;
+
   /* 2. Read onion key.  Make it if none is found. */
   keydir = get_datadir_fname2("keys", "secret_onion_key");
   log_info(LD_GENERAL,"Reading/making onion key \"%s\"...",keydir);
diff --git a/src/or/routerkeys.c b/src/or/routerkeys.c
new file mode 100644
index 0000000000..fb61c310bd
--- /dev/null
+++ b/src/or/routerkeys.c
@@ -0,0 +1,453 @@
+/* Copyright (c) 2014, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#include "or.h"
+#include "config.h"
+#include "routerkeys.h"
+#include "torcert.h"
+
+/**
+ * Read an ed25519 key and associated certificates from files beginning with
+ * <b>fname</b>, with certificate type <b>cert_type</b>.  On failure, return
+ * NULL; on success return the keypair.
+ *
+ * If INIT_ED_KEY_CREATE is set in <b>flags</b>, then create the key (and
+ * certificate if requested) if it doesn't exist, and save it to disk.
+ *
+ * If INIT_ED_KEY_NEEDCERT is set in <b>flags</b>, load/create a certificate
+ * too and store it in *<b>cert_out</b>.  Fail if the cert can't be
+ * found/created.  To create a certificate, <b>signing_key</b> must be set to
+ * the key that should sign it; <b>now</b> to the current time, and
+ * <b>lifetime</b> to the lifetime of the key.
+ *
+ * If INIT_ED_KEY_REPLACE is set in <b>flags</b>, then create and save new key
+ * whether we can read the old one or not.
+ *
+ * If INIT_ED_KEY_EXTRA_STRONG is set in <b>flags</b>, set the extra_strong
+ * flag when creating the secret key.
+ *
+ * If INIT_ED_KEY_INCLUDE_SIGNING_KEY_IN_CERT is set in <b>flags</b>, and
+ * we create a new certificate, create it with the signing key embedded.
+ *
+ * If INIT_ED_KEY_SPLIT is set in <b>flags</b>, and we create a new key,
+ * store the public key in a separate file from the secret key.
+ *
+ * If INIT_ED_KEY_MISSING_SECRET_OK is set in <b>flags</b>, and we find a
+ * public key file but no secret key file, return successfully anyway.
+ */
+ed25519_keypair_t *
+ed_key_init_from_file(const char *fname, uint32_t flags,
+                      int severity,
+                      const ed25519_keypair_t *signing_key,
+                      time_t now,
+                      time_t lifetime,
+                      uint8_t cert_type,
+                      struct tor_cert_st **cert_out)
+{
+  char *secret_fname = NULL;
+  char *public_fname = NULL;
+  char *cert_fname = NULL;
+  int created_pk = 0, created_sk = 0, created_cert = 0;
+  const int try_to_load = ! (flags & INIT_ED_KEY_REPLACE);
+
+  char tag[8];
+  tor_snprintf(tag, sizeof(tag), "type%d", (int)cert_type);
+
+  tor_cert_t *cert = NULL;
+  char *got_tag = NULL;
+  ed25519_keypair_t *keypair = tor_malloc_zero(sizeof(ed25519_keypair_t));
+
+  tor_asprintf(&secret_fname, "%s_secret_key", fname);
+  tor_asprintf(&public_fname, "%s_public_key", fname);
+  tor_asprintf(&cert_fname, "%s_cert", fname);
+
+  /* Try to read the secret key. */
+  const int have_secret = try_to_load &&
+    ed25519_seckey_read_from_file(&keypair->seckey,
+                                  &got_tag, secret_fname) == 0;
+
+  if (have_secret) {
+    if (strcmp(got_tag, tag)) {
+      tor_log(severity, LD_OR, "%s has wrong tag", secret_fname);
+      goto err;
+    }
+    /* Derive the public key */
+    if (ed25519_public_key_generate(&keypair->pubkey, &keypair->seckey)<0) {
+      tor_log(severity, LD_OR, "%s can't produce a public key", secret_fname);
+      goto err;
+    }
+  }
+
+  /* If it's absent and that's okay, try to read the pubkey. */
+  int found_public = 0;
+  if (!have_secret && try_to_load && (flags & INIT_ED_KEY_MISSING_SECRET_OK)) {
+    tor_free(got_tag);
+    found_public = ed25519_pubkey_read_from_file(&keypair->pubkey,
+                                                 &got_tag, public_fname) == 0;
+    if (found_public && strcmp(got_tag, tag)) {
+      tor_log(severity, LD_OR, "%s has wrong tag", public_fname);
+      goto err;
+    }
+  }
+
+  /* If it's absent, and we're not supposed to make a new keypair, fail. */
+  if (!have_secret && !found_public && !(flags & INIT_ED_KEY_CREATE))
+    goto err;
+
+  /* if it's absent, make a new keypair and save it. */
+  if (!have_secret && !found_public) {
+    const int split = !! (flags & INIT_ED_KEY_SPLIT);
+    tor_free(keypair);
+    keypair = ed_key_new(signing_key, flags, now, lifetime,
+                         cert_type, &cert);
+    if (!keypair) {
+      tor_log(severity, LD_OR, "Couldn't create keypair");
+      goto err;
+    }
+
+    created_pk = created_sk = created_cert = 1;
+    if (ed25519_seckey_write_to_file(&keypair->seckey, secret_fname, tag) < 0
+        ||
+        (split &&
+         ed25519_pubkey_write_to_file(&keypair->pubkey, public_fname, tag) < 0)
+        ||
+        (cert &&
+         crypto_write_tagged_contents_to_file(cert_fname, "ed25519v1-cert",
+                                 tag, cert->encoded, cert->encoded_len) < 0)) {
+      tor_log(severity, LD_OR, "Couldn't write keys or cert to file.");
+      goto err;
+    }
+    goto done;
+  }
+
+  /* If we're not supposed to get a cert, we're done. */
+  if (! (flags & INIT_ED_KEY_NEEDCERT))
+    goto done;
+
+  /* Read a cert. */
+  uint8_t certbuf[256];
+  ssize_t cert_body_len = crypto_read_tagged_contents_from_file(
+                 cert_fname, "ed25519v1-cert",
+                 &got_tag, certbuf, sizeof(certbuf));
+  if (cert_body_len >= 0 && !strcmp(got_tag, tag))
+    cert = tor_cert_parse(certbuf, cert_body_len);
+
+  /* If we got it, check it to the extent we can. */
+  if (cert) {
+    int bad_cert = 0;
+
+    if (! cert) {
+      tor_log(severity, LD_OR, "Cert was unparseable");
+      bad_cert = 1;
+    } else if (!tor_memeq(cert->signed_key.pubkey, keypair->pubkey.pubkey,
+                          ED25519_PUBKEY_LEN)) {
+      tor_log(severity, LD_OR, "Cert was for wrong key");
+      bad_cert = 1;
+    } else if (tor_cert_checksig(cert, &signing_key->pubkey, now) < 0 &&
+               (signing_key || cert->cert_expired)) {
+      tor_log(severity, LD_OR, "Can't check certificate");
+      bad_cert = 1;
+    }
+
+    if (bad_cert) {
+      tor_cert_free(cert);
+      cert = NULL;
+    }
+  }
+
+  /* If we got a cert, we're done. */
+  if (cert)
+    goto done;
+
+  /* If we didn't get a cert, and we're not supposed to make one, fail. */
+  if (!signing_key || !(flags & INIT_ED_KEY_CREATE))
+    goto err;
+
+  /* We have keys but not a certificate, so make one. */
+  uint32_t cert_flags = 0;
+  if (flags & INIT_ED_KEY_INCLUDE_SIGNING_KEY_IN_CERT)
+    cert_flags |= CERT_FLAG_INCLUDE_SIGNING_KEY;
+  cert = tor_cert_create(signing_key, cert_type,
+                         &keypair->pubkey,
+                         now, lifetime,
+                         cert_flags);
+
+  if (! cert)
+    goto err;
+
+  /* Write it to disk. */
+  created_cert = 1;
+  if (crypto_write_tagged_contents_to_file(cert_fname, "ed25519v1-cert",
+                             tag, cert->encoded, cert->encoded_len) < 0) {
+    tor_log(severity, LD_OR, "Couldn't write cert to disk.");
+    goto err;
+  }
+
+ done:
+  if (cert_out)
+    *cert_out = cert;
+  else
+    tor_cert_free(cert);
+
+  goto cleanup;
+
+ err:
+  memwipe(keypair, 0, sizeof(*keypair));
+  tor_free(keypair);
+  tor_cert_free(cert);
+  if (cert_out)
+    *cert_out = NULL;
+  if (created_sk)
+    unlink(secret_fname);
+  if (created_pk)
+    unlink(public_fname);
+  if (created_cert)
+    unlink(cert_fname);
+
+ cleanup:
+  tor_free(secret_fname);
+  tor_free(public_fname);
+  tor_free(cert_fname);
+
+  return keypair;
+}
+
+/**
+ * Create a new signing key and (optionally) certficiate; do not read or write
+ * from disk.  See ed_key_init_from_file() for more information.
+ */
+ed25519_keypair_t *
+ed_key_new(const ed25519_keypair_t *signing_key,
+           uint32_t flags,
+           time_t now,
+           time_t lifetime,
+           uint8_t cert_type,
+           struct tor_cert_st **cert_out)
+{
+  if (cert_out)
+    *cert_out = NULL;
+
+  const int extra_strong = !! (flags & INIT_ED_KEY_EXTRA_STRONG);
+  ed25519_keypair_t *keypair = tor_malloc_zero(sizeof(ed25519_keypair_t));
+  if (ed25519_keypair_generate(keypair, extra_strong) < 0)
+    goto err;
+
+  if (! (flags & INIT_ED_KEY_NEEDCERT))
+    return keypair;
+
+  tor_assert(signing_key);
+  tor_assert(cert_out);
+  uint32_t cert_flags = 0;
+  if (flags & INIT_ED_KEY_INCLUDE_SIGNING_KEY_IN_CERT)
+    cert_flags |= CERT_FLAG_INCLUDE_SIGNING_KEY;
+  tor_cert_t *cert = tor_cert_create(signing_key, cert_type,
+                                     &keypair->pubkey,
+                                     now, lifetime,
+                                     cert_flags);
+  if (! cert)
+    goto err;
+
+  *cert_out = cert;
+  return keypair;
+
+ err:
+  tor_free(keypair);
+  return NULL;
+}
+
+static ed25519_keypair_t *master_identity_key = NULL;
+static ed25519_keypair_t *master_signing_key = NULL;
+static ed25519_keypair_t *current_link_key = NULL;
+static ed25519_keypair_t *current_auth_key = NULL;
+static tor_cert_t *signing_key_cert = NULL;
+static tor_cert_t *link_key_cert = NULL;
+static tor_cert_t *auth_key_cert = NULL;
+
+/**
+ * Running as a server: load, reload, or refresh our ed25519 keys and
+ * certificates, creating and saving new ones as needed.
+ */
+int
+load_ed_keys(const or_options_t *options, time_t now)
+{
+  ed25519_keypair_t *id = NULL;
+  ed25519_keypair_t *sign = NULL;
+  ed25519_keypair_t *link = NULL;
+  ed25519_keypair_t *auth = NULL;
+  const ed25519_keypair_t *use_signing = NULL;
+  tor_cert_t *sign_cert = NULL;
+  tor_cert_t *link_cert = NULL;
+  tor_cert_t *auth_cert = NULL;
+
+#define FAIL(msg) do {                          \
+    log_warn(LD_OR, (msg));                     \
+    goto err;                                   \
+  } while (0)
+#define SET_KEY(key, newval) do {               \
+    ed25519_keypair_free(key);                  \
+    key = (newval);                             \
+  } while (0)
+#define SET_CERT(cert, newval) do {             \
+    tor_cert_free(cert);                        \
+    cert = (newval);                            \
+  } while (0)
+#define EXPIRES_SOON(cert, interval)            \
+  (!(cert) || (cert)->valid_until < now + (interval))
+
+  /* XXXX support encrypted identity keys fully */
+
+  /* XXXX use options. */
+  (void) options;
+
+  id = ed_key_init_from_file(
+               options_get_datadir_fname2(options, "keys", "ed25519_master_id"),
+                             (INIT_ED_KEY_CREATE|INIT_ED_KEY_SPLIT|
+                              INIT_ED_KEY_MISSING_SECRET_OK|
+                              INIT_ED_KEY_EXTRA_STRONG),
+                             LOG_WARN, NULL, 0, 0, 0, NULL);
+  if (!id)
+    FAIL("Missing identity key");
+
+  if (!master_signing_key || EXPIRES_SOON(signing_key_cert, 86400/*???*/)) {
+    uint32_t flags = (INIT_ED_KEY_CREATE|
+                      INIT_ED_KEY_EXTRA_STRONG|
+                      INIT_ED_KEY_NEEDCERT|
+                      INIT_ED_KEY_INCLUDE_SIGNING_KEY_IN_CERT);
+    const ed25519_keypair_t *sign_with_id = id;
+    if (master_signing_key) {
+      flags |= INIT_ED_KEY_REPLACE; /* it's expired, so force-replace it. */
+    }
+    if (tor_mem_is_zero((char*)id->seckey.seckey, sizeof(id->seckey))) {
+      sign_with_id = NULL;
+      flags &= ~INIT_ED_KEY_CREATE;
+    }
+    sign = ed_key_init_from_file(
+               options_get_datadir_fname2(options, "keys", "ed25519_signing"),
+                                 flags, LOG_WARN,
+                                 sign_with_id, now, 30*86400/*XXX option*/,
+                                 CERT_TYPE_ID_SIGNING, &sign_cert);
+    if (!sign)
+      FAIL("Missing signing key");
+    use_signing = sign;
+  } else {
+    use_signing = master_signing_key;
+  }
+
+  /* At this point we no longer need our secret identity key.  So wipe
+   * it, if we loaded it in the first place. */
+  memwipe(id->seckey.seckey, 0, sizeof(id->seckey));
+
+  if (!current_link_key || EXPIRES_SOON(link_key_cert, 7200/*???*/)) {
+    link = ed_key_new(use_signing, INIT_ED_KEY_NEEDCERT,
+                      now, 2*86400/*XXX option??*/,
+                      CERT_TYPE_SIGNING_LINK, &link_cert);
+
+    if (!link)
+      FAIL("Can't create link key");
+  }
+
+  if (!current_auth_key || EXPIRES_SOON(auth_key_cert, 7200)/*???*/) {
+    auth = ed_key_new(use_signing, INIT_ED_KEY_NEEDCERT,
+                      now, 2*86400/*XXX option??*/,
+                      CERT_TYPE_SIGNING_AUTH, &auth_cert);
+
+    if (!auth)
+      FAIL("Can't create auth key");
+  }
+
+  /* We've generated or loaded everything.  Put them in memory. */
+
+  if (! master_identity_key) {
+    SET_KEY(master_identity_key, id);
+  } else {
+    tor_free(id);
+  }
+  if (sign) {
+    SET_KEY(master_signing_key, sign);
+    SET_CERT(signing_key_cert, sign_cert);
+  }
+  if (link) {
+    SET_KEY(current_link_key, link);
+    SET_CERT(link_key_cert, link_cert);
+  }
+  if (auth) {
+    SET_KEY(current_auth_key, auth);
+    SET_CERT(auth_key_cert, auth_cert);
+  }
+
+  return 0;
+ err:
+  ed25519_keypair_free(id);
+  ed25519_keypair_free(sign);
+  ed25519_keypair_free(link);
+  ed25519_keypair_free(auth);
+  tor_cert_free(sign_cert);
+  tor_cert_free(link_cert);
+  tor_cert_free(auth_cert);
+  return -1;
+#undef FAIL
+#undef SET_KEY
+#undef SET_CERT
+#undef EXPIRES_SOON
+}
+
+const ed25519_public_key_t *
+get_master_identity_key(void)
+{
+  if (!master_identity_key)
+    return NULL;
+  return &master_identity_key->pubkey;
+}
+
+const ed25519_keypair_t *
+get_master_signing_keypair(void)
+{
+  return master_signing_key;
+}
+
+const struct tor_cert_st *
+get_master_signing_key_cert(void)
+{
+  return signing_key_cert;
+}
+
+const ed25519_keypair_t *
+get_current_link_keypair(void)
+{
+  return current_link_key;
+}
+
+const ed25519_keypair_t *
+get_current_auth_keypair(void)
+{
+  return current_auth_key;
+}
+
+const tor_cert_t *
+get_current_link_key_cert(void)
+{
+  return link_key_cert;
+}
+
+const tor_cert_t *
+get_current_auth_key_cert(void)
+{
+  return auth_key_cert;
+}
+
+void
+routerkeys_free_all(void)
+{
+  ed25519_keypair_free(master_identity_key);
+  ed25519_keypair_free(master_signing_key);
+  ed25519_keypair_free(current_link_key);
+  ed25519_keypair_free(current_auth_key);
+  tor_cert_free(signing_key_cert);
+  tor_cert_free(link_key_cert);
+  tor_cert_free(auth_key_cert);
+
+  master_identity_key = master_signing_key = NULL;
+  current_link_key = current_auth_key = NULL;
+  signing_key_cert = link_key_cert = auth_key_cert = NULL;
+}
+
diff --git a/src/or/routerkeys.h b/src/or/routerkeys.h
new file mode 100644
index 0000000000..eb21401d56
--- /dev/null
+++ b/src/or/routerkeys.h
@@ -0,0 +1,44 @@
+/* Copyright (c) 2014, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#ifndef TOR_ROUTERKEYS_H
+#define TOR_ROUTERKEYS_H
+
+#include "crypto_ed25519.h"
+
+#define INIT_ED_KEY_CREATE                      (1u<<0)
+#define INIT_ED_KEY_REPLACE                     (1u<<1)
+#define INIT_ED_KEY_SPLIT                       (1u<<2)
+#define INIT_ED_KEY_MISSING_SECRET_OK           (1u<<3)
+#define INIT_ED_KEY_NEEDCERT                    (1u<<4)
+#define INIT_ED_KEY_EXTRA_STRONG                (1u<<5)
+#define INIT_ED_KEY_INCLUDE_SIGNING_KEY_IN_CERT (1u<<6)
+
+struct tor_cert_st;
+ed25519_keypair_t *ed_key_init_from_file(const char *fname, uint32_t flags,
+                                         int severity,
+                                         const ed25519_keypair_t *signing_key,
+                                         time_t now,
+                                         time_t lifetime,
+                                         uint8_t cert_type,
+                                         struct tor_cert_st **cert_out);
+ed25519_keypair_t *ed_key_new(const ed25519_keypair_t *signing_key,
+                              uint32_t flags,
+                              time_t now,
+                              time_t lifetime,
+                              uint8_t cert_type,
+                              struct tor_cert_st **cert_out);
+const ed25519_public_key_t *get_master_identity_key(void);
+const ed25519_keypair_t *get_master_signing_keypair(void);
+const struct tor_cert_st *get_master_signing_key_cert(void);
+
+const ed25519_keypair_t *get_current_link_keypair(void);
+const ed25519_keypair_t *get_current_auth_keypair(void);
+const struct tor_cert_st *get_current_link_key_cert(void);
+const struct tor_cert_st *get_current_auth_key_cert(void);
+
+int load_ed_keys(const or_options_t *options, time_t now);
+void routerkeys_free_all(void);
+
+#endif
+
diff --git a/src/or/torcert.c b/src/or/torcert.c
new file mode 100644
index 0000000000..478ec4d5ac
--- /dev/null
+++ b/src/or/torcert.c
@@ -0,0 +1,208 @@
+/* Copyright (c) 2014, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#include "torcert.h"
+#include "crypto.h"
+#include "ed25519_cert.h"
+#include "torlog.h"
+#include "util.h"
+#include "compat.h"
+
+/** Helper for tor_cert_create(): signs any 32 bytes, not just an ed25519
+ * key.
+ */
+static tor_cert_t *
+tor_cert_sign_impl(const ed25519_keypair_t *signing_key,
+                      uint8_t cert_type,
+                      uint8_t signed_key_type,
+                      const uint8_t signed_key_info[32],
+                      time_t now, time_t lifetime,
+                      uint32_t flags)
+{
+  tor_cert_t *torcert = NULL;
+
+  ed25519_cert_t *cert = ed25519_cert_new();
+  cert->cert_type = cert_type;
+  cert->exp_field = (uint32_t) CEIL_DIV(now + lifetime, 3600);
+  cert->cert_key_type = signed_key_type;
+  memcpy(cert->certified_key, signed_key_info, 32);
+
+  if (flags & CERT_FLAG_INCLUDE_SIGNING_KEY) {
+    ed25519_cert_extension_t *ext = ed25519_cert_extension_new();
+    ext->ext_type = CERTEXT_SIGNED_WITH_KEY;
+    memcpy(ext->un_signing_key, signing_key->pubkey.pubkey, 32);
+    ed25519_cert_add_ext(cert, ext);
+    ++cert->n_extensions;
+  }
+
+  const ssize_t alloc_len = ed25519_cert_encoded_len(cert);
+  tor_assert(alloc_len > 0);
+  uint8_t *encoded = tor_malloc(alloc_len);
+  const ssize_t real_len = ed25519_cert_encode(encoded, alloc_len, cert);
+  if (real_len < 0)
+    goto err;
+  tor_assert(real_len == alloc_len);
+  tor_assert(real_len > ED25519_SIG_LEN);
+  uint8_t *sig = encoded + (real_len - ED25519_SIG_LEN);
+  tor_assert(tor_mem_is_zero((char*)sig, ED25519_SIG_LEN));
+
+  ed25519_signature_t signature;
+  if (ed25519_sign(&signature, encoded,
+                   real_len-ED25519_SIG_LEN, signing_key)<0) {
+    log_warn(LD_BUG, "Can't sign certificate");
+    goto err;
+  }
+  memcpy(sig, signature.sig, ED25519_SIG_LEN);
+
+  torcert = tor_cert_parse(encoded, real_len);
+  if (! torcert) {
+    log_warn(LD_BUG, "Generated a certificate we cannot parse");
+    goto err;
+  }
+
+  if (tor_cert_checksig(torcert, &signing_key->pubkey, now) < 0) {
+    log_warn(LD_BUG, "Generated a certificate whose signature we can't check");
+    goto err;
+  }
+
+  tor_free(encoded);
+
+  return torcert;
+
+ err:
+  tor_cert_free(torcert);
+  ed25519_cert_free(cert);
+  tor_free(encoded);
+  return NULL;
+}
+
+/**
+ * Create and return a new new certificate of type <b>cert_type</b> to
+ * authenticate <b>signed_key</b> using the key <b>signing_key</b>.  The
+ * certificate should remain valid for at least <b>lifetime</b> seconds after
+ * <b>now</b>.
+ *
+ * If CERT_FLAG_INCLUDE_SIGNING_KEY is set in <b>flags</b>, embed
+ * the public part of <b>signing_key</b> in the certificate.
+ */
+tor_cert_t *
+tor_cert_create(const ed25519_keypair_t *signing_key,
+                uint8_t cert_type,
+                const ed25519_public_key_t *signed_key,
+                time_t now, time_t lifetime,
+                uint32_t flags)
+{
+  return tor_cert_sign_impl(signing_key, cert_type,
+                            SIGNED_KEY_TYPE_ED25519, signed_key->pubkey,
+                            now, lifetime, flags);
+}
+
+/** Release all storage held for <b>cert</>. */
+void
+tor_cert_free(tor_cert_t *cert)
+{
+  if (! cert)
+    return;
+
+  if (cert->encoded)
+    memwipe(cert->encoded, 0, cert->encoded_len);
+  tor_free(cert->encoded);
+
+  memwipe(cert, 0, sizeof(tor_cert_t));
+  tor_free(cert);
+}
+
+/** Parse a certificate encoded with <b>len</b> bytes in <b>encoded</b>. */
+tor_cert_t *
+tor_cert_parse(const uint8_t *encoded, const size_t len)
+{
+  tor_cert_t *cert = NULL;
+  ed25519_cert_t *parsed = NULL;
+  ssize_t got_len = ed25519_cert_parse(&parsed, encoded, len);
+  if (got_len < 0 || (size_t) got_len != len)
+    goto err;
+
+  cert = tor_malloc_zero(sizeof(tor_cert_t));
+  cert->encoded = tor_memdup(encoded, len);
+  cert->encoded_len = len;
+
+  memcpy(cert->signed_key.pubkey, parsed->certified_key, 32);
+  cert->valid_until = parsed->exp_field * 3600;
+  cert->cert_type = parsed->cert_type;
+
+  for (unsigned i = 0; i < ed25519_cert_getlen_ext(parsed); ++i) {
+    ed25519_cert_extension_t *ext = ed25519_cert_get_ext(parsed, i);
+    if (ext->ext_type == CERTEXT_SIGNED_WITH_KEY) {
+      if (cert->signing_key_included)
+        goto err;
+
+      cert->signing_key_included = 1;
+      memcpy(cert->signing_key.pubkey, ext->un_signing_key, 32);
+    } else if (ext->ext_flags & CERTEXT_FLAG_AFFECTS_VALIDATION) {
+      /* Unrecognized extension with affects_validation set */
+      goto err;
+    }
+  }
+
+  return cert;
+ err:
+  ed25519_cert_free(parsed);
+  tor_cert_free(cert);
+  return NULL;
+}
+
+/** Fill in <b>checkable_out</b> with the information needed to check
+ * the signature on <b>cert</b> with <b>pubkey</b>. */
+int
+tor_cert_get_checkable_sig(ed25519_checkable_t *checkable_out,
+                           const tor_cert_t *cert,
+                           const ed25519_public_key_t *pubkey)
+{
+  if (! pubkey) {
+    if (cert->signing_key_included)
+      pubkey = &cert->signing_key;
+    else
+      return -1;
+  }
+
+  checkable_out->msg = cert->encoded;
+  checkable_out->pubkey = pubkey;
+  tor_assert(cert->encoded_len > ED25519_SIG_LEN);
+  const size_t signed_len = cert->encoded_len - ED25519_SIG_LEN;
+  checkable_out->len = signed_len;
+  memcpy(checkable_out->signature.sig,
+         cert->encoded + signed_len, ED25519_SIG_LEN);
+
+  return 0;
+}
+
+/** Validates the signature on <b>cert</b> with <b>pubkey</b> relative to
+ * the current time <b>now</b>.  Return 0 on success, -1 on failure.
+ * Sets flags in <b>cert</b> as appropriate.
+ */
+int
+tor_cert_checksig(tor_cert_t *cert,
+                  const ed25519_public_key_t *pubkey, time_t now)
+{
+  ed25519_checkable_t checkable;
+  int okay;
+
+  if (now > cert->valid_until) {
+    cert->cert_expired = 1;
+    return -1;
+  }
+
+  if (tor_cert_get_checkable_sig(&checkable, cert, pubkey) < 0)
+    return -1;
+
+  if (ed25519_checksig_batch(&okay, &checkable, 1) < 0) {
+    cert->sig_bad = 1;
+    return -1;
+  } else {
+    cert->sig_ok = 1;
+    memcpy(cert->signing_key.pubkey, checkable.pubkey->pubkey, 32);
+    cert->cert_valid = 1;
+    return 0;
+  }
+}
+
diff --git a/src/or/torcert.h b/src/or/torcert.h
new file mode 100644
index 0000000000..7e9c3f5b2d
--- /dev/null
+++ b/src/or/torcert.h
@@ -0,0 +1,66 @@
+/* Copyright (c) 2014, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#ifndef TORCERT_H_INCLUDED
+#define TORCERT_H_INCLUDED
+
+#include "crypto_ed25519.h"
+
+#define SIGNED_KEY_TYPE_ED25519 0x01
+
+#define CERT_TYPE_ID_SIGNING    0x04
+#define CERT_TYPE_SIGNING_LINK  0x05
+#define CERT_TYPE_SIGNING_AUTH  0x06
+
+#define CERT_FLAG_INCLUDE_SIGNING_KEY 0x1
+
+/** An ed25519-signed certificate as used throughout the Tor protocol.
+ **/
+typedef struct tor_cert_st {
+  /** The key authenticated by this certificate */
+  ed25519_public_key_t signed_key;
+  /** The key that signed this certificate. This value may be unset if the
+   * certificate has never been checked, and didn't include its own key. */
+  ed25519_public_key_t signing_key;
+  /** A time after which this certificate will no longer be valid. */
+  time_t valid_until;
+
+  /** The encoded representation of this certificate */
+  uint8_t *encoded;
+  /** The length of <b>encoded</b> */
+  size_t encoded_len;
+
+  /** One of CERT_TYPE_... */
+  uint8_t cert_type;
+  /** True iff we received a signing key embedded in this certificate */
+  unsigned signing_key_included : 1;
+  /** True iff we checked the signature and found it bad */
+  unsigned sig_bad : 1;
+  /** True iff we checked the signature and found it correct */
+  unsigned sig_ok : 1;
+  /** True iff we checked the signature and first found that the cert
+   * had expired */
+  unsigned cert_expired : 1;
+  /** True iff we checked the signature and found the whole cert valid */
+  unsigned cert_valid : 1;
+} tor_cert_t;
+
+tor_cert_t *tor_cert_create(const ed25519_keypair_t *signing_key,
+                            uint8_t cert_type,
+                            const ed25519_public_key_t *signed_key,
+                            time_t now, time_t lifetime,
+                            uint32_t flags);
+
+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);
+
+int tor_cert_checksig(tor_cert_t *cert,
+                      const ed25519_public_key_t *pubkey, time_t now);
+
+#endif
+