Merge branch 'ntor-resquashed'

Conflicts:
	src/or/cpuworker.c
	src/or/or.h
	src/test/bench.c

7 files changed, 506 insertions, 42 deletions

diff --git a/src/common/crypto.c b/src/common/crypto.c
index 4cf9a9cdb0..80d1ed2540 100644
--- a/src/common/crypto.c
+++ b/src/common/crypto.c
@@ -2036,6 +2036,16 @@ crypto_dh_new(int dh_type)
   return NULL;
 }
 
+/** Return a copy of <b>dh</b>, sharing its internal state. */
+crypto_dh_t *
+crypto_dh_dup(const crypto_dh_t *dh)
+{
+  crypto_dh_t *dh_new = tor_malloc_zero(sizeof(crypto_dh_t));
+  dh_new->dh = dh->dh;
+  DH_up_ref(dh->dh);
+  return dh_new;
+}
+
 /** Return the length of the DH key in <b>dh</b>, in bytes.
  */
 int
@@ -2174,8 +2184,8 @@ crypto_dh_compute_secret(int severity, crypto_dh_t *dh,
     goto error;
   }
   secret_len = result;
-  if (crypto_expand_key_material(secret_tmp, secret_len,
-                                 secret_out, secret_bytes_out)<0)
+  if (crypto_expand_key_material_TAP((uint8_t*)secret_tmp, secret_len,
+                                     (uint8_t*)secret_out, secret_bytes_out)<0)
     goto error;
   secret_len = secret_bytes_out;
 
@@ -2201,15 +2211,18 @@ crypto_dh_compute_secret(int severity, crypto_dh_t *dh,
  * <b>key_out</b> by taking the first <b>key_out_len</b> bytes of
  *    H(K | [00]) | H(K | [01]) | ....
  *
+ * This is the key expansion algorithm used in the "TAP" circuit extension
+ * mechanism; it shouldn't be used for new protocols.
+ *
  * Return 0 on success, -1 on failure.
  */
 int
-crypto_expand_key_material(const char *key_in, size_t key_in_len,
-                           char *key_out, size_t key_out_len)
+crypto_expand_key_material_TAP(const uint8_t *key_in, size_t key_in_len,
+                               uint8_t *key_out, size_t key_out_len)
 {
   int i;
-  char *cp, *tmp = tor_malloc(key_in_len+1);
-  char digest[DIGEST_LEN];
+  uint8_t *cp, *tmp = tor_malloc(key_in_len+1);
+  uint8_t digest[DIGEST_LEN];
 
   /* If we try to get more than this amount of key data, we'll repeat blocks.*/
   tor_assert(key_out_len <= DIGEST_LEN*256);
@@ -2218,7 +2231,7 @@ crypto_expand_key_material(const char *key_in, size_t key_in_len,
   for (cp = key_out, i=0; cp < key_out+key_out_len;
        ++i, cp += DIGEST_LEN) {
     tmp[key_in_len] = i;
-    if (crypto_digest(digest, tmp, key_in_len+1))
+    if (crypto_digest((char*)digest, (const char *)tmp, key_in_len+1))
       goto err;
     memcpy(cp, digest, MIN(DIGEST_LEN, key_out_len-(cp-key_out)));
   }
@@ -2234,6 +2247,65 @@ crypto_expand_key_material(const char *key_in, size_t key_in_len,
   return -1;
 }
 
+/** Expand some secret key material according to RFC5869, using SHA256 as the
+ * underlying hash.  The <b>key_in_len</b> bytes at <b>key_in</b> are the
+ * secret key material; the <b>salt_in_len</b> bytes at <b>salt_in</b> and the
+ * <b>info_in_len</b> bytes in <b>info_in_len</b> are the algorithm's "salt"
+ * and "info" parameters respectively.  On success, write <b>key_out_len</b>
+ * bytes to <b>key_out</b> and return 0.  On failure, return -1.
+ */
+int
+crypto_expand_key_material_rfc5869_sha256(
+                                    const uint8_t *key_in, size_t key_in_len,
+                                    const uint8_t *salt_in, size_t salt_in_len,
+                                    const uint8_t *info_in, size_t info_in_len,
+                                    uint8_t *key_out, size_t key_out_len)
+{
+  uint8_t prk[DIGEST256_LEN];
+  uint8_t tmp[DIGEST256_LEN + 128 + 1];
+  uint8_t mac[DIGEST256_LEN];
+  int i;
+  uint8_t *outp;
+  size_t tmp_len;
+
+  crypto_hmac_sha256((char*)prk,
+                     (const char*)salt_in, salt_in_len,
+                     (const char*)key_in, key_in_len);
+
+  /* If we try to get more than this amount of key data, we'll repeat blocks.*/
+  tor_assert(key_out_len <= DIGEST256_LEN * 256);
+  tor_assert(info_in_len <= 128);
+  memset(tmp, 0, sizeof(tmp));
+  outp = key_out;
+  i = 1;
+
+  while (key_out_len) {
+    size_t n;
+    if (i > 1) {
+      memcpy(tmp, mac, DIGEST256_LEN);
+      memcpy(tmp+DIGEST256_LEN, info_in, info_in_len);
+      tmp[DIGEST256_LEN+info_in_len] = i;
+      tmp_len = DIGEST256_LEN + info_in_len + 1;
+    } else {
+      memcpy(tmp, info_in, info_in_len);
+      tmp[info_in_len] = i;
+      tmp_len = info_in_len + 1;
+    }
+    crypto_hmac_sha256((char*)mac,
+                       (const char*)prk, DIGEST256_LEN,
+                       (const char*)tmp, tmp_len);
+    n = key_out_len < DIGEST256_LEN ? key_out_len : DIGEST256_LEN;
+    memcpy(outp, mac, n);
+    key_out_len -= n;
+    outp += n;
+    ++i;
+  }
+
+  memwipe(tmp, 0, sizeof(tmp));
+  memwipe(mac, 0, sizeof(mac));
+  return 0;
+}
+
 /** Free a DH key exchange object.
  */
 void
@@ -2272,22 +2344,16 @@ seed_weak_rng(void)
   tor_init_weak_random(seed);
 }
 
-/** Seed OpenSSL's random number generator with bytes from the operating
- * system.  <b>startup</b> should be true iff we have just started Tor and
- * have not yet allocated a bunch of fds.  Return 0 on success, -1 on failure.
+/** Try to get <b>out_len</b> bytes of the strongest entropy we can generate,
+ * storing it into <b>out</b>.
  */
 int
-crypto_seed_rng(int startup)
+crypto_strongest_rand(uint8_t *out, size_t out_len)
 {
-  int rand_poll_status = 0;
-
-  /* local variables */
 #ifdef _WIN32
-  unsigned char buf[ADD_ENTROPY];
   static int provider_set = 0;
   static HCRYPTPROV provider;
 #else
-  char buf[ADD_ENTROPY];
   static const char *filenames[] = {
     "/dev/srandom", "/dev/urandom", "/dev/random", NULL
   };
@@ -2295,58 +2361,77 @@ crypto_seed_rng(int startup)
   size_t n;
 #endif
 
-  /* OpenSSL has a RAND_poll function that knows about more kinds of
-   * entropy than we do.  We'll try calling that, *and* calling our own entropy
-   * functions.  If one succeeds, we'll accept the RNG as seeded. */
-  if (startup || RAND_POLL_IS_SAFE) {
-    rand_poll_status = RAND_poll();
-    if (rand_poll_status == 0)
-      log_warn(LD_CRYPTO, "RAND_poll() failed.");
-  }
-
 #ifdef _WIN32
   if (!provider_set) {
     if (!CryptAcquireContext(&provider, NULL, NULL, PROV_RSA_FULL,
                              CRYPT_VERIFYCONTEXT)) {
       if ((unsigned long)GetLastError() != (unsigned long)NTE_BAD_KEYSET) {
         log_warn(LD_CRYPTO, "Can't get CryptoAPI provider [1]");
-        return rand_poll_status ? 0 : -1;
+        return -1;
       }
     }
     provider_set = 1;
   }
-  if (!CryptGenRandom(provider, sizeof(buf), buf)) {
+  if (!CryptGenRandom(provider, out_len, out)) {
     log_warn(LD_CRYPTO, "Can't get entropy from CryptoAPI.");
-    return rand_poll_status ? 0 : -1;
+    return -1;
   }
-  RAND_seed(buf, sizeof(buf));
-  memwipe(buf, 0, sizeof(buf));
-  seed_weak_rng();
+
   return 0;
 #else
   for (i = 0; filenames[i]; ++i) {
     fd = open(filenames[i], O_RDONLY, 0);
     if (fd<0) continue;
-    log_info(LD_CRYPTO, "Seeding RNG from \"%s\"", filenames[i]);
-    n = read_all(fd, buf, sizeof(buf), 0);
+    log_info(LD_CRYPTO, "Reading entropy from \"%s\"", filenames[i]);
+    n = read_all(fd, (char*)out, out_len, 0);
     close(fd);
-    if (n != sizeof(buf)) {
+    if (n != out_len) {
       log_warn(LD_CRYPTO,
                "Error reading from entropy source (read only %lu bytes).",
                (unsigned long)n);
       return -1;
     }
-    RAND_seed(buf, (int)sizeof(buf));
-    memwipe(buf, 0, sizeof(buf));
-    seed_weak_rng();
+
     return 0;
   }
 
-  log_warn(LD_CRYPTO, "Cannot seed RNG -- no entropy source found.");
-  return rand_poll_status ? 0 : -1;
+  log_warn(LD_CRYPTO, "Cannot get strong entropy: no entropy source found.");
+  return -1;
 #endif
 }
 
+/** Seed OpenSSL's random number generator with bytes from the operating
+ * system.  <b>startup</b> should be true iff we have just started Tor and
+ * have not yet allocated a bunch of fds.  Return 0 on success, -1 on failure.
+ */
+int
+crypto_seed_rng(int startup)
+{
+  int rand_poll_ok = 0, load_entropy_ok = 0;
+  uint8_t buf[ADD_ENTROPY];
+
+  /* OpenSSL has a RAND_poll function that knows about more kinds of
+   * entropy than we do.  We'll try calling that, *and* calling our own entropy
+   * functions.  If one succeeds, we'll accept the RNG as seeded. */
+  if (startup || RAND_POLL_IS_SAFE) {
+    rand_poll_ok = RAND_poll();
+    if (rand_poll_ok == 0)
+      log_warn(LD_CRYPTO, "RAND_poll() failed.");
+  }
+
+  load_entropy_ok = !crypto_strongest_rand(buf, sizeof(buf));
+  if (load_entropy_ok) {
+    RAND_seed(buf, sizeof(buf));
+  }
+
+  memwipe(buf, 0, sizeof(buf));
+  seed_weak_rng();
+  if (rand_poll_ok || load_entropy_ok)
+    return 0;
+  else
+    return -1;
+}
+
 /** Write <b>n</b> bytes of strong random data to <b>to</b>. Return 0 on
  * success, -1 on failure.
  */
diff --git a/src/common/crypto.h b/src/common/crypto.h
index 4c5fa6ad97..b6e8e6c560 100644
--- a/src/common/crypto.h
+++ b/src/common/crypto.h
@@ -230,6 +230,7 @@ void crypto_hmac_sha256(char *hmac_out,
 #define DH_TYPE_REND 2
 #define DH_TYPE_TLS 3
 crypto_dh_t *crypto_dh_new(int dh_type);
+crypto_dh_t *crypto_dh_dup(const crypto_dh_t *dh);
 int crypto_dh_get_bytes(crypto_dh_t *dh);
 int crypto_dh_generate_public(crypto_dh_t *dh);
 int crypto_dh_get_public(crypto_dh_t *dh, char *pubkey_out,
@@ -238,12 +239,20 @@ ssize_t crypto_dh_compute_secret(int severity, crypto_dh_t *dh,
                              const char *pubkey, size_t pubkey_len,
                              char *secret_out, size_t secret_out_len);
 void crypto_dh_free(crypto_dh_t *dh);
-int crypto_expand_key_material(const char *key_in, size_t in_len,
-                               char *key_out, size_t key_out_len);
+
+int crypto_expand_key_material_TAP(const uint8_t *key_in,
+                                   size_t key_in_len,
+                                   uint8_t *key_out, size_t key_out_len);
+int crypto_expand_key_material_rfc5869_sha256(
+                                    const uint8_t *key_in, size_t key_in_len,
+                                    const uint8_t *salt_in, size_t salt_in_len,
+                                    const uint8_t *info_in, size_t info_in_len,
+                                    uint8_t *key_out, size_t key_out_len);
 
 /* random numbers */
 int crypto_seed_rng(int startup);
 int crypto_rand(char *to, size_t n);
+int crypto_strongest_rand(uint8_t *out, size_t out_len);
 int crypto_rand_int(unsigned int max);
 uint64_t crypto_rand_uint64(uint64_t max);
 double crypto_rand_double(void);
diff --git a/src/common/crypto_curve25519.c b/src/common/crypto_curve25519.c
new file mode 100644
index 0000000000..a4ab65cf4f
--- /dev/null
+++ b/src/common/crypto_curve25519.c
@@ -0,0 +1,180 @@
+/* Copyright (c) 2012, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/* Wrapper code for a curve25519 implementation. */
+
+#define CRYPTO_CURVE25519_PRIVATE
+#include "orconfig.h"
+#ifdef HAVE_SYS_STAT_H
+#include <sys/stat.h>
+#endif
+#include "crypto.h"
+#include "crypto_curve25519.h"
+#include "util.h"
+#include "torlog.h"
+
+/* ==============================
+   Part 1: wrap a suitable curve25519 implementation as curve25519_impl
+   ============================== */
+
+#ifdef USE_CURVE25519_DONNA
+int curve25519_donna(uint8_t *mypublic,
+                     const uint8_t *secret, const uint8_t *basepoint);
+#endif
+#ifdef USE_CURVE25519_NACL
+#include <crypto_scalarmult_curve25519.h>
+#endif
+
+int
+curve25519_impl(uint8_t *output, const uint8_t *secret,
+                const uint8_t *basepoint)
+{
+#ifdef USE_CURVE25519_DONNA
+  return curve25519_donna(output, secret, basepoint);
+#elif defined(USE_CURVE25519_NACL)
+  return crypto_scalarmult_curve25519(output, secret, basepoint);
+#else
+#error "No implementation of curve25519 is available."
+#endif
+}
+
+/* ==============================
+   Part 2: Wrap curve25519_impl with some convenience types and functions.
+   ============================== */
+
+/**
+ * Return true iff a curve25519_public_key_t seems valid. (It's not necessary
+ * to see if the point is on the curve, since the twist is also secure, but we
+ * do need to make sure that it isn't the point at infinity.) */
+int
+curve25519_public_key_is_ok(const curve25519_public_key_t *key)
+{
+  return !safe_mem_is_zero(key->public_key, CURVE25519_PUBKEY_LEN);
+}
+
+/** Generate a new keypair and return the secret key.  If <b>extra_strong</b>
+ * is true, this key is possibly going to get used more than once, so
+ * use a better-than-usual RNG. Return 0 on success, -1 on failure. */
+int
+curve25519_secret_key_generate(curve25519_secret_key_t *key_out,
+                               int extra_strong)
+{
+  uint8_t k_tmp[CURVE25519_SECKEY_LEN];
+
+  if (crypto_rand((char*)key_out->secret_key, CURVE25519_SECKEY_LEN) < 0)
+    return -1;
+  if (extra_strong && !crypto_strongest_rand(k_tmp, CURVE25519_SECKEY_LEN)) {
+    /* If they asked for extra-strong entropy and we have some, use it as an
+     * HMAC key to improve not-so-good entopy rather than using it directly,
+     * just in case the extra-strong entropy is less amazing than we hoped. */
+    crypto_hmac_sha256((char *)key_out->secret_key,
+                    (const char *)k_tmp, sizeof(k_tmp),
+                    (const char *)key_out->secret_key, CURVE25519_SECKEY_LEN);
+  }
+  memwipe(k_tmp, 0, sizeof(k_tmp));
+  key_out->secret_key[0] &= 248;
+  key_out->secret_key[31] &= 127;
+  key_out->secret_key[31] |= 64;
+
+  return 0;
+}
+
+void
+curve25519_public_key_generate(curve25519_public_key_t *key_out,
+                               const curve25519_secret_key_t *seckey)
+{
+  static const uint8_t basepoint[32] = {9};
+
+  curve25519_impl(key_out->public_key, seckey->secret_key, basepoint);
+}
+
+int
+curve25519_keypair_generate(curve25519_keypair_t *keypair_out,
+                            int extra_strong)
+{
+  if (curve25519_secret_key_generate(&keypair_out->seckey, extra_strong) < 0)
+    return -1;
+  curve25519_public_key_generate(&keypair_out->pubkey, &keypair_out->seckey);
+  return 0;
+}
+
+int
+curve25519_keypair_write_to_file(const curve25519_keypair_t *keypair,
+                                 const char *fname,
+                                 const char *tag)
+{
+  char contents[32 + CURVE25519_SECKEY_LEN + CURVE25519_PUBKEY_LEN];
+  int r;
+
+  memset(contents, 0, sizeof(contents));
+  tor_snprintf(contents, sizeof(contents), "== c25519v1: %s ==", tag);
+  tor_assert(strlen(contents) <= 32);
+  memcpy(contents+32, keypair->seckey.secret_key, CURVE25519_SECKEY_LEN);
+  memcpy(contents+32+CURVE25519_SECKEY_LEN,
+         keypair->pubkey.public_key, CURVE25519_PUBKEY_LEN);
+
+  r = write_bytes_to_file(fname, contents, sizeof(contents), 1);
+
+  memwipe(contents, 0, sizeof(contents));
+  return r;
+}
+
+int
+curve25519_keypair_read_from_file(curve25519_keypair_t *keypair_out,
+                                  char **tag_out,
+                                  const char *fname)
+{
+  char prefix[33];
+  char *content;
+  struct stat st;
+  int r = -1;
+
+  *tag_out = NULL;
+
+  st.st_size = 0;
+  content = read_file_to_str(fname, RFTS_BIN|RFTS_IGNORE_MISSING, &st);
+  if (! content)
+    goto end;
+  if (st.st_size != 32 + CURVE25519_SECKEY_LEN + CURVE25519_PUBKEY_LEN)
+    goto end;
+
+  memcpy(prefix, content, 32);
+  prefix[32] = '\0';
+  if (strcmpstart(prefix, "== c25519v1: ") ||
+      strcmpend(prefix, " =="))
+    goto end;
+
+  *tag_out = tor_strndup(prefix+strlen("== c25519v1: "),
+                         strlen(prefix) - strlen("== c25519v1:  =="));
+
+  memcpy(keypair_out->seckey.secret_key, content+32, CURVE25519_SECKEY_LEN);
+  curve25519_public_key_generate(&keypair_out->pubkey, &keypair_out->seckey);
+  if (tor_memneq(keypair_out->pubkey.public_key,
+                 content + 32 + CURVE25519_SECKEY_LEN,
+                 CURVE25519_PUBKEY_LEN))
+    goto end;
+
+  r = 0;
+
+ end:
+  if (content) {
+    memwipe(content, 0, st.st_size);
+    tor_free(content);
+  }
+  if (r != 0) {
+    memset(keypair_out, 0, sizeof(*keypair_out));
+    tor_free(*tag_out);
+  }
+  return r;
+}
+
+/** Perform the curve25519 ECDH handshake with <b>skey</b> and <b>pkey</b>,
+ * writing CURVE25519_OUTPUT_LEN bytes of output into <b>output</b>. */
+void
+curve25519_handshake(uint8_t *output,
+                     const curve25519_secret_key_t *skey,
+                     const curve25519_public_key_t *pkey)
+{
+  curve25519_impl(output, skey->secret_key, pkey->public_key);
+}
+
diff --git a/src/common/crypto_curve25519.h b/src/common/crypto_curve25519.h
new file mode 100644
index 0000000000..e768b8c427
--- /dev/null
+++ b/src/common/crypto_curve25519.h
@@ -0,0 +1,61 @@
+/* Copyright (c) 2012, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#ifndef TOR_CRYPTO_CURVE25519_H
+#define TOR_CRYPTO_CURVE25519_H
+
+#include "torint.h"
+
+/** Length of a curve25519 public key when encoded. */
+#define CURVE25519_PUBKEY_LEN 32
+/** Length of a curve25519 secret key when encoded. */
+#define CURVE25519_SECKEY_LEN 32
+/** Length of the result of a curve25519 handshake. */
+#define CURVE25519_OUTPUT_LEN 32
+
+/** Wrapper type for a curve25519 public key */
+typedef struct curve25519_public_key_t {
+  uint8_t public_key[CURVE25519_PUBKEY_LEN];
+} curve25519_public_key_t;
+
+/** Wrapper type for a curve25519 secret key */
+typedef struct curve25519_secret_key_t {
+  uint8_t secret_key[CURVE25519_SECKEY_LEN];
+} curve25519_secret_key_t;
+
+/** A paired public and private key for curve25519. **/
+typedef struct curve25519_keypair_t {
+  curve25519_public_key_t pubkey;
+  curve25519_secret_key_t seckey;
+} curve25519_keypair_t;
+
+#ifdef CURVE25519_ENABLED
+int curve25519_public_key_is_ok(const curve25519_public_key_t *);
+
+int curve25519_secret_key_generate(curve25519_secret_key_t *key_out,
+                                   int extra_strong);
+void curve25519_public_key_generate(curve25519_public_key_t *key_out,
+                                    const curve25519_secret_key_t *seckey);
+int curve25519_keypair_generate(curve25519_keypair_t *keypair_out,
+                                int extra_strong);
+
+void curve25519_handshake(uint8_t *output,
+                          const curve25519_secret_key_t *,
+                          const curve25519_public_key_t *);
+
+int curve25519_keypair_write_to_file(const curve25519_keypair_t *keypair,
+                                     const char *fname,
+                                     const char *tag);
+
+int curve25519_keypair_read_from_file(curve25519_keypair_t *keypair_out,
+                                      char **tag_out,
+                                      const char *fname);
+
+#ifdef CRYPTO_CURVE25519_PRIVATE
+int curve25519_impl(uint8_t *output, const uint8_t *secret,
+                    const uint8_t *basepoint);
+#endif
+#endif
+
+#endif
+
diff --git a/src/common/di_ops.c b/src/common/di_ops.c
index 418d6e3dca..e299e31507 100644
--- a/src/common/di_ops.c
+++ b/src/common/di_ops.c
@@ -8,6 +8,8 @@
 
 #include "orconfig.h"
 #include "di_ops.h"
+#include "torlog.h"
+#include "util.h"
 
 /**
  * Timing-safe version of memcmp.  As memcmp, compare the <b>sz</b> bytes at
@@ -131,3 +133,90 @@ tor_memeq(const void *a, const void *b, size_t sz)
   return 1 & ((any_difference - 1) >> 8);
 }
 
+/* Implement di_digest256_map_t as a linked list of entries. */
+struct di_digest256_map_t {
+  struct di_digest256_map_t *next;
+  uint8_t key[32];
+  void *val;
+};
+
+/** Release all storage held in <b>map</b>, calling free_fn on each value
+ * as we go. */
+void
+dimap_free(di_digest256_map_t *map, dimap_free_fn free_fn)
+{
+  while (map) {
+    di_digest256_map_t *victim = map;
+    map = map->next;
+    if (free_fn)
+      free_fn(victim->val);
+    tor_free(victim);
+  }
+}
+
+/** Adjust the map at *<b>map</b>, adding an entry for <b>key</b> ->
+ * <b>val</b>, where <b>key</b> is a DIGEST256_LEN-byte key.
+ *
+ * The caller MUST NOT add a key that already appears in the map.
+ */
+void
+dimap_add_entry(di_digest256_map_t **map,
+                const uint8_t *key, void *val)
+{
+  di_digest256_map_t *new_ent;
+  {
+    void *old_val = dimap_search(*map, key, NULL);
+    tor_assert(! old_val);
+    tor_assert(val);
+  }
+  new_ent = tor_malloc_zero(sizeof(di_digest256_map_t));
+  new_ent->next = *map;
+  memcpy(new_ent->key, key, 32);
+  new_ent->val = val;
+  *map = new_ent;
+}
+
+/** Search the map at <b>map</b> for an entry whose key is <b>key</b> (a
+ * DIGEST256_LEN-byte key) returning the corresponding value if we found one,
+ * and returning <b>dflt_val</b> if the key wasn't found.
+ *
+ * This operation takes an amount of time dependent only on the length of
+ * <b>map</b>, not on the position or presence of <b>key</b> within <b>map</b>.
+ */
+void *
+dimap_search(const di_digest256_map_t *map, const uint8_t *key,
+             void *dflt_val)
+{
+  uintptr_t result = (uintptr_t)dflt_val;
+
+  while (map) {
+    uintptr_t r = (uintptr_t) tor_memeq(map->key, key, 32);
+    r -= 1; /* Now r is (uintptr_t)-1 if memeq returned false, and
+             * 0 if memeq returned true. */
+
+    result &= r;
+    result |= ((uintptr_t)(map->val)) & ~r;
+
+    map = map->next;
+  }
+
+  return (void *)result;
+}
+
+/**
+ * Return true iff the <b>sz</b> bytes at <b>mem</b> are all zero. Runs in
+ * time independent of the contents of <b>mem</b>.
+ */
+int
+safe_mem_is_zero(const void *mem, size_t sz)
+{
+  uint32_t total = 0;
+  const uint8_t *ptr = mem;
+
+  while (sz--) {
+    total |= *ptr++;
+  }
+
+  return 1 & ((total - 1) >> 8);
+}
+
diff --git a/src/common/di_ops.h b/src/common/di_ops.h
index 8f0bb698f9..144482811f 100644
--- a/src/common/di_ops.h
+++ b/src/common/di_ops.h
@@ -27,5 +27,21 @@ int tor_memeq(const void *a, const void *b, size_t sz);
 #define fast_memeq(a,b,c)  (0==memcmp((a),(b),(c)))
 #define fast_memneq(a,b,c) (0!=memcmp((a),(b),(c)))
 
+int safe_mem_is_zero(const void *mem, size_t sz);
+
+/** A type for a map from DIGEST256_LEN-byte blobs to void*, such that
+ * data lookups take an amount of time proportional only to the size
+ * of the map, and not to the position or presence of the item in the map.
+ *
+ * Not efficient for large maps! */
+typedef struct di_digest256_map_t di_digest256_map_t;
+typedef void (*dimap_free_fn)(void *);
+
+void dimap_free(di_digest256_map_t *map, dimap_free_fn free_fn);
+void dimap_add_entry(di_digest256_map_t **map,
+                     const uint8_t *key, void *val);
+void *dimap_search(const di_digest256_map_t *map, const uint8_t *key,
+                   void *dflt_val);
+
 #endif
 
diff --git a/src/common/include.am b/src/common/include.am
index 0fdc72057f..808238dd1f 100644
--- a/src/common/include.am
+++ b/src/common/include.am
@@ -14,6 +14,28 @@ else
 libor_extra_source=
 endif
 
+if BUILD_CURVE25519_DONNA
+src_common_libcurve25519_donna_a_SOURCES=\
+	src/ext/curve25519_donna/curve25519-donna.c
+noinst_LIBRARIES+=src/common/libcurve25519_donna.a
+LIBDONNA=src/common/libcurve25519_donna.a
+else
+if BUILD_CURVE25519_DONNA_C64
+src_common_libcurve25519_donna_a_SOURCES=\
+	src/ext/curve25519_donna/curve25519-donna-c64.c
+noinst_LIBRARIES+=src/common/libcurve25519_donna.a
+LIBDONNA=src/common/libcurve25519_donna.a
+else
+LIBDONNA=
+endif
+endif
+
+src_common_libcurve25519_donna_a_CFLAGS =
+
+if CURVE25519_ENABLED
+libcrypto_extra_source=src/common/crypto_curve25519.c
+endif
+
 src_common_libor_a_SOURCES = \
   src/common/address.c					\
   src/common/compat.c					\
@@ -31,7 +53,8 @@ src_common_libor_crypto_a_SOURCES = \
   src/common/aes.c		\
   src/common/crypto.c		\
   src/common/torgzip.c		\
-  src/common/tortls.c
+  src/common/tortls.c		\
+  $(libcrypto_extra_source)
 
 src_common_libor_event_a_SOURCES = src/common/compat_libevent.c
 
@@ -43,6 +66,7 @@ COMMONHEADERS = \
   src/common/compat_libevent.h			\
   src/common/container.h			\
   src/common/crypto.h				\
+  src/common/crypto_curve25519.h		\
   src/common/di_ops.h				\
   src/common/memarea.h				\
   src/common/mempool.h				\