Line data Source code
1 : /* Copyright (c) 2001 Matej Pfajfar.
2 : * Copyright (c) 2001-2004, Roger Dingledine.
3 : * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
4 : * Copyright (c) 2007-2021, The Tor Project, Inc. */
5 : /* See LICENSE for licensing information */
6 :
7 : /**
8 : * \file circuitbuild.c
9 : *
10 : * \brief Implements the details of building circuits (by choosing paths,
11 : * constructing/sending create/extend cells, and so on).
12 : *
13 : * On the client side, this module handles launching circuits. Circuit
14 : * launches are srtarted from circuit_establish_circuit(), called from
15 : * circuit_launch_by_extend_info()). To choose the path the circuit will
16 : * take, onion_extend_cpath() calls into a maze of node selection functions.
17 : *
18 : * Once the circuit is ready to be launched, the first hop is treated as a
19 : * special case with circuit_handle_first_hop(), since it might need to open a
20 : * channel. As the channel opens, and later as CREATED and RELAY_EXTENDED
21 : * cells arrive, the client will invoke circuit_send_next_onion_skin() to send
22 : * CREATE or RELAY_EXTEND cells.
23 : *
24 : * The server side is handled in feature/relay/circuitbuild_relay.c.
25 : **/
26 :
27 : #define CIRCUITBUILD_PRIVATE
28 : #define OCIRC_EVENT_PRIVATE
29 :
30 : #include "core/or/or.h"
31 : #include "app/config/config.h"
32 : #include "lib/confmgt/confmgt.h"
33 : #include "core/crypto/hs_ntor.h"
34 : #include "core/crypto/onion_crypto.h"
35 : #include "core/crypto/onion_fast.h"
36 : #include "core/crypto/onion_tap.h"
37 : #include "core/mainloop/connection.h"
38 : #include "core/mainloop/mainloop.h"
39 : #include "core/or/channel.h"
40 : #include "core/or/circuitbuild.h"
41 : #include "core/or/circuitlist.h"
42 : #include "core/or/circuitstats.h"
43 : #include "core/or/circuituse.h"
44 : #include "core/or/circuitpadding.h"
45 : #include "core/or/command.h"
46 : #include "core/or/connection_edge.h"
47 : #include "core/or/connection_or.h"
48 : #include "core/or/extendinfo.h"
49 : #include "core/or/onion.h"
50 : #include "core/or/ocirc_event.h"
51 : #include "core/or/policies.h"
52 : #include "core/or/relay.h"
53 : #include "core/or/trace_probes_circuit.h"
54 : #include "core/or/crypt_path.h"
55 : #include "feature/client/bridges.h"
56 : #include "feature/client/circpathbias.h"
57 : #include "feature/client/entrynodes.h"
58 : #include "feature/client/transports.h"
59 : #include "feature/control/control_events.h"
60 : #include "feature/dircommon/directory.h"
61 : #include "feature/nodelist/describe.h"
62 : #include "feature/nodelist/microdesc.h"
63 : #include "feature/nodelist/networkstatus.h"
64 : #include "feature/nodelist/nickname.h"
65 : #include "feature/nodelist/node_select.h"
66 : #include "feature/nodelist/nodelist.h"
67 : #include "feature/nodelist/routerlist.h"
68 : #include "feature/nodelist/routerset.h"
69 : #include "feature/relay/router.h"
70 : #include "feature/relay/routermode.h"
71 : #include "feature/relay/selftest.h"
72 : #include "feature/stats/predict_ports.h"
73 : #include "lib/crypt_ops/crypto_rand.h"
74 : #include "lib/trace/events.h"
75 :
76 : #include "core/or/cell_st.h"
77 : #include "core/or/cpath_build_state_st.h"
78 : #include "core/or/entry_connection_st.h"
79 : #include "core/or/extend_info_st.h"
80 : #include "feature/nodelist/node_st.h"
81 : #include "core/or/or_circuit_st.h"
82 : #include "core/or/origin_circuit_st.h"
83 :
84 : static int circuit_send_first_onion_skin(origin_circuit_t *circ);
85 : static int circuit_build_no_more_hops(origin_circuit_t *circ);
86 : static int circuit_send_intermediate_onion_skin(origin_circuit_t *circ,
87 : crypt_path_t *hop);
88 : static const node_t *choose_good_middle_server(uint8_t purpose,
89 : cpath_build_state_t *state,
90 : crypt_path_t *head,
91 : int cur_len);
92 :
93 : /** This function tries to get a channel to the specified endpoint,
94 : * and then calls command_setup_channel() to give it the right
95 : * callbacks.
96 : */
97 0 : MOCK_IMPL(channel_t *,
98 : channel_connect_for_circuit,(const extend_info_t *ei))
99 : {
100 0 : channel_t *chan;
101 :
102 0 : const tor_addr_port_t *orport = extend_info_pick_orport(ei);
103 0 : if (!orport)
104 : return NULL;
105 0 : const char *id_digest = ei->identity_digest;
106 0 : const ed25519_public_key_t *ed_id = &ei->ed_identity;
107 :
108 0 : chan = channel_connect(&orport->addr, orport->port, id_digest, ed_id);
109 0 : if (chan) command_setup_channel(chan);
110 :
111 : return chan;
112 : }
113 :
114 : /** Search for a value for circ_id that we can use on <b>chan</b> for an
115 : * outbound circuit, until we get a circ_id that is not in use by any other
116 : * circuit on that conn.
117 : *
118 : * Return it, or 0 if can't get a unique circ_id.
119 : */
120 : STATIC circid_t
121 29572 : get_unique_circ_id_by_chan(channel_t *chan)
122 : {
123 : /* This number is chosen somewhat arbitrarily; see comment below for more
124 : * info. When the space is 80% full, it gives a one-in-a-million failure
125 : * chance; when the space is 90% full, it gives a one-in-850 chance; and when
126 : * the space is 95% full, it gives a one-in-26 failure chance. That seems
127 : * okay, though you could make a case IMO for anything between N=32 and
128 : * N=256. */
129 : #define MAX_CIRCID_ATTEMPTS 64
130 29572 : int in_use;
131 29572 : unsigned n_with_circ = 0, n_pending_destroy = 0, n_weird_pending_destroy = 0;
132 29572 : circid_t test_circ_id;
133 29572 : circid_t attempts=0;
134 29572 : circid_t high_bit, max_range, mask;
135 29572 : int64_t pending_destroy_time_total = 0;
136 29572 : int64_t pending_destroy_time_max = 0;
137 :
138 29572 : tor_assert(chan);
139 :
140 29572 : if (chan->circ_id_type == CIRC_ID_TYPE_NEITHER) {
141 1 : log_warn(LD_BUG,
142 : "Trying to pick a circuit ID for a connection from "
143 : "a client with no identity.");
144 1 : return 0;
145 : }
146 29571 : max_range = (chan->wide_circ_ids) ? (1u<<31) : (1u<<15);
147 29571 : mask = max_range - 1;
148 29671 : high_bit = (chan->circ_id_type == CIRC_ID_TYPE_HIGHER) ? max_range : 0;
149 72966 : do {
150 72966 : if (++attempts > MAX_CIRCID_ATTEMPTS) {
151 : /* Make sure we don't loop forever because all circuit IDs are used.
152 : *
153 : * Once, we would try until we had tried every possible circuit ID. But
154 : * that's quite expensive. Instead, we try MAX_CIRCID_ATTEMPTS random
155 : * circuit IDs, and then give up.
156 : *
157 : * This potentially causes us to give up early if our circuit ID space
158 : * is nearly full. If we have N circuit IDs in use, then we will reject
159 : * a new circuit with probability (N / max_range) ^ MAX_CIRCID_ATTEMPTS.
160 : * This means that in practice, a few percent of our circuit ID capacity
161 : * will go unused.
162 : *
163 : * The alternative here, though, is to do a linear search over the
164 : * whole circuit ID space every time we extend a circuit, which is
165 : * not so great either.
166 : */
167 1 : int64_t queued_destroys;
168 1 : char *m = rate_limit_log(&chan->last_warned_circ_ids_exhausted,
169 : approx_time());
170 1 : if (m == NULL)
171 : return 0; /* This message has been rate-limited away. */
172 1 : if (n_pending_destroy)
173 1 : pending_destroy_time_total /= n_pending_destroy;
174 2 : log_warn(LD_CIRC,"No unused circIDs found on channel %s wide "
175 : "circID support, with %u inbound and %u outbound circuits. "
176 : "Found %u circuit IDs in use by circuits, and %u with "
177 : "pending destroy cells. (%u of those were marked bogusly.) "
178 : "The ones with pending destroy cells "
179 : "have been marked unusable for an average of %ld seconds "
180 : "and a maximum of %ld seconds. This channel is %ld seconds "
181 : "old. Failing a circuit.%s",
182 : chan->wide_circ_ids ? "with" : "without",
183 : chan->num_p_circuits, chan->num_n_circuits,
184 : n_with_circ, n_pending_destroy, n_weird_pending_destroy,
185 : (long)pending_destroy_time_total,
186 : (long)pending_destroy_time_max,
187 : (long)(approx_time() - chan->timestamp_created),
188 : m);
189 1 : tor_free(m);
190 :
191 1 : if (!chan->cmux) {
192 : /* This warning should be impossible. */
193 0 : log_warn(LD_BUG, " This channel somehow has no cmux on it!");
194 0 : return 0;
195 : }
196 :
197 : /* analysis so far on 12184 suggests that we're running out of circuit
198 : IDs because it looks like we have too many pending destroy
199 : cells. Let's see how many we really have pending.
200 : */
201 1 : queued_destroys = circuitmux_count_queued_destroy_cells(chan,
202 : chan->cmux);
203 :
204 1 : log_warn(LD_CIRC, " Circuitmux on this channel has %u circuits, "
205 : "of which %u are active. It says it has %"PRId64
206 : " destroy cells queued.",
207 : circuitmux_num_circuits(chan->cmux),
208 : circuitmux_num_active_circuits(chan->cmux),
209 : (queued_destroys));
210 :
211 : /* Change this into "if (1)" in order to get more information about
212 : * possible failure modes here. You'll need to know how to use gdb with
213 : * Tor: this will make Tor exit with an assertion failure if the cmux is
214 : * corrupt. */
215 1 : if (0)
216 : circuitmux_assert_okay(chan->cmux);
217 :
218 1 : channel_dump_statistics(chan, LOG_WARN);
219 :
220 1 : return 0;
221 : }
222 :
223 72968 : do {
224 72968 : crypto_rand((char*) &test_circ_id, sizeof(test_circ_id));
225 72968 : test_circ_id &= mask;
226 72968 : } while (test_circ_id == 0);
227 :
228 72965 : test_circ_id |= high_bit;
229 :
230 72965 : in_use = circuit_id_in_use_on_channel(test_circ_id, chan);
231 72965 : if (in_use == 1)
232 0 : ++n_with_circ;
233 72965 : else if (in_use == 2) {
234 43395 : time_t since_when;
235 43395 : ++n_pending_destroy;
236 43395 : since_when =
237 43395 : circuit_id_when_marked_unusable_on_channel(test_circ_id, chan);
238 43395 : if (since_when) {
239 43395 : time_t waiting = approx_time() - since_when;
240 43395 : pending_destroy_time_total += waiting;
241 43395 : if (waiting > pending_destroy_time_max)
242 : pending_destroy_time_max = waiting;
243 : } else {
244 0 : ++n_weird_pending_destroy;
245 : }
246 : }
247 72965 : } while (in_use);
248 29570 : return test_circ_id;
249 : }
250 :
251 : /** If <b>verbose</b> is false, allocate and return a comma-separated list of
252 : * the currently built elements of <b>circ</b>. If <b>verbose</b> is true, also
253 : * list information about link status in a more verbose format using spaces.
254 : * If <b>verbose_names</b> is false, give hex digests; if <b>verbose_names</b>
255 : * is true, use $DIGEST=Name style names.
256 : */
257 : static char *
258 7 : circuit_list_path_impl(origin_circuit_t *circ, int verbose, int verbose_names)
259 : {
260 7 : crypt_path_t *hop;
261 7 : smartlist_t *elements;
262 7 : const char *states[] = {"closed", "waiting for keys", "open"};
263 7 : char *s;
264 :
265 7 : elements = smartlist_new();
266 :
267 7 : if (verbose) {
268 7 : const char *nickname = build_state_get_exit_nickname(circ->build_state);
269 14 : smartlist_add_asprintf(elements, "%s%s circ (length %d%s%s):",
270 7 : circ->build_state->is_internal ? "internal" : "exit",
271 7 : circ->build_state->need_uptime ? " (high-uptime)" : "",
272 : circ->build_state->desired_path_len,
273 : circ->base_.state == CIRCUIT_STATE_OPEN ? "" : ", last hop ",
274 7 : circ->base_.state == CIRCUIT_STATE_OPEN ? "" :
275 7 : (nickname?nickname:"*unnamed*"));
276 : }
277 :
278 7 : hop = circ->cpath;
279 10 : do {
280 10 : char *elt;
281 10 : const char *id;
282 10 : const node_t *node;
283 10 : if (!hop)
284 : break;
285 10 : if (!verbose && hop->state != CPATH_STATE_OPEN)
286 : break;
287 10 : if (!hop->extend_info)
288 : break;
289 4 : id = hop->extend_info->identity_digest;
290 4 : if (verbose_names) {
291 0 : elt = tor_malloc(MAX_VERBOSE_NICKNAME_LEN+1);
292 0 : if ((node = node_get_by_id(id))) {
293 0 : node_get_verbose_nickname(node, elt);
294 0 : } else if (is_legal_nickname(hop->extend_info->nickname)) {
295 0 : elt[0] = '$';
296 0 : base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN);
297 0 : elt[HEX_DIGEST_LEN+1]= '~';
298 0 : strlcpy(elt+HEX_DIGEST_LEN+2,
299 0 : hop->extend_info->nickname, MAX_NICKNAME_LEN+1);
300 : } else {
301 0 : elt[0] = '$';
302 0 : base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN);
303 : }
304 : } else { /* ! verbose_names */
305 4 : elt = tor_malloc(HEX_DIGEST_LEN+2);
306 4 : elt[0] = '$';
307 4 : base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN);
308 : }
309 4 : tor_assert(elt);
310 4 : if (verbose) {
311 4 : tor_assert(hop->state <= 2);
312 4 : smartlist_add_asprintf(elements,"%s(%s)",elt,states[hop->state]);
313 4 : tor_free(elt);
314 : } else {
315 0 : smartlist_add(elements, elt);
316 : }
317 4 : hop = hop->next;
318 4 : } while (hop != circ->cpath);
319 :
320 7 : s = smartlist_join_strings(elements, verbose?" ":",", 0, NULL);
321 18 : SMARTLIST_FOREACH(elements, char*, cp, tor_free(cp));
322 7 : smartlist_free(elements);
323 7 : return s;
324 : }
325 :
326 : /** If <b>verbose</b> is false, allocate and return a comma-separated
327 : * list of the currently built elements of <b>circ</b>. If
328 : * <b>verbose</b> is true, also list information about link status in
329 : * a more verbose format using spaces.
330 : */
331 : char *
332 7 : circuit_list_path(origin_circuit_t *circ, int verbose)
333 : {
334 7 : return circuit_list_path_impl(circ, verbose, 0);
335 : }
336 :
337 : /** Allocate and return a comma-separated list of the currently built elements
338 : * of <b>circ</b>, giving each as a verbose nickname.
339 : */
340 : char *
341 0 : circuit_list_path_for_controller(origin_circuit_t *circ)
342 : {
343 0 : return circuit_list_path_impl(circ, 0, 1);
344 : }
345 :
346 : /** Log, at severity <b>severity</b>, the nicknames of each router in
347 : * <b>circ</b>'s cpath. Also log the length of the cpath, and the intended
348 : * exit point.
349 : */
350 : void
351 7 : circuit_log_path(int severity, unsigned int domain, origin_circuit_t *circ)
352 : {
353 7 : char *s = circuit_list_path(circ,1);
354 7 : tor_log(severity,domain,"%s",s);
355 7 : tor_free(s);
356 7 : }
357 :
358 : /** Return 1 iff every node in circ's cpath definitely supports ntor. */
359 : static int
360 0 : circuit_cpath_supports_ntor(const origin_circuit_t *circ)
361 : {
362 0 : crypt_path_t *head, *cpath;
363 :
364 0 : cpath = head = circ->cpath;
365 0 : do {
366 : /* if the extend_info is missing, we can't tell if it supports ntor */
367 0 : if (!cpath->extend_info) {
368 : return 0;
369 : }
370 :
371 : /* if the key is blank, it definitely doesn't support ntor */
372 0 : if (!extend_info_supports_ntor(cpath->extend_info)) {
373 : return 0;
374 : }
375 0 : cpath = cpath->next;
376 0 : } while (cpath != head);
377 :
378 : return 1;
379 : }
380 :
381 : /** Pick all the entries in our cpath. Stop and return 0 when we're
382 : * happy, or return -1 if an error occurs. */
383 : static int
384 0 : onion_populate_cpath(origin_circuit_t *circ)
385 : {
386 0 : int r = 0;
387 :
388 : /* onion_extend_cpath assumes these are non-NULL */
389 0 : tor_assert(circ);
390 0 : tor_assert(circ->build_state);
391 :
392 0 : while (r == 0) {
393 0 : r = onion_extend_cpath(circ);
394 0 : if (r < 0) {
395 0 : log_info(LD_CIRC,"Generating cpath hop failed.");
396 0 : return -1;
397 : }
398 : }
399 :
400 : /* The path is complete */
401 0 : tor_assert(r == 1);
402 :
403 : /* Does every node in this path support ntor? */
404 0 : int path_supports_ntor = circuit_cpath_supports_ntor(circ);
405 :
406 : /* We would like every path to support ntor, but we have to allow for some
407 : * edge cases. */
408 0 : tor_assert(circuit_get_cpath_len(circ));
409 0 : if (circuit_can_use_tap(circ)) {
410 : /* Circuits from clients to intro points, and hidden services to rend
411 : * points do not support ntor, because the hidden service protocol does
412 : * not include ntor onion keys. This is also true for Single Onion
413 : * Services. */
414 : return 0;
415 : }
416 :
417 0 : if (circuit_get_cpath_len(circ) == 1) {
418 : /* Allow for bootstrapping: when we're fetching directly from a fallback,
419 : * authority, or bridge, we have no way of knowing its ntor onion key
420 : * before we connect to it. So instead, we try connecting, and end up using
421 : * CREATE_FAST. */
422 0 : tor_assert(circ->cpath);
423 0 : tor_assert(circ->cpath->extend_info);
424 0 : const node_t *node = node_get_by_id(
425 0 : circ->cpath->extend_info->identity_digest);
426 : /* If we don't know the node and its descriptor, we must be bootstrapping.
427 : */
428 0 : if (!node || !node_has_preferred_descriptor(node, 1)) {
429 0 : return 0;
430 : }
431 : }
432 :
433 0 : if (BUG(!path_supports_ntor)) {
434 : /* If we're building a multi-hop path, and it's not one of the HS or
435 : * bootstrapping exceptions, and it doesn't support ntor, something has
436 : * gone wrong. */
437 0 : return -1;
438 : }
439 :
440 : return 0;
441 : }
442 :
443 : /** Create and return a new origin circuit. Initialize its purpose and
444 : * build-state based on our arguments. The <b>flags</b> argument is a
445 : * bitfield of CIRCLAUNCH_* flags, see circuit_launch_by_extend_info() for
446 : * more details. */
447 : origin_circuit_t *
448 21 : origin_circuit_init(uint8_t purpose, int flags)
449 : {
450 : /* sets circ->p_circ_id and circ->p_chan */
451 21 : origin_circuit_t *circ = origin_circuit_new();
452 21 : circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_CHAN_WAIT);
453 21 : circ->build_state = tor_malloc_zero(sizeof(cpath_build_state_t));
454 21 : circ->build_state->onehop_tunnel =
455 21 : ((flags & CIRCLAUNCH_ONEHOP_TUNNEL) ? 1 : 0);
456 21 : circ->build_state->need_uptime =
457 21 : ((flags & CIRCLAUNCH_NEED_UPTIME) ? 1 : 0);
458 21 : circ->build_state->need_capacity =
459 21 : ((flags & CIRCLAUNCH_NEED_CAPACITY) ? 1 : 0);
460 21 : circ->build_state->is_internal =
461 21 : ((flags & CIRCLAUNCH_IS_INTERNAL) ? 1 : 0);
462 21 : circ->build_state->is_ipv6_selftest =
463 21 : ((flags & CIRCLAUNCH_IS_IPV6_SELFTEST) ? 1 : 0);
464 21 : circ->base_.purpose = purpose;
465 21 : return circ;
466 : }
467 :
468 : /** Build a new circuit for <b>purpose</b>. If <b>exit</b> is defined, then use
469 : * that as your exit router, else choose a suitable exit node. The <b>flags</b>
470 : * argument is a bitfield of CIRCLAUNCH_* flags, see
471 : * circuit_launch_by_extend_info() for more details.
472 : *
473 : * Also launch a connection to the first OR in the chosen path, if
474 : * it's not open already.
475 : */
476 : origin_circuit_t *
477 0 : circuit_establish_circuit(uint8_t purpose, extend_info_t *exit_ei, int flags)
478 : {
479 0 : origin_circuit_t *circ;
480 0 : int err_reason = 0;
481 0 : int is_hs_v3_rp_circuit = 0;
482 :
483 0 : if (flags & CIRCLAUNCH_IS_V3_RP) {
484 0 : is_hs_v3_rp_circuit = 1;
485 : }
486 :
487 0 : circ = origin_circuit_init(purpose, flags);
488 :
489 0 : if (onion_pick_cpath_exit(circ, exit_ei, is_hs_v3_rp_circuit) < 0 ||
490 0 : onion_populate_cpath(circ) < 0) {
491 0 : circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_NOPATH);
492 0 : return NULL;
493 : }
494 :
495 0 : circuit_event_status(circ, CIRC_EVENT_LAUNCHED, 0);
496 :
497 0 : if ((err_reason = circuit_handle_first_hop(circ)) < 0) {
498 0 : circuit_mark_for_close(TO_CIRCUIT(circ), -err_reason);
499 0 : return NULL;
500 : }
501 :
502 : tor_trace(TR_SUBSYS(circuit), TR_EV(establish), circ);
503 : return circ;
504 : }
505 :
506 : /** Return the guard state associated with <b>circ</b>, which may be NULL. */
507 : circuit_guard_state_t *
508 406 : origin_circuit_get_guard_state(origin_circuit_t *circ)
509 : {
510 406 : return circ->guard_state;
511 : }
512 :
513 : /**
514 : * Helper function to publish a channel association message
515 : *
516 : * circuit_handle_first_hop() calls this to notify subscribers about a
517 : * channel launch event, which associates a circuit with a channel.
518 : * This doesn't always correspond to an assignment of the circuit's
519 : * n_chan field, because that seems to be only for fully-open
520 : * channels.
521 : **/
522 : static void
523 0 : circuit_chan_publish(const origin_circuit_t *circ, const channel_t *chan)
524 : {
525 0 : ocirc_chan_msg_t *msg = tor_malloc(sizeof(*msg));
526 :
527 0 : msg->gid = circ->global_identifier;
528 0 : msg->chan = chan->global_identifier;
529 0 : msg->onehop = circ->build_state->onehop_tunnel;
530 :
531 0 : ocirc_chan_publish(msg);
532 0 : }
533 :
534 : /** Start establishing the first hop of our circuit. Figure out what
535 : * OR we should connect to, and if necessary start the connection to
536 : * it. If we're already connected, then send the 'create' cell.
537 : * Return 0 for ok, -reason if circ should be marked-for-close. */
538 : int
539 0 : circuit_handle_first_hop(origin_circuit_t *circ)
540 : {
541 0 : crypt_path_t *firsthop;
542 0 : channel_t *n_chan;
543 0 : int err_reason = 0;
544 0 : const char *msg = NULL;
545 0 : int should_launch = 0;
546 0 : const or_options_t *options = get_options();
547 :
548 0 : firsthop = cpath_get_next_non_open_hop(circ->cpath);
549 0 : tor_assert(firsthop);
550 0 : tor_assert(firsthop->extend_info);
551 :
552 : /* Some bridges are on private addresses. Others pass a dummy private
553 : * address to the pluggable transport, which ignores it.
554 : * Deny the connection if:
555 : * - the address is internal, and
556 : * - we're not connecting to a configured bridge, and
557 : * - we're not configured to allow extends to private addresses. */
558 0 : if (extend_info_any_orport_addr_is_internal(firsthop->extend_info) &&
559 0 : !extend_info_is_a_configured_bridge(firsthop->extend_info) &&
560 0 : !options->ExtendAllowPrivateAddresses) {
561 0 : log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
562 : "Client asked me to connect directly to a private address");
563 0 : return -END_CIRC_REASON_TORPROTOCOL;
564 : }
565 :
566 : /* now see if we're already connected to the first OR in 'route' */
567 0 : const tor_addr_port_t *orport4 =
568 0 : extend_info_get_orport(firsthop->extend_info, AF_INET);
569 0 : const tor_addr_port_t *orport6 =
570 0 : extend_info_get_orport(firsthop->extend_info, AF_INET6);
571 0 : n_chan = channel_get_for_extend(
572 0 : firsthop->extend_info->identity_digest,
573 0 : &firsthop->extend_info->ed_identity,
574 : orport4 ? &orport4->addr : NULL,
575 : orport6 ? &orport6->addr : NULL,
576 : true,
577 : &msg,
578 : &should_launch);
579 :
580 0 : if (!n_chan) {
581 : /* not currently connected in a useful way. */
582 0 : log_info(LD_CIRC, "Next router is %s: %s",
583 : safe_str_client(extend_info_describe(firsthop->extend_info)),
584 : msg?msg:"???");
585 0 : circ->base_.n_hop = extend_info_dup(firsthop->extend_info);
586 :
587 0 : if (should_launch) {
588 0 : n_chan = channel_connect_for_circuit(firsthop->extend_info);
589 0 : if (!n_chan) { /* connect failed, forget the whole thing */
590 0 : log_info(LD_CIRC,"connect to firsthop failed. Closing.");
591 0 : return -END_CIRC_REASON_CONNECTFAILED;
592 : }
593 : /* We didn't find a channel, but we're launching one for an origin
594 : * circuit. (If we decided not to launch a channel, then we found at
595 : * least one once good in-progress channel use for this circuit, and
596 : * marked it in channel_get_for_extend().) */
597 0 : channel_mark_as_used_for_origin_circuit(n_chan);
598 0 : circuit_chan_publish(circ, n_chan);
599 : }
600 :
601 0 : log_debug(LD_CIRC,"connecting in progress (or finished). Good.");
602 : /* return success. The onion/circuit/etc will be taken care of
603 : * automatically (may already have been) whenever n_chan reaches
604 : * OR_CONN_STATE_OPEN.
605 : */
606 0 : return 0;
607 : } else { /* it's already open. use it. */
608 0 : tor_assert(!circ->base_.n_hop);
609 0 : circ->base_.n_chan = n_chan;
610 : /* We found a channel, and we're using it for an origin circuit. */
611 0 : channel_mark_as_used_for_origin_circuit(n_chan);
612 0 : circuit_chan_publish(circ, n_chan);
613 0 : log_debug(LD_CIRC,"Conn open for %s. Delivering first onion skin.",
614 : safe_str_client(extend_info_describe(firsthop->extend_info)));
615 0 : if ((err_reason = circuit_send_next_onion_skin(circ)) < 0) {
616 0 : log_info(LD_CIRC,"circuit_send_next_onion_skin failed.");
617 0 : circ->base_.n_chan = NULL;
618 0 : return err_reason;
619 : }
620 : }
621 : return 0;
622 : }
623 :
624 : /** Find any circuits that are waiting on <b>or_conn</b> to become
625 : * open and get them to send their create cells forward.
626 : *
627 : * Status is 1 if connect succeeded, or 0 if connect failed.
628 : *
629 : * Close_origin_circuits is 1 if we should close all the origin circuits
630 : * through this channel, or 0 otherwise. (This happens when we want to retry
631 : * an older guard.)
632 : */
633 : void
634 33 : circuit_n_chan_done(channel_t *chan, int status, int close_origin_circuits)
635 : {
636 33 : smartlist_t *pending_circs;
637 33 : int err_reason = 0;
638 :
639 33 : tor_assert(chan);
640 :
641 33 : log_debug(LD_CIRC,"chan to %s, status=%d",
642 : channel_describe_peer(chan), status);
643 :
644 33 : pending_circs = smartlist_new();
645 33 : circuit_get_all_pending_on_channel(pending_circs, chan);
646 :
647 33 : SMARTLIST_FOREACH_BEGIN(pending_circs, circuit_t *, circ)
648 : {
649 : /* These checks are redundant wrt get_all_pending_on_or_conn, but I'm
650 : * leaving them in in case it's possible for the status of a circuit to
651 : * change as we're going down the list. */
652 0 : if (circ->marked_for_close || circ->n_chan || !circ->n_hop ||
653 0 : circ->state != CIRCUIT_STATE_CHAN_WAIT)
654 0 : continue;
655 :
656 0 : const char *rsa_ident = NULL;
657 0 : const ed25519_public_key_t *ed_ident = NULL;
658 0 : if (! tor_digest_is_zero(circ->n_hop->identity_digest)) {
659 0 : rsa_ident = circ->n_hop->identity_digest;
660 : }
661 0 : if (! ed25519_public_key_is_zero(&circ->n_hop->ed_identity)) {
662 0 : ed_ident = &circ->n_hop->ed_identity;
663 : }
664 :
665 0 : if (rsa_ident == NULL && ed_ident == NULL) {
666 : /* Look at addr/port. This is an unkeyed connection. */
667 0 : if (!channel_matches_extend_info(chan, circ->n_hop))
668 0 : continue;
669 : } else {
670 : /* We expected a key or keys. See if they matched. */
671 0 : if (!channel_remote_identity_matches(chan, rsa_ident, ed_ident))
672 0 : continue;
673 :
674 : /* If the channel is canonical, great. If not, it needs to match
675 : * the requested address exactly. */
676 0 : if (! chan->is_canonical &&
677 0 : ! channel_matches_extend_info(chan, circ->n_hop)) {
678 0 : continue;
679 : }
680 : }
681 0 : if (!status) { /* chan failed; close circ */
682 0 : log_info(LD_CIRC,"Channel failed; closing circ.");
683 0 : circuit_mark_for_close(circ, END_CIRC_REASON_CHANNEL_CLOSED);
684 0 : continue;
685 : }
686 :
687 0 : if (close_origin_circuits && CIRCUIT_IS_ORIGIN(circ)) {
688 0 : log_info(LD_CIRC,"Channel deprecated for origin circs; closing circ.");
689 0 : circuit_mark_for_close(circ, END_CIRC_REASON_CHANNEL_CLOSED);
690 0 : continue;
691 : }
692 0 : log_debug(LD_CIRC, "Found circ, sending create cell.");
693 : /* circuit_deliver_create_cell will set n_circ_id and add us to
694 : * chan_circuid_circuit_map, so we don't need to call
695 : * set_circid_chan here. */
696 0 : circ->n_chan = chan;
697 0 : extend_info_free(circ->n_hop);
698 0 : circ->n_hop = NULL;
699 :
700 0 : if (CIRCUIT_IS_ORIGIN(circ)) {
701 0 : if ((err_reason =
702 0 : circuit_send_next_onion_skin(TO_ORIGIN_CIRCUIT(circ))) < 0) {
703 0 : log_info(LD_CIRC,
704 : "send_next_onion_skin failed; circuit marked for closing.");
705 0 : circuit_mark_for_close(circ, -err_reason);
706 0 : continue;
707 : /* XXX could this be bad, eg if next_onion_skin failed because conn
708 : * died? */
709 : }
710 : } else {
711 : /* pull the create cell out of circ->n_chan_create_cell, and send it */
712 0 : tor_assert(circ->n_chan_create_cell);
713 0 : if (circuit_deliver_create_cell(circ, circ->n_chan_create_cell, 1)<0) {
714 0 : circuit_mark_for_close(circ, END_CIRC_REASON_RESOURCELIMIT);
715 0 : continue;
716 : }
717 0 : tor_free(circ->n_chan_create_cell);
718 0 : circuit_set_state(circ, CIRCUIT_STATE_OPEN);
719 : }
720 : }
721 0 : SMARTLIST_FOREACH_END(circ);
722 :
723 33 : smartlist_free(pending_circs);
724 33 : }
725 :
726 : /** Find a new circid that isn't currently in use on the circ->n_chan
727 : * for the outgoing
728 : * circuit <b>circ</b>, and deliver the cell <b>create_cell</b> to this
729 : * circuit. If <b>relayed</b> is true, this is a create cell somebody
730 : * gave us via an EXTEND cell, so we shouldn't worry if we don't understand
731 : * it. Return -1 if we failed to find a suitable circid, else return 0.
732 : */
733 0 : MOCK_IMPL(int,
734 : circuit_deliver_create_cell,(circuit_t *circ,
735 : const struct create_cell_t *create_cell,
736 : int relayed))
737 : {
738 0 : cell_t cell;
739 0 : circid_t id;
740 0 : int r;
741 :
742 0 : tor_assert(circ);
743 0 : tor_assert(circ->n_chan);
744 0 : tor_assert(create_cell);
745 0 : tor_assert(create_cell->cell_type == CELL_CREATE ||
746 : create_cell->cell_type == CELL_CREATE_FAST ||
747 : create_cell->cell_type == CELL_CREATE2);
748 :
749 0 : id = get_unique_circ_id_by_chan(circ->n_chan);
750 0 : if (!id) {
751 0 : static ratelim_t circid_warning_limit = RATELIM_INIT(9600);
752 0 : log_fn_ratelim(&circid_warning_limit, LOG_WARN, LD_CIRC,
753 : "failed to get unique circID.");
754 0 : goto error;
755 : }
756 :
757 0 : tor_assert_nonfatal_once(circ->n_chan->is_canonical);
758 :
759 0 : memset(&cell, 0, sizeof(cell_t));
760 0 : r = relayed ? create_cell_format_relayed(&cell, create_cell)
761 0 : : create_cell_format(&cell, create_cell);
762 0 : if (r < 0) {
763 0 : log_warn(LD_CIRC,"Couldn't format create cell");
764 0 : goto error;
765 : }
766 0 : log_debug(LD_CIRC,"Chosen circID %u.", (unsigned)id);
767 0 : circuit_set_n_circid_chan(circ, id, circ->n_chan);
768 0 : cell.circ_id = circ->n_circ_id;
769 :
770 0 : append_cell_to_circuit_queue(circ, circ->n_chan, &cell,
771 : CELL_DIRECTION_OUT, 0);
772 :
773 0 : if (CIRCUIT_IS_ORIGIN(circ)) {
774 : /* Update began timestamp for circuits starting their first hop */
775 0 : if (TO_ORIGIN_CIRCUIT(circ)->cpath->state == CPATH_STATE_CLOSED) {
776 0 : if (!CHANNEL_IS_OPEN(circ->n_chan)) {
777 0 : log_warn(LD_CIRC,
778 : "Got first hop for a circuit without an opened channel. "
779 : "State: %s.", channel_state_to_string(circ->n_chan->state));
780 0 : tor_fragile_assert();
781 : }
782 :
783 0 : tor_gettimeofday(&circ->timestamp_began);
784 : }
785 :
786 : /* mark it so it gets better rate limiting treatment. */
787 0 : channel_timestamp_client(circ->n_chan);
788 : }
789 :
790 : return 0;
791 0 : error:
792 0 : circ->n_chan = NULL;
793 0 : return -1;
794 : }
795 :
796 : /** Return true iff we should send a create_fast cell to start building a
797 : * given circuit */
798 : static inline bool
799 2 : should_use_create_fast_for_circuit(origin_circuit_t *circ)
800 : {
801 2 : tor_assert(circ->cpath);
802 2 : tor_assert(circ->cpath->extend_info);
803 :
804 2 : return ! circuit_has_usable_onion_key(circ);
805 : }
806 :
807 : /**
808 : * Return true if <b>circ</b> is the type of circuit we want to count
809 : * timeouts from.
810 : *
811 : * In particular, we want to consider any circuit that plans to build
812 : * at least 3 hops (but maybe more), but has 3 or fewer hops built
813 : * so far.
814 : *
815 : * We still want to consider circuits before 3 hops, because we need
816 : * to decide if we should convert them to a measurement circuit in
817 : * circuit_build_times_handle_completed_hop(), rather than letting
818 : * slow circuits get killed right away.
819 : */
820 : int
821 19 : circuit_timeout_want_to_count_circ(const origin_circuit_t *circ)
822 : {
823 19 : return !circ->has_opened
824 13 : && circ->build_state->desired_path_len >= DEFAULT_ROUTE_LEN
825 32 : && circuit_get_cpath_opened_len(circ) <= DEFAULT_ROUTE_LEN;
826 : }
827 :
828 : /** Decide whether to use a TAP or ntor handshake for connecting to <b>ei</b>
829 : * directly, and set *<b>cell_type_out</b> and *<b>handshake_type_out</b>
830 : * accordingly.
831 : * Note that TAP handshakes in CREATE cells are only used for direct
832 : * connections:
833 : * - from Single Onions to rend points not in the service's consensus.
834 : * This is checked in onion_populate_cpath. */
835 : static void
836 6 : circuit_pick_create_handshake(uint8_t *cell_type_out,
837 : uint16_t *handshake_type_out,
838 : const extend_info_t *ei)
839 : {
840 : /* torspec says: In general, clients SHOULD use CREATE whenever they are
841 : * using the TAP handshake, and CREATE2 otherwise. */
842 6 : if (extend_info_supports_ntor(ei)) {
843 0 : *cell_type_out = CELL_CREATE2;
844 0 : *handshake_type_out = ONION_HANDSHAKE_TYPE_NTOR;
845 : } else {
846 : /* XXXX030 Remove support for deciding to use TAP and EXTEND. */
847 6 : *cell_type_out = CELL_CREATE;
848 6 : *handshake_type_out = ONION_HANDSHAKE_TYPE_TAP;
849 : }
850 6 : }
851 :
852 : /** Decide whether to use a TAP or ntor handshake for extending to <b>ei</b>
853 : * and set *<b>handshake_type_out</b> accordingly. Decide whether we should
854 : * use an EXTEND2 or an EXTEND cell to do so, and set *<b>cell_type_out</b>
855 : * and *<b>create_cell_type_out</b> accordingly.
856 : * Note that TAP handshakes in EXTEND cells are only used:
857 : * - from clients to intro points, and
858 : * - from hidden services to rend points.
859 : * This is checked in onion_populate_cpath.
860 : */
861 : static void
862 6 : circuit_pick_extend_handshake(uint8_t *cell_type_out,
863 : uint8_t *create_cell_type_out,
864 : uint16_t *handshake_type_out,
865 : const extend_info_t *ei)
866 : {
867 6 : uint8_t t;
868 6 : circuit_pick_create_handshake(&t, handshake_type_out, ei);
869 :
870 : /* torspec says: Clients SHOULD use the EXTEND format whenever sending a TAP
871 : * handshake... In other cases, clients SHOULD use EXTEND2. */
872 6 : if (*handshake_type_out != ONION_HANDSHAKE_TYPE_TAP) {
873 0 : *cell_type_out = RELAY_COMMAND_EXTEND2;
874 0 : *create_cell_type_out = CELL_CREATE2;
875 : } else {
876 : /* XXXX030 Remove support for deciding to use TAP and EXTEND. */
877 6 : *cell_type_out = RELAY_COMMAND_EXTEND;
878 6 : *create_cell_type_out = CELL_CREATE;
879 : }
880 6 : }
881 :
882 : /**
883 : * Return true iff <b>circ</b> is allowed
884 : * to have no guard configured, even if the circuit is multihop
885 : * and guards are enabled.
886 : */
887 : static int
888 0 : circuit_may_omit_guard(const origin_circuit_t *circ)
889 : {
890 0 : if (BUG(!circ))
891 0 : return 0;
892 :
893 0 : if (circ->first_hop_from_controller) {
894 : /* The controller picked the first hop: that bypasses the guard system. */
895 : return 1;
896 : }
897 :
898 0 : switch (circ->base_.purpose) {
899 : case CIRCUIT_PURPOSE_TESTING:
900 : case CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT:
901 : /* Testing circuits may omit guards because they're measuring
902 : * liveness or performance, and don't want guards to interfere. */
903 : return 1;
904 0 : default:
905 : /* All other multihop circuits should use guards if guards are
906 : * enabled. */
907 0 : return 0;
908 : }
909 : }
910 :
911 : /** This is the backbone function for building circuits.
912 : *
913 : * If circ's first hop is closed, then we need to build a create
914 : * cell and send it forward.
915 : *
916 : * Otherwise, if circ's cpath still has any non-open hops, we need to
917 : * build a relay extend cell and send it forward to the next non-open hop.
918 : *
919 : * If all hops on the cpath are open, we're done building the circuit
920 : * and we should do housekeeping for the newly opened circuit.
921 : *
922 : * Return -reason if we want to tear down circ, else return 0.
923 : */
924 : int
925 8 : circuit_send_next_onion_skin(origin_circuit_t *circ)
926 : {
927 8 : tor_assert(circ);
928 :
929 8 : if (circ->cpath->state == CPATH_STATE_CLOSED) {
930 : /* Case one: we're on the first hop. */
931 2 : return circuit_send_first_onion_skin(circ);
932 : }
933 :
934 6 : tor_assert(circ->cpath->state == CPATH_STATE_OPEN);
935 6 : tor_assert(circ->base_.state == CIRCUIT_STATE_BUILDING);
936 :
937 6 : crypt_path_t *hop = cpath_get_next_non_open_hop(circ->cpath);
938 6 : circuit_build_times_handle_completed_hop(circ);
939 :
940 6 : circpad_machine_event_circ_added_hop(circ);
941 :
942 6 : if (hop) {
943 : /* Case two: we're on a hop after the first. */
944 6 : return circuit_send_intermediate_onion_skin(circ, hop);
945 : }
946 :
947 : /* Case three: the circuit is finished. Do housekeeping tasks on it. */
948 0 : circpad_machine_event_circ_built(circ);
949 0 : return circuit_build_no_more_hops(circ);
950 : }
951 :
952 : /**
953 : * Called from circuit_send_next_onion_skin() when we find ourselves connected
954 : * to the first hop in <b>circ</b>: Send a CREATE or CREATE2 or CREATE_FAST
955 : * cell to that hop. Return 0 on success; -reason on failure (if the circuit
956 : * should be torn down).
957 : */
958 : static int
959 2 : circuit_send_first_onion_skin(origin_circuit_t *circ)
960 : {
961 2 : int fast;
962 2 : int len;
963 2 : const node_t *node;
964 2 : create_cell_t cc;
965 2 : memset(&cc, 0, sizeof(cc));
966 :
967 2 : log_debug(LD_CIRC,"First skin; sending create cell.");
968 :
969 2 : if (circ->build_state->onehop_tunnel) {
970 2 : control_event_bootstrap(BOOTSTRAP_STATUS_ONEHOP_CREATE, 0);
971 : } else {
972 0 : control_event_bootstrap(BOOTSTRAP_STATUS_CIRCUIT_CREATE, 0);
973 :
974 : /* If this is not a one-hop tunnel, the channel is being used
975 : * for traffic that wants anonymity and protection from traffic
976 : * analysis (such as netflow record retention). That means we want
977 : * to pad it.
978 : */
979 0 : if (circ->base_.n_chan->channel_usage < CHANNEL_USED_FOR_FULL_CIRCS)
980 0 : circ->base_.n_chan->channel_usage = CHANNEL_USED_FOR_FULL_CIRCS;
981 : }
982 :
983 2 : node = node_get_by_id(circ->base_.n_chan->identity_digest);
984 2 : fast = should_use_create_fast_for_circuit(circ);
985 2 : if (!fast) {
986 : /* We know the right onion key: we should send a create cell. */
987 0 : circuit_pick_create_handshake(&cc.cell_type, &cc.handshake_type,
988 0 : circ->cpath->extend_info);
989 : } else {
990 : /* We don't know an onion key, so we need to fall back to CREATE_FAST. */
991 2 : cc.cell_type = CELL_CREATE_FAST;
992 2 : cc.handshake_type = ONION_HANDSHAKE_TYPE_FAST;
993 : }
994 :
995 4 : len = onion_skin_create(cc.handshake_type,
996 2 : circ->cpath->extend_info,
997 2 : &circ->cpath->handshake_state,
998 : cc.onionskin);
999 2 : if (len < 0) {
1000 0 : log_warn(LD_CIRC,"onion_skin_create (first hop) failed.");
1001 0 : return - END_CIRC_REASON_INTERNAL;
1002 : }
1003 2 : cc.handshake_len = len;
1004 :
1005 2 : if (circuit_deliver_create_cell(TO_CIRCUIT(circ), &cc, 0) < 0)
1006 : return - END_CIRC_REASON_RESOURCELIMIT;
1007 2 : tor_trace(TR_SUBSYS(circuit), TR_EV(first_onion_skin), circ, circ->cpath);
1008 :
1009 2 : circ->cpath->state = CPATH_STATE_AWAITING_KEYS;
1010 2 : circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_BUILDING);
1011 2 : log_info(LD_CIRC,"First hop: finished sending %s cell to '%s'",
1012 : fast ? "CREATE_FAST" : "CREATE",
1013 : node ? node_describe(node) : "<unnamed>");
1014 2 : return 0;
1015 : }
1016 :
1017 : /**
1018 : * Called from circuit_send_next_onion_skin() when we find that we have no
1019 : * more hops: mark the circuit as finished, and perform the necessary
1020 : * bookkeeping. Return 0 on success; -reason on failure (if the circuit
1021 : * should be torn down).
1022 : */
1023 : static int
1024 0 : circuit_build_no_more_hops(origin_circuit_t *circ)
1025 : {
1026 0 : guard_usable_t r;
1027 0 : if (! circ->guard_state) {
1028 0 : if (circuit_get_cpath_len(circ) != 1 &&
1029 0 : ! circuit_may_omit_guard(circ) &&
1030 0 : get_options()->UseEntryGuards) {
1031 0 : log_warn(LD_BUG, "%d-hop circuit %p with purpose %d has no "
1032 : "guard state",
1033 : circuit_get_cpath_len(circ), circ, circ->base_.purpose);
1034 : }
1035 : r = GUARD_USABLE_NOW;
1036 : } else {
1037 0 : r = entry_guard_succeeded(&circ->guard_state);
1038 : }
1039 0 : const int is_usable_for_streams = (r == GUARD_USABLE_NOW);
1040 0 : if (r == GUARD_USABLE_NOW) {
1041 0 : circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_OPEN);
1042 0 : } else if (r == GUARD_MAYBE_USABLE_LATER) {
1043 : // Wait till either a better guard succeeds, or till
1044 : // all better guards fail.
1045 0 : circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_GUARD_WAIT);
1046 : } else {
1047 0 : tor_assert_nonfatal(r == GUARD_USABLE_NEVER);
1048 0 : return - END_CIRC_REASON_INTERNAL;
1049 : }
1050 :
1051 : /* XXXX #21422 -- the rest of this branch needs careful thought!
1052 : * Some of the things here need to happen when a circuit becomes
1053 : * mechanically open; some need to happen when it is actually usable.
1054 : * I think I got them right, but more checking would be wise. -NM
1055 : */
1056 :
1057 0 : log_info(LD_CIRC,"circuit built!");
1058 0 : circuit_reset_failure_count(0);
1059 :
1060 0 : if (circ->build_state->onehop_tunnel || circ->has_opened) {
1061 0 : control_event_bootstrap(BOOTSTRAP_STATUS_REQUESTING_STATUS, 0);
1062 : }
1063 :
1064 0 : pathbias_count_build_success(circ);
1065 0 : if (is_usable_for_streams)
1066 0 : circuit_has_opened(circ); /* do other actions as necessary */
1067 :
1068 0 : if (!have_completed_a_circuit() && !circ->build_state->onehop_tunnel) {
1069 0 : const or_options_t *options = get_options();
1070 0 : note_that_we_completed_a_circuit();
1071 : /* FFFF Log a count of known routers here */
1072 0 : log_info(LD_GENERAL,
1073 : "Tor has successfully opened a circuit. "
1074 : "Looks like client functionality is working.");
1075 0 : control_event_bootstrap(BOOTSTRAP_STATUS_DONE, 0);
1076 0 : control_event_client_status(LOG_NOTICE, "CIRCUIT_ESTABLISHED");
1077 0 : clear_broken_connection_map(1);
1078 0 : if (server_mode(options) &&
1079 0 : !router_all_orports_seem_reachable(options)) {
1080 0 : router_do_reachability_checks();
1081 : }
1082 : }
1083 :
1084 : /* We're done with measurement circuits here. Just close them */
1085 0 : if (circ->base_.purpose == CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
1086 0 : circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_FINISHED);
1087 : }
1088 : return 0;
1089 : }
1090 :
1091 : /**
1092 : * Called from circuit_send_next_onion_skin() when we find that we have a hop
1093 : * other than the first that we need to extend to: use <b>hop</b>'s
1094 : * information to extend the circuit another step. Return 0 on success;
1095 : * -reason on failure (if the circuit should be torn down).
1096 : */
1097 : static int
1098 6 : circuit_send_intermediate_onion_skin(origin_circuit_t *circ,
1099 : crypt_path_t *hop)
1100 : {
1101 6 : int len;
1102 6 : extend_cell_t ec;
1103 : /* Relays and bridges can send IPv6 extends. But for clients, it's an
1104 : * obvious version distinguisher. */
1105 6 : const bool include_ipv6 = server_mode(get_options());
1106 6 : memset(&ec, 0, sizeof(ec));
1107 6 : tor_addr_make_unspec(&ec.orport_ipv4.addr);
1108 6 : tor_addr_make_unspec(&ec.orport_ipv6.addr);
1109 :
1110 6 : log_debug(LD_CIRC,"starting to send subsequent skin.");
1111 :
1112 6 : circuit_pick_extend_handshake(&ec.cell_type,
1113 : &ec.create_cell.cell_type,
1114 : &ec.create_cell.handshake_type,
1115 6 : hop->extend_info);
1116 :
1117 6 : const tor_addr_port_t *orport4 =
1118 6 : extend_info_get_orport(hop->extend_info, AF_INET);
1119 6 : const tor_addr_port_t *orport6 =
1120 6 : extend_info_get_orport(hop->extend_info, AF_INET6);
1121 6 : int n_addrs_set = 0;
1122 6 : if (orport4) {
1123 2 : tor_addr_copy(&ec.orport_ipv4.addr, &orport4->addr);
1124 2 : ec.orport_ipv4.port = orport4->port;
1125 2 : ++n_addrs_set;
1126 : }
1127 6 : if (orport6 && include_ipv6) {
1128 1 : tor_addr_copy(&ec.orport_ipv6.addr, &orport6->addr);
1129 1 : ec.orport_ipv6.port = orport6->port;
1130 1 : ++n_addrs_set;
1131 : }
1132 :
1133 6 : if (n_addrs_set == 0) {
1134 3 : log_warn(LD_BUG, "No supported address family found in extend_info.");
1135 3 : return - END_CIRC_REASON_INTERNAL;
1136 : }
1137 3 : memcpy(ec.node_id, hop->extend_info->identity_digest, DIGEST_LEN);
1138 : /* Set the ED25519 identity too -- it will only get included
1139 : * in the extend2 cell if we're configured to use it, though. */
1140 3 : ed25519_pubkey_copy(&ec.ed_pubkey, &hop->extend_info->ed_identity);
1141 :
1142 6 : len = onion_skin_create(ec.create_cell.handshake_type,
1143 3 : hop->extend_info,
1144 : &hop->handshake_state,
1145 : ec.create_cell.onionskin);
1146 3 : if (len < 0) {
1147 3 : log_warn(LD_CIRC,"onion_skin_create failed.");
1148 3 : return - END_CIRC_REASON_INTERNAL;
1149 : }
1150 0 : ec.create_cell.handshake_len = len;
1151 :
1152 0 : log_info(LD_CIRC,"Sending extend relay cell.");
1153 : {
1154 0 : uint8_t command = 0;
1155 0 : uint16_t payload_len=0;
1156 0 : uint8_t payload[RELAY_PAYLOAD_SIZE];
1157 0 : if (extend_cell_format(&command, &payload_len, payload, &ec)<0) {
1158 0 : log_warn(LD_CIRC,"Couldn't format extend cell");
1159 0 : return -END_CIRC_REASON_INTERNAL;
1160 : }
1161 :
1162 : /* send it to hop->prev, because that relay will transfer
1163 : * it to a create cell and then send to hop */
1164 0 : if (relay_send_command_from_edge(0, TO_CIRCUIT(circ),
1165 : command,
1166 : (char*)payload, payload_len,
1167 : hop->prev) < 0)
1168 : return 0; /* circuit is closed */
1169 : }
1170 0 : hop->state = CPATH_STATE_AWAITING_KEYS;
1171 0 : tor_trace(TR_SUBSYS(circuit), TR_EV(intermediate_onion_skin), circ, hop);
1172 0 : return 0;
1173 : }
1174 :
1175 : /** Our clock just jumped by <b>seconds_elapsed</b>. If <b>was_idle</b> is
1176 : * true, then the monotonic time matches; otherwise it doesn't. Assume
1177 : * something has also gone wrong with our network: notify the user, and
1178 : * abandon all not-yet-used circuits. */
1179 : void
1180 3 : circuit_note_clock_jumped(int64_t seconds_elapsed, bool was_idle)
1181 : {
1182 3 : int severity = server_mode(get_options()) ? LOG_WARN : LOG_NOTICE;
1183 3 : if (was_idle) {
1184 1 : tor_log(severity, LD_GENERAL, "Tor has been idle for %"PRId64
1185 : " seconds; assuming established circuits no longer work.",
1186 : (seconds_elapsed));
1187 : } else {
1188 3 : tor_log(severity, LD_GENERAL,
1189 : "Your system clock just jumped %"PRId64" seconds %s; "
1190 : "assuming established circuits no longer work.",
1191 : (
1192 : seconds_elapsed >=0 ? seconds_elapsed : -seconds_elapsed),
1193 : seconds_elapsed >=0 ? "forward" : "backward");
1194 : }
1195 3 : control_event_general_status(LOG_WARN, "CLOCK_JUMPED TIME=%"PRId64
1196 : " IDLE=%d",
1197 : (seconds_elapsed), was_idle?1:0);
1198 : /* so we log when it works again */
1199 3 : note_that_we_maybe_cant_complete_circuits();
1200 3 : control_event_client_status(severity, "CIRCUIT_NOT_ESTABLISHED REASON=%s",
1201 : "CLOCK_JUMPED");
1202 3 : circuit_mark_all_unused_circs();
1203 3 : circuit_mark_all_dirty_circs_as_unusable();
1204 3 : if (seconds_elapsed < 0) {
1205 : /* Restart all the timers in case we jumped a long way into the past. */
1206 1 : reset_all_main_loop_timers();
1207 : }
1208 3 : }
1209 :
1210 : /** A "created" cell <b>reply</b> came back to us on circuit <b>circ</b>.
1211 : * (The body of <b>reply</b> varies depending on what sort of handshake
1212 : * this is.)
1213 : *
1214 : * Calculate the appropriate keys and digests, make sure KH is
1215 : * correct, and initialize this hop of the cpath.
1216 : *
1217 : * Return - reason if we want to mark circ for close, else return 0.
1218 : */
1219 : int
1220 0 : circuit_finish_handshake(origin_circuit_t *circ,
1221 : const created_cell_t *reply)
1222 : {
1223 0 : char keys[CPATH_KEY_MATERIAL_LEN];
1224 0 : crypt_path_t *hop;
1225 0 : int rv;
1226 :
1227 0 : if ((rv = pathbias_count_build_attempt(circ)) < 0) {
1228 0 : log_warn(LD_CIRC, "pathbias_count_build_attempt failed: %d", rv);
1229 0 : return rv;
1230 : }
1231 :
1232 0 : if (circ->cpath->state == CPATH_STATE_AWAITING_KEYS) {
1233 : hop = circ->cpath;
1234 : } else {
1235 0 : hop = cpath_get_next_non_open_hop(circ->cpath);
1236 0 : if (!hop) { /* got an extended when we're all done? */
1237 0 : log_warn(LD_PROTOCOL,"got extended when circ already built? Closing.");
1238 0 : return - END_CIRC_REASON_TORPROTOCOL;
1239 : }
1240 : }
1241 0 : tor_assert(hop->state == CPATH_STATE_AWAITING_KEYS);
1242 :
1243 : {
1244 0 : const char *msg = NULL;
1245 0 : if (onion_skin_client_handshake(hop->handshake_state.tag,
1246 0 : &hop->handshake_state,
1247 0 : reply->reply, reply->handshake_len,
1248 : (uint8_t*)keys, sizeof(keys),
1249 0 : (uint8_t*)hop->rend_circ_nonce,
1250 : &msg) < 0) {
1251 0 : if (msg)
1252 0 : log_warn(LD_CIRC,"onion_skin_client_handshake failed: %s", msg);
1253 0 : return -END_CIRC_REASON_TORPROTOCOL;
1254 : }
1255 : }
1256 :
1257 0 : onion_handshake_state_release(&hop->handshake_state);
1258 :
1259 0 : if (cpath_init_circuit_crypto(hop, keys, sizeof(keys), 0, 0)<0) {
1260 : return -END_CIRC_REASON_TORPROTOCOL;
1261 : }
1262 :
1263 0 : hop->state = CPATH_STATE_OPEN;
1264 0 : log_info(LD_CIRC,"Finished building circuit hop:");
1265 0 : circuit_log_path(LOG_INFO,LD_CIRC,circ);
1266 0 : circuit_event_status(circ, CIRC_EVENT_EXTENDED, 0);
1267 :
1268 0 : return 0;
1269 : }
1270 :
1271 : /** We received a relay truncated cell on circ.
1272 : *
1273 : * Since we don't send truncates currently, getting a truncated
1274 : * means that a connection broke or an extend failed. For now,
1275 : * just give up: force circ to close, and return 0.
1276 : */
1277 : int
1278 1 : circuit_truncated(origin_circuit_t *circ, int reason)
1279 : {
1280 : // crypt_path_t *victim;
1281 : // connection_t *stream;
1282 :
1283 1 : tor_assert(circ);
1284 :
1285 : /* XXX Since we don't send truncates currently, getting a truncated
1286 : * means that a connection broke or an extend failed. For now,
1287 : * just give up.
1288 : */
1289 1 : circuit_mark_for_close(TO_CIRCUIT(circ),
1290 : END_CIRC_REASON_FLAG_REMOTE|reason);
1291 1 : return 0;
1292 :
1293 : #if 0
1294 : while (layer->next != circ->cpath) {
1295 : /* we need to clear out layer->next */
1296 : victim = layer->next;
1297 : log_debug(LD_CIRC, "Killing a layer of the cpath.");
1298 :
1299 : for (stream = circ->p_streams; stream; stream=stream->next_stream) {
1300 : if (stream->cpath_layer == victim) {
1301 : log_info(LD_APP, "Marking stream %d for close because of truncate.",
1302 : stream->stream_id);
1303 : /* no need to send 'end' relay cells,
1304 : * because the other side's already dead
1305 : */
1306 : connection_mark_unattached_ap(stream, END_STREAM_REASON_DESTROY);
1307 : }
1308 : }
1309 :
1310 : layer->next = victim->next;
1311 : cpath_free(victim);
1312 : }
1313 :
1314 : log_info(LD_CIRC, "finished");
1315 : return 0;
1316 : #endif /* 0 */
1317 : }
1318 :
1319 : /** Helper for new_route_len(). Choose a circuit length for purpose
1320 : * <b>purpose</b>: DEFAULT_ROUTE_LEN (+ 1 if someone else chose the
1321 : * exit). If someone else chose the exit, they could be colluding
1322 : * with the exit, so add a randomly selected node to preserve
1323 : * anonymity.
1324 : *
1325 : * Here, "exit node" sometimes means an OR acting as an internal
1326 : * endpoint, rather than as a relay to an external endpoint. This
1327 : * means there need to be at least DEFAULT_ROUTE_LEN routers between
1328 : * us and the internal endpoint to preserve the same anonymity
1329 : * properties that we would get when connecting to an external
1330 : * endpoint. These internal endpoints can include:
1331 : *
1332 : * - Connections to a directory of hidden services
1333 : * (CIRCUIT_PURPOSE_C_GENERAL)
1334 : *
1335 : * - A client connecting to an introduction point, which the hidden
1336 : * service picked (CIRCUIT_PURPOSE_C_INTRODUCING, via
1337 : * circuit_get_open_circ_or_launch() which rewrites it from
1338 : * CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT)
1339 : *
1340 : * - A hidden service connecting to a rendezvous point, which the
1341 : * client picked (CIRCUIT_PURPOSE_S_CONNECT_REND.
1342 : *
1343 : * There are currently two situations where we picked the exit node
1344 : * ourselves, making DEFAULT_ROUTE_LEN a safe circuit length:
1345 : *
1346 : * - We are a hidden service connecting to an introduction point
1347 : * (CIRCUIT_PURPOSE_S_ESTABLISH_INTRO).
1348 : *
1349 : * - We are a router testing its own reachabiity
1350 : * (CIRCUIT_PURPOSE_TESTING, via router_do_reachability_checks())
1351 : *
1352 : * onion_pick_cpath_exit() bypasses us (by not calling
1353 : * new_route_len()) in the one-hop tunnel case, so we don't need to
1354 : * handle that.
1355 : */
1356 : int
1357 15 : route_len_for_purpose(uint8_t purpose, extend_info_t *exit_ei)
1358 : {
1359 15 : int routelen = DEFAULT_ROUTE_LEN;
1360 15 : int known_purpose = 0;
1361 :
1362 15 : if (circuit_should_use_vanguards(purpose)) {
1363 : /* Clients want an extra hop for rends to avoid linkability.
1364 : * Services want it for intro points to avoid publishing their
1365 : * layer3 guards. They want it for hsdir posts to use
1366 : * their full layer3 guard set for those connections.
1367 : * Ex: C - G - L2 - L3 - R
1368 : * S - G - L2 - L3 - HSDIR
1369 : * S - G - L2 - L3 - I
1370 : */
1371 3 : if (purpose == CIRCUIT_PURPOSE_C_ESTABLISH_REND ||
1372 3 : purpose == CIRCUIT_PURPOSE_S_HSDIR_POST ||
1373 : purpose == CIRCUIT_PURPOSE_HS_VANGUARDS ||
1374 : purpose == CIRCUIT_PURPOSE_S_ESTABLISH_INTRO)
1375 : return routelen+1;
1376 :
1377 : /* If we only have Layer2 vanguards, then we do not need
1378 : * the extra hop for linkabilty reasons (see below).
1379 : * This means all hops can be of the form:
1380 : * S/C - G - L2 - M - R/HSDir/I
1381 : */
1382 0 : if (get_options()->HSLayer2Nodes && !get_options()->HSLayer3Nodes)
1383 : return routelen+1;
1384 :
1385 : /* For connections to hsdirs, clients want two extra hops
1386 : * when using layer3 guards, to avoid linkability.
1387 : * Same goes for intro points. Note that the route len
1388 : * includes the intro point or hsdir, hence the +2.
1389 : * Ex: C - G - L2 - L3 - M - I
1390 : * C - G - L2 - L3 - M - HSDIR
1391 : * S - G - L2 - L3 - M - R
1392 : */
1393 0 : if (purpose == CIRCUIT_PURPOSE_S_CONNECT_REND ||
1394 0 : purpose == CIRCUIT_PURPOSE_C_HSDIR_GET ||
1395 : purpose == CIRCUIT_PURPOSE_C_INTRODUCING)
1396 : return routelen+2;
1397 : }
1398 :
1399 12 : if (!exit_ei)
1400 : return routelen;
1401 :
1402 6 : switch (purpose) {
1403 : /* These two purposes connect to a router that we chose, so
1404 : * DEFAULT_ROUTE_LEN is safe. */
1405 : case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO:
1406 : /* hidden service connecting to introduction point */
1407 : case CIRCUIT_PURPOSE_TESTING:
1408 : /* router reachability testing */
1409 : known_purpose = 1;
1410 : break;
1411 :
1412 : /* These three purposes connect to a router that someone else
1413 : * might have chosen, so add an extra hop to protect anonymity. */
1414 3 : case CIRCUIT_PURPOSE_C_GENERAL:
1415 : case CIRCUIT_PURPOSE_C_HSDIR_GET:
1416 : case CIRCUIT_PURPOSE_S_HSDIR_POST:
1417 : /* connecting to hidden service directory */
1418 : case CIRCUIT_PURPOSE_C_INTRODUCING:
1419 : /* client connecting to introduction point */
1420 : case CIRCUIT_PURPOSE_S_CONNECT_REND:
1421 : /* hidden service connecting to rendezvous point */
1422 3 : known_purpose = 1;
1423 3 : routelen++;
1424 3 : break;
1425 :
1426 1 : default:
1427 : /* Got a purpose not listed above along with a chosen exit.
1428 : * Increase the circuit length by one anyway for safety. */
1429 1 : routelen++;
1430 1 : break;
1431 : }
1432 :
1433 6 : if (BUG(exit_ei && !known_purpose)) {
1434 1 : log_warn(LD_BUG, "Unhandled purpose %d with a chosen exit; "
1435 : "assuming routelen %d.", purpose, routelen);
1436 : }
1437 : return routelen;
1438 : }
1439 :
1440 : /** Choose a length for a circuit of purpose <b>purpose</b> and check
1441 : * if enough routers are available.
1442 : *
1443 : * If the routerlist <b>nodes</b> doesn't have enough routers
1444 : * to handle the desired path length, return -1.
1445 : */
1446 : STATIC int
1447 15 : new_route_len(uint8_t purpose, extend_info_t *exit_ei,
1448 : const smartlist_t *nodes)
1449 : {
1450 15 : int routelen;
1451 :
1452 15 : tor_assert(nodes);
1453 :
1454 15 : routelen = route_len_for_purpose(purpose, exit_ei);
1455 :
1456 15 : int num_acceptable_direct = count_acceptable_nodes(nodes, 1);
1457 15 : int num_acceptable_indirect = count_acceptable_nodes(nodes, 0);
1458 :
1459 15 : log_debug(LD_CIRC,"Chosen route length %d (%d direct and %d indirect "
1460 : "routers suitable).", routelen, num_acceptable_direct,
1461 : num_acceptable_indirect);
1462 :
1463 15 : if (num_acceptable_direct < 1 || num_acceptable_indirect < routelen - 1) {
1464 0 : log_info(LD_CIRC,
1465 : "Not enough acceptable routers (%d/%d direct and %d/%d "
1466 : "indirect routers suitable). Discarding this circuit.",
1467 : num_acceptable_direct, routelen,
1468 : num_acceptable_indirect, routelen);
1469 0 : return -1;
1470 : }
1471 :
1472 : return routelen;
1473 : }
1474 :
1475 : /** Return a newly allocated list of uint16_t * for each predicted port not
1476 : * handled by a current circuit. */
1477 : static smartlist_t *
1478 3 : circuit_get_unhandled_ports(time_t now)
1479 : {
1480 3 : smartlist_t *dest = rep_hist_get_predicted_ports(now);
1481 3 : circuit_remove_handled_ports(dest);
1482 3 : return dest;
1483 : }
1484 :
1485 : /** Return 1 if we already have circuits present or on the way for
1486 : * all anticipated ports. Return 0 if we should make more.
1487 : *
1488 : * If we're returning 0, set need_uptime and need_capacity to
1489 : * indicate any requirements that the unhandled ports have.
1490 : */
1491 0 : MOCK_IMPL(int,
1492 : circuit_all_predicted_ports_handled, (time_t now, int *need_uptime,
1493 : int *need_capacity))
1494 : {
1495 0 : int i, enough;
1496 0 : uint16_t *port;
1497 0 : smartlist_t *sl = circuit_get_unhandled_ports(now);
1498 0 : smartlist_t *LongLivedServices = get_options()->LongLivedPorts;
1499 0 : tor_assert(need_uptime);
1500 0 : tor_assert(need_capacity);
1501 : // Always predict need_capacity
1502 0 : *need_capacity = 1;
1503 0 : enough = (smartlist_len(sl) == 0);
1504 0 : for (i = 0; i < smartlist_len(sl); ++i) {
1505 0 : port = smartlist_get(sl, i);
1506 0 : if (smartlist_contains_int_as_string(LongLivedServices, *port))
1507 0 : *need_uptime = 1;
1508 0 : tor_free(port);
1509 : }
1510 0 : smartlist_free(sl);
1511 0 : return enough;
1512 : }
1513 :
1514 : /** Return 1 if <b>node</b> can handle one or more of the ports in
1515 : * <b>needed_ports</b>, else return 0.
1516 : */
1517 : static int
1518 813 : node_handles_some_port(const node_t *node, smartlist_t *needed_ports)
1519 : { /* XXXX MOVE */
1520 813 : int i;
1521 813 : uint16_t port;
1522 :
1523 1509 : for (i = 0; i < smartlist_len(needed_ports); ++i) {
1524 813 : addr_policy_result_t r;
1525 : /* alignment issues aren't a worry for this dereference, since
1526 : needed_ports is explicitly a smartlist of uint16_t's */
1527 813 : port = *(uint16_t *)smartlist_get(needed_ports, i);
1528 813 : tor_assert(port);
1529 813 : if (node)
1530 813 : r = compare_tor_addr_to_node_policy(NULL, port, node);
1531 : else
1532 0 : continue;
1533 813 : if (r != ADDR_POLICY_REJECTED && r != ADDR_POLICY_PROBABLY_REJECTED)
1534 : return 1;
1535 : }
1536 : return 0;
1537 : }
1538 :
1539 : /** Return true iff <b>conn</b> needs another general circuit to be
1540 : * built. */
1541 : static int
1542 0 : ap_stream_wants_exit_attention(connection_t *conn)
1543 : {
1544 0 : entry_connection_t *entry;
1545 0 : if (conn->type != CONN_TYPE_AP)
1546 : return 0;
1547 0 : entry = TO_ENTRY_CONN(conn);
1548 :
1549 0 : if (conn->state == AP_CONN_STATE_CIRCUIT_WAIT &&
1550 0 : !conn->marked_for_close &&
1551 0 : !(entry->want_onehop) && /* ignore one-hop streams */
1552 0 : !(entry->use_begindir) && /* ignore targeted dir fetches */
1553 0 : !(entry->chosen_exit_name) && /* ignore defined streams */
1554 0 : !connection_edge_is_rendezvous_stream(TO_EDGE_CONN(conn)) &&
1555 0 : !circuit_stream_is_being_handled(TO_ENTRY_CONN(conn), 0,
1556 : MIN_CIRCUITS_HANDLING_STREAM))
1557 0 : return 1;
1558 : return 0;
1559 : }
1560 :
1561 : /** Return a pointer to a suitable router to be the exit node for the
1562 : * general-purpose circuit we're about to build.
1563 : *
1564 : * Look through the connection array, and choose a router that maximizes
1565 : * the number of pending streams that can exit from this router.
1566 : *
1567 : * Return NULL if we can't find any suitable routers.
1568 : */
1569 : static const node_t *
1570 3 : choose_good_exit_server_general(router_crn_flags_t flags)
1571 : {
1572 3 : int *n_supported;
1573 3 : int n_pending_connections = 0;
1574 3 : smartlist_t *connections;
1575 3 : int best_support = -1;
1576 3 : int n_best_support=0;
1577 3 : const or_options_t *options = get_options();
1578 3 : const smartlist_t *the_nodes;
1579 3 : const node_t *selected_node=NULL;
1580 3 : const int need_uptime = (flags & CRN_NEED_UPTIME) != 0;
1581 3 : const int need_capacity = (flags & CRN_NEED_CAPACITY) != 0;
1582 :
1583 : /* We should not require guard flags on exits. */
1584 3 : IF_BUG_ONCE(flags & CRN_NEED_GUARD)
1585 : return NULL;
1586 :
1587 : /* We reject single-hop exits for all node positions. */
1588 3 : IF_BUG_ONCE(flags & CRN_DIRECT_CONN)
1589 : return NULL;
1590 :
1591 : /* This isn't the function for picking rendezvous nodes. */
1592 3 : IF_BUG_ONCE(flags & CRN_RENDEZVOUS_V3)
1593 : return NULL;
1594 :
1595 : /* We only want exits to extend if we cannibalize the circuit.
1596 : * But we don't require IPv6 extends yet. */
1597 3 : IF_BUG_ONCE(flags & CRN_INITIATE_IPV6_EXTEND)
1598 : return NULL;
1599 :
1600 3 : connections = get_connection_array();
1601 :
1602 : /* Count how many connections are waiting for a circuit to be built.
1603 : * We use this for log messages now, but in the future we may depend on it.
1604 : */
1605 3 : SMARTLIST_FOREACH(connections, connection_t *, conn,
1606 : {
1607 : if (ap_stream_wants_exit_attention(conn))
1608 : ++n_pending_connections;
1609 : });
1610 : // log_fn(LOG_DEBUG, "Choosing exit node; %d connections are pending",
1611 : // n_pending_connections);
1612 : /* Now we count, for each of the routers in the directory, how many
1613 : * of the pending connections could possibly exit from that
1614 : * router (n_supported[i]). (We can't be sure about cases where we
1615 : * don't know the IP address of the pending connection.)
1616 : *
1617 : * -1 means "Don't use this router at all."
1618 : */
1619 3 : the_nodes = nodelist_get_list();
1620 3 : n_supported = tor_calloc(smartlist_len(the_nodes), sizeof(int));
1621 816 : SMARTLIST_FOREACH_BEGIN(the_nodes, const node_t *, node) {
1622 813 : const int i = node_sl_idx;
1623 813 : if (router_digest_is_me(node->identity)) {
1624 0 : n_supported[i] = -1;
1625 : // log_fn(LOG_DEBUG,"Skipping node %s -- it's me.", router->nickname);
1626 : /* XXX there's probably a reverse predecessor attack here, but
1627 : * it's slow. should we take this out? -RD
1628 : */
1629 0 : continue;
1630 : }
1631 813 : if (!router_can_choose_node(node, flags)) {
1632 0 : n_supported[i] = -1;
1633 0 : continue;
1634 : }
1635 813 : if (node->is_bad_exit) {
1636 0 : n_supported[i] = -1;
1637 0 : continue; /* skip routers that are known to be down or bad exits */
1638 : }
1639 813 : if (routerset_contains_node(options->ExcludeExitNodesUnion_, node)) {
1640 0 : n_supported[i] = -1;
1641 0 : continue; /* user asked us not to use it, no matter what */
1642 : }
1643 813 : if (options->ExitNodes &&
1644 0 : !routerset_contains_node(options->ExitNodes, node)) {
1645 0 : n_supported[i] = -1;
1646 0 : continue; /* not one of our chosen exit nodes */
1647 : }
1648 813 : if (node_exit_policy_rejects_all(node)) {
1649 0 : n_supported[i] = -1;
1650 : // log_fn(LOG_DEBUG,"Skipping node %s (index %d) -- it rejects all.",
1651 : // router->nickname, i);
1652 0 : continue; /* skip routers that reject all */
1653 : }
1654 813 : n_supported[i] = 0;
1655 : /* iterate over connections */
1656 813 : SMARTLIST_FOREACH_BEGIN(connections, connection_t *, conn) {
1657 0 : if (!ap_stream_wants_exit_attention(conn))
1658 0 : continue; /* Skip everything but APs in CIRCUIT_WAIT */
1659 0 : if (connection_ap_can_use_exit(TO_ENTRY_CONN(conn), node)) {
1660 0 : ++n_supported[i];
1661 : // log_fn(LOG_DEBUG,"%s is supported. n_supported[%d] now %d.",
1662 : // router->nickname, i, n_supported[i]);
1663 : } else {
1664 : // log_fn(LOG_DEBUG,"%s (index %d) would reject this stream.",
1665 : // router->nickname, i);
1666 : }
1667 0 : } SMARTLIST_FOREACH_END(conn);
1668 813 : if (n_pending_connections > 0 && n_supported[i] == 0) {
1669 : /* Leave best_support at -1 if that's where it is, so we can
1670 : * distinguish it later. */
1671 0 : continue;
1672 : }
1673 813 : if (n_supported[i] > best_support) {
1674 : /* If this router is better than previous ones, remember its index
1675 : * and goodness, and start counting how many routers are this good. */
1676 : best_support = n_supported[i]; n_best_support=1;
1677 : // log_fn(LOG_DEBUG,"%s is new best supported option so far.",
1678 : // router->nickname);
1679 810 : } else if (n_supported[i] == best_support) {
1680 : /* If this router is _as good_ as the best one, just increment the
1681 : * count of equally good routers.*/
1682 810 : ++n_best_support;
1683 : }
1684 813 : } SMARTLIST_FOREACH_END(node);
1685 3 : log_info(LD_CIRC,
1686 : "Found %d servers that might support %d/%d pending connections.",
1687 : n_best_support, best_support >= 0 ? best_support : 0,
1688 : n_pending_connections);
1689 :
1690 : /* If any routers definitely support any pending connections, choose one
1691 : * at random. */
1692 3 : if (best_support > 0) {
1693 0 : smartlist_t *supporting = smartlist_new();
1694 :
1695 0 : SMARTLIST_FOREACH(the_nodes, const node_t *, node, {
1696 : if (n_supported[node_sl_idx] == best_support)
1697 : smartlist_add(supporting, (void*)node);
1698 : });
1699 :
1700 0 : selected_node = node_sl_choose_by_bandwidth(supporting, WEIGHT_FOR_EXIT);
1701 0 : smartlist_free(supporting);
1702 : } else {
1703 : /* Either there are no pending connections, or no routers even seem to
1704 : * possibly support any of them. Choose a router at random that satisfies
1705 : * at least one predicted exit port. */
1706 :
1707 3 : int attempt;
1708 3 : smartlist_t *needed_ports, *supporting;
1709 :
1710 3 : if (best_support == -1) {
1711 0 : if (need_uptime || need_capacity) {
1712 0 : log_info(LD_CIRC,
1713 : "We couldn't find any live%s%s routers; falling back "
1714 : "to list of all routers.",
1715 : need_capacity?", fast":"",
1716 : need_uptime?", stable":"");
1717 0 : tor_free(n_supported);
1718 0 : flags &= ~(CRN_NEED_UPTIME|CRN_NEED_CAPACITY);
1719 0 : return choose_good_exit_server_general(flags);
1720 : }
1721 0 : log_notice(LD_CIRC, "All routers are down or won't exit%s -- "
1722 : "choosing a doomed exit at random.",
1723 : options->ExcludeExitNodesUnion_ ? " or are Excluded" : "");
1724 : }
1725 3 : supporting = smartlist_new();
1726 3 : needed_ports = circuit_get_unhandled_ports(time(NULL));
1727 6 : for (attempt = 0; attempt < 2; attempt++) {
1728 : /* try once to pick only from routers that satisfy a needed port,
1729 : * then if there are none, pick from any that support exiting. */
1730 816 : SMARTLIST_FOREACH_BEGIN(the_nodes, const node_t *, node) {
1731 813 : if (n_supported[node_sl_idx] != -1 &&
1732 813 : (attempt || node_handles_some_port(node, needed_ports))) {
1733 : // log_fn(LOG_DEBUG,"Try %d: '%s' is a possibility.",
1734 : // try, router->nickname);
1735 117 : smartlist_add(supporting, (void*)node);
1736 : }
1737 813 : } SMARTLIST_FOREACH_END(node);
1738 :
1739 3 : selected_node = node_sl_choose_by_bandwidth(supporting, WEIGHT_FOR_EXIT);
1740 3 : if (selected_node)
1741 : break;
1742 0 : smartlist_clear(supporting);
1743 : /* If we reach this point, we can't actually support any unhandled
1744 : * predicted ports, so clear all the remaining ones. */
1745 0 : if (smartlist_len(needed_ports))
1746 0 : rep_hist_remove_predicted_ports(needed_ports);
1747 : }
1748 6 : SMARTLIST_FOREACH(needed_ports, uint16_t *, cp, tor_free(cp));
1749 3 : smartlist_free(needed_ports);
1750 3 : smartlist_free(supporting);
1751 : }
1752 :
1753 3 : tor_free(n_supported);
1754 3 : if (selected_node) {
1755 3 : log_info(LD_CIRC, "Chose exit server '%s'", node_describe(selected_node));
1756 3 : return selected_node;
1757 : }
1758 0 : if (options->ExitNodes) {
1759 0 : log_warn(LD_CIRC,
1760 : "No exits in ExitNodes%s seem to be running: "
1761 : "can't choose an exit.",
1762 : options->ExcludeExitNodesUnion_ ?
1763 : ", except possibly those excluded by your configuration, " : "");
1764 : }
1765 : return NULL;
1766 : }
1767 :
1768 : /* Pick a Rendezvous Point for our HS circuits according to <b>flags</b>. */
1769 : static const node_t *
1770 0 : pick_rendezvous_node(router_crn_flags_t flags)
1771 : {
1772 0 : const or_options_t *options = get_options();
1773 0 : return router_choose_random_node(NULL, options->ExcludeNodes, flags);
1774 : }
1775 :
1776 : /*
1777 : * Helper function to pick a configured restricted middle node
1778 : * (either HSLayer2Nodes or HSLayer3Nodes).
1779 : *
1780 : * Make sure that the node we chose is alive, and not excluded,
1781 : * and return it.
1782 : *
1783 : * The exclude_set is a routerset of nodes that the selected node
1784 : * must not match, and the exclude_list is a simple list of nodes
1785 : * that the selected node must not be in. Either or both may be
1786 : * NULL.
1787 : *
1788 : * Return NULL if no usable nodes could be found. */
1789 : static const node_t *
1790 6 : pick_restricted_middle_node(router_crn_flags_t flags,
1791 : const routerset_t *pick_from,
1792 : const routerset_t *exclude_set,
1793 : const smartlist_t *exclude_list,
1794 : int position_hint)
1795 : {
1796 6 : const node_t *middle_node = NULL;
1797 :
1798 6 : smartlist_t *allowlisted_live_middles = smartlist_new();
1799 6 : smartlist_t *all_live_nodes = smartlist_new();
1800 :
1801 6 : tor_assert(pick_from);
1802 :
1803 : /* Add all running nodes to all_live_nodes */
1804 6 : router_add_running_nodes_to_smartlist(all_live_nodes, flags);
1805 :
1806 : /* Filter all_live_nodes to only add live *and* allowlisted middles
1807 : * to the list allowlisted_live_middles. */
1808 1632 : SMARTLIST_FOREACH_BEGIN(all_live_nodes, node_t *, live_node) {
1809 1626 : if (routerset_contains_node(pick_from, live_node)) {
1810 30 : smartlist_add(allowlisted_live_middles, live_node);
1811 : }
1812 1626 : } SMARTLIST_FOREACH_END(live_node);
1813 :
1814 : /* Honor ExcludeNodes */
1815 6 : if (exclude_set) {
1816 0 : routerset_subtract_nodes(allowlisted_live_middles, exclude_set);
1817 : }
1818 :
1819 6 : if (exclude_list) {
1820 6 : smartlist_subtract(allowlisted_live_middles, exclude_list);
1821 : }
1822 :
1823 : /**
1824 : * Max number of restricted nodes before we alert the user and try
1825 : * to load balance for them.
1826 : *
1827 : * The most aggressive vanguard design had 16 nodes at layer3.
1828 : * Let's give a small ceiling above that. */
1829 : #define MAX_SANE_RESTRICTED_NODES 20
1830 : /* If the user (or associated tor controller) selected only a few nodes,
1831 : * assume they took load balancing into account and don't do it for them.
1832 : *
1833 : * If there are a lot of nodes in here, assume they did not load balance
1834 : * and do it for them, but also warn them that they may be Doing It Wrong.
1835 : */
1836 6 : if (smartlist_len(allowlisted_live_middles) <=
1837 : MAX_SANE_RESTRICTED_NODES) {
1838 6 : middle_node = smartlist_choose(allowlisted_live_middles);
1839 : } else {
1840 0 : static ratelim_t pinned_notice_limit = RATELIM_INIT(24*3600);
1841 0 : log_fn_ratelim(&pinned_notice_limit, LOG_NOTICE, LD_CIRC,
1842 : "Your _HSLayer%dNodes setting has resulted "
1843 : "in %d total nodes. This is a lot of nodes. "
1844 : "You may want to consider using a Tor controller "
1845 : "to select and update a smaller set of nodes instead.",
1846 : position_hint, smartlist_len(allowlisted_live_middles));
1847 :
1848 : /* NO_WEIGHTING here just means don't take node flags into account
1849 : * (ie: use consensus measurement only). This is done so that
1850 : * we don't further surprise the user by not using Exits that they
1851 : * specified at all */
1852 0 : middle_node = node_sl_choose_by_bandwidth(allowlisted_live_middles,
1853 : NO_WEIGHTING);
1854 : }
1855 :
1856 6 : smartlist_free(allowlisted_live_middles);
1857 6 : smartlist_free(all_live_nodes);
1858 :
1859 6 : return middle_node;
1860 : }
1861 :
1862 : /** Return a pointer to a suitable router to be the exit node for the
1863 : * circuit of purpose <b>purpose</b> that we're about to build (or NULL
1864 : * if no router is suitable).
1865 : *
1866 : * For general-purpose circuits, pass it off to
1867 : * choose_good_exit_server_general()
1868 : *
1869 : * For client-side rendezvous circuits, choose a random node, weighted
1870 : * toward the preferences in 'options'.
1871 : */
1872 : static const node_t *
1873 6 : choose_good_exit_server(origin_circuit_t *circ,
1874 : router_crn_flags_t flags, int is_internal)
1875 : {
1876 6 : const or_options_t *options = get_options();
1877 6 : flags |= CRN_NEED_DESC;
1878 :
1879 6 : switch (TO_CIRCUIT(circ)->purpose) {
1880 3 : case CIRCUIT_PURPOSE_C_HSDIR_GET:
1881 : case CIRCUIT_PURPOSE_S_HSDIR_POST:
1882 : case CIRCUIT_PURPOSE_HS_VANGUARDS:
1883 : /* For these three, we want to pick the exit like a middle hop,
1884 : * since it should be random. */
1885 3 : tor_assert_nonfatal(is_internal);
1886 6 : FALLTHROUGH;
1887 : case CIRCUIT_PURPOSE_C_GENERAL:
1888 6 : if (is_internal) /* pick it like a middle hop */
1889 3 : return router_choose_random_node(NULL, options->ExcludeNodes, flags);
1890 : else
1891 3 : return choose_good_exit_server_general(flags);
1892 0 : case CIRCUIT_PURPOSE_C_ESTABLISH_REND:
1893 : {
1894 : /* Pick a new RP */
1895 0 : const node_t *rendezvous_node = pick_rendezvous_node(flags);
1896 0 : log_info(LD_REND, "Picked new RP: %s",
1897 : safe_str_client(node_describe(rendezvous_node)));
1898 0 : return rendezvous_node;
1899 : }
1900 : }
1901 0 : log_warn(LD_BUG,"Unhandled purpose %d", TO_CIRCUIT(circ)->purpose);
1902 0 : tor_fragile_assert();
1903 : return NULL;
1904 : }
1905 :
1906 : /** Log a warning if the user specified an exit for the circuit that
1907 : * has been excluded from use by ExcludeNodes or ExcludeExitNodes. */
1908 : static void
1909 0 : warn_if_last_router_excluded(origin_circuit_t *circ,
1910 : const extend_info_t *exit_ei)
1911 : {
1912 0 : const or_options_t *options = get_options();
1913 0 : routerset_t *rs = options->ExcludeNodes;
1914 0 : const char *description;
1915 0 : uint8_t purpose = circ->base_.purpose;
1916 :
1917 0 : if (circ->build_state->onehop_tunnel)
1918 : return;
1919 :
1920 0 : switch (purpose)
1921 : {
1922 0 : default:
1923 : case CIRCUIT_PURPOSE_OR:
1924 : case CIRCUIT_PURPOSE_INTRO_POINT:
1925 : case CIRCUIT_PURPOSE_REND_POINT_WAITING:
1926 : case CIRCUIT_PURPOSE_REND_ESTABLISHED:
1927 0 : log_warn(LD_BUG, "Called on non-origin circuit (purpose %d, %s)",
1928 : (int)purpose,
1929 : circuit_purpose_to_string(purpose));
1930 0 : return;
1931 0 : case CIRCUIT_PURPOSE_S_HSDIR_POST:
1932 : case CIRCUIT_PURPOSE_C_HSDIR_GET:
1933 : case CIRCUIT_PURPOSE_C_GENERAL:
1934 0 : if (circ->build_state->is_internal)
1935 : return;
1936 0 : description = "requested exit node";
1937 0 : rs = options->ExcludeExitNodesUnion_;
1938 0 : break;
1939 : case CIRCUIT_PURPOSE_C_INTRODUCING:
1940 : case CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT:
1941 : case CIRCUIT_PURPOSE_C_INTRODUCE_ACKED:
1942 : case CIRCUIT_PURPOSE_S_ESTABLISH_INTRO:
1943 : case CIRCUIT_PURPOSE_S_CONNECT_REND:
1944 : case CIRCUIT_PURPOSE_S_REND_JOINED:
1945 : case CIRCUIT_PURPOSE_TESTING:
1946 : return;
1947 : case CIRCUIT_PURPOSE_C_ESTABLISH_REND:
1948 : case CIRCUIT_PURPOSE_C_REND_READY:
1949 : case CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED:
1950 : case CIRCUIT_PURPOSE_C_REND_JOINED:
1951 : description = "chosen rendezvous point";
1952 : break;
1953 0 : case CIRCUIT_PURPOSE_CONTROLLER:
1954 0 : rs = options->ExcludeExitNodesUnion_;
1955 0 : description = "controller-selected circuit target";
1956 0 : break;
1957 : }
1958 :
1959 0 : if (routerset_contains_extendinfo(rs, exit_ei)) {
1960 : /* We should never get here if StrictNodes is set to 1. */
1961 0 : if (options->StrictNodes) {
1962 0 : log_warn(LD_BUG, "Using %s '%s' which is listed in ExcludeNodes%s, "
1963 : "even though StrictNodes is set. Please report. "
1964 : "(Circuit purpose: %s)",
1965 : description, extend_info_describe(exit_ei),
1966 : rs==options->ExcludeNodes?"":" or ExcludeExitNodes",
1967 : circuit_purpose_to_string(purpose));
1968 : } else {
1969 0 : log_warn(LD_CIRC, "Using %s '%s' which is listed in "
1970 : "ExcludeNodes%s, because no better options were available. To "
1971 : "prevent this (and possibly break your Tor functionality), "
1972 : "set the StrictNodes configuration option. "
1973 : "(Circuit purpose: %s)",
1974 : description, extend_info_describe(exit_ei),
1975 : rs==options->ExcludeNodes?"":" or ExcludeExitNodes",
1976 : circuit_purpose_to_string(purpose));
1977 : }
1978 0 : circuit_log_path(LOG_WARN, LD_CIRC, circ);
1979 : }
1980 :
1981 : return;
1982 : }
1983 :
1984 : /* Return a set of generic CRN_* flags based on <b>state</b>.
1985 : *
1986 : * Called for every position in the circuit. */
1987 : STATIC int
1988 20 : cpath_build_state_to_crn_flags(const cpath_build_state_t *state)
1989 : {
1990 20 : router_crn_flags_t flags = 0;
1991 : /* These flags apply to entry, middle, and exit nodes.
1992 : * If a flag only applies to a specific position, it should be checked in
1993 : * that function. */
1994 20 : if (state->need_uptime)
1995 3 : flags |= CRN_NEED_UPTIME;
1996 20 : if (state->need_capacity)
1997 3 : flags |= CRN_NEED_CAPACITY;
1998 20 : return flags;
1999 : }
2000 :
2001 : /* Return the CRN_INITIATE_IPV6_EXTEND flag, based on <b>state</b> and
2002 : * <b>cur_len</b>.
2003 : *
2004 : * Only called for middle nodes (for now). Must not be called on single-hop
2005 : * circuits. */
2006 : STATIC int
2007 15 : cpath_build_state_to_crn_ipv6_extend_flag(const cpath_build_state_t *state,
2008 : int cur_len)
2009 : {
2010 15 : IF_BUG_ONCE(state->desired_path_len < 2)
2011 : return 0;
2012 :
2013 : /* The last node is the relay doing the self-test. So we want to extend over
2014 : * IPv6 from the second-last node. */
2015 14 : if (state->is_ipv6_selftest && cur_len == state->desired_path_len - 2)
2016 : return CRN_INITIATE_IPV6_EXTEND;
2017 : else
2018 13 : return 0;
2019 : }
2020 :
2021 : /** Decide a suitable length for circ's cpath, and pick an exit
2022 : * router (or use <b>exit</b> if provided). Store these in the
2023 : * cpath.
2024 : *
2025 : * If <b>is_hs_v3_rp_circuit</b> is set, then this exit should be suitable to
2026 : * be used as an HS v3 rendezvous point.
2027 : *
2028 : * Return 0 if ok, -1 if circuit should be closed. */
2029 : STATIC int
2030 6 : onion_pick_cpath_exit(origin_circuit_t *circ, extend_info_t *exit_ei,
2031 : int is_hs_v3_rp_circuit)
2032 : {
2033 6 : cpath_build_state_t *state = circ->build_state;
2034 :
2035 6 : if (state->onehop_tunnel) {
2036 0 : log_debug(LD_CIRC, "Launching a one-hop circuit for dir tunnel%s.",
2037 : (hs_service_allow_non_anonymous_connection(get_options()) ?
2038 : ", or intro or rendezvous connection" : ""));
2039 0 : state->desired_path_len = 1;
2040 : } else {
2041 6 : int r = new_route_len(circ->base_.purpose, exit_ei, nodelist_get_list());
2042 6 : if (r < 1) /* must be at least 1 */
2043 : return -1;
2044 6 : state->desired_path_len = r;
2045 : }
2046 :
2047 6 : if (exit_ei) { /* the circuit-builder pre-requested one */
2048 0 : warn_if_last_router_excluded(circ, exit_ei);
2049 0 : log_info(LD_CIRC,"Using requested exit node '%s'",
2050 : extend_info_describe(exit_ei));
2051 0 : exit_ei = extend_info_dup(exit_ei);
2052 : } else { /* we have to decide one */
2053 6 : router_crn_flags_t flags = CRN_NEED_DESC;
2054 6 : flags |= cpath_build_state_to_crn_flags(state);
2055 : /* Some internal exits are one hop, for example directory connections.
2056 : * (Guards are always direct, middles are never direct.) */
2057 6 : if (state->onehop_tunnel)
2058 0 : flags |= CRN_DIRECT_CONN;
2059 6 : if (is_hs_v3_rp_circuit)
2060 0 : flags |= CRN_RENDEZVOUS_V3;
2061 6 : const node_t *node =
2062 6 : choose_good_exit_server(circ, flags, state->is_internal);
2063 6 : if (!node) {
2064 0 : log_warn(LD_CIRC,"Failed to choose an exit server");
2065 0 : return -1;
2066 : }
2067 6 : exit_ei = extend_info_from_node(node, state->onehop_tunnel);
2068 6 : if (BUG(exit_ei == NULL))
2069 0 : return -1;
2070 : }
2071 6 : state->chosen_exit = exit_ei;
2072 6 : return 0;
2073 : }
2074 :
2075 : /** Give <b>circ</b> a new exit destination to <b>exit</b>, and add a
2076 : * hop to the cpath reflecting this. Don't send the next extend cell --
2077 : * the caller will do this if it wants to.
2078 : */
2079 : int
2080 0 : circuit_append_new_exit(origin_circuit_t *circ, extend_info_t *exit_ei)
2081 : {
2082 0 : cpath_build_state_t *state;
2083 0 : tor_assert(exit_ei);
2084 0 : tor_assert(circ);
2085 :
2086 0 : state = circ->build_state;
2087 0 : tor_assert(state);
2088 0 : extend_info_free(state->chosen_exit);
2089 0 : state->chosen_exit = extend_info_dup(exit_ei);
2090 :
2091 0 : ++circ->build_state->desired_path_len;
2092 0 : cpath_append_hop(&circ->cpath, exit_ei);
2093 0 : return 0;
2094 : }
2095 :
2096 : /** Take an open <b>circ</b>, and add a new hop at the end, based on
2097 : * <b>info</b>. Set its state back to CIRCUIT_STATE_BUILDING, and then
2098 : * send the next extend cell to begin connecting to that hop.
2099 : */
2100 : int
2101 0 : circuit_extend_to_new_exit(origin_circuit_t *circ, extend_info_t *exit_ei)
2102 : {
2103 0 : int err_reason = 0;
2104 0 : warn_if_last_router_excluded(circ, exit_ei);
2105 :
2106 0 : tor_gettimeofday(&circ->base_.timestamp_began);
2107 :
2108 0 : circuit_append_new_exit(circ, exit_ei);
2109 0 : circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_BUILDING);
2110 0 : if ((err_reason = circuit_send_next_onion_skin(circ))<0) {
2111 0 : log_warn(LD_CIRC, "Couldn't extend circuit to new point %s.",
2112 : extend_info_describe(exit_ei));
2113 0 : circuit_mark_for_close(TO_CIRCUIT(circ), -err_reason);
2114 0 : return -1;
2115 : }
2116 :
2117 : // XXX: Should cannibalized circuits be dirty or not? Not easy to say..
2118 :
2119 : return 0;
2120 : }
2121 :
2122 : /** Return the number of routers in <b>nodes</b> that are currently up and
2123 : * available for building circuits through.
2124 : *
2125 : * If <b>direct</b> is true, only count nodes that are suitable for direct
2126 : * connections. Counts nodes regardless of whether their addresses are
2127 : * preferred.
2128 : */
2129 12 : MOCK_IMPL(STATIC int,
2130 : count_acceptable_nodes, (const smartlist_t *nodes, int direct))
2131 : {
2132 12 : int num=0;
2133 12 : int flags = CRN_NEED_DESC;
2134 :
2135 12 : if (direct)
2136 6 : flags |= CRN_DIRECT_CONN;
2137 :
2138 3264 : SMARTLIST_FOREACH_BEGIN(nodes, const node_t *, node) {
2139 : // log_debug(LD_CIRC,
2140 : // "Contemplating whether router %d (%s) is a new option.",
2141 : // i, r->nickname);
2142 3252 : if (!router_can_choose_node(node, flags))
2143 0 : continue;
2144 3252 : ++num;
2145 3252 : } SMARTLIST_FOREACH_END(node);
2146 :
2147 : // log_debug(LD_CIRC,"I like %d. num_acceptable_routers now %d.",i, num);
2148 :
2149 12 : return num;
2150 : }
2151 :
2152 : /**
2153 : * Build the exclude list for vanguard circuits.
2154 : *
2155 : * For vanguard circuits we exclude all the already chosen nodes (including the
2156 : * exit) from being middle hops to prevent the creation of A - B - A subpaths.
2157 : * We also allow the 4th hop to be the same as the guard node so as to not leak
2158 : * guard information to RP/IP/HSDirs.
2159 : *
2160 : * For vanguard circuits, we don't apply any subnet or family restrictions.
2161 : * This is to avoid impossible-to-build circuit paths, or just situations where
2162 : * our earlier guards prevent us from using most of our later ones.
2163 : *
2164 : * The alternative is building the circuit in reverse. Reverse calls to
2165 : * onion_extend_cpath() (ie: select outer hops first) would then have the
2166 : * property that you don't gain information about inner hops by observing
2167 : * outer ones. See https://bugs.torproject.org/tpo/core/tor/24487
2168 : * for this.
2169 : *
2170 : * (Note further that we still exclude the exit to prevent A - B - A
2171 : * at the end of the path. */
2172 : static smartlist_t *
2173 6 : build_vanguard_middle_exclude_list(uint8_t purpose,
2174 : cpath_build_state_t *state,
2175 : crypt_path_t *head,
2176 : int cur_len)
2177 : {
2178 6 : smartlist_t *excluded;
2179 6 : const node_t *r;
2180 6 : crypt_path_t *cpath;
2181 6 : int i;
2182 :
2183 6 : (void) purpose;
2184 :
2185 6 : excluded = smartlist_new();
2186 :
2187 : /* Add the exit to the exclude list (note that the exit/last hop is always
2188 : * chosen first in circuit_establish_circuit()). */
2189 6 : if ((r = build_state_get_exit_node(state))) {
2190 6 : smartlist_add(excluded, (node_t*)r);
2191 : }
2192 :
2193 : /* If we are picking the 4th hop, allow that node to be the guard too.
2194 : * This prevents us from avoiding the Guard for those hops, which
2195 : * gives the adversary information about our guard if they control
2196 : * the RP, IP, or HSDIR. We don't do this check based on purpose
2197 : * because we also want to allow HS_VANGUARDS pre-build circuits
2198 : * to use the guard for that last hop.
2199 : */
2200 6 : if (cur_len == DEFAULT_ROUTE_LEN+1) {
2201 : /* Skip the first hop for the exclude list below */
2202 0 : head = head->next;
2203 0 : cur_len--;
2204 : }
2205 :
2206 15 : for (i = 0, cpath = head; cpath && i < cur_len; ++i, cpath=cpath->next) {
2207 9 : if ((r = node_get_by_id(cpath->extend_info->identity_digest))) {
2208 9 : smartlist_add(excluded, (node_t*)r);
2209 : }
2210 : }
2211 :
2212 6 : return excluded;
2213 : }
2214 :
2215 : /**
2216 : * Build a list of nodes to exclude from the choice of this middle
2217 : * hop, based on already chosen nodes.
2218 : */
2219 : static smartlist_t *
2220 9 : build_middle_exclude_list(uint8_t purpose,
2221 : cpath_build_state_t *state,
2222 : crypt_path_t *head,
2223 : int cur_len)
2224 : {
2225 9 : smartlist_t *excluded;
2226 9 : const node_t *r;
2227 9 : crypt_path_t *cpath;
2228 9 : int i;
2229 :
2230 : /** Vanguard circuits have their own path selection rules */
2231 9 : if (circuit_should_use_vanguards(purpose)) {
2232 6 : return build_vanguard_middle_exclude_list(purpose, state, head, cur_len);
2233 : }
2234 :
2235 3 : excluded = smartlist_new();
2236 :
2237 : /* For non-vanguard circuits, add the exit and its family to the exclude list
2238 : * (note that the exit/last hop is always chosen first in
2239 : * circuit_establish_circuit()). */
2240 3 : if ((r = build_state_get_exit_node(state))) {
2241 3 : nodelist_add_node_and_family(excluded, r);
2242 : }
2243 :
2244 : /* also exclude all other already chosen nodes and their family */
2245 6 : for (i = 0, cpath = head; cpath && i < cur_len; ++i, cpath=cpath->next) {
2246 3 : if ((r = node_get_by_id(cpath->extend_info->identity_digest))) {
2247 3 : nodelist_add_node_and_family(excluded, r);
2248 : }
2249 : }
2250 :
2251 : return excluded;
2252 : }
2253 :
2254 : /** Return true if we MUST use vanguards for picking this middle node. */
2255 : static int
2256 9 : middle_node_must_be_vanguard(const or_options_t *options,
2257 : uint8_t purpose, int cur_len)
2258 : {
2259 : /* If this is not a hidden service circuit, don't use vanguards */
2260 9 : if (!circuit_purpose_is_hidden_service(purpose)) {
2261 : return 0;
2262 : }
2263 :
2264 : /* If we have sticky L2 nodes, and this is an L2 pick, use vanguards */
2265 6 : if (options->HSLayer2Nodes && cur_len == 1) {
2266 : return 1;
2267 : }
2268 :
2269 : /* If we have sticky L3 nodes, and this is an L3 pick, use vanguards */
2270 3 : if (options->HSLayer3Nodes && cur_len == 2) {
2271 3 : return 1;
2272 : }
2273 :
2274 : return 0;
2275 : }
2276 :
2277 : /** Pick a sticky vanguard middle node or return NULL if not found.
2278 : * See doc of pick_restricted_middle_node() for argument details. */
2279 : static const node_t *
2280 6 : pick_vanguard_middle_node(const or_options_t *options,
2281 : router_crn_flags_t flags, int cur_len,
2282 : const smartlist_t *excluded)
2283 : {
2284 6 : const routerset_t *vanguard_routerset = NULL;
2285 6 : const node_t *node = NULL;
2286 :
2287 : /* Pick the right routerset based on the current hop */
2288 6 : if (cur_len == 1) {
2289 3 : vanguard_routerset = options->HSLayer2Nodes;
2290 3 : } else if (cur_len == 2) {
2291 3 : vanguard_routerset = options->HSLayer3Nodes;
2292 : } else {
2293 : /* guaranteed by middle_node_should_be_vanguard() */
2294 0 : tor_assert_nonfatal_unreached();
2295 0 : return NULL;
2296 : }
2297 :
2298 12 : node = pick_restricted_middle_node(flags, vanguard_routerset,
2299 6 : options->ExcludeNodes, excluded,
2300 : cur_len+1);
2301 :
2302 6 : if (!node) {
2303 0 : static ratelim_t pinned_warning_limit = RATELIM_INIT(300);
2304 0 : log_fn_ratelim(&pinned_warning_limit, LOG_WARN, LD_CIRC,
2305 : "Could not find a node that matches the configured "
2306 : "_HSLayer%dNodes set", cur_len+1);
2307 : }
2308 :
2309 : return node;
2310 : }
2311 :
2312 : /** A helper function used by onion_extend_cpath(). Use <b>purpose</b>
2313 : * and <b>state</b> and the cpath <b>head</b> (currently populated only
2314 : * to length <b>cur_len</b> to decide a suitable middle hop for a
2315 : * circuit. In particular, make sure we don't pick the exit node or its
2316 : * family, and make sure we don't duplicate any previous nodes or their
2317 : * families. */
2318 : static const node_t *
2319 9 : choose_good_middle_server(uint8_t purpose,
2320 : cpath_build_state_t *state,
2321 : crypt_path_t *head,
2322 : int cur_len)
2323 : {
2324 9 : const node_t *choice;
2325 9 : smartlist_t *excluded;
2326 9 : const or_options_t *options = get_options();
2327 9 : router_crn_flags_t flags = CRN_NEED_DESC;
2328 9 : tor_assert(CIRCUIT_PURPOSE_MIN_ <= purpose &&
2329 : purpose <= CIRCUIT_PURPOSE_MAX_);
2330 :
2331 9 : log_debug(LD_CIRC, "Contemplating intermediate hop #%d: random choice.",
2332 : cur_len+1);
2333 :
2334 9 : excluded = build_middle_exclude_list(purpose, state, head, cur_len);
2335 :
2336 9 : flags |= cpath_build_state_to_crn_flags(state);
2337 9 : flags |= cpath_build_state_to_crn_ipv6_extend_flag(state, cur_len);
2338 :
2339 : /** If a hidden service circuit wants a specific middle node, pin it. */
2340 9 : if (middle_node_must_be_vanguard(options, purpose, cur_len)) {
2341 6 : log_debug(LD_GENERAL, "Picking a sticky node (cur_len = %d)", cur_len);
2342 6 : choice = pick_vanguard_middle_node(options, flags, cur_len, excluded);
2343 6 : smartlist_free(excluded);
2344 6 : return choice;
2345 : }
2346 :
2347 3 : if (options->MiddleNodes) {
2348 0 : smartlist_t *sl = smartlist_new();
2349 0 : routerset_get_all_nodes(sl, options->MiddleNodes,
2350 0 : options->ExcludeNodes, 1);
2351 :
2352 0 : smartlist_subtract(sl, excluded);
2353 :
2354 0 : choice = node_sl_choose_by_bandwidth(sl, WEIGHT_FOR_MID);
2355 0 : smartlist_free(sl);
2356 0 : if (choice) {
2357 0 : log_fn(LOG_INFO, LD_CIRC, "Chose fixed middle node: %s",
2358 : hex_str(choice->identity, DIGEST_LEN));
2359 : } else {
2360 0 : log_fn(LOG_NOTICE, LD_CIRC, "Restricted middle not available");
2361 : }
2362 : } else {
2363 3 : choice = router_choose_random_node(excluded, options->ExcludeNodes, flags);
2364 : }
2365 3 : smartlist_free(excluded);
2366 3 : return choice;
2367 : }
2368 :
2369 : /** Pick a good entry server for the circuit to be built according to
2370 : * <b>state</b>. Don't reuse a chosen exit (if any), don't use this
2371 : * router (if we're an OR), and respect firewall settings; if we're
2372 : * configured to use entry guards, return one.
2373 : *
2374 : * Set *<b>guard_state_out</b> to information about the guard that
2375 : * we're selecting, which we'll use later to remember whether the
2376 : * guard worked or not.
2377 : */
2378 : const node_t *
2379 6 : choose_good_entry_server(uint8_t purpose, cpath_build_state_t *state,
2380 : circuit_guard_state_t **guard_state_out)
2381 : {
2382 6 : const node_t *choice;
2383 6 : smartlist_t *excluded;
2384 6 : const or_options_t *options = get_options();
2385 : /* If possible, choose an entry server with a preferred address,
2386 : * otherwise, choose one with an allowed address */
2387 6 : router_crn_flags_t flags = (CRN_NEED_GUARD|CRN_NEED_DESC|CRN_PREF_ADDR|
2388 : CRN_DIRECT_CONN);
2389 6 : const node_t *node;
2390 :
2391 : /* Once we used this function to select a node to be a guard. We had
2392 : * 'state == NULL' be the signal for that. But we don't do that any more.
2393 : */
2394 6 : tor_assert_nonfatal(state);
2395 :
2396 6 : if (state && options->UseEntryGuards &&
2397 0 : (purpose != CIRCUIT_PURPOSE_TESTING || options->BridgeRelay)) {
2398 : /* This request is for an entry server to use for a regular circuit,
2399 : * and we use entry guard nodes. Just return one of the guard nodes. */
2400 6 : tor_assert(guard_state_out);
2401 6 : return guards_choose_guard(state, purpose, guard_state_out);
2402 : }
2403 :
2404 0 : excluded = smartlist_new();
2405 :
2406 0 : if (state && (node = build_state_get_exit_node(state))) {
2407 : /* Exclude the exit node from the state, if we have one. Also exclude its
2408 : * family. */
2409 0 : nodelist_add_node_and_family(excluded, node);
2410 : }
2411 :
2412 0 : if (state) {
2413 0 : flags |= cpath_build_state_to_crn_flags(state);
2414 : }
2415 :
2416 0 : choice = router_choose_random_node(excluded, options->ExcludeNodes, flags);
2417 0 : smartlist_free(excluded);
2418 0 : return choice;
2419 : }
2420 :
2421 : /** Choose a suitable next hop for the circuit <b>circ</b>.
2422 : * Append the hop info to circ->cpath.
2423 : *
2424 : * Return 1 if the path is complete, 0 if we successfully added a hop,
2425 : * and -1 on error.
2426 : */
2427 : STATIC int
2428 27 : onion_extend_cpath(origin_circuit_t *circ)
2429 : {
2430 27 : uint8_t purpose = circ->base_.purpose;
2431 27 : cpath_build_state_t *state = circ->build_state;
2432 27 : int cur_len = circuit_get_cpath_len(circ);
2433 27 : extend_info_t *info = NULL;
2434 :
2435 27 : if (cur_len >= state->desired_path_len) {
2436 6 : log_debug(LD_CIRC, "Path is complete: %d steps long",
2437 : state->desired_path_len);
2438 6 : return 1;
2439 : }
2440 :
2441 21 : log_debug(LD_CIRC, "Path is %d long; we want %d", cur_len,
2442 : state->desired_path_len);
2443 :
2444 21 : if (cur_len == state->desired_path_len - 1) { /* Picking last node */
2445 6 : info = extend_info_dup(state->chosen_exit);
2446 15 : } else if (cur_len == 0) { /* picking first node */
2447 6 : const node_t *r = choose_good_entry_server(purpose, state,
2448 : &circ->guard_state);
2449 6 : if (r) {
2450 : /* If we're a client, use the preferred address rather than the
2451 : primary address, for potentially connecting to an IPv6 OR
2452 : port. Servers always want the primary (IPv4) address. */
2453 6 : int client = (server_mode(get_options()) == 0);
2454 6 : info = extend_info_from_node(r, client);
2455 : /* Clients can fail to find an allowed address */
2456 6 : tor_assert_nonfatal(info || client);
2457 : }
2458 : } else {
2459 9 : const node_t *r =
2460 9 : choose_good_middle_server(purpose, state, circ->cpath, cur_len);
2461 9 : if (r) {
2462 9 : info = extend_info_from_node(r, 0);
2463 : }
2464 : }
2465 :
2466 21 : if (!info) {
2467 0 : log_warn(LD_CIRC,"Failed to find node for hop #%d of our path. Discarding "
2468 : "this circuit.", cur_len+1);
2469 0 : return -1;
2470 : }
2471 :
2472 21 : log_debug(LD_CIRC,"Chose router %s for hop #%d (exit is %s)",
2473 : extend_info_describe(info),
2474 : cur_len+1, build_state_get_exit_nickname(state));
2475 :
2476 21 : cpath_append_hop(&circ->cpath, info);
2477 21 : extend_info_free(info);
2478 21 : return 0;
2479 : }
2480 :
2481 : /** Return the node_t for the chosen exit router in <b>state</b>.
2482 : * If there is no chosen exit, or if we don't know the node_t for
2483 : * the chosen exit, return NULL.
2484 : */
2485 13 : MOCK_IMPL(const node_t *,
2486 : build_state_get_exit_node,(cpath_build_state_t *state))
2487 : {
2488 13 : if (!state || !state->chosen_exit)
2489 : return NULL;
2490 9 : return node_get_by_id(state->chosen_exit->identity_digest);
2491 : }
2492 :
2493 : /** Return the RSA ID digest for the chosen exit router in <b>state</b>.
2494 : * If there is no chosen exit, return NULL.
2495 : */
2496 : const uint8_t *
2497 3 : build_state_get_exit_rsa_id(cpath_build_state_t *state)
2498 : {
2499 3 : if (!state || !state->chosen_exit)
2500 : return NULL;
2501 3 : return (const uint8_t *) state->chosen_exit->identity_digest;
2502 : }
2503 :
2504 : /** Return the nickname for the chosen exit router in <b>state</b>. If
2505 : * there is no chosen exit, or if we don't know the routerinfo_t for the
2506 : * chosen exit, return NULL.
2507 : */
2508 : const char *
2509 30 : build_state_get_exit_nickname(cpath_build_state_t *state)
2510 : {
2511 30 : if (!state || !state->chosen_exit)
2512 : return NULL;
2513 23 : return state->chosen_exit->nickname;
2514 : }
2515 :
2516 : /* Is circuit purpose allowed to use the deprecated TAP encryption protocol?
2517 : * The hidden service protocol still uses TAP for some connections, because
2518 : * ntor onion keys aren't included in HS descriptors or INTRODUCE cells. */
2519 : static int
2520 2 : circuit_purpose_can_use_tap_impl(uint8_t purpose)
2521 : {
2522 2 : return (purpose == CIRCUIT_PURPOSE_S_CONNECT_REND ||
2523 2 : purpose == CIRCUIT_PURPOSE_C_INTRODUCING);
2524 : }
2525 :
2526 : /* Is circ allowed to use the deprecated TAP encryption protocol?
2527 : * The hidden service protocol still uses TAP for some connections, because
2528 : * ntor onion keys aren't included in HS descriptors or INTRODUCE cells. */
2529 : int
2530 2 : circuit_can_use_tap(const origin_circuit_t *circ)
2531 : {
2532 2 : tor_assert(circ);
2533 2 : tor_assert(circ->cpath);
2534 2 : tor_assert(circ->cpath->extend_info);
2535 2 : return (circuit_purpose_can_use_tap_impl(circ->base_.purpose) &&
2536 0 : extend_info_supports_tap(circ->cpath->extend_info));
2537 : }
2538 :
2539 : /* Does circ have an onion key which it's allowed to use? */
2540 : int
2541 2 : circuit_has_usable_onion_key(const origin_circuit_t *circ)
2542 : {
2543 2 : tor_assert(circ);
2544 2 : tor_assert(circ->cpath);
2545 2 : tor_assert(circ->cpath->extend_info);
2546 4 : return (extend_info_supports_ntor(circ->cpath->extend_info) ||
2547 2 : circuit_can_use_tap(circ));
2548 : }
2549 :
2550 : /** Find the circuits that are waiting to find out whether their guards are
2551 : * usable, and if any are ready to become usable, mark them open and try
2552 : * attaching streams as appropriate. */
2553 : void
2554 0 : circuit_upgrade_circuits_from_guard_wait(void)
2555 : {
2556 0 : smartlist_t *to_upgrade =
2557 0 : circuit_find_circuits_to_upgrade_from_guard_wait();
2558 :
2559 0 : if (to_upgrade == NULL)
2560 0 : return;
2561 :
2562 0 : log_info(LD_GUARD, "Upgrading %d circuits from 'waiting for better guard' "
2563 : "to 'open'.", smartlist_len(to_upgrade));
2564 :
2565 0 : SMARTLIST_FOREACH_BEGIN(to_upgrade, origin_circuit_t *, circ) {
2566 0 : circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_OPEN);
2567 0 : circuit_has_opened(circ);
2568 0 : } SMARTLIST_FOREACH_END(circ);
2569 :
2570 0 : smartlist_free(to_upgrade);
2571 : }
|
