circuitbuild.c 94.1 KB
Newer Older
Roger Dingledine's avatar
Roger Dingledine committed
1
2
/* Copyright (c) 2001 Matej Pfajfar.
 * Copyright (c) 2001-2004, Roger Dingledine.
3
 * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
4
 * Copyright (c) 2007-2020, The Tor Project, Inc. */
5
6
7
8
/* See LICENSE for licensing information */

/**
 * \file circuitbuild.c
9
10
11
 *
 * \brief Implements the details of building circuits (by chosing paths,
 * constructing/sending create/extend cells, and so on).
12
13
14
15
16
17
18
19
20
21
22
23
 *
 * On the client side, this module handles launching circuits. Circuit
 * launches are srtarted from circuit_establish_circuit(), called from
 * circuit_launch_by_extend_info()).  To choose the path the circuit will
 * take, onion_extend_cpath() calls into a maze of node selection functions.
 *
 * Once the circuit is ready to be launched, the first hop is treated as a
 * special case with circuit_handle_first_hop(), since it might need to open a
 * channel.  As the channel opens, and later as CREATED and RELAY_EXTENDED
 * cells arrive, the client will invoke circuit_send_next_onion_skin() to send
 * CREATE or RELAY_EXTEND cells.
 *
24
 * The server side is handled in feature/relay/circuitbuild_relay.c.
25
26
 **/

27
#define CIRCUITBUILD_PRIVATE
28
#define OCIRC_EVENT_PRIVATE
29

30
#include "core/or/or.h"
31
#include "app/config/config.h"
32
#include "lib/confmgt/confmgt.h"
33
34
35
36
37
38
#include "core/crypto/hs_ntor.h"
#include "core/crypto/onion_crypto.h"
#include "core/crypto/onion_fast.h"
#include "core/crypto/onion_tap.h"
#include "core/mainloop/connection.h"
#include "core/mainloop/mainloop.h"
39
40
41
42
43
#include "core/or/channel.h"
#include "core/or/circuitbuild.h"
#include "core/or/circuitlist.h"
#include "core/or/circuitstats.h"
#include "core/or/circuituse.h"
44
#include "core/or/circuitpadding.h"
45
46
47
#include "core/or/command.h"
#include "core/or/connection_edge.h"
#include "core/or/connection_or.h"
48
#include "core/or/onion.h"
49
#include "core/or/ocirc_event.h"
50
51
#include "core/or/policies.h"
#include "core/or/relay.h"
52
#include "core/or/crypt_path.h"
53
54
55
56
#include "feature/client/bridges.h"
#include "feature/client/circpathbias.h"
#include "feature/client/entrynodes.h"
#include "feature/client/transports.h"
57
#include "feature/control/control_events.h"
58
#include "feature/dircommon/directory.h"
59
#include "feature/nodelist/describe.h"
60
61
#include "feature/nodelist/microdesc.h"
#include "feature/nodelist/networkstatus.h"
62
#include "feature/nodelist/nickname.h"
63
#include "feature/nodelist/node_select.h"
64
#include "feature/nodelist/nodelist.h"
65
66
#include "feature/nodelist/routerlist.h"
#include "feature/nodelist/routerset.h"
67
68
69
70
#include "feature/relay/router.h"
#include "feature/relay/routermode.h"
#include "feature/relay/selftest.h"
#include "feature/rend/rendcommon.h"
71
#include "feature/stats/predict_ports.h"
72
#include "lib/crypt_ops/crypto_rand.h"
73

74
75
76
77
78
79
80
81
82
83
#include "core/or/cell_st.h"
#include "core/or/cpath_build_state_st.h"
#include "core/or/entry_connection_st.h"
#include "core/or/extend_info_st.h"
#include "feature/nodelist/node_st.h"
#include "core/or/or_circuit_st.h"
#include "core/or/origin_circuit_st.h"
#include "feature/nodelist/microdesc_st.h"
#include "feature/nodelist/routerinfo_st.h"
#include "feature/nodelist/routerstatus_st.h"
84

85
86
87
88
static int circuit_send_first_onion_skin(origin_circuit_t *circ);
static int circuit_build_no_more_hops(origin_circuit_t *circ);
static int circuit_send_intermediate_onion_skin(origin_circuit_t *circ,
                                                crypt_path_t *hop);
89
90
91
92
static const node_t *choose_good_middle_server(uint8_t purpose,
                          cpath_build_state_t *state,
                          crypt_path_t *head,
                          int cur_len);
93

94
95
96
97
/** This function tries to get a channel to the specified endpoint,
 * and then calls command_setup_channel() to give it the right
 * callbacks.
 */
98
99
100
101
MOCK_IMPL(channel_t *,
channel_connect_for_circuit,(const tor_addr_t *addr, uint16_t port,
                             const char *id_digest,
                             const struct ed25519_public_key_t *ed_id))
102
103
104
{
  channel_t *chan;

105
  chan = channel_connect(addr, port, id_digest, ed_id);
106
107
108
109
110
  if (chan) command_setup_channel(chan);

  return chan;
}

111
112
113
/** Search for a value for circ_id that we can use on <b>chan</b> for an
 * outbound circuit, until we get a circ_id that is not in use by any other
 * circuit on that conn.
Mike Perry's avatar
Mike Perry committed
114
 *
115
 * Return it, or 0 if can't get a unique circ_id.
Mike Perry's avatar
Mike Perry committed
116
 */
117
STATIC circid_t
118
get_unique_circ_id_by_chan(channel_t *chan)
119
{
120
121
122
123
124
125
/* This number is chosen somewhat arbitrarily; see comment below for more
 * info.  When the space is 80% full, it gives a one-in-a-million failure
 * chance; when the space is 90% full, it gives a one-in-850 chance; and when
 * the space is 95% full, it gives a one-in-26 failure chance.  That seems
 * okay, though you could make a case IMO for anything between N=32 and
 * N=256. */
126
#define MAX_CIRCID_ATTEMPTS 64
127
  int in_use;
Nick Mathewson's avatar
Nick Mathewson committed
128
  unsigned n_with_circ = 0, n_pending_destroy = 0, n_weird_pending_destroy = 0;
129
130
  circid_t test_circ_id;
  circid_t attempts=0;
131
  circid_t high_bit, max_range, mask;
Nick Mathewson's avatar
Nick Mathewson committed
132
133
  int64_t pending_destroy_time_total = 0;
  int64_t pending_destroy_time_max = 0;
134
135
136
137
138
139
140

  tor_assert(chan);

  if (chan->circ_id_type == CIRC_ID_TYPE_NEITHER) {
    log_warn(LD_BUG,
             "Trying to pick a circuit ID for a connection from "
             "a client with no identity.");
141
    return 0;
142
  }
143
144
  max_range = (chan->wide_circ_ids) ? (1u<<31) : (1u<<15);
  mask = max_range - 1;
145
  high_bit = (chan->circ_id_type == CIRC_ID_TYPE_HIGHER) ? max_range : 0;
146
  do {
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
    if (++attempts > MAX_CIRCID_ATTEMPTS) {
      /* Make sure we don't loop forever because all circuit IDs are used.
       *
       * Once, we would try until we had tried every possible circuit ID.  But
       * that's quite expensive.  Instead, we try MAX_CIRCID_ATTEMPTS random
       * circuit IDs, and then give up.
       *
       * This potentially causes us to give up early if our circuit ID space
       * is nearly full.  If we have N circuit IDs in use, then we will reject
       * a new circuit with probability (N / max_range) ^ MAX_CIRCID_ATTEMPTS.
       * This means that in practice, a few percent of our circuit ID capacity
       * will go unused.
       *
       * The alternative here, though, is to do a linear search over the
       * whole circuit ID space every time we extend a circuit, which is
       * not so great either.
163
       */
Nick Mathewson's avatar
Nick Mathewson committed
164
165
166
167
168
169
170
171
      int64_t queued_destroys;
      char *m = rate_limit_log(&chan->last_warned_circ_ids_exhausted,
                               approx_time());
      if (m == NULL)
        return 0; /* This message has been rate-limited away. */
      if (n_pending_destroy)
        pending_destroy_time_total /= n_pending_destroy;
      log_warn(LD_CIRC,"No unused circIDs found on channel %s wide "
172
                 "circID support, with %u inbound and %u outbound circuits. "
173
                 "Found %u circuit IDs in use by circuits, and %u with "
Nick Mathewson's avatar
Nick Mathewson committed
174
175
176
177
178
                 "pending destroy cells. (%u of those were marked bogusly.) "
                 "The ones with pending destroy cells "
                 "have been marked unusable for an average of %ld seconds "
                 "and a maximum of %ld seconds. This channel is %ld seconds "
                 "old. Failing a circuit.%s",
179
                 chan->wide_circ_ids ? "with" : "without",
180
                 chan->num_p_circuits, chan->num_n_circuits,
Nick Mathewson's avatar
Nick Mathewson committed
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
                 n_with_circ, n_pending_destroy, n_weird_pending_destroy,
                 (long)pending_destroy_time_total,
                 (long)pending_destroy_time_max,
                 (long)(approx_time() - chan->timestamp_created),
                 m);
      tor_free(m);

      if (!chan->cmux) {
        /* This warning should be impossible. */
        log_warn(LD_BUG, "  This channel somehow has no cmux on it!");
        return 0;
      }

      /* analysis so far on 12184 suggests that we're running out of circuit
         IDs because it looks like we have too many pending destroy
         cells. Let's see how many we really have pending.
      */
      queued_destroys = circuitmux_count_queued_destroy_cells(chan,
                                                              chan->cmux);

      log_warn(LD_CIRC, "  Circuitmux on this channel has %u circuits, "
202
               "of which %u are active. It says it has %"PRId64
Nick Mathewson's avatar
Nick Mathewson committed
203
204
205
               " destroy cells queued.",
               circuitmux_num_circuits(chan->cmux),
               circuitmux_num_active_circuits(chan->cmux),
206
               (queued_destroys));
Nick Mathewson's avatar
Nick Mathewson committed
207
208
209
210
211
212
213
214

      /* Change this into "if (1)" in order to get more information about
       * possible failure modes here.  You'll need to know how to use gdb with
       * Tor: this will make Tor exit with an assertion failure if the cmux is
       * corrupt. */
      if (0)
        circuitmux_assert_okay(chan->cmux);

215
216
      channel_dump_statistics(chan, LOG_WARN);

Mike Perry's avatar
Mike Perry committed
217
218
      return 0;
    }
219

220
221
222
223
224
    do {
      crypto_rand((char*) &test_circ_id, sizeof(test_circ_id));
      test_circ_id &= mask;
    } while (test_circ_id == 0);

225
    test_circ_id |= high_bit;
226
227
228
229

    in_use = circuit_id_in_use_on_channel(test_circ_id, chan);
    if (in_use == 1)
      ++n_with_circ;
Nick Mathewson's avatar
Nick Mathewson committed
230
231
    else if (in_use == 2) {
      time_t since_when;
232
      ++n_pending_destroy;
Nick Mathewson's avatar
Nick Mathewson committed
233
234
235
236
237
238
239
240
241
242
243
      since_when =
        circuit_id_when_marked_unusable_on_channel(test_circ_id, chan);
      if (since_when) {
        time_t waiting = approx_time() - since_when;
        pending_destroy_time_total += waiting;
        if (waiting > pending_destroy_time_max)
          pending_destroy_time_max = waiting;
      } else {
        ++n_weird_pending_destroy;
      }
    }
244
  } while (in_use);
245
  return test_circ_id;
246
247
}

248
249
250
/** If <b>verbose</b> is false, allocate and return a comma-separated list of
 * the currently built elements of <b>circ</b>. If <b>verbose</b> is true, also
 * list information about link status in a more verbose format using spaces.
251
252
 * If <b>verbose_names</b> is false, give hex digests; if <b>verbose_names</b>
 * is true, use $DIGEST=Name style names.
Mike Perry's avatar
Mike Perry committed
253
 */
254
255
static char *
circuit_list_path_impl(origin_circuit_t *circ, int verbose, int verbose_names)
Mike Perry's avatar
Mike Perry committed
256
{
257
258
259
260
  crypt_path_t *hop;
  smartlist_t *elements;
  const char *states[] = {"closed", "waiting for keys", "open"};
  char *s;
261

262
  elements = smartlist_new();
Mike Perry's avatar
Mike Perry committed
263

264
265
266
267
268
269
270
271
272
  if (verbose) {
    const char *nickname = build_state_get_exit_nickname(circ->build_state);
    smartlist_add_asprintf(elements, "%s%s circ (length %d%s%s):",
                 circ->build_state->is_internal ? "internal" : "exit",
                 circ->build_state->need_uptime ? " (high-uptime)" : "",
                 circ->build_state->desired_path_len,
                 circ->base_.state == CIRCUIT_STATE_OPEN ? "" : ", last hop ",
                 circ->base_.state == CIRCUIT_STATE_OPEN ? "" :
                 (nickname?nickname:"*unnamed*"));
273
274
  }

275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
  hop = circ->cpath;
  do {
    char *elt;
    const char *id;
    const node_t *node;
    if (!hop)
      break;
    if (!verbose && hop->state != CPATH_STATE_OPEN)
      break;
    if (!hop->extend_info)
      break;
    id = hop->extend_info->identity_digest;
    if (verbose_names) {
      elt = tor_malloc(MAX_VERBOSE_NICKNAME_LEN+1);
      if ((node = node_get_by_id(id))) {
        node_get_verbose_nickname(node, elt);
      } else if (is_legal_nickname(hop->extend_info->nickname)) {
        elt[0] = '$';
        base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN);
        elt[HEX_DIGEST_LEN+1]= '~';
        strlcpy(elt+HEX_DIGEST_LEN+2,
                hop->extend_info->nickname, MAX_NICKNAME_LEN+1);
      } else {
        elt[0] = '$';
        base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN);
      }
    } else { /* ! verbose_names */
302
303
304
      elt = tor_malloc(HEX_DIGEST_LEN+2);
      elt[0] = '$';
      base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN);
305
306
307
308
309
310
311
312
313
314
315
    }
    tor_assert(elt);
    if (verbose) {
      tor_assert(hop->state <= 2);
      smartlist_add_asprintf(elements,"%s(%s)",elt,states[hop->state]);
      tor_free(elt);
    } else {
      smartlist_add(elements, elt);
    }
    hop = hop->next;
  } while (hop != circ->cpath);
316

317
318
319
320
  s = smartlist_join_strings(elements, verbose?" ":",", 0, NULL);
  SMARTLIST_FOREACH(elements, char*, cp, tor_free(cp));
  smartlist_free(elements);
  return s;
Mike Perry's avatar
Mike Perry committed
321
322
}

323
324
325
326
327
328
329
/** If <b>verbose</b> is false, allocate and return a comma-separated
 * list of the currently built elements of <b>circ</b>.  If
 * <b>verbose</b> is true, also list information about link status in
 * a more verbose format using spaces.
 */
char *
circuit_list_path(origin_circuit_t *circ, int verbose)
330
{
331
  return circuit_list_path_impl(circ, verbose, 0);
332
333
}

334
335
/** Allocate and return a comma-separated list of the currently built elements
 * of <b>circ</b>, giving each as a verbose nickname.
Mike Perry's avatar
Mike Perry committed
336
 */
337
338
char *
circuit_list_path_for_controller(origin_circuit_t *circ)
Mike Perry's avatar
Mike Perry committed
339
{
340
  return circuit_list_path_impl(circ, 0, 1);
Mike Perry's avatar
Mike Perry committed
341
342
}

343
344
345
346
347
348
/** Log, at severity <b>severity</b>, the nicknames of each router in
 * <b>circ</b>'s cpath. Also log the length of the cpath, and the intended
 * exit point.
 */
void
circuit_log_path(int severity, unsigned int domain, origin_circuit_t *circ)
349
{
350
351
352
  char *s = circuit_list_path(circ,1);
  tor_log(severity,domain,"%s",s);
  tor_free(s);
353
354
}

355
/** Return 1 iff every node in circ's cpath definitely supports ntor. */
356
357
358
static int
circuit_cpath_supports_ntor(const origin_circuit_t *circ)
{
359
  crypt_path_t *head, *cpath;
360

361
  cpath = head = circ->cpath;
362
  do {
363
364
365
366
    /* if the extend_info is missing, we can't tell if it supports ntor */
    if (!cpath->extend_info) {
      return 0;
    }
367

368
369
370
371
    /* if the key is blank, it definitely doesn't support ntor */
    if (!extend_info_supports_ntor(cpath->extend_info)) {
      return 0;
    }
372
373
374
    cpath = cpath->next;
  } while (cpath != head);

375
  return 1;
376
377
}

378
379
380
381
/** Pick all the entries in our cpath. Stop and return 0 when we're
 * happy, or return -1 if an error occurs. */
static int
onion_populate_cpath(origin_circuit_t *circ)
Mike Perry's avatar
Mike Perry committed
382
{
383
  int r = 0;
384

385
386
387
  /* onion_extend_cpath assumes these are non-NULL */
  tor_assert(circ);
  tor_assert(circ->build_state);
388

389
390
  while (r == 0) {
    r = onion_extend_cpath(circ);
391
392
393
394
    if (r < 0) {
      log_info(LD_CIRC,"Generating cpath hop failed.");
      return -1;
    }
395
  }
396

397
398
  /* The path is complete */
  tor_assert(r == 1);
399

400
401
402
403
404
405
406
  /* Does every node in this path support ntor? */
  int path_supports_ntor = circuit_cpath_supports_ntor(circ);

  /* We would like every path to support ntor, but we have to allow for some
   * edge cases. */
  tor_assert(circuit_get_cpath_len(circ));
  if (circuit_can_use_tap(circ)) {
David Goulet's avatar
David Goulet committed
407
408
409
410
    /* Circuits from clients to intro points, and hidden services to rend
     * points do not support ntor, because the hidden service protocol does
     * not include ntor onion keys. This is also true for Single Onion
     * Services. */
411
412
    return 0;
  }
413

414
415
416
417
418
419
420
421
422
423
424
  if (circuit_get_cpath_len(circ) == 1) {
    /* Allow for bootstrapping: when we're fetching directly from a fallback,
     * authority, or bridge, we have no way of knowing its ntor onion key
     * before we connect to it. So instead, we try connecting, and end up using
     * CREATE_FAST. */
    tor_assert(circ->cpath);
    tor_assert(circ->cpath->extend_info);
    const node_t *node = node_get_by_id(
                                    circ->cpath->extend_info->identity_digest);
    /* If we don't know the node and its descriptor, we must be bootstrapping.
     */
425
    if (!node || !node_has_preferred_descriptor(node, 1)) {
426
      return 0;
427
    }
428
  }
429

430
431
432
433
434
435
436
437
  if (BUG(!path_supports_ntor)) {
    /* If we're building a multi-hop path, and it's not one of the HS or
     * bootstrapping exceptions, and it doesn't support ntor, something has
     * gone wrong. */
    return -1;
  }

  return 0;
Mike Perry's avatar
Mike Perry committed
438
439
}

440
441
442
443
444
/** Create and return a new origin circuit. Initialize its purpose and
 * build-state based on our arguments.  The <b>flags</b> argument is a
 * bitfield of CIRCLAUNCH_* flags. */
origin_circuit_t *
origin_circuit_init(uint8_t purpose, int flags)
Mike Perry's avatar
Mike Perry committed
445
{
446
447
448
449
450
451
452
453
454
455
456
457
458
459
  /* sets circ->p_circ_id and circ->p_chan */
  origin_circuit_t *circ = origin_circuit_new();
  circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_CHAN_WAIT);
  circ->build_state = tor_malloc_zero(sizeof(cpath_build_state_t));
  circ->build_state->onehop_tunnel =
    ((flags & CIRCLAUNCH_ONEHOP_TUNNEL) ? 1 : 0);
  circ->build_state->need_uptime =
    ((flags & CIRCLAUNCH_NEED_UPTIME) ? 1 : 0);
  circ->build_state->need_capacity =
    ((flags & CIRCLAUNCH_NEED_CAPACITY) ? 1 : 0);
  circ->build_state->is_internal =
    ((flags & CIRCLAUNCH_IS_INTERNAL) ? 1 : 0);
  circ->base_.purpose = purpose;
  return circ;
Mike Perry's avatar
Mike Perry committed
460
461
}

462
463
464
/** Build a new circuit for <b>purpose</b>. If <b>exit</b>
 * is defined, then use that as your exit router, else choose a suitable
 * exit node.
Mike Perry's avatar
Mike Perry committed
465
 *
466
467
 * Also launch a connection to the first OR in the chosen path, if
 * it's not open already.
Mike Perry's avatar
Mike Perry committed
468
 */
469
origin_circuit_t *
470
circuit_establish_circuit(uint8_t purpose, extend_info_t *exit_ei, int flags)
Mike Perry's avatar
Mike Perry committed
471
{
472
473
  origin_circuit_t *circ;
  int err_reason = 0;
474
475
476
477
478
  int is_hs_v3_rp_circuit = 0;

  if (flags & CIRCLAUNCH_IS_V3_RP) {
    is_hs_v3_rp_circuit = 1;
  }
479

480
  circ = origin_circuit_init(purpose, flags);
Mike Perry's avatar
Mike Perry committed
481

482
  if (onion_pick_cpath_exit(circ, exit_ei, is_hs_v3_rp_circuit) < 0 ||
483
484
485
      onion_populate_cpath(circ) < 0) {
    circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_NOPATH);
    return NULL;
486
487
  }

488
  circuit_event_status(circ, CIRC_EVENT_LAUNCHED, 0);
489
490
491
492
493
494

  if ((err_reason = circuit_handle_first_hop(circ)) < 0) {
    circuit_mark_for_close(TO_CIRCUIT(circ), -err_reason);
    return NULL;
  }
  return circ;
Mike Perry's avatar
Mike Perry committed
495
496
}

497
498
499
500
501
502
503
/** Return the guard state associated with <b>circ</b>, which may be NULL. */
circuit_guard_state_t *
origin_circuit_get_guard_state(origin_circuit_t *circ)
{
  return circ->guard_state;
}

504
505
506
507
508
509
510
511
512
513
514
515
/**
 * Helper function to publish a channel association message
 *
 * circuit_handle_first_hop() calls this to notify subscribers about a
 * channel launch event, which associates a circuit with a channel.
 * This doesn't always correspond to an assignment of the circuit's
 * n_chan field, because that seems to be only for fully-open
 * channels.
 **/
static void
circuit_chan_publish(const origin_circuit_t *circ, const channel_t *chan)
{
516
  ocirc_chan_msg_t *msg = tor_malloc(sizeof(*msg));
517

518
519
520
  msg->gid = circ->global_identifier;
  msg->chan = chan->global_identifier;
  msg->onehop = circ->build_state->onehop_tunnel;
521

522
  ocirc_chan_publish(msg);
523
524
}

525
526
527
528
529
530
/** Start establishing the first hop of our circuit. Figure out what
 * OR we should connect to, and if necessary start the connection to
 * it. If we're already connected, then send the 'create' cell.
 * Return 0 for ok, -reason if circ should be marked-for-close. */
int
circuit_handle_first_hop(origin_circuit_t *circ)
Mike Perry's avatar
Mike Perry committed
531
{
532
533
534
535
536
  crypt_path_t *firsthop;
  channel_t *n_chan;
  int err_reason = 0;
  const char *msg = NULL;
  int should_launch = 0;
537
  const or_options_t *options = get_options();
538

539
  firsthop = cpath_get_next_non_open_hop(circ->cpath);
540
541
  tor_assert(firsthop);
  tor_assert(firsthop->extend_info);
542

543
544
545
546
547
548
  /* Some bridges are on private addresses. Others pass a dummy private
   * address to the pluggable transport, which ignores it.
   * Deny the connection if:
   * - the address is internal, and
   * - we're not connecting to a configured bridge, and
   * - we're not configured to allow extends to private addresses. */
549
  if (tor_addr_is_internal(&firsthop->extend_info->addr, 0) &&
550
551
      !extend_info_is_a_configured_bridge(firsthop->extend_info) &&
      !options->ExtendAllowPrivateAddresses) {
552
553
554
555
556
    log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
           "Client asked me to connect directly to a private address");
    return -END_CIRC_REASON_TORPROTOCOL;
  }

557
558
559
560
  /* now see if we're already connected to the first OR in 'route' */
  log_debug(LD_CIRC,"Looking for firsthop '%s'",
            fmt_addrport(&firsthop->extend_info->addr,
                         firsthop->extend_info->port));
561

562
563
564
565
566
567
568
569
570
571
572
  /* We'll cleanup this code in #33220, when we add an IPv6 address to
   * extend_info_t. */
  const bool addr_is_ipv4 =
    (tor_addr_family(&firsthop->extend_info->addr) == AF_INET);
  n_chan = channel_get_for_extend(
                          firsthop->extend_info->identity_digest,
                          &firsthop->extend_info->ed_identity,
                          addr_is_ipv4 ? &firsthop->extend_info->addr : NULL,
                          addr_is_ipv4 ? NULL : &firsthop->extend_info->addr,
                          &msg,
                          &should_launch);
573

574
575
576
577
578
579
  if (!n_chan) {
    /* not currently connected in a useful way. */
    log_info(LD_CIRC, "Next router is %s: %s",
             safe_str_client(extend_info_describe(firsthop->extend_info)),
             msg?msg:"???");
    circ->base_.n_hop = extend_info_dup(firsthop->extend_info);
580

581
582
583
584
    if (should_launch) {
      n_chan = channel_connect_for_circuit(
          &firsthop->extend_info->addr,
          firsthop->extend_info->port,
585
586
          firsthop->extend_info->identity_digest,
          &firsthop->extend_info->ed_identity);
587
588
589
      if (!n_chan) { /* connect failed, forget the whole thing */
        log_info(LD_CIRC,"connect to firsthop failed. Closing.");
        return -END_CIRC_REASON_CONNECTFAILED;
590
      }
591
      circuit_chan_publish(circ, n_chan);
592
    }
593

594
595
596
597
598
599
600
601
602
    log_debug(LD_CIRC,"connecting in progress (or finished). Good.");
    /* return success. The onion/circuit/etc will be taken care of
     * automatically (may already have been) whenever n_chan reaches
     * OR_CONN_STATE_OPEN.
     */
    return 0;
  } else { /* it's already open. use it. */
    tor_assert(!circ->base_.n_hop);
    circ->base_.n_chan = n_chan;
603
    circuit_chan_publish(circ, n_chan);
604
605
606
    log_debug(LD_CIRC,"Conn open. Delivering first onion skin.");
    if ((err_reason = circuit_send_next_onion_skin(circ)) < 0) {
      log_info(LD_CIRC,"circuit_send_next_onion_skin failed.");
607
      circ->base_.n_chan = NULL;
608
      return err_reason;
609
    }
610
  }
611
  return 0;
612
613
}

614
615
/** Find any circuits that are waiting on <b>or_conn</b> to become
 * open and get them to send their create cells forward.
Mike Perry's avatar
Mike Perry committed
616
 *
617
 * Status is 1 if connect succeeded, or 0 if connect failed.
618
 *
Nick Mathewson's avatar
Nick Mathewson committed
619
620
621
 * Close_origin_circuits is 1 if we should close all the origin circuits
 * through this channel, or 0 otherwise.  (This happens when we want to retry
 * an older guard.)
622
 */
Andrea Shepard's avatar
Andrea Shepard committed
623
void
624
circuit_n_chan_done(channel_t *chan, int status, int close_origin_circuits)
Andrea Shepard's avatar
Andrea Shepard committed
625
{
626
627
  smartlist_t *pending_circs;
  int err_reason = 0;
628

629
  tor_assert(chan);
630

631
  log_debug(LD_CIRC,"chan to %s, status=%d",
632
            channel_get_canonical_remote_descr(chan), status);
633

634
635
  pending_circs = smartlist_new();
  circuit_get_all_pending_on_channel(pending_circs, chan);
636

637
638
639
640
641
642
643
644
  SMARTLIST_FOREACH_BEGIN(pending_circs, circuit_t *, circ)
    {
      /* These checks are redundant wrt get_all_pending_on_or_conn, but I'm
       * leaving them in in case it's possible for the status of a circuit to
       * change as we're going down the list. */
      if (circ->marked_for_close || circ->n_chan || !circ->n_hop ||
          circ->state != CIRCUIT_STATE_CHAN_WAIT)
        continue;
645

646
647
648
649
650
651
652
653
654
655
      const char *rsa_ident = NULL;
      const ed25519_public_key_t *ed_ident = NULL;
      if (! tor_digest_is_zero(circ->n_hop->identity_digest)) {
        rsa_ident = circ->n_hop->identity_digest;
      }
      if (! ed25519_public_key_is_zero(&circ->n_hop->ed_identity)) {
        ed_ident = &circ->n_hop->ed_identity;
      }

      if (rsa_ident == NULL && ed_ident == NULL) {
656
657
658
659
        /* Look at addr/port. This is an unkeyed connection. */
        if (!channel_matches_extend_info(chan, circ->n_hop))
          continue;
      } else {
660
661
        /* We expected a key or keys. See if they matched. */
        if (!channel_remote_identity_matches(chan, rsa_ident, ed_ident))
662
          continue;
663
664
665
666
667
668
669

        /* If the channel is canonical, great.  If not, it needs to match
         * the requested address exactly. */
        if (! chan->is_canonical &&
            ! channel_matches_extend_info(chan, circ->n_hop)) {
          continue;
        }
670
671
672
673
      }
      if (!status) { /* chan failed; close circ */
        log_info(LD_CIRC,"Channel failed; closing circ.");
        circuit_mark_for_close(circ, END_CIRC_REASON_CHANNEL_CLOSED);
674
675
        continue;
      }
676

677
678
679
      if (close_origin_circuits && CIRCUIT_IS_ORIGIN(circ)) {
        log_info(LD_CIRC,"Channel deprecated for origin circs; closing circ.");
        circuit_mark_for_close(circ, END_CIRC_REASON_CHANNEL_CLOSED);
680
681
682
683
684
685
686
687
688
        continue;
      }
      log_debug(LD_CIRC, "Found circ, sending create cell.");
      /* circuit_deliver_create_cell will set n_circ_id and add us to
       * chan_circuid_circuit_map, so we don't need to call
       * set_circid_chan here. */
      circ->n_chan = chan;
      extend_info_free(circ->n_hop);
      circ->n_hop = NULL;
689

690
691
692
693
694
695
696
697
698
699
700
      if (CIRCUIT_IS_ORIGIN(circ)) {
        if ((err_reason =
             circuit_send_next_onion_skin(TO_ORIGIN_CIRCUIT(circ))) < 0) {
          log_info(LD_CIRC,
                   "send_next_onion_skin failed; circuit marked for closing.");
          circuit_mark_for_close(circ, -err_reason);
          continue;
          /* XXX could this be bad, eg if next_onion_skin failed because conn
           *     died? */
        }
      } else {
701
702
        /* pull the create cell out of circ->n_chan_create_cell, and send it */
        tor_assert(circ->n_chan_create_cell);
703
        if (circuit_deliver_create_cell(circ, circ->n_chan_create_cell, 1)<0) {
704
705
706
          circuit_mark_for_close(circ, END_CIRC_REASON_RESOURCELIMIT);
          continue;
        }
707
        tor_free(circ->n_chan_create_cell);
708
709
710
711
        circuit_set_state(circ, CIRCUIT_STATE_OPEN);
      }
    }
  SMARTLIST_FOREACH_END(circ);
712

713
  smartlist_free(pending_circs);
714
715
}

716
717
/** Find a new circid that isn't currently in use on the circ->n_chan
 * for the outgoing
718
719
720
721
 * circuit <b>circ</b>, and deliver the cell <b>create_cell</b> to this
 * circuit.  If <b>relayed</b> is true, this is a create cell somebody
 * gave us via an EXTEND cell, so we shouldn't worry if we don't understand
 * it. Return -1 if we failed to find a suitable circid, else return 0.
722
 */
teor's avatar
teor committed
723
724
725
726
MOCK_IMPL(int,
circuit_deliver_create_cell,(circuit_t *circ,
                             const struct create_cell_t *create_cell,
                             int relayed))
727
{
728
729
  cell_t cell;
  circid_t id;
730
  int r;
731
732
733

  tor_assert(circ);
  tor_assert(circ->n_chan);
734
735
736
737
  tor_assert(create_cell);
  tor_assert(create_cell->cell_type == CELL_CREATE ||
             create_cell->cell_type == CELL_CREATE_FAST ||
             create_cell->cell_type == CELL_CREATE2);
738
739
740

  id = get_unique_circ_id_by_chan(circ->n_chan);
  if (!id) {
741
742
743
    static ratelim_t circid_warning_limit = RATELIM_INIT(9600);
    log_fn_ratelim(&circid_warning_limit, LOG_WARN, LD_CIRC,
                   "failed to get unique circID.");
744
    goto error;
745
  }
746

747
748
  tor_assert_nonfatal_once(circ->n_chan->is_canonical);

749
  memset(&cell, 0, sizeof(cell_t));
750
751
752
  r = relayed ? create_cell_format_relayed(&cell, create_cell)
              : create_cell_format(&cell, create_cell);
  if (r < 0) {
753
    log_warn(LD_CIRC,"Couldn't format create cell");
754
    goto error;
755
  }
756
757
  log_debug(LD_CIRC,"Chosen circID %u.", (unsigned)id);
  circuit_set_n_circid_chan(circ, id, circ->n_chan);
758
  cell.circ_id = circ->n_circ_id;
759

760
761
  append_cell_to_circuit_queue(circ, circ->n_chan, &cell,
                               CELL_DIRECTION_OUT, 0);
762

763
  if (CIRCUIT_IS_ORIGIN(circ)) {
764
765
    /* Update began timestamp for circuits starting their first hop */
    if (TO_ORIGIN_CIRCUIT(circ)->cpath->state == CPATH_STATE_CLOSED) {
766
      if (!CHANNEL_IS_OPEN(circ->n_chan)) {
767
768
769
770
771
772
773
774
775
        log_warn(LD_CIRC,
                 "Got first hop for a circuit without an opened channel. "
                 "State: %s.", channel_state_to_string(circ->n_chan->state));
        tor_fragile_assert();
      }

      tor_gettimeofday(&circ->timestamp_began);
    }

776
777
    /* mark it so it gets better rate limiting treatment. */
    channel_timestamp_client(circ->n_chan);
Mike Perry's avatar
Mike Perry committed
778
779
  }

780
  return 0;
781
782
783
 error:
  circ->n_chan = NULL;
  return -1;
784
785
}

786
787
/** Return true iff we should send a create_fast cell to start building a given
 * circuit */
788
static inline int
789
should_use_create_fast_for_circuit(origin_circuit_t *circ)
790
{
791
792
793
  const or_options_t *options = get_options();
  tor_assert(circ->cpath);
  tor_assert(circ->cpath->extend_info);
794

795
796
797
798
799
  if (!circuit_has_usable_onion_key(circ)) {
    /* We don't have ntor, and we don't have or can't use TAP,
     * so our hand is forced: only a create_fast will work. */
    return 1;
  }
800
  if (public_server_mode(options)) {
801
    /* We're a server, and we have a usable onion key. We can choose.
802
803
804
     * Prefer to blend our circuit into the other circuits we are
     * creating on behalf of others. */
    return 0;
805
  }
806
  return networkstatus_get_param(NULL, "usecreatefast", 0, 0, 1);
807
808
}

809
810
811
812
813
814
815
816
817
818
819
820
/**
 * Return true if <b>circ</b> is the type of circuit we want to count
 * timeouts from.
 *
 * In particular, we want to consider any circuit that plans to build
 * at least 3 hops (but maybe more), but has 3 or fewer hops built
 * so far.
 *
 * We still want to consider circuits before 3 hops, because we need
 * to decide if we should convert them to a measurement circuit in
 * circuit_build_times_handle_completed_hop(), rather than letting
 * slow circuits get killed right away.
821
 */
822
int
823
circuit_timeout_want_to_count_circ(const origin_circuit_t *circ)
824
{
825
  return !circ->has_opened
826
827
          && circ->build_state->desired_path_len >= DEFAULT_ROUTE_LEN
          && circuit_get_cpath_opened_len(circ) <= DEFAULT_ROUTE_LEN;
828
829
}

830
831
/** Decide whether to use a TAP or ntor handshake for connecting to <b>ei</b>
 * directly, and set *<b>cell_type_out</b> and *<b>handshake_type_out</b>
832
 * accordingly.
833
834
 * Note that TAP handshakes in CREATE cells are only used for direct
 * connections:
835
836
 *  - from Single Onions to rend points not in the service's consensus.
 * This is checked in onion_populate_cpath. */
837
838
839
840
841
static void
circuit_pick_create_handshake(uint8_t *cell_type_out,
                              uint16_t *handshake_type_out,
                              const extend_info_t *ei)
{
842
843
  /* torspec says: In general, clients SHOULD use CREATE whenever they are
   * using the TAP handshake, and CREATE2 otherwise. */
844
  if (extend_info_supports_ntor(ei)) {
845
846
    *cell_type_out = CELL_CREATE2;
    *handshake_type_out = ONION_HANDSHAKE_TYPE_NTOR;
teor's avatar
teor committed
847
848
849
850
  } else {
    /* XXXX030 Remove support for deciding to use TAP and EXTEND. */
    *cell_type_out = CELL_CREATE;
    *handshake_type_out = ONION_HANDSHAKE_TYPE_TAP;
851
852
853
  }
}

854
855
856
857
858
/** Decide whether to use a TAP or ntor handshake for extending to <b>ei</b>
 * and set *<b>handshake_type_out</b> accordingly. Decide whether we should
 * use an EXTEND2 or an EXTEND cell to do so, and set *<b>cell_type_out</b>
 * and *<b>create_cell_type_out</b> accordingly.
 * Note that TAP handshakes in EXTEND cells are only used:
859
860
 *  - from clients to intro points, and
 *  - from hidden services to rend points.
861
862
 * This is checked in onion_populate_cpath.
 */
863
864
865
866
867
868
869
870
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)
{
  uint8_t t;
  circuit_pick_create_handshake(&t, handshake_type_out, ei);
871

872
873
874
  /* torspec says: Clients SHOULD use the EXTEND format whenever sending a TAP
   * handshake... In other cases, clients SHOULD use EXTEND2. */
  if (*handshake_type_out != ONION_HANDSHAKE_TYPE_TAP) {
875
876
877
    *cell_type_out = RELAY_COMMAND_EXTEND2;
    *create_cell_type_out = CELL_CREATE2;
  } else {
878
    /* XXXX030 Remove support for deciding to use TAP and EXTEND. */
879
880
881
    *cell_type_out = RELAY_COMMAND_EXTEND;
    *create_cell_type_out = CELL_CREATE;
  }
882
883
}

884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
/**
 * Return true iff <b>purpose</b> is a purpose for a circuit which is
 * allowed to have no guard configured, even if the circuit is multihop
 * and guards are enabled.
 */
static int
circuit_purpose_may_omit_guard(int purpose)
{
  switch (purpose) {
    case CIRCUIT_PURPOSE_TESTING:
    case CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT:
      /* Testing circuits may omit guards because they're measuring
       * liveness or performance, and don't want guards to interfere. */
      return 1;
    default:
      /* All other multihop circuits should use guards if guards are
       * enabled. */
      return 0;
  }
}

905
/** This is the backbone function for building circuits.
Mike Perry's avatar
Mike Perry committed
906
 *
907
908
909
 * If circ's first hop is closed, then we need to build a create
 * cell and send it forward.
 *
910
911
912
913
914
 * Otherwise, if circ's cpath still has any non-open hops, we need to
 * build a relay extend cell and send it forward to the next non-open hop.
 *
 * If all hops on the cpath are open, we're done building the circuit
 * and we should do housekeeping for the newly opened circuit.
915
 *
916
 * Return -reason if we want to tear down circ, else return 0.
Mike Perry's avatar
Mike Perry committed
917
 */
918
919
int
circuit_send_next_onion_skin(origin_circuit_t *circ)
Mike Perry's avatar
Mike Perry committed
920
{
921
  tor_assert(circ);
Mike Perry's avatar
Mike Perry committed
922

923
  if (circ->cpath->state == CPATH_STATE_CLOSED) {
924
    /* Case one: we're on the first hop. */
925
926
    return circuit_send_first_onion_skin(circ);
  }
927
928
929

  tor_assert(circ->cpath->state == CPATH_STATE_OPEN);
  tor_assert(circ->base_.state == CIRCUIT_STATE_BUILDING);
930

931
  crypt_path_t *hop = cpath_get_next_non_open_hop(circ->cpath);
932
  circuit_build_times_handle_completed_hop(circ);
933

934
935
  circpad_machine_event_circ_added_hop(circ);

936
937
938
939
940
941
  if (hop) {
    /* Case two: we're on a hop after the first. */
    return circuit_send_intermediate_onion_skin(circ, hop);
  }

  /* Case three: the circuit is finished. Do housekeeping tasks on it. */
942
  circpad_machine_event_circ_built(circ);
943
  return circuit_build_no_more_hops(circ);
944
945
}

946
947
948
949
950
951
/**
 * Called from circuit_send_next_onion_skin() when we find ourselves connected
 * to the first hop in <b>circ</b>: Send a CREATE or CREATE2 or CREATE_FAST
 * cell to that hop.  Return 0 on success; -reason on failure (if the circuit
 * should be torn down).
 */
952
953
954
static int
circuit_send_first_onion_skin(origin_circuit_t *circ)
{
955
956
  int fast;
  int len;
957
958
  const node_t *node;
  create_cell_t cc;
959
  memset(&cc, 0, sizeof(cc));
960
961
962
963

  log_debug(LD_CIRC,"First skin; sending create cell.");

  if (circ->build_state->onehop_tunnel) {
964
    control_event_bootstrap(BOOTSTRAP_STATUS_ONEHOP_CREATE, 0);
965
  } else {
966
967
968
969
970
971
972
973
974
975
    control_event_bootstrap(BOOTSTRAP_STATUS_CIRCUIT_CREATE, 0);

    /* If this is not a one-hop tunnel, the channel is being used
     * for traffic that wants anonymity and protection from traffic
     * analysis (such as netflow record retention). That means we want
     * to pad it.
     */
    if (circ->base_.n_chan->channel_usage < CHANNEL_USED_FOR_FULL_CIRCS)
      circ->base_.n_chan->channel_usage = CHANNEL_USED_FOR_FULL_CIRCS;
  }
976

977
978
979
  node = node_get_by_id(circ->base_.n_chan->identity_digest);
  fast = should_use_create_fast_for_circuit(circ);
  if (!fast) {
980
    /* We know the right onion key: we should send a create cell. */
981
982
983
    circuit_pick_create_handshake(&cc.cell_type, &cc.handshake_type,
                                  circ->cpath->extend_info);
  } else {
984
    /* We don't know an onion key, so we need to fall back to CREATE_FAST. */
985
986
987
    cc.cell_type = CELL_CREATE_FAST;
    cc.handshake_type = ONION_HANDSHAKE_TYPE_FAST;
  }
Mike Perry's avatar
Mike Perry committed
988

989
990
991
992
993
994
995
996
997
  len = onion_skin_create(cc.handshake_type,
                          circ->cpath->extend_info,
                          &circ->cpath->handshake_state,
                          cc.onionskin);
  if (len < 0) {
    log_warn(LD_CIRC,"onion_skin_create (first hop) failed.");
    return - END_CIRC_REASON_INTERNAL;
  }
  cc.handshake_len = len;
998

999
1000
  if (circuit_deliver_create_cell(TO_CIRCUIT(circ), &cc, 0) < 0)
    return - END_CIRC_REASON_RESOURCELIMIT;
For faster browsing, not all history is shown. View entire blame