hs_circuitmap.c (18676B)
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 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 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 hs_circuit_hash_token(const circuit_t *circuit) 68 { 69 tor_assert(circuit->hs_token); 70 71 return (unsigned) siphash24g(circuit->hs_token->token, 72 circuit->hs_token->token_len); 73 } 74 75 /** Register the circuitmap hash table */ 76 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 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 get_hs_circuitmap(void) 90 { 91 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 hs_token_new(hs_token_type_t type, size_t token_len, 101 const uint8_t *token) 102 { 103 tor_assert(token); 104 105 hs_token_t *hs_token = tor_malloc_zero(sizeof(hs_token_t)); 106 hs_token->type = type; 107 hs_token->token_len = token_len; 108 hs_token->token = tor_memdup(token, token_len); 109 110 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 hs_token_free_(hs_token_t *hs_token) 119 { 120 if (!hs_token) { 121 return; 122 } 123 124 tor_free(hs_token->token); 125 tor_free(hs_token); 126 } 127 128 /** Return the circuit from the circuitmap with token <b>search_token</b>. */ 129 static circuit_t * 130 get_circuit_with_token(hs_token_t *search_token) 131 { 132 tor_assert(the_hs_circuitmap); 133 134 /* We use a dummy circuit object for the hash table search routine. */ 135 circuit_t search_circ; 136 search_circ.hs_token = search_token; 137 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 hs_circuitmap_register_impl(circuit_t *circ, hs_token_t *token) 144 { 145 tor_assert(circ); 146 tor_assert(token); 147 tor_assert(the_hs_circuitmap); 148 149 /* If this circuit already has a token, clear it. */ 150 if (circ->hs_token) { 151 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 circuit_t *found_circ; 159 found_circ = get_circuit_with_token(token); 160 if (found_circ) { 161 hs_circuitmap_remove_circuit(found_circ); 162 if (!found_circ->marked_for_close) { 163 circuit_mark_for_close(found_circ, END_CIRC_REASON_FINISHED); 164 } 165 } 166 } 167 168 /* Register circuit and token to circuitmap. */ 169 circ->hs_token = token; 170 HT_INSERT(hs_circuitmap_ht, the_hs_circuitmap, circ); 171 } 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 hs_circuitmap_register_circuit(circuit_t *circ, 178 hs_token_type_t type, size_t token_len, 179 const uint8_t *token) 180 { 181 hs_token_t *hs_token = NULL; 182 183 /* Create a new token and register it to the circuitmap */ 184 tor_assert(token); 185 hs_token = hs_token_new(type, token_len, token); 186 tor_assert(hs_token); 187 hs_circuitmap_register_impl(circ, hs_token); 188 } 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 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 circuit_t *found_circ = NULL; 203 204 tor_assert(the_hs_circuitmap); 205 206 /* Check the circuitmap if we have a circuit with this token */ 207 { 208 hs_token_t *search_hs_token = hs_token_new(type, token_len, token); 209 tor_assert(search_hs_token); 210 found_circ = get_circuit_with_token(search_hs_token); 211 hs_token_free(search_hs_token); 212 } 213 214 /* Check that the circuit is useful to us */ 215 if (!found_circ || 216 found_circ->purpose != wanted_circ_purpose || 217 found_circ->marked_for_close) { 218 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 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 circuit_t *circ; 235 tor_assert(token); 236 tor_assert(CIRCUIT_PURPOSE_IS_ORIGIN(wanted_circ_purpose)); 237 238 circ = hs_circuitmap_get_circuit_impl(type, token_len, token, 239 wanted_circ_purpose); 240 if (!circ) { 241 return NULL; 242 } 243 244 tor_assert(CIRCUIT_IS_ORIGIN(circ)); 245 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 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 circuit_t *circ; 259 tor_assert(token); 260 tor_assert(!CIRCUIT_PURPOSE_IS_ORIGIN(wanted_circ_purpose)); 261 262 circ = hs_circuitmap_get_circuit_impl(type, token_len, token, 263 wanted_circ_purpose); 264 if (!circ) { 265 return NULL; 266 } 267 268 tor_assert(CIRCUIT_IS_ORCIRC(circ)); 269 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 hs_circuitmap_get_all_intro_circ_relay_side(void) 281 { 282 circuit_t **iter; 283 smartlist_t *circuit_list = smartlist_new(); 284 285 HT_FOREACH(iter, hs_circuitmap_ht, the_hs_circuitmap) { 286 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 if (CIRCUIT_IS_ORIGIN(circ) || 292 circ->purpose != CIRCUIT_PURPOSE_INTRO_POINT || 293 circ->hs_token->type != HS_TOKEN_INTRO_V3_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 * 306 hs_circuitmap_get_intro_circ_v3_relay_side( 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, 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 hs_circuitmap_get_rend_circ_relay_side(const uint8_t *cookie) 318 { 319 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 hs_circuitmap_register_rend_circ_relay_side(or_circuit_t *circ, 330 const uint8_t *cookie) 331 { 332 hs_circuitmap_register_circuit(TO_CIRCUIT(circ), 333 HS_TOKEN_REND_RELAY_SIDE, 334 REND_TOKEN_LEN, cookie); 335 } 336 337 /** Public function: Register v3 intro circuit with key <b>auth_key</b> to the 338 * circuitmap. */ 339 void 340 hs_circuitmap_register_intro_circ_v3_relay_side(or_circuit_t *circ, 341 const ed25519_public_key_t *auth_key) 342 { 343 hs_circuitmap_register_circuit(TO_CIRCUIT(circ), 344 HS_TOKEN_INTRO_V3_RELAY_SIDE, 345 ED25519_PUBKEY_LEN, auth_key->pubkey); 346 } 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 hs_circuitmap_get_intro_circ_v3_service_side(const 355 ed25519_public_key_t *auth_key) 356 { 357 origin_circuit_t *circ = NULL; 358 359 /* Check first for established intro circuits */ 360 circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_INTRO_V3_SERVICE_SIDE, 361 ED25519_PUBKEY_LEN, auth_key->pubkey, 362 CIRCUIT_PURPOSE_S_INTRO); 363 if (circ) { 364 return circ; 365 } 366 367 /* ...if nothing found, check for pending intro circs */ 368 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 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 hs_circuitmap_get_rend_circ_service_side(const uint8_t *cookie) 380 { 381 origin_circuit_t *circ = NULL; 382 383 /* Try to check if we have a connecting circuit. */ 384 circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_REND_SERVICE_SIDE, 385 REND_TOKEN_LEN, cookie, 386 CIRCUIT_PURPOSE_S_CONNECT_REND); 387 if (circ) { 388 return circ; 389 } 390 391 /* Then try for connected circuit. */ 392 circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_REND_SERVICE_SIDE, 393 REND_TOKEN_LEN, cookie, 394 CIRCUIT_PURPOSE_S_REND_JOINED); 395 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 hs_circuitmap_get_rend_circ_client_side(const uint8_t *cookie) 417 { 418 origin_circuit_t *circ = NULL; 419 420 circ = hs_circuitmap_get_established_rend_circ_client_side(cookie); 421 if (circ) { 422 return circ; 423 } 424 425 circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_REND_CLIENT_SIDE, 426 REND_TOKEN_LEN, cookie, 427 CIRCUIT_PURPOSE_C_ESTABLISH_REND); 428 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 hs_circuitmap_get_established_rend_circ_client_side(const uint8_t *cookie) 448 { 449 origin_circuit_t *circ = NULL; 450 451 circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_REND_CLIENT_SIDE, 452 REND_TOKEN_LEN, cookie, 453 CIRCUIT_PURPOSE_C_REND_READY); 454 if (circ) { 455 return circ; 456 } 457 458 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 if (circ) { 462 return circ; 463 } 464 465 circ = hs_circuitmap_get_origin_circuit(HS_TOKEN_REND_CLIENT_SIDE, 466 REND_TOKEN_LEN, cookie, 467 CIRCUIT_PURPOSE_C_REND_JOINED); 468 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 hs_circuitmap_register_intro_circ_v3_service_side(origin_circuit_t *circ, 477 const ed25519_public_key_t *auth_key) 478 { 479 hs_circuitmap_register_circuit(TO_CIRCUIT(circ), 480 HS_TOKEN_INTRO_V3_SERVICE_SIDE, 481 ED25519_PUBKEY_LEN, auth_key->pubkey); 482 } 483 484 /** Public function: Register rendezvous circuit with key <b>cookie</b> to the 485 * circuitmap. */ 486 void 487 hs_circuitmap_register_rend_circ_service_side(origin_circuit_t *circ, 488 const uint8_t *cookie) 489 { 490 hs_circuitmap_register_circuit(TO_CIRCUIT(circ), 491 HS_TOKEN_REND_SERVICE_SIDE, 492 REND_TOKEN_LEN, cookie); 493 } 494 495 /** Public function: Register rendezvous circuit with key <b>cookie</b> to the 496 * client-side circuitmap. */ 497 void 498 hs_circuitmap_register_rend_circ_client_side(origin_circuit_t *or_circ, 499 const uint8_t *cookie) 500 { 501 circuit_t *circ = TO_CIRCUIT(or_circ); 502 { /* Basic circ purpose sanity checking */ 503 tor_assert_nonfatal(circ->purpose == CIRCUIT_PURPOSE_C_ESTABLISH_REND); 504 } 505 506 hs_circuitmap_register_circuit(circ, HS_TOKEN_REND_CLIENT_SIDE, 507 REND_TOKEN_LEN, cookie); 508 } 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 hs_circuitmap_remove_circuit(circuit_t *circ) 516 { 517 tor_assert(the_hs_circuitmap); 518 519 if (!circ || !circ->hs_token) { 520 return; 521 } 522 523 /* Remove circ from circuitmap */ 524 circuit_t *tmp; 525 tmp = HT_REMOVE(hs_circuitmap_ht, the_hs_circuitmap, circ); 526 /* ... and ensure the removal was successful. */ 527 if (tmp) { 528 tor_assert(tmp == circ); 529 } else { 530 log_warn(LD_BUG, "Could not find circuit (%u) in circuitmap.", 531 circ->n_circ_id); 532 } 533 534 /* Clear token from circ */ 535 hs_token_free(circ->hs_token); 536 circ->hs_token = NULL; 537 } 538 539 /** Public function: Initialize the global HS circuitmap. */ 540 void 541 hs_circuitmap_init(void) 542 { 543 tor_assert(!the_hs_circuitmap); 544 545 the_hs_circuitmap = tor_malloc_zero(sizeof(struct hs_circuitmap_ht)); 546 HT_INIT(hs_circuitmap_ht, the_hs_circuitmap); 547 } 548 549 /** Public function: Free all memory allocated by the global HS circuitmap. */ 550 void 551 hs_circuitmap_free_all(void) 552 { 553 if (the_hs_circuitmap) { 554 HT_CLEAR(hs_circuitmap_ht, the_hs_circuitmap); 555 tor_free(the_hs_circuitmap); 556 } 557 }