circuitbuild.c 119 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-2013, The Tor Project, Inc. */
5
6
7
8
9
10
11
/* See LICENSE for licensing information */

/**
 * \file circuitbuild.c
 * \brief The actual details of building circuits.
 **/

Mike Perry's avatar
Mike Perry committed
12
#include "or.h"
13
#include "channel.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
14
#include "circuitbuild.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
15
#include "circuitlist.h"
16
#include "circuitstats.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
17
#include "circuituse.h"
18
#include "command.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
19
#include "config.h"
20
#include "confparse.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
21
#include "connection.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
22
#include "connection_edge.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
23
#include "connection_or.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
24
#include "control.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
25
#include "directory.h"
26
#include "entrynodes.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
27
#include "main.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
28
#include "networkstatus.h"
29
#include "nodelist.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
30
#include "onion.h"
31
32
#include "onion_tap.h"
#include "onion_fast.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
33
#include "policies.h"
34
#include "transports.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
35
#include "relay.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
36
#include "rephist.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
37
#include "router.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
38
#include "routerlist.h"
Sebastian Hahn's avatar
Sebastian Hahn committed
39
#include "routerparse.h"
40
#include "routerset.h"
Mike Perry's avatar
Mike Perry committed
41
#include "crypto.h"
42
#include "connection_edge.h"
43

Roger Dingledine's avatar
Roger Dingledine committed
44
45
46
47
#ifndef MIN
#define MIN(a,b) ((a)<(b)?(a):(b))
#endif

48
49
50
51
52
53
54
/********* START VARIABLES **********/

/** A global list of all circuits at this hop. */
extern circuit_t *global_circuitlist;

/********* END VARIABLES ************/

55
56
57
static channel_t * channel_connect_for_circuit(const tor_addr_t *addr,
                                               uint16_t port,
                                               const char *id_digest);
58
static int circuit_deliver_create_cell(circuit_t *circ,
59
60
                                       const create_cell_t *create_cell,
                                       int relayed);
61
static int onion_pick_cpath_exit(origin_circuit_t *circ, extend_info_t *exit);
62
static crypt_path_t *onion_next_hop_in_cpath(crypt_path_t *cpath);
Roger Dingledine's avatar
Roger Dingledine committed
63
static int onion_extend_cpath(origin_circuit_t *circ);
64
static int count_acceptable_nodes(smartlist_t *routers);
65
static int onion_append_hop(crypt_path_t **head_ptr, extend_info_t *choice);
Mike Perry's avatar
Mike Perry committed
66
static int entry_guard_inc_circ_attempt_count(entry_guard_t *guard);
67
68
69
static void pathbias_count_build_success(origin_circuit_t *circ);
static void pathbias_count_successful_close(origin_circuit_t *circ);
static void pathbias_count_collapse(origin_circuit_t *circ);
70
71
72
static void pathbias_count_use_failed(origin_circuit_t *circ);
static int pathbias_check_use_rate(entry_guard_t *guard);
static int pathbias_check_close_rate(entry_guard_t *guard);
73

74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
/** 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,
                            const char *id_digest)
{
  channel_t *chan;

  chan = channel_connect(addr, port, id_digest);
  if (chan) command_setup_channel(chan);

  return chan;
}

90
91
92
/** Iterate over values of circ_id, starting from conn-\>next_circ_id,
 * and with the high bit specified by conn-\>circ_id_type, 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
93
 *
94
 * Return it, or 0 if can't get a unique circ_id.
Mike Perry's avatar
Mike Perry committed
95
 */
96
97
static circid_t
get_unique_circ_id_by_chan(channel_t *chan)
98
{
99
100
101
102
103
104
105
106
107
108
  circid_t test_circ_id;
  circid_t attempts=0;
  circid_t high_bit;

  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.");
109
    return 0;
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
  }
  high_bit =
    (chan->circ_id_type == CIRC_ID_TYPE_HIGHER) ? 1<<15 : 0;
  do {
    /* Sequentially iterate over test_circ_id=1...1<<15-1 until we find a
     * circID such that (high_bit|test_circ_id) is not already used. */
    test_circ_id = chan->next_circ_id++;
    if (test_circ_id == 0 || test_circ_id >= 1<<15) {
      test_circ_id = 1;
      chan->next_circ_id = 2;
    }
    if (++attempts > 1<<15) {
      /* Make sure we don't loop forever if all circ_id's are used. This
       * matters because it's an external DoS opportunity.
       */
      log_warn(LD_CIRC,"No unused circ IDs. Failing.");
Mike Perry's avatar
Mike Perry committed
126
127
      return 0;
    }
128
129
130
    test_circ_id |= high_bit;
  } while (circuit_id_in_use_on_channel(test_circ_id, chan));
  return test_circ_id;
131
132
}

133
134
135
136
137
138
/** 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.
 * If <b>verbose_names</b> is false, give nicknames for Named routers and hex
 * digests for others; if <b>verbose_names</b> is true, use $DIGEST=Name style
 * names.
Mike Perry's avatar
Mike Perry committed
139
 */
140
141
static char *
circuit_list_path_impl(origin_circuit_t *circ, int verbose, int verbose_names)
Mike Perry's avatar
Mike Perry committed
142
{
143
144
145
146
  crypt_path_t *hop;
  smartlist_t *elements;
  const char *states[] = {"closed", "waiting for keys", "open"};
  char *s;
147

148
  elements = smartlist_new();
Mike Perry's avatar
Mike Perry committed
149

150
151
152
153
154
155
156
157
158
  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*"));
159
160
  }

161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
  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 */
      node = node_get_by_id(id);
      if (node && node_is_named(node)) {
        elt = tor_strdup(node_get_nickname(node));
      } else {
        elt = tor_malloc(HEX_DIGEST_LEN+2);
        elt[0] = '$';
        base16_encode(elt+1, HEX_DIGEST_LEN+1, id, DIGEST_LEN);
      }
    }
    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);
207

208
209
210
211
  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
212
213
}

214
215
216
217
218
219
220
/** 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)
221
{
222
  return circuit_list_path_impl(circ, verbose, 0);
223
224
}

225
226
/** 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
227
 */
228
229
char *
circuit_list_path_for_controller(origin_circuit_t *circ)
Mike Perry's avatar
Mike Perry committed
230
{
231
  return circuit_list_path_impl(circ, 0, 1);
Mike Perry's avatar
Mike Perry committed
232
233
}

234
235
236
237
238
239
/** 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)
240
{
241
242
243
  char *s = circuit_list_path(circ,1);
  tor_log(severity,domain,"%s",s);
  tor_free(s);
244
245
}

246
247
248
249
/** Tell the rep(utation)hist(ory) module about the status of the links
 * in <b>circ</b>.  Hops that have become OPEN are marked as successfully
 * extended; the _first_ hop that isn't open (if any) is marked as
 * unable to extend.
Mike Perry's avatar
Mike Perry committed
250
 */
251
252
253
/* XXXX Someday we should learn from OR circuits too. */
void
circuit_rep_hist_note_result(origin_circuit_t *circ)
254
{
255
256
257
258
259
260
261
262
263
264
  crypt_path_t *hop;
  const char *prev_digest = NULL;
  hop = circ->cpath;
  if (!hop) /* circuit hasn't started building yet. */
    return;
  if (server_mode(get_options())) {
    const routerinfo_t *me = router_get_my_routerinfo();
    if (!me)
      return;
    prev_digest = me->cache_info.identity_digest;
265
  }
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
  do {
    const node_t *node = node_get_by_id(hop->extend_info->identity_digest);
    if (node) { /* Why do we check this?  We know the identity. -NM XXXX */
      if (prev_digest) {
        if (hop->state == CPATH_STATE_OPEN)
          rep_hist_note_extend_succeeded(prev_digest, node->identity);
        else {
          rep_hist_note_extend_failed(prev_digest, node->identity);
          break;
        }
      }
      prev_digest = node->identity;
    } else {
      prev_digest = NULL;
    }
    hop=hop->next;
  } while (hop!=circ->cpath);
283
284
}

285
286
287
288
/** 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
289
{
290
291
292
293
294
295
  int r;
 again:
  r = onion_extend_cpath(circ);
  if (r < 0) {
    log_info(LD_CIRC,"Generating cpath hop failed.");
    return -1;
296
  }
297
298
299
  if (r == 0)
    goto again;
  return 0; /* if r == 1 */
Mike Perry's avatar
Mike Perry committed
300
301
}

302
303
304
305
306
/** 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
307
{
308
309
310
311
312
313
314
315
316
317
318
319
320
321
  /* 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
322
323
}

324
325
326
/** 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
327
 *
328
329
 * 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
330
 */
331
332
origin_circuit_t *
circuit_establish_circuit(uint8_t purpose, extend_info_t *exit, int flags)
Mike Perry's avatar
Mike Perry committed
333
{
334
335
  origin_circuit_t *circ;
  int err_reason = 0;
336

337
  circ = origin_circuit_init(purpose, flags);
Mike Perry's avatar
Mike Perry committed
338

339
340
341
342
  if (onion_pick_cpath_exit(circ, exit) < 0 ||
      onion_populate_cpath(circ) < 0) {
    circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_NOPATH);
    return NULL;
343
344
  }

345
346
347
348
349
350
351
  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
352
353
}

354
355
356
357
358
359
/** 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
360
{
361
362
363
364
365
  crypt_path_t *firsthop;
  channel_t *n_chan;
  int err_reason = 0;
  const char *msg = NULL;
  int should_launch = 0;
366

367
368
369
  firsthop = onion_next_hop_in_cpath(circ->cpath);
  tor_assert(firsthop);
  tor_assert(firsthop->extend_info);
370

371
372
373
374
  /* 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));
375

376
377
378
379
  n_chan = channel_get_for_extend(firsthop->extend_info->identity_digest,
                                  &firsthop->extend_info->addr,
                                  &msg,
                                  &should_launch);
380

381
382
383
384
385
386
  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);
387

388
389
390
391
392
393
394
395
396
397
    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,
          firsthop->extend_info->identity_digest);
      if (!n_chan) { /* connect failed, forget the whole thing */
        log_info(LD_CIRC,"connect to firsthop failed. Closing.");
        return -END_CIRC_REASON_CONNECTFAILED;
398
399
      }
    }
400

401
402
403
404
405
406
407
408
409
410
411
412
413
    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.");
      return err_reason;
414
    }
415
  }
416
  return 0;
417
418
}

419
420
/** 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
421
 *
422
 * Status is 1 if connect succeeded, or 0 if connect failed.
423
 */
Andrea Shepard's avatar
Andrea Shepard committed
424
void
425
circuit_n_chan_done(channel_t *chan, int status)
Andrea Shepard's avatar
Andrea Shepard committed
426
{
427
428
  smartlist_t *pending_circs;
  int err_reason = 0;
429

430
  tor_assert(chan);
431

432
433
434
  log_debug(LD_CIRC,"chan to %s/%s, status=%d",
            chan->nickname ? chan->nickname : "NULL",
            channel_get_canonical_remote_descr(chan), status);
435

436
437
  pending_circs = smartlist_new();
  circuit_get_all_pending_on_channel(pending_circs, chan);
438

439
440
441
442
443
444
445
446
  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;
447

448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
      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);
        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;
470

471
472
473
474
475
476
477
478
479
480
481
      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 {
482
483
        /* pull the create cell out of circ->n_chan_create_cell, and send it */
        tor_assert(circ->n_chan_create_cell);
484
        if (circuit_deliver_create_cell(circ, circ->n_chan_create_cell, 1)<0) {
485
486
487
          circuit_mark_for_close(circ, END_CIRC_REASON_RESOURCELIMIT);
          continue;
        }
488
        tor_free(circ->n_chan_create_cell);
489
490
491
492
        circuit_set_state(circ, CIRCUIT_STATE_OPEN);
      }
    }
  SMARTLIST_FOREACH_END(circ);
493

494
  smartlist_free(pending_circs);
495
496
}

497
498
/** Find a new circid that isn't currently in use on the circ->n_chan
 * for the outgoing
499
500
501
502
 * 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.
503
 */
504
static int
505
506
circuit_deliver_create_cell(circuit_t *circ, const create_cell_t *create_cell,
                            int relayed)
507
{
508
509
  cell_t cell;
  circid_t id;
510
  int r;
511
512
513

  tor_assert(circ);
  tor_assert(circ->n_chan);
514
515
516
517
  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);
518
519
520
521

  id = get_unique_circ_id_by_chan(circ->n_chan);
  if (!id) {
    log_warn(LD_CIRC,"failed to get unique circID.");
522
    return -1;
523
  }
524
525
  log_debug(LD_CIRC,"Chosen circID %u.", id);
  circuit_set_n_circid_chan(circ, id, circ->n_chan);
526

527
  memset(&cell, 0, sizeof(cell_t));
528
529
530
  r = relayed ? create_cell_format_relayed(&cell, create_cell)
              : create_cell_format(&cell, create_cell);
  if (r < 0) {
531
532
533
    log_warn(LD_CIRC,"Couldn't format create cell");
    return -1;
  }
534
  cell.circ_id = circ->n_circ_id;
535

536
537
  append_cell_to_circuit_queue(circ, circ->n_chan, &cell,
                               CELL_DIRECTION_OUT, 0);
538

539
  if (CIRCUIT_IS_ORIGIN(circ)) {
540
541
542
543
544
545
546
547
548
549
550
551
    /* Update began timestamp for circuits starting their first hop */
    if (TO_ORIGIN_CIRCUIT(circ)->cpath->state == CPATH_STATE_CLOSED) {
      if (circ->n_chan->state != CHANNEL_STATE_OPEN) {
        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);
    }

552
553
    /* mark it so it gets better rate limiting treatment. */
    channel_timestamp_client(circ->n_chan);
Mike Perry's avatar
Mike Perry committed
554
555
  }

556
557
558
  return 0;
}

559
560
561
562
563
/** 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)
564
{
565
566
567
568
569
570
571
572
573
574
575
576
577
  char dirbuf[128];
  const routerinfo_t *me = router_get_my_routerinfo();
  if (!me)
    return 0;
  control_event_server_status(LOG_NOTICE,
                              "CHECKING_REACHABILITY ORADDRESS=%s:%d",
                              me->address, me->or_port);
  if (me->dir_port) {
    tor_snprintf(dirbuf, sizeof(dirbuf), " and DirPort %s:%d",
                 me->address, me->dir_port);
    control_event_server_status(LOG_NOTICE,
                                "CHECKING_REACHABILITY DIRADDRESS=%s:%d",
                                me->address, me->dir_port);
578
  }
579
580
581
582
583
584
585
  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)",
      me->address, me->or_port,
      me->dir_port ? dirbuf : "",
      me->dir_port ? "are" : "is",
      TIMEOUT_UNTIL_UNREACHABILITY_COMPLAINT/60);
586

587
  return 1;
588
589
}

590
591
592
593
/** Return true iff we should send a create_fast cell to start building a given
 * circuit */
static INLINE int
should_use_create_fast_for_circuit(origin_circuit_t *circ)
594
{
595
596
597
  const or_options_t *options = get_options();
  tor_assert(circ->cpath);
  tor_assert(circ->cpath->extend_info);
598

599
600
601
602
603
604
605
606
607
  if (!circ->cpath->extend_info->onion_key)
    return 1; /* our hand is forced: only a create_fast will work. */
  if (!options->FastFirstHopPK)
    return 0; /* we prefer to avoid create_fast */
  if (public_server_mode(options)) {
    /* We're a server, and we know an onion key. We can choose.
     * Prefer to blend our circuit into the other circuits we are
     * creating on behalf of others. */
    return 0;
608
609
  }

610
  return 1;
611
612
}

613
614
615
616
/** Return true if <b>circ</b> is the type of circuit we want to count
 * timeouts from. In particular, we want it to have not completed yet
 * (already completing indicates we cannibalized it), and we want it to
 * have exactly three hops.
617
 */
618
619
int
circuit_timeout_want_to_count_circ(origin_circuit_t *circ)
620
{
621
622
  return !circ->has_opened
          && circ->build_state->desired_path_len == DEFAULT_ROUTE_LEN;
623
624
}

625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
#ifdef CURVE25519_ENABLED
/** Return true if the ntor handshake is enabled in the configuration, or if
 * it's been set to "auto" in the configuration and it's enabled in the
 * consensus. */
static int
circuits_can_use_ntor(void)
{
  const or_options_t *options = get_options();
  if (options->UseNTorHandshake != -1)
    return options->UseNTorHandshake;
  return networkstatus_get_param(NULL, "UseNTorHandshake", 0, 0, 1);
}
#endif

/** 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>
 * accordingly. */
static void
circuit_pick_create_handshake(uint8_t *cell_type_out,
                              uint16_t *handshake_type_out,
                              const extend_info_t *ei)
{
#ifdef CURVE25519_ENABLED
  if (!tor_mem_is_zero((const char*)ei->curve25519_onion_key.public_key,
                       CURVE25519_PUBKEY_LEN) &&
      circuits_can_use_ntor()) {
    *cell_type_out = CELL_CREATE2;
    *handshake_type_out = ONION_HANDSHAKE_TYPE_NTOR;
    return;
  }
#else
  (void) ei;
#endif

  *cell_type_out = CELL_CREATE;
  *handshake_type_out = ONION_HANDSHAKE_TYPE_TAP;
}

/** Decide whether to use a TAP or ntor handshake for connecting to <b>ei</b>
 * directly, and set *<b>handshake_type_out</b> accordingly. Decide whether,
 * in extending through <b>node</b> to do so, 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. */
static void
circuit_pick_extend_handshake(uint8_t *cell_type_out,
                              uint8_t *create_cell_type_out,
                              uint16_t *handshake_type_out,
                              const node_t *node_prev,
                              const extend_info_t *ei)
{
  uint8_t t;
  circuit_pick_create_handshake(&t, handshake_type_out, ei);
  /* XXXX024 The check for whether the node has a curve25519 key is a bad
   * proxy for whether it can do extend2 cells; once a version that
   * handles extend2 cells is out, remove it. */
  if (node_prev &&
      *handshake_type_out != ONION_HANDSHAKE_TYPE_TAP &&
      (node_has_curve25519_onion_key(node_prev) ||
       (node_prev->rs && node_prev->rs->version_supports_extend2_cells))) {
    *cell_type_out = RELAY_COMMAND_EXTEND2;
    *create_cell_type_out = CELL_CREATE2;
  } else {
    *cell_type_out = RELAY_COMMAND_EXTEND;
    *create_cell_type_out = CELL_CREATE;
  }
}

692
/** This is the backbone function for building circuits.
Mike Perry's avatar
Mike Perry committed
693
 *
694
695
696
697
698
 * If circ's first hop is closed, then we need to build a create
 * cell and send it forward.
 *
 * Otherwise, we need to build a relay extend cell and send it
 * forward.
699
 *
700
 * Return -reason if we want to tear down circ, else return 0.
Mike Perry's avatar
Mike Perry committed
701
 */
702
703
int
circuit_send_next_onion_skin(origin_circuit_t *circ)
Mike Perry's avatar
Mike Perry committed
704
{
705
706
  crypt_path_t *hop;
  const node_t *node;
Mike Perry's avatar
Mike Perry committed
707

708
  tor_assert(circ);
Mike Perry's avatar
Mike Perry committed
709

710
  if (circ->cpath->state == CPATH_STATE_CLOSED) {
711
712
    /* This is the first hop. */
    create_cell_t cc;
713
    int fast;
714
    int len;
715
    log_debug(LD_CIRC,"First skin; sending create cell.");
716
    memset(&cc, 0, sizeof(cc));
717
718
719
720
    if (circ->build_state->onehop_tunnel)
      control_event_bootstrap(BOOTSTRAP_STATUS_ONEHOP_CREATE, 0);
    else
      control_event_bootstrap(BOOTSTRAP_STATUS_CIRCUIT_CREATE, 0);
Mike Perry's avatar
Mike Perry committed
721

722
723
724
725
    node = node_get_by_id(circ->base_.n_chan->identity_digest);
    fast = should_use_create_fast_for_circuit(circ);
    if (!fast) {
      /* We are an OR and we know the right onion key: we should
726
       * send a create cell.
727
       */
728
729
      circuit_pick_create_handshake(&cc.cell_type, &cc.handshake_type,
                                    circ->cpath->extend_info);
730
731
732
733
734
      note_request("cell: create", 1);
    } else {
      /* We are not an OR, and we're building the first hop of a circuit to a
       * new OR: we can be speedy and use CREATE_FAST to save an RSA operation
       * and a DH operation. */
735
736
      cc.cell_type = CELL_CREATE_FAST;
      cc.handshake_type = ONION_HANDSHAKE_TYPE_FAST;
737
      note_request("cell: create fast", 1);
Mike Perry's avatar
Mike Perry committed
738
739
    }

740
741
742
743
744
    len = onion_skin_create(cc.handshake_type,
                            circ->cpath->extend_info,
                            &circ->cpath->handshake_state,
                            cc.onionskin);
    if (len < 0) {
745
746
747
      log_warn(LD_CIRC,"onion_skin_create (first hop) failed.");
      return - END_CIRC_REASON_INTERNAL;
    }
748
    cc.handshake_len = len;
749

750
    if (circuit_deliver_create_cell(TO_CIRCUIT(circ), &cc, 0) < 0)
751
      return - END_CIRC_REASON_RESOURCELIMIT;
Mike Perry's avatar
Mike Perry committed
752

753
754
755
756
757
758
    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>");
  } else {
759
760
    extend_cell_t ec;
    int len;
761
762
763
764
    tor_assert(circ->cpath->state == CPATH_STATE_OPEN);
    tor_assert(circ->base_.state == CIRCUIT_STATE_BUILDING);
    log_debug(LD_CIRC,"starting to send subsequent skin.");
    hop = onion_next_hop_in_cpath(circ->cpath);
765
    memset(&ec, 0, sizeof(ec));
766
767
768
769
770
771
772
    if (!hop) {
      /* done building the circuit. whew. */
      circuit_set_state(TO_CIRCUIT(circ), CIRCUIT_STATE_OPEN);
      if (circuit_timeout_want_to_count_circ(circ)) {
        struct timeval end;
        long timediff;
        tor_gettimeofday(&end);
773
        timediff = tv_mdiff(&circ->base_.timestamp_began, &end);
Mike Perry's avatar
Mike Perry committed
774

775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
        /*
         * If the circuit build time is much greater than we would have cut
         * it off at, we probably had a suspend event along this codepath,
         * and we should discard the value.
         */
        if (timediff < 0 || timediff > 2*circ_times.close_ms+1000) {
          log_notice(LD_CIRC, "Strange value for circuit build time: %ldmsec. "
                              "Assuming clock jump. Purpose %d (%s)", timediff,
                     circ->base_.purpose,
                     circuit_purpose_to_string(circ->base_.purpose));
        } else if (!circuit_build_times_disabled()) {
          /* Only count circuit times if the network is live */
          if (circuit_build_times_network_check_live(&circ_times)) {
            circuit_build_times_add_time(&circ_times, (build_time_t)timediff);
            circuit_build_times_set_timeout(&circ_times);
          }
791

792
793
794
795
          if (circ->base_.purpose != CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
            circuit_build_times_network_circ_success(&circ_times);
          }
        }
796
      }
797
798
      log_info(LD_CIRC,"circuit built!");
      circuit_reset_failure_count(0);
799

800
801
      if (circ->build_state->onehop_tunnel || circ->has_opened) {
        control_event_bootstrap(BOOTSTRAP_STATUS_REQUESTING_STATUS, 0);
802
803
      }

804
805
806
807
808
809
810
811
812
813
814
815
816
817
      if (!can_complete_circuit && !circ->build_state->onehop_tunnel) {
        const or_options_t *options = get_options();
        can_complete_circuit=1;
        /* FFFF Log a count of known routers here */
        log_notice(LD_GENERAL,
            "Tor has successfully opened a circuit. "
            "Looks like client functionality is working.");
        control_event_bootstrap(BOOTSTRAP_STATUS_DONE, 0);
        control_event_client_status(LOG_NOTICE, "CIRCUIT_ESTABLISHED");
        clear_broken_connection_map(1);
        if (server_mode(options) && !check_whether_orport_reachable()) {
          inform_testing_reachability();
          consider_testing_reachability(1, 1);
        }
818
      }
Mike Perry's avatar
Mike Perry committed
819

820
      pathbias_count_build_success(circ);
821
822
      circuit_rep_hist_note_result(circ);
      circuit_has_opened(circ); /* do other actions as necessary */
Mike Perry's avatar
Mike Perry committed
823

824
      /* We're done with measurement circuits here. Just close them */
825
826
827
828
      if (circ->base_.purpose == CIRCUIT_PURPOSE_C_MEASURE_TIMEOUT) {
        /* If a measurement circ ever gets back to us, consider it
         * succeeded for path bias */
        circ->path_state = PATH_STATE_USE_SUCCEEDED;
829
        circuit_mark_for_close(TO_CIRCUIT(circ), END_CIRC_REASON_FINISHED);
830
      }
831
832
833
834
835
836
837
      return 0;
    }

    if (tor_addr_family(&hop->extend_info->addr) != AF_INET) {
      log_warn(LD_BUG, "Trying to extend to a non-IPv4 address.");
      return - END_CIRC_REASON_INTERNAL;
    }
838

839
840
841
842
843
844
845
846
847
    {
      const node_t *prev_node;
      prev_node = node_get_by_id(hop->prev->extend_info->identity_digest);
      circuit_pick_extend_handshake(&ec.cell_type,
                                    &ec.create_cell.cell_type,
                                    &ec.create_cell.handshake_type,
                                    prev_node,
                                    hop->extend_info);
    }
848

849
850
851
852
    tor_addr_copy(&ec.orport_ipv4.addr, &hop->extend_info->addr);
    ec.orport_ipv4.port = hop->extend_info->port;
    tor_addr_make_unspec(&ec.orport_ipv6.addr);
    memcpy(ec.node_id, hop->extend_info->identity_digest, DIGEST_LEN);
853

854
855
856
857
858
    len = onion_skin_create(ec.create_cell.handshake_type,
                            hop->extend_info,
                            &hop->handshake_state,
                            ec.create_cell.onionskin);
    if (len < 0) {
859
860
861
      log_warn(LD_CIRC,"onion_skin_create failed.");
      return - END_CIRC_REASON_INTERNAL;
    }
862
    ec.create_cell.handshake_len = len;
Mike Perry's avatar
Mike Perry committed
863

864
865
    log_info(LD_CIRC,"Sending extend relay cell.");
    note_request("cell: extend", 1);
866
867
868
869
870
871
872
873
    {
      uint8_t command = 0;
      uint16_t payload_len=0;
      uint8_t payload[RELAY_PAYLOAD_SIZE];
      if (extend_cell_format(&command, &payload_len, payload, &ec)<0) {
        log_warn(LD_CIRC,"Couldn't format extend cell");
        return -END_CIRC_REASON_INTERNAL;
      }
Mike Perry's avatar
Mike Perry committed
874

875
876
877
878
879
880
881
882
      /* send it to hop->prev, because it will transfer
       * it to a create cell and then send to hop */
      if (relay_send_command_from_edge(0, TO_CIRCUIT(circ),
                                       command,
                                       (char*)payload, payload_len,
                                       hop->prev) < 0)
        return 0; /* circuit is closed */
    }
883
    hop->state = CPATH_STATE_AWAITING_KEYS;
Mike Perry's avatar
Mike Perry committed
884
  }
885
  return 0;
886
887
}

888
889
890
/** Our clock just jumped by <b>seconds_elapsed</b>. Assume
 * something has also gone wrong with our network: notify the user,
 * and abandon all not-yet-used circuits. */
891
void
892
circuit_note_clock_jumped(int seconds_elapsed)
893
{
894
895
896
897
898
899
900
901
902
903
904
905
  int severity = server_mode(get_options()) ? LOG_WARN : LOG_NOTICE;
  tor_log(severity, LD_GENERAL, "Your system clock just jumped %d seconds %s; "
      "assuming established circuits no longer work.",
      seconds_elapsed >=0 ? seconds_elapsed : -seconds_elapsed,
      seconds_elapsed >=0 ? "forward" : "backward");
  control_event_general_status(LOG_WARN, "CLOCK_JUMPED TIME=%d",
                               seconds_elapsed);
  can_complete_circuit=0; /* so it'll log when it works again */
  control_event_client_status(severity, "CIRCUIT_NOT_ESTABLISHED REASON=%s",
                              "CLOCK_JUMPED");
  circuit_mark_all_unused_circs();
  circuit_expire_all_dirty_circs();
906
907
}

908
909
910
911
912
913
914
/** Take the 'extend' <b>cell</b>, pull out addr/port plus the onion
 * skin and identity digest for the next hop. If we're already connected,
 * pass the onion skin to the next hop using a create cell; otherwise
 * launch a new OR connection, and <b>circ</b> will notice when the
 * connection succeeds or fails.
 *
 * Return -1 if we want to warn and tear down the circuit, else return 0.
Mike Perry's avatar
Mike Perry committed
915
 */
916
int
917
circuit_extend(cell_t *cell, circuit_t *circ)
918
{
919
920
  channel_t *n_chan;
  relay_header_t rh;
921
  extend_cell_t ec;
922
923
  const char *msg = NULL;
  int should_launch = 0;
924

925
926
927
928
  if (circ->n_chan) {
    log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
           "n_chan already set. Bug/attack. Closing.");
    return -1;
929
  }
930
931
932
933
  if (circ->n_hop) {
    log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
           "conn to next hop already launched. Bug/attack. Closing.");
    return -1;
934
  }
935

936
937
938
939
  if (!server_mode(get_options())) {
    log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
           "Got an extend cell, but running as a client. Closing.");
    return -1;
940
941
  }

942
  relay_header_unpack(&rh, cell->payload);
943

944
945
946
  if (extend_cell_parse(&ec, rh.command,
                        cell->payload+RELAY_HEADER_SIZE,
                        rh.length) < 0) {
947
    log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
948
           "Can't parse extend cell. Closing circuit.");
949
    return -1;
Mike Perry's avatar
Mike Perry committed
950
  }
951

952
  if (!ec.orport_ipv4.port || tor_addr_is_null(&ec.orport_ipv4.addr)) {
953
954
955
    log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
           "Client asked me to extend to zero destination port or addr.");
    return -1;
956
957
  }

958
  if (tor_addr_is_internal(&ec.orport_ipv4.addr, 0) &&
959
960
961
962
      !get_options()->ExtendAllowPrivateAddresses) {
    log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
           "Client asked me to extend to a private address");
    return -1;
963
964
  }

965
966
967
968
969
970
  /* Check if they asked us for 0000..0000. We support using
   * an empty fingerprint for the first hop (e.g. for a bridge relay),
   * but we don't want to let people send us extend cells for empty
   * fingerprints -- a) because it opens the user up to a mitm attack,
   * and b) because it lets an attacker force the relay to hold open a
   * new TLS connection for each extend request. */
971
  if (tor_digest_is_zero((const char*)ec.node_id)) {
972
973
974
    log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
           "Client asked me to extend without specifying an id_digest.");
    return -1;
975
976
  }

977
978
979
  /* Next, check if we're being asked to connect to the hop that the
   * extend cell came from. There isn't any reason for that, and it can
   * assist circular-path attacks. */
980
  if (tor_memeq(ec.node_id,
981
982
983
984
985
986
                TO_OR_CIRCUIT(circ)->p_chan->identity_digest,
                DIGEST_LEN)) {
    log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
           "Client asked me to extend back to the previous hop.");
    return -1;
  }
987

988
989
  n_chan = channel_get_for_extend((const char*)ec.node_id,
                                  &ec.orport_ipv4.addr,
990
991
                                  &msg,
                                  &should_launch);
992

993
994
  if (!n_chan) {
    log_debug(LD_CIRC|LD_OR,"Next router (%s): %s",
995
996
              fmt_addrport(&ec.orport_ipv4.addr,ec.orport_ipv4.port),
              msg?msg:"????");
997

998
    circ->n_hop = extend_info_new(NULL /*nickname*/,
999
1000
                                  (const char*)ec.node_id,
                                  NULL /*onion_key*/,
For faster browsing, not all history is shown. View entire blame