commit 2b9abbef2e5d0e58e5a15b7cf8cd03965aa70117 Author: George Kadianakis desnacked@riseup.net Date: Mon Sep 5 18:48:15 2016 +0300
prop224 prepwork: Introduce HS circuitmap subsystem.
The HS circuitmap is 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. It supports rend circuits and v2/v3 intro circuits.
It will be used by the prop224 ESTABLISH_INTRO code to register and lookup v3 introduction circuits.
The next commit after this removes the old code and fixes the unittests. Please consult both commits while reviewing functionality differences between the old and new code. Let me know if you want this rebased differently :)
WRT architectural differences, this commit removes the rendinfo pointer from or_circuit_t. It then adds an hs_token_t pointer and a hashtable node for the HS circuitmap. IIUC, this adds another pointer to the weight of or_circuit_t. Let me know if you don't like this, or if you have suggestions on improving it. --- src/or/hs_circuitmap.c | 328 +++++++++++++++++++++++++++++++++++++++++++++++++ src/or/hs_circuitmap.h | 69 +++++++++++ src/or/or.h | 8 +- 3 files changed, 404 insertions(+), 1 deletion(-)
diff --git a/src/or/hs_circuitmap.c b/src/or/hs_circuitmap.c new file mode 100644 index 0000000..790c4d3 --- /dev/null +++ b/src/or/hs_circuitmap.c @@ -0,0 +1,328 @@ +/* Copyright (c) 2016, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/** + * \file hs_circuitmap.c + * + * \brief Manage the hidden service circuitmap: A hash table that maps binary + * tokens to introduction and rendezvous circuits. + **/ + +#define HS_CIRCUITMAP_PRIVATE + +#include "or.h" +#include "config.h" +#include "circuitlist.h" +#include "hs_circuitmap.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 or_circuit_t *first_circuit, + const or_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 or_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 + or_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, or_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 + +/****************** 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; +} + +/** 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 or_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. */ + or_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(or_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. */ + { + or_circuit_t *found_circ; + found_circ = get_circuit_with_token(token); + if (found_circ) { + hs_circuitmap_remove_circuit(found_circ); + if (!found_circ->base_.marked_for_close) { + circuit_mark_for_close(TO_CIRCUIT(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(or_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); +} + +/* Query circuitmap for circuit with <b>token</b> of size <b>token_len</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_circuit(hs_token_type_t type, + size_t token_len, + const uint8_t *token, + uint8_t wanted_circ_purpose) +{ + or_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->base_.purpose != wanted_circ_purpose || + found_circ->base_.marked_for_close) { + return NULL; + } + + return found_circ; +} + +/************** Public circuitmap API ****************************************/ + +/* Public function: Return v3 introduction circuit 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(const ed25519_public_key_t *auth_key) +{ + tor_assert(auth_key); + + return hs_circuitmap_get_circuit(HS_TOKEN_INTRO_V3, + ED25519_PUBKEY_LEN, auth_key->pubkey, + CIRCUIT_PURPOSE_INTRO_POINT); +} + +/* Public function: Return v2 introduction circuit with <b>digest</b>. Return + * NULL if no such circuit is found in the circuitmap. */ +or_circuit_t * +hs_circuitmap_get_intro_circ_v2(const uint8_t *digest) +{ + tor_assert(digest); + + return hs_circuitmap_get_circuit(HS_TOKEN_INTRO_V2, + REND_TOKEN_LEN, digest, + CIRCUIT_PURPOSE_INTRO_POINT); +} + +/* Public function: Return rendezvous circuit with rendezvous + * <b>cookie</b>. Return NULL if no such circuit is found in the circuitmap. */ +or_circuit_t * +hs_circuitmap_get_rend_circ(const uint8_t *cookie) +{ + tor_assert(cookie); + + return hs_circuitmap_get_circuit(HS_TOKEN_REND, + REND_TOKEN_LEN, cookie, + CIRCUIT_PURPOSE_REND_POINT_WAITING); +} + +/* Public function: Register rendezvous circuit with key <b>cookie</b> to the + * circuitmap. */ +void +hs_circuitmap_register_rend_circ(or_circuit_t *circ, const uint8_t *cookie) +{ + hs_circuitmap_register_circuit(circ, + HS_TOKEN_REND, + 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(or_circuit_t *circ, const uint8_t *digest) +{ + hs_circuitmap_register_circuit(circ, + HS_TOKEN_INTRO_V2, + 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(or_circuit_t *circ, + const ed25519_public_key_t *auth_key) +{ + hs_circuitmap_register_circuit(circ, + HS_TOKEN_INTRO_V3, + ED25519_PUBKEY_LEN, auth_key->pubkey); +} + +/** Remove this circuit from the HS circuitmap. Clear its HS token, and remove + * it from the hashtable. */ +void +hs_circuitmap_remove_circuit(or_circuit_t *circ) +{ + tor_assert(the_hs_circuitmap); + + if (!circ || !circ->hs_token) { + return; + } + + /* Remove circ from circuitmap */ + or_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->p_circ_id); + } + + /* Clear token from circ */ + hs_token_free(circ->hs_token); + circ->hs_token = NULL; +} + +/* 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); +} + +/* Free all memory allocated by the global HS circuitmap. */ +void +hs_circuitmap_free_all(void) +{ + tor_assert(the_hs_circuitmap); + + HT_CLEAR(hs_circuitmap_ht, the_hs_circuitmap); + tor_free(the_hs_circuitmap); +} + diff --git a/src/or/hs_circuitmap.h b/src/or/hs_circuitmap.h new file mode 100644 index 0000000..a2be97c --- /dev/null +++ b/src/or/hs_circuitmap.h @@ -0,0 +1,69 @@ +/* Copyright (c) 2016, The Tor Project, Inc. */ +/* See LICENSE for licensing information */ + +/** + * \file hs_circuitmap.h + * \brief Header file for hs_circuitmap.c. + **/ + +#ifndef TOR_HS_CIRCUITMAP_H +#define TOR_HS_CIRCUITMAP_H + +typedef HT_HEAD(hs_circuitmap_ht, or_circuit_t) hs_circuitmap_ht; + +typedef struct hs_token_s hs_token_t; +typedef struct or_circuit_t or_circuit_t; + +/** Public HS circuitmap API: */ + +or_circuit_t *hs_circuitmap_get_rend_circ(const uint8_t *cookie); +or_circuit_t * +hs_circuitmap_get_intro_circ_v3(const ed25519_public_key_t *auth_key); +or_circuit_t *hs_circuitmap_get_intro_circ_v2(const uint8_t *digest); + +void hs_circuitmap_register_rend_circ(or_circuit_t *circ, + const uint8_t *cookie); +void hs_circuitmap_register_intro_circ_v2(or_circuit_t *circ, + const uint8_t *digest); +void hs_circuitmap_register_intro_circ_v3(or_circuit_t *circ, + const ed25519_public_key_t *auth_key); + +void hs_circuitmap_remove_circuit(or_circuit_t *circ); + +void hs_circuitmap_init(void); +void hs_circuitmap_free_all(void); + +#ifdef HS_CIRCUITMAP_PRIVATE + +/** Represents the type of HS token. */ +typedef enum { + /** A rendezvous cookie (128bit)*/ + HS_TOKEN_REND, + /** A v2 introduction point pubkey (160bit) */ + HS_TOKEN_INTRO_V2, + /** A v3 introduction point pubkey (256bit) */ + HS_TOKEN_INTRO_V3, +} hs_token_type_t; + +/** Represents a token used in the HS protocol. Each such token maps to a + * specific introduction or rendezvous circuit. */ +struct hs_token_s { + /* Type of HS token. */ + hs_token_type_t type; + + /* The size of the token (depends on the type). */ + size_t token_len; + + /* The token itself. Memory allocated at runtime. */ + uint8_t *token; +}; + +#endif /* HS_CIRCUITMAP_PRIVATE */ + +#ifdef TOR_UNIT_TESTS + +hs_circuitmap_ht *get_hs_circuitmap(void); + +#endif /* TOR_UNIT_TESTS */ + +#endif /* TOR_HS_CIRCUITMAP_H */ diff --git a/src/or/or.h b/src/or/or.h index eb94f63..9581c6d 100644 --- a/src/or/or.h +++ b/src/or/or.h @@ -80,6 +80,7 @@ #include "crypto_ed25519.h" #include "tor_queue.h" #include "util_format.h" +#include "hs_circuitmap.h"
/* These signals are defined to help handle_control_signal work. */ @@ -3352,7 +3353,12 @@ typedef struct or_circuit_t { * is not marked for close. */ struct or_circuit_t *rend_splice;
- struct or_circuit_rendinfo_s *rendinfo; + /** If set, points to an HS token that this circuit might be carrying. + * Used by the HS circuitmap. */ + hs_token_t *hs_token; + /** Hashtable node: used to look up the circuit by its HS token using the HS + circuitmap. */ + HT_ENTRY(or_circuit_t) hs_circuitmap_node;
/** Stores KH for the handshake. */ char rend_circ_nonce[DIGEST_LEN];/* KH in tor-spec.txt */