circuitbuild.c 104 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.
Nick Mathewson's avatar
Nick Mathewson committed
4
 * Copyright (c) 2007-2019, 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
24
25
 *
 * 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.
 *
 * On the server side, this module also handles the logic of responding to
 * RELAY_EXTEND requests, using circuit_extend().
26
27
 **/

28
29
#define CIRCUITBUILD_PRIVATE

30
#include "core/or/or.h"
31
32
33
34
35
36
37
38
39
#include "app/config/config.h"
#include "app/config/confparse.h"
#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/crypto/relay_crypto.h"
#include "core/mainloop/connection.h"
#include "core/mainloop/mainloop.h"
40
41
42
43
44
45
46
47
#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"
#include "core/or/command.h"
#include "core/or/connection_edge.h"
#include "core/or/connection_or.h"
48
49
50
51
52
53
54
#include "core/or/onion.h"
#include "core/or/policies.h"
#include "core/or/relay.h"
#include "feature/client/bridges.h"
#include "feature/client/circpathbias.h"
#include "feature/client/entrynodes.h"
#include "feature/client/transports.h"
55
#include "feature/control/control.h"
56
#include "feature/dircommon/directory.h"
57
#include "feature/nodelist/describe.h"
58
59
#include "feature/nodelist/microdesc.h"
#include "feature/nodelist/networkstatus.h"
60
#include "feature/nodelist/nickname.h"
61
#include "feature/nodelist/node_select.h"
62
#include "feature/nodelist/nodelist.h"
63
64
#include "feature/nodelist/routerlist.h"
#include "feature/nodelist/routerset.h"
65
66
67
68
#include "feature/relay/router.h"
#include "feature/relay/routermode.h"
#include "feature/relay/selftest.h"
#include "feature/rend/rendcommon.h"
69
#include "feature/stats/predict_ports.h"
70
#include "lib/crypt_ops/crypto_rand.h"
71

72
73
74
75
76
77
78
79
80
81
#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"
82

83
static channel_t * channel_connect_for_circuit(const tor_addr_t *addr,
84
85
86
                                            uint16_t port,
                                            const char *id_digest,
                                            const ed25519_public_key_t *ed_id);
87
static int circuit_deliver_create_cell(circuit_t *circ,
88
89
                                       const create_cell_t *create_cell,
                                       int relayed);
90
static crypt_path_t *onion_next_hop_in_cpath(crypt_path_t *cpath);
Mike Perry's avatar
Mike Perry committed
91
STATIC int onion_append_hop(crypt_path_t **head_ptr, extend_info_t *choice);
92
93
94
95
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);
96
97
98
99
static const node_t *choose_good_middle_server(uint8_t purpose,
                          cpath_build_state_t *state,
                          crypt_path_t *head,
                          int cur_len);
100

101
102
103
104
105
106
/** This function tries to get a channel to the specified endpoint,
 * and then calls command_setup_channel() to give it the right
 * callbacks.
 */
static channel_t *
channel_connect_for_circuit(const tor_addr_t *addr, uint16_t port,
107
108
                            const char *id_digest,
                            const ed25519_public_key_t *ed_id)
109
110
111
{
  channel_t *chan;

112
  chan = channel_connect(addr, port, id_digest, ed_id);
113
114
115
116
117
  if (chan) command_setup_channel(chan);

  return chan;
}

118
119
120
/** 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
121
 *
122
 * Return it, or 0 if can't get a unique circ_id.
Mike Perry's avatar
Mike Perry committed
123
 */
124
STATIC circid_t
125
get_unique_circ_id_by_chan(channel_t *chan)
126
{
127
128
129
130
131
132
/* 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. */
133
#define MAX_CIRCID_ATTEMPTS 64
134
  int in_use;
Nick Mathewson's avatar
Nick Mathewson committed
135
  unsigned n_with_circ = 0, n_pending_destroy = 0, n_weird_pending_destroy = 0;
136
137
  circid_t test_circ_id;
  circid_t attempts=0;
138
  circid_t high_bit, max_range, mask;
Nick Mathewson's avatar
Nick Mathewson committed
139
140
  int64_t pending_destroy_time_total = 0;
  int64_t pending_destroy_time_max = 0;
141
142
143
144
145
146
147

  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.");
148
    return 0;
149
  }
150
151
  max_range = (chan->wide_circ_ids) ? (1u<<31) : (1u<<15);
  mask = max_range - 1;
152
  high_bit = (chan->circ_id_type == CIRC_ID_TYPE_HIGHER) ? max_range : 0;
153
  do {
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
    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.
170
       */
Nick Mathewson's avatar
Nick Mathewson committed
171
172
173
174
175
176
177
178
      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 "
179
                 "circID support, with %u inbound and %u outbound circuits. "
180
                 "Found %u circuit IDs in use by circuits, and %u with "
Nick Mathewson's avatar
Nick Mathewson committed
181
182
183
184
185
                 "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",
186
                 chan->wide_circ_ids ? "with" : "without",
187
                 chan->num_p_circuits, chan->num_n_circuits,
Nick Mathewson's avatar
Nick Mathewson committed
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
                 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, "
209
               "of which %u are active. It says it has %"PRId64
Nick Mathewson's avatar
Nick Mathewson committed
210
211
212
               " destroy cells queued.",
               circuitmux_num_circuits(chan->cmux),
               circuitmux_num_active_circuits(chan->cmux),
213
               (queued_destroys));
Nick Mathewson's avatar
Nick Mathewson committed
214
215
216
217
218
219
220
221

      /* 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);

222
223
      channel_dump_statistics(chan, LOG_WARN);

Mike Perry's avatar
Mike Perry committed
224
225
      return 0;
    }
226

227
228
229
230
231
    do {
      crypto_rand((char*) &test_circ_id, sizeof(test_circ_id));
      test_circ_id &= mask;
    } while (test_circ_id == 0);

232
    test_circ_id |= high_bit;
233
234
235
236

    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
237
238
    else if (in_use == 2) {
      time_t since_when;
239
      ++n_pending_destroy;
Nick Mathewson's avatar
Nick Mathewson committed
240
241
242
243
244
245
246
247
248
249
250
      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;
      }
    }
251
  } while (in_use);
252
  return test_circ_id;
253
254
}

255
256
257
/** 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.
258
259
 * 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
260
 */
261
262
static char *
circuit_list_path_impl(origin_circuit_t *circ, int verbose, int verbose_names)
Mike Perry's avatar
Mike Perry committed
263
{
264
265
266
267
  crypt_path_t *hop;
  smartlist_t *elements;
  const char *states[] = {"closed", "waiting for keys", "open"};
  char *s;
268

269
  elements = smartlist_new();
Mike Perry's avatar
Mike Perry committed
270

271
272
273
274
275
276
277
278
279
  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*"));
280
281
  }

282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
  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 */
309
310
311
      elt = tor_malloc(HEX_DIGEST_LEN+2);
      elt[0] = '$';
      base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN);
312
313
314
315
316
317
318
319
320
321
322
    }
    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);
323

324
325
326
327
  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
328
329
}

330
331
332
333
334
335
336
/** 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)
337
{
338
  return circuit_list_path_impl(circ, verbose, 0);
339
340
}

341
342
/** 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
343
 */
344
345
char *
circuit_list_path_for_controller(origin_circuit_t *circ)
Mike Perry's avatar
Mike Perry committed
346
{
347
  return circuit_list_path_impl(circ, 0, 1);
Mike Perry's avatar
Mike Perry committed
348
349
}

350
351
352
353
354
355
/** 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)
356
{
357
358
359
  char *s = circuit_list_path(circ,1);
  tor_log(severity,domain,"%s",s);
  tor_free(s);
360
361
}

362
/** Return 1 iff every node in circ's cpath definitely supports ntor. */
363
364
365
static int
circuit_cpath_supports_ntor(const origin_circuit_t *circ)
{
366
  crypt_path_t *head, *cpath;
367

368
  cpath = head = circ->cpath;
369
  do {
370
371
372
373
    /* if the extend_info is missing, we can't tell if it supports ntor */
    if (!cpath->extend_info) {
      return 0;
    }
374

375
376
377
378
    /* if the key is blank, it definitely doesn't support ntor */
    if (!extend_info_supports_ntor(cpath->extend_info)) {
      return 0;
    }
379
380
381
    cpath = cpath->next;
  } while (cpath != head);

382
  return 1;
383
384
}

385
386
387
388
/** 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
389
{
390
  int r = 0;
391

392
393
394
  /* onion_extend_cpath assumes these are non-NULL */
  tor_assert(circ);
  tor_assert(circ->build_state);
395

396
397
  while (r == 0) {
    r = onion_extend_cpath(circ);
398
399
400
401
    if (r < 0) {
      log_info(LD_CIRC,"Generating cpath hop failed.");
      return -1;
    }
402
  }
403

404
405
  /* The path is complete */
  tor_assert(r == 1);
406

407
408
409
410
411
412
413
  /* 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
414
415
416
417
    /* 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. */
418
419
    return 0;
  }
420

421
422
423
424
425
426
427
428
429
430
431
  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.
     */
432
    if (!node || !node_has_preferred_descriptor(node, 1)) {
433
      return 0;
434
    }
435
  }
436

437
438
439
440
441
442
443
444
  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
445
446
}

447
448
449
450
451
/** 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
452
{
453
454
455
456
457
458
459
460
461
462
463
464
465
466
  /* 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
467
468
}

469
470
471
/** 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
472
 *
473
474
 * 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
475
 */
476
origin_circuit_t *
477
circuit_establish_circuit(uint8_t purpose, extend_info_t *exit_ei, int flags)
Mike Perry's avatar
Mike Perry committed
478
{
479
480
  origin_circuit_t *circ;
  int err_reason = 0;
481
482
483
484
485
  int is_hs_v3_rp_circuit = 0;

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

487
  circ = origin_circuit_init(purpose, flags);
Mike Perry's avatar
Mike Perry committed
488

489
  if (onion_pick_cpath_exit(circ, exit_ei, is_hs_v3_rp_circuit) < 0 ||
490
491
492
      onion_populate_cpath(circ) < 0) {
    circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_NOPATH);
    return NULL;
493
494
  }

495
496
497
498
499
500
501
  control_event_circuit_status(circ, CIRC_EVENT_LAUNCHED, 0);

  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
502
503
}

504
505
506
507
508
509
510
/** 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;
}

511
512
513
514
515
516
/** 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
517
{
518
519
520
521
522
  crypt_path_t *firsthop;
  channel_t *n_chan;
  int err_reason = 0;
  const char *msg = NULL;
  int should_launch = 0;
523
  const or_options_t *options = get_options();
524

525
526
527
  firsthop = onion_next_hop_in_cpath(circ->cpath);
  tor_assert(firsthop);
  tor_assert(firsthop->extend_info);
528

529
530
531
532
533
534
  /* 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. */
535
  if (tor_addr_is_internal(&firsthop->extend_info->addr, 0) &&
536
537
      !extend_info_is_a_configured_bridge(firsthop->extend_info) &&
      !options->ExtendAllowPrivateAddresses) {
538
539
540
541
542
    log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
           "Client asked me to connect directly to a private address");
    return -END_CIRC_REASON_TORPROTOCOL;
  }

543
544
545
546
  /* 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));
547

548
  n_chan = channel_get_for_extend(firsthop->extend_info->identity_digest,
549
                                  &firsthop->extend_info->ed_identity,
550
551
552
                                  &firsthop->extend_info->addr,
                                  &msg,
                                  &should_launch);
553

554
555
556
557
558
559
  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);
560

561
562
563
564
565
566
    if (should_launch) {
      if (circ->build_state->onehop_tunnel)
        control_event_bootstrap(BOOTSTRAP_STATUS_CONN_DIR, 0);
      n_chan = channel_connect_for_circuit(
          &firsthop->extend_info->addr,
          firsthop->extend_info->port,
567
568
          firsthop->extend_info->identity_digest,
          &firsthop->extend_info->ed_identity);
569
570
571
      if (!n_chan) { /* connect failed, forget the whole thing */
        log_info(LD_CIRC,"connect to firsthop failed. Closing.");
        return -END_CIRC_REASON_CONNECTFAILED;
572
573
      }
    }
574

575
576
577
578
579
580
581
582
583
584
585
586
    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;
    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.");
587
      circ->base_.n_chan = NULL;
588
      return err_reason;
589
    }
590
  }
591
  return 0;
592
593
}

594
595
/** 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
596
 *
597
 * Status is 1 if connect succeeded, or 0 if connect failed.
598
 *
Nick Mathewson's avatar
Nick Mathewson committed
599
600
601
 * 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.)
602
 */
Andrea Shepard's avatar
Andrea Shepard committed
603
void
604
circuit_n_chan_done(channel_t *chan, int status, int close_origin_circuits)
Andrea Shepard's avatar
Andrea Shepard committed
605
{
606
607
  smartlist_t *pending_circs;
  int err_reason = 0;
608

609
  tor_assert(chan);
610

611
  log_debug(LD_CIRC,"chan to %s, status=%d",
612
            channel_get_canonical_remote_descr(chan), status);
613

614
615
  pending_circs = smartlist_new();
  circuit_get_all_pending_on_channel(pending_circs, chan);
616

617
618
619
620
621
622
623
624
  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;
625

626
627
628
629
630
631
632
633
634
635
636
637
638
      if (tor_digest_is_zero(circ->n_hop->identity_digest)) {
        /* Look at addr/port. This is an unkeyed connection. */
        if (!channel_matches_extend_info(chan, circ->n_hop))
          continue;
      } else {
        /* We expected a key. See if it's the right one. */
        if (tor_memneq(chan->identity_digest,
                   circ->n_hop->identity_digest, DIGEST_LEN))
          continue;
      }
      if (!status) { /* chan failed; close circ */
        log_info(LD_CIRC,"Channel failed; closing circ.");
        circuit_mark_for_close(circ, END_CIRC_REASON_CHANNEL_CLOSED);
639
640
641
642
643
        continue;
      }
      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);
644
645
646
647
648
649
650
651
652
        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;
653

654
655
656
657
658
659
660
661
662
663
664
      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 {
665
666
        /* pull the create cell out of circ->n_chan_create_cell, and send it */
        tor_assert(circ->n_chan_create_cell);
667
        if (circuit_deliver_create_cell(circ, circ->n_chan_create_cell, 1)<0) {
668
669
670
          circuit_mark_for_close(circ, END_CIRC_REASON_RESOURCELIMIT);
          continue;
        }
671
        tor_free(circ->n_chan_create_cell);
672
673
674
675
        circuit_set_state(circ, CIRCUIT_STATE_OPEN);
      }
    }
  SMARTLIST_FOREACH_END(circ);
676

677
  smartlist_free(pending_circs);
678
679
}

680
681
/** Find a new circid that isn't currently in use on the circ->n_chan
 * for the outgoing
682
683
684
685
 * 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.
686
 */
687
static int
688
689
circuit_deliver_create_cell(circuit_t *circ, const create_cell_t *create_cell,
                            int relayed)
690
{
691
692
  cell_t cell;
  circid_t id;
693
  int r;
694
695
696

  tor_assert(circ);
  tor_assert(circ->n_chan);
697
698
699
700
  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);
701
702
703

  id = get_unique_circ_id_by_chan(circ->n_chan);
  if (!id) {
704
705
706
    static ratelim_t circid_warning_limit = RATELIM_INIT(9600);
    log_fn_ratelim(&circid_warning_limit, LOG_WARN, LD_CIRC,
                   "failed to get unique circID.");
707
    goto error;
708
  }
709

710
  memset(&cell, 0, sizeof(cell_t));
711
712
713
  r = relayed ? create_cell_format_relayed(&cell, create_cell)
              : create_cell_format(&cell, create_cell);
  if (r < 0) {
714
    log_warn(LD_CIRC,"Couldn't format create cell");
715
    goto error;
716
  }
717
718
  log_debug(LD_CIRC,"Chosen circID %u.", (unsigned)id);
  circuit_set_n_circid_chan(circ, id, circ->n_chan);
719
  cell.circ_id = circ->n_circ_id;
720

721
722
  append_cell_to_circuit_queue(circ, circ->n_chan, &cell,
                               CELL_DIRECTION_OUT, 0);
723

724
  if (CIRCUIT_IS_ORIGIN(circ)) {
725
726
    /* Update began timestamp for circuits starting their first hop */
    if (TO_ORIGIN_CIRCUIT(circ)->cpath->state == CPATH_STATE_CLOSED) {
727
      if (!CHANNEL_IS_OPEN(circ->n_chan)) {
728
729
730
731
732
733
734
735
736
        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);
    }

737
738
    /* mark it so it gets better rate limiting treatment. */
    channel_timestamp_client(circ->n_chan);
Mike Perry's avatar
Mike Perry committed
739
740
  }

741
  return 0;
742
743
744
 error:
  circ->n_chan = NULL;
  return -1;
745
746
}

747
748
749
750
751
/** We've decided to start our reachability testing. If all
 * is set, log this to the user. Return 1 if we did, or 0 if
 * we chose not to log anything. */
int
inform_testing_reachability(void)
752
{
753
  char dirbuf[128];
754
  char *address;
755
756
757
  const routerinfo_t *me = router_get_my_routerinfo();
  if (!me)
    return 0;
758
  address = tor_dup_ip(me->addr);
759
760
  control_event_server_status(LOG_NOTICE,
                              "CHECKING_REACHABILITY ORADDRESS=%s:%d",
761
                              address, me->or_port);
762
763
  if (me->dir_port) {
    tor_snprintf(dirbuf, sizeof(dirbuf), " and DirPort %s:%d",
764
                 address, me->dir_port);
765
766
    control_event_server_status(LOG_NOTICE,
                                "CHECKING_REACHABILITY DIRADDRESS=%s:%d",
767
                                address, me->dir_port);
768
  }
769
770
771
  log_notice(LD_OR, "Now checking whether ORPort %s:%d%s %s reachable... "
                         "(this may take up to %d minutes -- look for log "
                         "messages indicating success)",
772
      address, me->or_port,
773
774
775
      me->dir_port ? dirbuf : "",
      me->dir_port ? "are" : "is",
      TIMEOUT_UNTIL_UNREACHABILITY_COMPLAINT/60);
776

777
  tor_free(address);
778
  return 1;
779
780
}

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

790
791
792
793
794
  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;
  }
795
  if (public_server_mode(options)) {
796
    /* We're a server, and we have a usable onion key. We can choose.
797
798
799
     * Prefer to blend our circuit into the other circuits we are
     * creating on behalf of others. */
    return 0;
800
  }
801
  return networkstatus_get_param(NULL, "usecreatefast", 0, 0, 1);
802
803
}

804
805
806
807
808
809
810
811
812
813
814
815
/**
 * 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.
816
 */
817
int
818
circuit_timeout_want_to_count_circ(const origin_circuit_t *circ)
819
{
820
  return !circ->has_opened
821
822
          && circ->build_state->desired_path_len >= DEFAULT_ROUTE_LEN
          && circuit_get_cpath_opened_len(circ) <= DEFAULT_ROUTE_LEN;
823
824
}

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

849
850
851
852
853
/** 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:
854
855
 *  - from clients to intro points, and
 *  - from hidden services to rend points.
856
857
 * This is checked in onion_populate_cpath.
 */
858
859
860
861
862
863
864
865
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);
866

867
868
869
  /* 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) {
870
871
872
    *cell_type_out = RELAY_COMMAND_EXTEND2;
    *create_cell_type_out = CELL_CREATE2;
  } else {
873
    /* XXXX030 Remove support for deciding to use TAP and EXTEND. */
874
875
876
    *cell_type_out = RELAY_COMMAND_EXTEND;
    *create_cell_type_out = CELL_CREATE;
  }
877
878
}

879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
/**
 * 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;
  }
}

900
/** This is the backbone function for building circuits.
Mike Perry's avatar
Mike Perry committed
901
 *
902
903
904
 * If circ's first hop is closed, then we need to build a create
 * cell and send it forward.
 *
905
906
907
908
909
 * 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.
910
 *
911
 * Return -reason if we want to tear down circ, else return 0.
Mike Perry's avatar
Mike Perry committed
912
 */
913
914
int
circuit_send_next_onion_skin(origin_circuit_t *circ)
Mike Perry's avatar
Mike Perry committed
915
{
916
  tor_assert(circ);
Mike Perry's avatar
Mike Perry committed
917

918
  if (circ->cpath->state == CPATH_STATE_CLOSED) {
919
    /* Case one: we're on the first hop. */
920
921
    return circuit_send_first_onion_skin(circ);
  }
922
923
924

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

926
  crypt_path_t *hop = onion_next_hop_in_cpath(circ->cpath);
927
  circuit_build_times_handle_completed_hop(circ);
928
929
930
931
932
933
934
935

  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. */
  return circuit_build_no_more_hops(circ);
936
937
}

938
939
940
941
942
943
/**
 * 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).
 */
944
945
946
static int
circuit_send_first_onion_skin(origin_circuit_t *circ)
{
947
948
  int fast;
  int len;
949
950
  const node_t *node;
  create_cell_t cc;
951
  memset(&cc, 0, sizeof(cc));
952
953
954
955

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

  if (circ->build_state->onehop_tunnel) {
956
    control_event_bootstrap(BOOTSTRAP_STATUS_ONEHOP_CREATE, 0);
957
  } else {
958
959
960
961
962
963
964
965
966
967
    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;
  }
968

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

981
982
983
984
985
986
987
988
989
  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;
990

991
992
  if (circuit_deliver_create_cell(TO_CIRCUIT(circ), &cc, 0) < 0)
    return - END_CIRC_REASON_RESOURCELIMIT;
Mike Perry's avatar
Mike Perry committed
993

994
995
996
997
998
999
  circ->cpath->state = CPATH_STATE_AWAITING_KEYS;
  circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_BUILDING);
  log_info(LD_CIRC,"First hop: finished sending %s cell to '%s'",
           fast ? "CREATE_FAST" : "CREATE",
           node ? node_describe(node) : "<unnamed>");
  return 0;
1000
}
For faster browsing, not all history is shown. View entire blame