Merge branch 'tor-gitlab/mr/424'

8 files changed, 1385 insertions, 0 deletions

diff --git a/src/core/crypto/include.am b/src/core/crypto/include.am
index 28b7e22905..2d53b3cb0b 100644
--- a/src/core/crypto/include.am
+++ b/src/core/crypto/include.am
@@ -5,6 +5,7 @@ LIBTOR_APP_A_SOURCES += 				\
 	src/core/crypto/onion_crypto.c		\
 	src/core/crypto/onion_fast.c		\
 	src/core/crypto/onion_ntor.c		\
+	src/core/crypto/onion_ntor_v3.c		\
 	src/core/crypto/onion_tap.c		\
 	src/core/crypto/relay_crypto.c
 
@@ -14,5 +15,6 @@ noinst_HEADERS +=					\
 	src/core/crypto/onion_crypto.h	        	\
 	src/core/crypto/onion_fast.h			\
 	src/core/crypto/onion_ntor.h			\
+	src/core/crypto/onion_ntor_v3.h			\
 	src/core/crypto/onion_tap.h			\
 	src/core/crypto/relay_crypto.h
diff --git a/src/core/crypto/onion_ntor_v3.c b/src/core/crypto/onion_ntor_v3.c
new file mode 100644
index 0000000000..491c69cf8d
--- /dev/null
+++ b/src/core/crypto/onion_ntor_v3.c
@@ -0,0 +1,760 @@
+/* Copyright (c) 2001 Matej Pfajfar.
+ * Copyright (c) 2001-2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2021, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * @file onion_ntor_v3.c
+ * @brief Implements the version 3 ntor handshake as first specified in
+ * proposal 332.
+ *
+ * The v3 ntor handshake differs from the earlier versions (ntor and hs-ntor)
+ * primarily in that it allows the client to send an authenticated encrypted
+ * message as part of its onion skin, and allows the relay to send and
+ * encrypted authenticated reply as part of its response.
+ *
+ * It also takes a "verification string" -- the handshake cannot succeed
+ * unless both parties use the same value for their verification stream.
+ **/
+
+#define ONION_NTOR_V3_PRIVATE
+
+#include "orconfig.h"
+#include "core/crypto/onion_ntor_v3.h"
+
+#include "lib/arch/bytes.h"
+#include "lib/crypt_ops/crypto_digest.h"
+#include "lib/crypt_ops/crypto_rand.h"
+#include "lib/crypt_ops/crypto_util.h"
+#include "lib/ctime/di_ops.h"
+#include "lib/log/util_bug.h"
+
+#include <string.h>
+
+/* Parameters used to keep the outputs of this handshake from colliding with
+ * others.  These are defined in the specification. */
+#define PROTOID "ntor3-curve25519-sha3_256-1"
+#define TWEAK(A) (PROTOID ":" A)
+
+#define T_MSGKDF TWEAK("kdf_phase1")
+#define T_MSGMAC TWEAK("msg_mac")
+#define T_KEY_SEED TWEAK("key_seed")
+#define T_VERIFY TWEAK("verify")
+#define T_FINAL TWEAK("kdf_final")
+#define T_AUTH TWEAK("auth_final")
+
+/**
+ * Add @a len bytes of @a data as input to the provided @a xof.
+ *
+ * (This is provided just for abbreviation).
+ **/
+#define xof_add(xof, data, len) crypto_xof_add_bytes((xof), (data), (len))
+/**
+ * Add @a len bytes of @a data as input to the provided @a xof,
+ * prefixed with an encoding of the length.
+ *
+ * This is equivalent to ENCAP(data) in the spec.
+ **/
+static void
+xof_add_encap(crypto_xof_t *xof, const uint8_t *data, size_t len)
+{
+  uint64_t len64 = tor_htonll(len);
+  xof_add(xof, (uint8_t *)(&len64), 8);
+  xof_add(xof, data, len);
+}
+/**
+ * Add an encapsulated tweak to the provided xof.
+ **/
+#define xof_add_tweak(d, s) xof_add_encap((d), (const uint8_t *)(s), strlen(s))
+
+/**
+ * Add @a len bytes of @a data to the provided @a digest.
+ *
+ * This is provided as an abbreviation, and to get the types right.
+ **/
+static void
+d_add(crypto_digest_t *digest, const uint8_t *data, size_t len)
+{
+  crypto_digest_add_bytes(digest, (const char *)data, len);
+}
+/**
+ * Add @a len bytes of @a data to the provided @a digest, prefixed
+ * with the encoded length.
+ *
+ * This is equivalent to ENCAP(data) from the spec.
+ **/
+static void
+d_add_encap(crypto_digest_t *digest, const uint8_t *data, size_t len)
+{
+  uint64_t len64 = tor_htonll(len);
+  d_add(digest, (const uint8_t *)(&len64), 8);
+  d_add(digest, data, len);
+}
+/**
+ * Add an encapsulated tweak to the provided digest.
+ **/
+#define d_add_tweak(d, s) d_add_encap((d), (const uint8_t *)(s), strlen(s))
+
+/**
+ * Helper: copy @a len bytes of @a data onto *@a ptr, and advance @a ptr
+ * forward by @a len bytes.
+ *
+ * Asserts that @a ptr will not be advanced beyond @a endptr.
+ **/
+static void
+push(uint8_t **ptr, const uint8_t *endptr, const uint8_t *data, size_t len)
+{
+  size_t remaining = endptr - *ptr;
+  tor_assert(len <= remaining);
+  memcpy(*ptr, data, len);
+  *ptr += len;
+}
+
+/**
+ * Helper: Drop storage held by @a state, after wiping it.
+ **/
+void
+ntor3_handshake_state_free_(ntor3_handshake_state_t *state)
+{
+  if (!state)
+    return;
+
+  memwipe(state, 0, sizeof(*state));
+  tor_free(state);
+}
+
+/**
+ * Perform a client-side v3 ntor handshake with a given relay.
+ *
+ * As inputs this function takes the relay's Ed25519 identity (@a relay_id),
+ * the relay's current ntor onion key (@a relay_key), a verification string
+ * (@a verification_len bytes at @a verification), and a message to send
+ * as part of the handshake (@a message_len bytes at @a message).
+ *
+ * The message will be encrypted and authenticated to the relay, but will not
+ * receive the same forward secrecy as the rest of the handshake.  We should
+ * not put any super-confidential data in it.
+ *
+ * The handshake will only succeed if the relay uses the same verification
+ * string as we are using.
+ *
+ * As outputs, this function returns 0 on success and -1 on failure.  On
+ * success, it sets @a onion_skin_out and @a onion_skin_len_out to a newly
+ * allocated handshake message that the client can send as part of its CREATE2
+ * or EXTEND2 cell.  It also sets it sets @a handshake_state_out to a newly
+ * allocated handshake state object; the client needs to use this object to
+ * process the relay's eventual reply.
+ **/
+int
+onion_skin_ntor3_create(const ed25519_public_key_t *relay_id,
+                        const curve25519_public_key_t *relay_key,
+                        const uint8_t *verification,
+                        const size_t verification_len,
+                        const uint8_t *message,
+                        const size_t message_len,
+                        ntor3_handshake_state_t **handshake_state_out,
+                        uint8_t **onion_skin_out,
+                        size_t *onion_skin_len_out)
+{
+  curve25519_keypair_t client_keypair;
+  if (curve25519_keypair_generate(&client_keypair, 0) < 0) {
+    return -1;
+  }
+  int r = onion_skin_ntor3_create_nokeygen(
+                                   &client_keypair,
+                                   relay_id,
+                                   relay_key,
+                                   verification,
+                                   verification_len,
+                                   message,
+                                   message_len,
+                                   handshake_state_out,
+                                   onion_skin_out,
+                                   onion_skin_len_out);
+  memwipe(&client_keypair, 0, sizeof(client_keypair));
+  return r;
+}
+
+/**
+ * Like onion_skin_ntor3_create, but do not generate a new ephemeral keypair.
+ * Instead, take the ephemeral keypair (x,X) from @a client_keypair.
+ *
+ * (Having a separate function for this lets us test the code for correct
+ * behavior.)
+ **/
+STATIC int
+onion_skin_ntor3_create_nokeygen(
+                        const curve25519_keypair_t *client_keypair,
+                        const ed25519_public_key_t *relay_id,
+                        const curve25519_public_key_t *relay_key,
+                        const uint8_t *verification,
+                        const size_t verification_len,
+                        const uint8_t *message,
+                        const size_t message_len,
+                        ntor3_handshake_state_t **handshake_state_out,
+                        uint8_t **onion_skin_out,
+                        size_t *onion_skin_len_out)
+{
+  *handshake_state_out = NULL;
+  *onion_skin_out = NULL;
+  *onion_skin_len_out = 0;
+
+  // Set up the handshake state object.
+  *handshake_state_out = tor_malloc_zero(sizeof(ntor3_handshake_state_t));
+  memcpy(&(*handshake_state_out)->client_keypair, client_keypair,
+         sizeof(*client_keypair));
+  memcpy(&(*handshake_state_out)->relay_id, relay_id, sizeof(*relay_id));
+  memcpy(&(*handshake_state_out)->relay_key, relay_key, sizeof(*relay_key));
+
+  // Perform the first DH handshake.
+  curve25519_handshake((*handshake_state_out)->bx,
+                       &client_keypair->seckey, relay_key);
+  if (safe_mem_is_zero((*handshake_state_out)->bx, CURVE25519_OUTPUT_LEN)) {
+    // Okay to return early here, since our behavior here doesn't
+    // cause a visible timing sidechannel.
+    return -1;
+  }
+
+  // Compute phase1_keys.
+  uint8_t enc_key[CIPHER256_KEY_LEN];
+  uint8_t mac_key[DIGEST256_LEN];
+  {
+    crypto_xof_t *xof = crypto_xof_new();
+    // secret_input_phase1 = Bx | ID | X | B | PROTOID | ENCAP(VER)
+    xof_add_tweak(xof, T_MSGKDF);
+    xof_add(xof, (*handshake_state_out)->bx, CURVE25519_OUTPUT_LEN);
+    xof_add(xof, relay_id->pubkey, ED25519_PUBKEY_LEN);
+    xof_add(xof, client_keypair->pubkey.public_key, CURVE25519_PUBKEY_LEN);
+    xof_add(xof, relay_key->public_key, CURVE25519_PUBKEY_LEN);
+    xof_add(xof, (const uint8_t *)PROTOID, strlen(PROTOID));
+    xof_add_encap(xof, verification, verification_len);
+    crypto_xof_squeeze_bytes(xof, enc_key, sizeof(enc_key));
+    crypto_xof_squeeze_bytes(xof, mac_key, sizeof(mac_key));
+    crypto_xof_free(xof);
+  }
+
+  // Compute encrypted message.
+  uint8_t *encrypted_message = tor_memdup(message, message_len);
+  {
+    crypto_cipher_t *c =
+      crypto_cipher_new_with_bits((const char *)enc_key, 256);
+    crypto_cipher_crypt_inplace(c, (char *)encrypted_message, message_len);
+    crypto_cipher_free(c);
+  }
+
+  // Compute the MAC value.
+  {
+    crypto_digest_t *m = crypto_digest256_new(DIGEST_SHA3_256);
+    d_add_tweak(m, T_MSGMAC);
+    d_add_encap(m, mac_key, sizeof(mac_key));
+    d_add(m, relay_id->pubkey, ED25519_PUBKEY_LEN);
+    d_add(m, relay_key->public_key, CURVE25519_PUBKEY_LEN);
+    d_add(m, client_keypair->pubkey.public_key, CURVE25519_PUBKEY_LEN);
+    d_add(m, encrypted_message, message_len);
+    crypto_digest_get_digest(m,
+                             (char *)(*handshake_state_out)->msg_mac,
+                             DIGEST256_LEN);
+    crypto_digest_free(m);
+  }
+
+  // Build the onionskin.
+  *onion_skin_len_out = (ED25519_PUBKEY_LEN + CURVE25519_PUBKEY_LEN*2 +
+                          DIGEST256_LEN + message_len);
+  *onion_skin_out = tor_malloc(*onion_skin_len_out);
+  {
+    uint8_t *ptr = *onion_skin_out, *end = ptr + *onion_skin_len_out;
+
+    push(&ptr, end, relay_id->pubkey, ED25519_PUBKEY_LEN);
+    push(&ptr, end, relay_key->public_key, CURVE25519_PUBKEY_LEN);
+    push(&ptr, end, client_keypair->pubkey.public_key, CURVE25519_PUBKEY_LEN);
+    push(&ptr, end, encrypted_message, message_len);
+    push(&ptr, end, (*handshake_state_out)->msg_mac, DIGEST256_LEN);
+    tor_assert(ptr == end);
+  }
+
+  memwipe(&enc_key, 0, sizeof(enc_key));
+  memwipe(&mac_key, 0, sizeof(mac_key));
+  memwipe(encrypted_message, 0, message_len);
+  tor_free(encrypted_message);
+
+  return 0;
+}
+
+/**
+ * Complete a client-side v3 ntor handshake.
+ *
+ * Takes a @a handshake_state returned earlier by `onion_skin_ntor3_create()`,
+ * and the relay's reply to that handshake (@a reply_len bytes at @a
+ * handshake_reply).  Also takes a verification string (@a verification_len
+ * bytes at @a verification).
+ *
+ * Returns 0 on success and -1 on failure. On success, generates @a key_len
+ * bytes of key material into the provided @a keys_out buffer, and sets @a
+ * message_out to the message that the relay sent in reply to our message (and
+ * sets @a message_out_len to that message's length).
+ **/
+int
+onion_ntor3_client_handshake(const ntor3_handshake_state_t *handshake_state,
+                             const uint8_t *handshake_reply,
+                             size_t reply_len,
+                             const uint8_t *verification,
+                             size_t verification_len,
+                             uint8_t *keys_out,
+                             size_t keys_out_len,
+                             uint8_t **message_out,
+                             size_t *message_len_out)
+{
+  *message_out = NULL;
+  *message_len_out = 0;
+
+  int problems = 0;
+
+  // Parse the relay's message.
+  curve25519_public_key_t relay_Y;
+  uint8_t relay_auth[DIGEST256_LEN];
+  size_t encrypted_msg_len;
+  const uint8_t *encrypted_msg;
+  {
+    if (reply_len < CURVE25519_PUBKEY_LEN + DIGEST256_LEN) {
+      // Okay to return early here, since the message is completely
+      // ill-formed, so we can't leak anything.
+      ++problems;
+      goto done;
+    }
+    encrypted_msg_len = reply_len - (CURVE25519_PUBKEY_LEN + DIGEST256_LEN);
+
+    memcpy(&relay_Y.public_key, handshake_reply, CURVE25519_PUBKEY_LEN);
+    handshake_reply += CURVE25519_PUBKEY_LEN;
+    memcpy(&relay_auth, handshake_reply, DIGEST256_LEN);
+    handshake_reply += DIGEST256_LEN;
+    encrypted_msg = handshake_reply;
+  }
+
+  // Finish the second diffie hellman handshake.
+  uint8_t yx[CURVE25519_OUTPUT_LEN];
+  curve25519_handshake(yx, &handshake_state->client_keypair.seckey, &relay_Y);
+  problems |= safe_mem_is_zero(yx, sizeof(yx));
+
+  // Compute two tweaked hashes of secret_input.
+  uint8_t key_seed[DIGEST256_LEN], verify[DIGEST256_LEN];
+  {
+    crypto_digest_t *ks = crypto_digest256_new(DIGEST_SHA3_256);
+    crypto_digest_t *v = crypto_digest256_new(DIGEST_SHA3_256);
+    d_add_tweak(ks, T_KEY_SEED);
+    d_add_tweak(v, T_VERIFY);
+#define ADD2(s,len) STMT_BEGIN { \
+      d_add(ks, (s),(len)); d_add(v, (s), (len));       \
+    } STMT_END
+#define ADD2_ENCAP(s,len) STMT_BEGIN { \
+        d_add_encap(ks, (s),(len)); d_add_encap(v, (s), (len)); \
+      } STMT_END
+
+    ADD2(yx, sizeof(yx));
+    ADD2(handshake_state->bx, sizeof(handshake_state->bx));
+    ADD2(handshake_state->relay_id.pubkey, ED25519_PUBKEY_LEN);
+    ADD2(handshake_state->relay_key.public_key, CURVE25519_PUBKEY_LEN);
+    ADD2(handshake_state->client_keypair.pubkey.public_key,
+         CURVE25519_PUBKEY_LEN);
+    ADD2(relay_Y.public_key, CURVE25519_PUBKEY_LEN);
+    ADD2((const uint8_t *)PROTOID, strlen(PROTOID));
+    ADD2_ENCAP(verification, verification_len);
+
+    crypto_digest_get_digest(ks, (char*) key_seed, DIGEST256_LEN);
+    crypto_digest_get_digest(v, (char*) verify, DIGEST256_LEN);
+    crypto_digest_free(ks);
+    crypto_digest_free(v);
+  }
+
+  // compute expected auth value.
+  uint8_t auth_computed[DIGEST256_LEN];
+  {
+    crypto_digest_t *d = crypto_digest256_new(DIGEST_SHA3_256);
+    d_add_tweak(d, T_AUTH);
+    d_add(d, verify, sizeof(verify));
+    d_add(d, handshake_state->relay_id.pubkey, ED25519_PUBKEY_LEN);
+    d_add(d, handshake_state->relay_key.public_key, CURVE25519_PUBKEY_LEN);
+    d_add(d, relay_Y.public_key, CURVE25519_PUBKEY_LEN);
+    d_add(d, handshake_state->client_keypair.pubkey.public_key,
+          CURVE25519_PUBKEY_LEN);
+    d_add(d, handshake_state->msg_mac, DIGEST256_LEN);
+    d_add_encap(d, encrypted_msg, encrypted_msg_len);
+    d_add(d, (const uint8_t*)PROTOID, strlen(PROTOID));
+    d_add(d, (const uint8_t*)"Server", strlen("Server"));
+    crypto_digest_get_digest(d, (char *)auth_computed, DIGEST256_LEN);
+    crypto_digest_free(d);
+  }
+
+  // Check authentication value.
+  problems |= tor_memneq(auth_computed, relay_auth, DIGEST256_LEN);
+
+  // Compute keystream, decrypt message, and return.
+  *message_out = tor_malloc(encrypted_msg_len);
+  *message_len_out = encrypted_msg_len;
+  uint8_t enc_key[CIPHER256_KEY_LEN];
+  {
+    crypto_xof_t *xof = crypto_xof_new();
+    xof_add_tweak(xof, T_FINAL);
+    xof_add(xof, key_seed, sizeof(key_seed));
+    crypto_xof_squeeze_bytes(xof, enc_key, sizeof(enc_key));
+    crypto_xof_squeeze_bytes(xof, (uint8_t *)keys_out, keys_out_len);
+    crypto_xof_free(xof);
+
+    crypto_cipher_t *c =
+      crypto_cipher_new_with_bits((const char *)enc_key, 256);
+    crypto_cipher_decrypt(c, (char *)*message_out,
+                          (const char *)encrypted_msg, encrypted_msg_len);
+    crypto_cipher_free(c);
+  }
+
+ done:
+  memwipe(&relay_Y, 0, sizeof(relay_Y));
+  memwipe(&relay_auth, 0, sizeof(relay_auth));
+  memwipe(&yx, 0, sizeof(yx));
+  memwipe(key_seed, 0, sizeof(key_seed));
+  memwipe(verify, 0, sizeof(verify));
+  memwipe(enc_key, 0, sizeof(enc_key));
+  if (problems) {
+    if (*message_out) {
+      memwipe(*message_out, 0, *message_len_out);
+      tor_free(*message_out); // Sets it to NULL.
+    }
+    *message_len_out = 0;
+    crypto_rand((char*)keys_out, keys_out_len); // In case bad code uses it.
+    return -1;
+  }
+
+  return 0;
+}
+
+/**
+ * Wipe a server handshake state, and release the storage it holds.
+ **/
+void
+ntor3_server_handshake_state_free_(ntor3_server_handshake_state_t *state)
+{
+  if (state == NULL)
+    return;
+
+  memwipe(state, 0, sizeof(ntor3_server_handshake_state_t));
+  tor_free(state);
+}
+
+/**
+ * As a relay, start handling a client's v3 ntor handshake.
+ *
+ * This function performs the _first half_ of the handshake, up to the point
+ * where the client's message is decoded.  After calling it, the relay should
+ * decide how and whether to reply to the client's message, compose its reply,
+ * and call `onion_skin_ntor3_server_handshake_part2`.
+ *
+ * It takes as input a map of the relay's known onion keys in @a private_keys,
+ * along with a fake @a junk_key to use if there is a complete mismatch.  It
+ * takes the relay's ed25519 identity in @a my_id, along with the client's
+ * handshake message (@a client_handshake_len bytes in @a client_handshake),
+ * and a verification string (@a verification_len bytes in @a verification).
+ *
+ * Return 0 on success, and -1 on failure.  On success, sets @a
+ * client_message_out to a newly allocated string holding the plaintext of the
+ * message that the client sent as part of its handshake, and @a
+ * client_message_out_len to its length. Also sets @a state_out to a newly
+ * allocated state object holding the intermediate computation for this
+ * handshake.
+ **/
+int
+onion_skin_ntor3_server_handshake_part1(
+                const di_digest256_map_t *private_keys,
+                const curve25519_keypair_t *junk_key,
+                const ed25519_public_key_t *my_id,
+                const uint8_t *client_handshake,
+                size_t client_handshake_len,
+                const uint8_t *verification,
+                size_t verification_len,
+                uint8_t **client_message_out,
+                size_t *client_message_len_out,
+                ntor3_server_handshake_state_t **state_out)
+{
+  *client_message_out = NULL;
+  *client_message_len_out = 0;
+  *state_out = NULL;
+
+  int problems = 0;
+
+  // Initialize state.
+  (*state_out) = tor_malloc_zero(sizeof(ntor3_server_handshake_state_t));
+  memcpy(&(*state_out)->my_id, my_id, sizeof(*my_id));
+
+  const uint8_t *wanted_id; // [ED25519_PUBKEY_LEN]
+  const uint8_t *wanted_key; // [CURVE25519_PUBKEY_LEN]
+  const uint8_t *encrypted_message;
+  size_t encrypted_message_len;
+  // Unpack the client handshake.
+  {
+    const uint8_t *ptr = client_handshake;
+    const uint8_t *end = ptr + client_handshake_len;
+
+    if (client_handshake_len <
+        ED25519_PUBKEY_LEN + CURVE25519_PUBKEY_LEN * 2 + DIGEST256_LEN) {
+      // Okay to end early; the client knows this is unparseable already.
+      ++problems;
+      goto done;
+    }
+    wanted_id = ptr;
+    ptr += ED25519_PUBKEY_LEN;
+    wanted_key = ptr;
+    ptr += CURVE25519_PUBKEY_LEN;
+    memcpy((*state_out)->client_key.public_key, ptr, CURVE25519_PUBKEY_LEN);
+    ptr += CURVE25519_PUBKEY_LEN;
+    size_t remaining = (end-ptr);
+    if (BUG(remaining < DIGEST256_LEN)) {
+      // Okay to end early; this is a bug.
+      ++problems;
+      goto done;
+    }
+    encrypted_message = ptr;
+    encrypted_message_len = remaining - DIGEST256_LEN;
+    ptr += encrypted_message_len;
+    remaining = (end-ptr);
+    tor_assert(remaining == DIGEST256_LEN);
+    memcpy((*state_out)->msg_mac, ptr, DIGEST256_LEN);
+  }
+
+  // Check the identity.
+  problems |= tor_memneq(my_id->pubkey, wanted_id, ED25519_PUBKEY_LEN);
+
+  // Find the correct keypair.
+  const curve25519_keypair_t *keypair =
+    dimap_search(private_keys, wanted_key, (void *)junk_key);
+  tor_assert(keypair);
+  memcpy(&(*state_out)->my_key, &keypair->pubkey,
+         sizeof(curve25519_public_key_t));
+
+  // Do the first diffie hellman handshake.
+  curve25519_handshake((*state_out)->xb,
+                       &keypair->seckey, &(*state_out)->client_key);
+  problems |= safe_mem_is_zero((*state_out)->xb, CURVE25519_OUTPUT_LEN);
+
+  // Derive the encryption and mac keys
+  uint8_t enc_key[CIPHER256_KEY_LEN], mac_key[DIGEST256_LEN];
+  {
+    crypto_xof_t *xof = crypto_xof_new();
+    xof_add_tweak(xof, T_MSGKDF);
+    xof_add(xof, (*state_out)->xb, CURVE25519_OUTPUT_LEN);
+    xof_add(xof, wanted_id, ED25519_PUBKEY_LEN);
+    xof_add(xof, (*state_out)->client_key.public_key, CURVE25519_PUBKEY_LEN);
+    xof_add(xof, keypair->pubkey.public_key, CURVE25519_PUBKEY_LEN);
+    xof_add(xof, (const uint8_t *)PROTOID, strlen(PROTOID));
+    xof_add_encap(xof, verification, verification_len);
+    crypto_xof_squeeze_bytes(xof, enc_key, sizeof(enc_key));
+    crypto_xof_squeeze_bytes(xof, mac_key, sizeof(mac_key));
+    crypto_xof_free(xof);
+  }
+
+  // Check the MAC.
+  uint8_t computed_mac[DIGEST256_LEN];
+  {
+    crypto_digest_t *d = crypto_digest256_new(DIGEST_SHA3_256);
+    d_add_tweak(d, T_MSGMAC);
+    d_add_encap(d, mac_key, sizeof(mac_key));
+    d_add(d, my_id->pubkey, ED25519_PUBKEY_LEN);
+    d_add(d, keypair->pubkey.public_key, CURVE25519_PUBKEY_LEN);
+    d_add(d, (*state_out)->client_key.public_key, CURVE25519_PUBKEY_LEN);
+    d_add(d, encrypted_message, encrypted_message_len);
+    crypto_digest_get_digest(d, (char *)computed_mac, DIGEST256_LEN);
+    crypto_digest_free(d);
+  }
+
+  problems |= tor_memneq((*state_out)->msg_mac, computed_mac, DIGEST256_LEN);
+
+  // Decrypt the message.
+  *client_message_out = tor_malloc(encrypted_message_len);
+  *client_message_len_out = encrypted_message_len;
+  {
+    crypto_cipher_t *c =
+      crypto_cipher_new_with_bits((const char *)enc_key, 256);
+    crypto_cipher_decrypt(c, (char *)*client_message_out,
+                          (const char *)encrypted_message,
+                          encrypted_message_len);
+    crypto_cipher_free(c);
+  }
+
+ done:
+  memwipe(enc_key, 0, sizeof(enc_key));
+  memwipe(mac_key, 0, sizeof(mac_key));
+  memwipe(computed_mac, 0, sizeof(computed_mac));
+  if (problems) {
+    if (*client_message_out) {
+      memwipe(*client_message_out, 0, *client_message_len_out);
+      tor_free(*client_message_out); // Sets it to NULL.
+    }
+    *client_message_len_out = 0;
+    ntor3_server_handshake_state_free(*state_out);
+    return -1;
+  }
+
+  return 0;
+}
+
+/**
+ * Finish the relay side of an ntor v3 handshake.
+ *
+ * The relay calls this function after it has decided to respond to the
+ * client's original encrypted message.  This function receives the relay's
+ * message in @a server_message and its length in @a server_message_len, and
+ * completes the handshake.
+ *
+ * Returns 0 on success and -1 on failure. On success, stores the newly
+ * allocated handshake for the relay to send in @a handshake_out, and its
+ * length in @a handshake_len_out.  Stores @a keys_out_len bytes of generated
+ * keys in the provided buffer at @a keys_out.
+ **/
+int
+onion_skin_ntor3_server_handshake_part2(
+                const ntor3_server_handshake_state_t *state,
+                const uint8_t *verification,
+                size_t verification_len,
+                const uint8_t *server_message,
+                size_t server_message_len,
+                uint8_t **handshake_out,
+                size_t *handshake_len_out,
+                uint8_t *keys_out,
+                size_t keys_out_len)
+{
+  curve25519_keypair_t relay_keypair;
+  if (curve25519_keypair_generate(&relay_keypair, 0) < 0) {
+    return -1;
+  }
+  int r = onion_skin_ntor3_server_handshake_part2_nokeygen(
+              &relay_keypair,
+              state,
+              verification,
+              verification_len,
+              server_message,
+              server_message_len,
+              handshake_out,
+              handshake_len_out,
+              keys_out,
+              keys_out_len);
+  memwipe(&relay_keypair, 0, sizeof(relay_keypair));
+  return r;
+}
+
+/**
+ * Like `onion_skin_ntor3_server_handshake_part2`, but do not generate
+ * an ephemeral (y,Y) keypair.
+ *
+ * Instead, this function takes that keypair as @a relay_keypair_y.
+ *
+ * (Having a separate function for this lets us test the code for correct
+ * behavior.)
+ **/
+STATIC int
+onion_skin_ntor3_server_handshake_part2_nokeygen(
+                const curve25519_keypair_t *relay_keypair_y,
+                const ntor3_server_handshake_state_t *state,
+                const uint8_t *verification,
+                size_t verification_len,
+                const uint8_t *server_message,
+                size_t server_message_len,
+                uint8_t **handshake_out,
+                size_t *handshake_len_out,
+                uint8_t *keys_out,
+                size_t keys_out_len)
+{
+  *handshake_out = NULL;
+  *handshake_len_out = 0;
+
+  int problems = 0;
+
+  // Second diffie-hellman handshake.
+  uint8_t xy[CURVE25519_OUTPUT_LEN];
+  curve25519_handshake(xy, &relay_keypair_y->seckey, &state->client_key);
+  problems |= safe_mem_is_zero(xy, sizeof(xy));
+
+  // Compute two tweaked hashes of secret_input.
+  uint8_t key_seed[DIGEST256_LEN], verify[DIGEST256_LEN];
+  {
+    crypto_digest_t *ks = crypto_digest256_new(DIGEST_SHA3_256);
+    crypto_digest_t *v = crypto_digest256_new(DIGEST_SHA3_256);
+    d_add_tweak(ks, T_KEY_SEED);
+    d_add_tweak(v, T_VERIFY);
+    ADD2(xy, sizeof(xy));
+    ADD2(state->xb, sizeof(state->xb));
+    ADD2(state->my_id.pubkey, ED25519_PUBKEY_LEN);
+    ADD2(state->my_key.public_key, CURVE25519_PUBKEY_LEN);
+    ADD2(state->client_key.public_key, CURVE25519_PUBKEY_LEN);
+    ADD2(relay_keypair_y->pubkey.public_key, CURVE25519_PUBKEY_LEN);
+    ADD2((const uint8_t *)PROTOID, strlen(PROTOID));
+    ADD2_ENCAP(verification, verification_len);
+    crypto_digest_get_digest(ks, (char*) key_seed, DIGEST256_LEN);
+    crypto_digest_get_digest(v, (char*) verify, DIGEST256_LEN);
+    crypto_digest_free(ks);
+    crypto_digest_free(v);
+  }
+
+  // Compute enc_key and keystream.
+  uint8_t enc_key[CIPHER256_KEY_LEN];
+  {
+    crypto_xof_t *xof = crypto_xof_new();
+    xof_add_tweak(xof, T_FINAL);
+    xof_add(xof, key_seed, sizeof(key_seed));
+    crypto_xof_squeeze_bytes(xof, enc_key, sizeof(enc_key));
+    crypto_xof_squeeze_bytes(xof, keys_out, keys_out_len);
+    crypto_xof_free(xof);
+  }
+
+  // Encrypt message.
+  uint8_t *encrypted_message = tor_memdup(server_message, server_message_len);
+  {
+    crypto_cipher_t *c =
+      crypto_cipher_new_with_bits((const char *)enc_key, 256);
+    crypto_cipher_crypt_inplace(
+                c, (char *)encrypted_message, server_message_len);
+    crypto_cipher_free(c);
+  }
+
+  // Compute AUTH digest.
+  uint8_t auth[DIGEST256_LEN];
+  {
+    crypto_digest_t *d = crypto_digest256_new(DIGEST_SHA3_256);
+    d_add_tweak(d, T_AUTH);
+    d_add(d, verify, sizeof(verify));
+    d_add(d, state->my_id.pubkey, ED25519_PUBKEY_LEN);
+    d_add(d, state->my_key.public_key, CURVE25519_PUBKEY_LEN);
+    d_add(d, relay_keypair_y->pubkey.public_key, CURVE25519_PUBKEY_LEN);
+    d_add(d, state->client_key.public_key, CURVE25519_PUBKEY_LEN);
+    d_add(d, state->msg_mac, DIGEST256_LEN);
+    d_add_encap(d, encrypted_message, server_message_len);
+    d_add(d, (const uint8_t*)PROTOID, strlen(PROTOID));
+    d_add(d, (const uint8_t*)"Server", strlen("Server"));
+    crypto_digest_get_digest(d, (char *)auth, DIGEST256_LEN);
+    crypto_digest_free(d);
+  }
+
+  // Compose the reply.
+  *handshake_len_out = CURVE25519_PUBKEY_LEN + DIGEST256_LEN +
+    server_message_len;
+  *handshake_out = tor_malloc(*handshake_len_out);
+  uint8_t *ptr = *handshake_out, *end = ptr + *handshake_len_out;
+  push(&ptr, end, relay_keypair_y->pubkey.public_key, CURVE25519_PUBKEY_LEN);
+  push(&ptr, end, auth, sizeof(auth));
+  push(&ptr, end, encrypted_message, server_message_len);
+  tor_assert(ptr == end);
+
+  // Clean up and return.
+  memwipe(xy, 0, sizeof(xy));
+  memwipe(key_seed, 0, sizeof(key_seed));
+  memwipe(verify, 0, sizeof(verify));
+  memwipe(enc_key, 0, sizeof(enc_key));
+  memwipe(encrypted_message, 0, server_message_len);
+  tor_free(encrypted_message);
+
+  if (problems) {
+    memwipe(*handshake_out, 0, *handshake_len_out);
+    tor_free(*handshake_out); // Sets it to NULL.
+    *handshake_len_out = 0;
+    crypto_rand((char*)keys_out, keys_out_len); // In case bad code uses it.
+    return -1;
+  }
+  return 0;
+}
diff --git a/src/core/crypto/onion_ntor_v3.h b/src/core/crypto/onion_ntor_v3.h
new file mode 100644
index 0000000000..4449eb237d
--- /dev/null
+++ b/src/core/crypto/onion_ntor_v3.h
@@ -0,0 +1,140 @@
+/* Copyright (c) 2001 Matej Pfajfar.
+ * Copyright (c) 2001-2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2021, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * @file onion_ntor_v3.h
+ * @brief Header for core/crypto/onion_ntor_v3.c
+ **/
+
+#ifndef TOR_CORE_CRYPTO_ONION_NTOR_V3_H
+#define TOR_CORE_CRYPTO_ONION_NTOR_V3_H
+
+#include "lib/cc/torint.h"
+#include "lib/testsupport/testsupport.h"
+#include "lib/crypt_ops/crypto_cipher.h"
+#include "lib/crypt_ops/crypto_curve25519.h"
+#include "lib/crypt_ops/crypto_ed25519.h"
+#include "lib/malloc/malloc.h"
+
+/**
+ * Client-side state held while an ntor v3 handshake is in progress.
+ **/
+typedef struct ntor3_handshake_state_t ntor3_handshake_state_t;
+
+/**
+ * Server-side state held while the relay is handling a client's
+ * encapsulated message, before replying to the v3 handshake.
+ **/
+typedef struct ntor3_server_handshake_state_t ntor3_server_handshake_state_t;
+
+void ntor3_handshake_state_free_(ntor3_handshake_state_t *st);
+#define ntor3_handshake_state_free(ptr) \
+  FREE_AND_NULL(ntor3_handshake_state_t, ntor3_handshake_state_free_, (ptr))
+void ntor3_server_handshake_state_free_(ntor3_server_handshake_state_t *st);
+#define ntor3_server_handshake_state_free(ptr) \
+  FREE_AND_NULL(ntor3_server_handshake_state_t, \
+                ntor3_server_handshake_state_free_, (ptr))
+
+int onion_skin_ntor3_create(const ed25519_public_key_t *relay_id,
+                            const curve25519_public_key_t *relay_key,
+                            const uint8_t *verification,
+                            const size_t verification_len,
+                            const uint8_t *message,
+                            const size_t message_len,
+                            ntor3_handshake_state_t **handshake_state_out,
+                            uint8_t **onion_skin_out,
+                            size_t *onion_skin_len_out);
+
+int onion_ntor3_client_handshake(
+                             const ntor3_handshake_state_t *handshake_state,
+                             const uint8_t *handshake_reply,
+                             size_t reply_len,
+                             const uint8_t *verification,
+                             size_t verification_len,
+                             uint8_t *keys_out,
+                             size_t keys_out_len,
+                             uint8_t **message_out,
+                             size_t *message_len_out);
+
+struct di_digest256_map_t;
+int onion_skin_ntor3_server_handshake_part1(
+                const struct di_digest256_map_t *private_keys,
+                const curve25519_keypair_t *junk_key,
+                const ed25519_public_key_t *my_id,
+                const uint8_t *client_handshake,
+                size_t client_handshake_len,
+                const uint8_t *verification,
+                size_t verification_len,
+                uint8_t **client_message_out,
+                size_t *client_message_len_out,
+                ntor3_server_handshake_state_t **state_out);
+
+int onion_skin_ntor3_server_handshake_part2(
+                const ntor3_server_handshake_state_t *state,
+                const uint8_t *verification,
+                size_t verification_len,
+                const uint8_t *server_message,
+                size_t server_message_len,
+                uint8_t **handshake_out,
+                size_t *handshake_len_out,
+                uint8_t *keys_out,
+                size_t keys_out_len);
+
+#ifdef ONION_NTOR_V3_PRIVATE
+struct ntor3_handshake_state_t {
+  /** Ephemeral (x,X) keypair. */
+  curve25519_keypair_t client_keypair;
+  /** Relay's ed25519 identity key (ID) */
+  ed25519_public_key_t relay_id;
+  /** Relay's public key (B) */
+  curve25519_public_key_t relay_key;
+  /** Shared secret (Bx). */
+  uint8_t bx[CURVE25519_OUTPUT_LEN];
+  /** MAC of the client's encrypted message data (MAC) */
+  uint8_t msg_mac[DIGEST256_LEN];
+};
+
+struct ntor3_server_handshake_state_t {
+  /** Relay's ed25519 identity key (ID) */
+  ed25519_public_key_t my_id;
+  /** Relay's public key (B) */
+  curve25519_public_key_t my_key;
+  /** Client's public ephemeral key (X). */
+  curve25519_public_key_t client_key;
+
+  /** Shared secret (Xb) */
+  uint8_t xb[CURVE25519_OUTPUT_LEN];
+  /** MAC of the client's encrypted message data */
+  uint8_t msg_mac[DIGEST256_LEN];
+};
+
+STATIC int onion_skin_ntor3_create_nokeygen(
+                        const curve25519_keypair_t *client_keypair,
+                        const ed25519_public_key_t *relay_id,
+                        const curve25519_public_key_t *relay_key,
+                        const uint8_t *verification,
+                        const size_t verification_len,
+                        const uint8_t *message,
+                        const size_t message_len,
+                        ntor3_handshake_state_t **handshake_state_out,
+                        uint8_t **onion_skin_out,
+                        size_t *onion_skin_len_out);
+
+STATIC int onion_skin_ntor3_server_handshake_part2_nokeygen(
+                const curve25519_keypair_t *relay_keypair_y,
+                const ntor3_server_handshake_state_t *state,
+                const uint8_t *verification,
+                size_t verification_len,
+                const uint8_t *server_message,
+                size_t server_message_len,
+                uint8_t **handshake_out,
+                size_t *handshake_len_out,
+                uint8_t *keys_out,
+                size_t keys_out_len);
+
+#endif
+
+#endif /* !defined(TOR_CORE_CRYPTO_ONION_NTOR_V3_H) */
diff --git a/src/test/include.am b/src/test/include.am
index b5e121d1ad..0dc1630044 100644
--- a/src/test/include.am
+++ b/src/test/include.am
@@ -204,6 +204,7 @@ src_test_test_SOURCES += \
 	src/test/test_namemap.c \
 	src/test/test_netinfo.c \
 	src/test/test_nodelist.c \
+	src/test/test_ntor_v3.c \
 	src/test/test_oom.c \
 	src/test/test_oos.c \
 	src/test/test_options.c \
diff --git a/src/test/ntor_v3_ref.py b/src/test/ntor_v3_ref.py
new file mode 100755
index 0000000000..28bc077105
--- /dev/null
+++ b/src/test/ntor_v3_ref.py
@@ -0,0 +1,308 @@
+#!/usr/bin/python
+
+import binascii
+import hashlib
+import os
+import struct
+
+import donna25519
+from Crypto.Cipher import AES
+from Crypto.Util import Counter
+
+# Define basic wrappers.
+
+DIGEST_LEN = 32
+ENC_KEY_LEN = 32
+PUB_KEY_LEN = 32
+SEC_KEY_LEN = 32
+IDENTITY_LEN = 32
+
+def sha3_256(s):
+    d = hashlib.sha3_256(s).digest()
+    assert len(d) == DIGEST_LEN
+    return d
+
+def shake_256(s):
+    # Note: In reality, you wouldn't want to generate more bytes than needed.
+    MAX_KEY_BYTES = 1024
+    return hashlib.shake_256(s).digest(MAX_KEY_BYTES)
+
+def curve25519(pk, sk):
+    assert len(pk) == PUB_KEY_LEN
+    assert len(sk) == SEC_KEY_LEN
+    private = donna25519.PrivateKey.load(sk)
+    public = donna25519.PublicKey(pk)
+    return private.do_exchange(public)
+
+def keygen():
+    private = donna25519.PrivateKey()
+    public = private.get_public()
+    return (private.private, public.public)
+
+def aes256_ctr(k, s):
+    assert len(k) == ENC_KEY_LEN
+    cipher = AES.new(k, AES.MODE_CTR, counter=Counter.new(128, initial_value=0))
+    return cipher.encrypt(s)
+
+# Byte-oriented helper.  We use this for decoding keystreams and messages.
+
+class ByteSeq:
+    def __init__(self, data):
+        self.data = data
+
+    def take(self, n):
+        assert n <= len(self.data)
+        result = self.data[:n]
+        self.data = self.data[n:]
+        return result
+
+    def exhausted(self):
+        return len(self.data) == 0
+
+    def remaining(self):
+        return len(self.data)
+
+# Low-level functions
+
+MAC_KEY_LEN = 32
+MAC_LEN = DIGEST_LEN
+
+hash_func = sha3_256
+
+def encapsulate(s):
+    """encapsulate `s` with a length prefix.
+
+       We use this whenever we need to avoid message ambiguities in
+       cryptographic inputs.
+    """
+    assert len(s) <= 0xffffffff
+    header = b"\0\0\0\0" + struct.pack("!L", len(s))
+    assert len(header) == 8
+    return header + s
+
+def h(s, tweak):
+    return hash_func(encapsulate(tweak) + s)
+
+def mac(s, key, tweak):
+    return hash_func(encapsulate(tweak) + encapsulate(key) + s)
+
+def kdf(s, tweak):
+    data = shake_256(encapsulate(tweak) + s)
+    return ByteSeq(data)
+
+def enc(s, k):
+    return aes256_ctr(k, s)
+
+# Tweaked wrappers
+
+PROTOID = b"ntor3-curve25519-sha3_256-1"
+T_KDF_PHASE1 = PROTOID + b":kdf_phase1"
+T_MAC_PHASE1 = PROTOID + b":msg_mac"
+T_KDF_FINAL = PROTOID + b":kdf_final"
+T_KEY_SEED = PROTOID + b":key_seed"
+T_VERIFY = PROTOID + b":verify"
+T_AUTH = PROTOID + b":auth_final"
+
+def kdf_phase1(s):
+    return kdf(s, T_KDF_PHASE1)
+
+def kdf_final(s):
+    return kdf(s, T_KDF_FINAL)
+
+def mac_phase1(s, key):
+    return mac(s, key, T_MAC_PHASE1)
+
+def h_key_seed(s):
+    return h(s, T_KEY_SEED)
+
+def h_verify(s):
+    return h(s, T_VERIFY)
+
+def h_auth(s):
+    return h(s, T_AUTH)
+
+# Handshake.
+
+def client_phase1(msg, verification, B, ID):
+    assert len(B) == PUB_KEY_LEN
+    assert len(ID) == IDENTITY_LEN
+
+    (x,X) = keygen()
+    p(["x", "X"], locals())
+    p(["msg", "verification"], locals())
+    Bx = curve25519(B, x)
+    secret_input_phase1 = Bx + ID + X + B + PROTOID + encapsulate(verification)
+
+    phase1_keys = kdf_phase1(secret_input_phase1)
+    enc_key = phase1_keys.take(ENC_KEY_LEN)
+    mac_key = phase1_keys.take(MAC_KEY_LEN)
+    p(["enc_key", "mac_key"], locals())
+
+    msg_0 = ID + B + X + enc(msg, enc_key)
+    mac = mac_phase1(msg_0, mac_key)
+    p(["mac"], locals())
+
+    client_handshake = msg_0 + mac
+    state = dict(x=x, X=X, B=B, ID=ID, Bx=Bx, mac=mac, verification=verification)
+
+    p(["client_handshake"], locals())
+
+    return (client_handshake, state)
+
+# server.
+
+class Reject(Exception):
+    pass
+
+def server_part1(cmsg, verification, b, B, ID):
+    assert len(B) == PUB_KEY_LEN
+    assert len(ID) == IDENTITY_LEN
+    assert len(b) == SEC_KEY_LEN
+
+    if len(cmsg) < (IDENTITY_LEN + PUB_KEY_LEN * 2 + MAC_LEN):
+        raise Reject()
+
+    mac_covered_portion = cmsg[0:-MAC_LEN]
+    cmsg = ByteSeq(cmsg)
+    cmsg_id = cmsg.take(IDENTITY_LEN)
+    cmsg_B = cmsg.take(PUB_KEY_LEN)
+    cmsg_X = cmsg.take(PUB_KEY_LEN)
+    cmsg_msg = cmsg.take(cmsg.remaining() - MAC_LEN)
+    cmsg_mac = cmsg.take(MAC_LEN)
+
+    assert cmsg.exhausted()
+
+    # XXXX for real purposes, you would use constant-time checks here
+    if cmsg_id != ID or cmsg_B != B:
+        raise Reject()
+
+    Xb = curve25519(cmsg_X, b)
+    secret_input_phase1 = Xb + ID + cmsg_X + B + PROTOID + encapsulate(verification)
+
+    phase1_keys = kdf_phase1(secret_input_phase1)
+    enc_key = phase1_keys.take(ENC_KEY_LEN)
+    mac_key = phase1_keys.take(MAC_KEY_LEN)
+
+    mac_received = mac_phase1(mac_covered_portion, mac_key)
+    if mac_received != cmsg_mac:
+        raise Reject()
+
+    client_msg = enc(cmsg_msg, enc_key)
+    state = dict(
+        b=b,
+        B=B,
+        X=cmsg_X,
+        mac_received=mac_received,
+        Xb=Xb,
+        ID=ID,
+        verification=verification)
+
+    return (client_msg, state)
+
+def server_part2(state, server_msg):
+    X = state['X']
+    Xb = state['Xb']
+    B = state['B']
+    b = state['b']
+    ID = state['ID']
+    mac_received = state['mac_received']
+    verification = state['verification']
+
+    p(["server_msg"], locals())
+    
+    (y,Y) = keygen()
+    p(["y", "Y"], locals())
+    Xy = curve25519(X, y)
+
+    secret_input = Xy + Xb + ID + B + X + Y + PROTOID + encapsulate(verification)
+    key_seed = h_key_seed(secret_input)
+    verify = h_verify(secret_input)
+    p(["key_seed", "verify"], locals())
+
+    keys = kdf_final(key_seed)
+    server_enc_key = keys.take(ENC_KEY_LEN)
+    p(["server_enc_key"], locals())
+
+    smsg_msg = enc(server_msg, server_enc_key)
+
+    auth_input = verify + ID + B + Y + X + mac_received + encapsulate(smsg_msg) + PROTOID + b"Server"
+
+    auth = h_auth(auth_input)
+    server_handshake = Y + auth + smsg_msg
+    p(["auth", "server_handshake"], locals())
+
+    return (server_handshake, keys)
+
+def client_phase2(state, smsg):
+    x = state['x']
+    X = state['X']
+    B = state['B']
+    ID = state['ID']
+    Bx = state['Bx']
+    mac_sent = state['mac']
+    verification = state['verification']
+
+    if len(smsg) < PUB_KEY_LEN + DIGEST_LEN:
+        raise Reject()
+
+    smsg = ByteSeq(smsg)
+    Y = smsg.take(PUB_KEY_LEN)
+    auth_received = smsg.take(DIGEST_LEN)
+    server_msg = smsg.take(smsg.remaining())
+
+    Yx = curve25519(Y,x)
+
+    secret_input = Yx + Bx + ID + B + X + Y + PROTOID + encapsulate(verification)
+    key_seed = h_key_seed(secret_input)
+    verify = h_verify(secret_input)
+
+    auth_input = verify + ID + B + Y + X + mac_sent + encapsulate(server_msg) + PROTOID + b"Server"
+
+    auth = h_auth(auth_input)
+    if auth != auth_received:
+        raise Reject()
+
+    keys = kdf_final(key_seed)
+    enc_key = keys.take(ENC_KEY_LEN)
+
+    server_msg_decrypted = enc(server_msg, enc_key)
+
+    return (keys, server_msg_decrypted)
+
+def p(varnames, localvars):
+    for v in varnames:
+        label = v
+        val = localvars[label]
+        print('{} = "{}"'.format(label, binascii.b2a_hex(val).decode("ascii")))
+
+def test():
+    (b,B) = keygen()
+    ID = os.urandom(IDENTITY_LEN)
+
+    p(["b", "B", "ID"], locals())
+
+    print("# ============")
+    (c_handshake, c_state) = client_phase1(b"hello world", b"xyzzy", B, ID)
+
+    print("# ============")
+
+    (c_msg_got, s_state) = server_part1(c_handshake, b"xyzzy", b, B, ID)
+
+    #print(repr(c_msg_got))
+
+    (s_handshake, s_keys) = server_part2(s_state, b"Hola Mundo")
+
+    print("# ============")
+
+    (c_keys, s_msg_got) = client_phase2(c_state, s_handshake)
+
+    #print(repr(s_msg_got))
+
+    c_keys_256 = c_keys.take(256)
+    p(["c_keys_256"], locals())
+
+    assert (c_keys_256 == s_keys.take(256))
+
+
+if __name__ == '__main__':
+    test()
diff --git a/src/test/test.c b/src/test/test.c
index 9543a24376..0aa1353ec2 100644
--- a/src/test/test.c
+++ b/src/test/test.c
@@ -707,6 +707,7 @@ struct testgroup_t testgroups[] = {
   { "netinfo/", netinfo_tests },
   { "nodelist/", nodelist_tests },
   { "oom/", oom_tests },
+  { "onion-handshake/ntor-v3/", ntor_v3_tests },
   { "oos/", oos_tests },
   { "options/", options_tests },
   { "options/act/", options_act_tests },
diff --git a/src/test/test.h b/src/test/test.h
index 700aa70a4b..0a22043acc 100644
--- a/src/test/test.h
+++ b/src/test/test.h
@@ -155,6 +155,7 @@ extern struct testcase_t microdesc_tests[];
 extern struct testcase_t namemap_tests[];
 extern struct testcase_t netinfo_tests[];
 extern struct testcase_t nodelist_tests[];
+extern struct testcase_t ntor_v3_tests[];
 extern struct testcase_t oom_tests[];
 extern struct testcase_t oos_tests[];
 extern struct testcase_t options_tests[];
diff --git a/src/test/test_ntor_v3.c b/src/test/test_ntor_v3.c
new file mode 100644
index 0000000000..096ac6668f
--- /dev/null
+++ b/src/test/test_ntor_v3.c
@@ -0,0 +1,172 @@
+/* Copyright (c) 2001-2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2021, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#include "orconfig.h"
+#define ONION_NTOR_V3_PRIVATE
+#include "core/or/or.h"
+#include "test/test.h"
+#include "lib/crypt_ops/crypto_curve25519.h"
+#include "lib/crypt_ops/crypto_ed25519.h"
+#include "core/crypto/onion_ntor_v3.h"
+
+#define unhex(arry, s)                                                  \
+  { tt_int_op(sizeof(arry), OP_EQ,                                      \
+              base16_decode((char*)arry, sizeof(arry), s, strlen(s)));  \
+  }
+
+static void
+test_ntor3_testvecs(void *arg)
+{
+  (void)arg;
+  char *mem_op_hex_tmp = NULL; // temp val to make test_memeq_hex work.
+
+  ntor3_server_handshake_state_t *relay_state = NULL;
+  uint8_t *onion_skin = NULL;
+  size_t onion_skin_len;
+  ntor3_handshake_state_t *client_state = NULL;
+  uint8_t *cm = NULL, *sm = NULL;
+  size_t cm_len, sm_len;
+  di_digest256_map_t *private_keys = NULL;
+  uint8_t *server_handshake = NULL;
+  size_t server_handshake_len;
+
+  // Test vectors from python implementation, confirmed with rust
+  // implementation.
+  curve25519_keypair_t relay_keypair_b;
+  curve25519_keypair_t client_keypair_x;
+  curve25519_keypair_t relay_keypair_y;
+  ed25519_public_key_t relay_id;
+
+  unhex(relay_keypair_b.seckey.secret_key,
+        "4051daa5921cfa2a1c27b08451324919538e79e788a81b38cbed097a5dff454a");
+  unhex(relay_keypair_b.pubkey.public_key,
+        "f8307a2bc1870b00b828bb74dbb8fd88e632a6375ab3bcd1ae706aaa8b6cdd1d");
+  unhex(relay_id.pubkey,
+        "9fad2af287ef942632833d21f946c6260c33fae6172b60006e86e4a6911753a2");
+  unhex(client_keypair_x.seckey.secret_key,
+        "b825a3719147bcbe5fb1d0b0fcb9c09e51948048e2e3283d2ab7b45b5ef38b49");
+  unhex(client_keypair_x.pubkey.public_key,
+        "252fe9ae91264c91d4ecb8501f79d0387e34ad8ca0f7c995184f7d11d5da4f46");
+  unhex(relay_keypair_y.seckey.secret_key,
+        "4865a5b7689dafd978f529291c7171bc159be076b92186405d13220b80e2a053");
+  unhex(relay_keypair_y.pubkey.public_key,
+        "4bf4814326fdab45ad5184f5518bd7fae25dc59374062698201a50a22954246d");
+
+  uint8_t client_message[11];
+  uint8_t verification[5];
+  unhex(client_message, "68656c6c6f20776f726c64");
+  unhex(verification, "78797a7a79");
+
+  // ========= Client handshake 1.
+
+  onion_skin_ntor3_create_nokeygen(
+                    &client_keypair_x,
+                    &relay_id,
+                    &relay_keypair_b.pubkey,
+                    verification,
+                    sizeof(verification),
+                    client_message,
+                    sizeof(client_message),
+                    &client_state,
+                    &onion_skin,
+                    &onion_skin_len);
+
+  const char expect_client_handshake[] = "9fad2af287ef942632833d21f946c6260c"
+    "33fae6172b60006e86e4a6911753a2f8307a2bc1870b00b828bb74dbb8fd88e632a6375"
+    "ab3bcd1ae706aaa8b6cdd1d252fe9ae91264c91d4ecb8501f79d0387e34ad8ca0f7c995"
+    "184f7d11d5da4f463bebd9151fd3b47c180abc9e044d53565f04d82bbb3bebed3d06cea"
+    "65db8be9c72b68cd461942088502f67";
+
+  tt_int_op(onion_skin_len, OP_EQ, strlen(expect_client_handshake)/2);
+  test_memeq_hex(onion_skin, expect_client_handshake);
+
+  // ========= Relay handshake.
+
+  dimap_add_entry(&private_keys,
+                  relay_keypair_b.pubkey.public_key,
+                  &relay_keypair_b);
+
+  int r = onion_skin_ntor3_server_handshake_part1(
+                    private_keys,
+                    &client_keypair_x,
+                    &relay_id,
+                    onion_skin,
+                    onion_skin_len,
+                    verification,
+                    sizeof(verification),
+                    &cm,
+                    &cm_len,
+                    &relay_state);
+  tt_int_op(r, OP_EQ, 0);
+  tt_int_op(cm_len, OP_EQ, sizeof(client_message));
+  tt_mem_op(cm, OP_EQ, client_message, cm_len);
+
+  uint8_t server_message[10];
+  unhex(server_message, "486f6c61204d756e646f");
+
+  uint8_t server_keys[256];
+  onion_skin_ntor3_server_handshake_part2_nokeygen(
+                    &relay_keypair_y,
+                    relay_state,
+                    verification,
+                    sizeof(verification),
+                    server_message,
+                    sizeof(server_message),
+                    &server_handshake,
+                    &server_handshake_len,
+                    server_keys,
+                    sizeof(server_keys));
+
+  const char expect_server_handshake[] = "4bf4814326fdab45ad5184f5518bd7fae25"
+    "dc59374062698201a50a22954246d2fc5f8773ca824542bc6cf6f57c7c29bbf4e5476461"
+    "ab130c5b18ab0a91276651202c3e1e87c0d32054c";
+  tt_int_op(server_handshake_len, OP_EQ, strlen(expect_server_handshake)/2);
+  test_memeq_hex(server_handshake, expect_server_handshake);
+
+  uint8_t expect_keys[256];
+  unhex(expect_keys, "9c19b631fd94ed86a817e01f6c80b0743a43f5faebd39cfaa8b00f"
+        "a8bcc65c3bfeaa403d91acbd68a821bf6ee8504602b094a254392a07737d5662768"
+        "c7a9fb1b2814bb34780eaee6e867c773e28c212ead563e98a1cd5d5b4576f5ee61c"
+        "59bde025ff2851bb19b721421694f263818e3531e43a9e4e3e2c661e2ad547d8984"
+        "caa28ebecd3e4525452299be26b9185a20a90ce1eac20a91f2832d731b54502b097"
+        "49b5a2a2949292f8cfcbeffb790c7790ed935a9d251e7e336148ea83b063a5618fc"
+        "ff674a44581585fd22077ca0e52c59a24347a38d1a1ceebddbf238541f226b8f88d"
+        "0fb9c07a1bcd2ea764bbbb5dacdaf5312a14c0b9e4f06309b0333b4a");
+  tt_mem_op(server_keys, OP_EQ, expect_keys, 256);
+
+  // ===== Client handshake 2
+
+  uint8_t client_keys[256];
+  r = onion_ntor3_client_handshake(
+                  client_state,
+                  server_handshake,
+                  server_handshake_len,
+                  verification,
+                  sizeof(verification),
+                  client_keys,
+                  sizeof(client_keys),
+                  &sm,
+                  &sm_len);
+
+  tt_int_op(r, OP_EQ, 0);
+  tt_int_op(sm_len, OP_EQ, sizeof(server_message));
+  tt_mem_op(sm, OP_EQ, server_message, sizeof(server_message));
+  tt_mem_op(client_keys, OP_EQ, server_keys, 256);
+
+ done:
+  tor_free(onion_skin);
+  tor_free(server_handshake);
+  tor_free(mem_op_hex_tmp);
+  ntor3_handshake_state_free(client_state);
+  ntor3_server_handshake_state_free(relay_state);
+  tor_free(cm);
+  tor_free(sm);
+  dimap_free(private_keys, NULL);
+}
+
+struct testcase_t ntor_v3_tests[] = {
+  { "testvecs", test_ntor3_testvecs, 0, NULL, NULL, },
+  END_OF_TESTCASES,
+};