Implementat the ntor handshake

The ntor handshake--described in proposal 216 and in a paper by
Goldberg, Stebila, and Ustaoglu--gets us much better performance than
our current approach.

5 files changed, 503 insertions, 7 deletions

diff --git a/src/or/include.am b/src/or/include.am
index 405cbd071..18088493e 100644
--- a/src/or/include.am
+++ b/src/or/include.am
@@ -15,6 +15,12 @@ else
 evdns_source=src/ext/eventdns.c
 endif
 
+if CURVE25519_ENABLED
+onion_ntor_source=src/or/onion_ntor.c
+else
+onion_ntor_source=
+endif
+
 src_or_libtor_a_SOURCES = \
 	src/or/addressmap.c				\
 	src/or/buffers.c				\
@@ -65,6 +71,7 @@ src_or_libtor_a_SOURCES = \
 	src/or/status.c					\
 	$(evdns_source)					\
 	$(tor_platform_source)				\
+	$(onion_ntor_source)				\
 	src/or/config_codedigest.c
 
 #libtor_a_LIBADD = ../common/libor.a ../common/libor-crypto.a \
@@ -125,6 +132,7 @@ ORHEADERS = \
 	src/or/nodelist.h				\
 	src/or/ntmain.h					\
 	src/or/onion.h					\
+	src/or/onion_ntor.h				\
 	src/or/or.h					\
 	src/or/transports.h				\
 	src/or/policies.h				\
diff --git a/src/or/onion_ntor.c b/src/or/onion_ntor.c
new file mode 100644
index 000000000..30d18cc47
--- /dev/null
+++ b/src/or/onion_ntor.c
@@ -0,0 +1,315 @@
+/* Copyright (c) 2012, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#include "orconfig.h"
+
+#include "onion_ntor.h"
+#include "crypto.h"
+#include "torlog.h"
+#include "util.h"
+
+/** Storage held by a client while waiting for an ntor reply from a server. */
+struct ntor_handshake_state_t {
+  /** Identity digest of the router we're talking to. */
+  uint8_t router_id[DIGEST_LEN];
+  /** Onion key of the router we're talking to. */
+  curve25519_public_key_t pubkey_B;
+
+  /**
+   * Short-lived keypair for use with this handshake.
+   * @{ */
+  curve25519_secret_key_t seckey_x;
+  curve25519_public_key_t pubkey_X;
+  /** @} */
+};
+
+/** Free storage held in an ntor handshake state. */
+void
+ntor_handshake_state_free(ntor_handshake_state_t *state)
+{
+  if (!state)
+    return;
+  memwipe(state, 0, sizeof(*state));
+  tor_free(state);
+}
+
+/** Convenience function to represent HMAC_SHA256 as our instantiation of
+ * ntor's "tweaked hash'.  Hash the <b>inp_len</b> bytes at <b>inp</b> into
+ * a DIGEST256_LEN-byte digest at <b>out</b>, with the hash changing
+ * depending on the value of <b>tweak</b>. */
+static void
+h_tweak(uint8_t *out,
+        const uint8_t *inp, size_t inp_len,
+        const char *tweak)
+{
+  size_t tweak_len = strlen(tweak);
+  crypto_hmac_sha256((char*)out, tweak, tweak_len, (const char*)inp, inp_len);
+}
+
+/** Wrapper around a set of tweak-values for use with the ntor handshake. */
+typedef struct tweakset_t {
+  const char *t_mac;
+  const char *t_key;
+  const char *t_verify;
+  const char *m_expand;
+} tweakset_t;
+
+/** The tweaks to be used with our handshake. */
+const tweakset_t proto1_tweaks = {
+#define PROTOID "ntor-curve25519-sha256-1"
+#define PROTOID_LEN 24
+  PROTOID ":mac",
+  PROTOID ":key_extract",
+  PROTOID ":verify",
+  PROTOID ":key_expand"
+};
+
+/** Convenience macro: copy <b>len</b> bytes from <b>inp</b> to <b>ptr</b>,
+ * and advance <b>ptr</b> by the number of bytes copied. */
+#define APPEND(ptr, inp, len)                   \
+  STMT_BEGIN {                                  \
+    memcpy(ptr, (inp), (len));                  \
+    ptr += len;                                 \
+  } STMT_END
+
+/**
+ * Compute the first client-side step of the ntor handshake for communicating
+ * with a server whose DIGEST_LEN-byte server identity is <b>router_id</b>,
+ * and whose onion key is <b>router_key</b>. Store the NTOR_ONIONSKIN_LEN-byte
+ * message in <b>onion_skin_out</b>, and store the handshake state in
+ * *<b>handshake_state_out</b>.  Return 0 on success, -1 on failure.
+ */
+int
+onion_skin_ntor_create(const uint8_t *router_id,
+                       const curve25519_public_key_t *router_key,
+                       ntor_handshake_state_t **handshake_state_out,
+                       uint8_t *onion_skin_out)
+{
+  ntor_handshake_state_t *state;
+  uint8_t *op;
+
+  state = tor_malloc_zero(sizeof(ntor_handshake_state_t));
+
+  memcpy(state->router_id, router_id, DIGEST_LEN);
+  memcpy(&state->pubkey_B, router_key, sizeof(curve25519_public_key_t));
+  curve25519_secret_key_generate(&state->seckey_x, 0);
+  curve25519_public_key_generate(&state->pubkey_X, &state->seckey_x);
+
+  op = onion_skin_out;
+  APPEND(op, router_id, DIGEST_LEN);
+  APPEND(op, router_key->public_key, CURVE25519_PUBKEY_LEN);
+  APPEND(op, state->pubkey_X.public_key, CURVE25519_PUBKEY_LEN);
+  tor_assert(op == onion_skin_out + NTOR_ONIONSKIN_LEN);
+
+  *handshake_state_out = state;
+
+  return 0;
+}
+
+#define SERVER_STR "Server"
+#define SERVER_STR_LEN 6
+
+#define SECRET_INPUT_LEN (CURVE25519_PUBKEY_LEN * 3 +   \
+                          CURVE25519_OUTPUT_LEN * 2 +   \
+                          DIGEST_LEN + PROTOID_LEN)
+#define AUTH_INPUT_LEN (DIGEST256_LEN + DIGEST_LEN +    \
+                        CURVE25519_PUBKEY_LEN*3 +       \
+                        PROTOID_LEN + SERVER_STR_LEN)
+
+/**
+ * Perform the server side of an ntor handshake. Given an
+ * NTOR_ONIONSKIN_LEN-byte message in <b>onion_skin</b>, our own identity
+ * fingerprint as <b>my_node_id</b>, and an associative array mapping public
+ * onion keys to curve25519_keypair_t in <b>private_keys</b>, attempt to
+ * perform the handshake.  Write an NTOR_REPLY_LEN-byte message to send back
+ * to the client into <b>handshake_reply_out</b>, and generate
+ * <b>key_out_len</b> bytes of key material in <b>key_out</b>. Return 0 on
+ * success, -1 on failure.
+ */
+int
+onion_skin_ntor_server_handshake(const uint8_t *onion_skin,
+                                 const di_digest256_map_t *private_keys,
+                                 const uint8_t *my_node_id,
+                                 uint8_t *handshake_reply_out,
+                                 uint8_t *key_out,
+                                 size_t key_out_len)
+{
+  const tweakset_t *T = &proto1_tweaks;
+  /* Sensitive stack-allocated material. Kept in an anonymous struct to make
+   * it easy to wipe. */
+  struct {
+    uint8_t secret_input[SECRET_INPUT_LEN];
+    uint8_t auth_input[AUTH_INPUT_LEN];
+    curve25519_public_key_t pubkey_X;
+    curve25519_secret_key_t seckey_y;
+    curve25519_public_key_t pubkey_Y;
+    uint8_t verify[DIGEST256_LEN];
+  } s;
+  uint8_t *si = s.secret_input, *ai = s.auth_input;
+  const curve25519_keypair_t *keypair_bB;
+  int bad;
+
+  /* Decode the onion skin */
+  /* XXXX Does this possible early-return business threaten our security? */
+  if (tor_memneq(onion_skin, my_node_id, DIGEST_LEN))
+    return -1;
+  keypair_bB = dimap_search(private_keys, onion_skin + DIGEST_LEN, NULL);
+  if (!keypair_bB)
+    return -1;
+  memcpy(s.pubkey_X.public_key, onion_skin+DIGEST_LEN+DIGEST256_LEN,
+         CURVE25519_PUBKEY_LEN);
+
+  /* Make y, Y */
+  curve25519_secret_key_generate(&s.seckey_y, 0);
+  curve25519_public_key_generate(&s.pubkey_Y, &s.seckey_y);
+
+  /* NOTE: If we ever use a group other than curve25519, or a different
+   * representation for its points, we may need to perform different or
+   * additional checks on X here and on Y in the client handshake, or lose our
+   * security properties. What checks we need would depend on the properties
+   * of the group and its representation.
+   *
+   * In short: if you use anything other than curve25519, this aspect of the
+   * code will need to be reconsidered carefully. */
+
+  /* build secret_input */
+  curve25519_handshake(si, &s.seckey_y, &s.pubkey_X);
+  bad = tor_memeq(si,
+                  "\x00\x00\x00\x00\x00\x00\x00\x00"
+                  "\x00\x00\x00\x00\x00\x00\x00\x00"
+                  "\x00\x00\x00\x00\x00\x00\x00\x00"
+                  "\x00\x00\x00\x00\x00\x00\x00\x00", 32);
+  si += CURVE25519_OUTPUT_LEN;
+  curve25519_handshake(si, &keypair_bB->seckey, &s.pubkey_X);
+  bad |= tor_memeq(si,
+                   "\x00\x00\x00\x00\x00\x00\x00\x00"
+                   "\x00\x00\x00\x00\x00\x00\x00\x00"
+                   "\x00\x00\x00\x00\x00\x00\x00\x00"
+                   "\x00\x00\x00\x00\x00\x00\x00\x00", 32);
+  si += CURVE25519_OUTPUT_LEN;
+
+  APPEND(si, my_node_id, DIGEST_LEN);
+  APPEND(si, keypair_bB->pubkey.public_key, CURVE25519_PUBKEY_LEN);
+  APPEND(si, s.pubkey_X.public_key, CURVE25519_PUBKEY_LEN);
+  APPEND(si, s.pubkey_Y.public_key, CURVE25519_PUBKEY_LEN);
+  APPEND(si, PROTOID, PROTOID_LEN);
+  tor_assert(si == s.secret_input + sizeof(s.secret_input));
+
+  /* Compute hashes of secret_input */
+  h_tweak(s.verify, s.secret_input, sizeof(s.secret_input), T->t_verify);
+
+  /* Compute auth_input */
+  APPEND(ai, s.verify, DIGEST256_LEN);
+  APPEND(ai, my_node_id, DIGEST_LEN);
+  APPEND(ai, keypair_bB->pubkey.public_key, CURVE25519_PUBKEY_LEN);
+  APPEND(ai, s.pubkey_Y.public_key, CURVE25519_PUBKEY_LEN);
+  APPEND(ai, s.pubkey_X.public_key, CURVE25519_PUBKEY_LEN);
+  APPEND(ai, PROTOID, PROTOID_LEN);
+  APPEND(ai, SERVER_STR, SERVER_STR_LEN);
+  tor_assert(ai == s.auth_input + sizeof(s.auth_input));
+
+  /* Build the reply */
+  memcpy(handshake_reply_out, s.pubkey_Y.public_key, CURVE25519_PUBKEY_LEN);
+  h_tweak(handshake_reply_out+CURVE25519_PUBKEY_LEN,
+          s.auth_input, sizeof(s.auth_input),
+          T->t_mac);
+
+  /* Generate the key material */
+  crypto_expand_key_material_rfc5869_sha256(
+                           s.secret_input, sizeof(s.secret_input),
+                           (const uint8_t*)T->t_key, strlen(T->t_key),
+                           (const uint8_t*)T->m_expand, strlen(T->m_expand),
+                           key_out, key_out_len);
+
+  /* Wipe all of our local state */
+  memwipe(&s, 0, sizeof(s));
+
+  return bad ? -1 : 0;
+}
+
+/**
+ * Perform the final client side of the ntor handshake, using the state in
+ * <b>handshake_state</b> and the server's NTOR_REPLY_LEN-byte reply in
+ * <b>handshake_reply</b>.  Generate <b>key_out_len</b> bytes of key material
+ * in <b>key_out</b>. Return 0 on success, -1 on failure.
+ */
+int
+onion_skin_ntor_client_handshake(
+                             const ntor_handshake_state_t *handshake_state,
+                             const uint8_t *handshake_reply,
+                             uint8_t *key_out,
+                             size_t key_out_len)
+{
+  const tweakset_t *T = &proto1_tweaks;
+  /* Sensitive stack-allocated material. Kept in an anonymous struct to make
+   * it easy to wipe. */
+  struct {
+    curve25519_public_key_t pubkey_Y;
+    uint8_t secret_input[SECRET_INPUT_LEN];
+    uint8_t verify[DIGEST256_LEN];
+    uint8_t auth_input[AUTH_INPUT_LEN];
+    uint8_t auth[DIGEST256_LEN];
+  } s;
+  uint8_t *ai = s.auth_input, *si = s.secret_input;
+  const uint8_t *auth_candidate;
+  int bad;
+
+  /* Decode input */
+  memcpy(s.pubkey_Y.public_key, handshake_reply, CURVE25519_PUBKEY_LEN);
+  auth_candidate = handshake_reply + CURVE25519_PUBKEY_LEN;
+
+  /* See note in server_handshake above about checking points.  The
+   * circumstances under which we'd need to check Y for membership are
+   * different than those under which we'd be checking X. */
+
+  /* Compute secret_input */
+  curve25519_handshake(si, &handshake_state->seckey_x, &s.pubkey_Y);
+  bad = tor_memeq(si,
+                  "\x00\x00\x00\x00\x00\x00\x00\x00"
+                  "\x00\x00\x00\x00\x00\x00\x00\x00"
+                  "\x00\x00\x00\x00\x00\x00\x00\x00"
+                  "\x00\x00\x00\x00\x00\x00\x00\x00", 32);
+  si += CURVE25519_OUTPUT_LEN;
+  curve25519_handshake(si, &handshake_state->seckey_x,
+                       &handshake_state->pubkey_B);
+  bad |= tor_memeq(si,
+                   "\x00\x00\x00\x00\x00\x00\x00\x00"
+                   "\x00\x00\x00\x00\x00\x00\x00\x00"
+                   "\x00\x00\x00\x00\x00\x00\x00\x00"
+                   "\x00\x00\x00\x00\x00\x00\x00\x00", 32);
+  si += CURVE25519_OUTPUT_LEN;
+  APPEND(si, handshake_state->router_id, DIGEST_LEN);
+  APPEND(si, handshake_state->pubkey_B.public_key, CURVE25519_PUBKEY_LEN);
+  APPEND(si, handshake_state->pubkey_X.public_key, CURVE25519_PUBKEY_LEN);
+  APPEND(si, s.pubkey_Y.public_key, CURVE25519_PUBKEY_LEN);
+  APPEND(si, PROTOID, PROTOID_LEN);
+  tor_assert(si == s.secret_input + sizeof(s.secret_input));
+
+  /* Compute verify from secret_input */
+  h_tweak(s.verify, s.secret_input, sizeof(s.secret_input), T->t_verify);
+
+  /* Compute auth_input */
+  APPEND(ai, s.verify, DIGEST256_LEN);
+  APPEND(ai, handshake_state->router_id, DIGEST_LEN);
+  APPEND(ai, handshake_state->pubkey_B.public_key, CURVE25519_PUBKEY_LEN);
+  APPEND(ai, s.pubkey_Y.public_key, CURVE25519_PUBKEY_LEN);
+  APPEND(ai, handshake_state->pubkey_X.public_key, CURVE25519_PUBKEY_LEN);
+  APPEND(ai, PROTOID, PROTOID_LEN);
+  APPEND(ai, SERVER_STR, SERVER_STR_LEN);
+  tor_assert(ai == s.auth_input + sizeof(s.auth_input));
+
+  /* Compute auth */
+  h_tweak(s.auth, s.auth_input, sizeof(s.auth_input), T->t_mac);
+
+  bad |= tor_memneq(s.auth, auth_candidate, DIGEST256_LEN);
+
+  crypto_expand_key_material_rfc5869_sha256(
+                           s.secret_input, sizeof(s.secret_input),
+                           (const uint8_t*)T->t_key, strlen(T->t_key),
+                           (const uint8_t*)T->m_expand, strlen(T->m_expand),
+                           key_out, key_out_len);
+
+  memwipe(&s, 0, sizeof(s));
+  return bad ? -1 : 0;
+}
+
diff --git a/src/or/onion_ntor.h b/src/or/onion_ntor.h
new file mode 100644
index 000000000..03b83da5f
--- /dev/null
+++ b/src/or/onion_ntor.h
@@ -0,0 +1,49 @@
+/* Copyright (c) 2012, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#ifndef TOR_ONION_NTOR_H
+#define TOR_ONION_NTOR_H
+
+#include "torint.h"
+#include "crypto_curve25519.h"
+#include "di_ops.h"
+
+/** State to be maintained by a client between sending an ntor onionskin
+ * and receiving a reply. */
+typedef struct ntor_handshake_state_t ntor_handshake_state_t;
+
+/** Length of an ntor onionskin, as sent from the client to server. */
+#define NTOR_ONIONSKIN_LEN 84
+/** Length of an ntor reply, as sent from server to client. */
+#define NTOR_REPLY_LEN 64
+
+/** A paired public and private key for curve25519.
+ * XXXX024 move this structure somewhere smarter.
+ **/
+typedef struct curve25519_keypair_t {
+  curve25519_public_key_t pubkey;
+  curve25519_secret_key_t seckey;
+} curve25519_keypair_t;
+
+void ntor_handshake_state_free(ntor_handshake_state_t *state);
+
+int onion_skin_ntor_create(const uint8_t *router_id,
+                           const curve25519_public_key_t *router_key,
+                           ntor_handshake_state_t **handshake_state_out,
+                           uint8_t *onion_skin_out);
+
+int onion_skin_ntor_server_handshake(const uint8_t *onion_skin,
+                                 const di_digest256_map_t *private_keys,
+                                 const uint8_t *my_node_id,
+                                 uint8_t *handshake_reply_out,
+                                 uint8_t *key_out,
+                                 size_t key_out_len);
+
+int onion_skin_ntor_client_handshake(
+                             const ntor_handshake_state_t *handshake_state,
+                             const uint8_t *handshake_reply,
+                             uint8_t *key_out,
+                             size_t key_out_len);
+
+#endif
+
diff --git a/src/test/bench.c b/src/test/bench.c
index cf8ba4a48..de7e4e557 100644
--- a/src/test/bench.c
+++ b/src/test/bench.c
@@ -21,6 +21,10 @@ const char tor_git_revision[] = "";
 #include "onion.h"
 #include "relay.h"
 #include "config.h"
+#ifdef CURVE25519_ENABLED
+#include "crypto_curve25519.h"
+#include "onion_ntor.h"
+#endif
 
 #if defined(HAVE_CLOCK_GETTIME) && defined(CLOCK_PROCESS_CPUTIME_ID)
 static uint64_t nanostart;
@@ -122,7 +126,7 @@ bench_onion_TAP(void)
     crypto_dh_free(dh_out);
   }
   end = perftime();
-  printf("Client-side, part 1: %f msec.\n", NANOCOUNT(start, end, iters)/1e6);
+  printf("Client-side, part 1: %f usec.\n", NANOCOUNT(start, end, iters)/1e3);
 
   onion_skin_create(key, &dh_out, os);
   start = perftime();
@@ -131,8 +135,8 @@ bench_onion_TAP(void)
     onion_skin_server_handshake(os, key, NULL, or, key_out, sizeof(key_out));
   }
   end = perftime();
-  printf("Server-side, key guessed right: %f msec\n",
-         NANOCOUNT(start, end, iters)/1e6);
+  printf("Server-side, key guessed right: %f usec\n",
+         NANOCOUNT(start, end, iters)/1e3);
 
   start = perftime();
   for (i = 0; i < iters; ++i) {
@@ -140,8 +144,8 @@ bench_onion_TAP(void)
     onion_skin_server_handshake(os, key2, key, or, key_out, sizeof(key_out));
   }
   end = perftime();
-  printf("Server-side, key guessed wrong: %f msec.\n",
-         NANOCOUNT(start, end, iters)/1e6);
+  printf("Server-side, key guessed wrong: %f usec.\n",
+         NANOCOUNT(start, end, iters)/1e3);
 
   start = perftime();
   for (i = 0; i < iters; ++i) {
@@ -153,12 +157,69 @@ bench_onion_TAP(void)
     tor_assert(s == 0);
   }
   end = perftime();
-  printf("Client-side, part 2: %f msec.\n",
-         NANOCOUNT(start, end, iters)/1e6);
+  printf("Client-side, part 2: %f usec.\n",
+         NANOCOUNT(start, end, iters)/1e3);
 
   crypto_pk_free(key);
 }
 
+#ifdef CURVE25519_ENABLED
+static void
+bench_onion_ntor(void)
+{
+  const int iters = 1<<10;
+  int i;
+  curve25519_keypair_t keypair1, keypair2;
+  uint64_t start, end;
+  uint8_t os[NTOR_ONIONSKIN_LEN];
+  uint8_t or[NTOR_REPLY_LEN];
+  ntor_handshake_state_t *state = NULL;
+  uint8_t nodeid[DIGEST_LEN];
+  di_digest256_map_t *keymap = NULL;
+
+  curve25519_secret_key_generate(&keypair1.seckey, 0);
+  curve25519_public_key_generate(&keypair1.pubkey, &keypair1.seckey);
+  curve25519_secret_key_generate(&keypair2.seckey, 0);
+  curve25519_public_key_generate(&keypair2.pubkey, &keypair2.seckey);
+  dimap_add_entry(&keymap, keypair1.pubkey.public_key, &keypair1);
+  dimap_add_entry(&keymap, keypair2.pubkey.public_key, &keypair2);
+
+  reset_perftime();
+  start = perftime();
+  for (i = 0; i < iters; ++i) {
+    onion_skin_ntor_create(nodeid, &keypair1.pubkey, &state, os);
+    ntor_handshake_state_free(state);
+  }
+  end = perftime();
+  printf("Client-side, part 1: %f usec.\n", NANOCOUNT(start, end, iters)/1e3);
+
+  onion_skin_ntor_create(nodeid, &keypair1.pubkey, &state, os);
+  start = perftime();
+  for (i = 0; i < iters; ++i) {
+    uint8_t key_out[CPATH_KEY_MATERIAL_LEN];
+    onion_skin_ntor_server_handshake(os, keymap, nodeid, or,
+                                key_out, sizeof(key_out));
+  }
+  end = perftime();
+  printf("Server-side: %f usec\n",
+         NANOCOUNT(start, end, iters)/1e3);
+
+  start = perftime();
+  for (i = 0; i < iters; ++i) {
+    uint8_t key_out[CPATH_KEY_MATERIAL_LEN];
+    int s;
+    s = onion_skin_ntor_client_handshake(state, or, key_out, sizeof(key_out));
+    tor_assert(s == 0);
+  }
+  end = perftime();
+  printf("Client-side, part 2: %f usec.\n",
+         NANOCOUNT(start, end, iters)/1e3);
+
+  ntor_handshake_state_free(state);
+  dimap_free(keymap, NULL);
+}
+#endif
+
 static void
 bench_cell_aes(void)
 {
@@ -325,6 +386,9 @@ static struct benchmark_t benchmarks[] = {
   ENT(dmap),
   ENT(aes),
   ENT(onion_TAP),
+#ifdef CURVE25519_ENABLED
+  ENT(onion_ntor),
+#endif
   ENT(cell_aes),
   ENT(cell_ops),
   {NULL,NULL,0}
diff --git a/src/test/test.c b/src/test/test.c
index c96aeb705..78f9c0659 100644
--- a/src/test/test.c
+++ b/src/test/test.c
@@ -57,6 +57,10 @@ double fabs(double x);
 #include "policies.h"
 #include "rephist.h"
 #include "routerparse.h"
+#ifdef CURVE25519_ENABLED
+#include "crypto_curve25519.h"
+#include "onion_ntor.h"
+#endif
 
 #ifdef USE_DMALLOC
 #include <dmalloc.h>
@@ -856,6 +860,59 @@ test_onion_handshake(void)
     crypto_pk_free(pk);
 }
 
+#ifdef CURVE25519_ENABLED
+static void
+test_ntor_handshake(void *arg)
+{
+  /* client-side */
+  ntor_handshake_state_t *c_state = NULL;
+  uint8_t c_buf[NTOR_ONIONSKIN_LEN];
+  uint8_t c_keys[400];
+
+  /* server-side */
+  di_digest256_map_t *s_keymap=NULL;
+  curve25519_keypair_t s_keypair;
+  uint8_t s_buf[NTOR_REPLY_LEN];
+  uint8_t s_keys[400];
+
+  /* shared */
+  const curve25519_public_key_t *server_pubkey;
+  uint8_t node_id[20] = "abcdefghijklmnopqrst";
+
+  (void) arg;
+
+  /* Make the server some keys */
+  curve25519_secret_key_generate(&s_keypair.seckey, 0);
+  curve25519_public_key_generate(&s_keypair.pubkey, &s_keypair.seckey);
+  dimap_add_entry(&s_keymap, s_keypair.pubkey.public_key, &s_keypair);
+  server_pubkey = &s_keypair.pubkey;
+
+  /* client handshake 1. */
+  memset(c_buf, 0, NTOR_ONIONSKIN_LEN);
+  tt_int_op(0, ==, onion_skin_ntor_create(node_id, server_pubkey,
+                                          &c_state, c_buf));
+
+  /* server handshake */
+  memset(s_buf, 0, NTOR_REPLY_LEN);
+  memset(s_keys, 0, 40);
+  tt_int_op(0, ==, onion_skin_ntor_server_handshake(c_buf, s_keymap, node_id,
+                                                    s_buf, s_keys, 400));
+
+  /* client handshake 2 */
+  memset(c_keys, 0, 40);
+  tt_int_op(0, ==, onion_skin_ntor_client_handshake(c_state, s_buf,
+                                                    c_keys, 400));
+
+  test_memeq(c_keys, s_keys, 400);
+  memset(s_buf, 0, 40);
+  test_memneq(c_keys, s_buf, 40);
+
+ done:
+  ntor_handshake_state_free(c_state);
+  dimap_free(s_keymap, NULL);
+}
+#endif
+
 static void
 test_circuit_timeout(void)
 {
@@ -1947,6 +2004,9 @@ static struct testcase_t test_array[] = {
   ENT(buffers),
   { "buffer_copy", test_buffer_copy, 0, NULL, NULL },
   ENT(onion_handshake),
+#ifdef CURVE25519_ENABLED
+  { "ntor_handshake", test_ntor_handshake, 0, NULL, NULL },
+#endif
   ENT(circuit_timeout),
   ENT(policies),
   ENT(rend_fns),