commit 8d59690033b1cc2b462b2b9ed61ddeaebb6f9ab0 Author: Mike Perry <mikeperry-git@fscked.org> Date: Thu May 3 20:15:34 2012 -0700 Defend against entry node path bias attacks The defense counts the circuit failure rate for each guard for the past N circuits. Failure is defined as the ability to complete a first hop, but not finish completing the circuit all the way to the exit. If the failure rate exceeds a certain amount, a notice is emitted. If it exceeds a greater amount, a warn is emitted and the guard is disabled. These values are governed by consensus parameters which we intend to tune as we perform experiments and statistical simulations. --- doc/tor.1.txt | 28 +++++++ src/or/circuitbuild.c | 207 +++++++++++++++++++++++++++++++++++++++++++++++-- src/or/config.c | 16 ++++- src/or/or.h | 11 +++ 4 files changed, 254 insertions(+), 8 deletions(-) diff --git a/doc/tor.1.txt b/doc/tor.1.txt index 468ed63..65bdcfd 100644 --- a/doc/tor.1.txt +++ b/doc/tor.1.txt @@ -1096,6 +1096,34 @@ The following options are useful only for clients (that is, if "auto" (recommended) then it is on for all clients that do not set FetchUselessDescriptors. (Default: auto) +**PathBiasCircTheshold** __NUM__ + + +**PathBiasNoticeRate** __NUM.__ + + +**PathBiasDisableRate** __NUM__ + + +**PathBiasScaleThreshold** __NUM__ + + +**PathBiasScaleFactor** __NUM__:: + These options override the default behavior of Tor's (**currently + experimental**) path bias detection algorithm. To try to find broken or + misbehaving guard nodes, Tor looks for nodes where more than a certain + fraction of circuits through that node fail after the first hop. The + PathBiasCircThreshold option controls how many circuits we need to build + through a guard before we make these checks. The PathBiasNoticeRate and + PathBiasDisableRate options control what fraction of circuits must + succeed through a guard before we will warn about it or disable it, + respectively. When we have seen more than PathBiasScaleThreshold + circuits through a guard, we divide our observations by + PathBiasScaleFactor, so that new observations don't get swamped by old + ones. + + + + By default, or if a negative value is provided for one of these options, + Tor uses reasonable defaults from the networkstatus consensus document. + If no defaults are available there, these options default to 20, .70, + .50, 200, and 4 respectively. + + SERVER OPTIONS -------------- diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c index 3c72204..9969f7e 100644 --- a/src/or/circuitbuild.c +++ b/src/or/circuitbuild.c @@ -70,6 +70,10 @@ typedef struct { * router, 1 if we have. */ unsigned int can_retry : 1; /**< Should we retry connecting to this entry, * in spite of having it marked as unreachable?*/ + unsigned int path_bias_notice : 1; /**< Did we alert the user about path bias + * for this node already? */ + unsigned int path_bias_disabled : 1; /**< Have we disabled this node because + * of path bias issues? */ time_t bad_since; /**< 0 if this guard is currently usable, or the time at * which it was observed to become (according to the * directory or the user configuration) unusable. */ @@ -78,6 +82,10 @@ typedef struct { * connect to it. */ time_t last_attempted; /**< 0 if we can connect to this guard, or the time * at which we last failed to connect to it. */ + + unsigned first_hops; /**< Number of first hops this guard has completed */ + unsigned circuit_successes; /**< Number of successfully built circuits using + * this guard as first hop. */ } entry_guard_t; /** Information about a configured bridge. Currently this just matches the @@ -123,6 +131,7 @@ static int count_acceptable_nodes(smartlist_t *routers); static int onion_append_hop(crypt_path_t **head_ptr, extend_info_t *choice); static void entry_guards_changed(void); +static entry_guard_t *entry_guard_get_by_id_digest(const char *digest); static void bridge_free(bridge_info_t *bridge); @@ -2276,8 +2285,28 @@ circuit_send_next_onion_skin(origin_circuit_t *circ) } log_info(LD_CIRC,"circuit built!"); circuit_reset_failure_count(0); - if (circ->build_state->onehop_tunnel) + /* Don't count cannibalized or onehop circs for path bias */ + if (circ->build_state->onehop_tunnel || circ->has_opened) { control_event_bootstrap(BOOTSTRAP_STATUS_REQUESTING_STATUS, 0); + } else { + entry_guard_t *guard = + entry_guard_get_by_id_digest(circ->_base.n_conn->identity_digest); + + if (guard) { + guard->circuit_successes++; + + log_info(LD_PROTOCOL, "Got success count %u/%u for guard %s", + guard->circuit_successes, guard->first_hops, + guard->nickname); + + if (guard->first_hops < guard->circuit_successes) { + log_warn(LD_BUG, "Unexpectedly high circuit_successes (%u/%u) " + "for guard %s", + guard->circuit_successes, guard->first_hops, + guard->nickname); + } + } + } if (!can_complete_circuit && !circ->build_state->onehop_tunnel) { const or_options_t *options = get_options(); can_complete_circuit=1; @@ -2532,6 +2561,115 @@ circuit_init_cpath_crypto(crypt_path_t *cpath, const char *key_data, return 0; } +/** The minimum number of first hop completions before we start + * thinking about warning about path bias and dropping guards */ +static int +pathbias_get_min_circs(const or_options_t *options) +{ +#define DFLT_PATH_BIAS_MIN_CIRC 20 + if (options->PathBiasCircThreshold >= 5) + return options->PathBiasCircThreshold; + else + return networkstatus_get_param(NULL, "pb_mincircs", + DFLT_PATH_BIAS_MIN_CIRC, + 5, INT32_MAX); +} + +static double +pathbias_get_notice_rate(const or_options_t *options) +{ +#define DFLT_PATH_BIAS_NOTICE_PCT 70 + if (options->PathBiasNoticeRate >= 0.0) + return options->PathBiasNoticeRate; + else + return networkstatus_get_param(NULL, "pb_noticepct", + DFLT_PATH_BIAS_NOTICE_PCT, 0, 100)/100.0; +} + +static double +pathbias_get_disable_rate(const or_options_t *options) +{ +#define DFLT_PATH_BIAS_DISABLE_PCT 50 + if (options->PathBiasDisableRate >= 0.0) + return options->PathBiasDisableRate; + else + return networkstatus_get_param(NULL, "pb_disablepct", + DFLT_PATH_BIAS_DISABLE_PCT, 0, 100)/100.0; +} + +static int +pathbias_get_scale_threshold(const or_options_t *options) +{ +#define DFLT_PATH_BIAS_SCALE_THRESHOLD 200 + if (options->PathBiasScaleThreshold >= 2) + return options->PathBiasScaleThreshold; + else + return networkstatus_get_param(NULL, "pb_scalecircs", + DFLT_PATH_BIAS_SCALE_THRESHOLD, 10, + INT32_MAX); +} + +static int +pathbias_get_scale_factor(const or_options_t *options) +{ +#define DFLT_PATH_BIAS_SCALE_FACTOR 4 + if (options->PathBiasScaleFactor >= 1) + return options->PathBiasScaleFactor; + else + return networkstatus_get_param(NULL, "pb_scalefactor", + DFLT_PATH_BIAS_SCALE_THRESHOLD, 1, INT32_MAX); +} + +/** Increment the number of times we successfully extended a circuit to + * 'guard', first checking if the failure rate is high enough that we should + * eliminate the guard. Return -1 if the guard looks no good; return 0 if the + * guard looks fine. */ +static int +entry_guard_inc_first_hop_count(entry_guard_t *guard) +{ + const or_options_t *options = get_options(); + + entry_guards_changed(); + + if (guard->first_hops > (unsigned)pathbias_get_min_circs(options)) { + /* Note: We rely on the < comparison here to allow us to set a 0 + * rate and disable the feature entirely. If refactoring, don't + * change to <= */ + if (guard->circuit_successes/((double)guard->first_hops) + < pathbias_get_disable_rate(options)) { + + log_warn(LD_PROTOCOL, + "Extremely low circuit success rate %u/%u for guard %s=%s. " + "This might indicate an attack, or a bug.", + guard->circuit_successes, guard->first_hops, guard->nickname, + hex_str(guard->identity, DIGEST_LEN)); + + guard->path_bias_disabled = 1; + guard->bad_since = approx_time(); + return -1; + } else if (guard->circuit_successes/((double)guard->first_hops) + < pathbias_get_notice_rate(options) + && !guard->path_bias_notice) { + guard->path_bias_notice = 1; + log_notice(LD_PROTOCOL, + "Low circuit success rate %u/%u for guard %s=%s.", + guard->circuit_successes, guard->first_hops, guard->nickname, + hex_str(guard->identity, DIGEST_LEN)); + } + } + + /* If we get a ton of circuits, just scale everything down */ + if (guard->first_hops > (unsigned)pathbias_get_scale_threshold(options)) { + const int scale_factor = pathbias_get_scale_factor(options); + guard->first_hops /= scale_factor; + guard->circuit_successes /= scale_factor; + } + guard->first_hops++; + log_info(LD_PROTOCOL, "Got success count %u/%u for guard %s", + guard->circuit_successes, guard->first_hops, guard->nickname); + return 0; +} + /** A created or extended cell came back to us on the circuit, and it included * <b>reply</b> as its body. (If <b>reply_type</b> is CELL_CREATED, the body * contains (the second DH key, plus KH). If <b>reply_type</b> is @@ -2549,9 +2687,22 @@ circuit_finish_handshake(origin_circuit_t *circ, uint8_t reply_type, char keys[CPATH_KEY_MATERIAL_LEN]; crypt_path_t *hop; - if (circ->cpath->state == CPATH_STATE_AWAITING_KEYS) + if (circ->cpath->state == CPATH_STATE_AWAITING_KEYS) { hop = circ->cpath; - else { + /* Don't count cannibalized or onehop circs for path bias */ + if (!circ->has_opened && !circ->build_state->onehop_tunnel) { + entry_guard_t *guard; + + guard = entry_guard_get_by_id_digest( + circ->_base.n_conn->identity_digest); + if (guard) { + if (entry_guard_inc_first_hop_count(guard) < 0) { + /* Bogus guard; we already warned. */ + return -END_CIRC_REASON_TORPROTOCOL; + } + } + } + } else { hop = onion_next_hop_in_cpath(circ->cpath); if (!hop) { /* got an extended when we're all done? */ log_warn(LD_PROTOCOL,"got extended when circ already built? Closing."); @@ -3630,6 +3781,8 @@ entry_guard_set_status(entry_guard_t *e, const node_t *node, *reason = "not recommended as a guard"; else if (routerset_contains_node(options->ExcludeNodes, node)) *reason = "excluded"; + else if (e->path_bias_disabled) + *reason = "path-biased"; if (*reason && ! e->bad_since) { /* Router is newly bad. */ @@ -3694,6 +3847,10 @@ entry_is_live(entry_guard_t *e, int need_uptime, int need_capacity, const or_options_t *options = get_options(); tor_assert(msg); + if (e->path_bias_disabled) { + *msg = "path-biased"; + return NULL; + } if (e->bad_since) { *msg = "bad"; return NULL; @@ -3757,8 +3914,8 @@ num_live_entry_guards(void) /** If <b>digest</b> matches the identity of any node in the * entry_guards list, return that node. Else return NULL. */ -static INLINE entry_guard_t * -is_an_entry_guard(const char *digest) +static entry_guard_t * +entry_guard_get_by_id_digest(const char *digest) { SMARTLIST_FOREACH(entry_guards, entry_guard_t *, entry, if (tor_memeq(digest, entry->identity, DIGEST_LEN)) @@ -3844,7 +4001,7 @@ add_an_entry_guard(const node_t *chosen, int reset_status, int prepend) if (chosen) { node = chosen; - entry = is_an_entry_guard(node->identity); + entry = entry_guard_get_by_id_digest(node->identity); if (entry) { if (reset_status) { entry->bad_since = 0; @@ -3988,6 +4145,7 @@ remove_dead_entry_guards(time_t now) for (i = 0; i < smartlist_len(entry_guards); ) { entry_guard_t *entry = smartlist_get(entry_guards, i); if (entry->bad_since && + ! entry->path_bias_disabled && entry->bad_since + ENTRY_GUARD_REMOVE_AFTER < now) { base16_encode(dbuf, sizeof(dbuf), entry->identity, DIGEST_LEN); @@ -4253,7 +4411,7 @@ entry_guards_set_from_config(const or_options_t *options) /* Remove all currently configured guard nodes, excluded nodes, unreachable * nodes, or non-Guard nodes from entry_nodes. */ SMARTLIST_FOREACH_BEGIN(entry_nodes, const node_t *, node) { - if (is_an_entry_guard(node->identity)) { + if (entry_guard_get_by_id_digest(node->identity)) { SMARTLIST_DEL_CURRENT(entry_nodes, node); continue; } else if (routerset_contains_node(options->ExcludeNodes, node)) { @@ -4539,6 +4697,31 @@ entry_guards_parse_state(or_state_t *state, int set, char **msg) continue; } digestmap_set(added_by, d, tor_strdup(line->value+HEX_DIGEST_LEN+1)); + } else if (!strcasecmp(line->key, "EntryGuardPathBias")) { + const or_options_t *options = get_options(); + unsigned hop_cnt, success_cnt; + + if (tor_sscanf(line->value, "%u %u", &success_cnt, &hop_cnt) != 2) { + log_warn(LD_GENERAL, "Unable to parse guard path bias info: " + "Misformated EntryGuardPathBias %s", escaped(line->value)); + continue; + } + + node->first_hops = hop_cnt; + node->circuit_successes = success_cnt; + log_info(LD_GENERAL, "Read %u/%u path bias for node %s", + node->circuit_successes, node->first_hops, node->nickname); + /* Note: We rely on the < comparison here to allow us to set a 0 + * rate and disable the feature entirely. If refactoring, don't + * change to <= */ + if (node->circuit_successes/((double)node->first_hops) + < pathbias_get_disable_rate(options)) { + node->path_bias_disabled = 1; + log_info(LD_GENERAL, + "Path bias is too high (%u/%u); disabling node %s", + node->circuit_successes, node->first_hops, node->nickname); + } + } else { log_warn(LD_BUG, "Unexpected key %s", line->key); } @@ -4563,6 +4746,8 @@ entry_guards_parse_state(or_state_t *state, int set, char **msg) e->chosen_on_date = time(NULL) - crypto_rand_int(3600*24*30); } } + if (node->path_bias_disabled && !node->bad_since) + node->bad_since = time(NULL); }); if (*msg || !set) { @@ -4658,6 +4843,14 @@ entry_guards_update_state(or_state_t *state) d, e->chosen_by_version, t); next = &(line->next); } + if (e->first_hops) { + *next = line = tor_malloc_zero(sizeof(config_line_t)); + line->key = tor_strdup("EntryGuardPathBias"); + tor_asprintf(&line->value, "%u %u", + e->circuit_successes, e->first_hops); + next = &(line->next); + } + }); if (!get_options()->AvoidDiskWrites) or_state_mark_dirty(get_or_state(), 0); diff --git a/src/or/config.c b/src/or/config.c index 782a6e9..03e93e0 100644 --- a/src/or/config.c +++ b/src/or/config.c @@ -50,6 +50,7 @@ typedef enum config_type_t { CONFIG_TYPE_STRING = 0, /**< An arbitrary string. */ CONFIG_TYPE_FILENAME, /**< A filename: some prefixes get expanded. */ CONFIG_TYPE_UINT, /**< A non-negative integer less than MAX_INT */ + CONFIG_TYPE_INT, /**< Any integer. */ CONFIG_TYPE_PORT, /**< A port from 1...65535, 0 for "not set", or * "auto". */ CONFIG_TYPE_INTERVAL, /**< A number of seconds, with optional units*/ @@ -354,6 +355,13 @@ static config_var_t _option_vars[] = { V(ORListenAddress, LINELIST, NULL), V(ORPort, LINELIST, NULL), V(OutboundBindAddress, STRING, NULL), + + V(PathBiasCircThreshold, INT, "-1"), + V(PathBiasNoticeRate, DOUBLE, "-1"), + V(PathBiasDisableRate, DOUBLE, "-1"), + V(PathBiasScaleThreshold, INT, "-1"), + V(PathBiasScaleFactor, INT, "-1"), + OBSOLETE("PathlenCoinWeight"), V(PerConnBWBurst, MEMUNIT, "0"), V(PerConnBWRate, MEMUNIT, "0"), @@ -498,6 +506,7 @@ static config_var_t _state_vars[] = { VAR("EntryGuardDownSince", LINELIST_S, EntryGuards, NULL), VAR("EntryGuardUnlistedSince", LINELIST_S, EntryGuards, NULL), VAR("EntryGuardAddedBy", LINELIST_S, EntryGuards, NULL), + VAR("EntryGuardPathBias", LINELIST_S, EntryGuards, NULL), V(EntryGuards, LINELIST_V, NULL), VAR("TransportProxy", LINELIST_S, TransportProxies, NULL), @@ -2114,8 +2123,10 @@ config_assign_value(const config_format_t *fmt, or_options_t *options, break; } /* fall through */ + case CONFIG_TYPE_INT: case CONFIG_TYPE_UINT: - i = (int)tor_parse_long(c->value, 10, 0, + i = (int)tor_parse_long(c->value, 10, + var->type==CONFIG_TYPE_INT ? INT_MIN : 0, var->type==CONFIG_TYPE_PORT ? 65535 : INT_MAX, &ok, NULL); if (!ok) { @@ -2498,6 +2509,7 @@ get_assigned_option(const config_format_t *fmt, const void *options, case CONFIG_TYPE_INTERVAL: case CONFIG_TYPE_MSEC_INTERVAL: case CONFIG_TYPE_UINT: + case CONFIG_TYPE_INT: /* This means every or_options_t uint or bool element * needs to be an int. Not, say, a uint16_t or char. */ tor_asprintf(&result->value, "%d", *(int*)value); @@ -2741,6 +2753,7 @@ option_clear(const config_format_t *fmt, or_options_t *options, case CONFIG_TYPE_INTERVAL: case CONFIG_TYPE_MSEC_INTERVAL: case CONFIG_TYPE_UINT: + case CONFIG_TYPE_INT: case CONFIG_TYPE_PORT: case CONFIG_TYPE_BOOL: *(int*)lvalue = 0; @@ -7142,6 +7155,7 @@ getinfo_helper_config(control_connection_t *conn, case CONFIG_TYPE_STRING: type = "String"; break; case CONFIG_TYPE_FILENAME: type = "Filename"; break; case CONFIG_TYPE_UINT: type = "Integer"; break; + case CONFIG_TYPE_INT: type = "SignedInteger"; break; case CONFIG_TYPE_PORT: type = "Port"; break; case CONFIG_TYPE_INTERVAL: type = "TimeInterval"; break; case CONFIG_TYPE_MSEC_INTERVAL: type = "TimeMsecInterval"; break; diff --git a/src/or/or.h b/src/or/or.h index 7ff6284..3a53e5e 100644 --- a/src/or/or.h +++ b/src/or/or.h @@ -3550,6 +3550,17 @@ typedef struct { * control ports. */ int DisableNetwork; + /** + * Parameters for path-bias detection. + * @{ + */ + int PathBiasCircThreshold; + double PathBiasNoticeRate; + double PathBiasDisableRate; + int PathBiasScaleThreshold; + int PathBiasScaleFactor; + /** @} */ + } or_options_t; /** Persistent state for an onion router, as saved to disk. */