tor  0.4.1.0-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 a v3 introduction circuit to this relay with
276  * <b>auth_key</b>. Return NULL if no such circuit is found in the
277  * circuitmap. */
278 or_circuit_t *
280  const ed25519_public_key_t *auth_key)
281 {
282  return hs_circuitmap_get_or_circuit(HS_TOKEN_INTRO_V3_RELAY_SIDE,
283  ED25519_PUBKEY_LEN, auth_key->pubkey,
285 }
286 
287 /* Public function: Return v2 introduction circuit to this relay with
288  * <b>digest</b>. Return NULL if no such circuit is found in the circuitmap. */
289 or_circuit_t *
290 hs_circuitmap_get_intro_circ_v2_relay_side(const uint8_t *digest)
291 {
292  return hs_circuitmap_get_or_circuit(HS_TOKEN_INTRO_V2_RELAY_SIDE,
293  REND_TOKEN_LEN, digest,
295 }
296 
297 /* Public function: Return rendezvous circuit to this relay with rendezvous
298  * <b>cookie</b>. Return NULL if no such circuit is found in the circuitmap. */
299 or_circuit_t *
300 hs_circuitmap_get_rend_circ_relay_side(const uint8_t *cookie)
301 {
302  return hs_circuitmap_get_or_circuit(HS_TOKEN_REND_RELAY_SIDE,
303  REND_TOKEN_LEN, cookie,
305 }
306 
309 /* Public function: Register rendezvous circuit with key <b>cookie</b> to the
310  * circuitmap. */
311 void
313  const uint8_t *cookie)
314 {
316  HS_TOKEN_REND_RELAY_SIDE,
317  REND_TOKEN_LEN, cookie);
318 }
319 /* Public function: Register v2 intro circuit with key <b>digest</b> to the
320  * circuitmap. */
321 void
322 hs_circuitmap_register_intro_circ_v2_relay_side(or_circuit_t *circ,
323  const uint8_t *digest)
324 {
326  HS_TOKEN_INTRO_V2_RELAY_SIDE,
327  REND_TOKEN_LEN, digest);
328 }
329 
330 /* Public function: Register v3 intro circuit with key <b>auth_key</b> to the
331  * circuitmap. */
332 void
333 hs_circuitmap_register_intro_circ_v3_relay_side(or_circuit_t *circ,
334  const ed25519_public_key_t *auth_key)
335 {
337  HS_TOKEN_INTRO_V3_RELAY_SIDE,
338  ED25519_PUBKEY_LEN, auth_key->pubkey);
339 }
340 
341 /**** Public servide-side getters: */
342 
343 /* Public function: Return v3 introduction circuit with <b>auth_key</b>
344  * originating from this hidden service. Return NULL if no such circuit is
345  * found in the circuitmap. */
348  ed25519_public_key_t *auth_key)
349 {
350  origin_circuit_t *circ = NULL;
351 
352  /* Check first for established intro circuits */
353  circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_INTRO_V3_SERVICE_SIDE,
354  ED25519_PUBKEY_LEN, auth_key->pubkey,
356  if (circ) {
357  return circ;
358  }
359 
360  /* ...if nothing found, check for pending intro circs */
361  circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_INTRO_V3_SERVICE_SIDE,
362  ED25519_PUBKEY_LEN, auth_key->pubkey,
364 
365  return circ;
366 }
367 
368 /* Public function: Return v2 introduction circuit originating from this hidden
369  * service with <b>digest</b>. Return NULL if no such circuit is found in the
370  * circuitmap. */
372 hs_circuitmap_get_intro_circ_v2_service_side(const uint8_t *digest)
373 {
374  origin_circuit_t *circ = NULL;
375 
376  /* Check first for established intro circuits */
377  circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_INTRO_V2_SERVICE_SIDE,
378  REND_TOKEN_LEN, digest,
380  if (circ) {
381  return circ;
382  }
383 
384  /* ...if nothing found, check for pending intro circs */
385  circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_INTRO_V2_SERVICE_SIDE,
386  REND_TOKEN_LEN, digest,
388 
389  return circ;
390 }
391 
392 /* Public function: Return rendezvous circuit originating from this hidden
393  * service with rendezvous <b>cookie</b>. Return NULL if no such circuit is
394  * found in the circuitmap. */
396 hs_circuitmap_get_rend_circ_service_side(const uint8_t *cookie)
397 {
398  origin_circuit_t *circ = NULL;
399 
400  /* Try to check if we have a connecting circuit. */
401  circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_REND_SERVICE_SIDE,
402  REND_TOKEN_LEN, cookie,
404  if (circ) {
405  return circ;
406  }
407 
408  /* Then try for connected circuit. */
409  circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_REND_SERVICE_SIDE,
410  REND_TOKEN_LEN, cookie,
412  return circ;
413 }
414 
415 /* Public function: Return client-side rendezvous circuit with rendezvous
416  * <b>cookie</b>. It will look for circuits with the following purposes:
417 
418  * a) CIRCUIT_PURPOSE_C_REND_READY: Established rend circuit (received
419  * RENDEZVOUS_ESTABLISHED). Waiting for RENDEZVOUS2 from service, and for
420  * INTRODUCE_ACK from intro point.
421  *
422  * b) CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED: Established rend circuit and
423  * introduce circuit acked. Waiting for RENDEZVOUS2 from service.
424  *
425  * c) CIRCUIT_PURPOSE_C_REND_JOINED: Established rend circuit and received
426  * RENDEZVOUS2 from service.
427  *
428  * d) CIRCUIT_PURPOSE_C_ESTABLISH_REND: Rend circuit open but not yet
429  * established.
430  *
431  * Return NULL if no such circuit is found in the circuitmap. */
433 hs_circuitmap_get_rend_circ_client_side(const uint8_t *cookie)
434 {
435  origin_circuit_t *circ = NULL;
436 
437  circ = hs_circuitmap_get_established_rend_circ_client_side(cookie);
438  if (circ) {
439  return circ;
440  }
441 
442  circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_REND_CLIENT_SIDE,
443  REND_TOKEN_LEN, cookie,
445  return circ;
446 }
447 
448 /* Public function: Return client-side established rendezvous circuit with
449  * rendezvous <b>cookie</b>. It will look for circuits with the following
450  * purposes:
451  *
452  * a) CIRCUIT_PURPOSE_C_REND_READY: Established rend circuit (received
453  * RENDEZVOUS_ESTABLISHED). Waiting for RENDEZVOUS2 from service, and for
454  * INTRODUCE_ACK from intro point.
455  *
456  * b) CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED: Established rend circuit and
457  * introduce circuit acked. Waiting for RENDEZVOUS2 from service.
458  *
459  * c) CIRCUIT_PURPOSE_C_REND_JOINED: Established rend circuit and received
460  * RENDEZVOUS2 from service.
461  *
462  * Return NULL if no such circuit is found in the circuitmap. */
464 hs_circuitmap_get_established_rend_circ_client_side(const uint8_t *cookie)
465 {
466  origin_circuit_t *circ = NULL;
467 
468  circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_REND_CLIENT_SIDE,
469  REND_TOKEN_LEN, cookie,
471  if (circ) {
472  return circ;
473  }
474 
475  circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_REND_CLIENT_SIDE,
476  REND_TOKEN_LEN, cookie,
478  if (circ) {
479  return circ;
480  }
481 
482  circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_REND_CLIENT_SIDE,
483  REND_TOKEN_LEN, cookie,
485  return circ;
486 }
487 
488 /**** Public servide-side setters: */
489 
490 /* Public function: Register v2 intro circuit with key <b>digest</b> to the
491  * circuitmap. */
492 void
493 hs_circuitmap_register_intro_circ_v2_service_side(origin_circuit_t *circ,
494  const uint8_t *digest)
495 {
497  HS_TOKEN_INTRO_V2_SERVICE_SIDE,
498  REND_TOKEN_LEN, digest);
499 }
500 
501 /* Public function: Register v3 intro circuit with key <b>auth_key</b> to the
502  * circuitmap. */
503 void
504 hs_circuitmap_register_intro_circ_v3_service_side(origin_circuit_t *circ,
505  const ed25519_public_key_t *auth_key)
506 {
508  HS_TOKEN_INTRO_V3_SERVICE_SIDE,
509  ED25519_PUBKEY_LEN, auth_key->pubkey);
510 }
511 
512 /* Public function: Register rendezvous circuit with key <b>cookie</b> to the
513  * circuitmap. */
514 void
515 hs_circuitmap_register_rend_circ_service_side(origin_circuit_t *circ,
516  const uint8_t *cookie)
517 {
519  HS_TOKEN_REND_SERVICE_SIDE,
520  REND_TOKEN_LEN, cookie);
521 }
522 
523 /* Public function: Register rendezvous circuit with key <b>cookie</b> to the
524  * client-side circuitmap. */
525 void
526 hs_circuitmap_register_rend_circ_client_side(origin_circuit_t *or_circ,
527  const uint8_t *cookie)
528 {
529  circuit_t *circ = TO_CIRCUIT(or_circ);
530  { /* Basic circ purpose sanity checking */
531  tor_assert_nonfatal(circ->purpose == CIRCUIT_PURPOSE_C_ESTABLISH_REND);
532  }
533 
534  hs_circuitmap_register_circuit(circ, HS_TOKEN_REND_CLIENT_SIDE,
535  REND_TOKEN_LEN, cookie);
536 }
537 
538 /**** Misc public functions: */
539 
542 void
544 {
545  tor_assert(the_hs_circuitmap);
546 
547  if (!circ || !circ->hs_token) {
548  return;
549  }
550 
551  /* Remove circ from circuitmap */
552  circuit_t *tmp;
553  tmp = HT_REMOVE(hs_circuitmap_ht, the_hs_circuitmap, circ);
554  /* ... and ensure the removal was successful. */
555  if (tmp) {
556  tor_assert(tmp == circ);
557  } else {
558  log_warn(LD_BUG, "Could not find circuit (%u) in circuitmap.",
559  circ->n_circ_id);
560  }
561 
562  /* Clear token from circ */
563  hs_token_free(circ->hs_token);
564  circ->hs_token = NULL;
565 }
566 
567 /* Public function: Initialize the global HS circuitmap. */
568 void
569 hs_circuitmap_init(void)
570 {
571  tor_assert(!the_hs_circuitmap);
572 
573  the_hs_circuitmap = tor_malloc_zero(sizeof(struct hs_circuitmap_ht));
574  HT_INIT(hs_circuitmap_ht, the_hs_circuitmap);
575 }
576 
577 /* Public function: Free all memory allocated by the global HS circuitmap. */
578 void
579 hs_circuitmap_free_all(void)
580 {
581  if (the_hs_circuitmap) {
582  HT_CLEAR(hs_circuitmap_ht, the_hs_circuitmap);
583  tor_free(the_hs_circuitmap);
584  }
585 }
#define CIRCUIT_PURPOSE_IS_ORIGIN(p)
Definition: circuitlist.h:136
#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:148
#define CIRCUIT_IS_ORIGIN(c)
Definition: circuitlist.h:143
#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
#define TO_CIRCUIT(x)
Definition: or.h:947
#define CIRCUIT_PURPOSE_C_REND_READY
Definition: circuitlist.h:84
Header file for config.c.
#define CIRCUIT_PURPOSE_S_ESTABLISH_INTRO
Definition: circuitlist.h:100
struct hs_token_t * hs_token
Definition: circuit_st.h:175
#define tor_free(p)
Definition: malloc.h:52
uint8_t purpose
Definition: circuit_st.h:96
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:106
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:103
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:150
#define CIRCUIT_PURPOSE_S_REND_JOINED
Definition: circuitlist.h:109
#define LD_BUG
Definition: log.h:82