tor  0.4.2.1-alpha-dev
hs_circuitmap.c
Go to the documentation of this file.
1 /* Copyright (c) 2016-2019, The Tor Project, Inc. */
2 /* See LICENSE for licensing information */
3 
14 #define HS_CIRCUITMAP_PRIVATE
15 
16 #include "core/or/or.h"
17 #include "app/config/config.h"
18 #include "core/or/circuitlist.h"
20 
21 #include "core/or/or_circuit_st.h"
22 #include "core/or/origin_circuit_st.h"
23 
24 /************************** HS circuitmap code *******************************/
25 
26 /* This is the hidden service circuitmap. It's a hash table that maps
27  introduction and rendezvous tokens to specific circuits such that given a
28  token it's easy to find the corresponding circuit. */
29 static struct hs_circuitmap_ht *the_hs_circuitmap = NULL;
30 
31 /* This is a helper function used by the hash table code (HT_). It returns 1 if
32  * two circuits have the same HS token. */
33 static int
34 hs_circuits_have_same_token(const circuit_t *first_circuit,
35  const circuit_t *second_circuit)
36 {
37  const hs_token_t *first_token;
38  const hs_token_t *second_token;
39 
40  tor_assert(first_circuit);
41  tor_assert(second_circuit);
42 
43  first_token = first_circuit->hs_token;
44  second_token = second_circuit->hs_token;
45 
46  /* Both circs must have a token */
47  if (BUG(!first_token) || BUG(!second_token)) {
48  return 0;
49  }
50 
51  if (first_token->type != second_token->type) {
52  return 0;
53  }
54 
55  if (first_token->token_len != second_token->token_len)
56  return 0;
57 
58  return tor_memeq(first_token->token,
59  second_token->token,
60  first_token->token_len);
61 }
62 
63 /* This is a helper function for the hash table code (HT_). It hashes a circuit
64  * HS token into an unsigned int for use as a key by the hash table routines.*/
65 static inline unsigned int
66 hs_circuit_hash_token(const circuit_t *circuit)
67 {
68  tor_assert(circuit->hs_token);
69 
70  return (unsigned) siphash24g(circuit->hs_token->token,
71  circuit->hs_token->token_len);
72 }
73 
74 /* Register the circuitmap hash table */
75 HT_PROTOTYPE(hs_circuitmap_ht, // The name of the hashtable struct
76  circuit_t, // The name of the element struct,
77  hs_circuitmap_node, // The name of HT_ENTRY member
78  hs_circuit_hash_token, hs_circuits_have_same_token)
79 
80 HT_GENERATE2(hs_circuitmap_ht, circuit_t, hs_circuitmap_node,
81  hs_circuit_hash_token, hs_circuits_have_same_token,
82  0.6, tor_reallocarray, tor_free_)
83 
84 #ifdef TOR_UNIT_TESTS
85 
86 /* Return the global HS circuitmap. Used by unittests. */
87 hs_circuitmap_ht *
88 get_hs_circuitmap(void)
89 {
90  return the_hs_circuitmap;
91 }
92 
93 #endif /* defined(TOR_UNIT_TESTS) */
94 
95 /****************** HS circuitmap utility functions **************************/
96 
98 static hs_token_t *
99 hs_token_new(hs_token_type_t type, size_t token_len,
100  const uint8_t *token)
101 {
102  tor_assert(token);
103 
104  hs_token_t *hs_token = tor_malloc_zero(sizeof(hs_token_t));
105  hs_token->type = type;
106  hs_token->token_len = token_len;
107  hs_token->token = tor_memdup(token, token_len);
108 
109  return hs_token;
110 }
111 
112 #define hs_token_free(val) \
113  FREE_AND_NULL(hs_token_t, hs_token_free_, (val))
114 
116 static void
117 hs_token_free_(hs_token_t *hs_token)
118 {
119  if (!hs_token) {
120  return;
121  }
122 
123  tor_free(hs_token->token);
124  tor_free(hs_token);
125 }
126 
128 static circuit_t *
129 get_circuit_with_token(hs_token_t *search_token)
130 {
131  tor_assert(the_hs_circuitmap);
132 
133  /* We use a dummy circuit object for the hash table search routine. */
134  circuit_t search_circ;
135  search_circ.hs_token = search_token;
136  return HT_FIND(hs_circuitmap_ht, the_hs_circuitmap, &search_circ);
137 }
138 
139 /* Helper function that registers <b>circ</b> with <b>token</b> on the HS
140  circuitmap. This function steals reference of <b>token</b>. */
141 static void
142 hs_circuitmap_register_impl(circuit_t *circ, hs_token_t *token)
143 {
144  tor_assert(circ);
145  tor_assert(token);
146  tor_assert(the_hs_circuitmap);
147 
148  /* If this circuit already has a token, clear it. */
149  if (circ->hs_token) {
151  }
152 
153  /* Kill old circuits with the same token. We want new intro/rend circuits to
154  take precedence over old ones, so that HSes and clients and reestablish
155  killed circuits without changing the HS token. */
156  {
157  circuit_t *found_circ;
158  found_circ = get_circuit_with_token(token);
159  if (found_circ) {
160  hs_circuitmap_remove_circuit(found_circ);
161  if (!found_circ->marked_for_close) {
162  circuit_mark_for_close(found_circ, END_CIRC_REASON_FINISHED);
163  }
164  }
165  }
166 
167  /* Register circuit and token to circuitmap. */
168  circ->hs_token = token;
169  HT_INSERT(hs_circuitmap_ht, the_hs_circuitmap, circ);
170 }
171 
175 static void
177  hs_token_type_t type, size_t token_len,
178  const uint8_t *token)
179 {
180  hs_token_t *hs_token = NULL;
181 
182  /* Create a new token and register it to the circuitmap */
183  tor_assert(token);
184  hs_token = hs_token_new(type, token_len, token);
185  tor_assert(hs_token);
186  hs_circuitmap_register_impl(circ, hs_token);
187 }
188 
189 /* Helper function for hs_circuitmap_get_origin_circuit() and
190  * hs_circuitmap_get_or_circuit(). Because only circuit_t are indexed in the
191  * circuitmap, this function returns object type so the specialized functions
192  * using this helper can upcast it to the right type.
193  *
194  * Return NULL if not such circuit is found. */
195 static circuit_t *
196 hs_circuitmap_get_circuit_impl(hs_token_type_t type,
197  size_t token_len,
198  const uint8_t *token,
199  uint8_t wanted_circ_purpose)
200 {
201  circuit_t *found_circ = NULL;
202 
203  tor_assert(the_hs_circuitmap);
204 
205  /* Check the circuitmap if we have a circuit with this token */
206  {
207  hs_token_t *search_hs_token = hs_token_new(type, token_len, token);
208  tor_assert(search_hs_token);
209  found_circ = get_circuit_with_token(search_hs_token);
210  hs_token_free(search_hs_token);
211  }
212 
213  /* Check that the circuit is useful to us */
214  if (!found_circ ||
215  found_circ->purpose != wanted_circ_purpose ||
216  found_circ->marked_for_close) {
217  return NULL;
218  }
219 
220  return found_circ;
221 }
222 
223 /* Helper function: Query circuitmap for origin circuit with <b>token</b> of
224  * size <b>token_len</b> and <b>type</b>. Only returns a circuit with purpose
225  * equal to the <b>wanted_circ_purpose</b> parameter and if it is NOT marked
226  * for close. Return NULL if no such circuit is found. */
227 static origin_circuit_t *
228 hs_circuitmap_get_origin_circuit(hs_token_type_t type,
229  size_t token_len,
230  const uint8_t *token,
231  uint8_t wanted_circ_purpose)
232 {
233  circuit_t *circ;
234  tor_assert(token);
235  tor_assert(CIRCUIT_PURPOSE_IS_ORIGIN(wanted_circ_purpose));
236 
237  circ = hs_circuitmap_get_circuit_impl(type, token_len, token,
238  wanted_circ_purpose);
239  if (!circ) {
240  return NULL;
241  }
242 
244  return TO_ORIGIN_CIRCUIT(circ);
245 }
246 
247 /* Helper function: Query circuitmap for OR circuit with <b>token</b> of size
248  * <b>token_len</b> and <b>type</b>. Only returns a circuit with purpose equal
249  * to the <b>wanted_circ_purpose</b> parameter and if it is NOT marked for
250  * close. Return NULL if no such circuit is found. */
251 static or_circuit_t *
252 hs_circuitmap_get_or_circuit(hs_token_type_t type,
253  size_t token_len,
254  const uint8_t *token,
255  uint8_t wanted_circ_purpose)
256 {
257  circuit_t *circ;
258  tor_assert(token);
259  tor_assert(!CIRCUIT_PURPOSE_IS_ORIGIN(wanted_circ_purpose));
260 
261  circ = hs_circuitmap_get_circuit_impl(type, token_len, token,
262  wanted_circ_purpose);
263  if (!circ) {
264  return NULL;
265  }
266 
268  return TO_OR_CIRCUIT(circ);
269 }
270 
271 /************** Public circuitmap API ****************************************/
272 
273 /**** Public relay-side getters: */
274 
275 /* Public function: Return v2 and v3 introduction circuit to this relay.
276  * Always return a newly allocated list for which it is the caller's
277  * responsability to free it. */
278 smartlist_t *
279 hs_circuitmap_get_all_intro_circ_relay_side(void)
280 {
281  circuit_t **iter;
282  smartlist_t *circuit_list = smartlist_new();
283 
284  HT_FOREACH(iter, hs_circuitmap_ht, the_hs_circuitmap) {
285  circuit_t *circ = *iter;
286 
287  /* An origin circuit or purpose is wrong or the hs token is not set to be
288  * a v2 or v3 intro relay side type, we ignore the circuit. Else, we have
289  * a match so add it to our list. */
290  if (CIRCUIT_IS_ORIGIN(circ) ||
292  (circ->hs_token->type != HS_TOKEN_INTRO_V3_RELAY_SIDE &&
293  circ->hs_token->type != HS_TOKEN_INTRO_V2_RELAY_SIDE)) {
294  continue;
295  }
296  smartlist_add(circuit_list, circ);
297  }
298 
299  return circuit_list;
300 }
301 
302 /* Public function: Return a v3 introduction circuit to this relay with
303  * <b>auth_key</b>. Return NULL if no such circuit is found in the
304  * circuitmap. */
305 or_circuit_t *
307  const ed25519_public_key_t *auth_key)
308 {
309  return hs_circuitmap_get_or_circuit(HS_TOKEN_INTRO_V3_RELAY_SIDE,
310  ED25519_PUBKEY_LEN, auth_key->pubkey,
312 }
313 
314 /* Public function: Return v2 introduction circuit to this relay with
315  * <b>digest</b>. Return NULL if no such circuit is found in the circuitmap. */
316 or_circuit_t *
317 hs_circuitmap_get_intro_circ_v2_relay_side(const uint8_t *digest)
318 {
319  return hs_circuitmap_get_or_circuit(HS_TOKEN_INTRO_V2_RELAY_SIDE,
320  REND_TOKEN_LEN, digest,
322 }
323 
324 /* Public function: Return rendezvous circuit to this relay with rendezvous
325  * <b>cookie</b>. Return NULL if no such circuit is found in the circuitmap. */
326 or_circuit_t *
327 hs_circuitmap_get_rend_circ_relay_side(const uint8_t *cookie)
328 {
329  return hs_circuitmap_get_or_circuit(HS_TOKEN_REND_RELAY_SIDE,
330  REND_TOKEN_LEN, cookie,
332 }
333 
336 /* Public function: Register rendezvous circuit with key <b>cookie</b> to the
337  * circuitmap. */
338 void
340  const uint8_t *cookie)
341 {
343  HS_TOKEN_REND_RELAY_SIDE,
344  REND_TOKEN_LEN, cookie);
345 }
346 /* Public function: Register v2 intro circuit with key <b>digest</b> to the
347  * circuitmap. */
348 void
349 hs_circuitmap_register_intro_circ_v2_relay_side(or_circuit_t *circ,
350  const uint8_t *digest)
351 {
353  HS_TOKEN_INTRO_V2_RELAY_SIDE,
354  REND_TOKEN_LEN, digest);
355 }
356 
357 /* Public function: Register v3 intro circuit with key <b>auth_key</b> to the
358  * circuitmap. */
359 void
360 hs_circuitmap_register_intro_circ_v3_relay_side(or_circuit_t *circ,
361  const ed25519_public_key_t *auth_key)
362 {
364  HS_TOKEN_INTRO_V3_RELAY_SIDE,
365  ED25519_PUBKEY_LEN, auth_key->pubkey);
366 }
367 
368 /**** Public servide-side getters: */
369 
370 /* Public function: Return v3 introduction circuit with <b>auth_key</b>
371  * originating from this hidden service. Return NULL if no such circuit is
372  * found in the circuitmap. */
375  ed25519_public_key_t *auth_key)
376 {
377  origin_circuit_t *circ = NULL;
378 
379  /* Check first for established intro circuits */
380  circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_INTRO_V3_SERVICE_SIDE,
381  ED25519_PUBKEY_LEN, auth_key->pubkey,
383  if (circ) {
384  return circ;
385  }
386 
387  /* ...if nothing found, check for pending intro circs */
388  circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_INTRO_V3_SERVICE_SIDE,
389  ED25519_PUBKEY_LEN, auth_key->pubkey,
391 
392  return circ;
393 }
394 
395 /* Public function: Return v2 introduction circuit originating from this hidden
396  * service with <b>digest</b>. Return NULL if no such circuit is found in the
397  * circuitmap. */
399 hs_circuitmap_get_intro_circ_v2_service_side(const uint8_t *digest)
400 {
401  origin_circuit_t *circ = NULL;
402 
403  /* Check first for established intro circuits */
404  circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_INTRO_V2_SERVICE_SIDE,
405  REND_TOKEN_LEN, digest,
407  if (circ) {
408  return circ;
409  }
410 
411  /* ...if nothing found, check for pending intro circs */
412  circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_INTRO_V2_SERVICE_SIDE,
413  REND_TOKEN_LEN, digest,
415 
416  return circ;
417 }
418 
419 /* Public function: Return rendezvous circuit originating from this hidden
420  * service with rendezvous <b>cookie</b>. Return NULL if no such circuit is
421  * found in the circuitmap. */
423 hs_circuitmap_get_rend_circ_service_side(const uint8_t *cookie)
424 {
425  origin_circuit_t *circ = NULL;
426 
427  /* Try to check if we have a connecting circuit. */
428  circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_REND_SERVICE_SIDE,
429  REND_TOKEN_LEN, cookie,
431  if (circ) {
432  return circ;
433  }
434 
435  /* Then try for connected circuit. */
436  circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_REND_SERVICE_SIDE,
437  REND_TOKEN_LEN, cookie,
439  return circ;
440 }
441 
442 /* Public function: Return client-side rendezvous circuit with rendezvous
443  * <b>cookie</b>. It will look for circuits with the following purposes:
444 
445  * a) CIRCUIT_PURPOSE_C_REND_READY: Established rend circuit (received
446  * RENDEZVOUS_ESTABLISHED). Waiting for RENDEZVOUS2 from service, and for
447  * INTRODUCE_ACK from intro point.
448  *
449  * b) CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED: Established rend circuit and
450  * introduce circuit acked. Waiting for RENDEZVOUS2 from service.
451  *
452  * c) CIRCUIT_PURPOSE_C_REND_JOINED: Established rend circuit and received
453  * RENDEZVOUS2 from service.
454  *
455  * d) CIRCUIT_PURPOSE_C_ESTABLISH_REND: Rend circuit open but not yet
456  * established.
457  *
458  * Return NULL if no such circuit is found in the circuitmap. */
460 hs_circuitmap_get_rend_circ_client_side(const uint8_t *cookie)
461 {
462  origin_circuit_t *circ = NULL;
463 
464  circ = hs_circuitmap_get_established_rend_circ_client_side(cookie);
465  if (circ) {
466  return circ;
467  }
468 
469  circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_REND_CLIENT_SIDE,
470  REND_TOKEN_LEN, cookie,
472  return circ;
473 }
474 
475 /* Public function: Return client-side established rendezvous circuit with
476  * rendezvous <b>cookie</b>. It will look for circuits with the following
477  * purposes:
478  *
479  * a) CIRCUIT_PURPOSE_C_REND_READY: Established rend circuit (received
480  * RENDEZVOUS_ESTABLISHED). Waiting for RENDEZVOUS2 from service, and for
481  * INTRODUCE_ACK from intro point.
482  *
483  * b) CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED: Established rend circuit and
484  * introduce circuit acked. Waiting for RENDEZVOUS2 from service.
485  *
486  * c) CIRCUIT_PURPOSE_C_REND_JOINED: Established rend circuit and received
487  * RENDEZVOUS2 from service.
488  *
489  * Return NULL if no such circuit is found in the circuitmap. */
491 hs_circuitmap_get_established_rend_circ_client_side(const uint8_t *cookie)
492 {
493  origin_circuit_t *circ = NULL;
494 
495  circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_REND_CLIENT_SIDE,
496  REND_TOKEN_LEN, cookie,
498  if (circ) {
499  return circ;
500  }
501 
502  circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_REND_CLIENT_SIDE,
503  REND_TOKEN_LEN, cookie,
505  if (circ) {
506  return circ;
507  }
508 
509  circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_REND_CLIENT_SIDE,
510  REND_TOKEN_LEN, cookie,
512  return circ;
513 }
514 
515 /**** Public servide-side setters: */
516 
517 /* Public function: Register v2 intro circuit with key <b>digest</b> to the
518  * circuitmap. */
519 void
520 hs_circuitmap_register_intro_circ_v2_service_side(origin_circuit_t *circ,
521  const uint8_t *digest)
522 {
524  HS_TOKEN_INTRO_V2_SERVICE_SIDE,
525  REND_TOKEN_LEN, digest);
526 }
527 
528 /* Public function: Register v3 intro circuit with key <b>auth_key</b> to the
529  * circuitmap. */
530 void
531 hs_circuitmap_register_intro_circ_v3_service_side(origin_circuit_t *circ,
532  const ed25519_public_key_t *auth_key)
533 {
535  HS_TOKEN_INTRO_V3_SERVICE_SIDE,
536  ED25519_PUBKEY_LEN, auth_key->pubkey);
537 }
538 
539 /* Public function: Register rendezvous circuit with key <b>cookie</b> to the
540  * circuitmap. */
541 void
542 hs_circuitmap_register_rend_circ_service_side(origin_circuit_t *circ,
543  const uint8_t *cookie)
544 {
546  HS_TOKEN_REND_SERVICE_SIDE,
547  REND_TOKEN_LEN, cookie);
548 }
549 
550 /* Public function: Register rendezvous circuit with key <b>cookie</b> to the
551  * client-side circuitmap. */
552 void
553 hs_circuitmap_register_rend_circ_client_side(origin_circuit_t *or_circ,
554  const uint8_t *cookie)
555 {
556  circuit_t *circ = TO_CIRCUIT(or_circ);
557  { /* Basic circ purpose sanity checking */
558  tor_assert_nonfatal(circ->purpose == CIRCUIT_PURPOSE_C_ESTABLISH_REND);
559  }
560 
561  hs_circuitmap_register_circuit(circ, HS_TOKEN_REND_CLIENT_SIDE,
562  REND_TOKEN_LEN, cookie);
563 }
564 
565 /**** Misc public functions: */
566 
569 void
571 {
572  tor_assert(the_hs_circuitmap);
573 
574  if (!circ || !circ->hs_token) {
575  return;
576  }
577 
578  /* Remove circ from circuitmap */
579  circuit_t *tmp;
580  tmp = HT_REMOVE(hs_circuitmap_ht, the_hs_circuitmap, circ);
581  /* ... and ensure the removal was successful. */
582  if (tmp) {
583  tor_assert(tmp == circ);
584  } else {
585  log_warn(LD_BUG, "Could not find circuit (%u) in circuitmap.",
586  circ->n_circ_id);
587  }
588 
589  /* Clear token from circ */
590  hs_token_free(circ->hs_token);
591  circ->hs_token = NULL;
592 }
593 
594 /* Public function: Initialize the global HS circuitmap. */
595 void
596 hs_circuitmap_init(void)
597 {
598  tor_assert(!the_hs_circuitmap);
599 
600  the_hs_circuitmap = tor_malloc_zero(sizeof(struct hs_circuitmap_ht));
601  HT_INIT(hs_circuitmap_ht, the_hs_circuitmap);
602 }
603 
604 /* Public function: Free all memory allocated by the global HS circuitmap. */
605 void
606 hs_circuitmap_free_all(void)
607 {
608  if (the_hs_circuitmap) {
609  HT_CLEAR(hs_circuitmap_ht, the_hs_circuitmap);
610  tor_free(the_hs_circuitmap);
611  }
612 }
#define CIRCUIT_PURPOSE_IS_ORIGIN(p)
Definition: circuitlist.h:138
#define CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED
Definition: circuitlist.h:87
static circuit_t * get_circuit_with_token(hs_token_t *search_token)
uint16_t marked_for_close
Definition: circuit_st.h:178
#define CIRCUIT_IS_ORIGIN(c)
Definition: circuitlist.h:145
#define CIRCUIT_PURPOSE_REND_POINT_WAITING
Definition: circuitlist.h:44
HT_PROTOTYPE(HT_GENERATE2(strmap_impl, HT_GENERATE2(strmap_entry_t, HT_GENERATE2(node, HT_GENERATE2(strmap_entry_hash, HT_GENERATE2(strmap_entries_eq)
Definition: map.c:87
void smartlist_add(smartlist_t *sl, void *element)
#define TO_CIRCUIT(x)
Definition: or.h:951
#define CIRCUIT_PURPOSE_C_REND_READY
Definition: circuitlist.h:84
Header file for config.c.
#define CIRCUIT_PURPOSE_S_ESTABLISH_INTRO
Definition: circuitlist.h:102
struct hs_token_t * hs_token
Definition: circuit_st.h:205
#define tor_free(p)
Definition: malloc.h:52
uint8_t purpose
Definition: circuit_st.h:100
origin_circuit_t * hs_circuitmap_get_intro_circ_v3_service_side(const ed25519_public_key_t *auth_key)
tor_assert(buffer)
static void hs_token_free_(hs_token_t *hs_token)
int tor_memeq(const void *a, const void *b, size_t sz)
Definition: di_ops.c:107
circid_t n_circ_id
Definition: circuit_st.h:67
static void hs_circuitmap_register_circuit(circuit_t *circ, hs_token_type_t type, size_t token_len, const uint8_t *token)
void hs_circuitmap_register_rend_circ_relay_side(or_circuit_t *circ, const uint8_t *cookie)
Master header file for Tor-specific functionality.
#define CIRCUIT_PURPOSE_C_ESTABLISH_REND
Definition: circuitlist.h:82
void tor_free_(void *mem)
Definition: malloc.c:227
Header file for hs_circuitmap.c.
#define CIRCUIT_PURPOSE_S_CONNECT_REND
Definition: circuitlist.h:108
Header file for circuitlist.c.
or_circuit_t * hs_circuitmap_get_intro_circ_v3_relay_side(const ed25519_public_key_t *auth_key)
void hs_circuitmap_remove_circuit(circuit_t *circ)
#define CIRCUIT_PURPOSE_S_INTRO
Definition: circuitlist.h:105
origin_circuit_t * TO_ORIGIN_CIRCUIT(circuit_t *x)
Definition: circuitlist.c:163
#define CIRCUIT_PURPOSE_INTRO_POINT
Definition: circuitlist.h:41
#define CIRCUIT_PURPOSE_C_REND_JOINED
Definition: circuitlist.h:89
or_circuit_t * TO_OR_CIRCUIT(circuit_t *x)
Definition: circuitlist.c:151
#define CIRCUIT_IS_ORCIRC(c)
Definition: circuitlist.h:152
#define CIRCUIT_PURPOSE_S_REND_JOINED
Definition: circuitlist.h:111
#define LD_BUG
Definition: log.h:84