Move literally everything out of src/or

This commit won't build yet -- it just puts everything in a slightly
more logical place.

The reasoning here is that "src/core" will hold the stuff that every (or
nearly every) tor instance will need in order to do onion routing.
Other features (including some necessary ones) will live in
"src/feature".  The "src/app" directory will hold the stuff needed
to have Tor be an application you can actually run.

This commit DOES NOT refactor the former contents of src/or into a
logical set of acyclic libraries, or change any code at all.  That
will have to come in the future.

We will continue to move things around and split them in the future,
but I hope this lays a reasonable groundwork for doing so.

12 files changed, 3403 insertions, 0 deletions

diff --git a/src/core/crypto/hs_ntor.c b/src/core/crypto/hs_ntor.c
new file mode 100644
index 0000000000..b5007545db
--- /dev/null
+++ b/src/core/crypto/hs_ntor.c
@@ -0,0 +1,620 @@
+/* Copyright (c) 2017-2018, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/** \file hs_ntor.c
+ *  \brief Implements the ntor variant used in Tor hidden services.
+ *
+ *  \details
+ *  This module handles the variant of the ntor handshake that is documented in
+ *  section [NTOR-WITH-EXTRA-DATA] of rend-spec-ng.txt .
+ *
+ *  The functions in this file provide an API that should be used when sending
+ *  or receiving INTRODUCE1/RENDEZVOUS1 cells to generate the various key
+ *  material required to create and handle those cells.
+ *
+ *  In the case of INTRODUCE1 it provides encryption and MAC keys to
+ *  encode/decode the encrypted blob (see hs_ntor_intro_cell_keys_t). The
+ *  relevant pub functions are hs_ntor_{client,service}_get_introduce1_keys().
+ *
+ *  In the case of RENDEZVOUS1 it calculates the MAC required to authenticate
+ *  the cell, and also provides the key seed that is used to derive the crypto
+ *  material for rendezvous encryption (see hs_ntor_rend_cell_keys_t). The
+ *  relevant pub functions are hs_ntor_{client,service}_get_rendezvous1_keys().
+ *  It also provides a function (hs_ntor_circuit_key_expansion()) that does the
+ *  rendezvous key expansion to setup end-to-end rend circuit keys.
+ */
+
+#include "or/or.h"
+#include "lib/crypt_ops/crypto_util.h"
+#include "lib/crypt_ops/crypto_curve25519.h"
+#include "lib/crypt_ops/crypto_ed25519.h"
+#include "or/hs_ntor.h"
+
+/* String constants used by the ntor HS protocol */
+#define PROTOID "tor-hs-ntor-curve25519-sha3-256-1"
+#define PROTOID_LEN (sizeof(PROTOID) - 1)
+#define SERVER_STR "Server"
+#define SERVER_STR_LEN (sizeof(SERVER_STR) - 1)
+
+/* Protocol-specific tweaks to our crypto inputs */
+#define T_HSENC PROTOID ":hs_key_extract"
+#define T_HSENC_LEN (sizeof(T_HSENC) - 1)
+#define T_HSVERIFY PROTOID ":hs_verify"
+#define T_HSMAC PROTOID ":hs_mac"
+#define M_HSEXPAND PROTOID ":hs_key_expand"
+#define M_HSEXPAND_LEN (sizeof(M_HSEXPAND) - 1)
+
+/************************* Helper functions: *******************************/
+
+/** Helper 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. Stolen from onion_ntor.c */
+#define APPEND(ptr, inp, len)                   \
+  STMT_BEGIN {                                  \
+    memcpy(ptr, (inp), (len));                  \
+    ptr += len;                                 \
+  } STMT_END
+
+/* Length of EXP(X,y) | EXP(X,b) | AUTH_KEY | B | X | Y | PROTOID */
+#define REND_SECRET_HS_INPUT_LEN (CURVE25519_OUTPUT_LEN * 2 + \
+  ED25519_PUBKEY_LEN + CURVE25519_PUBKEY_LEN * 3 + PROTOID_LEN)
+/* Length of auth_input = verify | AUTH_KEY | B | Y | X | PROTOID | "Server" */
+#define REND_AUTH_INPUT_LEN (DIGEST256_LEN + ED25519_PUBKEY_LEN + \
+  CURVE25519_PUBKEY_LEN * 3 + PROTOID_LEN + SERVER_STR_LEN)
+
+/** Helper function: Compute the last part of the HS ntor handshake which
+ *  derives key material necessary to create and handle RENDEZVOUS1
+ *  cells. Function used by both client and service. The actual calculations is
+ *  as follows:
+ *
+ *    NTOR_KEY_SEED = MAC(rend_secret_hs_input, t_hsenc)
+ *    verify = MAC(rend_secret_hs_input, t_hsverify)
+ *    auth_input = verify | AUTH_KEY | B | Y | X | PROTOID | "Server"
+ *    auth_input_mac = MAC(auth_input, t_hsmac)
+ *
+ *  where in the above, AUTH_KEY is <b>intro_auth_pubkey</b>, B is
+ *  <b>intro_enc_pubkey</b>, Y is <b>service_ephemeral_rend_pubkey</b>, and X
+ *  is <b>client_ephemeral_enc_pubkey</b>. The provided
+ *  <b>rend_secret_hs_input</b> is of size REND_SECRET_HS_INPUT_LEN.
+ *
+ *  The final results of NTOR_KEY_SEED and auth_input_mac are placed in
+ *  <b>hs_ntor_rend_cell_keys_out</b>. Return 0 if everything went fine. */
+static int
+get_rendezvous1_key_material(const uint8_t *rend_secret_hs_input,
+                  const ed25519_public_key_t *intro_auth_pubkey,
+                  const curve25519_public_key_t *intro_enc_pubkey,
+                  const curve25519_public_key_t *service_ephemeral_rend_pubkey,
+                  const curve25519_public_key_t *client_ephemeral_enc_pubkey,
+                  hs_ntor_rend_cell_keys_t *hs_ntor_rend_cell_keys_out)
+{
+  int bad = 0;
+  uint8_t ntor_key_seed[DIGEST256_LEN];
+  uint8_t ntor_verify[DIGEST256_LEN];
+  uint8_t rend_auth_input[REND_AUTH_INPUT_LEN];
+  uint8_t rend_cell_auth[DIGEST256_LEN];
+  uint8_t *ptr;
+
+  /* Let's build NTOR_KEY_SEED */
+  crypto_mac_sha3_256(ntor_key_seed, sizeof(ntor_key_seed),
+                      rend_secret_hs_input, REND_SECRET_HS_INPUT_LEN,
+                      (const uint8_t *)T_HSENC, strlen(T_HSENC));
+  bad |= safe_mem_is_zero(ntor_key_seed, DIGEST256_LEN);
+
+  /* Let's build ntor_verify */
+  crypto_mac_sha3_256(ntor_verify, sizeof(ntor_verify),
+                      rend_secret_hs_input, REND_SECRET_HS_INPUT_LEN,
+                      (const uint8_t *)T_HSVERIFY, strlen(T_HSVERIFY));
+  bad |= safe_mem_is_zero(ntor_verify, DIGEST256_LEN);
+
+  /* Let's build auth_input: */
+  ptr = rend_auth_input;
+  /* Append ntor_verify */
+  APPEND(ptr, ntor_verify, sizeof(ntor_verify));
+  /* Append AUTH_KEY */
+  APPEND(ptr, intro_auth_pubkey->pubkey, ED25519_PUBKEY_LEN);
+  /* Append B */
+  APPEND(ptr, intro_enc_pubkey->public_key, CURVE25519_PUBKEY_LEN);
+  /* Append Y */
+  APPEND(ptr,
+         service_ephemeral_rend_pubkey->public_key, CURVE25519_PUBKEY_LEN);
+  /* Append X */
+  APPEND(ptr,
+         client_ephemeral_enc_pubkey->public_key, CURVE25519_PUBKEY_LEN);
+  /* Append PROTOID */
+  APPEND(ptr, PROTOID, strlen(PROTOID));
+  /* Append "Server" */
+  APPEND(ptr, SERVER_STR, strlen(SERVER_STR));
+  tor_assert(ptr == rend_auth_input + sizeof(rend_auth_input));
+
+  /* Let's build auth_input_mac that goes in RENDEZVOUS1 cell */
+  crypto_mac_sha3_256(rend_cell_auth, sizeof(rend_cell_auth),
+                      rend_auth_input, sizeof(rend_auth_input),
+                      (const uint8_t *)T_HSMAC, strlen(T_HSMAC));
+  bad |= safe_mem_is_zero(ntor_verify, DIGEST256_LEN);
+
+  { /* Get the computed RENDEZVOUS1 material! */
+    memcpy(&hs_ntor_rend_cell_keys_out->rend_cell_auth_mac,
+           rend_cell_auth, DIGEST256_LEN);
+    memcpy(&hs_ntor_rend_cell_keys_out->ntor_key_seed,
+           ntor_key_seed, DIGEST256_LEN);
+  }
+
+  memwipe(rend_cell_auth, 0, sizeof(rend_cell_auth));
+  memwipe(rend_auth_input, 0, sizeof(rend_auth_input));
+  memwipe(ntor_key_seed, 0, sizeof(ntor_key_seed));
+
+  return bad;
+}
+
+/** Length of secret_input = EXP(B,x) | AUTH_KEY | X | B | PROTOID */
+#define INTRO_SECRET_HS_INPUT_LEN (CURVE25519_OUTPUT_LEN +ED25519_PUBKEY_LEN +\
+  CURVE25519_PUBKEY_LEN + CURVE25519_PUBKEY_LEN + PROTOID_LEN)
+/* Length of info = m_hsexpand | subcredential */
+#define INFO_BLOB_LEN (M_HSEXPAND_LEN + DIGEST256_LEN)
+/* Length of KDF input = intro_secret_hs_input | t_hsenc | info */
+#define KDF_INPUT_LEN (INTRO_SECRET_HS_INPUT_LEN + T_HSENC_LEN + INFO_BLOB_LEN)
+
+/** Helper function: Compute the part of the HS ntor handshake that generates
+ *  key material for creating and handling INTRODUCE1 cells. Function used
+ *  by both client and service. Specifically, calculate the following:
+ *
+ *     info = m_hsexpand | subcredential
+ *     hs_keys = KDF(intro_secret_hs_input | t_hsenc | info, S_KEY_LEN+MAC_LEN)
+ *     ENC_KEY = hs_keys[0:S_KEY_LEN]
+ *     MAC_KEY = hs_keys[S_KEY_LEN:S_KEY_LEN+MAC_KEY_LEN]
+ *
+ *  where intro_secret_hs_input is <b>secret_input</b> (of size
+ *  INTRO_SECRET_HS_INPUT_LEN), and <b>subcredential</b> is of size
+ *  DIGEST256_LEN.
+ *
+ * If everything went well, fill <b>hs_ntor_intro_cell_keys_out</b> with the
+ * necessary key material, and return 0. */
+static void
+get_introduce1_key_material(const uint8_t *secret_input,
+                        const uint8_t *subcredential,
+                        hs_ntor_intro_cell_keys_t *hs_ntor_intro_cell_keys_out)
+{
+  uint8_t keystream[CIPHER256_KEY_LEN + DIGEST256_LEN];
+  uint8_t info_blob[INFO_BLOB_LEN];
+  uint8_t kdf_input[KDF_INPUT_LEN];
+  crypto_xof_t *xof;
+  uint8_t *ptr;
+
+  /* Let's build info */
+  ptr = info_blob;
+  APPEND(ptr, M_HSEXPAND, strlen(M_HSEXPAND));
+  APPEND(ptr, subcredential, DIGEST256_LEN);
+  tor_assert(ptr == info_blob + sizeof(info_blob));
+
+  /* Let's build the input to the KDF */
+  ptr = kdf_input;
+  APPEND(ptr, secret_input, INTRO_SECRET_HS_INPUT_LEN);
+  APPEND(ptr, T_HSENC, strlen(T_HSENC));
+  APPEND(ptr, info_blob, sizeof(info_blob));
+  tor_assert(ptr == kdf_input + sizeof(kdf_input));
+
+  /* Now we need to run kdf_input over SHAKE-256 */
+  xof = crypto_xof_new();
+  crypto_xof_add_bytes(xof, kdf_input, sizeof(kdf_input));
+  crypto_xof_squeeze_bytes(xof, keystream, sizeof(keystream)) ;
+  crypto_xof_free(xof);
+
+  { /* Get the keys */
+    memcpy(&hs_ntor_intro_cell_keys_out->enc_key, keystream,CIPHER256_KEY_LEN);
+    memcpy(&hs_ntor_intro_cell_keys_out->mac_key,
+           keystream+CIPHER256_KEY_LEN, DIGEST256_LEN);
+  }
+
+  memwipe(keystream,  0, sizeof(keystream));
+  memwipe(kdf_input,  0, sizeof(kdf_input));
+}
+
+/** Helper function: Calculate the 'intro_secret_hs_input' element used by the
+ * HS ntor handshake and place it in <b>secret_input_out</b>. This function is
+ * used by both client and service code.
+ *
+ * For the client-side it looks like this:
+ *
+ *         intro_secret_hs_input = EXP(B,x) | AUTH_KEY | X | B | PROTOID
+ *
+ * whereas for the service-side it looks like this:
+ *
+ *         intro_secret_hs_input = EXP(X,b) | AUTH_KEY | X | B | PROTOID
+ *
+ * In this function, <b>dh_result</b> carries the EXP() result (and has size
+ * CURVE25519_OUTPUT_LEN) <b>intro_auth_pubkey</b> is AUTH_KEY,
+ * <b>client_ephemeral_enc_pubkey</b> is X, and <b>intro_enc_pubkey</b> is B.
+ */
+static void
+get_intro_secret_hs_input(const uint8_t *dh_result,
+                    const ed25519_public_key_t *intro_auth_pubkey,
+                    const curve25519_public_key_t *client_ephemeral_enc_pubkey,
+                    const curve25519_public_key_t *intro_enc_pubkey,
+                    uint8_t *secret_input_out)
+{
+  uint8_t *ptr;
+
+  /* Append EXP() */
+  ptr = secret_input_out;
+  APPEND(ptr, dh_result, CURVE25519_OUTPUT_LEN);
+  /* Append AUTH_KEY */
+  APPEND(ptr, intro_auth_pubkey->pubkey, ED25519_PUBKEY_LEN);
+  /* Append X */
+  APPEND(ptr, client_ephemeral_enc_pubkey->public_key, CURVE25519_PUBKEY_LEN);
+  /* Append B */
+  APPEND(ptr, intro_enc_pubkey->public_key, CURVE25519_PUBKEY_LEN);
+  /* Append PROTOID */
+  APPEND(ptr, PROTOID, strlen(PROTOID));
+  tor_assert(ptr == secret_input_out + INTRO_SECRET_HS_INPUT_LEN);
+}
+
+/** Calculate the 'rend_secret_hs_input' element used by the HS ntor handshake
+ *  and place it in <b>rend_secret_hs_input_out</b>. This function is used by
+ *  both client and service code.
+ *
+ * The computation on the client side is:
+ *  rend_secret_hs_input = EXP(X,y) | EXP(X,b) | AUTH_KEY | B | X | Y | PROTOID
+ * whereas on the service side it is:
+ *  rend_secret_hs_input = EXP(Y,x) | EXP(B,x) | AUTH_KEY | B | X | Y | PROTOID
+ *
+ * where:
+ * <b>dh_result1</b> and <b>dh_result2</b> carry the two EXP() results (of size
+ * CURVE25519_OUTPUT_LEN)
+ * <b>intro_auth_pubkey</b> is AUTH_KEY,
+ * <b>intro_enc_pubkey</b> is B,
+ * <b>client_ephemeral_enc_pubkey</b> is X, and
+ * <b>service_ephemeral_rend_pubkey</b> is Y.
+ */
+static void
+get_rend_secret_hs_input(const uint8_t *dh_result1, const uint8_t *dh_result2,
+                  const ed25519_public_key_t *intro_auth_pubkey,
+                  const curve25519_public_key_t *intro_enc_pubkey,
+                  const curve25519_public_key_t *client_ephemeral_enc_pubkey,
+                  const curve25519_public_key_t *service_ephemeral_rend_pubkey,
+                  uint8_t *rend_secret_hs_input_out)
+{
+  uint8_t *ptr;
+
+  ptr = rend_secret_hs_input_out;
+  /* Append the first EXP() */
+  APPEND(ptr, dh_result1, CURVE25519_OUTPUT_LEN);
+  /* Append the other EXP() */
+  APPEND(ptr, dh_result2, CURVE25519_OUTPUT_LEN);
+  /* Append AUTH_KEY */
+  APPEND(ptr, intro_auth_pubkey->pubkey, ED25519_PUBKEY_LEN);
+  /* Append B */
+  APPEND(ptr, intro_enc_pubkey->public_key, CURVE25519_PUBKEY_LEN);
+  /* Append X */
+  APPEND(ptr,
+         client_ephemeral_enc_pubkey->public_key, CURVE25519_PUBKEY_LEN);
+  /* Append Y */
+  APPEND(ptr,
+         service_ephemeral_rend_pubkey->public_key, CURVE25519_PUBKEY_LEN);
+  /* Append PROTOID */
+  APPEND(ptr, PROTOID, strlen(PROTOID));
+  tor_assert(ptr == rend_secret_hs_input_out + REND_SECRET_HS_INPUT_LEN);
+}
+
+/************************* Public functions: *******************************/
+
+/* Public function: Do the appropriate ntor calculations and derive the keys
+ * needed to encrypt and authenticate INTRODUCE1 cells. Return 0 and place the
+ * final key material in <b>hs_ntor_intro_cell_keys_out</b> if everything went
+ * well, otherwise return -1;
+ *
+ * The relevant calculations are as follows:
+ *
+ *     intro_secret_hs_input = EXP(B,x) | AUTH_KEY | X | B | PROTOID
+ *     info = m_hsexpand | subcredential
+ *     hs_keys = KDF(intro_secret_hs_input | t_hsenc | info, S_KEY_LEN+MAC_LEN)
+ *     ENC_KEY = hs_keys[0:S_KEY_LEN]
+ *     MAC_KEY = hs_keys[S_KEY_LEN:S_KEY_LEN+MAC_KEY_LEN]
+ *
+ * where:
+ * <b>intro_auth_pubkey</b> is AUTH_KEY (found in HS descriptor),
+ * <b>intro_enc_pubkey</b> is B (also found in HS descriptor),
+ * <b>client_ephemeral_enc_keypair</b> is freshly generated keypair (x,X)
+ * <b>subcredential</b> is the hidden service subcredential (of size
+ * DIGEST256_LEN). */
+int
+hs_ntor_client_get_introduce1_keys(
+                      const ed25519_public_key_t *intro_auth_pubkey,
+                      const curve25519_public_key_t *intro_enc_pubkey,
+                      const curve25519_keypair_t *client_ephemeral_enc_keypair,
+                      const uint8_t *subcredential,
+                      hs_ntor_intro_cell_keys_t *hs_ntor_intro_cell_keys_out)
+{
+  int bad = 0;
+  uint8_t secret_input[INTRO_SECRET_HS_INPUT_LEN];
+  uint8_t dh_result[CURVE25519_OUTPUT_LEN];
+
+  tor_assert(intro_auth_pubkey);
+  tor_assert(intro_enc_pubkey);
+  tor_assert(client_ephemeral_enc_keypair);
+  tor_assert(subcredential);
+  tor_assert(hs_ntor_intro_cell_keys_out);
+
+  /* Calculate EXP(B,x) */
+  curve25519_handshake(dh_result,
+                       &client_ephemeral_enc_keypair->seckey,
+                       intro_enc_pubkey);
+  bad |= safe_mem_is_zero(dh_result, CURVE25519_OUTPUT_LEN);
+
+  /* Get intro_secret_hs_input */
+  get_intro_secret_hs_input(dh_result, intro_auth_pubkey,
+                            &client_ephemeral_enc_keypair->pubkey,
+                            intro_enc_pubkey, secret_input);
+  bad |= safe_mem_is_zero(secret_input, CURVE25519_OUTPUT_LEN);
+
+  /* Get ENC_KEY and MAC_KEY! */
+  get_introduce1_key_material(secret_input, subcredential,
+                              hs_ntor_intro_cell_keys_out);
+
+  /* Cleanup */
+  memwipe(secret_input,  0, sizeof(secret_input));
+  if (bad) {
+    memwipe(hs_ntor_intro_cell_keys_out, 0, sizeof(hs_ntor_intro_cell_keys_t));
+  }
+
+  return bad ? -1 : 0;
+}
+
+/* Public function: Do the appropriate ntor calculations and derive the keys
+ * needed to verify RENDEZVOUS1 cells and encrypt further rendezvous
+ * traffic. Return 0 and place the final key material in
+ * <b>hs_ntor_rend_cell_keys_out</b> if everything went well, else return -1.
+ *
+ * The relevant calculations are as follows:
+ *
+ *  rend_secret_hs_input = EXP(Y,x) | EXP(B,x) | AUTH_KEY | B | X | Y | PROTOID
+ *  NTOR_KEY_SEED = MAC(rend_secret_hs_input, t_hsenc)
+ *  verify = MAC(rend_secret_hs_input, t_hsverify)
+ *  auth_input = verify | AUTH_KEY | B | Y | X | PROTOID | "Server"
+ *  auth_input_mac = MAC(auth_input, t_hsmac)
+ *
+ * where:
+ * <b>intro_auth_pubkey</b> is AUTH_KEY (found in HS descriptor),
+ * <b>client_ephemeral_enc_keypair</b> is freshly generated keypair (x,X)
+ * <b>intro_enc_pubkey</b> is B (also found in HS descriptor),
+ * <b>service_ephemeral_rend_pubkey</b> is Y (SERVER_PK in RENDEZVOUS1 cell) */
+int
+hs_ntor_client_get_rendezvous1_keys(
+                  const ed25519_public_key_t *intro_auth_pubkey,
+                  const curve25519_keypair_t *client_ephemeral_enc_keypair,
+                  const curve25519_public_key_t *intro_enc_pubkey,
+                  const curve25519_public_key_t *service_ephemeral_rend_pubkey,
+                  hs_ntor_rend_cell_keys_t *hs_ntor_rend_cell_keys_out)
+{
+  int bad = 0;
+  uint8_t rend_secret_hs_input[REND_SECRET_HS_INPUT_LEN];
+  uint8_t dh_result1[CURVE25519_OUTPUT_LEN];
+  uint8_t dh_result2[CURVE25519_OUTPUT_LEN];
+
+  tor_assert(intro_auth_pubkey);
+  tor_assert(client_ephemeral_enc_keypair);
+  tor_assert(intro_enc_pubkey);
+  tor_assert(service_ephemeral_rend_pubkey);
+  tor_assert(hs_ntor_rend_cell_keys_out);
+
+  /* Compute EXP(Y, x) */
+  curve25519_handshake(dh_result1,
+                       &client_ephemeral_enc_keypair->seckey,
+                       service_ephemeral_rend_pubkey);
+  bad |= safe_mem_is_zero(dh_result1, CURVE25519_OUTPUT_LEN);
+
+  /* Compute EXP(B, x) */
+  curve25519_handshake(dh_result2,
+                       &client_ephemeral_enc_keypair->seckey,
+                       intro_enc_pubkey);
+  bad |= safe_mem_is_zero(dh_result2, CURVE25519_OUTPUT_LEN);
+
+  /* Get rend_secret_hs_input */
+  get_rend_secret_hs_input(dh_result1, dh_result2,
+                           intro_auth_pubkey, intro_enc_pubkey,
+                           &client_ephemeral_enc_keypair->pubkey,
+                           service_ephemeral_rend_pubkey,
+                           rend_secret_hs_input);
+
+  /* Get NTOR_KEY_SEED and the auth_input MAC */
+  bad |= get_rendezvous1_key_material(rend_secret_hs_input,
+                                      intro_auth_pubkey,
+                                      intro_enc_pubkey,
+                                      service_ephemeral_rend_pubkey,
+                                      &client_ephemeral_enc_keypair->pubkey,
+                                      hs_ntor_rend_cell_keys_out);
+
+  memwipe(rend_secret_hs_input, 0, sizeof(rend_secret_hs_input));
+  if (bad) {
+    memwipe(hs_ntor_rend_cell_keys_out, 0, sizeof(hs_ntor_rend_cell_keys_t));
+  }
+
+  return bad ? -1 : 0;
+}
+
+/* Public function: Do the appropriate ntor calculations and derive the keys
+ * needed to decrypt and verify INTRODUCE1 cells. Return 0 and place the final
+ * key material in <b>hs_ntor_intro_cell_keys_out</b> if everything went well,
+ * otherwise return -1;
+ *
+ * The relevant calculations are as follows:
+ *
+ *    intro_secret_hs_input = EXP(X,b) | AUTH_KEY | X | B | PROTOID
+ *    info = m_hsexpand | subcredential
+ *    hs_keys = KDF(intro_secret_hs_input | t_hsenc | info, S_KEY_LEN+MAC_LEN)
+ *    HS_DEC_KEY = hs_keys[0:S_KEY_LEN]
+ *    HS_MAC_KEY = hs_keys[S_KEY_LEN:S_KEY_LEN+MAC_KEY_LEN]
+ *
+ * where:
+ * <b>intro_auth_pubkey</b> is AUTH_KEY (introduction point auth key),
+ * <b>intro_enc_keypair</b> is (b,B) (introduction point encryption keypair),
+ * <b>client_ephemeral_enc_pubkey</b> is X (CLIENT_PK in INTRODUCE2 cell),
+ * <b>subcredential</b> is the HS subcredential (of size DIGEST256_LEN) */
+int
+hs_ntor_service_get_introduce1_keys(
+                    const ed25519_public_key_t *intro_auth_pubkey,
+                    const curve25519_keypair_t *intro_enc_keypair,
+                    const curve25519_public_key_t *client_ephemeral_enc_pubkey,
+                    const uint8_t *subcredential,
+                    hs_ntor_intro_cell_keys_t *hs_ntor_intro_cell_keys_out)
+{
+  int bad = 0;
+  uint8_t secret_input[INTRO_SECRET_HS_INPUT_LEN];
+  uint8_t dh_result[CURVE25519_OUTPUT_LEN];
+
+  tor_assert(intro_auth_pubkey);
+  tor_assert(intro_enc_keypair);
+  tor_assert(client_ephemeral_enc_pubkey);
+  tor_assert(subcredential);
+  tor_assert(hs_ntor_intro_cell_keys_out);
+
+  /* Compute EXP(X, b) */
+  curve25519_handshake(dh_result,
+                       &intro_enc_keypair->seckey,
+                       client_ephemeral_enc_pubkey);
+  bad |= safe_mem_is_zero(dh_result, CURVE25519_OUTPUT_LEN);
+
+  /* Get intro_secret_hs_input */
+  get_intro_secret_hs_input(dh_result, intro_auth_pubkey,
+                            client_ephemeral_enc_pubkey,
+                            &intro_enc_keypair->pubkey,
+                            secret_input);
+  bad |= safe_mem_is_zero(secret_input, CURVE25519_OUTPUT_LEN);
+
+  /* Get ENC_KEY and MAC_KEY! */
+  get_introduce1_key_material(secret_input, subcredential,
+                              hs_ntor_intro_cell_keys_out);
+
+  memwipe(secret_input,  0, sizeof(secret_input));
+  if (bad) {
+    memwipe(hs_ntor_intro_cell_keys_out, 0, sizeof(hs_ntor_intro_cell_keys_t));
+  }
+
+  return bad ? -1 : 0;
+}
+
+/* Public function: Do the appropriate ntor calculations and derive the keys
+ * needed to create and authenticate RENDEZVOUS1 cells. Return 0 and place the
+ * final key material in <b>hs_ntor_rend_cell_keys_out</b> if all went fine,
+ * return -1 if error happened.
+ *
+ * The relevant calculations are as follows:
+ *
+ *  rend_secret_hs_input = EXP(X,y) | EXP(X,b) | AUTH_KEY | B | X | Y | PROTOID
+ *  NTOR_KEY_SEED = MAC(rend_secret_hs_input, t_hsenc)
+ *  verify = MAC(rend_secret_hs_input, t_hsverify)
+ *  auth_input = verify | AUTH_KEY | B | Y | X | PROTOID | "Server"
+ *  auth_input_mac = MAC(auth_input, t_hsmac)
+ *
+ * where:
+ * <b>intro_auth_pubkey</b> is AUTH_KEY (intro point auth key),
+ * <b>intro_enc_keypair</b> is (b,B) (intro point enc keypair)
+ * <b>service_ephemeral_rend_keypair</b> is a fresh (y,Y) keypair
+ * <b>client_ephemeral_enc_pubkey</b> is X (CLIENT_PK in INTRODUCE2 cell) */
+int
+hs_ntor_service_get_rendezvous1_keys(
+                    const ed25519_public_key_t *intro_auth_pubkey,
+                    const curve25519_keypair_t *intro_enc_keypair,
+                    const curve25519_keypair_t *service_ephemeral_rend_keypair,
+                    const curve25519_public_key_t *client_ephemeral_enc_pubkey,
+                    hs_ntor_rend_cell_keys_t *hs_ntor_rend_cell_keys_out)
+{
+  int bad = 0;
+  uint8_t rend_secret_hs_input[REND_SECRET_HS_INPUT_LEN];
+  uint8_t dh_result1[CURVE25519_OUTPUT_LEN];
+  uint8_t dh_result2[CURVE25519_OUTPUT_LEN];
+
+  tor_assert(intro_auth_pubkey);
+  tor_assert(intro_enc_keypair);
+  tor_assert(service_ephemeral_rend_keypair);
+  tor_assert(client_ephemeral_enc_pubkey);
+  tor_assert(hs_ntor_rend_cell_keys_out);
+
+  /* Compute EXP(X, y) */
+  curve25519_handshake(dh_result1,
+                       &service_ephemeral_rend_keypair->seckey,
+                       client_ephemeral_enc_pubkey);
+  bad |= safe_mem_is_zero(dh_result1, CURVE25519_OUTPUT_LEN);
+
+  /* Compute EXP(X, b) */
+  curve25519_handshake(dh_result2,
+                       &intro_enc_keypair->seckey,
+                       client_ephemeral_enc_pubkey);
+  bad |= safe_mem_is_zero(dh_result2, CURVE25519_OUTPUT_LEN);
+
+  /* Get rend_secret_hs_input */
+  get_rend_secret_hs_input(dh_result1, dh_result2,
+                           intro_auth_pubkey,
+                           &intro_enc_keypair->pubkey,
+                           client_ephemeral_enc_pubkey,
+                           &service_ephemeral_rend_keypair->pubkey,
+                           rend_secret_hs_input);
+
+  /* Get NTOR_KEY_SEED and AUTH_INPUT_MAC! */
+  bad |= get_rendezvous1_key_material(rend_secret_hs_input,
+                                      intro_auth_pubkey,
+                                      &intro_enc_keypair->pubkey,
+                                      &service_ephemeral_rend_keypair->pubkey,
+                                      client_ephemeral_enc_pubkey,
+                                      hs_ntor_rend_cell_keys_out);
+
+  memwipe(rend_secret_hs_input, 0, sizeof(rend_secret_hs_input));
+  if (bad) {
+    memwipe(hs_ntor_rend_cell_keys_out, 0, sizeof(hs_ntor_rend_cell_keys_t));
+  }
+
+  return bad ? -1 : 0;
+}
+
+/** Given a received RENDEZVOUS2 MAC in <b>mac</b> (of length DIGEST256_LEN),
+ *  and the RENDEZVOUS1 key material in <b>hs_ntor_rend_cell_keys</b>, return 1
+ *  if the MAC is good, otherwise return 0. */
+int
+hs_ntor_client_rendezvous2_mac_is_good(
+                        const hs_ntor_rend_cell_keys_t *hs_ntor_rend_cell_keys,
+                        const uint8_t *rcvd_mac)
+{
+  tor_assert(rcvd_mac);
+  tor_assert(hs_ntor_rend_cell_keys);
+
+  return tor_memeq(hs_ntor_rend_cell_keys->rend_cell_auth_mac,
+                   rcvd_mac, DIGEST256_LEN);
+}
+
+/* Input length to KDF for key expansion */
+#define NTOR_KEY_EXPANSION_KDF_INPUT_LEN (DIGEST256_LEN + M_HSEXPAND_LEN)
+
+/** Given the rendezvous key seed in <b>ntor_key_seed</b> (of size
+ *  DIGEST256_LEN), do the circuit key expansion as specified by section
+ *  '4.2.1. Key expansion' and place the keys in <b>keys_out</b> (which must be
+ *  of size HS_NTOR_KEY_EXPANSION_KDF_OUT_LEN).
+ *
+ * Return 0 if things went well, else return -1. */
+int
+hs_ntor_circuit_key_expansion(const uint8_t *ntor_key_seed, size_t seed_len,
+                              uint8_t *keys_out, size_t keys_out_len)
+{
+  uint8_t *ptr;
+  uint8_t kdf_input[NTOR_KEY_EXPANSION_KDF_INPUT_LEN];
+  crypto_xof_t *xof;
+
+  /* Sanity checks on lengths to make sure we are good */
+  if (BUG(seed_len != DIGEST256_LEN)) {
+    return -1;
+  }
+  if (BUG(keys_out_len != HS_NTOR_KEY_EXPANSION_KDF_OUT_LEN)) {
+    return -1;
+  }
+
+  /* Let's build the input to the KDF */
+  ptr = kdf_input;
+  APPEND(ptr, ntor_key_seed, DIGEST256_LEN);
+  APPEND(ptr, M_HSEXPAND, strlen(M_HSEXPAND));
+  tor_assert(ptr == kdf_input + sizeof(kdf_input));
+
+  /* Generate the keys */
+  xof = crypto_xof_new();
+  crypto_xof_add_bytes(xof, kdf_input, sizeof(kdf_input));
+  crypto_xof_squeeze_bytes(xof, keys_out, HS_NTOR_KEY_EXPANSION_KDF_OUT_LEN);
+  crypto_xof_free(xof);
+
+  return 0;
+}
diff --git a/src/core/crypto/hs_ntor.h b/src/core/crypto/hs_ntor.h
new file mode 100644
index 0000000000..67a9573436
--- /dev/null
+++ b/src/core/crypto/hs_ntor.h
@@ -0,0 +1,69 @@
+/* Copyright (c) 2017-2018, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#ifndef TOR_HS_NTOR_H
+#define TOR_HS_NTOR_H
+
+#include "or/or.h"
+struct ed25519_public_key_t;
+struct curve25519_public_key_t;
+struct curve25519_keypair_t;
+
+/* Output length of KDF for key expansion */
+#define HS_NTOR_KEY_EXPANSION_KDF_OUT_LEN \
+  (DIGEST256_LEN*2 + CIPHER256_KEY_LEN*2)
+
+/* Key material needed to encode/decode INTRODUCE1 cells */
+typedef struct {
+  /* Key used for encryption of encrypted INTRODUCE1 blob */
+  uint8_t enc_key[CIPHER256_KEY_LEN];
+  /* MAC key used to protect encrypted INTRODUCE1 blob */
+  uint8_t mac_key[DIGEST256_LEN];
+} hs_ntor_intro_cell_keys_t;
+
+/* Key material needed to encode/decode RENDEZVOUS1 cells */
+typedef struct {
+  /* This is the MAC of the HANDSHAKE_INFO field */
+  uint8_t rend_cell_auth_mac[DIGEST256_LEN];
+  /* This is the key seed used to derive further rendezvous crypto keys as
+   * detailed in section 4.2.1 of rend-spec-ng.txt. */
+  uint8_t ntor_key_seed[DIGEST256_LEN];
+} hs_ntor_rend_cell_keys_t;
+
+int hs_ntor_client_get_introduce1_keys(
+              const struct ed25519_public_key_t *intro_auth_pubkey,
+              const struct curve25519_public_key_t *intro_enc_pubkey,
+              const struct curve25519_keypair_t *client_ephemeral_enc_keypair,
+              const uint8_t *subcredential,
+              hs_ntor_intro_cell_keys_t *hs_ntor_intro_cell_keys_out);
+
+int hs_ntor_client_get_rendezvous1_keys(
+          const struct ed25519_public_key_t *intro_auth_pubkey,
+          const struct curve25519_keypair_t *client_ephemeral_enc_keypair,
+          const struct curve25519_public_key_t *intro_enc_pubkey,
+          const struct curve25519_public_key_t *service_ephemeral_rend_pubkey,
+          hs_ntor_rend_cell_keys_t *hs_ntor_rend_cell_keys_out);
+
+int hs_ntor_service_get_introduce1_keys(
+            const struct ed25519_public_key_t *intro_auth_pubkey,
+            const struct curve25519_keypair_t *intro_enc_keypair,
+            const struct curve25519_public_key_t *client_ephemeral_enc_pubkey,
+            const uint8_t *subcredential,
+            hs_ntor_intro_cell_keys_t *hs_ntor_intro_cell_keys_out);
+
+int hs_ntor_service_get_rendezvous1_keys(
+            const struct ed25519_public_key_t *intro_auth_pubkey,
+            const struct curve25519_keypair_t *intro_enc_keypair,
+            const struct curve25519_keypair_t *service_ephemeral_rend_keypair,
+            const struct curve25519_public_key_t *client_ephemeral_enc_pubkey,
+            hs_ntor_rend_cell_keys_t *hs_ntor_rend_cell_keys_out);
+
+int hs_ntor_circuit_key_expansion(const uint8_t *ntor_key_seed,
+                                  size_t seed_len,
+                                  uint8_t *keys_out, size_t keys_out_len);
+
+int hs_ntor_client_rendezvous2_mac_is_good(
+                        const hs_ntor_rend_cell_keys_t *hs_ntor_rend_cell_keys,
+                        const uint8_t *rcvd_mac);
+
+#endif /* !defined(TOR_HS_NTOR_H) */
diff --git a/src/core/crypto/onion.c b/src/core/crypto/onion.c
new file mode 100644
index 0000000000..80d8e1a8b1
--- /dev/null
+++ b/src/core/crypto/onion.c
@@ -0,0 +1,1346 @@
+/* Copyright (c) 2001 Matej Pfajfar.
+ * Copyright (c) 2001-2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2018, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file onion.c
+ * \brief Functions to queue create cells, wrap the various onionskin types,
+ * and parse and create the CREATE cell and its allies.
+ *
+ * This module has a few functions, all related to the CREATE/CREATED
+ * handshake that we use on links in order to create a circuit, and the
+ * related EXTEND/EXTENDED handshake that we use over circuits in order to
+ * extend them an additional hop.
+ *
+ * In this module, we provide a set of abstractions to create a uniform
+ * interface over the three circuit extension handshakes that Tor has used
+ * over the years (TAP, CREATE_FAST, and ntor).  These handshakes are
+ * implemented in onion_tap.c, onion_fast.c, and onion_ntor.c respectively.
+ *
+ * All[*] of these handshakes follow a similar pattern: a client, knowing
+ * some key from the relay it wants to extend through, generates the
+ * first part of a handshake. A relay receives that handshake, and sends
+ * a reply.  Once the client handles the reply, it knows that it is
+ * talking to the right relay, and it shares some freshly negotiated key
+ * material with that relay.
+ *
+ * We sometimes call the client's part of the handshake an "onionskin".
+ * We do this because historically, Onion Routing used a multi-layer
+ * structure called an "onion" to construct circuits. Each layer of the
+ * onion contained key material chosen by the client, the identity of
+ * the next relay in the circuit, and a smaller onion, encrypted with
+ * the key of the next relay.  When we changed Tor to use a telescoping
+ * circuit extension design, it corresponded to sending each layer of the
+ * onion separately -- as a series of onionskins.
+ *
+ * Clients invoke these functions when creating or extending a circuit,
+ * from circuitbuild.c.
+ *
+ * Relays invoke these functions when they receive a CREATE or EXTEND
+ * cell in command.c or relay.c, in order to queue the pending request.
+ * They also invoke them from cpuworker.c, which handles dispatching
+ * onionskin requests to different worker threads.
+ *
+ * <br>
+ *
+ * This module also handles:
+ *  <ul>
+ *  <li> Queueing incoming onionskins on the relay side before passing
+ *      them to worker threads.
+ *   <li>Expiring onionskins on the relay side if they have waited for
+ *     too long.
+ *   <li>Packaging private keys on the server side in order to pass
+ *     them to worker threads.
+ *   <li>Encoding and decoding CREATE, CREATED, CREATE2, and CREATED2 cells.
+ *   <li>Encoding and decodign EXTEND, EXTENDED, EXTEND2, and EXTENDED2
+ *    relay cells.
+ * </ul>
+ *
+ * [*] The CREATE_FAST handshake is weaker than described here; see
+ * onion_fast.c for more information.
+ **/
+
+#include "or/or.h"
+#include "or/circuitbuild.h"
+#include "or/circuitlist.h"
+#include "or/config.h"
+#include "or/cpuworker.h"
+#include "lib/crypt_ops/crypto_util.h"
+#include "lib/crypt_ops/crypto_dh.h"
+#include "or/networkstatus.h"
+#include "or/onion.h"
+#include "or/onion_fast.h"
+#include "or/onion_ntor.h"
+#include "or/onion_tap.h"
+#include "or/relay.h"
+#include "or/rephist.h"
+#include "or/router.h"
+
+#include "or/cell_st.h"
+#include "or/extend_info_st.h"
+#include "or/or_circuit_st.h"
+
+// trunnel
+#include "trunnel/ed25519_cert.h"
+
+/** Type for a linked list of circuits that are waiting for a free CPU worker
+ * to process a waiting onion handshake. */
+typedef struct onion_queue_t {
+  TOR_TAILQ_ENTRY(onion_queue_t) next;
+  or_circuit_t *circ;
+  uint16_t handshake_type;
+  create_cell_t *onionskin;
+  time_t when_added;
+} onion_queue_t;
+
+/** 5 seconds on the onion queue til we just send back a destroy */
+#define ONIONQUEUE_WAIT_CUTOFF 5
+
+/** Array of queues of circuits waiting for CPU workers. An element is NULL
+ * if that queue is empty.*/
+static TOR_TAILQ_HEAD(onion_queue_head_t, onion_queue_t)
+              ol_list[MAX_ONION_HANDSHAKE_TYPE+1] =
+{ TOR_TAILQ_HEAD_INITIALIZER(ol_list[0]), /* tap */
+  TOR_TAILQ_HEAD_INITIALIZER(ol_list[1]), /* fast */
+  TOR_TAILQ_HEAD_INITIALIZER(ol_list[2]), /* ntor */
+};
+
+/** Number of entries of each type currently in each element of ol_list[]. */
+static int ol_entries[MAX_ONION_HANDSHAKE_TYPE+1];
+
+static int num_ntors_per_tap(void);
+static void onion_queue_entry_remove(onion_queue_t *victim);
+
+/* XXXX Check lengths vs MAX_ONIONSKIN_{CHALLENGE,REPLY}_LEN.
+ *
+ * (By which I think I meant, "make sure that no
+ * X_ONIONSKIN_CHALLENGE/REPLY_LEN is greater than
+ * MAX_ONIONSKIN_CHALLENGE/REPLY_LEN."  Also, make sure that we can pass
+ * over-large values via EXTEND2/EXTENDED2, for future-compatibility.*/
+
+/** Return true iff we have room to queue another onionskin of type
+ * <b>type</b>. */
+static int
+have_room_for_onionskin(uint16_t type)
+{
+  const or_options_t *options = get_options();
+  int num_cpus;
+  uint64_t tap_usec, ntor_usec;
+  uint64_t ntor_during_tap_usec, tap_during_ntor_usec;
+
+  /* If we've got fewer than 50 entries, we always have room for one more. */
+  if (ol_entries[type] < 50)
+    return 1;
+  num_cpus = get_num_cpus(options);
+  /* Compute how many microseconds we'd expect to need to clear all
+   * onionskins in various combinations of the queues. */
+
+  /* How long would it take to process all the TAP cells in the queue? */
+  tap_usec  = estimated_usec_for_onionskins(
+                                    ol_entries[ONION_HANDSHAKE_TYPE_TAP],
+                                    ONION_HANDSHAKE_TYPE_TAP) / num_cpus;
+
+  /* How long would it take to process all the NTor cells in the queue? */
+  ntor_usec = estimated_usec_for_onionskins(
+                                    ol_entries[ONION_HANDSHAKE_TYPE_NTOR],
+                                    ONION_HANDSHAKE_TYPE_NTOR) / num_cpus;
+
+  /* How long would it take to process the tap cells that we expect to
+   * process while draining the ntor queue? */
+  tap_during_ntor_usec  = estimated_usec_for_onionskins(
+    MIN(ol_entries[ONION_HANDSHAKE_TYPE_TAP],
+        ol_entries[ONION_HANDSHAKE_TYPE_NTOR] / num_ntors_per_tap()),
+                                    ONION_HANDSHAKE_TYPE_TAP) / num_cpus;
+
+  /* How long would it take to process the ntor cells that we expect to
+   * process while draining the tap queue? */
+  ntor_during_tap_usec  = estimated_usec_for_onionskins(
+    MIN(ol_entries[ONION_HANDSHAKE_TYPE_NTOR],
+        ol_entries[ONION_HANDSHAKE_TYPE_TAP] * num_ntors_per_tap()),
+                                    ONION_HANDSHAKE_TYPE_NTOR) / num_cpus;
+
+  /* See whether that exceeds MaxOnionQueueDelay. If so, we can't queue
+   * this. */
+  if (type == ONION_HANDSHAKE_TYPE_NTOR &&
+      (ntor_usec + tap_during_ntor_usec) / 1000 >
+       (uint64_t)options->MaxOnionQueueDelay)
+    return 0;
+
+  if (type == ONION_HANDSHAKE_TYPE_TAP &&
+      (tap_usec + ntor_during_tap_usec) / 1000 >
+       (uint64_t)options->MaxOnionQueueDelay)
+    return 0;
+
+  /* If we support the ntor handshake, then don't let TAP handshakes use
+   * more than 2/3 of the space on the queue. */
+  if (type == ONION_HANDSHAKE_TYPE_TAP &&
+      tap_usec / 1000 > (uint64_t)options->MaxOnionQueueDelay * 2 / 3)
+    return 0;
+
+  return 1;
+}
+
+/** Add <b>circ</b> to the end of ol_list and return 0, except
+ * if ol_list is too long, in which case do nothing and return -1.
+ */
+int
+onion_pending_add(or_circuit_t *circ, create_cell_t *onionskin)
+{
+  onion_queue_t *tmp;
+  time_t now = time(NULL);
+
+  if (onionskin->handshake_type > MAX_ONION_HANDSHAKE_TYPE) {
+    /* LCOV_EXCL_START
+     * We should have rejected this far before this point */
+    log_warn(LD_BUG, "Handshake %d out of range! Dropping.",
+             onionskin->handshake_type);
+    return -1;
+    /* LCOV_EXCL_STOP */
+  }
+
+  tmp = tor_malloc_zero(sizeof(onion_queue_t));
+  tmp->circ = circ;
+  tmp->handshake_type = onionskin->handshake_type;
+  tmp->onionskin = onionskin;
+  tmp->when_added = now;
+
+  if (!have_room_for_onionskin(onionskin->handshake_type)) {
+#define WARN_TOO_MANY_CIRC_CREATIONS_INTERVAL (60)
+    static ratelim_t last_warned =
+      RATELIM_INIT(WARN_TOO_MANY_CIRC_CREATIONS_INTERVAL);
+    char *m;
+    if (onionskin->handshake_type == ONION_HANDSHAKE_TYPE_NTOR &&
+        (m = rate_limit_log(&last_warned, approx_time()))) {
+      log_warn(LD_GENERAL,
+               "Your computer is too slow to handle this many circuit "
+               "creation requests! Please consider using the "
+               "MaxAdvertisedBandwidth config option or choosing a more "
+               "restricted exit policy.%s",m);
+      tor_free(m);
+    }
+    tor_free(tmp);
+    return -1;
+  }
+
+  ++ol_entries[onionskin->handshake_type];
+  log_info(LD_OR, "New create (%s). Queues now ntor=%d and tap=%d.",
+    onionskin->handshake_type == ONION_HANDSHAKE_TYPE_NTOR ? "ntor" : "tap",
+    ol_entries[ONION_HANDSHAKE_TYPE_NTOR],
+    ol_entries[ONION_HANDSHAKE_TYPE_TAP]);
+
+  circ->onionqueue_entry = tmp;
+  TOR_TAILQ_INSERT_TAIL(&ol_list[onionskin->handshake_type], tmp, next);
+
+  /* cull elderly requests. */
+  while (1) {
+    onion_queue_t *head = TOR_TAILQ_FIRST(&ol_list[onionskin->handshake_type]);
+    if (now - head->when_added < (time_t)ONIONQUEUE_WAIT_CUTOFF)
+      break;
+
+    circ = head->circ;
+    circ->onionqueue_entry = NULL;
+    onion_queue_entry_remove(head);
+    log_info(LD_CIRC,
+             "Circuit create request is too old; canceling due to overload.");
+    if (! TO_CIRCUIT(circ)->marked_for_close) {
+      circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_RESOURCELIMIT);
+    }
+  }
+  return 0;
+}
+
+/** Return a fairness parameter, to prefer processing NTOR style
+ * handshakes but still slowly drain the TAP queue so we don't starve
+ * it entirely. */
+static int
+num_ntors_per_tap(void)
+{
+#define DEFAULT_NUM_NTORS_PER_TAP 10
+#define MIN_NUM_NTORS_PER_TAP 1
+#define MAX_NUM_NTORS_PER_TAP 100000
+
+  return networkstatus_get_param(NULL, "NumNTorsPerTAP",
+                                 DEFAULT_NUM_NTORS_PER_TAP,
+                                 MIN_NUM_NTORS_PER_TAP,
+                                 MAX_NUM_NTORS_PER_TAP);
+}
+
+/** Choose which onion queue we'll pull from next. If one is empty choose
+ * the other; if they both have elements, load balance across them but
+ * favoring NTOR. */
+static uint16_t
+decide_next_handshake_type(void)
+{
+  /* The number of times we've chosen ntor lately when both were available. */
+  static int recently_chosen_ntors = 0;
+
+  if (!ol_entries[ONION_HANDSHAKE_TYPE_NTOR])
+    return ONION_HANDSHAKE_TYPE_TAP; /* no ntors? try tap */
+
+  if (!ol_entries[ONION_HANDSHAKE_TYPE_TAP]) {
+
+    /* Nick wants us to prioritize new tap requests when there aren't
+     * any in the queue and we've processed k ntor cells since the last
+     * tap cell. This strategy is maybe a good idea, since it starves tap
+     * less in the case where tap is rare, or maybe a poor idea, since it
+     * makes the new tap cell unfairly jump in front of ntor cells that
+     * got here first. In any case this edge case will only become relevant
+     * once tap is rare. We should reevaluate whether we like this decision
+     * once tap gets more rare. */
+    if (ol_entries[ONION_HANDSHAKE_TYPE_NTOR] &&
+        recently_chosen_ntors <= num_ntors_per_tap())
+      ++recently_chosen_ntors;
+
+    return ONION_HANDSHAKE_TYPE_NTOR; /* no taps? try ntor */
+  }
+
+  /* They both have something queued. Pick ntor if we haven't done that
+   * too much lately. */
+  if (++recently_chosen_ntors <= num_ntors_per_tap()) {
+    return ONION_HANDSHAKE_TYPE_NTOR;
+  }
+
+  /* Else, it's time to let tap have its turn. */
+  recently_chosen_ntors = 0;
+  return ONION_HANDSHAKE_TYPE_TAP;
+}
+
+/** Remove the highest priority item from ol_list[] and return it, or
+ * return NULL if the lists are empty.
+ */
+or_circuit_t *
+onion_next_task(create_cell_t **onionskin_out)
+{
+  or_circuit_t *circ;
+  uint16_t handshake_to_choose = decide_next_handshake_type();
+  onion_queue_t *head = TOR_TAILQ_FIRST(&ol_list[handshake_to_choose]);
+
+  if (!head)
+    return NULL; /* no onions pending, we're done */
+
+  tor_assert(head->circ);
+  tor_assert(head->handshake_type <= MAX_ONION_HANDSHAKE_TYPE);
+//  tor_assert(head->circ->p_chan); /* make sure it's still valid */
+/* XXX I only commented out the above line to make the unit tests
+ * more manageable. That's probably not good long-term. -RD */
+  circ = head->circ;
+  if (head->onionskin)
+    --ol_entries[head->handshake_type];
+  log_info(LD_OR, "Processing create (%s). Queues now ntor=%d and tap=%d.",
+    head->handshake_type == ONION_HANDSHAKE_TYPE_NTOR ? "ntor" : "tap",
+    ol_entries[ONION_HANDSHAKE_TYPE_NTOR],
+    ol_entries[ONION_HANDSHAKE_TYPE_TAP]);
+
+  *onionskin_out = head->onionskin;
+  head->onionskin = NULL; /* prevent free. */
+  circ->onionqueue_entry = NULL;
+  onion_queue_entry_remove(head);
+  return circ;
+}
+
+/** Return the number of <b>handshake_type</b>-style create requests pending.
+ */
+int
+onion_num_pending(uint16_t handshake_type)
+{
+  return ol_entries[handshake_type];
+}
+
+/** Go through ol_list, find the onion_queue_t element which points to
+ * circ, remove and free that element. Leave circ itself alone.
+ */
+void
+onion_pending_remove(or_circuit_t *circ)
+{
+  onion_queue_t *victim;
+
+  if (!circ)
+    return;
+
+  victim = circ->onionqueue_entry;
+  if (victim)
+    onion_queue_entry_remove(victim);
+
+  cpuworker_cancel_circ_handshake(circ);
+}
+
+/** Remove a queue entry <b>victim</b> from the queue, unlinking it from
+ * its circuit and freeing it and any structures it owns.*/
+static void
+onion_queue_entry_remove(onion_queue_t *victim)
+{
+  if (victim->handshake_type > MAX_ONION_HANDSHAKE_TYPE) {
+    /* LCOV_EXCL_START
+     * We should have rejected this far before this point */
+    log_warn(LD_BUG, "Handshake %d out of range! Dropping.",
+             victim->handshake_type);
+    /* XXX leaks */
+    return;
+    /* LCOV_EXCL_STOP */
+  }
+
+  TOR_TAILQ_REMOVE(&ol_list[victim->handshake_type], victim, next);
+
+  if (victim->circ)
+    victim->circ->onionqueue_entry = NULL;
+
+  if (victim->onionskin)
+    --ol_entries[victim->handshake_type];
+
+  tor_free(victim->onionskin);
+  tor_free(victim);
+}
+
+/** Remove all circuits from the pending list.  Called from tor_free_all. */
+void
+clear_pending_onions(void)
+{
+  onion_queue_t *victim, *next;
+  int i;
+  for (i=0; i<=MAX_ONION_HANDSHAKE_TYPE; i++) {
+    for (victim = TOR_TAILQ_FIRST(&ol_list[i]); victim; victim = next) {
+      next = TOR_TAILQ_NEXT(victim,next);
+      onion_queue_entry_remove(victim);
+    }
+    tor_assert(TOR_TAILQ_EMPTY(&ol_list[i]));
+  }
+  memset(ol_entries, 0, sizeof(ol_entries));
+}
+
+/* ============================================================ */
+
+/** 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,
+ * and to avoid locking) */
+server_onion_keys_t *
+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);
+  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));
+  curve25519_keypair_generate(keys->junk_keypair, 0);
+  return keys;
+}
+
+/** Release all storage held in <b>keys</b>. */
+void
+server_onion_keys_free_(server_onion_keys_t *keys)
+{
+  if (! keys)
+    return;
+
+  crypto_pk_free(keys->onion_key);
+  crypto_pk_free(keys->last_onion_key);
+  ntor_key_map_free(keys->curve25519_key_map);
+  tor_free(keys->junk_keypair);
+  memwipe(keys, 0, sizeof(server_onion_keys_t));
+  tor_free(keys);
+}
+
+/** Release whatever storage is held in <b>state</b>, depending on its
+ * type, and clear its pointer. */
+void
+onion_handshake_state_release(onion_handshake_state_t *state)
+{
+  switch (state->tag) {
+  case ONION_HANDSHAKE_TYPE_TAP:
+    crypto_dh_free(state->u.tap);
+    state->u.tap = NULL;
+    break;
+  case ONION_HANDSHAKE_TYPE_FAST:
+    fast_handshake_state_free(state->u.fast);
+    state->u.fast = NULL;
+    break;
+  case ONION_HANDSHAKE_TYPE_NTOR:
+    ntor_handshake_state_free(state->u.ntor);
+    state->u.ntor = NULL;
+    break;
+  default:
+    /* LCOV_EXCL_START
+     * This state should not even exist. */
+    log_warn(LD_BUG, "called with unknown handshake state type %d",
+             (int)state->tag);
+    tor_fragile_assert();
+    /* LCOV_EXCL_STOP */
+  }
+}
+
+/** Perform the first step of a circuit-creation handshake of type <b>type</b>
+ * (one of ONION_HANDSHAKE_TYPE_*): generate the initial "onion skin" in
+ * <b>onion_skin_out</b>, and store any state information in <b>state_out</b>.
+ * Return -1 on failure, and the length of the onionskin on acceptance.
+ */
+int
+onion_skin_create(int type,
+                  const extend_info_t *node,
+                  onion_handshake_state_t *state_out,
+                  uint8_t *onion_skin_out)
+{
+  int r = -1;
+
+  switch (type) {
+  case ONION_HANDSHAKE_TYPE_TAP:
+    if (!node->onion_key)
+      return -1;
+
+    if (onion_skin_TAP_create(node->onion_key,
+                              &state_out->u.tap,
+                              (char*)onion_skin_out) < 0)
+      return -1;
+
+    r = TAP_ONIONSKIN_CHALLENGE_LEN;
+    break;
+  case ONION_HANDSHAKE_TYPE_FAST:
+    if (fast_onionskin_create(&state_out->u.fast, onion_skin_out) < 0)
+      return -1;
+
+    r = CREATE_FAST_LEN;
+    break;
+  case ONION_HANDSHAKE_TYPE_NTOR:
+    if (!extend_info_supports_ntor(node))
+      return -1;
+    if (onion_skin_ntor_create((const uint8_t*)node->identity_digest,
+                               &node->curve25519_onion_key,
+                               &state_out->u.ntor,
+                               onion_skin_out) < 0)
+      return -1;
+
+    r = NTOR_ONIONSKIN_LEN;
+    break;
+  default:
+    /* LCOV_EXCL_START
+     * We should never try to create an impossible handshake type. */
+    log_warn(LD_BUG, "called with unknown handshake state type %d", type);
+    tor_fragile_assert();
+    r = -1;
+    /* LCOV_EXCL_STOP */
+  }
+
+  if (r > 0)
+    state_out->tag = (uint16_t) type;
+
+  return r;
+}
+
+/* This is the maximum value for keys_out_len passed to
+ * onion_skin_server_handshake, plus 16. We can make it bigger if needed:
+ * It just defines how many bytes to stack-allocate. */
+#define MAX_KEYS_TMP_LEN 128
+
+/** Perform the second (server-side) step of a circuit-creation handshake of
+ * type <b>type</b>, responding to the client request in <b>onion_skin</b>
+ * using the keys in <b>keys</b>.  On success, write our response into
+ * <b>reply_out</b>, generate <b>keys_out_len</b> bytes worth of key material
+ * in <b>keys_out_len</b>, a hidden service nonce to <b>rend_nonce_out</b>,
+ * and return the length of the reply. On failure, return -1.
+ */
+int
+onion_skin_server_handshake(int type,
+                      const uint8_t *onion_skin, size_t onionskin_len,
+                      const server_onion_keys_t *keys,
+                      uint8_t *reply_out,
+                      uint8_t *keys_out, size_t keys_out_len,
+                      uint8_t *rend_nonce_out)
+{
+  int r = -1;
+
+  switch (type) {
+  case ONION_HANDSHAKE_TYPE_TAP:
+    if (onionskin_len != TAP_ONIONSKIN_CHALLENGE_LEN)
+      return -1;
+    if (onion_skin_TAP_server_handshake((const char*)onion_skin,
+                                        keys->onion_key, keys->last_onion_key,
+                                        (char*)reply_out,
+                                        (char*)keys_out, keys_out_len)<0)
+      return -1;
+    r = TAP_ONIONSKIN_REPLY_LEN;
+    memcpy(rend_nonce_out, reply_out+DH1024_KEY_LEN, DIGEST_LEN);
+    break;
+  case ONION_HANDSHAKE_TYPE_FAST:
+    if (onionskin_len != CREATE_FAST_LEN)
+      return -1;
+    if (fast_server_handshake(onion_skin, reply_out, keys_out, keys_out_len)<0)
+      return -1;
+    r = CREATED_FAST_LEN;
+    memcpy(rend_nonce_out, reply_out+DIGEST_LEN, DIGEST_LEN);
+    break;
+  case ONION_HANDSHAKE_TYPE_NTOR:
+    if (onionskin_len < NTOR_ONIONSKIN_LEN)
+      return -1;
+    {
+      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];
+
+      if (onion_skin_ntor_server_handshake(
+                                   onion_skin, keys->curve25519_key_map,
+                                   keys->junk_keypair,
+                                   keys->my_identity,
+                                   reply_out, keys_tmp, keys_tmp_len)<0) {
+        /* no need to memwipe here, since the output will never be used */
+        return -1;
+      }
+
+      memcpy(keys_out, keys_tmp, keys_out_len);
+      memcpy(rend_nonce_out, keys_tmp+keys_out_len, DIGEST_LEN);
+      memwipe(keys_tmp, 0, sizeof(keys_tmp));
+      r = NTOR_REPLY_LEN;
+    }
+    break;
+  default:
+    /* LCOV_EXCL_START
+     * We should have rejected this far before this point */
+    log_warn(LD_BUG, "called with unknown handshake state type %d", type);
+    tor_fragile_assert();
+    return -1;
+    /* LCOV_EXCL_STOP */
+  }
+
+  return r;
+}
+
+/** Perform the final (client-side) step of a circuit-creation handshake of
+ * type <b>type</b>, using our state in <b>handshake_state</b> and the
+ * server's response in <b>reply</b>. On success, generate <b>keys_out_len</b>
+ * bytes worth of key material in <b>keys_out_len</b>, set
+ * <b>rend_authenticator_out</b> to the "KH" field that can be used to
+ * establish introduction points at this hop, and return 0. On failure,
+ * return -1, and set *msg_out to an error message if this is worth
+ * complaining to the user about. */
+int
+onion_skin_client_handshake(int type,
+                      const onion_handshake_state_t *handshake_state,
+                      const uint8_t *reply, size_t reply_len,
+                      uint8_t *keys_out, size_t keys_out_len,
+                      uint8_t *rend_authenticator_out,
+                      const char **msg_out)
+{
+  if (handshake_state->tag != type)
+    return -1;
+
+  switch (type) {
+  case ONION_HANDSHAKE_TYPE_TAP:
+    if (reply_len != TAP_ONIONSKIN_REPLY_LEN) {
+      if (msg_out)
+        *msg_out = "TAP reply was not of the correct length.";
+      return -1;
+    }
+    if (onion_skin_TAP_client_handshake(handshake_state->u.tap,
+                                        (const char*)reply,
+                                        (char *)keys_out, keys_out_len,
+                                        msg_out) < 0)
+      return -1;
+
+    memcpy(rend_authenticator_out, reply+DH1024_KEY_LEN, DIGEST_LEN);
+
+    return 0;
+  case ONION_HANDSHAKE_TYPE_FAST:
+    if (reply_len != CREATED_FAST_LEN) {
+      if (msg_out)
+        *msg_out = "TAP reply was not of the correct length.";
+      return -1;
+    }
+    if (fast_client_handshake(handshake_state->u.fast, reply,
+                              keys_out, keys_out_len, msg_out) < 0)
+      return -1;
+
+    memcpy(rend_authenticator_out, reply+DIGEST_LEN, DIGEST_LEN);
+    return 0;
+  case ONION_HANDSHAKE_TYPE_NTOR:
+    if (reply_len < NTOR_REPLY_LEN) {
+      if (msg_out)
+        *msg_out = "ntor reply was not of the correct length.";
+      return -1;
+    }
+    {
+      size_t keys_tmp_len = keys_out_len + DIGEST_LEN;
+      uint8_t *keys_tmp = tor_malloc(keys_tmp_len);
+      if (onion_skin_ntor_client_handshake(handshake_state->u.ntor,
+                                        reply,
+                                        keys_tmp, keys_tmp_len, msg_out) < 0) {
+        tor_free(keys_tmp);
+        return -1;
+      }
+      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();
+    return -1;
+  }
+}
+
+/** Helper: return 0 if <b>cell</b> appears valid, -1 otherwise. If
+ * <b>unknown_ok</b> is true, allow cells with handshake types we don't
+ * recognize. */
+static int
+check_create_cell(const create_cell_t *cell, int unknown_ok)
+{
+  switch (cell->cell_type) {
+  case CELL_CREATE:
+    if (cell->handshake_type != ONION_HANDSHAKE_TYPE_TAP &&
+        cell->handshake_type != ONION_HANDSHAKE_TYPE_NTOR)
+      return -1;
+    break;
+  case CELL_CREATE_FAST:
+    if (cell->handshake_type != ONION_HANDSHAKE_TYPE_FAST)
+      return -1;
+    break;
+  case CELL_CREATE2:
+    break;
+  default:
+    return -1;
+  }
+
+  switch (cell->handshake_type) {
+  case ONION_HANDSHAKE_TYPE_TAP:
+    if (cell->handshake_len != TAP_ONIONSKIN_CHALLENGE_LEN)
+      return -1;
+    break;
+  case ONION_HANDSHAKE_TYPE_FAST:
+    if (cell->handshake_len != CREATE_FAST_LEN)
+      return -1;
+    break;
+  case ONION_HANDSHAKE_TYPE_NTOR:
+    if (cell->handshake_len != NTOR_ONIONSKIN_LEN)
+      return -1;
+    break;
+  default:
+    if (! unknown_ok)
+      return -1;
+  }
+
+  return 0;
+}
+
+/** Write the various parameters into the create cell. Separate from
+ * create_cell_parse() to make unit testing easier.
+ */
+void
+create_cell_init(create_cell_t *cell_out, uint8_t cell_type,
+                 uint16_t handshake_type, uint16_t handshake_len,
+                 const uint8_t *onionskin)
+{
+  memset(cell_out, 0, sizeof(*cell_out));
+
+  cell_out->cell_type = cell_type;
+  cell_out->handshake_type = handshake_type;
+  cell_out->handshake_len = handshake_len;
+  memcpy(cell_out->onionskin, onionskin, handshake_len);
+}
+
+/** Helper: parse the CREATE2 payload at <b>p</b>, which could be up to
+ * <b>p_len</b> bytes long, and use it to fill the fields of
+ * <b>cell_out</b>. Return 0 on success and -1 on failure.
+ *
+ * Note that part of the body of an EXTEND2 cell is a CREATE2 payload, so
+ * this function is also used for parsing those.
+ */
+static int
+parse_create2_payload(create_cell_t *cell_out, const uint8_t *p, size_t p_len)
+{
+  uint16_t handshake_type, handshake_len;
+
+  if (p_len < 4)
+    return -1;
+
+  handshake_type = ntohs(get_uint16(p));
+  handshake_len = ntohs(get_uint16(p+2));
+
+  if (handshake_len > CELL_PAYLOAD_SIZE - 4 || handshake_len > p_len - 4)
+    return -1;
+  if (handshake_type == ONION_HANDSHAKE_TYPE_FAST)
+    return -1;
+
+  create_cell_init(cell_out, CELL_CREATE2, handshake_type, handshake_len,
+                   p+4);
+  return 0;
+}
+
+/** Magic string which, in a CREATE or EXTEND cell, indicates that a seeming
+ * TAP payload is really an ntor payload.  We'd do away with this if every
+ * relay supported EXTEND2, but we want to be able to extend from A to B with
+ * ntor even when A doesn't understand EXTEND2 and so can't generate a
+ * CREATE2 cell.
+ **/
+#define NTOR_CREATE_MAGIC "ntorNTORntorNTOR"
+
+/** Parse a CREATE, CREATE_FAST, or CREATE2 cell from <b>cell_in</b> into
+ * <b>cell_out</b>. Return 0 on success, -1 on failure. (We reject some
+ * syntactically valid CREATE2 cells that we can't generate or react to.) */
+int
+create_cell_parse(create_cell_t *cell_out, const cell_t *cell_in)
+{
+  switch (cell_in->command) {
+  case CELL_CREATE:
+    if (tor_memeq(cell_in->payload, NTOR_CREATE_MAGIC, 16)) {
+      create_cell_init(cell_out, CELL_CREATE, ONION_HANDSHAKE_TYPE_NTOR,
+                       NTOR_ONIONSKIN_LEN, cell_in->payload+16);
+    } else {
+      create_cell_init(cell_out, CELL_CREATE, ONION_HANDSHAKE_TYPE_TAP,
+                       TAP_ONIONSKIN_CHALLENGE_LEN, cell_in->payload);
+    }
+    break;
+  case CELL_CREATE_FAST:
+    create_cell_init(cell_out, CELL_CREATE_FAST, ONION_HANDSHAKE_TYPE_FAST,
+                     CREATE_FAST_LEN, cell_in->payload);
+    break;
+  case CELL_CREATE2:
+    if (parse_create2_payload(cell_out, cell_in->payload,
+                              CELL_PAYLOAD_SIZE) < 0)
+      return -1;
+    break;
+  default:
+    return -1;
+  }
+
+  return check_create_cell(cell_out, 0);
+}
+
+/** Helper: return 0 if <b>cell</b> appears valid, -1 otherwise. */
+static int
+check_created_cell(const created_cell_t *cell)
+{
+  switch (cell->cell_type) {
+  case CELL_CREATED:
+    if (cell->handshake_len != TAP_ONIONSKIN_REPLY_LEN &&
+        cell->handshake_len != NTOR_REPLY_LEN)
+      return -1;
+    break;
+  case CELL_CREATED_FAST:
+    if (cell->handshake_len != CREATED_FAST_LEN)
+      return -1;
+    break;
+  case CELL_CREATED2:
+    if (cell->handshake_len > RELAY_PAYLOAD_SIZE-2)
+      return -1;
+    break;
+  }
+
+  return 0;
+}
+
+/** Parse a CREATED, CREATED_FAST, or CREATED2 cell from <b>cell_in</b> into
+ * <b>cell_out</b>. Return 0 on success, -1 on failure. */
+int
+created_cell_parse(created_cell_t *cell_out, const cell_t *cell_in)
+{
+  memset(cell_out, 0, sizeof(*cell_out));
+
+  switch (cell_in->command) {
+  case CELL_CREATED:
+    cell_out->cell_type = CELL_CREATED;
+    cell_out->handshake_len = TAP_ONIONSKIN_REPLY_LEN;
+    memcpy(cell_out->reply, cell_in->payload, TAP_ONIONSKIN_REPLY_LEN);
+    break;
+  case CELL_CREATED_FAST:
+    cell_out->cell_type = CELL_CREATED_FAST;
+    cell_out->handshake_len = CREATED_FAST_LEN;
+    memcpy(cell_out->reply, cell_in->payload, CREATED_FAST_LEN);
+    break;
+  case CELL_CREATED2:
+    {
+      const uint8_t *p = cell_in->payload;
+      cell_out->cell_type = CELL_CREATED2;
+      cell_out->handshake_len = ntohs(get_uint16(p));
+      if (cell_out->handshake_len > CELL_PAYLOAD_SIZE - 2)
+        return -1;
+      memcpy(cell_out->reply, p+2, cell_out->handshake_len);
+      break;
+    }
+  }
+
+  return check_created_cell(cell_out);
+}
+
+/** Helper: return 0 if <b>cell</b> appears valid, -1 otherwise. */
+static int
+check_extend_cell(const extend_cell_t *cell)
+{
+  if (tor_digest_is_zero((const char*)cell->node_id))
+    return -1;
+  /* We don't currently allow EXTEND2 cells without an IPv4 address */
+  if (tor_addr_family(&cell->orport_ipv4.addr) == AF_UNSPEC)
+    return -1;
+  if (cell->create_cell.cell_type == CELL_CREATE) {
+    if (cell->cell_type != RELAY_COMMAND_EXTEND)
+      return -1;
+  } else if (cell->create_cell.cell_type == CELL_CREATE2) {
+    if (cell->cell_type != RELAY_COMMAND_EXTEND2 &&
+        cell->cell_type != RELAY_COMMAND_EXTEND)
+      return -1;
+  } else {
+    /* In particular, no CREATE_FAST cells are allowed */
+    return -1;
+  }
+  if (cell->create_cell.handshake_type == ONION_HANDSHAKE_TYPE_FAST)
+    return -1;
+
+  return check_create_cell(&cell->create_cell, 1);
+}
+
+static int
+extend_cell_from_extend1_cell_body(extend_cell_t *cell_out,
+                                   const extend1_cell_body_t *cell)
+{
+  tor_assert(cell_out);
+  tor_assert(cell);
+  memset(cell_out, 0, sizeof(*cell_out));
+  tor_addr_make_unspec(&cell_out->orport_ipv4.addr);
+  tor_addr_make_unspec(&cell_out->orport_ipv6.addr);
+
+  cell_out->cell_type = RELAY_COMMAND_EXTEND;
+  tor_addr_from_ipv4h(&cell_out->orport_ipv4.addr, cell->ipv4addr);
+  cell_out->orport_ipv4.port = cell->port;
+  if (tor_memeq(cell->onionskin, NTOR_CREATE_MAGIC, 16)) {
+    cell_out->create_cell.cell_type = CELL_CREATE2;
+    cell_out->create_cell.handshake_type = ONION_HANDSHAKE_TYPE_NTOR;
+    cell_out->create_cell.handshake_len = NTOR_ONIONSKIN_LEN;
+    memcpy(cell_out->create_cell.onionskin, cell->onionskin + 16,
+           NTOR_ONIONSKIN_LEN);
+  } else {
+    cell_out->create_cell.cell_type = CELL_CREATE;
+    cell_out->create_cell.handshake_type = ONION_HANDSHAKE_TYPE_TAP;
+    cell_out->create_cell.handshake_len = TAP_ONIONSKIN_CHALLENGE_LEN;
+    memcpy(cell_out->create_cell.onionskin, cell->onionskin,
+           TAP_ONIONSKIN_CHALLENGE_LEN);
+  }
+  memcpy(cell_out->node_id, cell->identity, DIGEST_LEN);
+  return 0;
+}
+
+static int
+create_cell_from_create2_cell_body(create_cell_t *cell_out,
+                                   const create2_cell_body_t *cell)
+{
+  tor_assert(cell_out);
+  tor_assert(cell);
+  memset(cell_out, 0, sizeof(create_cell_t));
+  if (BUG(cell->handshake_len > sizeof(cell_out->onionskin))) {
+    /* This should be impossible because there just isn't enough room in the
+     * input cell to make the handshake_len this large and provide a
+     * handshake_data to match. */
+    return -1;
+  }
+
+  cell_out->cell_type = CELL_CREATE2;
+  cell_out->handshake_type = cell->handshake_type;
+  cell_out->handshake_len = cell->handshake_len;
+  memcpy(cell_out->onionskin,
+       create2_cell_body_getconstarray_handshake_data(cell),
+       cell->handshake_len);
+  return 0;
+}
+
+static int
+extend_cell_from_extend2_cell_body(extend_cell_t *cell_out,
+                                   const extend2_cell_body_t *cell)
+{
+  tor_assert(cell_out);
+  tor_assert(cell);
+  int found_ipv4 = 0, found_ipv6 = 0, found_rsa_id = 0, found_ed_id = 0;
+  memset(cell_out, 0, sizeof(*cell_out));
+  tor_addr_make_unspec(&cell_out->orport_ipv4.addr);
+  tor_addr_make_unspec(&cell_out->orport_ipv6.addr);
+  cell_out->cell_type = RELAY_COMMAND_EXTEND2;
+
+  unsigned i;
+  for (i = 0; i < cell->n_spec; ++i) {
+    const link_specifier_t *ls = extend2_cell_body_getconst_ls(cell, i);
+    switch (ls->ls_type) {
+      case LS_IPV4:
+        if (found_ipv4)
+          continue;
+        found_ipv4 = 1;
+        tor_addr_from_ipv4h(&cell_out->orport_ipv4.addr, ls->un_ipv4_addr);
+        cell_out->orport_ipv4.port = ls->un_ipv4_port;
+        break;
+      case LS_IPV6:
+        if (found_ipv6)
+          continue;
+        found_ipv6 = 1;
+        tor_addr_from_ipv6_bytes(&cell_out->orport_ipv6.addr,
+                                 (const char *)ls->un_ipv6_addr);
+        cell_out->orport_ipv6.port = ls->un_ipv6_port;
+        break;
+      case LS_LEGACY_ID:
+        if (found_rsa_id)
+          return -1;
+        found_rsa_id = 1;
+        memcpy(cell_out->node_id, ls->un_legacy_id, 20);
+        break;
+      case LS_ED25519_ID:
+        if (found_ed_id)
+          return -1;
+        found_ed_id = 1;
+        memcpy(cell_out->ed_pubkey.pubkey, ls->un_ed25519_id, 32);
+        break;
+      default:
+        /* Ignore this, whatever it is. */
+        break;
+    }
+  }
+
+  if (!found_rsa_id || !found_ipv4) /* These are mandatory */
+    return -1;
+
+  return create_cell_from_create2_cell_body(&cell_out->create_cell,
+                                            cell->create2);
+}
+
+/** Parse an EXTEND or EXTEND2 cell (according to <b>command</b>) from the
+ * <b>payload_length</b> bytes of <b>payload</b> into <b>cell_out</b>. Return
+ * 0 on success, -1 on failure. */
+int
+extend_cell_parse(extend_cell_t *cell_out, const uint8_t command,
+                  const uint8_t *payload, size_t payload_length)
+{
+
+  tor_assert(cell_out);
+  tor_assert(payload);
+
+  if (payload_length > RELAY_PAYLOAD_SIZE)
+    return -1;
+
+  switch (command) {
+  case RELAY_COMMAND_EXTEND:
+    {
+      extend1_cell_body_t *cell = NULL;
+      if (extend1_cell_body_parse(&cell, payload, payload_length)<0 ||
+          cell == NULL) {
+        if (cell)
+          extend1_cell_body_free(cell);
+        return -1;
+      }
+      int r = extend_cell_from_extend1_cell_body(cell_out, cell);
+      extend1_cell_body_free(cell);
+      if (r < 0)
+        return r;
+    }
+    break;
+  case RELAY_COMMAND_EXTEND2:
+    {
+      extend2_cell_body_t *cell = NULL;
+      if (extend2_cell_body_parse(&cell, payload, payload_length) < 0 ||
+          cell == NULL) {
+        if (cell)
+          extend2_cell_body_free(cell);
+        return -1;
+      }
+      int r = extend_cell_from_extend2_cell_body(cell_out, cell);
+      extend2_cell_body_free(cell);
+      if (r < 0)
+        return r;
+    }
+    break;
+  default:
+    return -1;
+  }
+
+  return check_extend_cell(cell_out);
+}
+
+/** Helper: return 0 if <b>cell</b> appears valid, -1 otherwise. */
+static int
+check_extended_cell(const extended_cell_t *cell)
+{
+  tor_assert(cell);
+  if (cell->created_cell.cell_type == CELL_CREATED) {
+    if (cell->cell_type != RELAY_COMMAND_EXTENDED)
+      return -1;
+  } else if (cell->created_cell.cell_type == CELL_CREATED2) {
+    if (cell->cell_type != RELAY_COMMAND_EXTENDED2)
+      return -1;
+  } else {
+    return -1;
+  }
+
+  return check_created_cell(&cell->created_cell);
+}
+
+/** Parse an EXTENDED or EXTENDED2 cell (according to <b>command</b>) from the
+ * <b>payload_length</b> bytes of <b>payload</b> into <b>cell_out</b>. Return
+ * 0 on success, -1 on failure. */
+int
+extended_cell_parse(extended_cell_t *cell_out,
+                    const uint8_t command, const uint8_t *payload,
+                    size_t payload_len)
+{
+  tor_assert(cell_out);
+  tor_assert(payload);
+
+  memset(cell_out, 0, sizeof(*cell_out));
+  if (payload_len > RELAY_PAYLOAD_SIZE)
+    return -1;
+
+  switch (command) {
+  case RELAY_COMMAND_EXTENDED:
+    if (payload_len != TAP_ONIONSKIN_REPLY_LEN)
+      return -1;
+    cell_out->cell_type = RELAY_COMMAND_EXTENDED;
+    cell_out->created_cell.cell_type = CELL_CREATED;
+    cell_out->created_cell.handshake_len = TAP_ONIONSKIN_REPLY_LEN;
+    memcpy(cell_out->created_cell.reply, payload, TAP_ONIONSKIN_REPLY_LEN);
+    break;
+  case RELAY_COMMAND_EXTENDED2:
+    {
+      cell_out->cell_type = RELAY_COMMAND_EXTENDED2;
+      cell_out->created_cell.cell_type = CELL_CREATED2;
+      cell_out->created_cell.handshake_len = ntohs(get_uint16(payload));
+      if (cell_out->created_cell.handshake_len > RELAY_PAYLOAD_SIZE - 2 ||
+          cell_out->created_cell.handshake_len > payload_len - 2)
+        return -1;
+      memcpy(cell_out->created_cell.reply, payload+2,
+             cell_out->created_cell.handshake_len);
+    }
+    break;
+  default:
+    return -1;
+  }
+
+  return check_extended_cell(cell_out);
+}
+
+/** Fill <b>cell_out</b> with a correctly formatted version of the
+ * CREATE{,_FAST,2} cell in <b>cell_in</b>. Return 0 on success, -1 on
+ * failure.  This is a cell we didn't originate if <b>relayed</b> is true. */
+static int
+create_cell_format_impl(cell_t *cell_out, const create_cell_t *cell_in,
+                        int relayed)
+{
+  uint8_t *p;
+  size_t space;
+  if (check_create_cell(cell_in, relayed) < 0)
+    return -1;
+
+  memset(cell_out->payload, 0, sizeof(cell_out->payload));
+  cell_out->command = cell_in->cell_type;
+
+  p = cell_out->payload;
+  space = sizeof(cell_out->payload);
+
+  switch (cell_in->cell_type) {
+  case CELL_CREATE:
+    if (cell_in->handshake_type == ONION_HANDSHAKE_TYPE_NTOR) {
+      memcpy(p, NTOR_CREATE_MAGIC, 16);
+      p += 16;
+      space -= 16;
+    }
+    /* Fall through */
+  case CELL_CREATE_FAST:
+    tor_assert(cell_in->handshake_len <= space);
+    memcpy(p, cell_in->onionskin, cell_in->handshake_len);
+    break;
+  case CELL_CREATE2:
+    tor_assert(cell_in->handshake_len <= sizeof(cell_out->payload)-4);
+    set_uint16(cell_out->payload, htons(cell_in->handshake_type));
+    set_uint16(cell_out->payload+2, htons(cell_in->handshake_len));
+    memcpy(cell_out->payload + 4, cell_in->onionskin, cell_in->handshake_len);
+    break;
+  default:
+    return -1;
+  }
+
+  return 0;
+}
+
+int
+create_cell_format(cell_t *cell_out, const create_cell_t *cell_in)
+{
+  return create_cell_format_impl(cell_out, cell_in, 0);
+}
+
+int
+create_cell_format_relayed(cell_t *cell_out, const create_cell_t *cell_in)
+{
+  return create_cell_format_impl(cell_out, cell_in, 1);
+}
+
+/** Fill <b>cell_out</b> with a correctly formatted version of the
+ * CREATED{,_FAST,2} cell in <b>cell_in</b>. Return 0 on success, -1 on
+ * failure. */
+int
+created_cell_format(cell_t *cell_out, const created_cell_t *cell_in)
+{
+  if (check_created_cell(cell_in) < 0)
+    return -1;
+
+  memset(cell_out->payload, 0, sizeof(cell_out->payload));
+  cell_out->command = cell_in->cell_type;
+
+  switch (cell_in->cell_type) {
+  case CELL_CREATED:
+  case CELL_CREATED_FAST:
+    tor_assert(cell_in->handshake_len <= sizeof(cell_out->payload));
+    memcpy(cell_out->payload, cell_in->reply, cell_in->handshake_len);
+    break;
+  case CELL_CREATED2:
+    tor_assert(cell_in->handshake_len <= sizeof(cell_out->payload)-2);
+    set_uint16(cell_out->payload, htons(cell_in->handshake_len));
+    memcpy(cell_out->payload + 2, cell_in->reply, cell_in->handshake_len);
+    break;
+  default:
+    return -1;
+  }
+  return 0;
+}
+
+/** Return true iff we are configured (by torrc or by the networkstatus
+ * parameters) to use Ed25519 identities in our Extend2 cells. */
+static int
+should_include_ed25519_id_extend_cells(const networkstatus_t *ns,
+                                       const or_options_t *options)
+{
+  if (options->ExtendByEd25519ID != -1)
+    return options->ExtendByEd25519ID; /* The user has an opinion. */
+
+  return (int) networkstatus_get_param(ns, "ExtendByEd25519ID",
+                                       0 /* default */,
+                                       0 /* min */,
+                                       1 /*max*/);
+}
+
+/** Format the EXTEND{,2} cell in <b>cell_in</b>, storing its relay payload in
+ * <b>payload_out</b>, the number of bytes used in *<b>len_out</b>, and the
+ * relay command in *<b>command_out</b>. The <b>payload_out</b> must have
+ * RELAY_PAYLOAD_SIZE bytes available.  Return 0 on success, -1 on failure. */
+int
+extend_cell_format(uint8_t *command_out, uint16_t *len_out,
+                   uint8_t *payload_out, const extend_cell_t *cell_in)
+{
+  uint8_t *p;
+  if (check_extend_cell(cell_in) < 0)
+    return -1;
+
+  p = payload_out;
+
+  memset(p, 0, RELAY_PAYLOAD_SIZE);
+
+  switch (cell_in->cell_type) {
+  case RELAY_COMMAND_EXTEND:
+    {
+      *command_out = RELAY_COMMAND_EXTEND;
+      *len_out = 6 + TAP_ONIONSKIN_CHALLENGE_LEN + DIGEST_LEN;
+      set_uint32(p, tor_addr_to_ipv4n(&cell_in->orport_ipv4.addr));
+      set_uint16(p+4, htons(cell_in->orport_ipv4.port));
+      if (cell_in->create_cell.handshake_type == ONION_HANDSHAKE_TYPE_NTOR) {
+        memcpy(p+6, NTOR_CREATE_MAGIC, 16);
+        memcpy(p+22, cell_in->create_cell.onionskin, NTOR_ONIONSKIN_LEN);
+      } else {
+        memcpy(p+6, cell_in->create_cell.onionskin,
+               TAP_ONIONSKIN_CHALLENGE_LEN);
+      }
+      memcpy(p+6+TAP_ONIONSKIN_CHALLENGE_LEN, cell_in->node_id, DIGEST_LEN);
+    }
+    break;
+  case RELAY_COMMAND_EXTEND2:
+    {
+      uint8_t n_specifiers = 2;
+      *command_out = RELAY_COMMAND_EXTEND2;
+      extend2_cell_body_t *cell = extend2_cell_body_new();
+      link_specifier_t *ls;
+      {
+        /* IPv4 specifier first. */
+        ls = link_specifier_new();
+        extend2_cell_body_add_ls(cell, ls);
+        ls->ls_type = LS_IPV4;
+        ls->ls_len = 6;
+        ls->un_ipv4_addr = tor_addr_to_ipv4h(&cell_in->orport_ipv4.addr);
+        ls->un_ipv4_port = cell_in->orport_ipv4.port;
+      }
+      {
+        /* Then RSA id */
+        ls = link_specifier_new();
+        extend2_cell_body_add_ls(cell, ls);
+        ls->ls_type = LS_LEGACY_ID;
+        ls->ls_len = DIGEST_LEN;
+        memcpy(ls->un_legacy_id, cell_in->node_id, DIGEST_LEN);
+      }
+      if (should_include_ed25519_id_extend_cells(NULL, get_options()) &&
+          !ed25519_public_key_is_zero(&cell_in->ed_pubkey)) {
+        /* Then, maybe, the ed25519 id! */
+        ++n_specifiers;
+        ls = link_specifier_new();
+        extend2_cell_body_add_ls(cell, ls);
+        ls->ls_type = LS_ED25519_ID;
+        ls->ls_len = 32;
+        memcpy(ls->un_ed25519_id, cell_in->ed_pubkey.pubkey, 32);
+      }
+      cell->n_spec = n_specifiers;
+
+      /* Now, the handshake */
+      cell->create2 = create2_cell_body_new();
+      cell->create2->handshake_type = cell_in->create_cell.handshake_type;
+      cell->create2->handshake_len = cell_in->create_cell.handshake_len;
+      create2_cell_body_setlen_handshake_data(cell->create2,
+                                         cell_in->create_cell.handshake_len);
+      memcpy(create2_cell_body_getarray_handshake_data(cell->create2),
+             cell_in->create_cell.onionskin,
+             cell_in->create_cell.handshake_len);
+
+      ssize_t len_encoded = extend2_cell_body_encode(
+                             payload_out, RELAY_PAYLOAD_SIZE,
+                             cell);
+      extend2_cell_body_free(cell);
+      if (len_encoded < 0 || len_encoded > UINT16_MAX)
+        return -1;
+      *len_out = (uint16_t) len_encoded;
+    }
+    break;
+  default:
+    return -1;
+  }
+
+  return 0;
+}
+
+/** Format the EXTENDED{,2} cell in <b>cell_in</b>, storing its relay payload
+ * in <b>payload_out</b>, the number of bytes used in *<b>len_out</b>, and the
+ * relay command in *<b>command_out</b>. The <b>payload_out</b> must have
+ * RELAY_PAYLOAD_SIZE bytes available.  Return 0 on success, -1 on failure. */
+int
+extended_cell_format(uint8_t *command_out, uint16_t *len_out,
+                     uint8_t *payload_out, const extended_cell_t *cell_in)
+{
+  uint8_t *p;
+  if (check_extended_cell(cell_in) < 0)
+    return -1;
+
+  p = payload_out;
+  memset(p, 0, RELAY_PAYLOAD_SIZE);
+
+  switch (cell_in->cell_type) {
+  case RELAY_COMMAND_EXTENDED:
+    {
+      *command_out = RELAY_COMMAND_EXTENDED;
+      *len_out = TAP_ONIONSKIN_REPLY_LEN;
+      memcpy(payload_out, cell_in->created_cell.reply,
+             TAP_ONIONSKIN_REPLY_LEN);
+    }
+    break;
+  case RELAY_COMMAND_EXTENDED2:
+    {
+      *command_out = RELAY_COMMAND_EXTENDED2;
+      *len_out = 2 + cell_in->created_cell.handshake_len;
+      set_uint16(payload_out, htons(cell_in->created_cell.handshake_len));
+      if (2+cell_in->created_cell.handshake_len > RELAY_PAYLOAD_SIZE)
+        return -1;
+      memcpy(payload_out+2, cell_in->created_cell.reply,
+             cell_in->created_cell.handshake_len);
+    }
+    break;
+  default:
+    return -1;
+  }
+
+  return 0;
+}
diff --git a/src/core/crypto/onion.h b/src/core/crypto/onion.h
new file mode 100644
index 0000000000..ff70f299d5
--- /dev/null
+++ b/src/core/crypto/onion.h
@@ -0,0 +1,128 @@
+/* Copyright (c) 2001 Matej Pfajfar.
+ * Copyright (c) 2001-2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2018, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file onion.h
+ * \brief Header file for onion.c.
+ **/
+
+#ifndef TOR_ONION_H
+#define TOR_ONION_H
+
+struct create_cell_t;
+struct curve25519_keypair_t;
+struct curve25519_public_key_t;
+#include "lib/crypt_ops/crypto_ed25519.h"
+
+int onion_pending_add(or_circuit_t *circ, struct create_cell_t *onionskin);
+or_circuit_t *onion_next_task(struct create_cell_t **onionskin_out);
+int onion_num_pending(uint16_t handshake_type);
+void onion_pending_remove(or_circuit_t *circ);
+void clear_pending_onions(void);
+
+typedef struct server_onion_keys_t {
+  uint8_t my_identity[DIGEST_LEN];
+  crypto_pk_t *onion_key;
+  crypto_pk_t *last_onion_key;
+  struct di_digest256_map_t *curve25519_key_map;
+  struct curve25519_keypair_t *junk_keypair;
+} server_onion_keys_t;
+
+#define MAX_ONIONSKIN_CHALLENGE_LEN 255
+#define MAX_ONIONSKIN_REPLY_LEN 255
+
+server_onion_keys_t *server_onion_keys_new(void);
+void server_onion_keys_free_(server_onion_keys_t *keys);
+#define server_onion_keys_free(keys) \
+  FREE_AND_NULL(server_onion_keys_t, server_onion_keys_free_, (keys))
+
+void onion_handshake_state_release(onion_handshake_state_t *state);
+
+int onion_skin_create(int type,
+                      const extend_info_t *node,
+                      onion_handshake_state_t *state_out,
+                      uint8_t *onion_skin_out);
+int onion_skin_server_handshake(int type,
+                      const uint8_t *onion_skin, size_t onionskin_len,
+                      const server_onion_keys_t *keys,
+                      uint8_t *reply_out,
+                      uint8_t *keys_out, size_t key_out_len,
+                      uint8_t *rend_nonce_out);
+int onion_skin_client_handshake(int type,
+                      const onion_handshake_state_t *handshake_state,
+                      const uint8_t *reply, size_t reply_len,
+                      uint8_t *keys_out, size_t key_out_len,
+                      uint8_t *rend_authenticator_out,
+                      const char **msg_out);
+
+/** A parsed CREATE, CREATE_FAST, or CREATE2 cell. */
+typedef struct create_cell_t {
+  /** The cell command. One of CREATE{,_FAST,2} */
+  uint8_t cell_type;
+  /** One of the ONION_HANDSHAKE_TYPE_* values */
+  uint16_t handshake_type;
+  /** The number of bytes used in <b>onionskin</b>. */
+  uint16_t handshake_len;
+  /** The client-side message for the circuit creation handshake. */
+  uint8_t onionskin[CELL_PAYLOAD_SIZE - 4];
+} create_cell_t;
+
+/** A parsed CREATED, CREATED_FAST, or CREATED2 cell. */
+typedef struct created_cell_t {
+  /** The cell command. One of CREATED{,_FAST,2} */
+  uint8_t cell_type;
+  /** The number of bytes used in <b>reply</b>. */
+  uint16_t handshake_len;
+  /** The server-side message for the circuit creation handshake. */
+  uint8_t reply[CELL_PAYLOAD_SIZE - 2];
+} created_cell_t;
+
+/** A parsed RELAY_EXTEND or RELAY_EXTEND2 cell */
+typedef struct extend_cell_t {
+  /** One of RELAY_EXTEND or RELAY_EXTEND2 */
+  uint8_t cell_type;
+  /** An IPv4 address and port for the node we're connecting to. */
+  tor_addr_port_t orport_ipv4;
+  /** An IPv6 address and port for the node we're connecting to. Not currently
+   * used. */
+  tor_addr_port_t orport_ipv6;
+  /** Identity fingerprint of the node we're conecting to.*/
+  uint8_t node_id[DIGEST_LEN];
+  /** Ed25519 public identity key. Zero if not set. */
+  struct ed25519_public_key_t ed_pubkey;
+  /** The "create cell" embedded in this extend cell. Note that unlike the
+   * create cells we generate ourself, this once can have a handshake type we
+   * don't recognize. */
+  create_cell_t create_cell;
+} extend_cell_t;
+
+/** A parsed RELAY_EXTEND or RELAY_EXTEND2 cell */
+typedef struct extended_cell_t {
+  /** One of RELAY_EXTENDED or RELAY_EXTENDED2. */
+  uint8_t cell_type;
+  /** The "created cell" embedded in this extended cell. */
+  created_cell_t created_cell;
+} extended_cell_t;
+
+void create_cell_init(create_cell_t *cell_out, uint8_t cell_type,
+                      uint16_t handshake_type, uint16_t handshake_len,
+                      const uint8_t *onionskin);
+int create_cell_parse(create_cell_t *cell_out, const cell_t *cell_in);
+int created_cell_parse(created_cell_t *cell_out, const cell_t *cell_in);
+int extend_cell_parse(extend_cell_t *cell_out, const uint8_t command,
+                      const uint8_t *payload_in, size_t payload_len);
+int extended_cell_parse(extended_cell_t *cell_out, const uint8_t command,
+                        const uint8_t *payload_in, size_t payload_len);
+
+int create_cell_format(cell_t *cell_out, const create_cell_t *cell_in);
+int create_cell_format_relayed(cell_t *cell_out, const create_cell_t *cell_in);
+int created_cell_format(cell_t *cell_out, const created_cell_t *cell_in);
+int extend_cell_format(uint8_t *command_out, uint16_t *len_out,
+                       uint8_t *payload_out, const extend_cell_t *cell_in);
+int extended_cell_format(uint8_t *command_out, uint16_t *len_out,
+                         uint8_t *payload_out, const extended_cell_t *cell_in);
+
+#endif /* !defined(TOR_ONION_H) */
diff --git a/src/core/crypto/onion_fast.c b/src/core/crypto/onion_fast.c
new file mode 100644
index 0000000000..6e834ccf95
--- /dev/null
+++ b/src/core/crypto/onion_fast.c
@@ -0,0 +1,144 @@
+/* Copyright (c) 2001 Matej Pfajfar.
+ * Copyright (c) 2001-2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2018, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file onion_fast.c
+ * \brief Functions implement the CREATE_FAST circuit handshake.
+ *
+ * The "CREATE_FAST" handshake is an unauthenticated, non-forward-secure
+ * key derivation mechanism based on SHA1.  We used to use it for the
+ * first hop of each circuit, since the TAP handshake provided no
+ * additional security beyond the security already provided by the TLS
+ * handshake [*].
+ *
+ * When we switched to ntor, we deprecated CREATE_FAST, since ntor is
+ * stronger than our TLS handshake was, and fast enough to not be worrisome.
+ *
+ * This handshake, like the other circuit-extension handshakes, is
+ * invoked from onion.c.
+ *
+ * [*]Actually, it's possible that TAP _was_ a little better than TLS with
+ * RSA1024 certificates and EDH1024 for forward secrecy, if you
+ * hypothesize an adversary who can compute discrete logarithms on a
+ * small number of targeted DH1024 fields, but who can't break all that
+ * many RSA1024 keys.
+ **/
+
+#include "or/or.h"
+#include "or/onion_fast.h"
+#include "lib/crypt_ops/crypto_hkdf.h"
+#include "lib/crypt_ops/crypto_rand.h"
+#include "lib/crypt_ops/crypto_util.h"
+
+/** Release all state held in <b>victim</b>. */
+void
+fast_handshake_state_free_(fast_handshake_state_t *victim)
+{
+  if (! victim)
+    return;
+  memwipe(victim, 0, sizeof(fast_handshake_state_t));
+  tor_free(victim);
+}
+
+/** Create the state needed to perform a CREATE_FAST handshake. Return 0
+ * on success, -1 on failure. */
+int
+fast_onionskin_create(fast_handshake_state_t **handshake_state_out,
+                      uint8_t *handshake_out)
+{
+  fast_handshake_state_t *s;
+  *handshake_state_out = s = tor_malloc(sizeof(fast_handshake_state_t));
+  crypto_rand((char*)s->state, sizeof(s->state));
+  memcpy(handshake_out, s->state, DIGEST_LEN);
+  return 0;
+}
+
+/** Implement the server side of the CREATE_FAST abbreviated handshake.  The
+ * client has provided DIGEST_LEN key bytes in <b>key_in</b> ("x").  We
+ * generate a reply of DIGEST_LEN*2 bytes in <b>key_out</b>, consisting of a
+ * new random "y", followed by H(x|y) to check for correctness.  We set
+ * <b>key_out_len</b> bytes of key material in <b>key_out</b>.
+ * Return 0 on success, &lt;0 on failure.
+ **/
+int
+fast_server_handshake(const uint8_t *key_in, /* DIGEST_LEN bytes */
+                      uint8_t *handshake_reply_out, /* DIGEST_LEN*2 bytes */
+                      uint8_t *key_out,
+                      size_t key_out_len)
+{
+  uint8_t tmp[DIGEST_LEN+DIGEST_LEN];
+  uint8_t *out = NULL;
+  size_t out_len;
+  int r = -1;
+
+  crypto_rand((char*)handshake_reply_out, DIGEST_LEN);
+
+  memcpy(tmp, key_in, DIGEST_LEN);
+  memcpy(tmp+DIGEST_LEN, handshake_reply_out, DIGEST_LEN);
+  out_len = key_out_len+DIGEST_LEN;
+  out = tor_malloc(out_len);
+  if (BUG(crypto_expand_key_material_TAP(tmp, sizeof(tmp), out, out_len))) {
+    goto done; // LCOV_EXCL_LINE
+  }
+  memcpy(handshake_reply_out+DIGEST_LEN, out, DIGEST_LEN);
+  memcpy(key_out, out+DIGEST_LEN, key_out_len);
+  r = 0;
+ done:
+  memwipe(tmp, 0, sizeof(tmp));
+  memwipe(out, 0, out_len);
+  tor_free(out);
+  return r;
+}
+
+/** Implement the second half of the client side of the CREATE_FAST handshake.
+ * We sent the server <b>handshake_state</b> ("x") already, and the server
+ * told us <b>handshake_reply_out</b> (y|H(x|y)).  Make sure that the hash is
+ * correct, and generate key material in <b>key_out</b>.  Return 0 on success,
+ * true on failure.
+ *
+ * NOTE: The "CREATE_FAST" handshake path is distinguishable from regular
+ * "onionskin" handshakes, and is not secure if an adversary can see or modify
+ * the messages.  Therefore, it should only be used by clients, and only as
+ * the first hop of a circuit (since the first hop is already authenticated
+ * and protected by TLS).
+ */
+int
+fast_client_handshake(const fast_handshake_state_t *handshake_state,
+                      const uint8_t *handshake_reply_out,/*DIGEST_LEN*2 bytes*/
+                      uint8_t *key_out,
+                      size_t key_out_len,
+                      const char **msg_out)
+{
+  uint8_t tmp[DIGEST_LEN+DIGEST_LEN];
+  uint8_t *out;
+  size_t out_len;
+  int r = -1;
+
+  memcpy(tmp, handshake_state->state, DIGEST_LEN);
+  memcpy(tmp+DIGEST_LEN, handshake_reply_out, DIGEST_LEN);
+  out_len = key_out_len+DIGEST_LEN;
+  out = tor_malloc(out_len);
+  if (BUG(crypto_expand_key_material_TAP(tmp, sizeof(tmp), out, out_len))) {
+    /* LCOV_EXCL_START */
+    if (msg_out)
+      *msg_out = "Failed to expand key material";
+    goto done;
+    /* LCOV_EXCL_STOP */
+  }
+  if (tor_memneq(out, handshake_reply_out+DIGEST_LEN, DIGEST_LEN)) {
+    /* H(K) does *not* match. Something fishy. */
+    if (msg_out)
+      *msg_out = "Digest DOES NOT MATCH on fast handshake. Bug or attack.";
+    goto done;
+  }
+  memcpy(key_out, out+DIGEST_LEN, key_out_len);
+  r = 0;
+ done:
+  memwipe(tmp, 0, sizeof(tmp));
+  memwipe(out, 0, out_len);
+  tor_free(out);
+  return r;
+}
diff --git a/src/core/crypto/onion_fast.h b/src/core/crypto/onion_fast.h
new file mode 100644
index 0000000000..a7b6ec53f4
--- /dev/null
+++ b/src/core/crypto/onion_fast.h
@@ -0,0 +1,41 @@
+/* Copyright (c) 2001 Matej Pfajfar.
+ * Copyright (c) 2001-2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2018, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file onion_fast.h
+ * \brief Header file for onion_fast.c.
+ **/
+
+#ifndef TOR_ONION_FAST_H
+#define TOR_ONION_FAST_H
+
+#define CREATE_FAST_LEN DIGEST_LEN
+#define CREATED_FAST_LEN (DIGEST_LEN*2)
+
+typedef struct fast_handshake_state_t {
+  uint8_t state[DIGEST_LEN];
+} fast_handshake_state_t;
+
+void fast_handshake_state_free_(fast_handshake_state_t *victim);
+#define fast_handshake_state_free(st) \
+  FREE_AND_NULL(fast_handshake_state_t, fast_handshake_state_free_, (st))
+
+int fast_onionskin_create(fast_handshake_state_t **handshake_state_out,
+                          uint8_t *handshake_out);
+
+int fast_server_handshake(const uint8_t *message_in,
+                          uint8_t *handshake_reply_out,
+                          uint8_t *key_out,
+                          size_t key_out_len);
+
+int fast_client_handshake(const fast_handshake_state_t *handshake_state,
+                          const uint8_t *handshake_reply_out,
+                          uint8_t *key_out,
+                          size_t key_out_len,
+                          const char **msg_out);
+
+#endif /* !defined(TOR_ONION_FAST_H) */
+
diff --git a/src/core/crypto/onion_ntor.c b/src/core/crypto/onion_ntor.c
new file mode 100644
index 0000000000..59c923cb97
--- /dev/null
+++ b/src/core/crypto/onion_ntor.c
@@ -0,0 +1,341 @@
+/* Copyright (c) 2012-2018, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file onion_ntor.c
+ *
+ * \brief Implementation for the ntor handshake.
+ *
+ * The ntor circuit-extension handshake was developed as a replacement
+ * for the old TAP handshake.  It uses Elliptic-curve Diffie-Hellman and
+ * a hash function in order to perform a one-way authenticated key
+ * exchange.  The ntor handshake is meant to replace the old "TAP"
+ * handshake.
+ *
+ * We instantiate ntor with curve25519, HMAC-SHA256, and HKDF.
+ *
+ * This handshake, like the other circuit-extension handshakes, is
+ * invoked from onion.c.
+ */
+
+#include "orconfig.h"
+
+#define ONION_NTOR_PRIVATE
+
+#include "lib/crypt_ops/crypto.h"
+#include "lib/crypt_ops/crypto_digest.h"
+#include "lib/crypt_ops/crypto_hkdf.h"
+#include "lib/crypt_ops/crypto_util.h"
+#include "lib/ctime/di_ops.h"
+#include "lib/log/torlog.h"
+#include "lib/log/util_bug.h"
+#include "or/onion_ntor.h"
+
+#include <string.h>
+
+/** 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. */
+static 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));
+  if (curve25519_secret_key_generate(&state->seckey_x, 0) < 0) {
+    /* LCOV_EXCL_START
+     * Secret key generation should be unable to fail when the key isn't
+     * marked as "extra-strong" */
+    tor_assert_nonfatal_unreached();
+    tor_free(state);
+    return -1;
+    /* LCOV_EXCL_STOP */
+  }
+  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.  Use <b>junk_keys</b> if present if the handshake
+ * indicates an unrecognized public key.  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 curve25519_keypair_t *junk_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;
+  /* Note that on key-not-found, we go through with this operation anyway,
+   * using "junk_keys". This will result in failed authentication, but won't
+   * leak whether we recognized the key. */
+  keypair_bB = dimap_search(private_keys, onion_skin + DIGEST_LEN,
+                            (void*)junk_keys);
+  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 = safe_mem_is_zero(si, CURVE25519_OUTPUT_LEN);
+  si += CURVE25519_OUTPUT_LEN;
+  curve25519_handshake(si, &keypair_bB->seckey, &s.pubkey_X);
+  bad |= safe_mem_is_zero(si, CURVE25519_OUTPUT_LEN);
+  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 char **msg_out)
+{
+  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 = safe_mem_is_zero(si, CURVE25519_OUTPUT_LEN);
+  si += CURVE25519_OUTPUT_LEN;
+  curve25519_handshake(si, &handshake_state->seckey_x,
+                       &handshake_state->pubkey_B);
+  bad |= (safe_mem_is_zero(si, CURVE25519_OUTPUT_LEN) << 1);
+  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) << 2);
+
+  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));
+
+  if (bad) {
+    if (bad & 4) {
+      if (msg_out)
+        *msg_out = NULL; /* Don't report this one; we probably just had the
+                          * wrong onion key.*/
+      log_fn(LOG_INFO, LD_PROTOCOL,
+             "Invalid result from curve25519 handshake: %d", bad);
+    }
+    if (bad & 3) {
+      if (msg_out)
+        *msg_out = "Zero output from curve25519 handshake";
+      log_fn(LOG_WARN, LD_PROTOCOL,
+             "Invalid result from curve25519 handshake: %d", bad);
+    }
+  }
+
+  return bad ? -1 : 0;
+}
diff --git a/src/core/crypto/onion_ntor.h b/src/core/crypto/onion_ntor.h
new file mode 100644
index 0000000000..0ba4abe49e
--- /dev/null
+++ b/src/core/crypto/onion_ntor.h
@@ -0,0 +1,65 @@
+/* Copyright (c) 2012-2018, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#ifndef TOR_ONION_NTOR_H
+#define TOR_ONION_NTOR_H
+
+#include "lib/cc/torint.h"
+
+struct di_digest256_map_t;
+struct curve25519_public_key_t;
+struct curve25519_keypair_t;
+
+/** 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
+
+void ntor_handshake_state_free_(ntor_handshake_state_t *state);
+#define ntor_handshake_state_free(state) \
+  FREE_AND_NULL(ntor_handshake_state_t, ntor_handshake_state_free_, (state))
+
+int onion_skin_ntor_create(const uint8_t *router_id,
+                           const struct 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 struct di_digest256_map_t *private_keys,
+                           const struct curve25519_keypair_t *junk_keypair,
+                           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,
+                             const char **msg_out);
+
+#ifdef ONION_NTOR_PRIVATE
+#include "lib/crypt_ops/crypto_curve25519.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;
+  /** @} */
+};
+#endif /* defined(ONION_NTOR_PRIVATE) */
+
+#endif /* !defined(TOR_ONION_NTOR_H) */
diff --git a/src/core/crypto/onion_tap.c b/src/core/crypto/onion_tap.c
new file mode 100644
index 0000000000..05bcce2e87
--- /dev/null
+++ b/src/core/crypto/onion_tap.c
@@ -0,0 +1,246 @@
+/* Copyright (c) 2001 Matej Pfajfar.
+ * Copyright (c) 2001-2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2018, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file onion_tap.c
+ * \brief Functions to implement the original Tor circuit extension handshake
+ * (a.k.a TAP).
+ *
+ * The "TAP" handshake is the first one that was widely used in Tor: It
+ * combines RSA1024-OAEP and AES128-CTR to perform a hybrid encryption over
+ * the first message DH1024 key exchange.  (The RSA-encrypted part of the
+ * encryption is authenticated; the AES-encrypted part isn't. This was
+ * not a smart choice.)
+ *
+ * We didn't call it "TAP" ourselves -- Ian Goldberg named it in "On the
+ * Security of the Tor Authentication Protocol".  (Spoiler: it's secure, but
+ * its security is kind of fragile and implementation dependent.  Never modify
+ * this implementation without reading and understanding that paper at least.)
+ *
+ * We have deprecated TAP since the ntor handshake came into general use.  It
+ * is still used for hidden service IP and RP connections, however.
+ *
+ * This handshake, like the other circuit-extension handshakes, is
+ * invoked from onion.c.
+ **/
+
+#include "or/or.h"
+#include "or/config.h"
+#include "lib/crypt_ops/crypto_dh.h"
+#include "lib/crypt_ops/crypto_rand.h"
+#include "lib/crypt_ops/crypto_util.h"
+#include "or/onion_tap.h"
+#include "or/rephist.h"
+
+/*----------------------------------------------------------------------*/
+
+/** Given a router's 128 byte public key,
+ * stores the following in onion_skin_out:
+ *   - [42 bytes] OAEP padding
+ *   - [16 bytes] Symmetric key for encrypting blob past RSA
+ *   - [70 bytes] g^x part 1 (inside the RSA)
+ *   - [58 bytes] g^x part 2 (symmetrically encrypted)
+ *
+ * Stores the DH private key into handshake_state_out for later completion
+ * of the handshake.
+ *
+ * The meeting point/cookies and auth are zeroed out for now.
+ */
+int
+onion_skin_TAP_create(crypto_pk_t *dest_router_key,
+                  crypto_dh_t **handshake_state_out,
+                  char *onion_skin_out) /* TAP_ONIONSKIN_CHALLENGE_LEN bytes */
+{
+  char challenge[DH1024_KEY_LEN];
+  crypto_dh_t *dh = NULL;
+  int dhbytes, pkbytes;
+
+  tor_assert(dest_router_key);
+  tor_assert(handshake_state_out);
+  tor_assert(onion_skin_out);
+  *handshake_state_out = NULL;
+  memset(onion_skin_out, 0, TAP_ONIONSKIN_CHALLENGE_LEN);
+
+  if (!(dh = crypto_dh_new(DH_TYPE_CIRCUIT)))
+    goto err;
+
+  dhbytes = crypto_dh_get_bytes(dh);
+  pkbytes = (int) crypto_pk_keysize(dest_router_key);
+  tor_assert(dhbytes == 128);
+  tor_assert(pkbytes == 128);
+
+  if (crypto_dh_get_public(dh, challenge, dhbytes))
+    goto err;
+
+  /* set meeting point, meeting cookie, etc here. Leave zero for now. */
+  if (crypto_pk_obsolete_public_hybrid_encrypt(dest_router_key, onion_skin_out,
+                                      TAP_ONIONSKIN_CHALLENGE_LEN,
+                                      challenge, DH1024_KEY_LEN,
+                                      PK_PKCS1_OAEP_PADDING, 1)<0)
+    goto err;
+
+  memwipe(challenge, 0, sizeof(challenge));
+  *handshake_state_out = dh;
+
+  return 0;
+ err:
+  /* LCOV_EXCL_START
+   * We only get here if RSA encryption fails or DH keygen fails. Those
+   * shouldn't be possible. */
+  memwipe(challenge, 0, sizeof(challenge));
+  if (dh) crypto_dh_free(dh);
+  return -1;
+  /* LCOV_EXCL_STOP */
+}
+
+/** Given an encrypted DH public key as generated by onion_skin_create,
+ * and the private key for this onion router, generate the reply (128-byte
+ * DH plus the first 20 bytes of shared key material), and store the
+ * next key_out_len bytes of key material in key_out.
+ */
+int
+onion_skin_TAP_server_handshake(
+                            /*TAP_ONIONSKIN_CHALLENGE_LEN*/
+                            const char *onion_skin,
+                            crypto_pk_t *private_key,
+                            crypto_pk_t *prev_private_key,
+                            /*TAP_ONIONSKIN_REPLY_LEN*/
+                            char *handshake_reply_out,
+                            char *key_out,
+                            size_t key_out_len)
+{
+  char challenge[TAP_ONIONSKIN_CHALLENGE_LEN];
+  crypto_dh_t *dh = NULL;
+  ssize_t len;
+  char *key_material=NULL;
+  size_t key_material_len=0;
+  int i;
+  crypto_pk_t *k;
+
+  len = -1;
+  for (i=0;i<2;++i) {
+    k = i==0?private_key:prev_private_key;
+    if (!k)
+      break;
+    len = crypto_pk_obsolete_private_hybrid_decrypt(k, challenge,
+                                           TAP_ONIONSKIN_CHALLENGE_LEN,
+                                           onion_skin,
+                                           TAP_ONIONSKIN_CHALLENGE_LEN,
+                                           PK_PKCS1_OAEP_PADDING,0);
+    if (len>0)
+      break;
+  }
+  if (len<0) {
+    log_info(LD_PROTOCOL,
+             "Couldn't decrypt onionskin: client may be using old onion key");
+    goto err;
+  } else if (len != DH1024_KEY_LEN) {
+    log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
+           "Unexpected onionskin length after decryption: %ld",
+           (long)len);
+    goto err;
+  }
+
+  dh = crypto_dh_new(DH_TYPE_CIRCUIT);
+  if (!dh) {
+    /* LCOV_EXCL_START
+     * Failure to allocate a DH key should be impossible.
+     */
+    log_warn(LD_BUG, "Couldn't allocate DH key");
+    goto err;
+    /* LCOV_EXCL_STOP */
+  }
+  if (crypto_dh_get_public(dh, handshake_reply_out, DH1024_KEY_LEN)) {
+    /* LCOV_EXCL_START
+     * This can only fail if the length of the key we just allocated is too
+     * big. That should be impossible. */
+    log_info(LD_GENERAL, "crypto_dh_get_public failed.");
+    goto err;
+    /* LCOV_EXCL_STOP */
+  }
+
+  key_material_len = DIGEST_LEN+key_out_len;
+  key_material = tor_malloc(key_material_len);
+  len = crypto_dh_compute_secret(LOG_PROTOCOL_WARN, dh, challenge,
+                                 DH1024_KEY_LEN, key_material,
+                                 key_material_len);
+  if (len < 0) {
+    log_info(LD_GENERAL, "crypto_dh_compute_secret failed.");
+    goto err;
+  }
+
+  /* send back H(K|0) as proof that we learned K. */
+  memcpy(handshake_reply_out+DH1024_KEY_LEN, key_material, DIGEST_LEN);
+
+  /* use the rest of the key material for our shared keys, digests, etc */
+  memcpy(key_out, key_material+DIGEST_LEN, key_out_len);
+
+  memwipe(challenge, 0, sizeof(challenge));
+  memwipe(key_material, 0, key_material_len);
+  tor_free(key_material);
+  crypto_dh_free(dh);
+  return 0;
+ err:
+  memwipe(challenge, 0, sizeof(challenge));
+  if (key_material) {
+    memwipe(key_material, 0, key_material_len);
+    tor_free(key_material);
+  }
+  if (dh) crypto_dh_free(dh);
+
+  return -1;
+}
+
+/** Finish the client side of the DH handshake.
+ * Given the 128 byte DH reply + 20 byte hash as generated by
+ * onion_skin_server_handshake and the handshake state generated by
+ * onion_skin_create, verify H(K) with the first 20 bytes of shared
+ * key material, then generate key_out_len more bytes of shared key
+ * material and store them in key_out.
+ *
+ * After the invocation, call crypto_dh_free on handshake_state.
+ */
+int
+onion_skin_TAP_client_handshake(crypto_dh_t *handshake_state,
+            const char *handshake_reply, /* TAP_ONIONSKIN_REPLY_LEN bytes */
+            char *key_out,
+            size_t key_out_len,
+            const char **msg_out)
+{
+  ssize_t len;
+  char *key_material=NULL;
+  size_t key_material_len;
+  tor_assert(crypto_dh_get_bytes(handshake_state) == DH1024_KEY_LEN);
+
+  key_material_len = DIGEST_LEN + key_out_len;
+  key_material = tor_malloc(key_material_len);
+  len = crypto_dh_compute_secret(LOG_PROTOCOL_WARN, handshake_state,
+                                 handshake_reply, DH1024_KEY_LEN, key_material,
+                                 key_material_len);
+  if (len < 0) {
+    if (msg_out)
+      *msg_out = "DH computation failed.";
+    goto err;
+  }
+
+  if (tor_memneq(key_material, handshake_reply+DH1024_KEY_LEN, DIGEST_LEN)) {
+    /* H(K) does *not* match. Something fishy. */
+    if (msg_out)
+      *msg_out = "Digest DOES NOT MATCH on onion handshake. Bug or attack.";
+    goto err;
+  }
+
+  /* use the rest of the key material for our shared keys, digests, etc */
+  memcpy(key_out, key_material+DIGEST_LEN, key_out_len);
+
+  memwipe(key_material, 0, key_material_len);
+  tor_free(key_material);
+  return 0;
+ err:
+  memwipe(key_material, 0, key_material_len);
+  tor_free(key_material);
+  return -1;
+}
diff --git a/src/core/crypto/onion_tap.h b/src/core/crypto/onion_tap.h
new file mode 100644
index 0000000000..9a3df684d6
--- /dev/null
+++ b/src/core/crypto/onion_tap.h
@@ -0,0 +1,40 @@
+/* Copyright (c) 2001 Matej Pfajfar.
+ * Copyright (c) 2001-2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2018, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file onion_tap.h
+ * \brief Header file for onion_tap.c.
+ **/
+
+#ifndef TOR_ONION_TAP_H
+#define TOR_ONION_TAP_H
+
+#define TAP_ONIONSKIN_CHALLENGE_LEN (PKCS1_OAEP_PADDING_OVERHEAD+\
+                                 CIPHER_KEY_LEN+\
+                                 DH1024_KEY_LEN)
+#define TAP_ONIONSKIN_REPLY_LEN (DH1024_KEY_LEN+DIGEST_LEN)
+
+struct crypto_dh_t;
+struct crypto_pk_t;
+
+int onion_skin_TAP_create(struct crypto_pk_t *router_key,
+                      struct crypto_dh_t **handshake_state_out,
+                      char *onion_skin_out);
+
+int onion_skin_TAP_server_handshake(const char *onion_skin,
+                                struct crypto_pk_t *private_key,
+                                struct crypto_pk_t *prev_private_key,
+                                char *handshake_reply_out,
+                                char *key_out,
+                                size_t key_out_len);
+
+int onion_skin_TAP_client_handshake(struct crypto_dh_t *handshake_state,
+                                const char *handshake_reply,
+                                char *key_out,
+                                size_t key_out_len,
+                                const char **msg_out);
+
+#endif /* !defined(TOR_ONION_TAP_H) */
diff --git a/src/core/crypto/relay_crypto.c b/src/core/crypto/relay_crypto.c
new file mode 100644
index 0000000000..1fcfae0b3a
--- /dev/null
+++ b/src/core/crypto/relay_crypto.c
@@ -0,0 +1,332 @@
+/* Copyright (c) 2001 Matej Pfajfar.
+ * Copyright (c) 2001-2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2018, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#include "or/or.h"
+#include "or/circuitlist.h"
+#include "or/config.h"
+#include "lib/crypt_ops/crypto.h"
+#include "lib/crypt_ops/crypto_util.h"
+#include "or/hs_ntor.h" // for HS_NTOR_KEY_EXPANSION_KDF_OUT_LEN
+#include "or/relay.h"
+#include "or/relay_crypto.h"
+
+#include "or/cell_st.h"
+#include "or/or_circuit_st.h"
+#include "or/origin_circuit_st.h"
+
+/** Update digest from the payload of cell. Assign integrity part to
+ * cell.
+ */
+static void
+relay_set_digest(crypto_digest_t *digest, cell_t *cell)
+{
+  char integrity[4];
+  relay_header_t rh;
+
+  crypto_digest_add_bytes(digest, (char*)cell->payload, CELL_PAYLOAD_SIZE);
+  crypto_digest_get_digest(digest, integrity, 4);
+//  log_fn(LOG_DEBUG,"Putting digest of %u %u %u %u into relay cell.",
+//    integrity[0], integrity[1], integrity[2], integrity[3]);
+  relay_header_unpack(&rh, cell->payload);
+  memcpy(rh.integrity, integrity, 4);
+  relay_header_pack(cell->payload, &rh);
+}
+
+/** Does the digest for this circuit indicate that this cell is for us?
+ *
+ * Update digest from the payload of cell (with the integrity part set
+ * to 0). If the integrity part is valid, return 1, else restore digest
+ * and cell to their original state and return 0.
+ */
+static int
+relay_digest_matches(crypto_digest_t *digest, cell_t *cell)
+{
+  uint32_t received_integrity, calculated_integrity;
+  relay_header_t rh;
+  crypto_digest_checkpoint_t backup_digest;
+
+  crypto_digest_checkpoint(&backup_digest, digest);
+
+  relay_header_unpack(&rh, cell->payload);
+  memcpy(&received_integrity, rh.integrity, 4);
+  memset(rh.integrity, 0, 4);
+  relay_header_pack(cell->payload, &rh);
+
+//  log_fn(LOG_DEBUG,"Reading digest of %u %u %u %u from relay cell.",
+//    received_integrity[0], received_integrity[1],
+//    received_integrity[2], received_integrity[3]);
+
+  crypto_digest_add_bytes(digest, (char*) cell->payload, CELL_PAYLOAD_SIZE);
+  crypto_digest_get_digest(digest, (char*) &calculated_integrity, 4);
+
+  int rv = 1;
+
+  if (calculated_integrity != received_integrity) {
+//    log_fn(LOG_INFO,"Recognized=0 but bad digest. Not recognizing.");
+// (%d vs %d).", received_integrity, calculated_integrity);
+    /* restore digest to its old form */
+    crypto_digest_restore(digest, &backup_digest);
+    /* restore the relay header */
+    memcpy(rh.integrity, &received_integrity, 4);
+    relay_header_pack(cell->payload, &rh);
+    rv = 0;
+  }
+
+  memwipe(&backup_digest, 0, sizeof(backup_digest));
+  return rv;
+}
+
+/** Apply <b>cipher</b> to CELL_PAYLOAD_SIZE bytes of <b>in</b>
+ * (in place).
+ *
+ * Note that we use the same operation for encrypting and for decrypting.
+ */
+static void
+relay_crypt_one_payload(crypto_cipher_t *cipher, uint8_t *in)
+{
+  crypto_cipher_crypt_inplace(cipher, (char*) in, CELL_PAYLOAD_SIZE);
+}
+
+/** Do the appropriate en/decryptions for <b>cell</b> arriving on
+ * <b>circ</b> in direction <b>cell_direction</b>.
+ *
+ * If cell_direction == CELL_DIRECTION_IN:
+ *   - If we're at the origin (we're the OP), for hops 1..N,
+ *     decrypt cell. If recognized, stop.
+ *   - Else (we're not the OP), encrypt one hop. Cell is not recognized.
+ *
+ * If cell_direction == CELL_DIRECTION_OUT:
+ *   - decrypt one hop. Check if recognized.
+ *
+ * If cell is recognized, set *recognized to 1, and set
+ * *layer_hint to the hop that recognized it.
+ *
+ * Return -1 to indicate that we should mark the circuit for close,
+ * else return 0.
+ */
+int
+relay_decrypt_cell(circuit_t *circ, cell_t *cell,
+                   cell_direction_t cell_direction,
+                   crypt_path_t **layer_hint, char *recognized)
+{
+  relay_header_t rh;
+
+  tor_assert(circ);
+  tor_assert(cell);
+  tor_assert(recognized);
+  tor_assert(cell_direction == CELL_DIRECTION_IN ||
+             cell_direction == CELL_DIRECTION_OUT);
+
+  if (cell_direction == CELL_DIRECTION_IN) {
+    if (CIRCUIT_IS_ORIGIN(circ)) { /* We're at the beginning of the circuit.
+                                    * We'll want to do layered decrypts. */
+      crypt_path_t *thishop, *cpath = TO_ORIGIN_CIRCUIT(circ)->cpath;
+      thishop = cpath;
+      if (thishop->state != CPATH_STATE_OPEN) {
+        log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
+               "Relay cell before first created cell? Closing.");
+        return -1;
+      }
+      do { /* Remember: cpath is in forward order, that is, first hop first. */
+        tor_assert(thishop);
+
+        /* decrypt one layer */
+        relay_crypt_one_payload(thishop->crypto.b_crypto, cell->payload);
+
+        relay_header_unpack(&rh, cell->payload);
+        if (rh.recognized == 0) {
+          /* it's possibly recognized. have to check digest to be sure. */
+          if (relay_digest_matches(thishop->crypto.b_digest, cell)) {
+            *recognized = 1;
+            *layer_hint = thishop;
+            return 0;
+          }
+        }
+
+        thishop = thishop->next;
+      } while (thishop != cpath && thishop->state == CPATH_STATE_OPEN);
+      log_fn(LOG_PROTOCOL_WARN, LD_OR,
+             "Incoming cell at client not recognized. Closing.");
+      return -1;
+    } else {
+      relay_crypto_t *crypto = &TO_OR_CIRCUIT(circ)->crypto;
+      /* We're in the middle. Encrypt one layer. */
+      relay_crypt_one_payload(crypto->b_crypto, cell->payload);
+    }
+  } else /* cell_direction == CELL_DIRECTION_OUT */ {
+    /* We're in the middle. Decrypt one layer. */
+    relay_crypto_t *crypto = &TO_OR_CIRCUIT(circ)->crypto;
+
+    relay_crypt_one_payload(crypto->f_crypto, cell->payload);
+
+    relay_header_unpack(&rh, cell->payload);
+    if (rh.recognized == 0) {
+      /* it's possibly recognized. have to check digest to be sure. */
+      if (relay_digest_matches(crypto->f_digest, cell)) {
+        *recognized = 1;
+        return 0;
+      }
+    }
+  }
+  return 0;
+}
+
+/**
+ * Encrypt a cell <b>cell</b> that we are creating, and sending outbound on
+ * <b>circ</b> until the hop corresponding to <b>layer_hint</b>.
+ *
+ * The integrity field and recognized field of <b>cell</b>'s relay headers
+ * must be set to zero.
+ */
+void
+relay_encrypt_cell_outbound(cell_t *cell,
+                            origin_circuit_t *circ,
+                            crypt_path_t *layer_hint)
+{
+  crypt_path_t *thishop; /* counter for repeated crypts */
+  relay_set_digest(layer_hint->crypto.f_digest, cell);
+
+  thishop = layer_hint;
+  /* moving from farthest to nearest hop */
+  do {
+    tor_assert(thishop);
+    log_debug(LD_OR,"encrypting a layer of the relay cell.");
+    relay_crypt_one_payload(thishop->crypto.f_crypto, cell->payload);
+
+    thishop = thishop->prev;
+  } while (thishop != circ->cpath->prev);
+}
+
+/**
+ * Encrypt a cell <b>cell</b> that we are creating, and sending on
+ * <b>circuit</b> to the origin.
+ *
+ * The integrity field and recognized field of <b>cell</b>'s relay headers
+ * must be set to zero.
+ */
+void
+relay_encrypt_cell_inbound(cell_t *cell,
+                           or_circuit_t *or_circ)
+{
+  relay_set_digest(or_circ->crypto.b_digest, cell);
+  /* encrypt one layer */
+  relay_crypt_one_payload(or_circ->crypto.b_crypto, cell->payload);
+}
+
+/**
+ * Release all storage held inside <b>crypto</b>, but do not free
+ * <b>crypto</b> itself: it lives inside another object.
+ */
+void
+relay_crypto_clear(relay_crypto_t *crypto)
+{
+  if (BUG(!crypto))
+    return;
+  crypto_cipher_free(crypto->f_crypto);
+  crypto_cipher_free(crypto->b_crypto);
+  crypto_digest_free(crypto->f_digest);
+  crypto_digest_free(crypto->b_digest);
+}
+
+/** Initialize <b>crypto</b> from the key material in key_data.
+ *
+ * If <b>is_hs_v3</b> is set, this cpath will be used for next gen hidden
+ * service circuits and <b>key_data</b> must be at least
+ * HS_NTOR_KEY_EXPANSION_KDF_OUT_LEN bytes in length.
+ *
+ * If <b>is_hs_v3</b> is not set, key_data must contain CPATH_KEY_MATERIAL_LEN
+ * bytes, which are used as follows:
+ *   - 20 to initialize f_digest
+ *   - 20 to initialize b_digest
+ *   - 16 to key f_crypto
+ *   - 16 to key b_crypto
+ *
+ * (If 'reverse' is true, then f_XX and b_XX are swapped.)
+ *
+ * Return 0 if init was successful, else -1 if it failed.
+ */
+int
+relay_crypto_init(relay_crypto_t *crypto,
+                  const char *key_data, size_t key_data_len,
+                  int reverse, int is_hs_v3)
+{
+  crypto_digest_t *tmp_digest;
+  crypto_cipher_t *tmp_crypto;
+  size_t digest_len = 0;
+  size_t cipher_key_len = 0;
+
+  tor_assert(crypto);
+  tor_assert(key_data);
+  tor_assert(!(crypto->f_crypto || crypto->b_crypto ||
+             crypto->f_digest || crypto->b_digest));
+
+  /* Basic key size validation */
+  if (is_hs_v3 && BUG(key_data_len != HS_NTOR_KEY_EXPANSION_KDF_OUT_LEN)) {
+    goto err;
+  } else if (!is_hs_v3 && BUG(key_data_len != CPATH_KEY_MATERIAL_LEN)) {
+    goto err;
+  }
+
+  /* If we are using this crypto for next gen onion services use SHA3-256,
+     otherwise use good ol' SHA1 */
+  if (is_hs_v3) {
+    digest_len = DIGEST256_LEN;
+    cipher_key_len = CIPHER256_KEY_LEN;
+    crypto->f_digest = crypto_digest256_new(DIGEST_SHA3_256);
+    crypto->b_digest = crypto_digest256_new(DIGEST_SHA3_256);
+  } else {
+    digest_len = DIGEST_LEN;
+    cipher_key_len = CIPHER_KEY_LEN;
+    crypto->f_digest = crypto_digest_new();
+    crypto->b_digest = crypto_digest_new();
+  }
+
+  tor_assert(digest_len != 0);
+  tor_assert(cipher_key_len != 0);
+  const int cipher_key_bits = (int) cipher_key_len * 8;
+
+  crypto_digest_add_bytes(crypto->f_digest, key_data, digest_len);
+  crypto_digest_add_bytes(crypto->b_digest, key_data+digest_len, digest_len);
+
+  crypto->f_crypto = crypto_cipher_new_with_bits(key_data+(2*digest_len),
+                                                cipher_key_bits);
+  if (!crypto->f_crypto) {
+    log_warn(LD_BUG,"Forward cipher initialization failed.");
+    goto err;
+  }
+
+  crypto->b_crypto = crypto_cipher_new_with_bits(
+                                        key_data+(2*digest_len)+cipher_key_len,
+                                        cipher_key_bits);
+  if (!crypto->b_crypto) {
+    log_warn(LD_BUG,"Backward cipher initialization failed.");
+    goto err;
+  }
+
+  if (reverse) {
+    tmp_digest = crypto->f_digest;
+    crypto->f_digest = crypto->b_digest;
+    crypto->b_digest = tmp_digest;
+    tmp_crypto = crypto->f_crypto;
+    crypto->f_crypto = crypto->b_crypto;
+    crypto->b_crypto = tmp_crypto;
+  }
+
+  return 0;
+ err:
+  relay_crypto_clear(crypto);
+  return -1;
+}
+
+/** Assert that <b>crypto</b> is valid and set. */
+void
+relay_crypto_assert_ok(const relay_crypto_t *crypto)
+{
+  tor_assert(crypto->f_crypto);
+  tor_assert(crypto->b_crypto);
+  tor_assert(crypto->f_digest);
+  tor_assert(crypto->b_digest);
+}
diff --git a/src/core/crypto/relay_crypto.h b/src/core/crypto/relay_crypto.h
new file mode 100644
index 0000000000..67da93344f
--- /dev/null
+++ b/src/core/crypto/relay_crypto.h
@@ -0,0 +1,31 @@
+/* Copyright (c) 2001 Matej Pfajfar.
+ * Copyright (c) 2001-2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2018, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file relay.h
+ * \brief Header file for relay.c.
+ **/
+
+#ifndef TOR_RELAY_CRYPTO_H
+#define TOR_RELAY_CRYPTO_H
+
+int relay_crypto_init(relay_crypto_t *crypto,
+                      const char *key_data, size_t key_data_len,
+                      int reverse, int is_hs_v3);
+
+int relay_decrypt_cell(circuit_t *circ, cell_t *cell,
+                       cell_direction_t cell_direction,
+                       crypt_path_t **layer_hint, char *recognized);
+void relay_encrypt_cell_outbound(cell_t *cell, origin_circuit_t *or_circ,
+                            crypt_path_t *layer_hint);
+void relay_encrypt_cell_inbound(cell_t *cell, or_circuit_t *or_circ);
+
+void relay_crypto_clear(relay_crypto_t *crypto);
+
+void relay_crypto_assert_ok(const relay_crypto_t *crypto);
+
+#endif /* !defined(TOR_RELAY_CRYPTO_H) */
+