May 2018 - tor-commits - lists.torproject.org

[tor/maint-0.3.3] Check for "the right descriptor", not just "any descriptor".
by nickm＠torproject.org 27 May '18

27 May '18

commit 948dd2c79ea9ca1fd06c13f275515a1745c46986 Author: Nick Mathewson <nickm(a)torproject.org> Date: Mon Apr 16 10:38:55 2018 -0400 Check for "the right descriptor", not just "any descriptor". This patch adds a new node_has_preferred_descriptor() function, and replaces most users of node_has_descriptor() with it. That's an important change, since as of d1874b433953f64 (our fix for #25213), we are willing to say that a node has _some_ descriptor, but not the _right_ descriptor for a particular use case. Part of a fix for 25691 and 25692. --- src/or/circuitbuild.c | 28 ++++++++++++---------------- src/or/circuituse.c | 4 ++-- src/or/entrynodes.c | 7 ++++--- src/or/hs_common.c | 15 +++++++++++---- src/or/nodelist.c | 30 +++++++++++++++++++++++++++++- src/or/nodelist.h | 2 ++ src/or/rendservice.c | 2 +- 7 files changed, 61 insertions(+), 27 deletions(-) diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c index 5f1f8122f..019b9c51f 100644 --- a/src/or/circuitbuild.c +++ b/src/or/circuitbuild.c @@ -417,7 +417,7 @@ onion_populate_cpath(origin_circuit_t *circ) circ->cpath->extend_info->identity_digest); /* If we don't know the node and its descriptor, we must be bootstrapping. */ - if (!node || !node_has_descriptor(node)) { + if (!node || !node_has_preferred_descriptor(node, 1)) { return 0; } } @@ -1869,7 +1869,7 @@ choose_good_exit_server_general(int need_uptime, int need_capacity) */ continue; } - if (!node_has_descriptor(node)) { + if (!node_has_preferred_descriptor(node, 0)) { n_supported[i] = -1; continue; } @@ -2443,6 +2443,10 @@ circuit_extend_to_new_exit(origin_circuit_t *circ, extend_info_t *exit_ei) /** Return the number of routers in routers that are currently up * and available for building circuits through. + * + * (Note that this function may overcount or undercount, if we have + * descriptors that are not the type we would prefer to use for some + * particular router. See bug #25885.) */ MOCK_IMPL(STATIC int, count_acceptable_nodes, (smartlist_t *nodes)) @@ -2847,9 +2851,10 @@ extend_info_new(const char *nickname, * of the node (i.e. its IPv4 address) unless * for_direct_connect is true, in which case the preferred * address is used instead. May return NULL if there is not enough - * info about node to extend to it--for example, if there is no - * routerinfo_t or microdesc_t, or if for_direct_connect is true and none of - * the node's addresses are allowed by tor's firewall and IP version config. + * info about node to extend to it--for example, if the preferred + * routerinfo_t or microdesc_t is missing, or if for_direct_connect is + * true and none of the node's addresses is allowed by tor's firewall + * and IP version config. **/ extend_info_t * extend_info_from_node(const node_t *node, int for_direct_connect) @@ -2857,17 +2862,8 @@ extend_info_from_node(const node_t *node, int for_direct_connect) tor_addr_port_t ap; int valid_addr = 0; - const int is_bridge = node_is_a_configured_bridge(node); - const int we_use_mds = we_use_microdescriptors_for_circuits(get_options()); - - if ((is_bridge && for_direct_connect) || !we_use_mds) { - /* We need an ri in this case. */ - if (!node->ri) - return NULL; - } else { - /* Otherwise we need an md. */ - if (node->rs == NULL || node->md == NULL) - return NULL; + if (!node_has_preferred_descriptor(node, for_direct_connect)) { + return NULL; } /* Choose a preferred address first, but fall back to an allowed address. diff --git a/src/or/circuituse.c b/src/or/circuituse.c index 3125fff65..5d8af4c6c 100644 --- a/src/or/circuituse.c +++ b/src/or/circuituse.c @@ -2384,7 +2384,7 @@ circuit_get_open_circ_or_launch(entry_connection_t *conn, const node_t *r; int opt = conn->chosen_exit_optional; r = node_get_by_nickname(conn->chosen_exit_name, 0); - if (r && node_has_descriptor(r)) { + if (r && node_has_preferred_descriptor(r, conn->want_onehop ? 1 : 0)) { /* We might want to connect to an IPv6 bridge for loading descriptors so we use the preferred address rather than the primary. */ @@ -2394,7 +2394,7 @@ circuit_get_open_circ_or_launch(entry_connection_t *conn, "Discarding this circuit.", conn->chosen_exit_name); return -1; } - } else { /* ! (r && node_has_descriptor(r)) */ + } else { /* ! (r && node_has_preferred_descriptor(...)) */ log_debug(LD_DIR, "considering %d, %s", want_onehop, conn->chosen_exit_name); if (want_onehop && conn->chosen_exit_name[0] == '$') { diff --git a/src/or/entrynodes.c b/src/or/entrynodes.c index 2b6ff38c9..54638810f 100644 --- a/src/or/entrynodes.c +++ b/src/or/entrynodes.c @@ -185,14 +185,14 @@ should_apply_guardfraction(const networkstatus_t *ns) return options->UseGuardFraction; } -/** Return true iff we know a descriptor for guard */ +/** Return true iff we know a preferred descriptor for guard */ static int guard_has_descriptor(const entry_guard_t *guard) { const node_t *node = node_get_by_id(guard->identity); if (!node) return 0; - return node_has_descriptor(node); + return node_has_preferred_descriptor(node, 1); } /** @@ -2269,7 +2269,8 @@ entry_guard_pick_for_circuit(guard_selection_t *gs, // XXXX #20827 check Ed ID. if (! node) goto fail; - if (BUG(usage != GUARD_USAGE_DIRGUARD && !node_has_descriptor(node))) + if (BUG(usage != GUARD_USAGE_DIRGUARD && + !node_has_preferred_descriptor(node, 1))) goto fail; *chosen_node_out = node; diff --git a/src/or/hs_common.c b/src/or/hs_common.c index 6d97c8775..10b56c0ba 100644 --- a/src/or/hs_common.c +++ b/src/or/hs_common.c @@ -1280,8 +1280,10 @@ node_has_hsdir_index(const node_t *node) tor_assert(node_supports_v3_hsdir(node)); /* A node can't have an HSDir index without a descriptor since we need desc - * to get its ed25519 key */ - if (!node_has_descriptor(node)) { + * to get its ed25519 key. for_direct_connect should be zero, since we + * always use the consensus-indexed node's keys to build the hash ring, even + * if some of the consensus-indexed nodes are also bridges. */ + if (!node_has_preferred_descriptor(node, 0)) { return 0; } @@ -1612,12 +1614,17 @@ hs_pick_hsdir(smartlist_t *responsible_dirs, const char *req_key_str) hs_clean_last_hid_serv_requests(now); /* Only select those hidden service directories to which we did not send a - * request recently and for which we have a router descriptor here. */ + * request recently and for which we have a router descriptor here. + * + * Use for_direct_connect==0 even if we will be connecting to the node + * directly, since we always use the key information in the + * consensus-indexed node descriptors for building the index. + **/ SMARTLIST_FOREACH_BEGIN(responsible_dirs, routerstatus_t *, dir) { time_t last = hs_lookup_last_hid_serv_request(dir, req_key_str, 0, 0); const node_t *node = node_get_by_id(dir->identity_digest); if (last + hs_hsdir_requery_period(options) >= now || - !node || !node_has_descriptor(node)) { + !node || !node_has_preferred_descriptor(node, 0)) { SMARTLIST_DEL_CURRENT(responsible_dirs, dir); continue; } diff --git a/src/or/nodelist.c b/src/or/nodelist.c index 3a26aee61..2962d3cb4 100644 --- a/src/or/nodelist.c +++ b/src/or/nodelist.c @@ -43,6 +43,7 @@ #include "or.h" #include "address.h" #include "address_set.h" +#include "bridges.h" #include "config.h" #include "control.h" #include "dirserv.h" @@ -1139,6 +1140,32 @@ node_has_descriptor(const node_t *node) (node->rs && node->md)); } +/** Return true iff node has the kind of descriptor we would prefer to + * use for it, given our configuration and how we intend to use the node. + * + * If for_direct_connect is true, we intend to connect to the node + * directly, as the first hop of a circuit; otherwise, we intend to connect to + * it indirectly, or use it as if we were connecting to it indirectly. */ +int +node_has_preferred_descriptor(const node_t *node, + int for_direct_connect) +{ + const int is_bridge = node_is_a_configured_bridge(node); + const int we_use_mds = we_use_microdescriptors_for_circuits(get_options()); + + if ((is_bridge && for_direct_connect) || !we_use_mds) { + /* We need an ri in this case. */ + if (!node->ri) + return 0; + } else { + /* Otherwise we need an rs and an md. */ + if (node->rs == NULL || node->md == NULL) + return 0; + } + + return 1; +} + /** Return the router_purpose of node. */ int node_get_purpose(const node_t *node) @@ -2221,7 +2248,8 @@ compute_frac_paths_available(const networkstatus_t *consensus, nu); SMARTLIST_FOREACH_BEGIN(myexits_unflagged, const node_t *, node) { - if (node_has_descriptor(node) && node_exit_policy_rejects_all(node)) { + if (node_has_preferred_descriptor(node, 0) && + node_exit_policy_rejects_all(node)) { SMARTLIST_DEL_CURRENT(myexits_unflagged, node); /* this node is not actually an exit */ np--; diff --git a/src/or/nodelist.h b/src/or/nodelist.h index 043d7b341..5e7254f60 100644 --- a/src/or/nodelist.h +++ b/src/or/nodelist.h @@ -47,6 +47,8 @@ void node_get_verbose_nickname_by_id(const char *id_digest, char *verbose_name_out); int node_is_dir(const node_t *node); int node_has_descriptor(const node_t *node); +int node_has_preferred_descriptor(const node_t *node, + int for_direct_connect); int node_get_purpose(const node_t *node); #define node_is_bridge(node) \ (node_get_purpose((node)) == ROUTER_PURPOSE_BRIDGE) diff --git a/src/or/rendservice.c b/src/or/rendservice.c index cc2242977..1a93c3643 100644 --- a/src/or/rendservice.c +++ b/src/or/rendservice.c @@ -3596,7 +3596,7 @@ directory_post_to_hs_dir(rend_service_descriptor_t *renddesc, /* Don't upload descriptor if we succeeded in doing so last time. */ continue; node = node_get_by_id(hs_dir->identity_digest); - if (!node || !node_has_descriptor(node)) { + if (!node || !node_has_preferred_descriptor(node,0)) { log_info(LD_REND, "Not launching upload for for v2 descriptor to " "hidden service directory %s; we don't have its " "router descriptor. Queuing for later upload.",

1 0

[tor/maint-0.3.3] Rename node_has_descriptor() to node_has_any_descriptor()
by nickm＠torproject.org 27 May '18

27 May '18

commit 47163780c3682d881ad6e8044320a57fce439ea1 Author: Nick Mathewson <nickm(a)torproject.org> Date: Mon Apr 16 11:51:02 2018 -0400 Rename node_has_descriptor() to node_has_any_descriptor() Changing the name of this function should help keep us from misusing it when node_has_preferred_descriptor() would be more appropriate. --- src/or/circuitbuild.c | 2 +- src/or/control.c | 2 +- src/or/nodelist.c | 9 ++++++--- src/or/nodelist.h | 2 +- src/or/routerlist.c | 4 ++-- src/test/test_hs_common.c | 3 ++- 6 files changed, 13 insertions(+), 9 deletions(-) diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c index 96cc8369d..06aff0620 100644 --- a/src/or/circuitbuild.c +++ b/src/or/circuitbuild.c @@ -2468,7 +2468,7 @@ count_acceptable_nodes, (smartlist_t *nodes)) if (! node->is_valid) // log_debug(LD_CIRC,"Nope, the directory says %d is not valid.",i); continue; - if (! node_has_descriptor(node)) + if (! node_has_any_descriptor(node)) continue; /* The node has a descriptor, so we can just check the ntor key directly */ if (!node_has_curve25519_onion_key(node)) diff --git a/src/or/control.c b/src/or/control.c index fa62e9dbd..f87a0ca48 100644 --- a/src/or/control.c +++ b/src/or/control.c @@ -3498,7 +3498,7 @@ handle_control_extendcircuit(control_connection_t *conn, uint32_t len, connection_printf_to_buf(conn, "552 No such router \"%s\"\r\n", n); goto done; } - if (!node_has_descriptor(node)) { + if (!node_has_any_descriptor(node)) { connection_printf_to_buf(conn, "552 No descriptor for \"%s\"\r\n", n); goto done; } diff --git a/src/or/nodelist.c b/src/or/nodelist.c index 2962d3cb4..212606d2f 100644 --- a/src/or/nodelist.c +++ b/src/or/nodelist.c @@ -1131,10 +1131,13 @@ node_is_dir(const node_t *node) } } -/** Return true iff node has either kind of usable descriptor -- that - * is, a routerdescriptor or a microdescriptor. */ +/** Return true iff node has either kind of descriptor -- that + * is, a routerdescriptor or a microdescriptor. + * + * You should probably use node_has_preferred_descriptor() instead. + **/ int -node_has_descriptor(const node_t *node) +node_has_any_descriptor(const node_t *node) { return (node->ri || (node->rs && node->md)); diff --git a/src/or/nodelist.h b/src/or/nodelist.h index 5e7254f60..00f12ca1e 100644 --- a/src/or/nodelist.h +++ b/src/or/nodelist.h @@ -46,7 +46,7 @@ void node_get_verbose_nickname(const node_t *node, void node_get_verbose_nickname_by_id(const char *id_digest, char *verbose_name_out); int node_is_dir(const node_t *node); -int node_has_descriptor(const node_t *node); +int node_has_any_descriptor(const node_t *node); int node_has_preferred_descriptor(const node_t *node, int for_direct_connect); int node_get_purpose(const node_t *node); diff --git a/src/or/routerlist.c b/src/or/routerlist.c index 2ab5017b7..1bfbd9f67 100644 --- a/src/or/routerlist.c +++ b/src/or/routerlist.c @@ -2758,7 +2758,7 @@ frac_nodes_with_descriptors(const smartlist_t *sl, total <= 0.0) { int n_with_descs = 0; SMARTLIST_FOREACH(sl, const node_t *, node, { - if (node_has_descriptor(node)) + if (node_has_any_descriptor(node)) n_with_descs++; }); return ((double)n_with_descs) / (double)smartlist_len(sl); @@ -2766,7 +2766,7 @@ frac_nodes_with_descriptors(const smartlist_t *sl, present = 0.0; SMARTLIST_FOREACH_BEGIN(sl, const node_t *, node) { - if (node_has_descriptor(node)) + if (node_has_any_descriptor(node)) present += bandwidths[node_sl_idx]; } SMARTLIST_FOREACH_END(node); diff --git a/src/test/test_hs_common.c b/src/test/test_hs_common.c index 8c273c963..17ba11ca7 100644 --- a/src/test/test_hs_common.c +++ b/src/test/test_hs_common.c @@ -305,7 +305,8 @@ helper_add_hsdir_to_networkstatus(networkstatus_t *ns, node_t *node = node_get_mutable_by_id(ri->cache_info.identity_digest); tt_assert(node); node->rs = rs; - /* We need this to exist for node_has_descriptor() to return true. */ + /* We need this to exist for node_has_preferred_descriptor() to return + * true. */ node->md = tor_malloc_zero(sizeof(microdesc_t)); /* Do this now the nodelist_set_routerinfo() function needs a "rs" to set * the indexes which it doesn't have when it is called. */

1 0

[tor/maint-0.3.3] Repair the legacy_hs/pick_tor2web_rendezvous_node unit test
by nickm＠torproject.org 27 May '18

27 May '18

commit f1c1328f8518ad46f09d36ef3545a7ac266658eb Author: Nick Mathewson <nickm(a)torproject.org> Date: Mon Apr 16 11:52:57 2018 -0400 Repair the legacy_hs/pick_tor2web_rendezvous_node unit test It tried to pick nodes for which only routerinfo_t items are set, but without setting UseMicroDescriptors to 0. This won't work any more, now that we're strict about using the right descriptor types due to 25691/25692/25213. --- src/test/test_hs.c | 1 + 1 file changed, 1 insertion(+) diff --git a/src/test/test_hs.c b/src/test/test_hs.c index 9189bb65b..64448de51 100644 --- a/src/test/test_hs.c +++ b/src/test/test_hs.c @@ -361,6 +361,7 @@ test_pick_tor2web_rendezvous_node(void *arg) /* Parse Tor2webRendezvousPoints as a routerset. */ options->Tor2webRendezvousPoints = routerset_new(); + options->UseMicrodescriptors = 0; retval = routerset_parse(options->Tor2webRendezvousPoints, tor2web_rendezvous_str, "test_tor2web_rp");

1 0

[tor/maint-0.3.3] Merge remote-tracking branch 'public/bug25691_033_again_squashed' into maint-0.3.3
by nickm＠torproject.org 27 May '18

27 May '18

commit fa1890e97f19a444f8103c1207d7d18c02887b1f Merge: 0ef432d45 0941c8bfe Author: Nick Mathewson <nickm(a)torproject.org> Date: Sun May 27 10:03:11 2018 -0400 Merge remote-tracking branch 'public/bug25691_033_again_squashed' into maint-0.3.3 changes/bug25691_again | 6 +++++ src/or/circuitbuild.c | 67 ++++++++++++++++++++++++----------------------- src/or/circuituse.c | 4 +-- src/or/control.c | 9 ++++--- src/or/entrynodes.c | 7 ++--- src/or/hs_common.c | 15 ++++++++--- src/or/nodelist.c | 39 ++++++++++++++++++++++++--- src/or/nodelist.h | 4 ++- src/or/rendservice.c | 2 +- src/or/routerlist.c | 6 ++--- src/test/test_hs.c | 1 + src/test/test_hs_common.c | 3 ++- 12 files changed, 108 insertions(+), 55 deletions(-)

1 0

[tor/maint-0.3.3] Use router_crn_flags in more places, to pass direct-connect flag
by nickm＠torproject.org 27 May '18

27 May '18

commit 7915efd1b83e45c53eb06cfb384eed024df440c0 Author: Nick Mathewson <nickm(a)torproject.org> Date: Mon Apr 16 11:41:45 2018 -0400 Use router_crn_flags in more places, to pass direct-connect flag In order to fix 25691 and 25692, we need to pass the "direct_conn" flag to more places -- particularly when choosing single-hop tunnels. The right way to do this involves having a couple more functions accept router_crn_flags_t, rather than a big list of boolean arguments. This commit also makes sure that choose_good_exit_server_general() honors the direct_conn flag, to fix 25691 and 25692. --- src/or/circuitbuild.c | 39 ++++++++++++++++++++++----------------- 1 file changed, 22 insertions(+), 17 deletions(-) diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c index 019b9c51f..96cc8369d 100644 --- a/src/or/circuitbuild.c +++ b/src/or/circuitbuild.c @@ -1827,7 +1827,7 @@ ap_stream_wants_exit_attention(connection_t *conn) * Return NULL if we can't find any suitable routers. */ static const node_t * -choose_good_exit_server_general(int need_uptime, int need_capacity) +choose_good_exit_server_general(router_crn_flags_t flags) { int *n_supported; int n_pending_connections = 0; @@ -1837,6 +1837,9 @@ choose_good_exit_server_general(int need_uptime, int need_capacity) const or_options_t *options = get_options(); const smartlist_t *the_nodes; const node_t *selected_node=NULL; + const int need_uptime = (flags & CRN_NEED_UPTIME) != 0; + const int need_capacity = (flags & CRN_NEED_CAPACITY) != 0; + const int direct_conn = (flags & CRN_DIRECT_CONN) != 0; connections = get_connection_array(); @@ -1869,7 +1872,7 @@ choose_good_exit_server_general(int need_uptime, int need_capacity) */ continue; } - if (!node_has_preferred_descriptor(node, 0)) { + if (!node_has_preferred_descriptor(node, direct_conn)) { n_supported[i] = -1; continue; } @@ -1982,7 +1985,8 @@ choose_good_exit_server_general(int need_uptime, int need_capacity) need_capacity?", fast":"", need_uptime?", stable":""); tor_free(n_supported); - return choose_good_exit_server_general(0, 0); + flags &= ~(CRN_NEED_UPTIME|CRN_NEED_CAPACITY); + return choose_good_exit_server_general(flags); } log_notice(LD_CIRC, "All routers are down or won't exit%s -- " "choosing a doomed exit at random.", @@ -2229,17 +2233,11 @@ pick_restricted_middle_node(router_crn_flags_t flags, * toward the preferences in 'options'. */ static const node_t * -choose_good_exit_server(origin_circuit_t *circ, int need_uptime, - int need_capacity, int is_internal, int need_hs_v3) +choose_good_exit_server(origin_circuit_t *circ, + router_crn_flags_t flags, int is_internal) { const or_options_t *options = get_options(); - router_crn_flags_t flags = CRN_NEED_DESC; - if (need_uptime) - flags |= CRN_NEED_UPTIME; - if (need_capacity) - flags |= CRN_NEED_CAPACITY; - if (need_hs_v3) - flags |= CRN_RENDEZVOUS_V3; + flags |= CRN_NEED_DESC; switch (TO_CIRCUIT(circ)->purpose) { case CIRCUIT_PURPOSE_C_HSDIR_GET: @@ -2253,7 +2251,7 @@ choose_good_exit_server(origin_circuit_t *circ, int need_uptime, if (is_internal) /* pick it like a middle hop */ return router_choose_random_node(NULL, options->ExcludeNodes, flags); else - return choose_good_exit_server_general(need_uptime,need_capacity); + return choose_good_exit_server_general(flags); case CIRCUIT_PURPOSE_C_ESTABLISH_REND: { /* Pick a new RP */ @@ -2378,15 +2376,22 @@ onion_pick_cpath_exit(origin_circuit_t *circ, extend_info_t *exit_ei, extend_info_describe(exit_ei)); exit_ei = extend_info_dup(exit_ei); } else { /* we have to decide one */ + router_crn_flags_t flags = CRN_NEED_DESC; + if (state->need_uptime) + flags |= CRN_NEED_UPTIME; + if (state->need_capacity) + flags |= CRN_NEED_CAPACITY; + if (is_hs_v3_rp_circuit) + flags |= CRN_RENDEZVOUS_V3; + if (state->onehop_tunnel) + flags |= CRN_DIRECT_CONN; const node_t *node = - choose_good_exit_server(circ, state->need_uptime, - state->need_capacity, state->is_internal, - is_hs_v3_rp_circuit); + choose_good_exit_server(circ, flags, state->is_internal); if (!node) { log_warn(LD_CIRC,"Failed to choose an exit server"); return -1; } - exit_ei = extend_info_from_node(node, 0); + exit_ei = extend_info_from_node(node, state->onehop_tunnel); if (BUG(exit_ei == NULL)) return -1; }

1 0

[torspec/master] mesh vanguards is now prop292
by nickm＠torproject.org 27 May '18

27 May '18

commit e541f2afe53cb25f7199f91c5f9d6dda5d25e036 Author: Nick Mathewson <nickm(a)torproject.org> Date: Sun May 27 09:59:24 2018 -0400 mesh vanguards is now prop292 --- proposals/000-index.txt | 6 ++++-- proposals/{xxx-mesh-vanguards.txt => 292-mesh-vanguards.txt} | 4 ++-- 2 files changed, 6 insertions(+), 4 deletions(-) diff --git a/proposals/000-index.txt b/proposals/000-index.txt index 787928b..b70e998 100644 --- a/proposals/000-index.txt +++ b/proposals/000-index.txt @@ -167,7 +167,7 @@ Proposals by number: 244 Use RFC5705 Key Exporting in our AUTHENTICATE calls [CLOSED] 245 Deprecating and removing the TAP circuit extension protocol [DRAFT] 246 Merging Hidden Service Directories and Introduction Points [NEEDS-RESEARCH] -247 Defending Against Guard Discovery Attacks using Vanguards [DRAFT] +247 Defending Against Guard Discovery Attacks using Vanguards [SUPERSEDED] 248 Remove all RSA identity keys [DRAFT] 249 Allow CREATE cells with >505 bytes of handshake data [ACCEPTED] 250 Random Number Generation During Tor Voting [CLOSED] @@ -212,6 +212,7 @@ Proposals by number: 289 Authenticating sendme cells to mitigate bandwidth attacks [OPEN] 290 Continuously update consensus methods [OPEN] 291 The move to two guard nodes [OPEN] +292 Mesh-based vanguards [OPEN] Proposals by status: @@ -224,7 +225,6 @@ Proposals by status: 239 Consensus Hash Chaining 240 Early signing key revocation for directory authorities 245 Deprecating and removing the TAP circuit extension protocol - 247 Defending Against Guard Discovery Attacks using Vanguards 248 Remove all RSA identity keys 253 Out of Band Circuit HMACs 254 Padding Negotiation @@ -272,6 +272,7 @@ Proposals by status: 289 Authenticating sendme cells to mitigate bandwidth attacks 290 Continuously update consensus methods 291 The move to two guard nodes + 292 Mesh-based vanguards ACCEPTED: 172 GETINFO controller option for circuit information 173 GETINFO Option Expansion @@ -393,6 +394,7 @@ Proposals by status: 194 Mnemonic .onion URLs 210 Faster Headless Consensus Bootstrapping 225 Strawman proposal: commit-and-reveal shared rng + 247 Defending Against Guard Discovery Attacks using Vanguards 252 Single Onion Services 266 Removing current obsolete clients from the Tor network 280 Privacy-Preserving Statistics with Privcount in Tor diff --git a/proposals/xxx-mesh-vanguards.txt b/proposals/292-mesh-vanguards.txt similarity index 99% rename from proposals/xxx-mesh-vanguards.txt rename to proposals/292-mesh-vanguards.txt index 7a47e0b..c488138 100644 --- a/proposals/xxx-mesh-vanguards.txt +++ b/proposals/292-mesh-vanguards.txt @@ -1,8 +1,8 @@ -Filename: xxx-mesh-vanguards.txt +Filename: 292-mesh-vanguards.txt Title: Mesh-based vanguards Authors: George Kadianakis and Mike Perry Created: 2018-05-08 -Status: Draft +Status: Open Supersedes: 247 0. Motivation

1 0

[torspec/master] Prop 247: Some notes from mailinglist discussion
by nickm＠torproject.org 27 May '18

27 May '18

commit d0bbdb3ccb19f1821670f6684eaf1c609281f2e8 Author: Mike Perry <mikeperry-git(a)torproject.org> Date: Wed Jan 27 13:47:24 2016 -0800 Prop 247: Some notes from mailinglist discussion --- proposals/247-hs-guard-discovery.txt | 35 +++++++++++++++++++++++++++++++++-- 1 file changed, 33 insertions(+), 2 deletions(-) diff --git a/proposals/247-hs-guard-discovery.txt b/proposals/247-hs-guard-discovery.txt index 51e5248..99b196c 100644 --- a/proposals/247-hs-guard-discovery.txt +++ b/proposals/247-hs-guard-discovery.txt @@ -103,6 +103,25 @@ Status: Draft Each node's rotation time is tracked independently, to avoid disclosing the rotation times of the primary and second-level guards. + XXX: IP and RP actually need to be separate 4th hops. On the server side, + IP should be separate to better unlink IP from the 3rd layer guards, + and on the client side, the RP needs to come from the full network to + avoid cross-visit linkability. So it's seven proxies all teh time... + + XXX: What about hsdir fetch? to avoid targeting and visit linkability, + it needs an emphemeral hop too.. Unless we believe that linkability is low? + It is lower than IP linkability, since the hsdescs can be cached for a bit. + But if we are worried about visit linkability, then client should also add + an extra ephemeral hop during IP visits, making that circuit 8 hops long... + + XXX: Emphemeral hops for service side before RP? + + XXX: Really crazy idea: We can provide multiple path security levels. + We could have full 4 hops, or combine Layer2+Layer3, or combine Layer1+Layer2 + and Layer3+Layer4 for lower-security HS circs.. + + XXX: update the load balancing proposal with the outcome of this :/ + XXX how should proposal 241 ("Resisting guard-turnover attacks") be applied here? @@ -504,6 +523,14 @@ Status: Draft be used for the second and third-level nodes at all, and to allow the primary guard to be chosen as a rend point. + XXX: Dgoulet suggested using arbitrary subsets here rather than the + no Guard-flag restriction, esp since Layer2 inference is still a + possibility. + + XXX: If a Guard-flagged node is chosen for the alls IP or RP, raise + protocolerror. Refuse connection. Or allow our guard/other nodes in + IP/RP.. + Additionally, in order to further limit the exposure of secondary guards to sybil attacks, the bin position of the third-level guards should be stable over long periods of time. When choosing third-level guards, these @@ -517,8 +544,8 @@ Status: Draft 4.4. Denial of service Since it will be fairly trivial for the adversary to enumerate the - current set of rend nodes for a hidden service, denial of service - becomes a serious risk for Vanguard users. + current set of third-layer guards for a hidden service, denial of + service becomes a serious risk for Vanguard users. For this reason, it is important to support a large number of third-level guards, to increase the amount of resources required to @@ -532,6 +559,10 @@ Status: Draft unwise to simply replace unresponsive third-level guards that fail to complete circuits, as this will accelerate the Sybil attack. +4.5. Path Bias + +XXX: Re-use Prop#259 here. + 5. Performance considerations

1 0

[torspec/master] Supersede proposal 247 by xxx-mesh-vanguards.txt.
by nickm＠torproject.org 27 May '18

27 May '18

commit 5bf8980bb8e88ba6cf3b2e3131dfa48cd0ec064c Author: George Kadianakis <desnacked(a)riseup.net> Date: Thu May 24 12:37:39 2018 +0300 Supersede proposal 247 by xxx-mesh-vanguards.txt. We need to update the xxx part when we give a number to the new proposal. --- proposals/247-hs-guard-discovery.txt | 6 +++++- proposals/xxx-mesh-vanguards.txt | 2 ++ 2 files changed, 7 insertions(+), 1 deletion(-) diff --git a/proposals/247-hs-guard-discovery.txt b/proposals/247-hs-guard-discovery.txt index 99b196c..a07b459 100644 --- a/proposals/247-hs-guard-discovery.txt +++ b/proposals/247-hs-guard-discovery.txt @@ -2,7 +2,11 @@ Filename: 247-hs-guard-discovery.txt Title: Defending Against Guard Discovery Attacks using Vanguards Authors: George Kadianakis and Mike Perry Created: 2015-07-10 -Status: Draft +Status: Superseded +Superseded-by: xxx-mesh-vanguards.txt + +[This proposal is superseded by proposal xxx-mesh-vanguards.txt based on our +analysis and experiences while implementing and simulating the vanguard design.] 0. Motivation diff --git a/proposals/xxx-mesh-vanguards.txt b/proposals/xxx-mesh-vanguards.txt index 86a74ad..7a47e0b 100644 --- a/proposals/xxx-mesh-vanguards.txt +++ b/proposals/xxx-mesh-vanguards.txt @@ -1,7 +1,9 @@ +Filename: xxx-mesh-vanguards.txt Title: Mesh-based vanguards Authors: George Kadianakis and Mike Perry Created: 2018-05-08 Status: Draft +Supersedes: 247 0. Motivation

1 0

[torspec/master] Write a proposal for the mesh vanguards design.
by nickm＠torproject.org 27 May '18

27 May '18

commit d4aaf28eb3a3ae9f60996d97ed6bf21153cc7601 Author: Mike Perry <mikeperry-git(a)torproject.org> Date: Tue May 8 21:14:43 2018 +0000 Write a proposal for the mesh vanguards design. --- proposals/xxx-mesh-vanguards.txt | 528 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 528 insertions(+) diff --git a/proposals/xxx-mesh-vanguards.txt b/proposals/xxx-mesh-vanguards.txt new file mode 100644 index 0000000..86a74ad --- /dev/null +++ b/proposals/xxx-mesh-vanguards.txt @@ -0,0 +1,528 @@ +Title: Mesh-based vanguards +Authors: George Kadianakis and Mike Perry +Created: 2018-05-08 +Status: Draft + +0. Motivation + + A guard discovery attack allows attackers to determine the guard + node of a Tor client. The hidden service rendezvous protocol + provides an attack vector for a guard discovery attack since anyone + can force an HS to construct a 3-hop circuit to a relay (#9001). + + Following the guard discovery attack with a compromise and/or + coercion of the guard node can lead to the deanonymization of a + hidden service. + +1. Overview + + This document tries to make the above guard discovery + compromise + attack harder to launch. It introduces a configuration + option which makes the hidden service also pin the second and third + hops of its circuits for a longer duration. + + With this new path selection, we force the adversary to perform a + Sybil attack and two compromise attacks before succeeding. This is + an improvement over the current state where the Sybil attack is + trivial to pull off, and only a single compromise attack is required. + + With this new path selection, an attacker is forced to do a one or + more node compromise attacks before learning the guard node of a hidden + service. This increases the uncertainty of the attacker, since + compromise attacks are costly and potentially detectable, so an + attacker will have to think twice before beginning a chain of node + compromise attacks that they might not be able to complete. + +1.1. Tor integration + + The mechanisms introduced in this proposal are currently implemented + partially in Tor and partially through an external Python script: + https://github.com/mikeperry-tor/vanguards + + The Python script uses the new Tor configuration options HSLayer2Nodes and + HSLayer3Nodes to be able to select nodes for the guard layers. The Python + script is tasked with maintaining and rotating the guard nodes as needed + based on the lifetimes described in this proposal. + + In the future, we are aiming to include the whole functionality into Tor, + with no need for external scripts. + +1.2. Visuals + + Here is how a hidden service rendezvous circuit currently looks like: + + -> middle_1 -> middle_A + -> middle_2 -> middle_B + -> middle_3 -> middle_C + -> middle_4 -> middle_D + HS -> guard -> middle_5 -> middle_E + -> middle_6 -> middle_F + -> middle_7 -> middle_G + -> middle_8 -> middle_H + -> ... -> ... + -> middle_n -> middle_n + + this proposal pins the two middle positions into a much more + restricted sets, as follows: + + -> guard_2A + -> guard_3A + -> guard_1A -> guard_2B -> guard_3B + HS -> guard_3C + -> guard_1B -> guard_2C -> guard_3D + -> guard_3E + -> guard_2D -> guard_3F + + Additionally, to avoid linkability, we insert an extra middle node + after the third layer guard for client side intro and hsdir circuits, + and service-side rendezvous circuits. This means that the set of + paths for Client (C) and Service (S) side look like this: + + C - G - L2 - L3 - R + S - G - L2 - L3 - HSDIR + S - G - L2 - L3 - I + C - G - L2 - L3 - M - I + C - G - L2 - L3 - M - HSDIR + S - G - L2 - L3 - M - R + +1.3. Threat model, Assumptions, and Goals + + Consider an adversary with the following powers: + + - Can launch a Sybil guard discovery attack against any node of a + rendezvous circuit. The slower the rotation period of the node, + the longer the attack takes. Similarly, the higher the percentage + of the network is compromised, the faster the attack runs. + + - Can compromise any node on the network, but this compromise takes + time and potentially even coercive action, and also carries risk + of discovery. + + We also make the following assumptions about the types of attacks: + + 1. A Sybil attack is observable by both people monitoring the network + for large numbers of new nodes, as well as vigilant hidden service + operators. It will require either large amounts of traffic sent + towards the hidden service, multiple test circuits, or both. + + 2. A Sybil attack against the second or first layer Guards will be + more noisy than a Sybil attack against the third layer guard, since the + second and first layer Sybil attack requires a timing side channel in + order to determine success, whereas the Sybil success is almost + immediately obvious to third layer guard, since it will be instructed + to connect to a cooperating malicious rend point by the adversary. + + 3. As soon as the adversary is confident they have won the Sybil attack, + an even more aggressive circuit building attack will allow them to + determine the next node very fast (an hour or less). + + 4. The adversary is strongly disincentivized from compromising nodes that + may prove useless, as node compromise is even more risky for the + adversary than a Sybil attack in terms of being noticed. + + Given this threat model, our security parameters were selected so that + the first two layers of guards should be hard to attack using a Sybil + guard discovery attack and hence require a node compromise attack. Ideally, + we want the node compromise attacks to carry a non-negligible probability of + being useless to the adversary by the time they complete. + + On the other hand, the outermost layer of guards should rotate fast enough to + _require_ a Sybil attack. + + See our vanguard simulator project for a simulation of the above adversary + model and a motivation for the parameters selected within this proposal: + https://github.com/asn-d6/vanguard_simulator + https://github.com/asn-d6/vanguard_simulator/wiki/Optimizing-vanguard-topol… + + +2. Design + + When a hidden service picks its guard nodes, it also picks an + additional NUM_LAYER2_GUARDS-sized set of middle nodes for its + `second_guard_set`, as well as a NUM_LAYER3_GUARDS-sized set of + middle nodes for its `third_guard_set`. + + When a hidden service needs to establish a circuit to an HSDir, + introduction point or a rendezvous point, it uses nodes from + `second_guard_set` as the second hop of the circuit and nodes from + `third_guard_set` as third hop of the circuit. + + A hidden service rotates nodes from the 'second_guard_set' at a random + time between MIN_SECOND_GUARD_LIFETIME hours and + MAX_SECOND_GUARD_LIFETIME hours. + + A hidden service rotates nodes from the 'third_guard_set' at a random + time between MIN_THIRD_GUARD_LIFETIME and MAX_THIRD_GUARD_LIFETIME + hours. + + Each node's rotation time is tracked independently, to avoid disclosing + the rotation times of the primary and second-level guards. + +2.1. Security parameters + + We set NUM_LAYER2_GUARDS to 4 nodes and NUM_LAYER3_GUARDS to 6 nodes. + + We set MIN_SECOND_GUARD_LIFETIME to 1 day, and MAX_SECOND_GUARD_LIFETIME + to 45 days inclusive, for an average rotation rate of 29.5 days, using + the max(X,X) distribution specified in Section 3.3. + + We set MIN_THIRD_GUARD_LIFETIME to 1 hour, and MAX_THIRD_GUARD_LIFETIME + to 48 hours inclusive, for an average rotation rate of 31.5 hours, using + the max(X,X) distribution specified in Section 3.3. + + See Section 3 for more analysis on these constants. + +2.2. Path restriction changes + + In order to avoid information leaks and ensure paths can be built, path + restrictions must be loosened. + + In particular, we allow the following: + 1. Nodes from the same /16 and same family for any/all hops + 2. Guard nodes can be chosen for RP/IP/HSDIR + 3. Guard nodes can be chosen for hop before RP/IP/HSDIR. + + The first change prevents the situation where paths cannot be built if two + layers all share the same subnet and/or node family. It also prevents the + the use of a different entry guard based on the family or subnet of the + IP, HSDIR, or RP. + + The second change prevents an adversary from forcing the use of a different + entry guard by enumerating all guard-flaged nodes as the RP. + + The third change prevents an adversary from learning the guard node by way + of noticing which nodes were not chosen for the hop before it. + + +3. Rationale and Security Parameter Selection + +3.1. Sybil rotation counts for a given number of Guards + + The probability of Sybil success for Guard discovery can be modeled as + the probability of choosing 1 or more malicious middle nodes for a + sensitive circuit over some period of time. + + P(At least 1 bad middle) = 1 - P(All Good Middles) + = 1 - P(One Good middle)^(num_middles) + = 1 - (1 - c/n)^(num_middles) + + c/n is the adversary compromise percentage + + In the case of Vanguards, num_middles is the number of Guards you rotate + through in a given time period. This is a function of the number of vanguards + in that position (v), as well as the number of rotations (r). + + P(At least one bad middle) = 1 - (1 - c/n)^(v*r) + + Here's detailed tables in terms of the number of rotations required for + a given Sybil success rate for certain number of guards. + + 1.0% Network Compromise: + Sybil Success One Two Three Four Five Six Eight Nine Ten Twelve Sixteen + 10% 11 6 4 3 3 2 2 2 2 1 1 + 15% 17 9 6 5 4 3 3 2 2 2 2 + 25% 29 15 10 8 6 5 4 4 3 3 2 + 50% 69 35 23 18 14 12 9 8 7 6 5 + 60% 92 46 31 23 19 16 12 11 10 8 6 + 75% 138 69 46 35 28 23 18 16 14 12 9 + 85% 189 95 63 48 38 32 24 21 19 16 12 + 90% 230 115 77 58 46 39 29 26 23 20 15 + 95% 299 150 100 75 60 50 38 34 30 25 19 + 99% 459 230 153 115 92 77 58 51 46 39 29 + + 5.0% Network Compromise: + Sybil Success One Two Three Four Five Six Eight Nine Ten Twelve Sixteen + 10% 3 2 1 1 1 1 1 1 1 1 1 + 15% 4 2 2 1 1 1 1 1 1 1 1 + 25% 6 3 2 2 2 1 1 1 1 1 1 + 50% 14 7 5 4 3 3 2 2 2 2 1 + 60% 18 9 6 5 4 3 3 2 2 2 2 + 75% 28 14 10 7 6 5 4 4 3 3 2 + 85% 37 19 13 10 8 7 5 5 4 4 3 + 90% 45 23 15 12 9 8 6 5 5 4 3 + 95% 59 30 20 15 12 10 8 7 6 5 4 + 99% 90 45 30 23 18 15 12 10 9 8 6 + + 10.0% Network Compromise: + Sybil Success One Two Three Four Five Six Eight Nine Ten Twelve Sixteen + 10% 2 1 1 1 1 1 1 1 1 1 1 + 15% 2 1 1 1 1 1 1 1 1 1 1 + 25% 3 2 1 1 1 1 1 1 1 1 1 + 50% 7 4 3 2 2 2 1 1 1 1 1 + 60% 9 5 3 3 2 2 2 1 1 1 1 + 75% 14 7 5 4 3 3 2 2 2 2 1 + 85% 19 10 7 5 4 4 3 3 2 2 2 + 90% 22 11 8 6 5 4 3 3 3 2 2 + 95% 29 15 10 8 6 5 4 4 3 3 2 + 99% 44 22 15 11 9 8 6 5 5 4 3 + + The rotation counts in these tables were generated with: + def num_rotations(c, v, success): + r = 0 + while 1-math.pow((1-c), v*r) < success: r += 1 + return r + +3.2. Rotation Period + + As specified in Section 1.2, the primary driving force for the third + layer selection was to ensure that these nodes rotate fast enough that + it is not worth trying to compromise them, because it is unlikely for + compromise to succeed and yield useful information before the nodes stop + being used. + + From the table in Section 3.1, with NUM_LAYER2_GUARDS=4 and + NUM_LAYER3_GUARDS=6, it can be seen that this means that the Sybil attack + on layer3 will complete with 50% chance in 12*31.5 hours (15.75 days) + for the 1% adversary, ~4 days for the 5% adversary, and 2.62 days for the + 10% adversary. + + Since rotation of each node happens independently, the distribution of + when the adversary expects to win this Sybil attack in order to discover + the next node up is uniform. This means that on average, the adversary + should expect that half of the rotation period of the next node is already + over by the time that they win the Sybil. + + With this fact, we choose our range and distribution for the second + layer rotation to be short enough to cause the adversary to risk + compromising nodes that are useless, yet long enough to require a + Sybil attack to be noticeable in terms of client activity. For this + reason, we choose a minimum second-layer guard lifetime of 1 day, + since this gives the adversary a minimum expected value of 12 hours for + during which they can compromise a guard before it might be rotated. + If the total expected rotation rate is 29.5 days, then the adversary can + expect overall to have 14.75 days remaining after completing their Sybil + attack before a second-layer guard rotates away. + +3.3. Rotation distributions + + In order to skew the distribution of the third layer guard towards + higher values, we use max(X,X) for the distribution, where X is a + random variable that takes on values from the uniform distribution. + + Here's a table of expectation (arithmetic means) for relevant + ranges of X (sampled from 0..N-1). The table was generated with the + following python functions: + + def ProbMinXX(N, i): return (2.0*(N-i)-1)/(N*N) + def ProbMaxXX(N, i): return (2.0*i+1)/(N*N) + + def ExpFn(N, ProbFunc): + exp = 0.0 + for i in xrange(N): exp += i*ProbFunc(N, i) + return exp + + The current choice for second-layer guards is noted with **, and + the current choice for third-layer guards is noted with ***. + + Range Min(X,X) Max(X,X) + 40 12.84 26.16 + 41 13.17 26.83 + 42 13.50 27.50 + 43 13.84 28.16 + 44 14.17 28.83 + 45 14.50 29.50** + 46 14.84 30.16 + 47 15.17 30.83 + 48 15.50 31.50*** + + The Cumulative Density Function (CDF) tells us the probability that a + guard will no longer be in use after a given number of time units have + passed. + + Because the Sybil attack on the third node is expected to complete at any + point in the second node's rotation period with uniform probability, if we + want to know the probability that a second-level Guard node will still be in + use after t days, we first need to compute the probability distribution of + the rotation duration of the second-level guard at a uniformly random point + in time. Let's call this P(R=r). + + For P(R=r), the probability of the rotation duration depends on the selection + probability of a rotation duration, and the fraction of total time that + rotation is likely to be in use. This can be written as: + + P(R=r) = ProbMaxXX(X=r)*r / \sum_{i=1}^N ProbMaxXX(X=i)*i + + or in Python: + + def ProbR(N, r, ProbFunc=ProbMaxXX): + return ProbFunc(N, r)*r/ExpFn(N, ProbFunc) + + For the full CDF, we simply sum up the fractional probability density for + all rotation durations. For rotation durations less than t days, we add the + entire probability mass for that period to the density function. For + durations d greater than t days, we take the fraction of that rotation + period's selection probability and multiply it by t/d and add it to the + density. In other words: + + def FullCDF(N, t, ProbFunc=ProbR): + density = 0.0 + for d in xrange(N): + if t >= d: density += ProbFunc(N, d) + # The +1's below compensate for 0-indexed arrays: + else: density += ProbFunc(N, d)*(float(t+1))/(d+1) + return density + + Computing this yields the following distribution for our current parameters: + + t P(SECOND_ROTATION <= t) + 1 0.03247 + 2 0.06494 + 3 0.09738 + 4 0.12977 + 5 0.16207 + 10 0.32111 + 15 0.47298 + 20 0.61353 + 25 0.73856 + 30 0.84391 + 35 0.92539 + 40 0.97882 + 45 1.00000 + + This CDF tells us that for the second-level Guard rotation, the + adversary can expect that 3.3% of the time, their third-level Sybil + attack will provide them with a second-level guard node that has only + 1 day remaining before it rotates. 6.5% of the time, there will + be only 2 day or less remaining, and 9.7% of the time, 3 days or less. + + Note that this distribution is still a day-resolution approximation. + + +4. Security concerns and mitigations + +4.1. Mitigating fingerprinting of new HS circuits + + By pinning the middle nodes of rendezvous circuits, we make it + easier for all hops of the circuit to detect that they are part of a + special hidden service circuit with varying degrees of certainty. + + The Guard node is able to recognize a Vanguard client with a high + degree of certainty because it will observe a client IP creating the + overwhelming majority of its circuits to just a few middle nodes in + any given 31.5 day time period. + + The middle nodes will be able to tell with a variable certainty that + depends on both its traffic volume and upon the popularity of the + service, because they will see a large number of circuits that tend to + pick the same Guard and Exit. + + The final nodes will be able to tell with a similar level of certainty + that depends on their capacity and the service popularity, because they + will see a lot of handshakes that all tend to have the same second + hops. + + The most serious of these is the Guard fingerprinting issue. When + proposal 254-padding-negotiation is implemented, services that enable + this feature should use those padding primitives to create fake circuits + to random middle nodes that are not their guards, in an attempt to look + more like a client. + + Additionally, if Tor Browser implements "virtual circuits" based on + SOCKS username+password isolation in order to enforce the re-use of + paths when SOCKS username+passwords are re-used, then the number of + middle nodes in use during a typical user's browsing session will be + proportional to the number of sites they are viewing at any one time. + This is likely to be much lower than one new middle node every ten + minutes, and for some users, may be close to the number of Vanguards + we're considering. + + This same reasoning is also an argument for increasing the number of + second-level guards beyond just two, as it will spread the hidden + service's traffic over a wider set of middle nodes, making it both + easier to cover, and behave closer to a client using SOCKS virtual + circuit isolation. + +5. Default vs optional behavior + + We suggest this torrc option to be optional because it changes path + selection in a way that may seriously impact hidden service performance, + especially for high traffic services that happen to pick slow guard + nodes. + + However, by having this setting be disabled by default, we make hidden + services who use it stand out a lot. For this reason, we should in fact + enable this feature globally, but only after we verify its viability for + high-traffic hidden services, and ensure that it is free of second-order + load balancing effects. + + Even after that point, until Single Onion Services are implemented, + there will likely still be classes of very high traffic hidden services + for whom some degree of location anonymity is desired, but for which + performance is much more important than the benefit of Vanguards, so there + should always remain a way to turn this option off. + + In the meantime, a reference implementation is available at: + https://github.com/mikeperry-tor/vanguards/blob/master/vanguards/vanguards.… + + +Appendix A: Full Python program for generating tables in this proposal + +#!/usr/bin/python +import math + +############ Section 3.1 ################# +def num_rotations(c, v, success): + i = 0 + while 1-math.pow((1-c), v*i) < success: i += 1 + return i + +def rotation_line(c, pct): + print " %2d%% %6d%6d%6d%6d%6d%6d%6d%6d%6d%6d%8d" % \ + (pct, num_rotations(c, 1, pct/100.0), num_rotations(c, 2, pct/100.0), \ + num_rotations(c, 3, pct/100.0), num_rotations(c, 4, pct/100.0), + num_rotations(c, 5, pct/100.0), num_rotations(c, 6, pct/100.0), + num_rotations(c, 8, pct/100.0), num_rotations(c, 9, pct/100.0), + num_rotations(c, 10, pct/100.0), num_rotations(c, 12, pct/100.0), + num_rotations(c, 16, pct/100.0)) + +def rotation_table_31(): + for c in [1,5,10]: + print "\n %2.1f%% Network Compromise: " % c + print " Sybil Success One Two Three Four Five Six Eight Nine Ten Twelve Sixteen" + for success in [10,15,25,50,60,75,85,90,95,99]: + rotation_line(c/100.0, success) + +############ Section 3.3 ################# +def ProbMinXX(N, i): return (2.0*(N-i)-1)/(N*N) +def ProbMaxXX(N, i): return (2.0*i+1)/(N*N) + +def ExpFn(N, ProbFunc): + exp = 0.0 + for i in xrange(N): exp += i*ProbFunc(N, i) + return exp + +def ProbUniformX(N, i): return 1.0/N + +def ProbR(N, r, ProbFunc=ProbMaxXX): + return ProbFunc(N, r)*r/ExpFn(N, ProbFunc) + +def FullCDF(N, t, ProbFunc=ProbR): + density = 0.0 + for d in xrange(N): + if t >= d: density += ProbFunc(N, d) + # The +1's below compensate for 0-indexed arrays: + else: density += ProbFunc(N, d)*float(t+1)/(d+1) + return density + +def expectation_table_33(): + print "\n Range Min(X,X) Max(X,X)" + for i in xrange(10,49): + print " %2d %2.2f %2.2f" % (i, ExpFn(i,ProbMinXX), ExpFn(i, ProbMaxXX)) + +def CDF_table_33(): + print "\n t P(SECOND_ROTATION <= t)" + for i in xrange(1,46): + print " %2d %2.5f" % (i, FullCDF(45, i-1)) + +########### Output ############ + +# Section 3.1 +rotation_table_31() + +# Section 3.3 +expectation_table_33() +CDF_table_33() + +---------------------- + +1. https://onionbalance.readthedocs.org/en/latest/design.html#overview

1 0

[torspec/master] Prop 265: Add nodes from mailinglist discussion.
by nickm＠torproject.org 27 May '18

27 May '18

commit a19d0bf1f05e1108805cfeec8a545d6ee85cb399 Author: Mike Perry <mikeperry-git(a)torproject.org> Date: Fri Jan 15 08:53:47 2016 -0800 Prop 265: Add nodes from mailinglist discussion. --- proposals/265-load-balancing-with-overhead.txt | 25 +++++++++++++++++++++---- 1 file changed, 21 insertions(+), 4 deletions(-) diff --git a/proposals/265-load-balancing-with-overhead.txt b/proposals/265-load-balancing-with-overhead.txt index 4bf42a6..e79d0a1 100644 --- a/proposals/265-load-balancing-with-overhead.txt +++ b/proposals/265-load-balancing-with-overhead.txt @@ -181,13 +181,12 @@ proposal. The final condition that we need to ensure is that these weight values never become negative or greater than 1.0[3]. - 3.1. Ensuring against underflow and overflow Note that if M_o = G_o = 0, then the solutions and the overflow conditions are the same as in Section 2. -Unfortunately, SimPy is unable to solve multivariate inequalities, which +Unfortunately, SymPy is unable to solve multivariate inequalities, which prevents us from directly deriving overflow conditions for each variable independently (at least easily and without mistakes). Wolfram Alpha is able to derive closed form solutions to some degree for this, but they @@ -243,13 +242,28 @@ easier to pinpoint the source of any potential overflow issues. This separation will also enable us to potentially govern padding's contribution to the overhead via a single tunable value. -4.2 Integration with Guardfraction +4.2. Accounting for hidden service overhead with Prop 247 + +XXX: Hidden service path selection and 247 complicates this. With 247, we +want paths only of G M M, where the Ms exclude Guard-flaged nodes. This means +that M_o needs to add the total hidden service *network bytecount* overhead +(2X the hidden service end-to-end traffic bytecount). We also need to +*subtract* 4*Wmg*hs_e2e_bytecount from the G_o overhead, to account for not using +Guard-flagged nodes for the four M's in full prop-247 G M M M M G circuits. + +4.3. Accounting for RSOS overhead + +XXX: We also need to separately account for RSOS (and maybe SOS?) path usage +in M_o. This will require separate acocunting for these service types in +extra-info descriptors. + +4.4 Integration with Guardfraction The GuardFraction changes in Proposal 236 and #16255 should continue to work with these new equations, so long as the total T, G, and M values are counted after the GuardFraction multiplier has been applied. -4.3. Guard flag assignment +4.5. Guard flag assignment Ideally, the Guard flag assignment process would also not count Exit-flagged nodes when determining the Guard flag uptime and bandwidth @@ -258,6 +272,9 @@ nodes at all when this change is applied. This will result in more accurate thresholds for Guard node status, as well as better control over the true total amount of Guard bandwidth in the consensus. +4.6. Cannibalization + +XXX: It sucks and complicates everything. kill it, except for hsdirs. 1. https://trac.torproject.org/projects/tor/ticket/16255

1 0