Implement core of ntor3 negotiation.

There are a lot of TODOs about what to send, whom to send it to, and
etc.

10 files changed, 191 insertions, 2 deletions

diff --git a/src/core/crypto/onion_crypto.c b/src/core/crypto/onion_crypto.c
index f93c2c8c58..b0808b80a8 100644
--- a/src/core/crypto/onion_crypto.c
+++ b/src/core/crypto/onion_crypto.c
@@ -35,14 +35,25 @@
 #include "core/crypto/onion_crypto.h"
 #include "core/crypto/onion_fast.h"
 #include "core/crypto/onion_ntor.h"
+#include "core/crypto/onion_ntor_v3.h"
 #include "core/crypto/onion_tap.h"
 #include "feature/relay/router.h"
 #include "lib/crypt_ops/crypto_dh.h"
 #include "lib/crypt_ops/crypto_util.h"
+#include "feature/relay/routerkeys.h"
+
+#include "core/or/circuitbuild.h"
 
 #include "core/or/crypt_path_st.h"
 #include "core/or/extend_info_st.h"
 
+/* TODO: Add this to the specification! */
+const uint8_t NTOR3_CIRC_VERIFICATION[] = "circuit extend";
+const size_t NTOR3_CIRC_VERIFICATION_LEN = 14;
+
+#define NTOR3_VERIFICATION_ARGS \
+  NTOR3_CIRC_VERIFICATION, NTOR3_CIRC_VERIFICATION_LEN
+
 /** Return a new server_onion_keys_t object with all of the keys
  * and other info we might need to do onion handshakes.  (We make a copy of
  * our keys for each cpuworker to avoid race conditions with the main thread,
@@ -52,6 +63,7 @@ server_onion_keys_new(void)
 {
   server_onion_keys_t *keys = tor_malloc_zero(sizeof(server_onion_keys_t));
   memcpy(keys->my_identity, router_get_my_id_digest(), DIGEST_LEN);
+  ed25519_pubkey_copy(&keys->my_ed_identity, get_master_identity_key());
   dup_onion_keys(&keys->onion_key, &keys->last_onion_key);
   keys->curve25519_key_map = construct_ntor_key_map();
   keys->junk_keypair = tor_malloc_zero(sizeof(curve25519_keypair_t));
@@ -91,6 +103,9 @@ onion_handshake_state_release(onion_handshake_state_t *state)
     ntor_handshake_state_free(state->u.ntor);
     state->u.ntor = NULL;
     break;
+  case ONION_HANDSHAKE_TYPE_NTOR_V3:
+    ntor3_handshake_state_free(state->u.ntor3);
+    break;
   default:
     /* LCOV_EXCL_START
      * This state should not even exist. */
@@ -149,6 +164,37 @@ onion_skin_create(int type,
 
     r = NTOR_ONIONSKIN_LEN;
     break;
+  case ONION_HANDSHAKE_TYPE_NTOR_V3:
+    if (!extend_info_supports_ntor_v3(node))
+      return -1;
+    if (ed25519_public_key_is_zero(&node->ed_identity))
+      return -1;
+    size_t msg_len = 0;
+    uint8_t *msg = NULL;
+    if (client_circ_negotiation_message(node, &msg, &msg_len) < 0)
+      return -1;
+    uint8_t *onion_skin = NULL;
+    size_t onion_skin_len = 0;
+    int status = onion_skin_ntor3_create(
+                             &node->ed_identity,
+                             &node->curve25519_onion_key,
+                             NTOR3_VERIFICATION_ARGS,
+                             msg, msg_len, /* client message */
+                             &state_out->u.ntor3,
+                             &onion_skin, &onion_skin_len);
+    tor_free(msg);
+    if (status < 0) {
+      return -1;
+    }
+    if (onion_skin_len > onion_skin_out_maxlen) {
+      tor_free(onion_skin);
+      return -1;
+    }
+    memcpy(onion_skin_out, onion_skin, onion_skin_len);
+    tor_free(onion_skin);
+    r = (int) onion_skin_len;
+    break;
+
   default:
     /* LCOV_EXCL_START
      * We should never try to create an impossible handshake type. */
@@ -238,6 +284,64 @@ onion_skin_server_handshake(int type,
       r = NTOR_REPLY_LEN;
     }
     break;
+  case ONION_HANDSHAKE_TYPE_NTOR_V3: {
+    size_t keys_tmp_len = keys_out_len + DIGEST_LEN;
+    tor_assert(keys_tmp_len <= MAX_KEYS_TMP_LEN);
+    uint8_t keys_tmp[MAX_KEYS_TMP_LEN];
+    uint8_t *client_msg = NULL;
+    size_t client_msg_len = 0;
+    ntor3_server_handshake_state_t *state = NULL;
+
+    if (onion_skin_ntor3_server_handshake_part1(
+               keys->curve25519_key_map,
+               keys->junk_keypair,
+               &keys->my_ed_identity,
+               onion_skin, onionskin_len,
+               NTOR3_VERIFICATION_ARGS,
+               &client_msg, &client_msg_len,
+               &state) < 0) {
+      return -1;
+    }
+
+    uint8_t reply_msg[1] = { 0 };
+    size_t reply_msg_len = 1;
+    {
+      /* TODO, Okay, we have a message from the client trying to negotiate
+       * parameters.  We need to decide whether the client's request is
+       * okay, what we're going to say in response, and what circuit
+       * parameters we've just negotiated
+       */
+
+      tor_free(client_msg);
+    }
+
+    uint8_t *server_handshake = NULL;
+    size_t server_handshake_len = 0;
+    if (onion_skin_ntor3_server_handshake_part2(
+               state,
+               NTOR3_VERIFICATION_ARGS,
+               reply_msg, reply_msg_len,
+               &server_handshake, &server_handshake_len,
+               keys_tmp, keys_tmp_len) < 0) {
+      // XXX TODO free some stuff
+      return -1;
+    }
+
+    if (server_handshake_len > reply_out_maxlen) {
+      // XXX TODO free that stuff
+      return -1;
+    }
+
+    memcpy(keys_out, keys_tmp, keys_out_len);
+    memcpy(rend_nonce_out, keys_tmp+keys_out_len, DIGEST_LEN);
+    memcpy(reply_out, server_handshake, server_handshake_len);
+    memwipe(keys_tmp, 0, keys_tmp_len);
+    memwipe(server_handshake, 0, server_handshake_len);
+    tor_free(server_handshake);
+
+    r = (int) server_handshake_len;
+  }
+    break;
   default:
     /* LCOV_EXCL_START
      * We should have rejected this far before this point */
@@ -321,6 +425,38 @@ onion_skin_client_handshake(int type,
       tor_free(keys_tmp);
     }
     return 0;
+  case ONION_HANDSHAKE_TYPE_NTOR_V3: {
+    size_t keys_tmp_len = keys_out_len + DIGEST_LEN;
+    uint8_t *keys_tmp = tor_malloc(keys_tmp_len);
+    uint8_t *server_msg = NULL;
+    size_t server_msg_len = 0;
+    int r = onion_ntor3_client_handshake(
+              handshake_state->u.ntor3,
+              reply, reply_len,
+              NTOR3_VERIFICATION_ARGS,
+              keys_tmp, keys_tmp_len,
+              &server_msg, &server_msg_len);
+    if (r < 0) {
+      tor_free(keys_tmp);
+      tor_free(server_msg);
+      return -1;
+    }
+
+    // XXXX handle the server message!
+    {
+      // XXXX TODO: see what the server said, make sure it's okay, see what
+      // parameters it gave us, make sure we like them, and put them into
+      // `params_out`
+    }
+    tor_free(server_msg);
+
+    memcpy(keys_out, keys_tmp, keys_out_len);
+    memcpy(rend_authenticator_out, keys_tmp + keys_out_len, DIGEST_LEN);
+    memwipe(keys_tmp, 0, keys_tmp_len);
+    tor_free(keys_tmp);
+
+    return 0;
+  }
   default:
     log_warn(LD_BUG, "called with unknown handshake state type %d", type);
     tor_fragile_assert();
diff --git a/src/core/crypto/onion_crypto.h b/src/core/crypto/onion_crypto.h
index af8dd1f03f..45e8eeca0c 100644
--- a/src/core/crypto/onion_crypto.h
+++ b/src/core/crypto/onion_crypto.h
@@ -12,8 +12,11 @@
 #ifndef TOR_ONION_CRYPTO_H
 #define TOR_ONION_CRYPTO_H
 
+#include "lib/crypt_ops/crypto_ed25519.h"
+
 typedef struct server_onion_keys_t {
   uint8_t my_identity[DIGEST_LEN];
+  ed25519_public_key_t my_ed_identity;
   crypto_pk_t *onion_key;
   crypto_pk_t *last_onion_key;
   struct di_digest256_map_t *curve25519_key_map;
diff --git a/src/core/or/circuitbuild.c b/src/core/or/circuitbuild.c
index f67fe196e5..ffb2c00493 100644
--- a/src/core/or/circuitbuild.c
+++ b/src/core/or/circuitbuild.c
@@ -841,7 +841,10 @@ circuit_pick_create_handshake(uint8_t *cell_type_out,
    * using the TAP handshake, and CREATE2 otherwise. */
   if (extend_info_supports_ntor(ei)) {
     *cell_type_out = CELL_CREATE2;
-    *handshake_type_out = ONION_HANDSHAKE_TYPE_NTOR;
+    if (ei->supports_ntor3_and_param_negotiation)
+      *handshake_type_out = ONION_HANDSHAKE_TYPE_NTOR_V3;
+    else
+      *handshake_type_out = ONION_HANDSHAKE_TYPE_NTOR;
   } else {
     /* XXXX030 Remove support for deciding to use TAP and EXTEND. */
     *cell_type_out = CELL_CREATE;
@@ -2579,3 +2582,24 @@ circuit_upgrade_circuits_from_guard_wait(void)
 
   smartlist_free(to_upgrade);
 }
+
+/**
+ * Try to generate a circuit-negotiation message for communication with a
+ * given relay.  Assumes we are using ntor v3, or some later version that
+ * supports parameter negotiatoin.
+ *
+ * On success, return 0 and pass back a message in the `out` parameters.
+ * Otherwise, return -1.
+ **/
+int
+client_circ_negotiation_message(const extend_info_t *ei,
+                                uint8_t **msg_out,
+                                size_t *msg_len_out)
+{
+  tor_assert(ei && msg_out && msg_len_out);
+  if (! ei->supports_ntor3_and_param_negotiation)
+    return -1;
+
+  /* TODO: fill in the client message that gets sent. */
+  tor_assert_unreached();
+}
diff --git a/src/core/or/circuitbuild.h b/src/core/or/circuitbuild.h
index 278cdfae1c..a66c611132 100644
--- a/src/core/or/circuitbuild.h
+++ b/src/core/or/circuitbuild.h
@@ -64,6 +64,10 @@ circuit_deliver_create_cell,(circuit_t *circ,
                              const struct create_cell_t *create_cell,
                              int relayed));
 
+int client_circ_negotiation_message(const extend_info_t *ei,
+                                    uint8_t **msg_out,
+                                    size_t *msg_len_out);
+
 #ifdef CIRCUITBUILD_PRIVATE
 STATIC circid_t get_unique_circ_id_by_chan(channel_t *chan);
 STATIC int new_route_len(uint8_t purpose, extend_info_t *exit_ei,
diff --git a/src/core/or/crypt_path_st.h b/src/core/or/crypt_path_st.h
index ddc85eec14..fdc6b6fbb2 100644
--- a/src/core/or/crypt_path_st.h
+++ b/src/core/or/crypt_path_st.h
@@ -21,11 +21,14 @@ struct fast_handshake_state_t;
 struct ntor_handshake_state_t;
 struct crypto_dh_t;
 struct onion_handshake_state_t {
+  /** One of `ONION_HANDSHAKE_TYPE_*`.  Determines which member of the union
+   * is accessible. */
   uint16_t tag;
   union {
     struct fast_handshake_state_t *fast;
     struct crypto_dh_t *tap;
     struct ntor_handshake_state_t *ntor;
+    struct ntor3_handshake_state_t *ntor3;
   } u;
 };
 
diff --git a/src/core/or/extend_info_st.h b/src/core/or/extend_info_st.h
index 868417f392..1666b168ad 100644
--- a/src/core/or/extend_info_st.h
+++ b/src/core/or/extend_info_st.h
@@ -38,6 +38,9 @@ struct extend_info_t {
   crypto_pk_t *onion_key;
   /** Ntor onion key for this hop. */
   curve25519_public_key_t curve25519_onion_key;
+  /** True if this hop supports NtorV3 _and_ negotiation of at least one
+   * relevant circuit parameter (currently only congestion control). */
+  bool supports_ntor3_and_param_negotiation;
 };
 
 #endif /* !defined(EXTEND_INFO_ST_H) */
diff --git a/src/core/or/extendinfo.c b/src/core/or/extendinfo.c
index 6bcef181be..f33e887e7d 100644
--- a/src/core/or/extendinfo.c
+++ b/src/core/or/extendinfo.c
@@ -56,6 +56,9 @@ extend_info_new(const char *nickname,
   if (addr) {
     extend_info_add_orport(info, addr, port);
   }
+
+  info->supports_ntor3_and_param_negotiation = false; // TODO: set this.
+
   return info;
 }
 
@@ -210,6 +213,15 @@ extend_info_supports_ntor(const extend_info_t* ei)
                           CURVE25519_PUBKEY_LEN);
 }
 
+/** Return true if we can use the Ntor v3 handshake with `ei` */
+int
+extend_info_supports_ntor_v3(const extend_info_t *ei)
+{
+  tor_assert(ei);
+  return extend_info_supports_ntor(ei) &&
+    ei->supports_ntor3_and_param_negotiation;
+}
+
 /* Does ei have an onion key which it would prefer to use?
  * Currently, we prefer ntor keys*/
 int
diff --git a/src/core/or/extendinfo.h b/src/core/or/extendinfo.h
index 9c07205709..ffe8317431 100644
--- a/src/core/or/extendinfo.h
+++ b/src/core/or/extendinfo.h
@@ -26,6 +26,7 @@ void extend_info_free_(extend_info_t *info);
 int extend_info_addr_is_allowed(const tor_addr_t *addr);
 int extend_info_supports_tap(const extend_info_t* ei);
 int extend_info_supports_ntor(const extend_info_t* ei);
+int extend_info_supports_ntor_v3(const extend_info_t *ei);
 int extend_info_has_preferred_onion_key(const extend_info_t* ei);
 bool extend_info_has_orport(const extend_info_t *ei,
                             const tor_addr_t *addr, uint16_t port);
diff --git a/src/core/or/or.h b/src/core/or/or.h
index 392a848ee7..3911797563 100644
--- a/src/core/or/or.h
+++ b/src/core/or/or.h
@@ -790,7 +790,8 @@ typedef enum {
 #define ONION_HANDSHAKE_TYPE_TAP  0x0000
 #define ONION_HANDSHAKE_TYPE_FAST 0x0001
 #define ONION_HANDSHAKE_TYPE_NTOR 0x0002
-#define MAX_ONION_HANDSHAKE_TYPE 0x0002
+#define ONION_HANDSHAKE_TYPE_NTOR_V3 0x0003 /* TODO: Add to spec */
+#define MAX_ONION_HANDSHAKE_TYPE 0x0003
 
 typedef struct onion_handshake_state_t onion_handshake_state_t;
 typedef struct relay_crypto_t relay_crypto_t;
diff --git a/src/feature/relay/relay_metrics.c b/src/feature/relay/relay_metrics.c
index fc8eb10d1b..908cfdb0d9 100644
--- a/src/feature/relay/relay_metrics.c
+++ b/src/feature/relay/relay_metrics.c
@@ -104,6 +104,8 @@ handshake_type_to_str(const uint16_t type)
       return "fast";
     case ONION_HANDSHAKE_TYPE_NTOR:
       return "ntor";
+    case ONION_HANDSHAKE_TYPE_NTOR_V3:
+      return "ntor_v3";
     default:
       // LCOV_EXCL_START
       tor_assert_unreached();