tor  0.4.1.0-alpha-dev
circuitbuild.c
Go to the documentation of this file.
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-2019, The Tor Project, Inc. */
5 /* See LICENSE for licensing information */
6 
28 #define CIRCUITBUILD_PRIVATE
29 #define OCIRC_EVENT_PRIVATE
30 
31 #include "core/or/or.h"
32 #include "app/config/config.h"
33 #include "app/config/confparse.h"
34 #include "core/crypto/hs_ntor.h"
36 #include "core/crypto/onion_fast.h"
37 #include "core/crypto/onion_tap.h"
38 #include "core/crypto/relay_crypto.h"
40 #include "core/mainloop/mainloop.h"
41 #include "core/or/channel.h"
42 #include "core/or/circuitbuild.h"
43 #include "core/or/circuitlist.h"
44 #include "core/or/circuitstats.h"
45 #include "core/or/circuituse.h"
46 #include "core/or/circuitpadding.h"
47 #include "core/or/command.h"
49 #include "core/or/connection_or.h"
50 #include "core/or/onion.h"
51 #include "core/or/ocirc_event.h"
52 #include "core/or/policies.h"
53 #include "core/or/relay.h"
54 #include "core/or/crypt_path.h"
55 #include "feature/client/bridges.h"
56 #include "feature/client/circpathbias.h"
68 #include "feature/nodelist/routerset.h"
69 #include "feature/relay/router.h"
71 #include "feature/relay/selftest.h"
73 #include "feature/stats/predict_ports.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 #include "feature/nodelist/microdesc_st.h"
84 #include "feature/nodelist/routerinfo_st.h"
85 #include "feature/nodelist/routerstatus_st.h"
86 
88  uint16_t port,
89  const char *id_digest,
90  const ed25519_public_key_t *ed_id);
91 static int circuit_deliver_create_cell(circuit_t *circ,
92  const create_cell_t *create_cell,
93  int relayed);
97  crypt_path_t *hop);
98 static const node_t *choose_good_middle_server(uint8_t purpose,
99  cpath_build_state_t *state,
100  crypt_path_t *head,
101  int cur_len);
102 
107 static channel_t *
108 channel_connect_for_circuit(const tor_addr_t *addr, uint16_t port,
109  const char *id_digest,
110  const ed25519_public_key_t *ed_id)
111 {
112  channel_t *chan;
113 
114  chan = channel_connect(addr, port, id_digest, ed_id);
115  if (chan) command_setup_channel(chan);
116 
117  return chan;
118 }
119 
126 STATIC circid_t
128 {
129 /* This number is chosen somewhat arbitrarily; see comment below for more
130  * info. When the space is 80% full, it gives a one-in-a-million failure
131  * chance; when the space is 90% full, it gives a one-in-850 chance; and when
132  * the space is 95% full, it gives a one-in-26 failure chance. That seems
133  * okay, though you could make a case IMO for anything between N=32 and
134  * N=256. */
135 #define MAX_CIRCID_ATTEMPTS 64
136  int in_use;
137  unsigned n_with_circ = 0, n_pending_destroy = 0, n_weird_pending_destroy = 0;
138  circid_t test_circ_id;
139  circid_t attempts=0;
140  circid_t high_bit, max_range, mask;
141  int64_t pending_destroy_time_total = 0;
142  int64_t pending_destroy_time_max = 0;
143 
144  tor_assert(chan);
145 
146  if (chan->circ_id_type == CIRC_ID_TYPE_NEITHER) {
147  log_warn(LD_BUG,
148  "Trying to pick a circuit ID for a connection from "
149  "a client with no identity.");
150  return 0;
151  }
152  max_range = (chan->wide_circ_ids) ? (1u<<31) : (1u<<15);
153  mask = max_range - 1;
154  high_bit = (chan->circ_id_type == CIRC_ID_TYPE_HIGHER) ? max_range : 0;
155  do {
156  if (++attempts > MAX_CIRCID_ATTEMPTS) {
157  /* Make sure we don't loop forever because all circuit IDs are used.
158  *
159  * Once, we would try until we had tried every possible circuit ID. But
160  * that's quite expensive. Instead, we try MAX_CIRCID_ATTEMPTS random
161  * circuit IDs, and then give up.
162  *
163  * This potentially causes us to give up early if our circuit ID space
164  * is nearly full. If we have N circuit IDs in use, then we will reject
165  * a new circuit with probability (N / max_range) ^ MAX_CIRCID_ATTEMPTS.
166  * This means that in practice, a few percent of our circuit ID capacity
167  * will go unused.
168  *
169  * The alternative here, though, is to do a linear search over the
170  * whole circuit ID space every time we extend a circuit, which is
171  * not so great either.
172  */
173  int64_t queued_destroys;
175  approx_time());
176  if (m == NULL)
177  return 0; /* This message has been rate-limited away. */
178  if (n_pending_destroy)
179  pending_destroy_time_total /= n_pending_destroy;
180  log_warn(LD_CIRC,"No unused circIDs found on channel %s wide "
181  "circID support, with %u inbound and %u outbound circuits. "
182  "Found %u circuit IDs in use by circuits, and %u with "
183  "pending destroy cells. (%u of those were marked bogusly.) "
184  "The ones with pending destroy cells "
185  "have been marked unusable for an average of %ld seconds "
186  "and a maximum of %ld seconds. This channel is %ld seconds "
187  "old. Failing a circuit.%s",
188  chan->wide_circ_ids ? "with" : "without",
189  chan->num_p_circuits, chan->num_n_circuits,
190  n_with_circ, n_pending_destroy, n_weird_pending_destroy,
191  (long)pending_destroy_time_total,
192  (long)pending_destroy_time_max,
193  (long)(approx_time() - chan->timestamp_created),
194  m);
195  tor_free(m);
196 
197  if (!chan->cmux) {
198  /* This warning should be impossible. */
199  log_warn(LD_BUG, " This channel somehow has no cmux on it!");
200  return 0;
201  }
202 
203  /* analysis so far on 12184 suggests that we're running out of circuit
204  IDs because it looks like we have too many pending destroy
205  cells. Let's see how many we really have pending.
206  */
207  queued_destroys = circuitmux_count_queued_destroy_cells(chan,
208  chan->cmux);
209 
210  log_warn(LD_CIRC, " Circuitmux on this channel has %u circuits, "
211  "of which %u are active. It says it has %"PRId64
212  " destroy cells queued.",
215  (queued_destroys));
216 
217  /* Change this into "if (1)" in order to get more information about
218  * possible failure modes here. You'll need to know how to use gdb with
219  * Tor: this will make Tor exit with an assertion failure if the cmux is
220  * corrupt. */
221  if (0)
222  circuitmux_assert_okay(chan->cmux);
223 
224  channel_dump_statistics(chan, LOG_WARN);
225 
226  return 0;
227  }
228 
229  do {
230  crypto_rand((char*) &test_circ_id, sizeof(test_circ_id));
231  test_circ_id &= mask;
232  } while (test_circ_id == 0);
233 
234  test_circ_id |= high_bit;
235 
236  in_use = circuit_id_in_use_on_channel(test_circ_id, chan);
237  if (in_use == 1)
238  ++n_with_circ;
239  else if (in_use == 2) {
240  time_t since_when;
241  ++n_pending_destroy;
242  since_when =
243  circuit_id_when_marked_unusable_on_channel(test_circ_id, chan);
244  if (since_when) {
245  time_t waiting = approx_time() - since_when;
246  pending_destroy_time_total += waiting;
247  if (waiting > pending_destroy_time_max)
248  pending_destroy_time_max = waiting;
249  } else {
250  ++n_weird_pending_destroy;
251  }
252  }
253  } while (in_use);
254  return test_circ_id;
255 }
256 
263 static char *
264 circuit_list_path_impl(origin_circuit_t *circ, int verbose, int verbose_names)
265 {
266  crypt_path_t *hop;
267  smartlist_t *elements;
268  const char *states[] = {"closed", "waiting for keys", "open"};
269  char *s;
270 
271  elements = smartlist_new();
272 
273  if (verbose) {
274  const char *nickname = build_state_get_exit_nickname(circ->build_state);
275  smartlist_add_asprintf(elements, "%s%s circ (length %d%s%s):",
276  circ->build_state->is_internal ? "internal" : "exit",
277  circ->build_state->need_uptime ? " (high-uptime)" : "",
279  circ->base_.state == CIRCUIT_STATE_OPEN ? "" : ", last hop ",
280  circ->base_.state == CIRCUIT_STATE_OPEN ? "" :
281  (nickname?nickname:"*unnamed*"));
282  }
283 
284  hop = circ->cpath;
285  do {
286  char *elt;
287  const char *id;
288  const node_t *node;
289  if (!hop)
290  break;
291  if (!verbose && hop->state != CPATH_STATE_OPEN)
292  break;
293  if (!hop->extend_info)
294  break;
295  id = hop->extend_info->identity_digest;
296  if (verbose_names) {
297  elt = tor_malloc(MAX_VERBOSE_NICKNAME_LEN+1);
298  if ((node = node_get_by_id(id))) {
299  node_get_verbose_nickname(node, elt);
300  } else if (is_legal_nickname(hop->extend_info->nickname)) {
301  elt[0] = '$';
302  base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN);
303  elt[HEX_DIGEST_LEN+1]= '~';
304  strlcpy(elt+HEX_DIGEST_LEN+2,
306  } else {
307  elt[0] = '$';
308  base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN);
309  }
310  } else { /* ! verbose_names */
311  elt = tor_malloc(HEX_DIGEST_LEN+2);
312  elt[0] = '$';
313  base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN);
314  }
315  tor_assert(elt);
316  if (verbose) {
317  tor_assert(hop->state <= 2);
318  smartlist_add_asprintf(elements,"%s(%s)",elt,states[hop->state]);
319  tor_free(elt);
320  } else {
321  smartlist_add(elements, elt);
322  }
323  hop = hop->next;
324  } while (hop != circ->cpath);
325 
326  s = smartlist_join_strings(elements, verbose?" ":",", 0, NULL);
327  SMARTLIST_FOREACH(elements, char*, cp, tor_free(cp));
328  smartlist_free(elements);
329  return s;
330 }
331 
337 char *
339 {
340  return circuit_list_path_impl(circ, verbose, 0);
341 }
342 
346 char *
348 {
349  return circuit_list_path_impl(circ, 0, 1);
350 }
351 
356 void
357 circuit_log_path(int severity, unsigned int domain, origin_circuit_t *circ)
358 {
359  char *s = circuit_list_path(circ,1);
360  tor_log(severity,domain,"%s",s);
361  tor_free(s);
362 }
363 
365 static int
367 {
368  crypt_path_t *head, *cpath;
369 
370  cpath = head = circ->cpath;
371  do {
372  /* if the extend_info is missing, we can't tell if it supports ntor */
373  if (!cpath->extend_info) {
374  return 0;
375  }
376 
377  /* if the key is blank, it definitely doesn't support ntor */
378  if (!extend_info_supports_ntor(cpath->extend_info)) {
379  return 0;
380  }
381  cpath = cpath->next;
382  } while (cpath != head);
383 
384  return 1;
385 }
386 
389 static int
391 {
392  int r = 0;
393 
394  /* onion_extend_cpath assumes these are non-NULL */
395  tor_assert(circ);
396  tor_assert(circ->build_state);
397 
398  while (r == 0) {
399  r = onion_extend_cpath(circ);
400  if (r < 0) {
401  log_info(LD_CIRC,"Generating cpath hop failed.");
402  return -1;
403  }
404  }
405 
406  /* The path is complete */
407  tor_assert(r == 1);
408 
409  /* Does every node in this path support ntor? */
410  int path_supports_ntor = circuit_cpath_supports_ntor(circ);
411 
412  /* We would like every path to support ntor, but we have to allow for some
413  * edge cases. */
415  if (circuit_can_use_tap(circ)) {
416  /* Circuits from clients to intro points, and hidden services to rend
417  * points do not support ntor, because the hidden service protocol does
418  * not include ntor onion keys. This is also true for Single Onion
419  * Services. */
420  return 0;
421  }
422 
423  if (circuit_get_cpath_len(circ) == 1) {
424  /* Allow for bootstrapping: when we're fetching directly from a fallback,
425  * authority, or bridge, we have no way of knowing its ntor onion key
426  * before we connect to it. So instead, we try connecting, and end up using
427  * CREATE_FAST. */
428  tor_assert(circ->cpath);
429  tor_assert(circ->cpath->extend_info);
430  const node_t *node = node_get_by_id(
432  /* If we don't know the node and its descriptor, we must be bootstrapping.
433  */
434  if (!node || !node_has_preferred_descriptor(node, 1)) {
435  return 0;
436  }
437  }
438 
439  if (BUG(!path_supports_ntor)) {
440  /* If we're building a multi-hop path, and it's not one of the HS or
441  * bootstrapping exceptions, and it doesn't support ntor, something has
442  * gone wrong. */
443  return -1;
444  }
445 
446  return 0;
447 }
448 
453 origin_circuit_init(uint8_t purpose, int flags)
454 {
455  /* sets circ->p_circ_id and circ->p_chan */
458  circ->build_state = tor_malloc_zero(sizeof(cpath_build_state_t));
459  circ->build_state->onehop_tunnel =
460  ((flags & CIRCLAUNCH_ONEHOP_TUNNEL) ? 1 : 0);
461  circ->build_state->need_uptime =
462  ((flags & CIRCLAUNCH_NEED_UPTIME) ? 1 : 0);
463  circ->build_state->need_capacity =
464  ((flags & CIRCLAUNCH_NEED_CAPACITY) ? 1 : 0);
465  circ->build_state->is_internal =
466  ((flags & CIRCLAUNCH_IS_INTERNAL) ? 1 : 0);
467  circ->base_.purpose = purpose;
468  return circ;
469 }
470 
479 circuit_establish_circuit(uint8_t purpose, extend_info_t *exit_ei, int flags)
480 {
481  origin_circuit_t *circ;
482  int err_reason = 0;
483  int is_hs_v3_rp_circuit = 0;
484 
485  if (flags & CIRCLAUNCH_IS_V3_RP) {
486  is_hs_v3_rp_circuit = 1;
487  }
488 
489  circ = origin_circuit_init(purpose, flags);
490 
491  if (onion_pick_cpath_exit(circ, exit_ei, is_hs_v3_rp_circuit) < 0 ||
492  onion_populate_cpath(circ) < 0) {
493  circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_NOPATH);
494  return NULL;
495  }
496 
497  circuit_event_status(circ, CIRC_EVENT_LAUNCHED, 0);
498 
499  if ((err_reason = circuit_handle_first_hop(circ)) < 0) {
500  circuit_mark_for_close(TO_CIRCUIT(circ), -err_reason);
501  return NULL;
502  }
503  return circ;
504 }
505 
507 circuit_guard_state_t *
509 {
510  return circ->guard_state;
511 }
512 
522 static void
524 {
525  ocirc_event_msg_t msg;
526 
527  msg.type = OCIRC_MSGTYPE_CHAN;
528  msg.u.chan.gid = circ->global_identifier;
529  msg.u.chan.chan = chan->global_identifier;
530  msg.u.chan.onehop = circ->build_state->onehop_tunnel;
531 
532  ocirc_event_publish(&msg);
533 }
534 
539 int
541 {
542  crypt_path_t *firsthop;
543  channel_t *n_chan;
544  int err_reason = 0;
545  const char *msg = NULL;
546  int should_launch = 0;
547  const or_options_t *options = get_options();
548 
549  firsthop = cpath_get_next_non_open_hop(circ->cpath);
550  tor_assert(firsthop);
551  tor_assert(firsthop->extend_info);
552 
553  /* Some bridges are on private addresses. Others pass a dummy private
554  * address to the pluggable transport, which ignores it.
555  * Deny the connection if:
556  * - the address is internal, and
557  * - we're not connecting to a configured bridge, and
558  * - we're not configured to allow extends to private addresses. */
559  if (tor_addr_is_internal(&firsthop->extend_info->addr, 0) &&
561  !options->ExtendAllowPrivateAddresses) {
562  log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
563  "Client asked me to connect directly to a private address");
564  return -END_CIRC_REASON_TORPROTOCOL;
565  }
566 
567  /* now see if we're already connected to the first OR in 'route' */
568  log_debug(LD_CIRC,"Looking for firsthop '%s'",
569  fmt_addrport(&firsthop->extend_info->addr,
570  firsthop->extend_info->port));
571 
573  &firsthop->extend_info->ed_identity,
574  &firsthop->extend_info->addr,
575  &msg,
576  &should_launch);
577 
578  if (!n_chan) {
579  /* not currently connected in a useful way. */
580  log_info(LD_CIRC, "Next router is %s: %s",
581  safe_str_client(extend_info_describe(firsthop->extend_info)),
582  msg?msg:"???");
583  circ->base_.n_hop = extend_info_dup(firsthop->extend_info);
584 
585  if (should_launch) {
587  &firsthop->extend_info->addr,
588  firsthop->extend_info->port,
589  firsthop->extend_info->identity_digest,
590  &firsthop->extend_info->ed_identity);
591  if (!n_chan) { /* connect failed, forget the whole thing */
592  log_info(LD_CIRC,"connect to firsthop failed. Closing.");
593  return -END_CIRC_REASON_CONNECTFAILED;
594  }
595  circuit_chan_publish(circ, n_chan);
596  }
597 
598  log_debug(LD_CIRC,"connecting in progress (or finished). Good.");
599  /* return success. The onion/circuit/etc will be taken care of
600  * automatically (may already have been) whenever n_chan reaches
601  * OR_CONN_STATE_OPEN.
602  */
603  return 0;
604  } else { /* it's already open. use it. */
605  tor_assert(!circ->base_.n_hop);
606  circ->base_.n_chan = n_chan;
607  circuit_chan_publish(circ, n_chan);
608  log_debug(LD_CIRC,"Conn open. Delivering first onion skin.");
609  if ((err_reason = circuit_send_next_onion_skin(circ)) < 0) {
610  log_info(LD_CIRC,"circuit_send_next_onion_skin failed.");
611  circ->base_.n_chan = NULL;
612  return err_reason;
613  }
614  }
615  return 0;
616 }
617 
627 void
628 circuit_n_chan_done(channel_t *chan, int status, int close_origin_circuits)
629 {
630  smartlist_t *pending_circs;
631  int err_reason = 0;
632 
633  tor_assert(chan);
634 
635  log_debug(LD_CIRC,"chan to %s, status=%d",
636  channel_get_canonical_remote_descr(chan), status);
637 
638  pending_circs = smartlist_new();
639  circuit_get_all_pending_on_channel(pending_circs, chan);
640 
641  SMARTLIST_FOREACH_BEGIN(pending_circs, circuit_t *, circ)
642  {
643  /* These checks are redundant wrt get_all_pending_on_or_conn, but I'm
644  * leaving them in in case it's possible for the status of a circuit to
645  * change as we're going down the list. */
646  if (circ->marked_for_close || circ->n_chan || !circ->n_hop ||
647  circ->state != CIRCUIT_STATE_CHAN_WAIT)
648  continue;
649 
650  if (tor_digest_is_zero(circ->n_hop->identity_digest)) {
651  /* Look at addr/port. This is an unkeyed connection. */
652  if (!channel_matches_extend_info(chan, circ->n_hop))
653  continue;
654  } else {
655  /* We expected a key. See if it's the right one. */
656  if (tor_memneq(chan->identity_digest,
657  circ->n_hop->identity_digest, DIGEST_LEN))
658  continue;
659  }
660  if (!status) { /* chan failed; close circ */
661  log_info(LD_CIRC,"Channel failed; closing circ.");
662  circuit_mark_for_close(circ, END_CIRC_REASON_CHANNEL_CLOSED);
663  continue;
664  }
665  if (close_origin_circuits && CIRCUIT_IS_ORIGIN(circ)) {
666  log_info(LD_CIRC,"Channel deprecated for origin circs; closing circ.");
667  circuit_mark_for_close(circ, END_CIRC_REASON_CHANNEL_CLOSED);
668  continue;
669  }
670  log_debug(LD_CIRC, "Found circ, sending create cell.");
671  /* circuit_deliver_create_cell will set n_circ_id and add us to
672  * chan_circuid_circuit_map, so we don't need to call
673  * set_circid_chan here. */
674  circ->n_chan = chan;
675  extend_info_free(circ->n_hop);
676  circ->n_hop = NULL;
677 
678  if (CIRCUIT_IS_ORIGIN(circ)) {
679  if ((err_reason =
681  log_info(LD_CIRC,
682  "send_next_onion_skin failed; circuit marked for closing.");
683  circuit_mark_for_close(circ, -err_reason);
684  continue;
685  /* XXX could this be bad, eg if next_onion_skin failed because conn
686  * died? */
687  }
688  } else {
689  /* pull the create cell out of circ->n_chan_create_cell, and send it */
690  tor_assert(circ->n_chan_create_cell);
691  if (circuit_deliver_create_cell(circ, circ->n_chan_create_cell, 1)<0) {
692  circuit_mark_for_close(circ, END_CIRC_REASON_RESOURCELIMIT);
693  continue;
694  }
695  tor_free(circ->n_chan_create_cell);
697  }
698  }
699  SMARTLIST_FOREACH_END(circ);
700 
701  smartlist_free(pending_circs);
702 }
703 
711 static int
713  int relayed)
714 {
715  cell_t cell;
716  circid_t id;
717  int r;
718 
719  tor_assert(circ);
720  tor_assert(circ->n_chan);
721  tor_assert(create_cell);
722  tor_assert(create_cell->cell_type == CELL_CREATE ||
723  create_cell->cell_type == CELL_CREATE_FAST ||
724  create_cell->cell_type == CELL_CREATE2);
725 
727  if (!id) {
728  static ratelim_t circid_warning_limit = RATELIM_INIT(9600);
729  log_fn_ratelim(&circid_warning_limit, LOG_WARN, LD_CIRC,
730  "failed to get unique circID.");
731  goto error;
732  }
733 
734  memset(&cell, 0, sizeof(cell_t));
735  r = relayed ? create_cell_format_relayed(&cell, create_cell)
736  : create_cell_format(&cell, create_cell);
737  if (r < 0) {
738  log_warn(LD_CIRC,"Couldn't format create cell");
739  goto error;
740  }
741  log_debug(LD_CIRC,"Chosen circID %u.", (unsigned)id);
742  circuit_set_n_circid_chan(circ, id, circ->n_chan);
743  cell.circ_id = circ->n_circ_id;
744 
745  append_cell_to_circuit_queue(circ, circ->n_chan, &cell,
746  CELL_DIRECTION_OUT, 0);
747 
748  if (CIRCUIT_IS_ORIGIN(circ)) {
749  /* Update began timestamp for circuits starting their first hop */
750  if (TO_ORIGIN_CIRCUIT(circ)->cpath->state == CPATH_STATE_CLOSED) {
751  if (!CHANNEL_IS_OPEN(circ->n_chan)) {
752  log_warn(LD_CIRC,
753  "Got first hop for a circuit without an opened channel. "
754  "State: %s.", channel_state_to_string(circ->n_chan->state));
756  }
757 
758  tor_gettimeofday(&circ->timestamp_began);
759  }
760 
761  /* mark it so it gets better rate limiting treatment. */
763  }
764 
765  return 0;
766  error:
767  circ->n_chan = NULL;
768  return -1;
769 }
770 
774 int
776 {
777  char dirbuf[128];
778  char *address;
779  const routerinfo_t *me = router_get_my_routerinfo();
780  if (!me)
781  return 0;
782  address = tor_dup_ip(me->addr);
784  "CHECKING_REACHABILITY ORADDRESS=%s:%d",
785  address, me->or_port);
786  if (me->dir_port) {
787  tor_snprintf(dirbuf, sizeof(dirbuf), " and DirPort %s:%d",
788  address, me->dir_port);
790  "CHECKING_REACHABILITY DIRADDRESS=%s:%d",
791  address, me->dir_port);
792  }
793  log_notice(LD_OR, "Now checking whether ORPort %s:%d%s %s reachable... "
794  "(this may take up to %d minutes -- look for log "
795  "messages indicating success)",
796  address, me->or_port,
797  me->dir_port ? dirbuf : "",
798  me->dir_port ? "are" : "is",
800 
801  tor_free(address);
802  return 1;
803 }
804 
807 static inline int
809 {
810  const or_options_t *options = get_options();
811  tor_assert(circ->cpath);
812  tor_assert(circ->cpath->extend_info);
813 
814  if (!circuit_has_usable_onion_key(circ)) {
815  /* We don't have ntor, and we don't have or can't use TAP,
816  * so our hand is forced: only a create_fast will work. */
817  return 1;
818  }
819  if (public_server_mode(options)) {
820  /* We're a server, and we have a usable onion key. We can choose.
821  * Prefer to blend our circuit into the other circuits we are
822  * creating on behalf of others. */
823  return 0;
824  }
825  return networkstatus_get_param(NULL, "usecreatefast", 0, 0, 1);
826 }
827 
841 int
843 {
844  return !circ->has_opened
847 }
848 
856 static void
857 circuit_pick_create_handshake(uint8_t *cell_type_out,
858  uint16_t *handshake_type_out,
859  const extend_info_t *ei)
860 {
861  /* torspec says: In general, clients SHOULD use CREATE whenever they are
862  * using the TAP handshake, and CREATE2 otherwise. */
863  if (extend_info_supports_ntor(ei)) {
864  *cell_type_out = CELL_CREATE2;
865  *handshake_type_out = ONION_HANDSHAKE_TYPE_NTOR;
866  } else {
867  /* XXXX030 Remove support for deciding to use TAP and EXTEND. */
868  *cell_type_out = CELL_CREATE;
869  *handshake_type_out = ONION_HANDSHAKE_TYPE_TAP;
870  }
871 }
872 
882 static void
883 circuit_pick_extend_handshake(uint8_t *cell_type_out,
884  uint8_t *create_cell_type_out,
885  uint16_t *handshake_type_out,
886  const extend_info_t *ei)
887 {
888  uint8_t t;
889  circuit_pick_create_handshake(&t, handshake_type_out, ei);
890 
891  /* torspec says: Clients SHOULD use the EXTEND format whenever sending a TAP
892  * handshake... In other cases, clients SHOULD use EXTEND2. */
893  if (*handshake_type_out != ONION_HANDSHAKE_TYPE_TAP) {
894  *cell_type_out = RELAY_COMMAND_EXTEND2;
895  *create_cell_type_out = CELL_CREATE2;
896  } else {
897  /* XXXX030 Remove support for deciding to use TAP and EXTEND. */
898  *cell_type_out = RELAY_COMMAND_EXTEND;
899  *create_cell_type_out = CELL_CREATE;
900  }
901 }
902 
908 static int
910 {
911  switch (purpose) {
914  /* Testing circuits may omit guards because they're measuring
915  * liveness or performance, and don't want guards to interfere. */
916  return 1;
917  default:
918  /* All other multihop circuits should use guards if guards are
919  * enabled. */
920  return 0;
921  }
922 }
923 
937 int
939 {
940  tor_assert(circ);
941 
942  if (circ->cpath->state == CPATH_STATE_CLOSED) {
943  /* Case one: we're on the first hop. */
944  return circuit_send_first_onion_skin(circ);
945  }
946 
947  tor_assert(circ->cpath->state == CPATH_STATE_OPEN);
948  tor_assert(circ->base_.state == CIRCUIT_STATE_BUILDING);
949 
952 
954 
955  if (hop) {
956  /* Case two: we're on a hop after the first. */
957  return circuit_send_intermediate_onion_skin(circ, hop);
958  }
959 
960  /* Case three: the circuit is finished. Do housekeeping tasks on it. */
962  return circuit_build_no_more_hops(circ);
963 }
964 
971 static int
973 {
974  int fast;
975  int len;
976  const node_t *node;
977  create_cell_t cc;
978  memset(&cc, 0, sizeof(cc));
979 
980  log_debug(LD_CIRC,"First skin; sending create cell.");
981 
982  if (circ->build_state->onehop_tunnel) {
983  control_event_bootstrap(BOOTSTRAP_STATUS_ONEHOP_CREATE, 0);
984  } else {
985  control_event_bootstrap(BOOTSTRAP_STATUS_CIRCUIT_CREATE, 0);
986 
987  /* If this is not a one-hop tunnel, the channel is being used
988  * for traffic that wants anonymity and protection from traffic
989  * analysis (such as netflow record retention). That means we want
990  * to pad it.
991  */
992  if (circ->base_.n_chan->channel_usage < CHANNEL_USED_FOR_FULL_CIRCS)
993  circ->base_.n_chan->channel_usage = CHANNEL_USED_FOR_FULL_CIRCS;
994  }
995 
996  node = node_get_by_id(circ->base_.n_chan->identity_digest);
998  if (!fast) {
999  /* We know the right onion key: we should send a create cell. */
1001  circ->cpath->extend_info);
1002  } else {
1003  /* We don't know an onion key, so we need to fall back to CREATE_FAST. */
1004  cc.cell_type = CELL_CREATE_FAST;
1005  cc.handshake_type = ONION_HANDSHAKE_TYPE_FAST;
1006  }
1007 
1009  circ->cpath->extend_info,
1010  &circ->cpath->handshake_state,
1011  cc.onionskin);
1012  if (len < 0) {
1013  log_warn(LD_CIRC,"onion_skin_create (first hop) failed.");
1014  return - END_CIRC_REASON_INTERNAL;
1015  }
1016  cc.handshake_len = len;
1017 
1018  if (circuit_deliver_create_cell(TO_CIRCUIT(circ), &cc, 0) < 0)
1019  return - END_CIRC_REASON_RESOURCELIMIT;
1020 
1021  circ->cpath->state = CPATH_STATE_AWAITING_KEYS;
1023  log_info(LD_CIRC,"First hop: finished sending %s cell to '%s'",
1024  fast ? "CREATE_FAST" : "CREATE",
1025  node ? node_describe(node) : "<unnamed>");
1026  return 0;
1027 }
1028 
1035 static int
1037 {
1038  guard_usable_t r;
1039  if (! circ->guard_state) {
1040  if (circuit_get_cpath_len(circ) != 1 &&
1041  ! circuit_purpose_may_omit_guard(circ->base_.purpose) &&
1042  get_options()->UseEntryGuards) {
1043  log_warn(LD_BUG, "%d-hop circuit %p with purpose %d has no "
1044  "guard state",
1045  circuit_get_cpath_len(circ), circ, circ->base_.purpose);
1046  }
1047  r = GUARD_USABLE_NOW;
1048  } else {
1049  r = entry_guard_succeeded(&circ->guard_state);
1050  }
1051  const int is_usable_for_streams = (r == GUARD_USABLE_NOW);
1052  if (r == GUARD_USABLE_NOW) {
1054  } else if (r == GUARD_MAYBE_USABLE_LATER) {
1055  // Wait till either a better guard succeeds, or till
1056  // all better guards fail.
1058  } else {
1059  tor_assert_nonfatal(r == GUARD_USABLE_NEVER);
1060  return - END_CIRC_REASON_INTERNAL;
1061  }
1062 
1063  /* XXXX #21422 -- the rest of this branch needs careful thought!
1064  * Some of the things here need to happen when a circuit becomes
1065  * mechanically open; some need to happen when it is actually usable.
1066  * I think I got them right, but more checking would be wise. -NM
1067  */
1068 
1069  log_info(LD_CIRC,"circuit built!");
1071 
1072  if (circ->build_state->onehop_tunnel || circ->has_opened) {
1073  control_event_bootstrap(BOOTSTRAP_STATUS_REQUESTING_STATUS, 0);
1074  }
1075 
1077  if (is_usable_for_streams)
1078  circuit_has_opened(circ); /* do other actions as necessary */
1079 
1081  const or_options_t *options = get_options();
1083  /* FFFF Log a count of known routers here */
1084  log_info(LD_GENERAL,
1085  "Tor has successfully opened a circuit. "
1086  "Looks like client functionality is working.");
1087  control_event_bootstrap(BOOTSTRAP_STATUS_DONE, 0);
1088  control_event_client_status(LOG_NOTICE, "CIRCUIT_ESTABLISHED");
1090  if (server_mode(options) && !check_whether_orport_reachable(options)) {
1093  }
1094  }
1095 
1096  /* We're done with measurement circuits here. Just close them */
1097  if (circ->base_.purpose == CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
1098  circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_FINISHED);
1099  }
1100  return 0;
1101 }
1102 
1109 static int
1111  crypt_path_t *hop)
1112 {
1113  int len;
1114  extend_cell_t ec;
1115  memset(&ec, 0, sizeof(ec));
1116 
1117  log_debug(LD_CIRC,"starting to send subsequent skin.");
1118 
1119  if (tor_addr_family(&hop->extend_info->addr) != AF_INET) {
1120  log_warn(LD_BUG, "Trying to extend to a non-IPv4 address.");
1121  return - END_CIRC_REASON_INTERNAL;
1122  }
1123 
1125  &ec.create_cell.cell_type,
1127  hop->extend_info);
1128 
1129  tor_addr_copy(&ec.orport_ipv4.addr, &hop->extend_info->addr);
1130  ec.orport_ipv4.port = hop->extend_info->port;
1132  memcpy(ec.node_id, hop->extend_info->identity_digest, DIGEST_LEN);
1133  /* Set the ED25519 identity too -- it will only get included
1134  * in the extend2 cell if we're configured to use it, though. */
1136 
1138  hop->extend_info,
1139  &hop->handshake_state,
1140  ec.create_cell.onionskin);
1141  if (len < 0) {
1142  log_warn(LD_CIRC,"onion_skin_create failed.");
1143  return - END_CIRC_REASON_INTERNAL;
1144  }
1145  ec.create_cell.handshake_len = len;
1146 
1147  log_info(LD_CIRC,"Sending extend relay cell.");
1148  {
1149  uint8_t command = 0;
1150  uint16_t payload_len=0;
1151  uint8_t payload[RELAY_PAYLOAD_SIZE];
1152  if (extend_cell_format(&command, &payload_len, payload, &ec)<0) {
1153  log_warn(LD_CIRC,"Couldn't format extend cell");
1154  return -END_CIRC_REASON_INTERNAL;
1155  }
1156 
1157  /* send it to hop->prev, because that relay will transfer
1158  * it to a create cell and then send to hop */
1159  if (relay_send_command_from_edge(0, TO_CIRCUIT(circ),
1160  command,
1161  (char*)payload, payload_len,
1162  hop->prev) < 0)
1163  return 0; /* circuit is closed */
1164  }
1165  hop->state = CPATH_STATE_AWAITING_KEYS;
1166  return 0;
1167 }
1168 
1173 void
1174 circuit_note_clock_jumped(int64_t seconds_elapsed, bool was_idle)
1175 {
1176  int severity = server_mode(get_options()) ? LOG_WARN : LOG_NOTICE;
1177  if (was_idle) {
1178  tor_log(severity, LD_GENERAL, "Tor has been idle for %"PRId64
1179  " seconds; assuming established circuits no longer work.",
1180  (seconds_elapsed));
1181  } else {
1182  tor_log(severity, LD_GENERAL,
1183  "Your system clock just jumped %"PRId64" seconds %s; "
1184  "assuming established circuits no longer work.",
1185  (
1186  seconds_elapsed >=0 ? seconds_elapsed : -seconds_elapsed),
1187  seconds_elapsed >=0 ? "forward" : "backward");
1188  }
1189  control_event_general_status(LOG_WARN, "CLOCK_JUMPED TIME=%"PRId64
1190  " IDLE=%d",
1191  (seconds_elapsed), was_idle?1:0);
1192  /* so we log when it works again */
1194  control_event_client_status(severity, "CIRCUIT_NOT_ESTABLISHED REASON=%s",
1195  "CLOCK_JUMPED");
1198  if (seconds_elapsed < 0) {
1199  /* Restart all the timers in case we jumped a long way into the past. */
1201  }
1202 }
1203 
1212 int
1214 {
1215  channel_t *n_chan;
1216  relay_header_t rh;
1217  extend_cell_t ec;
1218  const char *msg = NULL;
1219  int should_launch = 0;
1220 
1221  if (circ->n_chan) {
1222  log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
1223  "n_chan already set. Bug/attack. Closing.");
1224  return -1;
1225  }
1226  if (circ->n_hop) {
1227  log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
1228  "conn to next hop already launched. Bug/attack. Closing.");
1229  return -1;
1230  }
1231 
1232  if (!server_mode(get_options())) {
1233  log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
1234  "Got an extend cell, but running as a client. Closing.");
1235  return -1;
1236  }
1237 
1238  relay_header_unpack(&rh, cell->payload);
1239 
1240  if (extend_cell_parse(&ec, rh.command,
1241  cell->payload+RELAY_HEADER_SIZE,
1242  rh.length) < 0) {
1243  log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
1244  "Can't parse extend cell. Closing circuit.");
1245  return -1;
1246  }
1247 
1248  if (!ec.orport_ipv4.port || tor_addr_is_null(&ec.orport_ipv4.addr)) {
1249  log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
1250  "Client asked me to extend to zero destination port or addr.");
1251  return -1;
1252  }
1253 
1254  if (tor_addr_is_internal(&ec.orport_ipv4.addr, 0) &&
1255  !get_options()->ExtendAllowPrivateAddresses) {
1256  log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
1257  "Client asked me to extend to a private address");
1258  return -1;
1259  }
1260 
1261  /* Check if they asked us for 0000..0000. We support using
1262  * an empty fingerprint for the first hop (e.g. for a bridge relay),
1263  * but we don't want to let clients send us extend cells for empty
1264  * fingerprints -- a) because it opens the user up to a mitm attack,
1265  * and b) because it lets an attacker force the relay to hold open a
1266  * new TLS connection for each extend request. */
1267  if (tor_digest_is_zero((const char*)ec.node_id)) {
1268  log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
1269  "Client asked me to extend without specifying an id_digest.");
1270  return -1;
1271  }
1272 
1273  /* Fill in ed_pubkey if it was not provided and we can infer it from
1274  * our networkstatus */
1276  const node_t *node = node_get_by_id((const char*)ec.node_id);
1277  const ed25519_public_key_t *node_ed_id = NULL;
1278  if (node &&
1280  (node_ed_id = node_get_ed25519_id(node))) {
1281  ed25519_pubkey_copy(&ec.ed_pubkey, node_ed_id);
1282  }
1283  }
1284 
1285  /* Next, check if we're being asked to connect to the hop that the
1286  * extend cell came from. There isn't any reason for that, and it can
1287  * assist circular-path attacks. */
1288  if (tor_memeq(ec.node_id,
1289  TO_OR_CIRCUIT(circ)->p_chan->identity_digest,
1290  DIGEST_LEN)) {
1291  log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
1292  "Client asked me to extend back to the previous hop.");
1293  return -1;
1294  }
1295 
1296  /* Check the previous hop Ed25519 ID too */
1299  &TO_OR_CIRCUIT(circ)->p_chan->ed25519_identity)) {
1300  log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
1301  "Client asked me to extend back to the previous hop "
1302  "(by Ed25519 ID).");
1303  return -1;
1304  }
1305 
1306  n_chan = channel_get_for_extend((const char*)ec.node_id,
1307  &ec.ed_pubkey,
1308  &ec.orport_ipv4.addr,
1309  &msg,
1310  &should_launch);
1311 
1312  if (!n_chan) {
1313  log_debug(LD_CIRC|LD_OR,"Next router (%s): %s",
1314  fmt_addrport(&ec.orport_ipv4.addr,ec.orport_ipv4.port),
1315  msg?msg:"????");
1316 
1317  circ->n_hop = extend_info_new(NULL /*nickname*/,
1318  (const char*)ec.node_id,
1319  &ec.ed_pubkey,
1320  NULL, /*onion_key*/
1321  NULL, /*curve25519_key*/
1322  &ec.orport_ipv4.addr,
1323  ec.orport_ipv4.port);
1324 
1325  circ->n_chan_create_cell = tor_memdup(&ec.create_cell,
1326  sizeof(ec.create_cell));
1327 
1329 
1330  if (should_launch) {
1331  /* we should try to open a connection */
1332  n_chan = channel_connect_for_circuit(&ec.orport_ipv4.addr,
1333  ec.orport_ipv4.port,
1334  (const char*)ec.node_id,
1335  &ec.ed_pubkey);
1336  if (!n_chan) {
1337  log_info(LD_CIRC,"Launching n_chan failed. Closing circuit.");
1338  circuit_mark_for_close(circ, END_CIRC_REASON_CONNECTFAILED);
1339  return 0;
1340  }
1341  log_debug(LD_CIRC,"connecting in progress (or finished). Good.");
1342  }
1343  /* return success. The onion/circuit/etc will be taken care of
1344  * automatically (may already have been) whenever n_chan reaches
1345  * OR_CONN_STATE_OPEN.
1346  */
1347  return 0;
1348  }
1349 
1350  tor_assert(!circ->n_hop); /* Connection is already established. */
1351  circ->n_chan = n_chan;
1352  log_debug(LD_CIRC,
1353  "n_chan is %s",
1355 
1356  if (circuit_deliver_create_cell(circ, &ec.create_cell, 1) < 0)
1357  return -1;
1358 
1359  return 0;
1360 }
1361 
1371 int
1373  const created_cell_t *reply)
1374 {
1375  char keys[CPATH_KEY_MATERIAL_LEN];
1376  crypt_path_t *hop;
1377  int rv;
1378 
1379  if ((rv = pathbias_count_build_attempt(circ)) < 0) {
1380  log_warn(LD_CIRC, "pathbias_count_build_attempt failed: %d", rv);
1381  return rv;
1382  }
1383 
1384  if (circ->cpath->state == CPATH_STATE_AWAITING_KEYS) {
1385  hop = circ->cpath;
1386  } else {
1387  hop = cpath_get_next_non_open_hop(circ->cpath);
1388  if (!hop) { /* got an extended when we're all done? */
1389  log_warn(LD_PROTOCOL,"got extended when circ already built? Closing.");
1390  return - END_CIRC_REASON_TORPROTOCOL;
1391  }
1392  }
1393  tor_assert(hop->state == CPATH_STATE_AWAITING_KEYS);
1394 
1395  {
1396  const char *msg = NULL;
1398  &hop->handshake_state,
1399  reply->reply, reply->handshake_len,
1400  (uint8_t*)keys, sizeof(keys),
1401  (uint8_t*)hop->rend_circ_nonce,
1402  &msg) < 0) {
1403  if (msg)
1404  log_warn(LD_CIRC,"onion_skin_client_handshake failed: %s", msg);
1405  return -END_CIRC_REASON_TORPROTOCOL;
1406  }
1407  }
1408 
1410 
1411  if (cpath_init_circuit_crypto(hop, keys, sizeof(keys), 0, 0)<0) {
1412  return -END_CIRC_REASON_TORPROTOCOL;
1413  }
1414 
1415  hop->state = CPATH_STATE_OPEN;
1416  log_info(LD_CIRC,"Finished building circuit hop:");
1418  circuit_event_status(circ, CIRC_EVENT_EXTENDED, 0);
1419 
1420  return 0;
1421 }
1422 
1429 int
1431 {
1432 // crypt_path_t *victim;
1433 // connection_t *stream;
1434 
1435  tor_assert(circ);
1436 
1437  /* XXX Since we don't send truncates currently, getting a truncated
1438  * means that a connection broke or an extend failed. For now,
1439  * just give up.
1440  */
1441  circuit_mark_for_close(TO_CIRCUIT(circ),
1443  return 0;
1444 
1445 #if 0
1446  while (layer->next != circ->cpath) {
1447  /* we need to clear out layer->next */
1448  victim = layer->next;
1449  log_debug(LD_CIRC, "Killing a layer of the cpath.");
1450 
1451  for (stream = circ->p_streams; stream; stream=stream->next_stream) {
1452  if (stream->cpath_layer == victim) {
1453  log_info(LD_APP, "Marking stream %d for close because of truncate.",
1454  stream->stream_id);
1455  /* no need to send 'end' relay cells,
1456  * because the other side's already dead
1457  */
1458  connection_mark_unattached_ap(stream, END_STREAM_REASON_DESTROY);
1459  }
1460  }
1461 
1462  layer->next = victim->next;
1463  cpath_free(victim);
1464  }
1465 
1466  log_info(LD_CIRC, "finished");
1467  return 0;
1468 #endif /* 0 */
1469 }
1470 
1474 int
1476  const created_cell_t *created_cell,
1477  const char *keys, size_t keys_len,
1478  const uint8_t *rend_circ_nonce)
1479 {
1480  cell_t cell;
1481 
1482  tor_assert(keys_len == CPATH_KEY_MATERIAL_LEN);
1483 
1484  if (created_cell_format(&cell, created_cell) < 0) {
1485  log_warn(LD_BUG,"couldn't format created cell (type=%d, len=%d)",
1486  (int)created_cell->cell_type, (int)created_cell->handshake_len);
1487  return -1;
1488  }
1489  cell.circ_id = circ->p_circ_id;
1490 
1492 
1493  log_debug(LD_CIRC,"init digest forward 0x%.8x, backward 0x%.8x.",
1494  (unsigned int)get_uint32(keys),
1495  (unsigned int)get_uint32(keys+20));
1496  if (relay_crypto_init(&circ->crypto, keys, keys_len, 0, 0)<0) {
1497  log_warn(LD_BUG,"Circuit initialization failed");
1498  return -1;
1499  }
1500 
1501  memcpy(circ->rend_circ_nonce, rend_circ_nonce, DIGEST_LEN);
1502 
1503  int used_create_fast = (created_cell->cell_type == CELL_CREATED_FAST);
1504 
1506  circ->p_chan, &cell, CELL_DIRECTION_IN, 0);
1507  log_debug(LD_CIRC,"Finished sending '%s' cell.",
1508  used_create_fast ? "created_fast" : "created");
1509 
1510  /* Ignore the local bit when ExtendAllowPrivateAddresses is set:
1511  * it violates the assumption that private addresses are local.
1512  * Also, many test networks run on local addresses, and
1513  * TestingTorNetwork sets ExtendAllowPrivateAddresses. */
1514  if ((!channel_is_local(circ->p_chan)
1515  || get_options()->ExtendAllowPrivateAddresses)
1516  && !channel_is_outgoing(circ->p_chan)) {
1517  /* record that we could process create cells from a non-local conn
1518  * that we didn't initiate; presumably this means that create cells
1519  * can reach us too. */
1521  }
1522 
1523  return 0;
1524 }
1525 
1566 int
1567 route_len_for_purpose(uint8_t purpose, extend_info_t *exit_ei)
1568 {
1569  int routelen = DEFAULT_ROUTE_LEN;
1570  int known_purpose = 0;
1571 
1572  if (circuit_should_use_vanguards(purpose)) {
1573  /* Clients want an extra hop for rends to avoid linkability.
1574  * Services want it for intro points to avoid publishing their
1575  * layer3 guards. They want it for hsdir posts to use
1576  * their full layer3 guard set for those connections.
1577  * Ex: C - G - L2 - L3 - R
1578  * S - G - L2 - L3 - HSDIR
1579  * S - G - L2 - L3 - I
1580  */
1581  if (purpose == CIRCUIT_PURPOSE_C_ESTABLISH_REND ||
1582  purpose == CIRCUIT_PURPOSE_S_HSDIR_POST ||
1583  purpose == CIRCUIT_PURPOSE_HS_VANGUARDS ||
1585  return routelen+1;
1586 
1587  /* If we only have Layer2 vanguards, then we do not need
1588  * the extra hop for linkabilty reasons (see below).
1589  * This means all hops can be of the form:
1590  * S/C - G - L2 - M - R/HSDir/I
1591  */
1592  if (get_options()->HSLayer2Nodes && !get_options()->HSLayer3Nodes)
1593  return routelen+1;
1594 
1595  /* For connections to hsdirs, clients want two extra hops
1596  * when using layer3 guards, to avoid linkability.
1597  * Same goes for intro points. Note that the route len
1598  * includes the intro point or hsdir, hence the +2.
1599  * Ex: C - G - L2 - L3 - M - I
1600  * C - G - L2 - L3 - M - HSDIR
1601  * S - G - L2 - L3 - M - R
1602  */
1603  if (purpose == CIRCUIT_PURPOSE_S_CONNECT_REND ||
1604  purpose == CIRCUIT_PURPOSE_C_HSDIR_GET ||
1605  purpose == CIRCUIT_PURPOSE_C_INTRODUCING)
1606  return routelen+2;
1607  }
1608 
1609  if (!exit_ei)
1610  return routelen;
1611 
1612  switch (purpose) {
1613  /* These two purposes connect to a router that we chose, so
1614  * DEFAULT_ROUTE_LEN is safe. */
1616  /* hidden service connecting to introduction point */
1618  /* router reachability testing */
1619  known_purpose = 1;
1620  break;
1621 
1622  /* These three purposes connect to a router that someone else
1623  * might have chosen, so add an extra hop to protect anonymity. */
1627  /* connecting to hidden service directory */
1629  /* client connecting to introduction point */
1631  /* hidden service connecting to rendezvous point */
1632  known_purpose = 1;
1633  routelen++;
1634  break;
1635 
1636  default:
1637  /* Got a purpose not listed above along with a chosen exit.
1638  * Increase the circuit length by one anyway for safety. */
1639  routelen++;
1640  break;
1641  }
1642 
1643  if (BUG(exit_ei && !known_purpose)) {
1644  log_warn(LD_BUG, "Unhandled purpose %d with a chosen exit; "
1645  "assuming routelen %d.", purpose, routelen);
1646  }
1647  return routelen;
1648 }
1649 
1656 STATIC int
1657 new_route_len(uint8_t purpose, extend_info_t *exit_ei,
1658  const smartlist_t *nodes)
1659 {
1660  int routelen;
1661 
1662  tor_assert(nodes);
1663 
1664  routelen = route_len_for_purpose(purpose, exit_ei);
1665 
1666  int num_acceptable_direct = count_acceptable_nodes(nodes, 1);
1667  int num_acceptable_indirect = count_acceptable_nodes(nodes, 0);
1668 
1669  log_debug(LD_CIRC,"Chosen route length %d (%d direct and %d indirect "
1670  "routers suitable).", routelen, num_acceptable_direct,
1671  num_acceptable_indirect);
1672 
1673  if (num_acceptable_direct < 1 || num_acceptable_indirect < routelen - 1) {
1674  log_info(LD_CIRC,
1675  "Not enough acceptable routers (%d/%d direct and %d/%d "
1676  "indirect routers suitable). Discarding this circuit.",
1677  num_acceptable_direct, routelen,
1678  num_acceptable_indirect, routelen);
1679  return -1;
1680  }
1681 
1682  return routelen;
1683 }
1684 
1687 static smartlist_t *
1689 {
1692  return dest;
1693 }
1694 
1702 circuit_all_predicted_ports_handled, (time_t now, int *need_uptime,
1703  int *need_capacity))
1704 {
1705  int i, enough;
1706  uint16_t *port;
1708  smartlist_t *LongLivedServices = get_options()->LongLivedPorts;
1709  tor_assert(need_uptime);
1710  tor_assert(need_capacity);
1711  // Always predict need_capacity
1712  *need_capacity = 1;
1713  enough = (smartlist_len(sl) == 0);
1714  for (i = 0; i < smartlist_len(sl); ++i) {
1715  port = smartlist_get(sl, i);
1716  if (smartlist_contains_int_as_string(LongLivedServices, *port))
1717  *need_uptime = 1;
1718  tor_free(port);
1719  }
1720  smartlist_free(sl);
1721  return enough;
1722 }
1723 
1727 static int
1728 node_handles_some_port(const node_t *node, smartlist_t *needed_ports)
1729 { /* XXXX MOVE */
1730  int i;
1731  uint16_t port;
1732 
1733  for (i = 0; i < smartlist_len(needed_ports); ++i) {
1735  /* alignment issues aren't a worry for this dereference, since
1736  needed_ports is explicitly a smartlist of uint16_t's */
1737  port = *(uint16_t *)smartlist_get(needed_ports, i);
1738  tor_assert(port);
1739  if (node)
1740  r = compare_tor_addr_to_node_policy(NULL, port, node);
1741  else
1742  continue;
1744  return 1;
1745  }
1746  return 0;
1747 }
1748 
1751 static int
1753 {
1754  entry_connection_t *entry;
1755  if (conn->type != CONN_TYPE_AP)
1756  return 0;
1757  entry = TO_ENTRY_CONN(conn);
1758 
1759  if (conn->state == AP_CONN_STATE_CIRCUIT_WAIT &&
1760  !conn->marked_for_close &&
1761  !(entry->want_onehop) && /* ignore one-hop streams */
1762  !(entry->use_begindir) && /* ignore targeted dir fetches */
1763  !(entry->chosen_exit_name) && /* ignore defined streams */
1765  !circuit_stream_is_being_handled(TO_ENTRY_CONN(conn), 0,
1767  return 1;
1768  return 0;
1769 }
1770 
1779 static const node_t *
1781 {
1782  int *n_supported;
1783  int n_pending_connections = 0;
1784  smartlist_t *connections;
1785  int best_support = -1;
1786  int n_best_support=0;
1787  const or_options_t *options = get_options();
1788  const smartlist_t *the_nodes;
1789  const node_t *selected_node=NULL;
1790  const int need_uptime = (flags & CRN_NEED_UPTIME) != 0;
1791  const int need_capacity = (flags & CRN_NEED_CAPACITY) != 0;
1792  const int direct_conn = (flags & CRN_DIRECT_CONN) != 0;
1793 
1794  connections = get_connection_array();
1795 
1796  /* Count how many connections are waiting for a circuit to be built.
1797  * We use this for log messages now, but in the future we may depend on it.
1798  */
1799  SMARTLIST_FOREACH(connections, connection_t *, conn,
1800  {
1802  ++n_pending_connections;
1803  });
1804 // log_fn(LOG_DEBUG, "Choosing exit node; %d connections are pending",
1805 // n_pending_connections);
1806  /* Now we count, for each of the routers in the directory, how many
1807  * of the pending connections could possibly exit from that
1808  * router (n_supported[i]). (We can't be sure about cases where we
1809  * don't know the IP address of the pending connection.)
1810  *
1811  * -1 means "Don't use this router at all."
1812  */
1813  the_nodes = nodelist_get_list();
1814  n_supported = tor_calloc(smartlist_len(the_nodes), sizeof(int));
1815  SMARTLIST_FOREACH_BEGIN(the_nodes, const node_t *, node) {
1816  const int i = node_sl_idx;
1817  if (router_digest_is_me(node->identity)) {
1818  n_supported[i] = -1;
1819 // log_fn(LOG_DEBUG,"Skipping node %s -- it's me.", router->nickname);
1820  /* XXX there's probably a reverse predecessor attack here, but
1821  * it's slow. should we take this out? -RD
1822  */
1823  continue;
1824  }
1825  if (!node_has_preferred_descriptor(node, direct_conn)) {
1826  n_supported[i] = -1;
1827  continue;
1828  }
1829  if (!node->is_running || node->is_bad_exit) {
1830  n_supported[i] = -1;
1831  continue; /* skip routers that are known to be down or bad exits */
1832  }
1833  if (node_get_purpose(node) != ROUTER_PURPOSE_GENERAL) {
1834  /* never pick a non-general node as a random exit. */
1835  n_supported[i] = -1;
1836  continue;
1837  }
1838  if (routerset_contains_node(options->ExcludeExitNodesUnion_, node)) {
1839  n_supported[i] = -1;
1840  continue; /* user asked us not to use it, no matter what */
1841  }
1842  if (options->ExitNodes &&
1843  !routerset_contains_node(options->ExitNodes, node)) {
1844  n_supported[i] = -1;
1845  continue; /* not one of our chosen exit nodes */
1846  }
1847 
1848  if (node_is_unreliable(node, need_uptime, need_capacity, 0)) {
1849  n_supported[i] = -1;
1850  continue; /* skip routers that are not suitable. Don't worry if
1851  * this makes us reject all the possible routers: if so,
1852  * we'll retry later in this function with need_update and
1853  * need_capacity set to 0. */
1854  }
1855  if (!(node->is_valid)) {
1856  /* if it's invalid and we don't want it */
1857  n_supported[i] = -1;
1858 // log_fn(LOG_DEBUG,"Skipping node %s (index %d) -- invalid router.",
1859 // router->nickname, i);
1860  continue; /* skip invalid routers */
1861  }
1862  /* We do not allow relays that allow single hop exits by default. Option
1863  * was deprecated in 0.2.9.2-alpha and removed in 0.3.1.0-alpha. */
1864  if (node_allows_single_hop_exits(node)) {
1865  n_supported[i] = -1;
1866  continue;
1867  }
1868  if (node_exit_policy_rejects_all(node)) {
1869  n_supported[i] = -1;
1870 // log_fn(LOG_DEBUG,"Skipping node %s (index %d) -- it rejects all.",
1871 // router->nickname, i);
1872  continue; /* skip routers that reject all */
1873  }
1874  n_supported[i] = 0;
1875  /* iterate over connections */
1876  SMARTLIST_FOREACH_BEGIN(connections, connection_t *, conn) {
1877  if (!ap_stream_wants_exit_attention(conn))
1878  continue; /* Skip everything but APs in CIRCUIT_WAIT */
1879  if (connection_ap_can_use_exit(TO_ENTRY_CONN(conn), node)) {
1880  ++n_supported[i];
1881 // log_fn(LOG_DEBUG,"%s is supported. n_supported[%d] now %d.",
1882 // router->nickname, i, n_supported[i]);
1883  } else {
1884 // log_fn(LOG_DEBUG,"%s (index %d) would reject this stream.",
1885 // router->nickname, i);
1886  }
1887  } SMARTLIST_FOREACH_END(conn);
1888  if (n_pending_connections > 0 && n_supported[i] == 0) {
1889  /* Leave best_support at -1 if that's where it is, so we can
1890  * distinguish it later. */
1891  continue;
1892  }
1893  if (n_supported[i] > best_support) {
1894  /* If this router is better than previous ones, remember its index
1895  * and goodness, and start counting how many routers are this good. */
1896  best_support = n_supported[i]; n_best_support=1;
1897 // log_fn(LOG_DEBUG,"%s is new best supported option so far.",
1898 // router->nickname);
1899  } else if (n_supported[i] == best_support) {
1900  /* If this router is _as good_ as the best one, just increment the
1901  * count of equally good routers.*/
1902  ++n_best_support;
1903  }
1904  } SMARTLIST_FOREACH_END(node);
1905  log_info(LD_CIRC,
1906  "Found %d servers that might support %d/%d pending connections.",
1907  n_best_support, best_support >= 0 ? best_support : 0,
1908  n_pending_connections);
1909 
1910  /* If any routers definitely support any pending connections, choose one
1911  * at random. */
1912  if (best_support > 0) {
1913  smartlist_t *supporting = smartlist_new();
1914 
1915  SMARTLIST_FOREACH(the_nodes, const node_t *, node, {
1916  if (n_supported[node_sl_idx] == best_support)
1917  smartlist_add(supporting, (void*)node);
1918  });
1919 
1920  selected_node = node_sl_choose_by_bandwidth(supporting, WEIGHT_FOR_EXIT);
1921  smartlist_free(supporting);
1922  } else {
1923  /* Either there are no pending connections, or no routers even seem to
1924  * possibly support any of them. Choose a router at random that satisfies
1925  * at least one predicted exit port. */
1926 
1927  int attempt;
1928  smartlist_t *needed_ports, *supporting;
1929 
1930  if (best_support == -1) {
1931  if (need_uptime || need_capacity) {
1932  log_info(LD_CIRC,
1933  "We couldn't find any live%s%s routers; falling back "
1934  "to list of all routers.",
1935  need_capacity?", fast":"",
1936  need_uptime?", stable":"");
1937  tor_free(n_supported);
1938  flags &= ~(CRN_NEED_UPTIME|CRN_NEED_CAPACITY);
1939  return choose_good_exit_server_general(flags);
1940  }
1941  log_notice(LD_CIRC, "All routers are down or won't exit%s -- "
1942  "choosing a doomed exit at random.",
1943  options->ExcludeExitNodesUnion_ ? " or are Excluded" : "");
1944  }
1945  supporting = smartlist_new();
1946  needed_ports = circuit_get_unhandled_ports(time(NULL));
1947  for (attempt = 0; attempt < 2; attempt++) {
1948  /* try once to pick only from routers that satisfy a needed port,
1949  * then if there are none, pick from any that support exiting. */
1950  SMARTLIST_FOREACH_BEGIN(the_nodes, const node_t *, node) {
1951  if (n_supported[node_sl_idx] != -1 &&
1952  (attempt || node_handles_some_port(node, needed_ports))) {
1953 // log_fn(LOG_DEBUG,"Try %d: '%s' is a possibility.",
1954 // try, router->nickname);
1955  smartlist_add(supporting, (void*)node);
1956  }
1957  } SMARTLIST_FOREACH_END(node);
1958 
1959  selected_node = node_sl_choose_by_bandwidth(supporting, WEIGHT_FOR_EXIT);
1960  if (selected_node)
1961  break;
1962  smartlist_clear(supporting);
1963  /* If we reach this point, we can't actually support any unhandled
1964  * predicted ports, so clear all the remaining ones. */
1965  if (smartlist_len(needed_ports))
1966  rep_hist_remove_predicted_ports(needed_ports);
1967  }
1968  SMARTLIST_FOREACH(needed_ports, uint16_t *, cp, tor_free(cp));
1969  smartlist_free(needed_ports);
1970  smartlist_free(supporting);
1971  }
1972 
1973  tor_free(n_supported);
1974  if (selected_node) {
1975  log_info(LD_CIRC, "Chose exit server '%s'", node_describe(selected_node));
1976  return selected_node;
1977  }
1978  if (options->ExitNodes) {
1979  log_warn(LD_CIRC,
1980  "No exits in ExitNodes%s seem to be running: "
1981  "can't choose an exit.",
1982  options->ExcludeExitNodesUnion_ ?
1983  ", except possibly those excluded by your configuration, " : "");
1984  }
1985  return NULL;
1986 }
1987 
1988 /* Pick a Rendezvous Point for our HS circuits according to <b>flags</b>. */
1989 static const node_t *
1990 pick_rendezvous_node(router_crn_flags_t flags)
1991 {
1992  const or_options_t *options = get_options();
1993  return router_choose_random_node(NULL, options->ExcludeNodes, flags);
1994 }
1995 
1996 /*
1997  * Helper function to pick a configured restricted middle node
1998  * (either HSLayer2Nodes or HSLayer3Nodes).
1999  *
2000  * Make sure that the node we chose is alive, and not excluded,
2001  * and return it.
2002  *
2003  * The exclude_set is a routerset of nodes that the selected node
2004  * must not match, and the exclude_list is a simple list of nodes
2005  * that the selected node must not be in. Either or both may be
2006  * NULL.
2007  *
2008  * Return NULL if no usable nodes could be found. */
2009 static const node_t *
2011  const routerset_t *pick_from,
2012  const routerset_t *exclude_set,
2013  const smartlist_t *exclude_list,
2014  int position_hint)
2015 {
2016  const node_t *middle_node = NULL;
2017 
2018  smartlist_t *whitelisted_live_middles = smartlist_new();
2019  smartlist_t *all_live_nodes = smartlist_new();
2020 
2021  tor_assert(pick_from);
2022 
2023  /* Add all running nodes to all_live_nodes */
2025  (flags & CRN_NEED_UPTIME) != 0,
2026  (flags & CRN_NEED_CAPACITY) != 0,
2027  (flags & CRN_NEED_GUARD) != 0,
2028  (flags & CRN_NEED_DESC) != 0,
2029  (flags & CRN_PREF_ADDR) != 0,
2030  (flags & CRN_DIRECT_CONN) != 0);
2031 
2032  /* Filter all_live_nodes to only add live *and* whitelisted middles
2033  * to the list whitelisted_live_middles. */
2034  SMARTLIST_FOREACH_BEGIN(all_live_nodes, node_t *, live_node) {
2035  if (routerset_contains_node(pick_from, live_node)) {
2036  smartlist_add(whitelisted_live_middles, live_node);
2037  }
2038  } SMARTLIST_FOREACH_END(live_node);
2039 
2040  /* Honor ExcludeNodes */
2041  if (exclude_set) {
2042  routerset_subtract_nodes(whitelisted_live_middles, exclude_set);
2043  }
2044 
2045  if (exclude_list) {
2046  smartlist_subtract(whitelisted_live_middles, exclude_list);
2047  }
2048 
2055 #define MAX_SANE_RESTRICTED_NODES 20
2056  /* If the user (or associated tor controller) selected only a few nodes,
2057  * assume they took load balancing into account and don't do it for them.
2058  *
2059  * If there are a lot of nodes in here, assume they did not load balance
2060  * and do it for them, but also warn them that they may be Doing It Wrong.
2061  */
2062  if (smartlist_len(whitelisted_live_middles) <=
2063  MAX_SANE_RESTRICTED_NODES) {
2064  middle_node = smartlist_choose(whitelisted_live_middles);
2065  } else {
2066  static ratelim_t pinned_notice_limit = RATELIM_INIT(24*3600);
2067  log_fn_ratelim(&pinned_notice_limit, LOG_NOTICE, LD_CIRC,
2068  "Your _HSLayer%dNodes setting has resulted "
2069  "in %d total nodes. This is a lot of nodes. "
2070  "You may want to consider using a Tor controller "
2071  "to select and update a smaller set of nodes instead.",
2072  position_hint, smartlist_len(whitelisted_live_middles));
2073 
2074  /* NO_WEIGHTING here just means don't take node flags into account
2075  * (ie: use consensus measurement only). This is done so that
2076  * we don't further surprise the user by not using Exits that they
2077  * specified at all */
2078  middle_node = node_sl_choose_by_bandwidth(whitelisted_live_middles,
2079  NO_WEIGHTING);
2080  }
2081 
2082  smartlist_free(whitelisted_live_middles);
2083  smartlist_free(all_live_nodes);
2084 
2085  return middle_node;
2086 }
2087 
2098 static const node_t *
2100  router_crn_flags_t flags, int is_internal)
2101 {
2102  const or_options_t *options = get_options();
2103  flags |= CRN_NEED_DESC;
2104 
2105  switch (TO_CIRCUIT(circ)->purpose) {
2109  /* For these three, we want to pick the exit like a middle hop,
2110  * since it should be random. */
2111  tor_assert_nonfatal(is_internal);
2112  /* Falls through */
2114  if (is_internal) /* pick it like a middle hop */
2115  return router_choose_random_node(NULL, options->ExcludeNodes, flags);
2116  else
2117  return choose_good_exit_server_general(flags);
2119  {
2120  /* Pick a new RP */
2121  const node_t *rendezvous_node = pick_rendezvous_node(flags);
2122  log_info(LD_REND, "Picked new RP: %s",
2123  safe_str_client(node_describe(rendezvous_node)));
2124  return rendezvous_node;
2125  }
2126  }
2127  log_warn(LD_BUG,"Unhandled purpose %d", TO_CIRCUIT(circ)->purpose);
2129  return NULL;
2130 }
2131 
2134 static void
2136  const extend_info_t *exit_ei)
2137 {
2138  const or_options_t *options = get_options();
2139  routerset_t *rs = options->ExcludeNodes;
2140  const char *description;
2141  uint8_t purpose = circ->base_.purpose;
2142 
2143  if (circ->build_state->onehop_tunnel)
2144  return;
2145 
2146  switch (purpose)
2147  {
2148  default:
2149  case CIRCUIT_PURPOSE_OR:
2153  log_warn(LD_BUG, "Called on non-origin circuit (purpose %d, %s)",
2154  (int)purpose,
2155  circuit_purpose_to_string(purpose));
2156  return;
2160  if (circ->build_state->is_internal)
2161  return;
2162  description = "requested exit node";
2163  rs = options->ExcludeExitNodesUnion_;
2164  break;
2172  return;
2177  description = "chosen rendezvous point";
2178  break;
2180  rs = options->ExcludeExitNodesUnion_;
2181  description = "controller-selected circuit target";
2182  break;
2183  }
2184 
2185  if (routerset_contains_extendinfo(rs, exit_ei)) {
2186  /* We should never get here if StrictNodes is set to 1. */
2187  if (options->StrictNodes) {
2188  log_warn(LD_BUG, "Using %s '%s' which is listed in ExcludeNodes%s, "
2189  "even though StrictNodes is set. Please report. "
2190  "(Circuit purpose: %s)",
2191  description, extend_info_describe(exit_ei),
2192  rs==options->ExcludeNodes?"":" or ExcludeExitNodes",
2193  circuit_purpose_to_string(purpose));
2194  } else {
2195  log_warn(LD_CIRC, "Using %s '%s' which is listed in "
2196  "ExcludeNodes%s, because no better options were available. To "
2197  "prevent this (and possibly break your Tor functionality), "
2198  "set the StrictNodes configuration option. "
2199  "(Circuit purpose: %s)",
2200  description, extend_info_describe(exit_ei),
2201  rs==options->ExcludeNodes?"":" or ExcludeExitNodes",
2202  circuit_purpose_to_string(purpose));
2203  }
2205  }
2206 
2207  return;
2208 }
2209 
2218 STATIC int
2220  int is_hs_v3_rp_circuit)
2221 {
2222  cpath_build_state_t *state = circ->build_state;
2223 
2224  if (state->onehop_tunnel) {
2225  log_debug(LD_CIRC, "Launching a one-hop circuit for dir tunnel%s.",
2226  (rend_allow_non_anonymous_connection(get_options()) ?
2227  ", or intro or rendezvous connection" : ""));
2228  state->desired_path_len = 1;
2229  } else {
2230  int r = new_route_len(circ->base_.purpose, exit_ei, nodelist_get_list());
2231  if (r < 1) /* must be at least 1 */
2232  return -1;
2233  state->desired_path_len = r;
2234  }
2235 
2236  if (exit_ei) { /* the circuit-builder pre-requested one */
2237  warn_if_last_router_excluded(circ, exit_ei);
2238  log_info(LD_CIRC,"Using requested exit node '%s'",
2239  extend_info_describe(exit_ei));
2240  exit_ei = extend_info_dup(exit_ei);
2241  } else { /* we have to decide one */
2242  router_crn_flags_t flags = CRN_NEED_DESC;
2243  if (state->need_uptime)
2244  flags |= CRN_NEED_UPTIME;
2245  if (state->need_capacity)
2246  flags |= CRN_NEED_CAPACITY;
2247  if (is_hs_v3_rp_circuit)
2248  flags |= CRN_RENDEZVOUS_V3;
2249  if (state->onehop_tunnel)
2250  flags |= CRN_DIRECT_CONN;
2251  const node_t *node =
2252  choose_good_exit_server(circ, flags, state->is_internal);
2253  if (!node) {
2254  log_warn(LD_CIRC,"Failed to choose an exit server");
2255  return -1;
2256  }
2257  exit_ei = extend_info_from_node(node, state->onehop_tunnel);
2258  if (BUG(exit_ei == NULL))
2259  return -1;
2260  }
2261  state->chosen_exit = exit_ei;
2262  return 0;
2263 }
2264 
2269 int
2271 {
2272  cpath_build_state_t *state;
2273  tor_assert(exit_ei);
2274  tor_assert(circ);
2275 
2276  state = circ->build_state;
2277  tor_assert(state);
2278  extend_info_free(state->chosen_exit);
2279  state->chosen_exit = extend_info_dup(exit_ei);
2280 
2281  ++circ->build_state->desired_path_len;
2282  cpath_append_hop(&circ->cpath, exit_ei);
2283  return 0;
2284 }
2285 
2290 int
2292 {
2293  int err_reason = 0;
2294  warn_if_last_router_excluded(circ, exit_ei);
2295 
2296  tor_gettimeofday(&circ->base_.timestamp_began);
2297 
2298  circuit_append_new_exit(circ, exit_ei);
2300  if ((err_reason = circuit_send_next_onion_skin(circ))<0) {
2301  log_warn(LD_CIRC, "Couldn't extend circuit to new point %s.",
2302  extend_info_describe(exit_ei));
2303  circuit_mark_for_close(TO_CIRCUIT(circ), -err_reason);
2304  return -1;
2305  }
2306 
2307  // XXX: Should cannibalized circuits be dirty or not? Not easy to say..
2308 
2309  return 0;
2310 }
2311 
2319 MOCK_IMPL(STATIC int,
2320 count_acceptable_nodes, (const smartlist_t *nodes, int direct))
2321 {
2322  int num=0;
2323 
2324  SMARTLIST_FOREACH_BEGIN(nodes, const node_t *, node) {
2325  // log_debug(LD_CIRC,
2326 // "Contemplating whether router %d (%s) is a new option.",
2327 // i, r->nickname);
2328  if (! node->is_running)
2329 // log_debug(LD_CIRC,"Nope, the directory says %d is not running.",i);
2330  continue;
2331  if (! node->is_valid)
2332 // log_debug(LD_CIRC,"Nope, the directory says %d is not valid.",i);
2333  continue;
2334  if (! node_has_preferred_descriptor(node, direct))
2335  continue;
2336  /* The node has a descriptor, so we can just check the ntor key directly */
2337  if (!node_has_curve25519_onion_key(node))
2338  continue;
2339  ++num;
2340  } SMARTLIST_FOREACH_END(node);
2341 
2342 // log_debug(LD_CIRC,"I like %d. num_acceptable_routers now %d.",i, num);
2343 
2344  return num;
2345 }
2346 
2367 static smartlist_t *
2369  cpath_build_state_t *state,
2370  crypt_path_t *head,
2371  int cur_len)
2372 {
2373  smartlist_t *excluded;
2374  const node_t *r;
2375  crypt_path_t *cpath;
2376  int i;
2377 
2378  (void) purpose;
2379 
2380  excluded = smartlist_new();
2381 
2382  /* Add the exit to the exclude list (note that the exit/last hop is always
2383  * chosen first in circuit_establish_circuit()). */
2384  if ((r = build_state_get_exit_node(state))) {
2385  smartlist_add(excluded, (node_t*)r);
2386  }
2387 
2388  /* If we are picking the 4th hop, allow that node to be the guard too.
2389  * This prevents us from avoiding the Guard for those hops, which
2390  * gives the adversary information about our guard if they control
2391  * the RP, IP, or HSDIR. We don't do this check based on purpose
2392  * because we also want to allow HS_VANGUARDS pre-build circuits
2393  * to use the guard for that last hop.
2394  */
2395  if (cur_len == DEFAULT_ROUTE_LEN+1) {
2396  /* Skip the first hop for the exclude list below */
2397  head = head->next;
2398  cur_len--;
2399  }
2400 
2401  for (i = 0, cpath = head; cpath && i < cur_len; ++i, cpath=cpath->next) {
2402  if ((r = node_get_by_id(cpath->extend_info->identity_digest))) {
2403  smartlist_add(excluded, (node_t*)r);
2404  }
2405  }
2406 
2407  return excluded;
2408 }
2409 
2414 static smartlist_t *
2416  cpath_build_state_t *state,
2417  crypt_path_t *head,
2418  int cur_len)
2419 {
2420  smartlist_t *excluded;
2421  const node_t *r;
2422  crypt_path_t *cpath;
2423  int i;
2424 
2426  if (circuit_should_use_vanguards(purpose)) {
2427  return build_vanguard_middle_exclude_list(purpose, state, head, cur_len);
2428  }
2429 
2430  excluded = smartlist_new();
2431 
2432  /* For non-vanguard circuits, add the exit and its family to the exclude list
2433  * (note that the exit/last hop is always chosen first in
2434  * circuit_establish_circuit()). */
2435  if ((r = build_state_get_exit_node(state))) {
2436  nodelist_add_node_and_family(excluded, r);
2437  }
2438 
2439  /* also exclude all other already chosen nodes and their family */
2440  for (i = 0, cpath = head; cpath && i < cur_len; ++i, cpath=cpath->next) {
2441  if ((r = node_get_by_id(cpath->extend_info->identity_digest))) {
2442  nodelist_add_node_and_family(excluded, r);
2443  }
2444  }
2445 
2446  return excluded;
2447 }
2448 
2450 static int
2452  uint8_t purpose, int cur_len)
2453 {
2454  /* If this is not a hidden service circuit, don't use vanguards */
2455  if (!circuit_purpose_is_hidden_service(purpose)) {
2456  return 0;
2457  }
2458 
2459  /* If we have sticky L2 nodes, and this is an L2 pick, use vanguards */
2460  if (options->HSLayer2Nodes && cur_len == 1) {
2461  return 1;
2462  }
2463 
2464  /* If we have sticky L3 nodes, and this is an L3 pick, use vanguards */
2465  if (options->HSLayer3Nodes && cur_len == 2) {
2466  return 1;
2467  }
2468 
2469  return 0;
2470 }
2471 
2474 static const node_t *
2476  router_crn_flags_t flags, int cur_len,
2477  const smartlist_t *excluded)
2478 {
2479  const routerset_t *vanguard_routerset = NULL;
2480  const node_t *node = NULL;
2481 
2482  /* Pick the right routerset based on the current hop */
2483  if (cur_len == 1) {
2484  vanguard_routerset = options->HSLayer2Nodes;
2485  } else if (cur_len == 2) {
2486  vanguard_routerset = options->HSLayer3Nodes;
2487  } else {
2488  /* guaranteed by middle_node_should_be_vanguard() */
2489  tor_assert_nonfatal_unreached();
2490  return NULL;
2491  }
2492 
2493  node = pick_restricted_middle_node(flags, vanguard_routerset,
2494  options->ExcludeNodes, excluded,
2495  cur_len+1);
2496 
2497  if (!node) {
2498  static ratelim_t pinned_warning_limit = RATELIM_INIT(300);
2499  log_fn_ratelim(&pinned_warning_limit, LOG_WARN, LD_CIRC,
2500  "Could not find a node that matches the configured "
2501  "_HSLayer%dNodes set", cur_len+1);
2502  }
2503 
2504  return node;
2505 }
2506 
2513 static const node_t *
2515  cpath_build_state_t *state,
2516  crypt_path_t *head,
2517  int cur_len)
2518 {
2519  const node_t *choice;
2520  smartlist_t *excluded;
2521  const or_options_t *options = get_options();
2522  router_crn_flags_t flags = CRN_NEED_DESC;
2523  tor_assert(CIRCUIT_PURPOSE_MIN_ <= purpose &&
2524  purpose <= CIRCUIT_PURPOSE_MAX_);
2525 
2526  log_debug(LD_CIRC, "Contemplating intermediate hop #%d: random choice.",
2527  cur_len+1);
2528 
2529  excluded = build_middle_exclude_list(purpose, state, head, cur_len);
2530 
2531  if (state->need_uptime)
2532  flags |= CRN_NEED_UPTIME;
2533  if (state->need_capacity)
2534  flags |= CRN_NEED_CAPACITY;
2535 
2537  if (middle_node_must_be_vanguard(options, purpose, cur_len)) {
2538  log_debug(LD_GENERAL, "Picking a sticky node (cur_len = %d)", cur_len);
2539  choice = pick_vanguard_middle_node(options, flags, cur_len, excluded);
2540  smartlist_free(excluded);
2541  return choice;
2542  }
2543 
2544  if (options->MiddleNodes) {
2545  smartlist_t *sl = smartlist_new();
2546  routerset_get_all_nodes(sl, options->MiddleNodes,
2547  options->ExcludeNodes, 1);
2548 
2549  smartlist_subtract(sl, excluded);
2550 
2551  choice = node_sl_choose_by_bandwidth(sl, WEIGHT_FOR_MID);
2552  smartlist_free(sl);
2553  if (choice) {
2554  log_fn(LOG_INFO, LD_CIRC, "Chose fixed middle node: %s",
2555  hex_str(choice->identity, DIGEST_LEN));
2556  } else {
2557  log_fn(LOG_NOTICE, LD_CIRC, "Restricted middle not available");
2558  }
2559  } else {
2560  choice = router_choose_random_node(excluded, options->ExcludeNodes, flags);
2561  }
2562  smartlist_free(excluded);
2563  return choice;
2564 }
2565 
2575 const node_t *
2577  circuit_guard_state_t **guard_state_out)
2578 {
2579  const node_t *choice;
2580  smartlist_t *excluded;
2581  const or_options_t *options = get_options();
2582  /* If possible, choose an entry server with a preferred address,
2583  * otherwise, choose one with an allowed address */
2584  router_crn_flags_t flags = (CRN_NEED_GUARD|CRN_NEED_DESC|CRN_PREF_ADDR|
2585  CRN_DIRECT_CONN);
2586  const node_t *node;
2587 
2588  /* Once we used this function to select a node to be a guard. We had
2589  * 'state == NULL' be the signal for that. But we don't do that any more.
2590  */
2591  tor_assert_nonfatal(state);
2592 
2593  if (state && options->UseEntryGuards &&
2594  (purpose != CIRCUIT_PURPOSE_TESTING || options->BridgeRelay)) {
2595  /* This request is for an entry server to use for a regular circuit,
2596  * and we use entry guard nodes. Just return one of the guard nodes. */
2597  tor_assert(guard_state_out);
2598  return guards_choose_guard(state, purpose, guard_state_out);
2599  }
2600 
2601  excluded = smartlist_new();
2602 
2603  if (state && (node = build_state_get_exit_node(state))) {
2604  /* Exclude the exit node from the state, if we have one. Also exclude its
2605  * family. */
2606  nodelist_add_node_and_family(excluded, node);
2607  }
2608 
2609  if (state) {
2610  if (state->need_uptime)
2611  flags |= CRN_NEED_UPTIME;
2612  if (state->need_capacity)
2613  flags |= CRN_NEED_CAPACITY;
2614  }
2615 
2616  choice = router_choose_random_node(excluded, options->ExcludeNodes, flags);
2617  smartlist_free(excluded);
2618  return choice;
2619 }
2620 
2627 STATIC int
2629 {
2630  uint8_t purpose = circ->base_.purpose;
2631  cpath_build_state_t *state = circ->build_state;
2632  int cur_len = circuit_get_cpath_len(circ);
2633  extend_info_t *info = NULL;
2634 
2635  if (cur_len >= state->desired_path_len) {
2636  log_debug(LD_CIRC, "Path is complete: %d steps long",
2637  state->desired_path_len);
2638  return 1;
2639  }
2640 
2641  log_debug(LD_CIRC, "Path is %d long; we want %d", cur_len,
2642  state->desired_path_len);
2643 
2644  if (cur_len == state->desired_path_len - 1) { /* Picking last node */
2645  info = extend_info_dup(state->chosen_exit);
2646  } else if (cur_len == 0) { /* picking first node */
2647  const node_t *r = choose_good_entry_server(purpose, state,
2648  &circ->guard_state);
2649  if (r) {
2650  /* If we're a client, use the preferred address rather than the
2651  primary address, for potentially connecting to an IPv6 OR
2652  port. Servers always want the primary (IPv4) address. */
2653  int client = (server_mode(get_options()) == 0);
2654  info = extend_info_from_node(r, client);
2655  /* Clients can fail to find an allowed address */
2656  tor_assert_nonfatal(info || client);
2657  }
2658  } else {
2659  const node_t *r =
2660  choose_good_middle_server(purpose, state, circ->cpath, cur_len);
2661  if (r) {
2662  info = extend_info_from_node(r, 0);
2663  tor_assert_nonfatal(info);
2664  }
2665  }
2666 
2667  if (!info) {
2668  log_warn(LD_CIRC,"Failed to find node for hop #%d of our path. Discarding "
2669  "this circuit.", cur_len+1);
2670  return -1;
2671  }
2672 
2673  log_debug(LD_CIRC,"Chose router %s for hop #%d (exit is %s)",
2674  extend_info_describe(info),
2675  cur_len+1, build_state_get_exit_nickname(state));
2676 
2677  cpath_append_hop(&circ->cpath, info);
2678  extend_info_free(info);
2679  return 0;
2680 }
2681 
2683 extend_info_t *
2684 extend_info_new(const char *nickname,
2685  const char *rsa_id_digest,
2686  const ed25519_public_key_t *ed_id,
2687  crypto_pk_t *onion_key,
2688  const curve25519_public_key_t *ntor_key,
2689  const tor_addr_t *addr, uint16_t port)
2690 {
2691  extend_info_t *info = tor_malloc_zero(sizeof(extend_info_t));
2692  memcpy(info->identity_digest, rsa_id_digest, DIGEST_LEN);
2693  if (ed_id && !ed25519_public_key_is_zero(ed_id))
2694  memcpy(&info->ed_identity, ed_id, sizeof(ed25519_public_key_t));
2695  if (nickname)
2696  strlcpy(info->nickname, nickname, sizeof(info->nickname));
2697  if (onion_key)
2698  info->onion_key = crypto_pk_dup_key(onion_key);
2699  if (ntor_key)
2700  memcpy(&info->curve25519_onion_key, ntor_key,
2701  sizeof(curve25519_public_key_t));
2702  tor_addr_copy(&info->addr, addr);
2703  info->port = port;
2704  return info;
2705 }
2706 
2717 extend_info_t *
2718 extend_info_from_node(const node_t *node, int for_direct_connect)
2719 {
2720  crypto_pk_t *rsa_pubkey = NULL;
2721  extend_info_t *info = NULL;
2722  tor_addr_port_t ap;
2723  int valid_addr = 0;
2724 
2725  if (!node_has_preferred_descriptor(node, for_direct_connect)) {
2726  return NULL;
2727  }
2728 
2729  /* Choose a preferred address first, but fall back to an allowed address. */
2730  if (for_direct_connect)
2731  fascist_firewall_choose_address_node(node, FIREWALL_OR_CONNECTION, 0, &ap);
2732  else {
2733  node_get_prim_orport(node, &ap);
2734  }
2735  valid_addr = tor_addr_port_is_valid_ap(&ap, 0);
2736 
2737  if (valid_addr)
2738  log_debug(LD_CIRC, "using %s for %s",
2739  fmt_addrport(&ap.addr, ap.port),
2740  node->ri ? node->ri->nickname : node->rs->nickname);
2741  else
2742  log_warn(LD_CIRC, "Could not choose valid address for %s",
2743  node->ri ? node->ri->nickname : node->rs->nickname);
2744 
2745  /* Every node we connect or extend to must support ntor */
2746  if (!node_has_curve25519_onion_key(node)) {
2747  log_fn(LOG_PROTOCOL_WARN, LD_CIRC,
2748  "Attempted to create extend_info for a node that does not support "
2749  "ntor: %s", node_describe(node));
2750  return NULL;
2751  }
2752 
2753  const ed25519_public_key_t *ed_pubkey = NULL;
2754 
2755  /* Don't send the ed25519 pubkey unless the target node actually supports
2756  * authenticating with it. */
2758  log_info(LD_CIRC, "Including Ed25519 ID for %s", node_describe(node));
2759  ed_pubkey = node_get_ed25519_id(node);
2760  } else if (node_get_ed25519_id(node)) {
2761  log_info(LD_CIRC, "Not including the ed25519 ID for %s, since it won't "
2762  "be able to authenticate it.",
2763  node_describe(node));
2764  }
2765 
2766  /* Retrieve the curve25519 pubkey. */
2767  const curve25519_public_key_t *curve_pubkey =
2769  rsa_pubkey = node_get_rsa_onion_key(node);
2770 
2771  if (valid_addr && node->ri) {
2772  info = extend_info_new(node->ri->nickname,
2773  node->identity,
2774  ed_pubkey,
2775  rsa_pubkey,
2776  curve_pubkey,
2777  &ap.addr,
2778  ap.port);
2779  } else if (valid_addr && node->rs && node->md) {
2780  info = extend_info_new(node->rs->nickname,
2781  node->identity,
2782  ed_pubkey,
2783  rsa_pubkey,
2784  curve_pubkey,
2785  &ap.addr,
2786  ap.port);
2787  }
2788 
2789  crypto_pk_free(rsa_pubkey);
2790  return info;
2791 }
2792 
2794 void
2796 {
2797  if (!info)
2798  return;
2799  crypto_pk_free(info->onion_key);
2800  tor_free(info);
2801 }
2802 
2805 extend_info_t *
2807 {
2808  extend_info_t *newinfo;
2809  tor_assert(info);
2810  newinfo = tor_malloc(sizeof(extend_info_t));
2811  memcpy(newinfo, info, sizeof(extend_info_t));
2812  if (info->onion_key)
2813  newinfo->onion_key = crypto_pk_dup_key(info->onion_key);
2814  else
2815  newinfo->onion_key = NULL;
2816  return newinfo;
2817 }
2818 
2823 const node_t *
2825 {
2826  if (!state || !state->chosen_exit)
2827  return NULL;
2828  return node_get_by_id(state->chosen_exit->identity_digest);
2829 }
2830 
2834 const uint8_t *
2836 {
2837  if (!state || !state->chosen_exit)
2838  return NULL;
2839  return (const uint8_t *) state->chosen_exit->identity_digest;
2840 }
2841 
2846 const char *
2848 {
2849  if (!state || !state->chosen_exit)
2850  return NULL;
2851  return state->chosen_exit->nickname;
2852 }
2853 
2855 int
2857 {
2858  tor_assert(addr);
2859 
2860  /* Check if we have a private address and if we can extend to it. */
2861  if ((tor_addr_is_internal(addr, 0) || tor_addr_is_multicast(addr)) &&
2862  !get_options()->ExtendAllowPrivateAddresses) {
2863  goto disallow;
2864  }
2865  /* Allowed! */
2866  return 1;
2867  disallow:
2868  return 0;
2869 }
2870 
2871 /* Does ei have a valid TAP key? */
2872 int
2873 extend_info_supports_tap(const extend_info_t* ei)
2874 {
2875  tor_assert(ei);
2876  /* Valid TAP keys are not NULL */
2877  return ei->onion_key != NULL;
2878 }
2879 
2880 /* Does ei have a valid ntor key? */
2881 int
2882 extend_info_supports_ntor(const extend_info_t* ei)
2883 {
2884  tor_assert(ei);
2885  /* Valid ntor keys have at least one non-zero byte */
2886  return !fast_mem_is_zero(
2887  (const char*)ei->curve25519_onion_key.public_key,
2889 }
2890 
2891 /* Is circuit purpose allowed to use the deprecated TAP encryption protocol?
2892  * The hidden service protocol still uses TAP for some connections, because
2893  * ntor onion keys aren't included in HS descriptors or INTRODUCE cells. */
2894 static int
2895 circuit_purpose_can_use_tap_impl(uint8_t purpose)
2896 {
2897  return (purpose == CIRCUIT_PURPOSE_S_CONNECT_REND ||
2898  purpose == CIRCUIT_PURPOSE_C_INTRODUCING);
2899 }
2900 
2901 /* Is circ allowed to use the deprecated TAP encryption protocol?
2902  * The hidden service protocol still uses TAP for some connections, because
2903  * ntor onion keys aren't included in HS descriptors or INTRODUCE cells. */
2904 int
2905 circuit_can_use_tap(const origin_circuit_t *circ)
2906 {
2907  tor_assert(circ);
2908  tor_assert(circ->cpath);
2909  tor_assert(circ->cpath->extend_info);
2910  return (circuit_purpose_can_use_tap_impl(circ->base_.purpose) &&
2911  extend_info_supports_tap(circ->cpath->extend_info));
2912 }
2913 
2914 /* Does circ have an onion key which it's allowed to use? */
2915 int
2916 circuit_has_usable_onion_key(const origin_circuit_t *circ)
2917 {
2918  tor_assert(circ);
2919  tor_assert(circ->cpath);
2920  tor_assert(circ->cpath->extend_info);
2921  return (extend_info_supports_ntor(circ->cpath->extend_info) ||
2922  circuit_can_use_tap(circ));
2923 }
2924 
2925 /* Does ei have an onion key which it would prefer to use?
2926  * Currently, we prefer ntor keys*/
2927 int
2928 extend_info_has_preferred_onion_key(const extend_info_t* ei)
2929 {
2930  tor_assert(ei);
2931  return extend_info_supports_ntor(ei);
2932 }
2933 
2937 void
2939 {
2940  smartlist_t *to_upgrade =
2942 
2943  if (to_upgrade == NULL)
2944  return;
2945 
2946  log_info(LD_GUARD, "Upgrading %d circuits from 'waiting for better guard' "
2947  "to 'open'.", smartlist_len(to_upgrade));
2948 
2949  SMARTLIST_FOREACH_BEGIN(to_upgrade, origin_circuit_t *, circ) {
2951  circuit_has_opened(circ);
2952  } SMARTLIST_FOREACH_END(circ);
2953 
2954  smartlist_free(to_upgrade);
2955 }
#define RELAY_PAYLOAD_SIZE
Definition: or.h:605
#define CIRCUIT_PURPOSE_C_INTRODUCING
Definition: circuitlist.h:74
channel_state_t state
Definition: channel.h:192
Header file for circuitstats.c.
#define CIRCLAUNCH_ONEHOP_TUNNEL
Definition: circuituse.h:39
Header file for rendcommon.c.
void circuit_get_all_pending_on_channel(smartlist_t *out, channel_t *chan)
Definition: circuitlist.c:574
#define CIRCLAUNCH_IS_INTERNAL
Definition: circuituse.h:46
static void warn_if_last_router_excluded(origin_circuit_t *circ, const extend_info_t *exit_ei)
uint8_t onionskin[CELL_PAYLOAD_SIZE - 4]
Definition: onion.h:32
struct circuit_guard_state_t * guard_state
circ_id_type_bitfield_t circ_id_type
Definition: channel.h:411
static smartlist_t * build_middle_exclude_list(uint8_t purpose, cpath_build_state_t *state, crypt_path_t *head, int cur_len)
const char * channel_get_canonical_remote_descr(channel_t *chan)
Definition: channel.c:2847
int node_allows_single_hop_exits(const node_t *node)
Definition: nodelist.c:1408
#define CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT
Definition: circuitlist.h:94
int routerset_contains_extendinfo(const routerset_t *set, const extend_info_t *ei)
Definition: routerset.c:289
static void circuit_chan_publish(const origin_circuit_t *circ, const channel_t *chan)
Definition: circuitbuild.c:523
#define CIRCUIT_PURPOSE_C_REND_READY_INTRO_ACKED
Definition: circuitlist.h:87
int channel_is_outgoing(channel_t *chan)
Definition: channel.c:3071
void pathbias_count_build_success(origin_circuit_t *circ)
Definition: circpathbias.c:512
static smartlist_t * circuit_get_unhandled_ports(time_t now)
Header file for circuitbuild.c.
uint8_t payload[CELL_PAYLOAD_SIZE]
Definition: cell_st.h:16
extend_info_t * extend_info_new(const char *nickname, const char *rsa_id_digest, const ed25519_public_key_t *ed_id, crypto_pk_t *onion_key, const curve25519_public_key_t *ntor_key, const tor_addr_t *addr, uint16_t port)
Common functions for using (pseudo-)random number generators.
int extend_cell_format(uint8_t *command_out, uint16_t *len_out, uint8_t *payload_out, const extend_cell_t *cell_in)
Definition: onion.c:591
Definition: node_st.h:28
uint8_t cell_type
Definition: onion.h:38
int node_supports_ed25519_link_authentication(const node_t *node, int compatible_with_us)
Definition: nodelist.c:1135
#define SMARTLIST_FOREACH_BEGIN(sl, type, var)
uint16_t handshake_len
Definition: onion.h:30
int routerset_contains_node(const routerset_t *set, const node_t *node)
Definition: routerset.c:334
Header file for command.c.
void tor_addr_make_unspec(tor_addr_t *a)
Definition: address.c:225
extend_info_t * extend_info_from_node(const node_t *node, int for_direct_connect)
channel_t * channel_get_for_extend(const char *rsa_id_digest, const ed25519_public_key_t *ed_id, const tor_addr_t *target_addr, const char **msg_out, int *launch_out)
Definition: channel.c:2394
int circuit_handle_first_hop(origin_circuit_t *circ)
Definition: circuitbuild.c:540
addr_policy_result_t
Definition: policies.h:38
struct crypt_path_t * next
Definition: crypt_path_st.h:67
Header file for node_select.c.
void circpad_machine_event_circ_added_hop(origin_circuit_t *on_circ)
const char * extend_info_describe(const extend_info_t *ei)
Definition: describe.c:154
Header file for connection.c.
void circuit_n_chan_done(channel_t *chan, int status, int close_origin_circuits)
Definition: circuitbuild.c:628
Definition: cell_st.h:12
#define LD_GENERAL
Definition: log.h:59
int route_len_for_purpose(uint8_t purpose, extend_info_t *exit_ei)
#define CIRCUIT_IS_ORIGIN(c)
Definition: circuitlist.h:145
time_t timestamp_created
Definition: channel.h:295
#define CIRCLAUNCH_NEED_UPTIME
Definition: circuituse.h:41
addr_policy_result_t compare_tor_addr_to_node_policy(const tor_addr_t *addr, uint16_t port, const node_t *node)
Definition: policies.c:3004
int circuit_finish_handshake(origin_circuit_t *circ, const created_cell_t *reply)
origin_circuit_t * origin_circuit_init(uint8_t purpose, int flags)
Definition: circuitbuild.c:453
uint8_t state
Definition: connection_st.h:44
#define CIRCUIT_PURPOSE_REND_POINT_WAITING
Definition: circuitlist.h:44
const char * circuit_purpose_to_string(uint8_t purpose)
Definition: circuitlist.c:899
void rep_hist_remove_predicted_ports(const smartlist_t *rmv_ports)
#define LOG_INFO
Definition: log.h:42
Header file for describe.c.
#define DEFAULT_ROUTE_LEN
Definition: or.h:1003
Header file for nodelist.c.
STATIC int new_route_len(uint8_t purpose, extend_info_t *exit_ei, const smartlist_t *nodes)
crypt_path_t * cpath
void tor_log(int severity, log_domain_mask_t domain, const char *format,...)
Definition: log.c:632
const ed25519_public_key_t * node_get_ed25519_id(const node_t *node)
Definition: nodelist.c:1051
void node_get_prim_orport(const node_t *node, tor_addr_port_t *ap_out)
Definition: nodelist.c:1684
void relay_header_unpack(relay_header_t *dest, const uint8_t *src)
Definition: relay.c:483
Header file for directory.c.
int circuit_purpose_is_hidden_service(uint8_t purpose)
Definition: circuituse.c:1965
void smartlist_add(smartlist_t *sl, void *element)
void note_that_we_maybe_cant_complete_circuits(void)
Definition: mainloop.c:234
crypt_path_t * cpath_get_next_non_open_hop(crypt_path_t *cpath)
Definition: crypt_path.c:228
Header file for onion_tap.c.
void note_that_we_completed_a_circuit(void)
Definition: mainloop.c:226
int circuit_id_in_use_on_channel(circid_t circ_id, channel_t *chan)
Definition: circuitlist.c:1540
int circuit_extend(cell_t *cell, circuit_t *circ)
char * rate_limit_log(ratelim_t *lim, time_t now)
Definition: ratelim.c:41
int circuit_truncated(origin_circuit_t *circ, int reason)
#define MAX_NICKNAME_LEN
Definition: or.h:113
int onion_skin_create(int type, const extend_info_t *node, onion_handshake_state_t *state_out, uint8_t *onion_skin_out)
Definition: onion_crypto.c:110
#define TO_CIRCUIT(x)
Definition: or.h:947
#define CIRCUIT_PURPOSE_C_REND_READY
Definition: circuitlist.h:84
Header file for config.c.
Header file for nickname.c.
void router_do_reachability_checks(int test_or, int test_dir)
Definition: selftest.c:172
int circuit_stream_is_being_handled(entry_connection_t *conn, uint16_t port, int min)
Definition: circuituse.c:1039
int fast_mem_is_zero(const char *mem, size_t len)
Definition: util_string.c:74
char * circuit_list_path_for_controller(origin_circuit_t *circ)
Definition: circuitbuild.c:347
Header file for microdesc.c.
#define CIRCUIT_PURPOSE_S_ESTABLISH_INTRO
Definition: circuitlist.h:102
Header file for onion.c.
void circuit_set_state(circuit_t *circ, uint8_t state)
Definition: circuitlist.c:542
const node_t * choose_good_entry_server(uint8_t purpose, cpath_build_state_t *state, circuit_guard_state_t **guard_state_out)
const char * channel_state_to_string(channel_state_t state)
Definition: channel.c:315
static int circuit_purpose_may_omit_guard(int purpose)
Definition: circuitbuild.c:909
int circuit_event_status(origin_circuit_t *circ, circuit_status_event_t tp, int reason_code)
Definition: circuitlist.c:496
int circuit_timeout_want_to_count_circ(const origin_circuit_t *circ)
Definition: circuitbuild.c:842
unsigned int num_n_circuits
Definition: channel.h:416
channel_usage_info_t channel_usage
Definition: channel.h:228
#define tor_free(p)
Definition: malloc.h:52
int channel_is_local(channel_t *chan)
Definition: channel.c:3025
#define tor_fragile_assert()
Definition: util_bug.h:241
int node_has_preferred_descriptor(const node_t *node, int for_direct_connect)
Definition: nodelist.c:1340
#define LOG_NOTICE
Definition: log.h:47
int smartlist_contains_int_as_string(const smartlist_t *sl, int num)
Definition: smartlist.c:147
Header file for mainloop.c.
#define CIRCUIT_PURPOSE_REND_ESTABLISHED
Definition: circuitlist.h:46
circuitmux_t * cmux
Definition: channel.h:403
int circuit_get_cpath_len(origin_circuit_t *circ)
Definition: circuitlist.c:2035
uint8_t purpose
Definition: circuit_st.h:96
void append_cell_to_circuit_queue(circuit_t *circ, channel_t *chan, cell_t *cell, cell_direction_t direction, streamid_t fromstream)
Definition: relay.c:3000
STATIC int onion_pick_cpath_exit(origin_circuit_t *circ, extend_info_t *exit_ei, int is_hs_v3_rp_circuit)
char rend_circ_nonce[DIGEST_LEN]
Definition: or_circuit_st.h:51
int extend_cell_parse(extend_cell_t *cell_out, const uint8_t command, const uint8_t *payload, size_t payload_length)
Definition: onion.c:378
int node_has_curve25519_onion_key(const node_t *node)
Definition: nodelist.c:1872
origin_circuit_t * circuit_establish_circuit(uint8_t purpose, extend_info_t *exit_ei, int flags)
Definition: circuitbuild.c:479
circuit_guard_state_t * origin_circuit_get_guard_state(origin_circuit_t *circ)
Definition: circuitbuild.c:508
static const node_t * pick_restricted_middle_node(router_crn_flags_t flags, const routerset_t *pick_from, const routerset_t *exclude_set, const smartlist_t *exclude_list, int position_hint)
edge_connection_t * TO_EDGE_CONN(connection_t *c)
struct ed25519_public_key_t ed_pubkey
Definition: onion.h:57
#define END_CIRC_REASON_FLAG_REMOTE
Definition: or.h:328
static uint32_t get_uint32(const void *cp)
Definition: bytes.h:49
crypto_pk_t * onion_key
#define CIRCUIT_PURPOSE_C_HSDIR_GET
Definition: circuitlist.h:91
#define CIRCLAUNCH_IS_V3_RP
Definition: circuituse.h:49
extend_info_t * n_hop
Definition: circuit_st.h:76
int node_is_unreliable(const node_t *node, int need_uptime, int need_capacity, int need_guard)
Definition: nodelist.c:2195
void reset_all_main_loop_timers(void)
Definition: mainloop.c:1438
struct create_cell_t * n_chan_create_cell
Definition: circuit_st.h:132
int circuit_should_use_vanguards(uint8_t purpose)
Definition: circuituse.c:1997
static const node_t * choose_good_exit_server_general(router_crn_flags_t flags)
void control_event_bootstrap(bootstrap_status_t status, int progress)
#define MIN_CIRCUITS_HANDLING_STREAM
Definition: or.h:180
Header file for policies.c.
channel_t * p_chan
Definition: or_circuit_st.h:35
int ed25519_pubkey_eq(const ed25519_public_key_t *key1, const ed25519_public_key_t *key2)
#define LD_APP
Definition: log.h:75
int control_event_general_status(int severity, const char *format,...)
#define CIRCUIT_PURPOSE_CONTROLLER
Definition: circuitlist.h:119
void nodelist_add_node_and_family(smartlist_t *sl, const node_t *node)
Definition: nodelist.c:2099
static void circuit_pick_extend_handshake(uint8_t *cell_type_out, uint8_t *create_cell_type_out, uint16_t *handshake_type_out, const extend_info_t *ei)
Definition: circuitbuild.c:883
const curve25519_public_key_t * node_get_curve25519_onion_key(const node_t *node)
Definition: nodelist.c:1879
Header file for channel.c.
int ExtendAllowPrivateAddresses
tor_assert(buffer)
void channel_timestamp_client(channel_t *chan)
Definition: channel.c:3219
routerset_t * ExitNodes
Definition: or_options_st.h:72
#define MAX_VERBOSE_NICKNAME_LEN
Definition: or.h:119
guard_usable_t entry_guard_succeeded(circuit_guard_state_t **guard_state_p)
Definition: entrynodes.c:2432
int node_get_purpose(const node_t *node)
Definition: nodelist.c:1361
#define LD_CIRC
Definition: log.h:79
uint8_t state
Definition: circuit_st.h:95
Header file for routermode.c.
void ocirc_event_publish(const ocirc_event_msg_t *msg)
Definition: ocirc_event.c:70
int connection_ap_can_use_exit(const entry_connection_t *conn, const node_t *exit_node)
#define LD_GUARD
Definition: log.h:106
int tor_memeq(const void *a, const void *b, size_t sz)
Definition: di_ops.c:107
const node_t * guards_choose_guard(cpath_build_state_t *state, uint8_t purpose, circuit_guard_state_t **guard_state_out)
Definition: entrynodes.c:3613
static int circuit_build_no_more_hops(origin_circuit_t *circ)
const char * fmt_addrport(const tor_addr_t *addr, uint16_t port)
Definition: address.c:1168
void clear_broken_connection_map(int stop_recording)
routerset_t * ExcludeNodes
Definition: or_options_st.h:84
circid_t n_circ_id
Definition: circuit_st.h:67
static int circuit_deliver_create_cell(circuit_t *circ, const create_cell_t *create_cell, int relayed)
Definition: circuitbuild.c:712
time_t circuit_id_when_marked_unusable_on_channel(circid_t circ_id, channel_t *chan)
Definition: circuitlist.c:1553
Header file for circuitpadding.c.
char nickname[MAX_HEX_NICKNAME_LEN+1]
#define DIGEST_LEN
Definition: digest_sizes.h:20
#define CIRCUIT_PURPOSE_C_INTRODUCE_ACKED
Definition: circuitlist.h:80
#define CIRCUIT_PURPOSE_TESTING
Definition: circuitlist.h:117
const char * node_describe(const node_t *node)
Definition: describe.c:101
void smartlist_add_asprintf(struct smartlist_t *sl, const char *pattern,...)
Definition: smartlist.c:36
int ed25519_public_key_is_zero(const ed25519_public_key_t *pubkey)
char identity[DIGEST_LEN]
Definition: node_st.h:40
Header file for circuitbuild.c.
void ed25519_pubkey_copy(ed25519_public_key_t *dest, const ed25519_public_key_t *src)
static int circuit_cpath_supports_ntor(const origin_circuit_t *circ)
Definition: circuitbuild.c:366
Master header file for Tor-specific functionality.
#define CIRCUIT_STATE_OPEN
Definition: circuitlist.h:31
uint8_t reply[CELL_PAYLOAD_SIZE - 2]
Definition: onion.h:42
const char * hex_str(const char *from, size_t fromlen)
Definition: binascii.c:34
int extend_info_is_a_configured_bridge(const extend_info_t *ei)
Definition: bridges.c:264
Header file for circuitbuild.c.
void node_get_verbose_nickname(const node_t *node, char *verbose_name_out)
Definition: nodelist.c:1373
uint16_t marked_for_close
void circuit_mark_all_unused_circs(void)
Definition: circuitlist.c:2087
#define AP_CONN_STATE_CIRCUIT_WAIT
STATIC circid_t get_unique_circ_id_by_chan(channel_t *chan)
Definition: circuitbuild.c:127
Header file for onion_fast.c.
void cpath_free(crypt_path_t *victim)
Definition: crypt_path.c:162
uint8_t cell_type
Definition: onion.h:26
circid_t circ_id
Definition: cell_st.h:13
#define LOG_WARN
Definition: log.h:50
extend_info_t * extend_info_dup(extend_info_t *info)
int tor_addr_is_null(const tor_addr_t *addr)
Definition: address.c:769
unsigned int type
Definition: connection_st.h:45
const node_t * router_choose_random_node(smartlist_t *excludedsmartlist, routerset_t *excludedset, router_crn_flags_t flags)
Definition: node_select.c:903
static int middle_node_must_be_vanguard(const or_options_t *options, uint8_t purpose, int cur_len)
#define log_fn_ratelim(ratelim, severity, domain, args,...)
Definition: log.h:271
char nickname[MAX_NICKNAME_LEN+1]
char rend_circ_nonce[DIGEST_LEN]
Definition: crypt_path_st.h:53
Header file for circuituse.c.
void base16_encode(char *dest, size_t destlen, const char *src, size_t srclen)
Definition: binascii.c:478
int onionskin_answer(or_circuit_t *circ, const created_cell_t *created_cell, const char *keys, size_t keys_len, const uint8_t *rend_circ_nonce)
static const node_t * pick_vanguard_middle_node(const or_options_t *options, router_crn_flags_t flags, int cur_len, const smartlist_t *excluded)
static int should_use_create_fast_for_circuit(origin_circuit_t *circ)
Definition: circuitbuild.c:808
static channel_t * channel_connect_for_circuit(const tor_addr_t *addr, uint16_t port, const char *id_digest, const ed25519_public_key_t *ed_id)
Definition: circuitbuild.c:108
const node_t * build_state_get_exit_node(cpath_build_state_t *state)
#define CIRCUIT_PURPOSE_C_ESTABLISH_REND
Definition: circuitlist.h:82
static const node_t * choose_good_middle_server(uint8_t purpose, cpath_build_state_t *state, crypt_path_t *head, int cur_len)
static int ap_stream_wants_exit_attention(connection_t *conn)
circid_t p_circ_id
Definition: or_circuit_st.h:31
void circuit_remove_handled_ports(smartlist_t *needed_ports)
Definition: circuituse.c:1014
#define CIRCUIT_PURPOSE_S_CONNECT_REND
Definition: circuitlist.h:108
#define LD_REND
Definition: log.h:81
routerset_t * HSLayer2Nodes
Header file for circuitlist.c.
crypto_pk_t * crypto_pk_dup_key(crypto_pk_t *orig)
int control_event_client_status(int severity, const char *format,...)
void circuit_log_path(int severity, unsigned int domain, origin_circuit_t *circ)
Definition: circuitbuild.c:357
Headers for transports.c.
smartlist_t * rep_hist_get_predicted_ports(time_t now)
#define LD_OR
Definition: log.h:89
int channel_matches_extend_info(channel_t *chan, extend_info_t *extend_info)
Definition: channel.c:3313
int tor_digest_is_zero(const char *digest)
Definition: util_string.c:96
int cpath_init_circuit_crypto(crypt_path_t *cpath, const char *key_data, size_t key_data_len, int reverse, int is_hs_v3)
Definition: crypt_path.c:150
#define CIRCLAUNCH_NEED_CAPACITY
Definition: circuituse.h:43
int tor_addr_is_multicast(const tor_addr_t *a)
Definition: address.c:1499
uint8_t cell_type
Definition: onion.h:48
router_crn_flags_t
Definition: node_select.h:16
int connection_edge_is_rendezvous_stream(const edge_connection_t *conn)
int is_legal_nickname(const char *s)
Definition: nickname.c:19
#define HEX_DIGEST_LEN
Definition: crypto_digest.h:35
void smartlist_subtract(smartlist_t *sl1, const smartlist_t *sl2)
Definition: smartlist.c:264
#define CIRCUIT_PURPOSE_HS_VANGUARDS
Definition: circuitlist.h:129
#define END_CIRC_REASON_NOPATH
Definition: or.h:303
uint16_t length
Definition: or.h:642
uint8_t command
Definition: or.h:638
struct crypt_path_t * prev
Definition: crypt_path_st.h:70
cpath_build_state_t * build_state
Header file for connection_edge.c.
routerset_t * HSLayer3Nodes
void router_add_running_nodes_to_smartlist(smartlist_t *sl, int need_uptime, int need_capacity, int need_guard, int need_desc, int pref_addr, int direct_conn)
Definition: routerlist.c:504
routerset_t * ExcludeExitNodesUnion_
Definition: or_options_st.h:93
origin_circuit_t * TO_ORIGIN_CIRCUIT(circuit_t *x)
Definition: circuitlist.c:163
void circuit_has_opened(origin_circuit_t *circ)
Definition: circuituse.c:1685
Header file for crypt_path.c.
int tor_snprintf(char *str, size_t size, const char *format,...)
Definition: printf.c:27
char * smartlist_join_strings(smartlist_t *sl, const char *join, int terminate, size_t *len_out)
Definition: smartlist.c:279
int circuit_send_next_onion_skin(origin_circuit_t *circ)
Definition: circuitbuild.c:938
void circuit_mark_all_dirty_circs_as_unusable(void)
Definition: circuitlist.c:2106
#define CIRCUIT_PURPOSE_INTRO_POINT
Definition: circuitlist.h:41
Header file for relay.c.
edge_connection_t * p_streams
char identity_digest[DIGEST_LEN]
#define SMARTLIST_FOREACH(sl, type, var, cmd)
unsigned int has_opened
#define CIRCUIT_PURPOSE_S_HSDIR_POST
Definition: circuitlist.h:113
Header file for router.c.
void routerset_subtract_nodes(smartlist_t *lst, const routerset_t *routerset)
Definition: routerset.c:394
origin_circuit_t * origin_circuit_new(void)
Definition: circuitlist.c:1013
int created_cell_format(cell_t *cell_out, const created_cell_t *cell_in)
Definition: onion.c:546
static char * circuit_list_path_impl(origin_circuit_t *circ, int verbose, int verbose_names)
Definition: circuitbuild.c:264
#define CIRCUIT_PURPOSE_C_INTRODUCE_ACK_WAIT
Definition: circuitlist.h:77
int circuit_get_cpath_opened_len(const origin_circuit_t *circ)
Definition: circuitlist.c:2051
char * nickname
Definition: routerinfo_st.h:17
#define CIRCUIT_PURPOSE_C_REND_JOINED
Definition: circuitlist.h:89
uint8_t state
Definition: crypt_path_st.h:63
onion_handshake_state_t handshake_state
Definition: crypt_path_st.h:47
uint16_t handshake_type
Definition: onion.h:28
uint32_t circid_t
Definition: or.h:608
#define CIRCUIT_PURPOSE_OR
Definition: circuitlist.h:38
uint16_t dir_port
Definition: routerinfo_st.h:21
struct timeval timestamp_began
Definition: circuit_st.h:144
#define log_fn(severity, domain, args,...)
Definition: log.h:266
#define CIRCUIT_STATE_GUARD_WAIT
Definition: circuitlist.h:29
ratelim_t last_warned_circ_ids_exhausted
Definition: channel.h:444
static void circuit_pick_create_handshake(uint8_t *cell_type_out, uint16_t *handshake_type_out, const extend_info_t *ei)
Definition: circuitbuild.c:857
#define CIRCUIT_STATE_BUILDING
Definition: circuitlist.h:20
uint8_t node_id[DIGEST_LEN]
Definition: onion.h:55
int router_digest_is_me(const char *digest)
Definition: router.c:1592
or_circuit_t * TO_OR_CIRCUIT(circuit_t *x)
Definition: circuitlist.c:151
unsigned int circuitmux_num_circuits(circuitmux_t *cmux)
Definition: circuitmux.c:763
const node_t * node_sl_choose_by_bandwidth(const smartlist_t *sl, bandwidth_weight_rule_t rule)
Definition: node_select.c:803
static int node_handles_some_port(const node_t *node, smartlist_t *needed_ports)
void circpad_machine_event_circ_built(origin_circuit_t *circ)
void circuit_reset_failure_count(int timeout)
Definition: circuituse.c:2194
channel_t * channel_connect(const tor_addr_t *addr, uint16_t port, const char *id_digest, const ed25519_public_key_t *ed_id)
Definition: channel.c:2316
char * circuit_list_path(origin_circuit_t *circ, int verbose)
Definition: circuitbuild.c:338
#define CIRCUIT_PURPOSE_C_GENERAL
Definition: circuitlist.h:71
static const node_t * choose_good_exit_server(origin_circuit_t *circ, router_crn_flags_t flags, int is_internal)
time_t approx_time(void)
Definition: approx_time.c:32
void fascist_firewall_choose_address_node(const node_t *node, firewall_connection_t fw_connection, int pref_only, tor_addr_port_t *ap)
Definition: policies.c:1100
int node_exit_policy_rejects_all(const node_t *node)
Definition: nodelist.c:1419
routerset_t * MiddleNodes
Definition: or_options_st.h:75
extend_info_t * extend_info
Definition: crypt_path_st.h:56
#define CIRCUIT_STATE_CHAN_WAIT
Definition: circuitlist.h:25
uint32_t addr
Definition: routerinfo_st.h:19
void circuit_set_n_circid_chan(circuit_t *circ, circid_t id, channel_t *chan)
Definition: circuitlist.c:471
#define TIMEOUT_UNTIL_UNREACHABILITY_COMPLAINT
Definition: or.h:549
void command_setup_channel(channel_t *chan)
Definition: command.c:683
tor_addr_port_t orport_ipv4
Definition: onion.h:50
Header file for selftest.c.
int pathbias_count_build_attempt(origin_circuit_t *circ)
Definition: circpathbias.c:424
Header file for ocirc_event.c.
void circuit_build_times_handle_completed_hop(origin_circuit_t *circ)
Definition: circuitstats.c:683
Header file for connection_or.c.
int control_event_server_status(int severity, const char *format,...)
int circuit_append_new_exit(origin_circuit_t *circ, extend_info_t *exit_ei)
void routerset_get_all_nodes(smartlist_t *out, const routerset_t *routerset, const routerset_t *excludeset, int running_only)
Definition: routerset.c:360
extend_info_t * chosen_exit
unsigned int circuitmux_num_active_circuits(circuitmux_t *cmux)
Definition: circuitmux.c:751
static smartlist_t * build_vanguard_middle_exclude_list(uint8_t purpose, cpath_build_state_t *state, crypt_path_t *head, int cur_len)
char identity_digest[DIGEST_LEN]
Definition: channel.h:384
uint16_t handshake_len
Definition: onion.h:40
relay_crypto_t crypto
Definition: or_circuit_st.h:44
struct edge_connection_t * next_stream
tor_addr_t addr
void tor_addr_copy(tor_addr_t *dest, const tor_addr_t *src)
Definition: address.c:903
void onion_handshake_state_release(onion_handshake_state_t *state)
Definition: onion_crypto.c:79
void extend_info_free_(extend_info_t *info)
STATIC int onion_extend_cpath(origin_circuit_t *circ)
#define CIRCUIT_PURPOSE_S_REND_JOINED
Definition: circuitlist.h:111
#define CONN_TYPE_AP
Definition: connection.h:31
Header file for control_events.c.
ed25519_public_key_t ed_identity
void smartlist_clear(smartlist_t *sl)
#define LD_PROTOCOL
Definition: log.h:69
static int onion_populate_cpath(origin_circuit_t *circ)
Definition: circuitbuild.c:390
smartlist_t * circuit_find_circuits_to_upgrade_from_guard_wait(void)
Definition: circuitlist.c:2007
void router_orport_found_reachable(void)
Definition: selftest.c:220
const char * build_state_get_exit_nickname(cpath_build_state_t *state)
static int circuit_send_intermediate_onion_skin(origin_circuit_t *circ, crypt_path_t *hop)
#define RELAY_HEADER_SIZE
Definition: or.h:603
int check_whether_orport_reachable(const or_options_t *options)
Definition: selftest.c:75
int extend_info_addr_is_allowed(const tor_addr_t *addr)
int onion_skin_client_handshake(int type, const onion_handshake_state_t *handshake_state, const uint8_t *reply, size_t reply_len, uint8_t *keys_out, size_t keys_out_len, uint8_t *rend_authenticator_out, const char **msg_out)
Definition: onion_crypto.c:247
Header file for networkstatus.c.
#define LD_BUG
Definition: log.h:83
void circuit_upgrade_circuits_from_guard_wait(void)
int cpath_append_hop(crypt_path_t **head_ptr, extend_info_t *choice)
Definition: crypt_path.c:61
int circuit_extend_to_new_exit(origin_circuit_t *circ, extend_info_t *exit_ei)
#define CURVE25519_PUBKEY_LEN
Definition: x25519_sizes.h:20
int inform_testing_reachability(void)
Definition: circuitbuild.c:775
MOCK_IMPL(int, circuit_all_predicted_ports_handled,(time_t now, int *need_uptime, int *need_capacity))
Header file for routerlist.c.
const uint8_t * build_state_get_exit_rsa_id(cpath_build_state_t *state)
uint16_t or_port
Definition: routerinfo_st.h:20
channel_t * n_chan
Definition: circuit_st.h:58
static int circuit_send_first_onion_skin(origin_circuit_t *circ)
Definition: circuitbuild.c:972
static sa_family_t tor_addr_family(const tor_addr_t *a)
Definition: address.h:179
void * smartlist_choose(const smartlist_t *sl)
Definition: crypto_rand.c:590
create_cell_t create_cell
Definition: onion.h:61
Header for confparse.c.
void circuit_note_clock_jumped(int64_t seconds_elapsed, bool was_idle)
int have_completed_a_circuit(void)
Definition: mainloop.c:218
tor_addr_port_t orport_ipv6
Definition: onion.h:53
uint64_t global_identifier
Definition: channel.h:197
Header file for onion_crypto.c.
char * tor_dup_ip(uint32_t addr)
Definition: address.c:1890