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.

2 files changed, 131 insertions, 7 deletions

diff --git a/src/test/bench.c b/src/test/bench.c
index cf8ba4a48e..de7e4e557c 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 c96aeb7053..78f9c0659e 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),