/* Copyright (c) 2001 Matej Pfajfar. * Copyright (c) 2001-2004, Roger Dingledine. * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson. * Copyright (c) 2007-2017, 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. * *
* * This module also handles: * * * [*] The CREATE_FAST handshake is weaker than described here; see * onion_fast.c for more information. **/ #include "or.h" #include "circuitbuild.h" #include "circuitlist.h" #include "config.h" #include "cpuworker.h" #include "networkstatus.h" #include "onion.h" #include "onion_fast.h" #include "onion_ntor.h" #include "onion_tap.h" #include "relay.h" #include "rephist.h" #include "router.h" // trunnel #include "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 * type. */ 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 circ 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 handshake_type-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 victim 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 keys. */ 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 state, 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 type * (one of ONION_HANDSHAKE_TYPE_*): generate the initial "onion skin" in * onion_skin_out, and store any state information in state_out. * 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; } /** Perform the second (server-side) step of a circuit-creation handshake of * type type, responding to the client request in onion_skin * using the keys in keys. On success, write our response into * reply_out, generate keys_out_len bytes worth of key material * in keys_out_len, a hidden service nonce to rend_nonce_out, * 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+DH_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; uint8_t *keys_tmp = tor_malloc(keys_out_len + DIGEST_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) { tor_free(keys_tmp); 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, keys_tmp_len); tor_free(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 type, using our state in handshake_state and the * server's response in reply. On success, generate keys_out_len * bytes worth of key material in keys_out_len, set * rend_authenticator_out 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+DH_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 cell appears valid, -1 otherwise. If * unknown_ok 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 p, which could be up to * p_len bytes long, and use it to fill the fields of * cell_out. 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 cell_in into * cell_out. 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 cell 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 cell_in into * cell_out. 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 cell 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 command) from the * payload_length bytes of payload into cell_out. 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 cell 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 command) from the * payload_length bytes of payload into cell_out. 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 cell_out with a correctly formatted version of the * CREATE{,_FAST,2} cell in cell_in. Return 0 on success, -1 on * failure. This is a cell we didn't originate if relayed 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 cell_out with a correctly formatted version of the * CREATED{,_FAST,2} cell in cell_in. 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 cell_in, storing its relay payload in * payload_out, the number of bytes used in *len_out, and the * relay command in *command_out. The payload_out 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 cell_in, storing its relay payload * in payload_out, the number of bytes used in *len_out, and the * relay command in *command_out. The payload_out 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; }