March 2016 - tor-commits - lists.torproject.org

[tor/maint-0.2.7] Assert that dircollator is collated when we're reading its output.
by nickm＠torproject.org 21 Mar '16

21 Mar '16

commit beef6ed45160f096815b4ea840ff671fb484d1da Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Mar 15 10:24:18 2016 -0400 Assert that dircollator is collated when we're reading its output. Fix for 17668.S2. --- src/or/dircollate.c | 2 ++ 1 file changed, 2 insertions(+) diff --git a/src/or/dircollate.c b/src/or/dircollate.c index ca8b7ca..2f02512 100644 --- a/src/or/dircollate.c +++ b/src/or/dircollate.c @@ -303,6 +303,7 @@ dircollator_collate_by_ed25519(dircollator_t *dc) int dircollator_n_routers(dircollator_t *dc) { + tor_assert(dc->is_collated); return smartlist_len(dc->all_rsa_sha1_lst); } @@ -317,6 +318,7 @@ dircollator_n_routers(dircollator_t *dc) vote_routerstatus_t ** dircollator_get_votes_for_router(dircollator_t *dc, int idx) { + tor_assert(dc->is_collated); tor_assert(idx < smartlist_len(dc->all_rsa_sha1_lst)); return digestmap_get(dc->by_collated_rsa_sha1, smartlist_get(dc->all_rsa_sha1_lst, idx));

1 0

[tor/maint-0.2.7] Fix another case of 17668: Add NoEdConsensus
by nickm＠torproject.org 21 Mar '16

21 Mar '16

commit fa07c60c67d69ff25c4e64172e3a38b29a2e6143 Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Feb 23 09:31:23 2016 -0500 Fix another case of 17668: Add NoEdConsensus I had a half-built mechanism to track, during the voting process, whether the Ed25519 value (or lack thereof) reflected a true consensus among the authorities. But we never actually inserted this field in the consensus. The key idea here is that we first attempt to match up votes by pairs of <Ed,RSA>, where <Ed> can be NULL if we're told that there is no Ed key. If this succeeds, then we can treat all those votes as 'a consensus for Ed'. And we can include all other votes with a matching RSA key and no statement about Ed keys as being "also about the same relay." After that, we look for RSA keys we haven't actually found an entry for yet, and see if there are enough votes for them, NOT considering Ed keys. If there are, we match them as before, but we treat them as "not a consensus about ed". When we include an entry in a consensus, if it does not reflect a consensus about ed keys, then we include a new NoEdConsensus flag on it. This is all only for consensus method 22 or later. Also see corresponding dir-spec patch. --- changes/bug17668 | 5 +++++ src/or/dircollate.c | 4 +++- src/or/dirvote.c | 28 ++++++++++++++++++++++++++++ src/or/or.h | 5 ++++- 4 files changed, 40 insertions(+), 2 deletions(-) diff --git a/changes/bug17668 b/changes/bug17668 new file mode 100644 index 0000000..fa5c1c8 --- /dev/null +++ b/changes/bug17668 @@ -0,0 +1,5 @@ + o Major bugfixes (voting): + - When collating votes by Ed25519 identities, authorities now + include a "NoEdConsensus" flag if the ed25519 value (or lack thereof) + for a server does not reflect the majority consensus. Related to bug + 17668; bugfix on 0.2.7.2-alpha. diff --git a/src/or/dircollate.c b/src/or/dircollate.c index eeb0c24..ca8b7ca 100644 --- a/src/or/dircollate.c +++ b/src/or/dircollate.c @@ -81,6 +81,8 @@ dircollator_add_routerstatus(dircollator_t *dc, { const char *id = vrs->status.identity_digest; + vrs->ed25519_reflects_consensus = 0; + (void) vote; vote_routerstatus_t **vrs_lst = digestmap_get(dc->by_rsa_sha1, id); if (NULL == vrs_lst) { @@ -92,7 +94,7 @@ dircollator_add_routerstatus(dircollator_t *dc, const uint8_t *ed = vrs->ed25519_id; - if (tor_mem_is_zero((char*)ed, DIGEST256_LEN)) + if (! vrs->has_ed25519_listing) return; ddmap_entry_t search, *found; diff --git a/src/or/dirvote.c b/src/or/dirvote.c index be0635d..654d461 100644 --- a/src/or/dirvote.c +++ b/src/or/dirvote.c @@ -1242,6 +1242,9 @@ networkstatus_compute_consensus(smartlist_t *votes, smartlist_free(combined_server_versions); smartlist_free(combined_client_versions); + if (consensus_method >= MIN_METHOD_FOR_ED25519_ID_VOTING) + smartlist_add(flags, tor_strdup("NoEdConsensus")); + smartlist_sort_strings(flags); smartlist_uniq_strings(flags); @@ -1539,6 +1542,8 @@ networkstatus_compute_consensus(smartlist_t *votes, num_bandwidths = 0; num_mbws = 0; num_guardfraction_inputs = 0; + int ed_consensus = 0; + const uint8_t *ed_consensus_val = NULL; /* Okay, go through all the entries for this digest. */ for (int voter_idx = 0; voter_idx < smartlist_len(votes); ++voter_idx) { @@ -1580,6 +1585,17 @@ networkstatus_compute_consensus(smartlist_t *votes, if (rs->status.has_bandwidth) bandwidths_kb[num_bandwidths++] = rs->status.bandwidth_kb; + + /* Count number for which ed25519 is canonical. */ + if (rs->ed25519_reflects_consensus) { + ++ed_consensus; + if (ed_consensus_val) { + tor_assert(fast_memeq(ed_consensus_val, rs->ed25519_id, + ED25519_PUBKEY_LEN)); + } else { + ed_consensus_val = rs->ed25519_id; + } + } } /* We don't include this router at all unless more than half of @@ -1587,6 +1603,14 @@ networkstatus_compute_consensus(smartlist_t *votes, if (n_listing <= total_authorities/2) continue; + if (ed_consensus > 0) { + tor_assert(consensus_method >= MIN_METHOD_FOR_ED25519_ID_VOTING); + if (ed_consensus <= total_authorities / 2) { + log_warn(LD_BUG, "Not enough entries had ed_consensus set; how " + "can we have a consensus of %d?", ed_consensus); + } + } + /* The clangalyzer can't figure out that this will never be NULL * if n_listing is at least 1 */ tor_assert(current_rsa_id); @@ -1640,6 +1664,10 @@ networkstatus_compute_consensus(smartlist_t *votes, } else if (!strcmp(fl, "Unnamed")) { if (is_unnamed) smartlist_add(chosen_flags, (char*)fl); + } else if (!strcmp(fl, "NoEdConsensus") && + consensus_method >= MIN_METHOD_FOR_ED25519_ID_VOTING) { + if (ed_consensus <= total_authorities/2) + smartlist_add(chosen_flags, (char*)fl); } else { if (flag_counts[fl_sl_idx] > n_flag_voters[fl_sl_idx]/2) { smartlist_add(chosen_flags, (char*)fl); diff --git a/src/or/or.h b/src/or/or.h index b24b6a8..431927c 100644 --- a/src/or/or.h +++ b/src/or/or.h @@ -2380,7 +2380,10 @@ typedef struct vote_routerstatus_t { /** True iff the vote included an entry for ed25519 ID, or included * "id ed25519 none" to indicate that there was no ed25519 ID. */ unsigned int has_ed25519_listing:1; - unsigned int ed25519_reflects_consensus:1; /** DOCDOC */ + /** True if the Ed25519 listing here is the consensus-opinion for the + * Ed25519 listing; false if there was no consensus on Ed25519 key status, + * or if this VRS doesn't reflect it. */ + unsigned int ed25519_reflects_consensus:1; uint32_t measured_bw_kb; /**< Measured bandwidth (capacity) of the router */ /** The hash or hashes that the authority claims this microdesc has. */ vote_microdesc_hash_t *microdesc;

1 0

[tor/maint-0.2.7] Document has_ed25519_listing
by nickm＠torproject.org 21 Mar '16

21 Mar '16

commit 60ca3f358f80930778b12c9fcc8e3cf562b64e8e Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Feb 23 08:13:39 2016 -0500 Document has_ed25519_listing --- src/or/or.h | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) diff --git a/src/or/or.h b/src/or/or.h index b6d6ec0..b24b6a8 100644 --- a/src/or/or.h +++ b/src/or/or.h @@ -2377,7 +2377,9 @@ typedef struct vote_routerstatus_t { char *version; /**< The version that the authority says this router is * running. */ unsigned int has_measured_bw:1; /**< The vote had a measured bw */ - unsigned int has_ed25519_listing:1; /** DOCDOC */ + /** True iff the vote included an entry for ed25519 ID, or included + * "id ed25519 none" to indicate that there was no ed25519 ID. */ + unsigned int has_ed25519_listing:1; unsigned int ed25519_reflects_consensus:1; /** DOCDOC */ uint32_t measured_bw_kb; /**< Measured bandwidth (capacity) of the router */ /** The hash or hashes that the authority claims this microdesc has. */

1 0

[tor/maint-0.2.7] In routers_make_ed_keys_unique, break ties for published_on
by nickm＠torproject.org 21 Mar '16

21 Mar '16

commit b24f15a9a16acc8009c25823a127f3090b9b2edc Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Mar 15 10:34:05 2016 -0400 In routers_make_ed_keys_unique, break ties for published_on This ensures that if we can't use published_on to decide an ed,rsa mapping, we at least decide deterministically. Resolves 17668.T3 --- src/or/dirserv.c | 10 ++++++++-- 1 file changed, 8 insertions(+), 2 deletions(-) diff --git a/src/or/dirserv.c b/src/or/dirserv.c index ab8ddfe..ae67e8e 100644 --- a/src/or/dirserv.c +++ b/src/or/dirserv.c @@ -2124,7 +2124,8 @@ get_possible_sybil_list(const smartlist_t *routers) } /** If there are entries in routers with exactly the same ed25519 keys, - * remove the older one. May alter the order of the list. */ + * remove the older one. If they are exactly the same age, remove the one + * with the greater descriptor digest. May alter the order of the list. */ static void routers_make_ed_keys_unique(smartlist_t *routers) { @@ -2139,7 +2140,12 @@ routers_make_ed_keys_unique(smartlist_t *routers) if ((ri2 = digest256map_get(by_ed_key, pk))) { /* Duplicate; must omit one. Set the omit_from_vote flag in whichever * one has the earlier published_on. */ - if (ri2->cache_info.published_on < ri->cache_info.published_on) { + const time_t ri_pub = ri->cache_info.published_on; + const time_t ri2_pub = ri2->cache_info.published_on; + if (ri2_pub < ri_pub || + (ri2_pub == ri_pub && + memcmp(ri->cache_info.signed_descriptor_digest, + ri2->cache_info.signed_descriptor_digest,DIGEST_LEN)<0)) { digest256map_set(by_ed_key, pk, ri); ri2->omit_from_vote = 1; } else {

1 0

[tor/maint-0.2.7] Use nth consistently in dircollate.h.
by nickm＠torproject.org 21 Mar '16

21 Mar '16

commit 2f2fba8a918674b7187a5b497bb156b79aaec4e1 Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Mar 15 10:39:50 2016 -0400 Use nth consistently in dircollate.h. Documentation-only patch. Issue 17668.T6. --- src/or/dircollate.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/src/or/dircollate.c b/src/or/dircollate.c index 2f02512..43cf27f 100644 --- a/src/or/dircollate.c +++ b/src/or/dircollate.c @@ -22,8 +22,8 @@ static void dircollator_collate_by_ed25519(dircollator_t *dc); typedef struct ddmap_entry_s { HT_ENTRY(ddmap_entry_s) node; uint8_t d[DIGEST_LEN + DIGEST256_LEN]; - /* The i'th member of this array corresponds to the vote_routerstatus_t (if - * any) received for this digest pair from the n'th voter. */ + /* The nth member of this array corresponds to the vote_routerstatus_t (if + * any) received for this digest pair from the nth voter. */ vote_routerstatus_t *vrs_lst[FLEXIBLE_ARRAY_MEMBER]; } ddmap_entry_t;

1 0

[tor/maint-0.2.7] Merge branch 'ed25519_voting_fixes_squashed' into maint-0.2.7
by nickm＠torproject.org 21 Mar '16

21 Mar '16

commit e1e62f9d5735da64dc1435d3a40db77f6229766a Merge: 920e3d6 2f2fba8 Author: Nick Mathewson <nickm(a)torproject.org> Date: Mon Mar 21 13:25:12 2016 -0400 Merge branch 'ed25519_voting_fixes_squashed' into maint-0.2.7 changes/bug17668 | 5 ++++ changes/bug17702 | 6 ++++ changes/bug18318_ed | 7 +++++ changes/bug18368 | 5 ++++ src/or/dircollate.c | 78 ++++++++++++++++++++++++++++++++++++++++++++++---- src/or/dircollate.h | 24 ++++++++++++++-- src/or/dirserv.c | 75 +++++++++++++++++++++++++++++++++++++----------- src/or/dirserv.h | 2 +- src/or/dirvote.c | 35 ++++++++++++++++++++++ src/or/dirvote.h | 7 +++-- src/or/networkstatus.c | 2 +- src/or/or.h | 13 +++++++-- src/or/routerparse.c | 25 ++++++++-------- 13 files changed, 239 insertions(+), 45 deletions(-)

1 0

[tor/maint-0.2.7] After we strip out duplicate entries from 'routers', don't use 'rl'.
by nickm＠torproject.org 21 Mar '16

21 Mar '16

commit 48f8229504a00085676a737d9b519548ffc9d145 Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Mar 15 10:15:59 2016 -0400 After we strip out duplicate entries from 'routers', don't use 'rl'. We've got to make sure that every single subsequent calculation in dirserv_generate_networkstatus_vote_obj() are based on the list of routerinfo_t *after* we've removed possible duplicates, not before. Fortunately, none of the functions that were taking a routerlist_t as an argument were actually using any fields other than this list of routers. Resolves issue 18318.DG3. --- src/or/dirserv.c | 30 ++++++++++++++---------------- src/or/dirserv.h | 2 +- src/or/networkstatus.c | 2 +- 3 files changed, 16 insertions(+), 18 deletions(-) diff --git a/src/or/dirserv.c b/src/or/dirserv.c index 016514f..ab8ddfe 100644 --- a/src/or/dirserv.c +++ b/src/or/dirserv.c @@ -1422,7 +1422,7 @@ router_counts_toward_thresholds(const node_t *node, time_t now, * * Also, set the is_exit flag of each router appropriately. */ static void -dirserv_compute_performance_thresholds(routerlist_t *rl, +dirserv_compute_performance_thresholds(const smartlist_t *routers, digestmap_t *omit_as_sybil) { int n_active, n_active_nonexit, n_familiar; @@ -1450,18 +1450,18 @@ dirserv_compute_performance_thresholds(routerlist_t *rl, * sort them and use that to compute thresholds. */ n_active = n_active_nonexit = 0; /* Uptime for every active router. */ - uptimes = tor_calloc(smartlist_len(rl->routers), sizeof(uint32_t)); + uptimes = tor_calloc(smartlist_len(routers), sizeof(uint32_t)); /* Bandwidth for every active router. */ - bandwidths_kb = tor_calloc(smartlist_len(rl->routers), sizeof(uint32_t)); + bandwidths_kb = tor_calloc(smartlist_len(routers), sizeof(uint32_t)); /* Bandwidth for every active non-exit router. */ bandwidths_excluding_exits_kb = - tor_calloc(smartlist_len(rl->routers), sizeof(uint32_t)); + tor_calloc(smartlist_len(routers), sizeof(uint32_t)); /* Weighted mean time between failure for each active router. */ - mtbfs = tor_calloc(smartlist_len(rl->routers), sizeof(double)); + mtbfs = tor_calloc(smartlist_len(routers), sizeof(double)); /* Time-known for each active router. */ - tks = tor_calloc(smartlist_len(rl->routers), sizeof(long)); + tks = tor_calloc(smartlist_len(routers), sizeof(long)); /* Weighted fractional uptime for each active router. */ - wfus = tor_calloc(smartlist_len(rl->routers), sizeof(double)); + wfus = tor_calloc(smartlist_len(routers), sizeof(double)); nodelist_assert_ok(); @@ -1596,11 +1596,11 @@ dirserv_compute_performance_thresholds(routerlist_t *rl, * networkstatus_getinfo_by_purpose(). */ void -dirserv_compute_bridge_flag_thresholds(routerlist_t *rl) +dirserv_compute_bridge_flag_thresholds(const smartlist_t *routers) { digestmap_t *omit_as_sybil = digestmap_new(); - dirserv_compute_performance_thresholds(rl, omit_as_sybil); + dirserv_compute_performance_thresholds(routers, omit_as_sybil); digestmap_free(omit_as_sybil, NULL); } @@ -1753,16 +1753,13 @@ dirserv_get_bandwidth_for_router_kb(const routerinfo_t *ri) * how many measured bandwidths we know. This is used to decide whether we * ever trust advertised bandwidths for purposes of assigning flags. */ static void -dirserv_count_measured_bws(routerlist_t *rl) +dirserv_count_measured_bws(const smartlist_t *routers) { /* Initialize this first */ routers_with_measured_bw = 0; - tor_assert(rl); - tor_assert(rl->routers); - /* Iterate over the routerlist and count measured bandwidths */ - SMARTLIST_FOREACH_BEGIN(rl->routers, routerinfo_t *, ri) { + SMARTLIST_FOREACH_BEGIN(routers, const routerinfo_t *, ri) { /* Check if we know a measured bandwidth for this one */ if (dirserv_has_measured_bw(ri->cache_info.identity_digest)) { ++routers_with_measured_bw; @@ -2854,6 +2851,7 @@ dirserv_generate_networkstatus_vote_obj(crypto_pk_t *private_key, routers = smartlist_new(); smartlist_add_all(routers, rl->routers); routers_make_ed_keys_unique(routers); + /* After this point, don't use rl->routers; use 'routers' instead. */ routers_sort_by_identity(routers); omit_as_sybil = get_possible_sybil_list(routers); @@ -2864,9 +2862,9 @@ dirserv_generate_networkstatus_vote_obj(crypto_pk_t *private_key, /* Count how many have measured bandwidths so we know how to assign flags; * this must come before dirserv_compute_performance_thresholds() */ - dirserv_count_measured_bws(rl); + dirserv_count_measured_bws(routers); - dirserv_compute_performance_thresholds(rl, omit_as_sybil); + dirserv_compute_performance_thresholds(routers, omit_as_sybil); routerstatuses = smartlist_new(); microdescriptors = smartlist_new(); diff --git a/src/or/dirserv.h b/src/or/dirserv.h index d07339b..b16a67c 100644 --- a/src/or/dirserv.h +++ b/src/or/dirserv.h @@ -50,7 +50,7 @@ int list_server_status_v1(smartlist_t *routers, char **router_status_out, int dirserv_dump_directory_to_string(char **dir_out, crypto_pk_t *private_key); char *dirserv_get_flag_thresholds_line(void); -void dirserv_compute_bridge_flag_thresholds(routerlist_t *rl); +void dirserv_compute_bridge_flag_thresholds(const smartlist_t *routers); int directory_fetches_from_authorities(const or_options_t *options); int directory_fetches_dir_info_early(const or_options_t *options); diff --git a/src/or/networkstatus.c b/src/or/networkstatus.c index 71a2c0f..a9b22ed 100644 --- a/src/or/networkstatus.c +++ b/src/or/networkstatus.c @@ -1701,7 +1701,7 @@ networkstatus_dump_bridge_status_to_file(time_t now) char published[ISO_TIME_LEN+1]; format_iso_time(published, now); - dirserv_compute_bridge_flag_thresholds(rl); + dirserv_compute_bridge_flag_thresholds(rl->routers); thresholds = dirserv_get_flag_thresholds_line(); tor_asprintf(&published_thresholds_and_status, "published %s\nflag-thresholds %s\n%s",

1 0

[tor/master] Enable ed25519 collator in voting.
by nickm＠torproject.org 21 Mar '16

21 Mar '16

commit 60efce445b17d4b4153e91527887873812f5599f Author: Nick Mathewson <nickm(a)torproject.org> Date: Mon Feb 22 10:07:42 2016 -0500 Enable ed25519 collator in voting. Previously, I had left in some debugging code with /*XXX*/ after it, which nobody noticed. Live and learn! Next time I will use /*XXX DO NOT COMMIT*/ or something. We need to define a new consensus method for this; consensus method 21 shouldn't actually be used. Fixes bug 17702; bugfix on 0.2.7.2-alpha. --- changes/bug17702 | 6 ++++++ src/or/dircollate.c | 2 +- src/or/dirvote.c | 7 +++++++ src/or/dirvote.h | 7 ++++--- 4 files changed, 18 insertions(+), 4 deletions(-) diff --git a/changes/bug17702 b/changes/bug17702 new file mode 100644 index 0000000..4fda36f --- /dev/null +++ b/changes/bug17702 @@ -0,0 +1,6 @@ + o Major bugfixes: + - Actually enable Ed25519-based directory collation. + Previously, the code had been written, but some debugging code that had + accidentally been left in the codebase made it stay turned off. + Fixes bug 17702; bugfix on 0.2.7.2-alpha. + diff --git a/src/or/dircollate.c b/src/or/dircollate.c index 4c812c4..f56aea8 100644 --- a/src/or/dircollate.c +++ b/src/or/dircollate.c @@ -159,7 +159,7 @@ dircollator_collate(dircollator_t *dc, int consensus_method) tor_assert(!dc->is_collated); dc->all_rsa_sha1_lst = smartlist_new(); - if (consensus_method < MIN_METHOD_FOR_ED25519_ID_VOTING + 10/*XXX*/) + if (consensus_method < MIN_METHOD_FOR_ED25519_ID_VOTING) dircollator_collate_by_rsa(dc); else dircollator_collate_by_ed25519(dc); diff --git a/src/or/dirvote.c b/src/or/dirvote.c index d8e6ee2..be0635d 100644 --- a/src/or/dirvote.c +++ b/src/or/dirvote.c @@ -558,6 +558,13 @@ compute_consensus_method(smartlist_t *votes) static int consensus_method_is_supported(int method) { + if (method == MIN_METHOD_FOR_ED25519_ID_IN_MD) { + /* This method was broken due to buggy code accidently left in + * dircollate.c; do not actually use it. + */ + return 0; + } + return (method >= MIN_SUPPORTED_CONSENSUS_METHOD) && (method <= MAX_SUPPORTED_CONSENSUS_METHOD); } diff --git a/src/or/dirvote.h b/src/or/dirvote.h index dca8540..50c2496 100644 --- a/src/or/dirvote.h +++ b/src/or/dirvote.h @@ -55,7 +55,7 @@ #define MIN_SUPPORTED_CONSENSUS_METHOD 13 /** The highest consensus method that we currently support. */ -#define MAX_SUPPORTED_CONSENSUS_METHOD 21 +#define MAX_SUPPORTED_CONSENSUS_METHOD 22 /** Lowest consensus method where microdesc consensuses omit any entry * with no microdesc. */ @@ -87,11 +87,12 @@ #define MIN_METHOD_FOR_GUARDFRACTION 20 /** Lowest consensus method where authorities may include an "id" line for - * ed25519 identities in microdescriptors. */ + * ed25519 identities in microdescriptors. (Broken; see + * consensus_method_is_supported() for more info.) */ #define MIN_METHOD_FOR_ED25519_ID_IN_MD 21 /** Lowest consensus method where authorities vote on ed25519 ids and ensure * ed25519 id consistency. */ -#define MIN_METHOD_FOR_ED25519_ID_VOTING MIN_METHOD_FOR_ED25519_ID_IN_MD +#define MIN_METHOD_FOR_ED25519_ID_VOTING 22 /** Default bandwidth to clip unmeasured bandwidths to using method >= * MIN_METHOD_TO_CLIP_UNMEASURED_BW. (This is not a consensus method; do not

1 0

[tor/master] Never vote for an ed key twice.
by nickm＠torproject.org 21 Mar '16

21 Mar '16

commit 13a31e72db1b009623aa55bd52ffe7390a22623d Author: Nick Mathewson <nickm(a)torproject.org> Date: Mon Feb 22 11:43:59 2016 -0500 Never vote for an ed key twice. When generating a vote, and we have two routerinfos with the same ed key, omit the one published earlier. This was supposed to have been solved by key pinning, but when I made key pinning optional, I didn't realize that this would jump up and bite us. It is part of bug 18318, and the root cause of 17668. --- changes/bug18318_ed | 7 +++++++ src/or/dirserv.c | 39 +++++++++++++++++++++++++++++++++++++++ src/or/or.h | 4 ++++ 3 files changed, 50 insertions(+) diff --git a/changes/bug18318_ed b/changes/bug18318_ed new file mode 100644 index 0000000..af39234 --- /dev/null +++ b/changes/bug18318_ed @@ -0,0 +1,7 @@ + o Major bugfixes: + - When generating a vote with keypinning disabled, never include two + entries for the same ed25519 identity. This bug was causing + authorities to generate votes that they could not parse when a router + violated key pinning by changing its RSA identity but keeping its + Ed25519 identity. Fixes bug 17668; fixes part of bug 18318. Bugfix on + 0.2.7.2-alpha. diff --git a/src/or/dirserv.c b/src/or/dirserv.c index 8d9f166..016514f 100644 --- a/src/or/dirserv.c +++ b/src/or/dirserv.c @@ -2126,6 +2126,44 @@ get_possible_sybil_list(const smartlist_t *routers) return omit_as_sybil; } +/** If there are entries in routers with exactly the same ed25519 keys, + * remove the older one. May alter the order of the list. */ +static void +routers_make_ed_keys_unique(smartlist_t *routers) +{ + routerinfo_t *ri2; + digest256map_t *by_ed_key = digest256map_new(); + + SMARTLIST_FOREACH_BEGIN(routers, routerinfo_t *, ri) { + ri->omit_from_vote = 0; + if (ri->signing_key_cert == NULL) + continue; /* No ed key */ + const uint8_t *pk = ri->signing_key_cert->signing_key.pubkey; + if ((ri2 = digest256map_get(by_ed_key, pk))) { + /* Duplicate; must omit one. Set the omit_from_vote flag in whichever + * one has the earlier published_on. */ + if (ri2->cache_info.published_on < ri->cache_info.published_on) { + digest256map_set(by_ed_key, pk, ri); + ri2->omit_from_vote = 1; + } else { + ri->omit_from_vote = 1; + } + } else { + /* Add to map */ + digest256map_set(by_ed_key, pk, ri); + } + } SMARTLIST_FOREACH_END(ri); + + digest256map_free(by_ed_key, NULL); + + /* Now remove every router where the omit_from_vote flag got set. */ + SMARTLIST_FOREACH_BEGIN(routers, const routerinfo_t *, ri) { + if (ri->omit_from_vote) { + SMARTLIST_DEL_CURRENT(routers, ri); + } + } SMARTLIST_FOREACH_END(ri); +} + /** Extract status information from ri and from other authority * functions and store it in rs>. * @@ -2815,6 +2853,7 @@ dirserv_generate_networkstatus_vote_obj(crypto_pk_t *private_key, routers = smartlist_new(); smartlist_add_all(routers, rl->routers); + routers_make_ed_keys_unique(routers); routers_sort_by_identity(routers); omit_as_sybil = get_possible_sybil_list(routers); diff --git a/src/or/or.h b/src/or/or.h index 4496cbc..b6d6ec0 100644 --- a/src/or/or.h +++ b/src/or/or.h @@ -2081,6 +2081,10 @@ typedef struct { * tests for it. */ unsigned int needs_retest_if_added:1; + /** Used during voting to indicate that we should not include an entry for + * this routerinfo. Used only during voting. */ + unsigned int omit_from_vote:1; + /** Tor can use this router for general positions in circuits; we got it * from a directory server as usual, or we're an authority and a server * uploaded it. */

1 0

[tor/master] Document dircollate.c (and remove an unused global)
by nickm＠torproject.org 21 Mar '16

21 Mar '16

commit 6182e3462875d81dc3501bf0f1ad04fb658c2838 Author: Nick Mathewson <nickm(a)torproject.org> Date: Mon Feb 22 10:39:42 2016 -0500 Document dircollate.c (and remove an unused global) --- src/or/dircollate.c | 70 ++++++++++++++++++++++++++++++++++++++++++++++++++--- src/or/dircollate.h | 24 +++++++++++++++--- 2 files changed, 87 insertions(+), 7 deletions(-) diff --git a/src/or/dircollate.c b/src/or/dircollate.c index f56aea8..eeb0c24 100644 --- a/src/or/dircollate.c +++ b/src/or/dircollate.c @@ -17,20 +17,24 @@ static void dircollator_collate_by_rsa(dircollator_t *dc); static void dircollator_collate_by_ed25519(dircollator_t *dc); +/** Hashtable entry mapping a pair of digests (actually an ed25519 key and an + * RSA SHA1 digest) to an array of vote_routerstatus_t. */ typedef struct ddmap_entry_s { HT_ENTRY(ddmap_entry_s) node; uint8_t d[DIGEST_LEN + DIGEST256_LEN]; + /* The i'th member of this array corresponds to the vote_routerstatus_t (if + * any) received for this digest pair from the n'th voter. */ vote_routerstatus_t *vrs_lst[FLEXIBLE_ARRAY_MEMBER]; } ddmap_entry_t; -double_digest_map_t *by_both_ids; - +/** Release all storage held by e. */ static void ddmap_entry_free(ddmap_entry_t *e) { tor_free(e); } +/** Return a new empty ddmap_entry, with n_votes elements in vrs_list. */ static ddmap_entry_t * ddmap_entry_new(int n_votes) { @@ -50,6 +54,8 @@ ddmap_entry_eq(const ddmap_entry_t *a, const ddmap_entry_t *b) return fast_memeq(a->d, b->d, sizeof(a->d)); } +/** Record the RSA identity of ent as rsa_sha1, and the + * ed25519 identity as ed25519. */ static void ddmap_entry_set_digests(ddmap_entry_t *ent, const uint8_t *rsa_sha1, @@ -63,6 +69,10 @@ HT_PROTOTYPE(double_digest_map, ddmap_entry_s, node, ddmap_entry_hash, ddmap_entry_eq); HT_GENERATE2(double_digest_map, ddmap_entry_s, node, ddmap_entry_hash, ddmap_entry_eq, 0.6, tor_reallocarray, tor_free_); + +/** Helper: add a single vote_routerstatus_t vrs to the collator + * dc, indexing it by its RSA key digest, and by the 2-tuple of + * its RSA key digest and Ed25519 key. */ static void dircollator_add_routerstatus(dircollator_t *dc, int vote_num, @@ -99,6 +109,8 @@ dircollator_add_routerstatus(dircollator_t *dc, vrs_lst[vote_num] = vrs; } +/** Create and return a new dircollator object to use when collating + * n_votes out of a total of n_authorities. */ dircollator_t * dircollator_new(int n_votes, int n_authorities) { @@ -115,6 +127,7 @@ dircollator_new(int n_votes, int n_authorities) return dc; } +/** Release all storage held by dc. */ void dircollator_free(dircollator_t *dc) { @@ -139,6 +152,10 @@ dircollator_free(dircollator_t *dc) tor_free(dc); } +/** Add a single vote v to a dircollator dc. This function must + * be called exactly once for each vote to be used in the consensus. It may + * only be called before dircollator_collate(). + */ void dircollator_add_vote(dircollator_t *dc, networkstatus_t *v) { @@ -153,6 +170,9 @@ dircollator_add_vote(dircollator_t *dc, networkstatus_t *v) } SMARTLIST_FOREACH_END(vrs); } +/** Sort the entries in dc according to consensus_method, so + * that the consensus process can iterate over them with + * dircollator_n_routers() and dircollator_get_votes_for_router(). */ void dircollator_collate(dircollator_t *dc, int consensus_method) { @@ -168,6 +188,15 @@ dircollator_collate(dircollator_t *dc, int consensus_method) dc->is_collated = 1; } +/** + * Collation function for RSA-only consensuses: collate the votes for each + * entry in dc by their RSA keys. + * + * The rule is: + * If an RSA identity key is listed by more than half of the authorities, + * include that identity, and treat all descriptors with that RSA identity + * as describing the same router. + */ static void dircollator_collate_by_rsa(dircollator_t *dc) { @@ -189,6 +218,20 @@ dircollator_collate_by_rsa(dircollator_t *dc) dc->by_collated_rsa_sha1 = dc->by_rsa_sha1; } +/** + * Collation function for ed25519 consensuses: collate the votes for each + * entry in dc by ed25519 key and by RSA key. + * + * The rule is, approximately: + * If a <ed,rsa> identity is listed by more than half of authorities, + * include it. And include all <rsa>-only votes about that node as + * matching. + * + * Otherwise, if an <*,rsa> or <rsa> identity is listed by more than + * half of the authorities, and no <ed,rsa> pair for the same RSA key + * has been already been included based on the rule above, include + * that RSA identity. + */ static void dircollator_collate_by_ed25519(dircollator_t *dc) { @@ -197,6 +240,7 @@ dircollator_collate_by_ed25519(dircollator_t *dc) ddmap_entry_t **iter; + /* Go over all <ed,rsa> pairs */ HT_FOREACH(iter, double_digest_map, &dc->by_both_ids) { ddmap_entry_t *ent = *iter; int n = 0, i; @@ -205,9 +249,13 @@ dircollator_collate_by_ed25519(dircollator_t *dc) ++n; } + /* If not enough authorties listed this exact <ed,rsa> pair, + * don't include it. */ if (n <= total_authorities / 2) continue; + /* Now consider whether there are any other entries with the same + * RSA key (but with possibly different or missing ed value). */ vote_routerstatus_t **vrs_lst2 = digestmap_get(dc->by_rsa_sha1, (char*)ent->d); tor_assert(vrs_lst2); @@ -220,13 +268,17 @@ dircollator_collate_by_ed25519(dircollator_t *dc) } } + /* Record that we have seen this RSA digest. */ digestmap_set(rsa_digests, (char*)ent->d, ent->vrs_lst); smartlist_add(dc->all_rsa_sha1_lst, ent->d); } + /* Now look over all entries with an RSA digest, looking for RSA digests + * we didn't put in yet. + */ DIGESTMAP_FOREACH(dc->by_rsa_sha1, k, vote_routerstatus_t **, vrs_lst) { if (digestmap_get(rsa_digests, k) != NULL) - continue; + continue; /* We already included this RSA digest */ int n = 0, i; for (i = 0; i < dc->n_votes; ++i) { @@ -235,7 +287,7 @@ dircollator_collate_by_ed25519(dircollator_t *dc) } if (n <= total_authorities / 2) - continue; + continue; /* Not enough votes */ digestmap_set(rsa_digests, k, vrs_lst); smartlist_add(dc->all_rsa_sha1_lst, (char *)k); @@ -244,12 +296,22 @@ dircollator_collate_by_ed25519(dircollator_t *dc) dc->by_collated_rsa_sha1 = rsa_digests; } +/** Return the total number of collated router entries. This function may + * only be called after dircollator_collate. */ int dircollator_n_routers(dircollator_t *dc) { return smartlist_len(dc->all_rsa_sha1_lst); } +/** Return an array of vote_routerstatus_t entries for the idxth router + * in the collation order. Each array contains n_votes elements, where the + * nth element of the array is the vote_routerstatus_t from the nth voter for + * this identity (or NULL if there is no such entry). + * + * The maximum value for idx is dircollator_n_routers(). + * + * This function may only be called after dircollator_collate. */ vote_routerstatus_t ** dircollator_get_votes_for_router(dircollator_t *dc, int idx) { diff --git a/src/or/dircollate.h b/src/or/dircollate.h index cd1e8ac..d7f17ef 100644 --- a/src/or/dircollate.h +++ b/src/or/dircollate.h @@ -5,8 +5,8 @@ /* See LICENSE for licensing information */ /** - * \file dirvote.h - * \brief Header file for dirvote.c. + * \file dircollate.h + * \brief Header file for dircollate.c. **/ #ifndef TOR_DIRCOLLATE_H @@ -30,18 +30,36 @@ vote_routerstatus_t **dircollator_get_votes_for_router(dircollator_t *dc, #ifdef DIRCOLLATE_PRIVATE struct ddmap_entry_s; typedef HT_HEAD(double_digest_map, ddmap_entry_s) double_digest_map_t; +/** A dircollator keeps track of all the routerstatus entries in a + * set of networkstatus votes, and matches them by an appropriate rule. */ struct dircollator_s { - /**DOCDOC */ + /** True iff we have run the collation algorithm. */ int is_collated; + /** The total number of votes that we received. */ int n_votes; + /** The total number of authorities we acknowledge. */ int n_authorities; + /** The index which the next vote to be added to this collator should + * receive. */ int next_vote_num; + /** Map from RSA-SHA1 identity digest to an array of n_votes + * vote_routerstatus_t* pointers, such that the i'th member of the + * array is the i'th vote's entry for that RSA-SHA1 ID.*/ digestmap_t *by_rsa_sha1; + /** Map from <ed, RSA-SHA1> pair to an array similar to that used in + * by_rsa_sha1 above. We include <NULL,RSA-SHA1> entries for votes that + * say that there is no Ed key. */ struct double_digest_map by_both_ids; + /** One of two outputs created by collation: a map from RSA-SHA1 + * identity digest to an array of the vote_routerstatus_t objects. Entries + * only exist in this map for identities that we should include in the + * consensus. */ digestmap_t *by_collated_rsa_sha1; + /** One of two outputs created by collation: a sorted array of RSA-SHA1 + * identity digests .*/ smartlist_t *all_rsa_sha1_lst; }; #endif

1 0