hs_circuitmap.c 18 KB

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