commit 98ef3e82e48c2d57c09d5f551b72e7d6bfe5347a Author: Nick Mathewson <nickm@torproject.org> Date: Thu Sep 20 13:55:02 2018 -0400 Move the non-crypto parts of onion.c out of src/core/crypto The parts for handling cell formats should be in src/core/or. The parts for handling onionskin queues should be in src/core/or. Only the crypto wrapper belongs in src/core/crypto. --- src/core/crypto/onion_crypto.c | 311 +++++++++++++++++ src/core/crypto/onion_crypto.h | 47 +++ src/core/include.am | 8 +- src/core/mainloop/cpuworker.c | 4 +- src/core/mainloop/main.c | 3 +- src/core/or/circuitbuild.c | 3 +- src/core/or/circuitlist.c | 3 +- src/core/or/command.c | 4 +- src/core/{crypto => or}/onion.c | 636 +--------------------------------- src/core/{crypto => or}/onion.h | 38 -- src/core/or/relay.c | 2 +- src/feature/relay/onion_queue.c | 361 +++++++++++++++++++ src/feature/relay/onion_queue.h | 23 ++ src/test/test.c | 4 +- src/test/test_cell_formats.c | 2 +- src/test/test_workqueue.c | 2 +- src/tools/tor-print-ed-signing-cert.c | 2 +- 17 files changed, 770 insertions(+), 683 deletions(-) diff --git a/src/core/crypto/onion_crypto.c b/src/core/crypto/onion_crypto.c new file mode 100644 index 000000000..4978e0d46 --- /dev/null +++ b/src/core/crypto/onion_crypto.c @@ -0,0 +1,311 @@ +/* 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_crypto.c + * \brief Functions to handle different kinds of circuit extension crypto. + * + * 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. + **/ + +#include "core/or/or.h" +#include "core/or/circuitbuild.h" +#include "core/crypto/onion_crypto.h" +#include "core/crypto/onion_fast.h" +#include "core/crypto/onion_ntor.h" +#include "core/crypto/onion_tap.h" +#include "feature/relay/router.h" +#include "lib/crypt_ops/crypto_dh.h" +#include "lib/crypt_ops/crypto_util.h" + +#include "core/or/crypt_path_st.h" +#include "core/or/extend_info_st.h" + +/** 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; + } +} diff --git a/src/core/crypto/onion_crypto.h b/src/core/crypto/onion_crypto.h new file mode 100644 index 000000000..ed410ef25 --- /dev/null +++ b/src/core/crypto/onion_crypto.h @@ -0,0 +1,47 @@ +/* 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_crypto.h + * \brief Header file for onion_crypto.c. + **/ + +#ifndef TOR_ONION_CRYPTO_H +#define TOR_ONION_CRYPTO_H + +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; + +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); + +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)) + +#endif diff --git a/src/core/include.am b/src/core/include.am index 04e27b00d..6246db968 100644 --- a/src/core/include.am +++ b/src/core/include.am @@ -11,7 +11,7 @@ LIBTOR_APP_A_SOURCES = \ src/app/config/confparse.c \ src/app/config/statefile.c \ src/core/crypto/hs_ntor.c \ - src/core/crypto/onion.c \ + src/core/crypto/onion_crypto.c \ src/core/crypto/onion_fast.c \ src/core/crypto/onion_ntor.c \ src/core/crypto/onion_tap.c \ @@ -34,6 +34,7 @@ LIBTOR_APP_A_SOURCES = \ src/core/or/connection_edge.c \ src/core/or/connection_or.c \ src/core/or/dos.c \ + src/core/or/onion.c \ src/core/or/policies.c \ src/core/or/protover.c \ src/core/or/reasons.c \ @@ -95,6 +96,7 @@ LIBTOR_APP_A_SOURCES = \ src/feature/nodelist/torcert.c \ src/feature/relay/dns.c \ src/feature/relay/ext_orport.c \ + src/feature/relay/onion_queue.c \ src/feature/relay/router.c \ src/feature/relay/routerkeys.c \ src/feature/rend/rendcache.c \ @@ -164,7 +166,7 @@ noinst_HEADERS += \ src/app/config/statefile.h \ src/app/main/ntmain.h \ src/core/crypto/hs_ntor.h \ - src/core/crypto/onion.h \ + src/core/crypto/onion_crypto.h \ src/core/crypto/onion_fast.h \ src/core/crypto/onion_ntor.h \ src/core/crypto/onion_tap.h \ @@ -202,6 +204,7 @@ noinst_HEADERS += \ src/core/or/entry_port_cfg_st.h \ src/core/or/extend_info_st.h \ src/core/or/listener_connection_st.h \ + src/core/or/onion.h \ src/core/or/or.h \ src/core/or/or_circuit_st.h \ src/core/or/or_connection_st.h \ @@ -307,6 +310,7 @@ noinst_HEADERS += \ src/feature/relay/dns.h \ src/feature/relay/dns_structs.h \ src/feature/relay/ext_orport.h \ + src/feature/relay/onion_queue.h \ src/feature/relay/router.h \ src/feature/relay/routerkeys.h \ src/feature/rend/rend_authorized_client_st.h \ diff --git a/src/core/mainloop/cpuworker.c b/src/core/mainloop/cpuworker.c index a372db3f1..232d7efa9 100644 --- a/src/core/mainloop/cpuworker.c +++ b/src/core/mainloop/cpuworker.c @@ -27,10 +27,12 @@ #include "lib/crypt_ops/crypto_rand.h" #include "lib/crypt_ops/crypto_util.h" #include "core/mainloop/main.h" -#include "core/crypto/onion.h" +#include "core/or/onion.h" +#include "feature/relay/onion_queue.h" #include "feature/stats/rephist.h" #include "feature/relay/router.h" #include "lib/evloop/workqueue.h" +#include "core/crypto/onion_crypto.h" #include "core/or/or_circuit_st.h" #include "lib/intmath/weakrng.h" diff --git a/src/core/mainloop/main.c b/src/core/mainloop/main.c index 2a90192c9..5beccc0a6 100644 --- a/src/core/mainloop/main.c +++ b/src/core/mainloop/main.c @@ -92,7 +92,8 @@ #include "feature/nodelist/networkstatus.h" #include "feature/nodelist/nodelist.h" #include "app/main/ntmain.h" -#include "core/crypto/onion.h" +#include "core/or/onion.h" +#include "feature/relay/onion_queue.h" #include "core/mainloop/periodic.h" #include "core/or/policies.h" #include "core/or/protover.h" diff --git a/src/core/or/circuitbuild.c b/src/core/or/circuitbuild.c index ea23c1dfd..99b2fb19a 100644 --- a/src/core/or/circuitbuild.c +++ b/src/core/or/circuitbuild.c @@ -51,7 +51,8 @@ #include "feature/nodelist/microdesc.h" #include "feature/nodelist/networkstatus.h" #include "feature/nodelist/nodelist.h" -#include "core/crypto/onion.h" +#include "core/or/onion.h" +#include "core/crypto/onion_crypto.h" #include "core/crypto/onion_tap.h" #include "core/crypto/onion_fast.h" #include "core/or/policies.h" diff --git a/src/core/or/circuitlist.c b/src/core/or/circuitlist.c index 637feec8d..aead28ded 100644 --- a/src/core/or/circuitlist.c +++ b/src/core/or/circuitlist.c @@ -77,7 +77,8 @@ #include "feature/hs/hs_ident.h" #include "feature/nodelist/networkstatus.h" #include "feature/nodelist/nodelist.h" -#include "core/crypto/onion.h" +#include "feature/relay/onion_queue.h" +#include "core/crypto/onion_crypto.h" #include "core/crypto/onion_fast.h" #include "core/or/policies.h" #include "core/or/relay.h" diff --git a/src/core/or/command.c b/src/core/or/command.c index ebddc4a35..f93eb8d85 100644 --- a/src/core/or/command.c +++ b/src/core/or/command.c @@ -50,7 +50,8 @@ #include "core/or/dos.h" #include "feature/hibernate/hibernate.h" #include "feature/nodelist/nodelist.h" -#include "core/crypto/onion.h" +#include "core/or/onion.h" +#include "core/crypto/onion_crypto.h" #include "feature/stats/rephist.h" #include "core/or/relay.h" #include "feature/relay/router.h" @@ -699,4 +700,3 @@ command_setup_listener(channel_listener_t *listener) channel_listener_set_listener_fn(listener, command_handle_incoming_channel); } - diff --git a/src/core/crypto/onion.c b/src/core/or/onion.c similarity index 50% rename from src/core/crypto/onion.c rename to src/core/or/onion.c index e71bfc1fd..5c2944194 100644 --- a/src/core/crypto/onion.c +++ b/src/core/or/onion.c @@ -6,7 +6,7 @@ /** * \file onion.c - * \brief Functions to queue create cells, wrap the various onionskin types, + * \brief Functions to queue create cells, * and parse and create the CREATE cell and its allies. * * This module has a few functions, all related to the CREATE/CREATED @@ -14,27 +14,6 @@ * 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. * @@ -57,628 +36,23 @@ * <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 "core/or/or.h" -#include "core/or/circuitbuild.h" -#include "core/or/circuitlist.h" + #include "app/config/config.h" -#include "core/mainloop/cpuworker.h" -#include "lib/crypt_ops/crypto_util.h" -#include "lib/crypt_ops/crypto_dh.h" -#include "feature/nodelist/networkstatus.h" -#include "core/crypto/onion.h" +#include "core/crypto/onion_crypto.h" #include "core/crypto/onion_fast.h" #include "core/crypto/onion_ntor.h" #include "core/crypto/onion_tap.h" -#include "core/or/relay.h" -#include "feature/stats/rephist.h" -#include "feature/relay/router.h" +#include "core/or/onion.h" +#include "feature/nodelist/networkstatus.h" #include "core/or/cell_st.h" -#include "core/or/extend_info_st.h" -#include "core/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. */ diff --git a/src/core/crypto/onion.h b/src/core/or/onion.h similarity index 68% rename from src/core/crypto/onion.h rename to src/core/or/onion.h index ff70f299d..2049fdf41 100644 --- a/src/core/crypto/onion.h +++ b/src/core/or/onion.h @@ -17,47 +17,9 @@ 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} */ diff --git a/src/core/or/relay.c b/src/core/or/relay.c index 2c77abbee..119b677a6 100644 --- a/src/core/or/relay.c +++ b/src/core/or/relay.c @@ -70,7 +70,7 @@ #include "core/mainloop/main.h" #include "feature/nodelist/networkstatus.h" #include "feature/nodelist/nodelist.h" -#include "core/crypto/onion.h" +#include "core/or/onion.h" #include "core/or/policies.h" #include "core/or/reasons.h" #include "core/or/relay.h" diff --git a/src/feature/relay/onion_queue.c b/src/feature/relay/onion_queue.c new file mode 100644 index 000000000..13142bb05 --- /dev/null +++ b/src/feature/relay/onion_queue.c @@ -0,0 +1,361 @@ +/* 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_queue.c + * \brief Functions to queue create cells for processing. + * + * 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. + * </ul> + **/ + +#include "core/or/or.h" + +#include "feature/relay/onion_queue.h" + +#include "app/config/config.h" +#include "core/mainloop/cpuworker.h" +#include "core/or/circuitlist.h" +#include "core/or/onion.h" +#include "feature/nodelist/networkstatus.h" + +#include "core/or/or_circuit_st.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)); +} diff --git a/src/feature/relay/onion_queue.h b/src/feature/relay/onion_queue.h new file mode 100644 index 000000000..a71f497e3 --- /dev/null +++ b/src/feature/relay/onion_queue.h @@ -0,0 +1,23 @@ +/* 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_queue.h + * \brief Header file for onion_queue.c. + **/ + +#ifndef TOR_ONION_QUEUE_H +#define TOR_ONION_QUEUE_H + +struct create_cell_t; + +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); + +#endif diff --git a/src/test/test.c b/src/test/test.c index dc8e3bede..e3d1b1c67 100644 --- a/src/test/test.c +++ b/src/test/test.c @@ -11,7 +11,6 @@ #include "orconfig.h" #include "lib/crypt_ops/crypto_dh.h" #include "lib/crypt_ops/crypto_rand.h" - #include "app/config/or_state_st.h" #include <stdio.h> @@ -49,7 +48,7 @@ #include "test/test.h" #include "core/mainloop/main.h" #include "lib/memarea/memarea.h" -#include "core/crypto/onion.h" +#include "core/or/onion.h" #include "core/crypto/onion_ntor.h" #include "core/crypto/onion_fast.h" #include "core/crypto/onion_tap.h" @@ -64,6 +63,7 @@ #include "feature/rend/rend_encoded_v2_service_descriptor_st.h" #include "feature/rend/rend_intro_point_st.h" #include "feature/rend/rend_service_descriptor_st.h" +#include "feature/relay/onion_queue.h" /** Run unit tests for the onion handshake code. */ static void diff --git a/src/test/test_cell_formats.c b/src/test/test_cell_formats.c index 2753c4219..daf0296e2 100644 --- a/src/test/test_cell_formats.c +++ b/src/test/test_cell_formats.c @@ -13,7 +13,7 @@ #include "core/or/connection_or.h" #include "app/config/config.h" #include "lib/crypt_ops/crypto_rand.h" -#include "core/crypto/onion.h" +#include "core/or/onion.h" #include "core/crypto/onion_tap.h" #include "core/crypto/onion_fast.h" #include "core/crypto/onion_ntor.h" diff --git a/src/test/test_workqueue.c b/src/test/test_workqueue.c index 9d48d9277..28fbd6fb9 100644 --- a/src/test/test_workqueue.c +++ b/src/test/test_workqueue.c @@ -5,7 +5,7 @@ #include "core/or/or.h" #include "lib/thread/threads.h" -#include "core/crypto/onion.h" +#include "core/or/onion.h" #include "lib/evloop/workqueue.h" #include "lib/crypt_ops/crypto_curve25519.h" #include "lib/crypt_ops/crypto_rand.h" diff --git a/src/tools/tor-print-ed-signing-cert.c b/src/tools/tor-print-ed-signing-cert.c index 0f64059d8..9bb4db0a6 100644 --- a/src/tools/tor-print-ed-signing-cert.c +++ b/src/tools/tor-print-ed-signing-cert.c @@ -6,7 +6,7 @@ #include <string.h> #include <time.h> -#include "ed25519_cert.h" +#include "trunnel/ed25519_cert.h" #include "lib/cc/torint.h" /* TOR_PRIdSZ */ #include "lib/crypt_ops/crypto_format.h" #include "lib/malloc/malloc.h"