From 60efce445b17d4b4153e91527887873812f5599f Mon Sep 17 00:00:00 2001 From: Nick Mathewson Date: Mon, 22 Feb 2016 10:07:42 -0500 Subject: 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(-) create mode 100644 changes/bug17702 diff --git a/changes/bug17702 b/changes/bug17702 new file mode 100644 index 0000000000..4fda36f736 --- /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 4c812c40e6..f56aea8c64 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 d8e6ee2229..be0635d92b 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 dca8540870..50c2496bb0 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 -- cgit v1.2.3-54-g00ecf From 6182e3462875d81dc3501bf0f1ad04fb658c2838 Mon Sep 17 00:00:00 2001 From: Nick Mathewson Date: Mon, 22 Feb 2016 10:39:42 -0500 Subject: 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 f56aea8c64..eeb0c24008 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 identity is listed by more than half of authorities, + * include it. And include all -only votes about that node as + * matching. + * + * Otherwise, if an <*,rsa> or identity is listed by more than + * half of the authorities, and no 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 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 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 cd1e8ac96d..d7f17ef757 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 pair to an array similar to that used in + * by_rsa_sha1 above. We include 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 -- cgit v1.2.3-54-g00ecf From c20e34e1894bed07982fe64d60a1b3fe9403d269 Mon Sep 17 00:00:00 2001 From: Nick Mathewson Date: Mon, 22 Feb 2016 10:59:27 -0500 Subject: Fix log message subjects in networkstatus_parse_vote_from_string() Some of these messages called the thing being parsed a "vote" whether it is a vote or a consensus. Fixes bug 18368. --- changes/bug18368 | 5 +++++ src/or/routerparse.c | 25 ++++++++++++------------- 2 files changed, 17 insertions(+), 13 deletions(-) create mode 100644 changes/bug18368 diff --git a/changes/bug18368 b/changes/bug18368 new file mode 100644 index 0000000000..17218d432f --- /dev/null +++ b/changes/bug18368 @@ -0,0 +1,5 @@ + o Minor bugfixes: + - When logging information about an unparseable networkstatus vote or + consensus, do not say "vote" when we mean consensus. Fixes bug + 18368; bugfix on 0.2.0.8-alpha. + diff --git a/src/or/routerparse.c b/src/or/routerparse.c index f898ef8aef..6b6e21d5d0 100644 --- a/src/or/routerparse.c +++ b/src/or/routerparse.c @@ -2862,7 +2862,7 @@ networkstatus_parse_vote_from_string(const char *s, const char **eos_out, (ns_type == NS_TYPE_CONSENSUS) ? networkstatus_consensus_token_table : networkstatus_token_table, 0)) { - log_warn(LD_DIR, "Error tokenizing network-status vote header"); + log_warn(LD_DIR, "Error tokenizing network-status header"); goto err; } @@ -3085,7 +3085,7 @@ networkstatus_parse_vote_from_string(const char *s, const char **eos_out, base16_decode(voter->identity_digest, sizeof(voter->identity_digest), tok->args[1], HEX_DIGEST_LEN) < 0) { log_warn(LD_DIR, "Error decoding identity digest %s in " - "network-status vote.", escaped(tok->args[1])); + "network-status document.", escaped(tok->args[1])); goto err; } if (ns->type != NS_TYPE_CONSENSUS && @@ -3144,7 +3144,7 @@ networkstatus_parse_vote_from_string(const char *s, const char **eos_out, voter = NULL; } if (smartlist_len(ns->voters) == 0) { - log_warn(LD_DIR, "Missing dir-source elements in a vote networkstatus."); + log_warn(LD_DIR, "Missing dir-source elements in a networkstatus."); goto err; } else if (ns->type != NS_TYPE_CONSENSUS && smartlist_len(ns->voters) != 1) { log_warn(LD_DIR, "Too many dir-source elements in a vote networkstatus."); @@ -3205,8 +3205,7 @@ networkstatus_parse_vote_from_string(const char *s, const char **eos_out, } if (fast_memcmp(rs1->identity_digest, rs2->identity_digest, DIGEST_LEN) >= 0) { - log_warn(LD_DIR, "Vote networkstatus entries not sorted by identity " - "digest"); + log_warn(LD_DIR, "Networkstatus entries not sorted by identity digest"); goto err; } } @@ -3319,12 +3318,12 @@ networkstatus_parse_vote_from_string(const char *s, const char **eos_out, base16_decode(declared_identity, sizeof(declared_identity), id_hexdigest, HEX_DIGEST_LEN) < 0) { log_warn(LD_DIR, "Error decoding declared identity %s in " - "network-status vote.", escaped(id_hexdigest)); + "network-status document.", escaped(id_hexdigest)); goto err; } if (!(v = networkstatus_get_voter_by_id(ns, declared_identity))) { - log_warn(LD_DIR, "ID on signature on network-status vote does not match " - "any declared directory source."); + log_warn(LD_DIR, "ID on signature on network-status document does " + "not match any declared directory source."); goto err; } sig = tor_malloc_zero(sizeof(document_signature_t)); @@ -3334,7 +3333,7 @@ networkstatus_parse_vote_from_string(const char *s, const char **eos_out, base16_decode(sig->signing_key_digest, sizeof(sig->signing_key_digest), sk_hexdigest, HEX_DIGEST_LEN) < 0) { log_warn(LD_DIR, "Error decoding declared signing key digest %s in " - "network-status vote.", escaped(sk_hexdigest)); + "network-status document.", escaped(sk_hexdigest)); tor_free(sig); goto err; } @@ -3353,8 +3352,8 @@ networkstatus_parse_vote_from_string(const char *s, const char **eos_out, /* We already parsed a vote with this algorithm from this voter. Use the first one. */ log_fn(LOG_PROTOCOL_WARN, LD_DIR, "We received a networkstatus " - "that contains two votes from the same voter with the same " - "algorithm. Ignoring the second vote."); + "that contains two signatures from the same voter with the same " + "algorithm. Ignoring the second signature."); tor_free(sig); continue; } @@ -3362,7 +3361,7 @@ networkstatus_parse_vote_from_string(const char *s, const char **eos_out, if (ns->type != NS_TYPE_CONSENSUS) { if (check_signature_token(ns_digests.d[DIGEST_SHA1], DIGEST_LEN, tok, ns->cert->signing_key, 0, - "network-status vote")) { + "network-status document")) { tor_free(sig); goto err; } @@ -3381,7 +3380,7 @@ networkstatus_parse_vote_from_string(const char *s, const char **eos_out, } SMARTLIST_FOREACH_END(_tok); if (! n_signatures) { - log_warn(LD_DIR, "No signatures on networkstatus vote."); + log_warn(LD_DIR, "No signatures on networkstatus document."); goto err; } else if (ns->type == NS_TYPE_VOTE && n_signatures != 1) { log_warn(LD_DIR, "Received more than one signature on a " -- cgit v1.2.3-54-g00ecf From 13a31e72db1b009623aa55bd52ffe7390a22623d Mon Sep 17 00:00:00 2001 From: Nick Mathewson Date: Mon, 22 Feb 2016 11:43:59 -0500 Subject: 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(+) create mode 100644 changes/bug18318_ed diff --git a/changes/bug18318_ed b/changes/bug18318_ed new file mode 100644 index 0000000000..af39234d53 --- /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 8d9f166556..016514f10f 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 4496cbcec3..b6d6ec074f 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. */ -- cgit v1.2.3-54-g00ecf From 60ca3f358f80930778b12c9fcc8e3cf562b64e8e Mon Sep 17 00:00:00 2001 From: Nick Mathewson Date: Tue, 23 Feb 2016 08:13:39 -0500 Subject: 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 b6d6ec074f..b24b6a85e4 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. */ -- cgit v1.2.3-54-g00ecf From fa07c60c67d69ff25c4e64172e3a38b29a2e6143 Mon Sep 17 00:00:00 2001 From: Nick Mathewson Date: Tue, 23 Feb 2016 09:31:23 -0500 Subject: 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 , where 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(-) create mode 100644 changes/bug17668 diff --git a/changes/bug17668 b/changes/bug17668 new file mode 100644 index 0000000000..fa5c1c8081 --- /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 eeb0c24008..ca8b7ca847 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 be0635d92b..654d461dd6 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 b24b6a85e4..431927c7e7 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; -- cgit v1.2.3-54-g00ecf From 48f8229504a00085676a737d9b519548ffc9d145 Mon Sep 17 00:00:00 2001 From: Nick Mathewson Date: Tue, 15 Mar 2016 10:15:59 -0400 Subject: 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 016514f10f..ab8ddfe840 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 d07339bc12..b16a67c081 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 71a2c0f121..a9b22ed1cc 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", -- cgit v1.2.3-54-g00ecf From beef6ed45160f096815b4ea840ff671fb484d1da Mon Sep 17 00:00:00 2001 From: Nick Mathewson Date: Tue, 15 Mar 2016 10:24:18 -0400 Subject: 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 ca8b7ca847..2f02512d3e 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)); -- cgit v1.2.3-54-g00ecf From b24f15a9a16acc8009c25823a127f3090b9b2edc Mon Sep 17 00:00:00 2001 From: Nick Mathewson Date: Tue, 15 Mar 2016 10:34:05 -0400 Subject: 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 ab8ddfe840..ae67e8edb7 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 { -- cgit v1.2.3-54-g00ecf From 2f2fba8a918674b7187a5b497bb156b79aaec4e1 Mon Sep 17 00:00:00 2001 From: Nick Mathewson Date: Tue, 15 Mar 2016 10:39:50 -0400 Subject: 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 2f02512d3e..43cf27f489 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; -- cgit v1.2.3-54-g00ecf