diff options
Diffstat (limited to 'src/feature/hs/hs_circuitmap.c')
| -rw-r--r-- | src/feature/hs/hs_circuitmap.c | 585 |
1 files changed, 585 insertions, 0 deletions
diff --git a/src/feature/hs/hs_circuitmap.c b/src/feature/hs/hs_circuitmap.c new file mode 100644 index 0000000000..c4bf9fab43 --- /dev/null +++ b/src/feature/hs/hs_circuitmap.c @@ -0,0 +1,585 @@ +/* Copyright (c) 2016-2018, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/** + * \file hs_circuitmap.c + * + * \brief Hidden service circuitmap: A hash table that maps binary tokens to + * introduction and rendezvous circuits; it's used: + * (a) by relays acting as intro points and rendezvous points + * (b) by hidden services to find intro and rend circuits and + * (c) by HS clients to find rendezvous circuits. + **/ + +#define HS_CIRCUITMAP_PRIVATE + +#include "or/or.h" +#include "or/config.h" +#include "or/circuitlist.h" +#include "or/hs_circuitmap.h" + +#include "or/or_circuit_st.h" +#include "or/origin_circuit_st.h" + +/************************** HS circuitmap code *******************************/ + +/* This is the hidden service circuitmap. It's a hash table that maps + introduction and rendezvous tokens to specific circuits such that given a + token it's easy to find the corresponding circuit. */ +static struct hs_circuitmap_ht *the_hs_circuitmap = NULL; + +/* This is a helper function used by the hash table code (HT_). It returns 1 if + * two circuits have the same HS token. */ +static int +hs_circuits_have_same_token(const circuit_t *first_circuit, + const circuit_t *second_circuit) +{ + const hs_token_t *first_token; + const hs_token_t *second_token; + + tor_assert(first_circuit); + tor_assert(second_circuit); + + first_token = first_circuit->hs_token; + second_token = second_circuit->hs_token; + + /* Both circs must have a token */ + if (BUG(!first_token) || BUG(!second_token)) { + return 0; + } + + if (first_token->type != second_token->type) { + return 0; + } + + if (first_token->token_len != second_token->token_len) + return 0; + + return tor_memeq(first_token->token, + second_token->token, + first_token->token_len); +} + +/* This is a helper function for the hash table code (HT_). It hashes a circuit + * HS token into an unsigned int for use as a key by the hash table routines.*/ +static inline unsigned int +hs_circuit_hash_token(const circuit_t *circuit) +{ + tor_assert(circuit->hs_token); + + return (unsigned) siphash24g(circuit->hs_token->token, + circuit->hs_token->token_len); +} + +/* Register the circuitmap hash table */ +HT_PROTOTYPE(hs_circuitmap_ht, // The name of the hashtable struct + circuit_t, // The name of the element struct, + hs_circuitmap_node, // The name of HT_ENTRY member + hs_circuit_hash_token, hs_circuits_have_same_token) + +HT_GENERATE2(hs_circuitmap_ht, circuit_t, hs_circuitmap_node, + hs_circuit_hash_token, hs_circuits_have_same_token, + 0.6, tor_reallocarray, tor_free_) + +#ifdef TOR_UNIT_TESTS + +/* Return the global HS circuitmap. Used by unittests. */ +hs_circuitmap_ht * +get_hs_circuitmap(void) +{ + return the_hs_circuitmap; +} + +#endif /* defined(TOR_UNIT_TESTS) */ + +/****************** HS circuitmap utility functions **************************/ + +/** Return a new HS token of type <b>type</b> containing <b>token</b>. */ +static hs_token_t * +hs_token_new(hs_token_type_t type, size_t token_len, + const uint8_t *token) +{ + tor_assert(token); + + hs_token_t *hs_token = tor_malloc_zero(sizeof(hs_token_t)); + hs_token->type = type; + hs_token->token_len = token_len; + hs_token->token = tor_memdup(token, token_len); + + return hs_token; +} + +#define hs_token_free(val) \ + FREE_AND_NULL(hs_token_t, hs_token_free_, (val)) + +/** Free memory allocated by this <b>hs_token</b>. */ +static void +hs_token_free_(hs_token_t *hs_token) +{ + if (!hs_token) { + return; + } + + tor_free(hs_token->token); + tor_free(hs_token); +} + +/** Return the circuit from the circuitmap with token <b>search_token</b>. */ +static circuit_t * +get_circuit_with_token(hs_token_t *search_token) +{ + tor_assert(the_hs_circuitmap); + + /* We use a dummy circuit object for the hash table search routine. */ + circuit_t search_circ; + search_circ.hs_token = search_token; + return HT_FIND(hs_circuitmap_ht, the_hs_circuitmap, &search_circ); +} + +/* Helper function that registers <b>circ</b> with <b>token</b> on the HS + circuitmap. This function steals reference of <b>token</b>. */ +static void +hs_circuitmap_register_impl(circuit_t *circ, hs_token_t *token) +{ + tor_assert(circ); + tor_assert(token); + tor_assert(the_hs_circuitmap); + + /* If this circuit already has a token, clear it. */ + if (circ->hs_token) { + hs_circuitmap_remove_circuit(circ); + } + + /* Kill old circuits with the same token. We want new intro/rend circuits to + take precedence over old ones, so that HSes and clients and reestablish + killed circuits without changing the HS token. */ + { + circuit_t *found_circ; + found_circ = get_circuit_with_token(token); + if (found_circ) { + hs_circuitmap_remove_circuit(found_circ); + if (!found_circ->marked_for_close) { + circuit_mark_for_close(found_circ, END_CIRC_REASON_FINISHED); + } + } + } + + /* Register circuit and token to circuitmap. */ + circ->hs_token = token; + HT_INSERT(hs_circuitmap_ht, the_hs_circuitmap, circ); +} + +/** Helper function: Register <b>circ</b> of <b>type</b> on the HS + * circuitmap. Use the HS <b>token</b> as the key to the hash table. If + * <b>token</b> is not set, clear the circuit of any HS tokens. */ +static void +hs_circuitmap_register_circuit(circuit_t *circ, + hs_token_type_t type, size_t token_len, + const uint8_t *token) +{ + hs_token_t *hs_token = NULL; + + /* Create a new token and register it to the circuitmap */ + tor_assert(token); + hs_token = hs_token_new(type, token_len, token); + tor_assert(hs_token); + hs_circuitmap_register_impl(circ, hs_token); +} + +/* Helper function for hs_circuitmap_get_origin_circuit() and + * hs_circuitmap_get_or_circuit(). Because only circuit_t are indexed in the + * circuitmap, this function returns object type so the specialized functions + * using this helper can upcast it to the right type. + * + * Return NULL if not such circuit is found. */ +static circuit_t * +hs_circuitmap_get_circuit_impl(hs_token_type_t type, + size_t token_len, + const uint8_t *token, + uint8_t wanted_circ_purpose) +{ + circuit_t *found_circ = NULL; + + tor_assert(the_hs_circuitmap); + + /* Check the circuitmap if we have a circuit with this token */ + { + hs_token_t *search_hs_token = hs_token_new(type, token_len, token); + tor_assert(search_hs_token); + found_circ = get_circuit_with_token(search_hs_token); + hs_token_free(search_hs_token); + } + + /* Check that the circuit is useful to us */ + if (!found_circ || + found_circ->purpose != wanted_circ_purpose || + found_circ->marked_for_close) { + return NULL; + } + + return found_circ; +} + +/* Helper function: Query circuitmap for origin circuit with <b>token</b> of + * size <b>token_len</b> and <b>type</b>. Only returns a circuit with purpose + * equal to the <b>wanted_circ_purpose</b> parameter and if it is NOT marked + * for close. Return NULL if no such circuit is found. */ +static origin_circuit_t * +hs_circuitmap_get_origin_circuit(hs_token_type_t type, + size_t token_len, + const uint8_t *token, + uint8_t wanted_circ_purpose) +{ + circuit_t *circ; + tor_assert(token); + tor_assert(CIRCUIT_PURPOSE_IS_ORIGIN(wanted_circ_purpose)); + + circ = hs_circuitmap_get_circuit_impl(type, token_len, token, + wanted_circ_purpose); + if (!circ) { + return NULL; + } + + tor_assert(CIRCUIT_IS_ORIGIN(circ)); + return TO_ORIGIN_CIRCUIT(circ); +} + +/* Helper function: Query circuitmap for OR circuit with <b>token</b> of size + * <b>token_len</b> and <b>type</b>. Only returns a circuit with purpose equal + * to the <b>wanted_circ_purpose</b> parameter and if it is NOT marked for + * close. Return NULL if no such circuit is found. */ +static or_circuit_t * +hs_circuitmap_get_or_circuit(hs_token_type_t type, + size_t token_len, + const uint8_t *token, + uint8_t wanted_circ_purpose) +{ + circuit_t *circ; + tor_assert(token); + tor_assert(!CIRCUIT_PURPOSE_IS_ORIGIN(wanted_circ_purpose)); + + circ = hs_circuitmap_get_circuit_impl(type, token_len, token, + wanted_circ_purpose); + if (!circ) { + return NULL; + } + + tor_assert(CIRCUIT_IS_ORCIRC(circ)); + return TO_OR_CIRCUIT(circ); +} + +/************** Public circuitmap API ****************************************/ + +/**** Public relay-side getters: */ + +/* Public function: Return a v3 introduction circuit to this relay with + * <b>auth_key</b>. Return NULL if no such circuit is found in the + * circuitmap. */ +or_circuit_t * +hs_circuitmap_get_intro_circ_v3_relay_side( + const ed25519_public_key_t *auth_key) +{ + return hs_circuitmap_get_or_circuit(HS_TOKEN_INTRO_V3_RELAY_SIDE, + ED25519_PUBKEY_LEN, auth_key->pubkey, + CIRCUIT_PURPOSE_INTRO_POINT); +} + +/* Public function: Return v2 introduction circuit to this relay with + * <b>digest</b>. Return NULL if no such circuit is found in the circuitmap. */ +or_circuit_t * +hs_circuitmap_get_intro_circ_v2_relay_side(const uint8_t *digest) +{ + return hs_circuitmap_get_or_circuit(HS_TOKEN_INTRO_V2_RELAY_SIDE, + REND_TOKEN_LEN, digest, + CIRCUIT_PURPOSE_INTRO_POINT); +} + +/* Public function: Return rendezvous circuit to this relay with rendezvous + * <b>cookie</b>. Return NULL if no such circuit is found in the circuitmap. */ +or_circuit_t * +hs_circuitmap_get_rend_circ_relay_side(const uint8_t *cookie) +{ + return hs_circuitmap_get_or_circuit(HS_TOKEN_REND_RELAY_SIDE, + REND_TOKEN_LEN, cookie, + CIRCUIT_PURPOSE_REND_POINT_WAITING); +} + +/** Public relay-side setters: */ + +/* Public function: Register rendezvous circuit with key <b>cookie</b> to the + * circuitmap. */ +void +hs_circuitmap_register_rend_circ_relay_side(or_circuit_t *circ, + const uint8_t *cookie) +{ + hs_circuitmap_register_circuit(TO_CIRCUIT(circ), + HS_TOKEN_REND_RELAY_SIDE, + REND_TOKEN_LEN, cookie); +} +/* Public function: Register v2 intro circuit with key <b>digest</b> to the + * circuitmap. */ +void +hs_circuitmap_register_intro_circ_v2_relay_side(or_circuit_t *circ, + const uint8_t *digest) +{ + hs_circuitmap_register_circuit(TO_CIRCUIT(circ), + HS_TOKEN_INTRO_V2_RELAY_SIDE, + REND_TOKEN_LEN, digest); +} + +/* Public function: Register v3 intro circuit with key <b>auth_key</b> to the + * circuitmap. */ +void +hs_circuitmap_register_intro_circ_v3_relay_side(or_circuit_t *circ, + const ed25519_public_key_t *auth_key) +{ + hs_circuitmap_register_circuit(TO_CIRCUIT(circ), + HS_TOKEN_INTRO_V3_RELAY_SIDE, + ED25519_PUBKEY_LEN, auth_key->pubkey); +} + +/**** Public servide-side getters: */ + +/* Public function: Return v3 introduction circuit with <b>auth_key</b> + * originating from this hidden service. Return NULL if no such circuit is + * found in the circuitmap. */ +origin_circuit_t * +hs_circuitmap_get_intro_circ_v3_service_side(const + ed25519_public_key_t *auth_key) +{ + origin_circuit_t *circ = NULL; + + /* Check first for established intro circuits */ + circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_INTRO_V3_SERVICE_SIDE, + ED25519_PUBKEY_LEN, auth_key->pubkey, + CIRCUIT_PURPOSE_S_INTRO); + if (circ) { + return circ; + } + + /* ...if nothing found, check for pending intro circs */ + circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_INTRO_V3_SERVICE_SIDE, + ED25519_PUBKEY_LEN, auth_key->pubkey, + CIRCUIT_PURPOSE_S_ESTABLISH_INTRO); + + return circ; +} + +/* Public function: Return v2 introduction circuit originating from this hidden + * service with <b>digest</b>. Return NULL if no such circuit is found in the + * circuitmap. */ +origin_circuit_t * +hs_circuitmap_get_intro_circ_v2_service_side(const uint8_t *digest) +{ + origin_circuit_t *circ = NULL; + + /* Check first for established intro circuits */ + circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_INTRO_V2_SERVICE_SIDE, + REND_TOKEN_LEN, digest, + CIRCUIT_PURPOSE_S_INTRO); + if (circ) { + return circ; + } + + /* ...if nothing found, check for pending intro circs */ + circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_INTRO_V2_SERVICE_SIDE, + REND_TOKEN_LEN, digest, + CIRCUIT_PURPOSE_S_ESTABLISH_INTRO); + + return circ; +} + +/* Public function: Return rendezvous circuit originating from this hidden + * service with rendezvous <b>cookie</b>. Return NULL if no such circuit is + * found in the circuitmap. */ +origin_circuit_t * +hs_circuitmap_get_rend_circ_service_side(const uint8_t *cookie) +{ + origin_circuit_t *circ = NULL; + + /* Try to check if we have a connecting circuit. */ + circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_REND_SERVICE_SIDE, + REND_TOKEN_LEN, cookie, + CIRCUIT_PURPOSE_S_CONNECT_REND); + if (circ) { + return circ; + } + + /* Then try for connected circuit. */ + circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_REND_SERVICE_SIDE, + REND_TOKEN_LEN, cookie, + CIRCUIT_PURPOSE_S_REND_JOINED); + return circ; +} + +/* Public function: Return client-side rendezvous circuit with rendezvous + * <b>cookie</b>. It will look for circuits with the following purposes: + + * a) CIRCUIT_PURPOSE_C_REND_READY: Established rend circuit (received + * RENDEZVOUS_ESTABLISHED). Waiting for RENDEZVOUS2 from service, and for + * INTRODUCE_ACK from intro point. + * + * b) CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED: Established rend circuit and + * introduce circuit acked. Waiting for RENDEZVOUS2 from service. + * + * c) CIRCUIT_PURPOSE_C_REND_JOINED: Established rend circuit and received + * RENDEZVOUS2 from service. + * + * d) CIRCUIT_PURPOSE_C_ESTABLISH_REND: Rend circuit open but not yet + * established. + * + * Return NULL if no such circuit is found in the circuitmap. */ +origin_circuit_t * +hs_circuitmap_get_rend_circ_client_side(const uint8_t *cookie) +{ + origin_circuit_t *circ = NULL; + + circ = hs_circuitmap_get_established_rend_circ_client_side(cookie); + if (circ) { + return circ; + } + + circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_REND_CLIENT_SIDE, + REND_TOKEN_LEN, cookie, + CIRCUIT_PURPOSE_C_ESTABLISH_REND); + return circ; +} + +/* Public function: Return client-side established rendezvous circuit with + * rendezvous <b>cookie</b>. It will look for circuits with the following + * purposes: + * + * a) CIRCUIT_PURPOSE_C_REND_READY: Established rend circuit (received + * RENDEZVOUS_ESTABLISHED). Waiting for RENDEZVOUS2 from service, and for + * INTRODUCE_ACK from intro point. + * + * b) CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED: Established rend circuit and + * introduce circuit acked. Waiting for RENDEZVOUS2 from service. + * + * c) CIRCUIT_PURPOSE_C_REND_JOINED: Established rend circuit and received + * RENDEZVOUS2 from service. + * + * Return NULL if no such circuit is found in the circuitmap. */ +origin_circuit_t * +hs_circuitmap_get_established_rend_circ_client_side(const uint8_t *cookie) +{ + origin_circuit_t *circ = NULL; + + circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_REND_CLIENT_SIDE, + REND_TOKEN_LEN, cookie, + CIRCUIT_PURPOSE_C_REND_READY); + if (circ) { + return circ; + } + + circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_REND_CLIENT_SIDE, + REND_TOKEN_LEN, cookie, + CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED); + if (circ) { + return circ; + } + + circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_REND_CLIENT_SIDE, + REND_TOKEN_LEN, cookie, + CIRCUIT_PURPOSE_C_REND_JOINED); + return circ; +} + +/**** Public servide-side setters: */ + +/* Public function: Register v2 intro circuit with key <b>digest</b> to the + * circuitmap. */ +void +hs_circuitmap_register_intro_circ_v2_service_side(origin_circuit_t *circ, + const uint8_t *digest) +{ + hs_circuitmap_register_circuit(TO_CIRCUIT(circ), + HS_TOKEN_INTRO_V2_SERVICE_SIDE, + REND_TOKEN_LEN, digest); +} + +/* Public function: Register v3 intro circuit with key <b>auth_key</b> to the + * circuitmap. */ +void +hs_circuitmap_register_intro_circ_v3_service_side(origin_circuit_t *circ, + const ed25519_public_key_t *auth_key) +{ + hs_circuitmap_register_circuit(TO_CIRCUIT(circ), + HS_TOKEN_INTRO_V3_SERVICE_SIDE, + ED25519_PUBKEY_LEN, auth_key->pubkey); +} + +/* Public function: Register rendezvous circuit with key <b>cookie</b> to the + * circuitmap. */ +void +hs_circuitmap_register_rend_circ_service_side(origin_circuit_t *circ, + const uint8_t *cookie) +{ + hs_circuitmap_register_circuit(TO_CIRCUIT(circ), + HS_TOKEN_REND_SERVICE_SIDE, + REND_TOKEN_LEN, cookie); +} + +/* Public function: Register rendezvous circuit with key <b>cookie</b> to the + * client-side circuitmap. */ +void +hs_circuitmap_register_rend_circ_client_side(origin_circuit_t *or_circ, + const uint8_t *cookie) +{ + circuit_t *circ = TO_CIRCUIT(or_circ); + { /* Basic circ purpose sanity checking */ + tor_assert_nonfatal(circ->purpose == CIRCUIT_PURPOSE_C_ESTABLISH_REND); + } + + hs_circuitmap_register_circuit(circ, HS_TOKEN_REND_CLIENT_SIDE, + REND_TOKEN_LEN, cookie); +} + +/**** Misc public functions: */ + +/** Public function: Remove this circuit from the HS circuitmap. Clear its HS + * token, and remove it from the hashtable. */ +void +hs_circuitmap_remove_circuit(circuit_t *circ) +{ + tor_assert(the_hs_circuitmap); + + if (!circ || !circ->hs_token) { + return; + } + + /* Remove circ from circuitmap */ + circuit_t *tmp; + tmp = HT_REMOVE(hs_circuitmap_ht, the_hs_circuitmap, circ); + /* ... and ensure the removal was successful. */ + if (tmp) { + tor_assert(tmp == circ); + } else { + log_warn(LD_BUG, "Could not find circuit (%u) in circuitmap.", + circ->n_circ_id); + } + + /* Clear token from circ */ + hs_token_free(circ->hs_token); + circ->hs_token = NULL; +} + +/* Public function: Initialize the global HS circuitmap. */ +void +hs_circuitmap_init(void) +{ + tor_assert(!the_hs_circuitmap); + + the_hs_circuitmap = tor_malloc_zero(sizeof(struct hs_circuitmap_ht)); + HT_INIT(hs_circuitmap_ht, the_hs_circuitmap); +} + +/* Public function: Free all memory allocated by the global HS circuitmap. */ +void +hs_circuitmap_free_all(void) +{ + if (the_hs_circuitmap) { + HT_CLEAR(hs_circuitmap_ht, the_hs_circuitmap); + tor_free(the_hs_circuitmap); + } +} |