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