entrynodes.c 125 KB
Newer Older
1
2
3
/* Copyright (c) 2001 Matej Pfajfar.
 * Copyright (c) 2001-2004, Roger Dingledine.
 * 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
9
10
11
12
/* See LICENSE for licensing information */

/**
 * \file entrynodes.c
 * \brief Code to manage our fixed first nodes for various functions.
 *
 * Entry nodes can be guards (for general use) or bridges (for censorship
 * circumvention).
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
 *
 * In general, we use entry guards to prevent traffic-sampling attacks:
 * if we chose every circuit independently, an adversary controlling
 * some fraction of paths on the network would observe a sample of every
 * user's traffic. Using guards gives users a chance of not being
 * profiled.
 *
 * The current entry guard selection code is designed to try to avoid
 * _ever_ trying every guard on the network, to try to stick to guards
 * that we've used before, to handle hostile/broken networks, and
 * to behave sanely when the network goes up and down.
 *
 * Our algorithm works as follows: First, we maintain a SAMPLE of guards
 * we've seen in the networkstatus consensus.  We maintain this sample
 * over time, and store it persistently; it is chosen without reference
 * to our configuration or firewall rules.  Guards remain in the sample
 * as they enter and leave the consensus.  We expand this sample as
 * needed, up to a maximum size.
 *
 * As a subset of the sample, we maintain a FILTERED SET of the guards
 * that we would be willing to use if we could connect to them.  The
 * filter removes all the guards that we're excluding because they're
 * bridges (or not bridges), because we have restrictive firewall rules,
 * because of ExcludeNodes, because we of path bias restrictions,
 * because they're absent from the network at present, and so on.
 *
 * As a subset of the filtered set, we keep a REACHABLE FILTERED SET
 * (also called a "usable filtered set") of those guards that we call
 * "reachable" or "maybe reachable".  A guard is reachable if we've
 * connected to it more recently than we've failed.  A guard is "maybe
 * reachable" if we have never tried to connect to it, or if we
 * failed to connect to it so long ago that we no longer think our
 * failure means it's down.
 *
 * As a persistent ordered list whose elements are taken from the
 * sampled set, we track a CONFIRMED GUARDS LIST.  A guard becomes
 * confirmed when we successfully build a circuit through it, and decide
 * to use that circuit.  We order the guards on this list by the order
 * in which they became confirmed.
 *
 * And as a final group, we have an ordered list of PRIMARY GUARDS,
 * whose elements are taken from the filtered set. We prefer
 * confirmed guards to non-confirmed guards for this list, and place
 * other restrictions on it.  The primary guards are the ones that we
 * connect to "when nothing is wrong" -- circuits through them can be used
 * immediately.
 *
 * To build circuits, we take a primary guard if possible -- or a
 * reachable filtered confirmed guard if no primary guard is possible --
 * or a random reachable filtered guard otherwise.  If the guard is
 * primary, we can use the circuit immediately on success.  Otherwise,
 * the guard is now "pending" -- we won't use its circuit unless all
 * of the circuits we're trying to build through better guards have
 * definitely failed.
 *
 * While we're building circuits, we track a little "guard state" for
 * each circuit. We use this to keep track of whether the circuit is
Roger Dingledine's avatar
Roger Dingledine committed
70
 * one that we can use as soon as it's done, or whether it's one that
71
72
73
 * we should keep around to see if we can do better.  In the latter case,
 * a periodic call to entry_guards_upgrade_waiting_circuits() will
 * eventually upgrade it.
74
 **/
75
76
77
78
79
80
81
82
83
/* DOCDOC -- expand this.
 *
 * Information invariants:
 *
 * [x] whenever a guard becomes unreachable, clear its usable_filtered flag.
 *
 * [x] Whenever a guard becomes reachable or maybe-reachable, if its filtered
 * flag is set, set its usable_filtered flag.
 *
84
 * [x] Whenever we get a new consensus, call update_from_consensus(). (LATER.)
85
 *
86
 * [x] Whenever the configuration changes in a relevant way, update the
87
88
89
90
91
92
93
94
 * filtered/usable flags. (LATER.)
 *
 * [x] Whenever we add a guard to the sample, make sure its filtered/usable
 * flags are set as possible.
 *
 * [x] Whenever we remove a guard from the sample, remove it from the primary
 * and confirmed lists.
 *
95
 * [x] When we make a guard confirmed, update the primary list.
96
 *
97
 * [x] When we make a guard filtered or unfiltered, update the primary list.
98
 *
99
 * [x] When we are about to pick a guard, make sure that the primary list is
100
101
102
103
104
105
106
107
108
109
110
111
 * full.
 *
 * [x] Before calling sample_reachable_filtered_entry_guards(), make sure
 * that the filtered, primary, and confirmed flags are up-to-date.
 *
 * [x] Call entry_guard_consider_retry every time we are about to check
 * is_usable_filtered or is_reachable, and every time we set
 * is_filtered to 1.
 *
 * [x] Call entry_guards_changed_for_guard_selection() whenever we update
 * a persistent field.
 */
112

113
114
#define ENTRYNODES_PRIVATE

115
#include "core/or/or.h"
116
117
118
119
120
#include "app/config/config.h"
#include "app/config/confparse.h"
#include "app/config/statefile.h"
#include "core/mainloop/connection.h"
#include "core/mainloop/mainloop.h"
121
122
123
124
#include "core/or/channel.h"
#include "core/or/circuitbuild.h"
#include "core/or/circuitlist.h"
#include "core/or/circuitstats.h"
125
126
127
128
129
130
#include "core/or/circuituse.h"
#include "core/or/policies.h"
#include "feature/client/bridges.h"
#include "feature/client/circpathbias.h"
#include "feature/client/entrynodes.h"
#include "feature/client/transports.h"
131
#include "feature/control/control.h"
132
#include "feature/dircommon/directory.h"
133
#include "feature/nodelist/describe.h"
134
135
#include "feature/nodelist/microdesc.h"
#include "feature/nodelist/networkstatus.h"
136
137
#include "feature/nodelist/nickname.h"
#include "feature/nodelist/nodelist.h"
138
#include "feature/nodelist/node_select.h"
139
#include "feature/nodelist/routerset.h"
140
141
142
#include "feature/relay/router.h"
#include "lib/crypt_ops/crypto_rand.h"
#include "lib/crypt_ops/digestset.h"
143
#include "lib/encoding/confline.h"
144
#include "lib/math/fp.h"
145

146
147
148
#include "feature/nodelist/node_st.h"
#include "core/or/origin_circuit_st.h"
#include "app/config/or_state_st.h"
149

150
/** A list of existing guard selection contexts. */
151
static smartlist_t *guard_contexts = NULL;
152
/** The currently enabled guard selection context. */
153
static guard_selection_t *curr_guard_context = NULL;
154

155
156
157
158
/** A value of 1 means that at least one context has changed,
 * and those changes need to be flushed to disk. */
static int entry_guards_dirty = 0;

159
160
161
static void entry_guard_set_filtered_flags(const or_options_t *options,
                                           guard_selection_t *gs,
                                           entry_guard_t *guard);
162
163
static void pathbias_check_use_success_count(entry_guard_t *guard);
static void pathbias_check_close_success_count(entry_guard_t *guard);
164
static int node_is_possible_guard(const node_t *node);
165
166
static int node_passes_guard_filter(const or_options_t *options,
                                    const node_t *node);
167
168
169
170
static entry_guard_t *entry_guard_add_to_sample_impl(guard_selection_t *gs,
                               const uint8_t *rsa_id_digest,
                               const char *nickname,
                               const tor_addr_port_t *bridge_addrport);
171
172
static entry_guard_t *get_sampled_guard_by_bridge_addr(guard_selection_t *gs,
                                              const tor_addr_port_t *addrport);
173
174
static int entry_guard_obeys_restriction(const entry_guard_t *guard,
                                         const entry_guard_restriction_t *rst);
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196

/** Return 0 if we should apply guardfraction information found in the
 *  consensus. A specific consensus can be specified with the
 *  <b>ns</b> argument, if NULL the most recent one will be picked.*/
int
should_apply_guardfraction(const networkstatus_t *ns)
{
  /* We need to check the corresponding torrc option and the consensus
   * parameter if we need to. */
  const or_options_t *options = get_options();

  /* If UseGuardFraction is 'auto' then check the same-named consensus
   * parameter. If the consensus parameter is not present, default to
   * "off". */
  if (options->UseGuardFraction == -1) {
    return networkstatus_get_param(ns, "UseGuardFraction",
                                   0, /* default to "off" */
                                   0, 1);
  }

  return options->UseGuardFraction;
}
197

198
/** Return true iff we know a preferred descriptor for <b>guard</b> */
199
200
201
202
203
204
static int
guard_has_descriptor(const entry_guard_t *guard)
{
  const node_t *node = node_get_by_id(guard->identity);
  if (!node)
    return 0;
205
  return node_has_preferred_descriptor(node, 1);
206
207
}

208
/**
209
210
 * Try to determine the correct type for a selection named "name",
 * if <b>type</b> is GS_TYPE_INFER.
211
 */
212
213
214
STATIC guard_selection_type_t
guard_selection_infer_type(guard_selection_type_t type,
                           const char *name)
215
{
216
  if (type == GS_TYPE_INFER) {
Nick Mathewson's avatar
Nick Mathewson committed
217
    if (!strcmp(name, "bridges"))
218
219
220
221
222
223
      type = GS_TYPE_BRIDGE;
    else if (!strcmp(name, "restricted"))
      type = GS_TYPE_RESTRICTED;
    else
      type = GS_TYPE_NORMAL;
  }
224
225
226
227
228
229
230
231
232
233
234
235
236
  return type;
}

/**
 * Allocate and return a new guard_selection_t, with the name <b>name</b>.
 */
STATIC guard_selection_t *
guard_selection_new(const char *name,
                    guard_selection_type_t type)
{
  guard_selection_t *gs;

  type = guard_selection_infer_type(type, name);
237

238
  gs = tor_malloc_zero(sizeof(*gs));
239
  gs->name = tor_strdup(name);
240
  gs->type = type;
241
  gs->sampled_entry_guards = smartlist_new();
242
243
  gs->confirmed_entry_guards = smartlist_new();
  gs->primary_entry_guards = smartlist_new();
244
245
246
247

  return gs;
}

248
249
250
251
252
/**
 * Return the guard selection called <b>name</b>. If there is none, and
 * <b>create_if_absent</b> is true, then create and return it.  If there
 * is none, and <b>create_if_absent</b> is false, then return NULL.
 */
253
STATIC guard_selection_t *
254
255
256
get_guard_selection_by_name(const char *name,
                            guard_selection_type_t type,
                            int create_if_absent)
257
258
259
260
261
262
263
264
265
266
267
268
{
  if (!guard_contexts) {
    guard_contexts = smartlist_new();
  }
  SMARTLIST_FOREACH_BEGIN(guard_contexts, guard_selection_t *, gs) {
    if (!strcmp(gs->name, name))
      return gs;
  } SMARTLIST_FOREACH_END(gs);

  if (! create_if_absent)
    return NULL;

269
270
  log_debug(LD_GUARD, "Creating a guard selection called %s", name);
  guard_selection_t *new_selection = guard_selection_new(name, type);
271
272
273
274
275
  smartlist_add(guard_contexts, new_selection);

  return new_selection;
}

276
277
278
279
280
281
/**
 * Allocate the first guard context that we're planning to use,
 * and make it the current context.
 */
static void
create_initial_guard_context(void)
282
{
283
  tor_assert(! curr_guard_context);
284
285
286
  if (!guard_contexts) {
    guard_contexts = smartlist_new();
  }
287
288
289
  guard_selection_type_t type = GS_TYPE_INFER;
  const char *name = choose_guard_selection(
                             get_options(),
290
291
292
                             networkstatus_get_reasonably_live_consensus(
                                                    approx_time(),
                                                    usable_consensus_flavor()),
293
294
295
296
297
                             NULL,
                             &type);
  tor_assert(name); // "name" can only be NULL if we had an old name.
  tor_assert(type != GS_TYPE_INFER);
  log_notice(LD_GUARD, "Starting with guard context \"%s\"", name);
298
  curr_guard_context = get_guard_selection_by_name(name, type, 1);
299
}
300

301
302
303
304
/** Get current default guard_selection_t, creating it if necessary */
guard_selection_t *
get_guard_selection_info(void)
{
305
  if (!curr_guard_context) {
306
    create_initial_guard_context();
307
308
309
310
311
  }

  return curr_guard_context;
}

312
313
314
315
316
317
318
319
/** Return a statically allocated human-readable description of <b>guard</b>
 */
const char *
entry_guard_describe(const entry_guard_t *guard)
{
  static char buf[256];
  tor_snprintf(buf, sizeof(buf),
               "%s ($%s)",
320
               strlen(guard->nickname) ? guard->nickname : "[bridge]",
George Kadianakis's avatar
George Kadianakis committed
321
               hex_str(guard->identity, DIGEST_LEN));
322
323
324
  return buf;
}

325
326
327
328
329
330
331
/** Return <b>guard</b>'s 20-byte RSA identity digest */
const char *
entry_guard_get_rsa_id_digest(const entry_guard_t *guard)
{
  return guard->identity;
}

332
333
334
335
336
337
338
/** Return the pathbias state associated with <b>guard</b>. */
guard_pathbias_t *
entry_guard_get_pathbias_state(entry_guard_t *guard)
{
  return &guard->pb;
}

339
340
HANDLE_IMPL(entry_guard, entry_guard_t, ATTR_UNUSED STATIC)

341
/** Return an interval betweeen 'now' and 'max_backdate' seconds in the past,
342
343
344
345
346
 * chosen uniformly at random.  We use this before recording persistent
 * dates, so that we aren't leaking exactly when we recorded it.
 */
MOCK_IMPL(STATIC time_t,
randomize_time,(time_t now, time_t max_backdate))
347
348
349
350
351
352
353
354
355
356
357
358
359
{
  tor_assert(max_backdate > 0);

  time_t earliest = now - max_backdate;
  time_t latest = now;
  if (earliest <= 0)
    earliest = 1;
  if (latest <= earliest)
    latest = earliest + 1;

  return crypto_rand_time_range(earliest, latest);
}

360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
/**
 * @name parameters for networkstatus algorithm
 *
 * These parameters are taken from the consensus; some are overrideable in
 * the torrc.
 */
/**@{*/
/**
 * We never let our sampled guard set grow larger than this fraction
 * of the guards on the network.
 */
STATIC double
get_max_sample_threshold(void)
{
  int32_t pct =
    networkstatus_get_param(NULL, "guard-max-sample-threshold-percent",
                            DFLT_MAX_SAMPLE_THRESHOLD_PERCENT,
                            1, 100);
  return pct / 100.0;
}
380
381
382
383
384
385
386
387
388
389
/**
 * We never let our sampled guard set grow larger than this number.
 */
STATIC int
get_max_sample_size_absolute(void)
{
  return (int) networkstatus_get_param(NULL, "guard-max-sample-size",
                                       DFLT_MAX_SAMPLE_SIZE,
                                       1, INT32_MAX);
}
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
/**
 * We always try to make our sample contain at least this many guards.
 */
STATIC int
get_min_filtered_sample_size(void)
{
  return networkstatus_get_param(NULL, "guard-min-filtered-sample-size",
                                 DFLT_MIN_FILTERED_SAMPLE_SIZE,
                                 1, INT32_MAX);
}
/**
 * If a guard is unlisted for this many days in a row, we remove it.
 */
STATIC int
get_remove_unlisted_guards_after_days(void)
{
  return networkstatus_get_param(NULL,
                                 "guard-remove-unlisted-guards-after-days",
                                 DFLT_REMOVE_UNLISTED_GUARDS_AFTER_DAYS,
                                 1, 365*10);
}
411
412
413
414
415
416
417
418
419
420
421

/**
 * Return number of seconds that will make a guard no longer eligible
 * for selection if unlisted for this long.
 */
static time_t
get_remove_unlisted_guards_after_seconds(void)
{
  return get_remove_unlisted_guards_after_days() * 24 * 60 * 60;
}

422
423
424
425
426
/**
 * We remove unconfirmed guards from the sample after this many days,
 * regardless of whether they are listed or unlisted.
 */
STATIC int
427
get_guard_lifetime(void)
428
{
429
430
431
432
  if (get_options()->GuardLifetime >= 86400)
    return get_options()->GuardLifetime;
  int32_t days;
  days = networkstatus_get_param(NULL,
433
434
                                 "guard-lifetime-days",
                                 DFLT_GUARD_LIFETIME_DAYS, 1, 365*10);
435
  return days * 86400;
436
437
438
439
440
441
}
/**
 * We remove confirmed guards from the sample if they were sampled
 * GUARD_LIFETIME_DAYS ago and confirmed this many days ago.
 */
STATIC int
442
get_guard_confirmed_min_lifetime(void)
443
{
444
445
446
447
  if (get_options()->GuardLifetime >= 86400)
    return get_options()->GuardLifetime;
  int32_t days;
  days = networkstatus_get_param(NULL, "guard-confirmed-min-lifetime-days",
448
449
                                 DFLT_GUARD_CONFIRMED_MIN_LIFETIME_DAYS,
                                 1, 365*10);
450
  return days * 86400;
451
452
453
454
455
456
457
}
/**
 * How many guards do we try to keep on our primary guard list?
 */
STATIC int
get_n_primary_guards(void)
{
458
459
460
461
462
  /* If the user has explicitly configured the number of primary guards, do
   * what the user wishes to do */
  const int configured_primaries = get_options()->NumPrimaryGuards;
  if (configured_primaries) {
    return configured_primaries;
463
464
  }

465
466
  /* otherwise check for consensus parameter and if that's not set either, just
   * use the default value. */
467
468
  return networkstatus_get_param(NULL,
                                 "guard-n-primary-guards",
469
470
                                 DFLT_N_PRIMARY_GUARDS, 1, INT32_MAX);
}
471
472
473
474
475
/**
 * Return the number of the live primary guards we should look at when
 * making a circuit.
 */
STATIC int
476
477
478
479
480
get_n_primary_guards_to_use(guard_usage_t usage)
{
  int configured;
  const char *param_name;
  int param_default;
481
482
483

  /* If the user has explicitly configured the amount of guards, use
     that. Otherwise, fall back to the default value. */
484
485
486
487
488
489
490
491
492
493
494
  if (usage == GUARD_USAGE_DIRGUARD) {
    configured = get_options()->NumDirectoryGuards;
    param_name = "guard-n-primary-dir-guards-to-use";
    param_default = DFLT_N_PRIMARY_DIR_GUARDS_TO_USE;
  } else {
    configured = get_options()->NumEntryGuards;
    param_name = "guard-n-primary-guards-to-use";
    param_default = DFLT_N_PRIMARY_GUARDS_TO_USE;
  }
  if (configured >= 1) {
    return configured;
495
496
  }
  return networkstatus_get_param(NULL,
497
                                 param_name, param_default, 1, INT32_MAX);
498
}
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
/**
 * If we haven't successfully built or used a circuit in this long, then
 * consider that the internet is probably down.
 */
STATIC int
get_internet_likely_down_interval(void)
{
  return networkstatus_get_param(NULL, "guard-internet-likely-down-interval",
                                 DFLT_INTERNET_LIKELY_DOWN_INTERVAL,
                                 1, INT32_MAX);
}
/**
 * If we're trying to connect to a nonprimary guard for at least this
 * many seconds, and we haven't gotten the connection to work, we will treat
 * lower-priority guards as usable.
 */
STATIC int
get_nonprimary_guard_connect_timeout(void)
{
  return networkstatus_get_param(NULL,
                                 "guard-nonprimary-guard-connect-timeout",
                                 DFLT_NONPRIMARY_GUARD_CONNECT_TIMEOUT,
                                 1, INT32_MAX);
}
/**
 * If a circuit has been sitting around in 'waiting for better guard' state
 * for at least this long, we'll expire it.
 */
STATIC int
get_nonprimary_guard_idle_timeout(void)
{
  return networkstatus_get_param(NULL,
                                 "guard-nonprimary-guard-idle-timeout",
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
                                 DFLT_NONPRIMARY_GUARD_IDLE_TIMEOUT,
                                 1, INT32_MAX);
}
/**
 * If our configuration retains fewer than this fraction of guards from the
 * torrc, we are in a restricted setting.
 */
STATIC double
get_meaningful_restriction_threshold(void)
{
  int32_t pct = networkstatus_get_param(NULL,
                                        "guard-meaningful-restriction-percent",
                                        DFLT_MEANINGFUL_RESTRICTION_PERCENT,
                                        1, INT32_MAX);
  return pct / 100.0;
}
/**
 * If our configuration retains fewer than this fraction of guards from the
 * torrc, we are in an extremely restricted setting, and should warn.
 */
STATIC double
get_extreme_restriction_threshold(void)
{
  int32_t pct = networkstatus_get_param(NULL,
                                        "guard-extreme-restriction-percent",
                                        DFLT_EXTREME_RESTRICTION_PERCENT,
                                        1, INT32_MAX);
  return pct / 100.0;
560
}
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606

/* Mark <b>guard</b> as maybe reachable again. */
static void
mark_guard_maybe_reachable(entry_guard_t *guard)
{
  if (guard->is_reachable != GUARD_REACHABLE_NO) {
    return;
  }

  /* Note that we do not clear failing_since: this guard is now only
   * _maybe-reachable_. */
  guard->is_reachable = GUARD_REACHABLE_MAYBE;
  if (guard->is_filtered_guard)
    guard->is_usable_filtered_guard = 1;
}

/**
 * Called when the network comes up after having seemed to be down for
 * a while: Mark the primary guards as maybe-reachable so that we'll
 * try them again.
 */
STATIC void
mark_primary_guards_maybe_reachable(guard_selection_t *gs)
{
  tor_assert(gs);

  if (!gs->primary_guards_up_to_date)
    entry_guards_update_primary(gs);

  SMARTLIST_FOREACH_BEGIN(gs->primary_entry_guards, entry_guard_t *, guard) {
    mark_guard_maybe_reachable(guard);
  } SMARTLIST_FOREACH_END(guard);
}

/* Called when we exhaust all guards in our sampled set: Marks all guards as
   maybe-reachable so that we 'll try them again. */
static void
mark_all_guards_maybe_reachable(guard_selection_t *gs)
{
  tor_assert(gs);

  SMARTLIST_FOREACH_BEGIN(gs->sampled_entry_guards, entry_guard_t *, guard) {
    mark_guard_maybe_reachable(guard);
  } SMARTLIST_FOREACH_END(guard);
}

607
608
/**@}*/

609
610
611
612
613
614
615
616
/**
 * Given our options and our list of nodes, return the name of the
 * guard selection that we should use.  Return NULL for "use the
 * same selection you were using before.
 */
STATIC const char *
choose_guard_selection(const or_options_t *options,
                       const networkstatus_t *live_ns,
George Kadianakis's avatar
George Kadianakis committed
617
                       const guard_selection_t *old_selection,
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
                       guard_selection_type_t *type_out)
{
  tor_assert(options);
  tor_assert(type_out);

  if (options->UseBridges) {
    *type_out = GS_TYPE_BRIDGE;
    return "bridges";
  }

  if (! live_ns) {
    /* without a networkstatus, we can't tell any more than that. */
    *type_out = GS_TYPE_NORMAL;
    return "default";
  }

  const smartlist_t *nodes = nodelist_get_list();
  int n_guards = 0, n_passing_filter = 0;
  SMARTLIST_FOREACH_BEGIN(nodes, const node_t *, node) {
637
    if (node_is_possible_guard(node)) {
638
      ++n_guards;
639
      if (node_passes_guard_filter(options, node)) {
640
641
642
643
644
        ++n_passing_filter;
      }
    }
  } SMARTLIST_FOREACH_END(node);

645
646
  /* We use separate 'high' and 'low' thresholds here to prevent flapping
   * back and forth */
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
  const int meaningful_threshold_high =
    (int)(n_guards * get_meaningful_restriction_threshold() * 1.05);
  const int meaningful_threshold_mid =
    (int)(n_guards * get_meaningful_restriction_threshold());
  const int meaningful_threshold_low =
    (int)(n_guards * get_meaningful_restriction_threshold() * .95);
  const int extreme_threshold =
    (int)(n_guards * get_extreme_restriction_threshold());

  /*
    If we have no previous selection, then we're "restricted" iff we are
    below the meaningful restriction threshold.  That's easy enough.

    But if we _do_ have a previous selection, we make it a little
    "sticky": we only move from "restricted" to "default" when we find
    that we're above the threshold plus 5%, and we only move from
    "default" to "restricted" when we're below the threshold minus 5%.
    That should prevent us from flapping back and forth if we happen to
    be hovering very close to the default.

    The extreme threshold is for warning only.
  */

  static int have_warned_extreme_threshold = 0;
671
672
  if (n_guards &&
      n_passing_filter < extreme_threshold &&
673
674
675
676
677
678
679
680
681
      ! have_warned_extreme_threshold) {
    have_warned_extreme_threshold = 1;
    const double exclude_frac =
      (n_guards - n_passing_filter) / (double)n_guards;
    log_warn(LD_GUARD, "Your configuration excludes %d%% of all possible "
             "guards. That's likely to make you stand out from the "
             "rest of the world.", (int)(exclude_frac * 100));
  }

682
683
  /* Easy case: no previous selection. Just check if we are in restricted or
     normal guard selection. */
684
685
686
687
688
689
690
691
692
693
  if (old_selection == NULL) {
    if (n_passing_filter >= meaningful_threshold_mid) {
      *type_out = GS_TYPE_NORMAL;
      return "default";
    } else {
      *type_out = GS_TYPE_RESTRICTED;
      return "restricted";
    }
  }

George Kadianakis's avatar
George Kadianakis committed
694
695
696
697
698
  /* Trickier case: we do have a previous guard selection context. */
  tor_assert(old_selection);

  /* Use high and low thresholds to decide guard selection, and if we fall in
     the middle then keep the current guard selection context. */
699
700
701
702
703
704
705
  if (n_passing_filter >= meaningful_threshold_high) {
    *type_out = GS_TYPE_NORMAL;
    return "default";
  } else if (n_passing_filter < meaningful_threshold_low) {
    *type_out = GS_TYPE_RESTRICTED;
    return "restricted";
  } else {
George Kadianakis's avatar
George Kadianakis committed
706
707
708
    /* we are in the middle: maintain previous guard selection */
    *type_out = old_selection->type;
    return old_selection->name;
709
710
711
712
713
714
715
  }
}

/**
 * Check whether we should switch from our current guard selection to a
 * different one.  If so, switch and return 1.  Return 0 otherwise.
 *
716
717
718
 * On a 1 return, the caller should mark all currently live circuits unusable
 * for new streams, by calling circuit_mark_all_unused_circs() and
 * circuit_mark_all_dirty_circs_as_unusable().
719
720
721
722
723
724
725
726
727
728
729
730
 */
int
update_guard_selection_choice(const or_options_t *options)
{
  if (!curr_guard_context) {
    create_initial_guard_context();
    return 1;
  }

  guard_selection_type_t type = GS_TYPE_INFER;
  const char *new_name = choose_guard_selection(
                             options,
731
732
733
                             networkstatus_get_reasonably_live_consensus(
                                                    approx_time(),
                                                    usable_consensus_flavor()),
George Kadianakis's avatar
George Kadianakis committed
734
                             curr_guard_context,
735
736
737
738
                             &type);
  tor_assert(new_name);
  tor_assert(type != GS_TYPE_INFER);

George Kadianakis's avatar
George Kadianakis committed
739
  const char *cur_name = curr_guard_context->name;
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
  if (! strcmp(cur_name, new_name)) {
    log_debug(LD_GUARD,
              "Staying with guard context \"%s\" (no change)", new_name);
    return 0; // No change
  }

  log_notice(LD_GUARD, "Switching to guard context \"%s\" (was using \"%s\")",
             new_name, cur_name);
  guard_selection_t *new_guard_context;
  new_guard_context = get_guard_selection_by_name(new_name, type, 1);
  tor_assert(new_guard_context);
  tor_assert(new_guard_context != curr_guard_context);
  curr_guard_context = new_guard_context;

  return 1;
}

757
/**
758
759
760
761
 * Return true iff <b>node</b> has all the flags needed for us to consider it
 * a possible guard when sampling guards.
 */
static int
762
node_is_possible_guard(const node_t *node)
763
764
765
766
767
768
769
770
771
{
  /* The "GUARDS" set is all nodes in the nodelist for which this predicate
   * holds. */

  tor_assert(node);
  return (node->is_possible_guard &&
          node->is_stable &&
          node->is_fast &&
          node->is_valid &&
772
773
          node_is_dir(node) &&
          !router_digest_is_me(node->identity));
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
}

/**
 * Return the sampled guard with the RSA identity digest <b>rsa_id</b>, or
 * NULL if we don't have one. */
STATIC entry_guard_t *
get_sampled_guard_with_id(guard_selection_t *gs,
                          const uint8_t *rsa_id)
{
  tor_assert(gs);
  tor_assert(rsa_id);
  SMARTLIST_FOREACH_BEGIN(gs->sampled_entry_guards, entry_guard_t *, guard) {
    if (tor_memeq(guard->identity, rsa_id, DIGEST_LEN))
      return guard;
  } SMARTLIST_FOREACH_END(guard);
  return NULL;
}

792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
/** If <b>gs</b> contains a sampled entry guard matching <b>bridge</b>,
 * return that guard. Otherwise return NULL. */
static entry_guard_t *
get_sampled_guard_for_bridge(guard_selection_t *gs,
                             const bridge_info_t *bridge)
{
  const uint8_t *id = bridge_get_rsa_id_digest(bridge);
  const tor_addr_port_t *addrport = bridge_get_addr_port(bridge);
  entry_guard_t *guard;
  if (BUG(!addrport))
    return NULL; // LCOV_EXCL_LINE
  guard = get_sampled_guard_by_bridge_addr(gs, addrport);
  if (! guard || (id && tor_memneq(id, guard->identity, DIGEST_LEN)))
    return NULL;
  else
    return guard;
}

/** If we know a bridge_info_t matching <b>guard</b>, return that
 * bridge.  Otherwise return NULL. */
static bridge_info_t *
get_bridge_info_for_guard(const entry_guard_t *guard)
{
815
  const uint8_t *identity = NULL;
816
  if (! tor_digest_is_zero(guard->identity)) {
817
    identity = (const uint8_t *)guard->identity;
818
819
820
  }
  if (BUG(guard->bridge_addr == NULL))
    return NULL;
821
822
823
824
825

  return get_configured_bridge_by_exact_addr_port_digest(
                                                 &guard->bridge_addr->addr,
                                                 guard->bridge_addr->port,
                                                 (const char*)identity);
826
827
}

828
829
830
831
832
833
834
835
836
837
838
839
840
/**
 * Return true iff we have a sampled guard with the RSA identity digest
 * <b>rsa_id</b>. */
static inline int
have_sampled_guard_with_id(guard_selection_t *gs, const uint8_t *rsa_id)
{
  return get_sampled_guard_with_id(gs, rsa_id) != NULL;
}

/**
 * Allocate a new entry_guard_t object for <b>node</b>, add it to the
 * sampled entry guards in <b>gs</b>, and return it. <b>node</b> must
 * not currently be a sampled guard in <b>gs</b>.
841
 */
842
STATIC entry_guard_t *
843
entry_guard_add_to_sample(guard_selection_t *gs,
844
                          const node_t *node)
845
{
846
  log_info(LD_GUARD, "Adding %s to the entry guard sample set.",
847
848
           node_describe(node));

849
850
851
852
  /* make sure that the guard is not already sampled. */
  if (BUG(have_sampled_guard_with_id(gs, (const uint8_t*)node->identity)))
    return NULL; // LCOV_EXCL_LINE

853
854
855
856
857
858
859
860
  return entry_guard_add_to_sample_impl(gs,
                                        (const uint8_t*)node->identity,
                                        node_get_nickname(node),
                                        NULL);
}

/**
 * Backend: adds a new sampled guard to <b>gs</b>, with given identity,
861
862
863
 * nickname, and ORPort.  rsa_id_digest and bridge_addrport are optional, but
 * we need one of them. nickname is optional. The caller is responsible for
 * maintaining the size limit of the SAMPLED_GUARDS set.
864
865
866
867
868
869
870
 */
static entry_guard_t *
entry_guard_add_to_sample_impl(guard_selection_t *gs,
                               const uint8_t *rsa_id_digest,
                               const char *nickname,
                               const tor_addr_port_t *bridge_addrport)
{
871
  const int GUARD_LIFETIME = get_guard_lifetime();
872
873
  tor_assert(gs);

874
  // XXXX #20827 take ed25519 identity here too.
875

876
877
  /* Make sure we can actually identify the guard. */
  if (BUG(!rsa_id_digest && !bridge_addrport))
878
    return NULL; // LCOV_EXCL_LINE
879
880
881
882

  entry_guard_t *guard = tor_malloc_zero(sizeof(entry_guard_t));

  /* persistent fields */
883
  guard->is_persistent = (rsa_id_digest != NULL);
884
  guard->selection_name = tor_strdup(gs->name);
885
886
887
888
  if (rsa_id_digest)
    memcpy(guard->identity, rsa_id_digest, DIGEST_LEN);
  if (nickname)
    strlcpy(guard->nickname, nickname, sizeof(guard->nickname));
889
890
891
  guard->sampled_on_date = randomize_time(approx_time(), GUARD_LIFETIME/10);
  tor_free(guard->sampled_by_version);
  guard->sampled_by_version = tor_strdup(VERSION);
892
  guard->currently_listed = 1;
893
894
895
896
  guard->confirmed_idx = -1;

  /* non-persistent fields */
  guard->is_reachable = GUARD_REACHABLE_MAYBE;
897
898
  if (bridge_addrport)
    guard->bridge_addr = tor_memdup(bridge_addrport, sizeof(*bridge_addrport));
899
900

  smartlist_add(gs->sampled_entry_guards, guard);
901
  guard->in_selection = gs;
902
903
904
905
906
  entry_guard_set_filtered_flags(get_options(), gs, guard);
  entry_guards_changed_for_guard_selection(gs);
  return guard;
}

907
908
909
910
/**
 * Add an entry guard to the "bridges" guard selection sample, with
 * information taken from <b>bridge</b>. Return that entry guard.
 */
911
912
913
static entry_guard_t *
entry_guard_add_bridge_to_sample(guard_selection_t *gs,
                                 const bridge_info_t *bridge)
914
915
916
917
918
919
{
  const uint8_t *id_digest = bridge_get_rsa_id_digest(bridge);
  const tor_addr_port_t *addrport = bridge_get_addr_port(bridge);

  tor_assert(addrport);

920
921
922
923
  /* make sure that the guard is not already sampled. */
  if (BUG(get_sampled_guard_for_bridge(gs, bridge)))
    return NULL; // LCOV_EXCL_LINE

924
925
926
927
928
929
930
931
  return entry_guard_add_to_sample_impl(gs, id_digest, NULL, addrport);
}

/**
 * Return the entry_guard_t in <b>gs</b> whose address is <b>addrport</b>,
 * or NULL if none exists.
*/
static entry_guard_t *
932
933
get_sampled_guard_by_bridge_addr(guard_selection_t *gs,
                                 const tor_addr_port_t *addrport)
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
{
  if (! gs)
    return NULL;
  if (BUG(!addrport))
    return NULL;
  SMARTLIST_FOREACH_BEGIN(gs->sampled_entry_guards, entry_guard_t *, g) {
    if (g->bridge_addr && tor_addr_port_eq(addrport, g->bridge_addr))
      return g;
  } SMARTLIST_FOREACH_END(g);
  return NULL;
}

/** Update the guard subsystem's knowledge of the identity of the bridge
 * at <b>addrport</b>.  Idempotent.
 */
void
entry_guard_learned_bridge_identity(const tor_addr_port_t *addrport,
                                    const uint8_t *rsa_id_digest)
{
  guard_selection_t *gs = get_guard_selection_by_name("bridges",
                                                      GS_TYPE_BRIDGE,
                                                      0);
  if (!gs)
    return;

959
  entry_guard_t *g = get_sampled_guard_by_bridge_addr(gs, addrport);
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
  if (!g)
    return;

  int make_persistent = 0;

  if (tor_digest_is_zero(g->identity)) {
    memcpy(g->identity, rsa_id_digest, DIGEST_LEN);
    make_persistent = 1;
  } else if (tor_memeq(g->identity, rsa_id_digest, DIGEST_LEN)) {
    /* Nothing to see here; we learned something we already knew. */
    if (BUG(! g->is_persistent))
      make_persistent = 1;
  } else {
    char old_id[HEX_DIGEST_LEN+1];
    base16_encode(old_id, sizeof(old_id), g->identity, sizeof(g->identity));
    log_warn(LD_BUG, "We 'learned' an identity %s for a bridge at %s:%d, but "
             "we already knew a different one (%s). Ignoring the new info as "
             "possibly bogus.",
             hex_str((const char *)rsa_id_digest, DIGEST_LEN),
             fmt_and_decorate_addr(&addrport->addr), addrport->port,
             old_id);
    return; // redundant, but let's be clear: we're not making this persistent.
  }

  if (make_persistent) {
    g->is_persistent = 1;
    entry_guards_changed_for_guard_selection(gs);
  }
}

990
991
992
/**
 * Return the number of sampled guards in <b>gs</b> that are "filtered"
 * (that is, we're willing to connect to them) and that are "usable"
993
994
995
996
997
 * (that is, either "reachable" or "maybe reachable").
 *
 * If a restriction is provided in <b>rst</b>, do not count any guards that
 * violate it.
 */
998
STATIC int
999
num_reachable_filtered_guards(const guard_selection_t *gs,
1000
                              const entry_guard_restriction_t *rst)
For faster browsing, not all history is shown. View entire blame