commit 5b183328fdd4bf81a3a38afe88d2766e61773fb9 Author: David Goulet dgoulet@torproject.org Date: Tue May 3 10:57:49 2016 -0400

prop250: Add commit and SR values generation code

This adds the logic of commit and SR values generation. Furthermore, the concept of a protocol run is added that is commit is generated at the right time as well as SR values which are also rotated before a new protocol run.

Signed-off-by: George Kadianakis desnacked@riseup.net Signed-off-by: David Goulet dgoulet@torproject.org --- src/or/shared_random.c | 315 ++++++++++++++++++++++++++++++++++++++++++- src/or/shared_random.h | 14 ++ src/or/shared_random_state.c | 186 ++++++++++++++++++++++++- src/or/shared_random_state.h | 11 ++ 4 files changed, 516 insertions(+), 10 deletions(-)

diff --git a/src/or/shared_random.c b/src/or/shared_random.c index 447ab27..dd567bc 100644 --- a/src/or/shared_random.c +++ b/src/or/shared_random.c @@ -37,6 +37,35 @@ commit_new(const char *rsa_identity_fpr) return commit; }

+/* Issue a log message describing <b>commit</b>. */ +static void +commit_log(const sr_commit_t *commit) +{ + tor_assert(commit); + + log_debug(LD_DIR, "SR: Commit from %s", commit->rsa_identity_fpr); + + if (commit->commit_ts >= 0) { + log_debug(LD_DIR, "SR: Commit: [TS: %ld] [Encoded: %s]", + commit->commit_ts, commit->encoded_commit); + } + + if (commit->reveal_ts >= 0) { + log_debug(LD_DIR, "SR: Reveal: [TS: %ld] [Encoded: %s]", + commit->reveal_ts, safe_str(commit->encoded_reveal)); + } else { + log_debug(LD_DIR, "SR: Reveal: UNKNOWN"); + } +} + +/* Return true iff the commit contains an encoded reveal value. */ +STATIC int +commit_has_reveal_value(const sr_commit_t *commit) +{ + return !tor_mem_is_zero(commit->encoded_reveal, + sizeof(commit->encoded_reveal)); +} + /* Parse the encoded commit. The format is: * base64-encode( TIMESTAMP || H(REVEAL) ) * @@ -144,6 +173,62 @@ reveal_decode(const char *encoded, sr_commit_t *commit) return -1; }

+ +/* Encode a reveal element using a given commit object to dst which is a + * buffer large enough to put the base64-encoded reveal construction. The + * format is as follow: + * REVEAL = base64-encode( TIMESTAMP || H(RN) ) + * Return base64 encoded length on success else a negative value. + */ +STATIC int +reveal_encode(const sr_commit_t *commit, char *dst, size_t len) +{ + int ret; + size_t offset = 0; + char buf[SR_REVEAL_LEN] = {0}; + + tor_assert(commit); + tor_assert(dst); + + set_uint64(buf, tor_htonll(commit->reveal_ts)); + offset += sizeof(uint64_t); + memcpy(buf + offset, commit->random_number, + sizeof(commit->random_number)); + + /* Let's clean the buffer and then b64 encode it. */ + memset(dst, 0, len); + ret = base64_encode(dst, len, buf, sizeof(buf), 0); + /* Wipe this buffer because it contains our random value. */ + memwipe(buf, 0, sizeof(buf)); + return ret; +} + +/* Encode the given commit object to dst which is a buffer large enough to + * put the base64-encoded commit. The format is as follow: + * COMMIT = base64-encode( TIMESTAMP || H(H(RN)) ) + * Return base64 encoded length on success else a negative value. + */ +STATIC int +commit_encode(const sr_commit_t *commit, char *dst, size_t len) +{ + size_t offset = 0; + char buf[SR_COMMIT_LEN] = {0}; + + tor_assert(commit); + tor_assert(dst); + + /* First is the timestamp (8 bytes). */ + set_uint64(buf, tor_htonll((uint64_t) commit->commit_ts)); + offset += sizeof(uint64_t); + /* and then the hashed reveal. */ + memcpy(buf + offset, commit->hashed_reveal, + sizeof(commit->hashed_reveal)); + + /* Clean the buffer and then b64 encode it. */ + memset(dst, 0, len); + return base64_encode(dst, len, buf, sizeof(buf), 0); +} + /* Cleanup both our global state and disk state. */ static void sr_cleanup(void) @@ -151,6 +236,96 @@ sr_cleanup(void) sr_state_free(); }

+/* Using <b>commit</b>, return a newly allocated string containing the commit + * information that should be used during SRV calculation. It's the caller + * responsibility to free the memory. Return NULL if this is not a commit to be + * used for SRV calculation. */ +static char * +get_srv_element_from_commit(const sr_commit_t *commit) +{ + char *element; + tor_assert(commit); + + if (!commit_has_reveal_value(commit)) { + return NULL; + } + + tor_asprintf(&element, "%s%s", commit->rsa_identity_fpr, + commit->encoded_reveal); + return element; +} + +/* Return a srv object that is built with the construction: + * SRV = SHA3-256("shared-random" | INT_8(reveal_num) | + * INT_8(version) | HASHED_REVEALS | previous_SRV) + * This function cannot fail. */ +static sr_srv_t * +generate_srv(const char *hashed_reveals, uint8_t reveal_num, + const sr_srv_t *previous_srv) +{ + char msg[DIGEST256_LEN + SR_SRV_MSG_LEN] = {0}; + size_t offset = 0; + sr_srv_t *srv; + + tor_assert(hashed_reveals); + + /* Add the invariant token. */ + memcpy(msg, SR_SRV_TOKEN, SR_SRV_TOKEN_LEN); + offset += SR_SRV_TOKEN_LEN; + set_uint8(msg + offset, reveal_num); + offset += 1; + set_uint8(msg + offset, SR_PROTO_VERSION); + offset += 1; + memcpy(msg + offset, hashed_reveals, DIGEST256_LEN); + offset += DIGEST256_LEN; + if (previous_srv != NULL) { + memcpy(msg + offset, previous_srv->value, sizeof(previous_srv->value)); + } + + /* Ok we have our message and key for the HMAC computation, allocate our + * srv object and do the last step. */ + srv = tor_malloc_zero(sizeof(*srv)); + crypto_digest256((char *) srv->value, msg, sizeof(msg), SR_DIGEST_ALG); + srv->num_reveals = reveal_num; + + { + /* Debugging. */ + char srv_hash_encoded[SR_SRV_VALUE_BASE64_LEN + 1]; + sr_srv_encode(srv_hash_encoded, srv); + log_debug(LD_DIR, "SR: Generated SRV: %s", srv_hash_encoded); + } + return srv; +} + +/* Compare reveal values and return the result. This should exclusively be + * used by smartlist_sort(). */ +static int +compare_reveal_(const void **_a, const void **_b) +{ + const sr_commit_t *a = *_a, *b = *_b; + return fast_memcmp(a->hashed_reveal, b->hashed_reveal, + sizeof(a->hashed_reveal)); +} + +/* Encode the given shared random value and put it in dst. Destination + * buffer must be at least SR_SRV_VALUE_BASE64_LEN plus the NULL byte. */ +void +sr_srv_encode(char *dst, const sr_srv_t *srv) +{ + int ret; + /* Extra byte for the NULL terminated char. */ + char buf[SR_SRV_VALUE_BASE64_LEN + 1]; + + tor_assert(dst); + tor_assert(srv); + + ret = base64_encode(buf, sizeof(buf), (const char *) srv->value, + sizeof(srv->value), 0); + /* Always expect the full length without the NULL byte. */ + tor_assert(ret == (sizeof(buf) - 1)); + strlcpy(dst, buf, sizeof(buf)); +} + /* Free a commit object. */ void sr_commit_free(sr_commit_t *commit) @@ -163,6 +338,123 @@ sr_commit_free(sr_commit_t *commit) tor_free(commit); }

+/* Generate the commitment/reveal value for the protocol run starting at + * <b>timestamp</b>. <b>my_rsa_cert</b> is our authority RSA certificate. */ +sr_commit_t * +sr_generate_our_commit(time_t timestamp, const authority_cert_t *my_rsa_cert) +{ + sr_commit_t *commit = NULL; + char fingerprint[FINGERPRINT_LEN+1]; + + tor_assert(my_rsa_cert); + + /* Get our RSA identity fingerprint */ + if (crypto_pk_get_fingerprint(my_rsa_cert->identity_key, + fingerprint, 0) < 0) { + goto error; + } + + /* New commit with our identity key. */ + commit = commit_new(fingerprint); + + /* Generate the reveal random value */ + crypto_strongest_rand(commit->random_number, + sizeof(commit->random_number)); + commit->commit_ts = commit->reveal_ts = timestamp; + + /* Now get the base64 blob that corresponds to our reveal */ + if (reveal_encode(commit, commit->encoded_reveal, + sizeof(commit->encoded_reveal)) < 0) { + log_err(LD_DIR, "SR: Unable to encode our reveal value!"); + goto error; + } + + /* Now let's create the commitment */ + tor_assert(commit->alg == SR_DIGEST_ALG); + /* The invariant length is used here since the encoded reveal variable + * has an extra byte added for the NULL terminated byte. */ + if (crypto_digest256(commit->hashed_reveal, commit->encoded_reveal, + SR_REVEAL_BASE64_LEN, commit->alg)) { + goto error; + } + + /* Now get the base64 blob that corresponds to our commit. */ + if (commit_encode(commit, commit->encoded_commit, + sizeof(commit->encoded_commit)) < 0) { + log_err(LD_DIR, "SR: Unable to encode our commit value!"); + goto error; + } + + log_debug(LD_DIR, "SR: Generated our commitment:"); + commit_log(commit); + return commit; + + error: + sr_commit_free(commit); + return NULL; +} + +/* Compute the shared random value based on the active commits in our state. */ +void +sr_compute_srv(void) +{ + size_t reveal_num = 0; + char *reveals = NULL; + smartlist_t *chunks, *commits; + digestmap_t *state_commits; + + /* Computing a shared random value in the commit phase is very wrong. This + * should only happen at the very end of the reveal phase when a new + * protocol run is about to start. */ + tor_assert(sr_state_get_phase() == SR_PHASE_REVEAL); + state_commits = sr_state_get_commits(); + + commits = smartlist_new(); + chunks = smartlist_new(); + + /* We must make a list of commit ordered by authority fingerprint in + * ascending order as specified by proposal 250. */ + DIGESTMAP_FOREACH(state_commits, key, sr_commit_t *, c) { + smartlist_add(commits, c); + } DIGESTMAP_FOREACH_END; + smartlist_sort(commits, compare_reveal_); + + /* Now for each commit for that sorted list in ascending order, we'll + * build the element for each authority that needs to go into the srv + * computation. */ + SMARTLIST_FOREACH_BEGIN(commits, const sr_commit_t *, c) { + char *element = get_srv_element_from_commit(c); + if (element) { + smartlist_add(chunks, element); + reveal_num++; + } + } SMARTLIST_FOREACH_END(c); + smartlist_free(commits); + + { + /* Join all reveal values into one giant string that we'll hash so we + * can generated our shared random value. */ + sr_srv_t *current_srv; + char hashed_reveals[DIGEST256_LEN]; + reveals = smartlist_join_strings(chunks, "", 0, NULL); + SMARTLIST_FOREACH(chunks, char *, s, tor_free(s)); + smartlist_free(chunks); + if (crypto_digest256(hashed_reveals, reveals, strlen(reveals), + SR_DIGEST_ALG)) { + goto end; + } + tor_assert(reveal_num < UINT8_MAX); + current_srv = generate_srv(hashed_reveals, (uint8_t) reveal_num, + sr_state_get_previous_srv()); + sr_state_set_current_srv(current_srv); + /* We have a fresh SRV, flag our state. */ + sr_state_set_fresh_srv(); + } + + end: + tor_free(reveals); +} + /* Parse a list of arguments from a SRV value either from a vote, consensus * or from our disk state and return a newly allocated srv object. NULL is * returned on error. @@ -174,7 +466,7 @@ sr_srv_t * sr_parse_srv(const smartlist_t *args) { char *value; - int num_reveals, ok; + int num_reveals, ok, ret; sr_srv_t *srv = NULL;

tor_assert(args); @@ -189,13 +481,24 @@ sr_parse_srv(const smartlist_t *args) if (!ok) { goto end; } - srv = tor_malloc_zero(sizeof(*srv)); - srv->num_reveals = num_reveals; - /* Second and last argument is the shared random value it self. */ value = smartlist_get(args, 1); - base16_decode((char *) srv->value, sizeof(srv->value), value, - HEX_DIGEST256_LEN); + if (strlen(value) != SR_SRV_VALUE_BASE64_LEN) { + goto end; + } + + srv = tor_malloc_zero(sizeof(*srv)); + srv->num_reveals = num_reveals; + /* We substract one byte from the srclen because the function ignores the + * '=' character in the given buffer. This is broken but it's a documented + * behavior of the implementation. */ + ret = base64_decode((char *) srv->value, sizeof(srv->value), value, + SR_SRV_VALUE_BASE64_LEN - 1); + if (ret != sizeof(srv->value)) { + tor_free(srv); + srv = NULL; + goto end; + } end: return srv; } diff --git a/src/or/shared_random.h b/src/or/shared_random.h index 447de0c..878bfbf 100644 --- a/src/or/shared_random.h +++ b/src/or/shared_random.h @@ -42,6 +42,11 @@ * Formula is taken from base64_encode_size. This adds up to 56 bytes. */ #define SR_REVEAL_BASE64_LEN \ (((SR_REVEAL_LEN - 1) / 3) * 4 + 4) +/* Length of base64 encoded shared random value. It's 32 bytes long so 44 + * bytes from the base64_encode_size formula. That includes the '=' + * character at the end. */ +#define SR_SRV_VALUE_BASE64_LEN \ + (((DIGEST256_LEN - 1) / 3) * 4 + 4)

/* Protocol phase. */ typedef enum { @@ -97,18 +102,27 @@ typedef struct sr_commit_t { int sr_init(int save_to_disk); void sr_save_and_cleanup(void); void sr_commit_free(sr_commit_t *commit); +void sr_srv_encode(char *dst, const sr_srv_t *srv);

/* Private methods (only used by shared_random_state.c): */

sr_commit_t *sr_parse_commit(const smartlist_t *args); sr_srv_t *sr_parse_srv(const smartlist_t *args); +void sr_compute_srv(void); +sr_commit_t *sr_generate_our_commit(time_t timestamp, + const authority_cert_t *my_rsa_cert);

#ifdef SHARED_RANDOM_PRIVATE

+/* Encode */ +STATIC int reveal_encode(const sr_commit_t *commit, char *dst, size_t len); +STATIC int commit_encode(const sr_commit_t *commit, char *dst, size_t len); /* Decode. */ STATIC int commit_decode(const char *encoded, sr_commit_t *commit); STATIC int reveal_decode(const char *encoded, sr_commit_t *commit);

+STATIC int commit_has_reveal_value(const sr_commit_t *commit); + #endif /* SHARED_RANDOM_PRIVATE */

#endif /* TOR_SHARED_RANDOM_H */ diff --git a/src/or/shared_random_state.c b/src/or/shared_random_state.c index 9fd3b27..87bdfc0 100644 --- a/src/or/shared_random_state.c +++ b/src/or/shared_random_state.c @@ -22,6 +22,9 @@ /* Default filename of the shared random state on disk. */ static const char default_fname[] = "sr-state";

+/* String representation of a protocol phase. */ +static const char *phase_str[] = { "unknown", "commit", "reveal" }; + /* Our shared random protocol state. There is only one possible state per * protocol run so this is the global state which is reset at every run once * the shared random value has been computed. */ @@ -88,6 +91,25 @@ static const config_format_t state_format = { &state_extra_var, };

+/* Return a string representation of a protocol phase. */ +STATIC const char * +get_phase_str(sr_phase_t phase) +{ + const char *the_string = NULL; + + switch (phase) { + case SR_PHASE_COMMIT: + case SR_PHASE_REVEAL: + the_string = phase_str[phase]; + break; + default: + /* Unknown phase shouldn't be possible. */ + tor_assert(0); + } + + return the_string; +} + /* Return the voting interval of the tor vote subsystem. */ static int get_voting_interval(void) @@ -554,7 +576,7 @@ disk_state_put_commit_line(const sr_commit_t *commit, config_line_t *line) static void disk_state_put_srv_line(const sr_srv_t *srv, config_line_t *line) { - char encoded[HEX_DIGEST256_LEN + 1]; + char encoded[SR_SRV_VALUE_BASE64_LEN + 1];

tor_assert(line);

@@ -563,8 +585,7 @@ disk_state_put_srv_line(const sr_srv_t *srv, config_line_t *line) if (srv == NULL) { return; } - base16_encode(encoded, sizeof(encoded), (const char *) srv->value, - sizeof(srv->value)); + sr_srv_encode(encoded, srv); tor_asprintf(&line->value, "%d %s", srv->num_reveals, encoded); }

@@ -748,6 +769,82 @@ disk_state_save_to_disk(void) return ret; }

+/* Reset our state to prepare for a new protocol run. Once this returns, all + * commits in the state will be removed and freed. */ +STATIC void +reset_state_for_new_protocol_run(time_t valid_after) +{ + tor_assert(sr_state); + + /* Keep counters in track */ + sr_state->n_reveal_rounds = 0; + sr_state->n_commit_rounds = 0; + sr_state->n_protocol_runs++; + + /* Reset valid-until */ + sr_state->valid_until = get_state_valid_until_time(valid_after); + sr_state->valid_after = valid_after; + + /* We are in a new protocol run so cleanup commits. */ + sr_state_delete_commits(); +} + +/* Rotate SRV value by freeing the previous value, assigning the current + * value to the previous one and nullifying the current one. */ +STATIC void +state_rotate_srv(void) +{ + /* Get a pointer to the previous SRV so we can free it after rotation. */ + sr_srv_t *previous_srv = sr_state_get_previous_srv(); + /* Set previous SRV with the current one. */ + sr_state_set_previous_srv(sr_state_get_current_srv()); + /* Nullify the current srv. */ + sr_state_set_current_srv(NULL); + tor_free(previous_srv); +} + +/* This is the first round of the new protocol run starting at + * <b>valid_after</b>. Do the necessary housekeeping. */ +STATIC void +new_protocol_run(time_t valid_after) +{ + sr_commit_t *our_commitment = NULL; + + /* Only compute the srv at the end of the reveal phase. */ + if (sr_state->phase == SR_PHASE_REVEAL) { + /* We are about to compute a new shared random value that will be set in + * our state as the current value so rotate values. */ + state_rotate_srv(); + /* Compute the shared randomness value of the day. */ + sr_compute_srv(); + } + + /* Prepare for the new protocol run by reseting the state */ + reset_state_for_new_protocol_run(valid_after); + + /* Do some logging */ + log_info(LD_DIR, "SR: Protocol run #%" PRIu64 " starting!", + sr_state->n_protocol_runs); + + /* Generate fresh commitments for this protocol run */ + our_commitment = sr_generate_our_commit(valid_after, + get_my_v3_authority_cert()); + if (our_commitment) { + /* Add our commitment to our state. In case we are unable to create one + * (highly unlikely), we won't vote for this protocol run since our + * commitment won't be in our state. */ + sr_state_add_commit(our_commitment); + } +} + +/* Return 1 iff the <b>next_phase</b> is a phase transition from the current + * phase that is it's different. */ +STATIC int +is_phase_transition(sr_phase_t next_phase) +{ + return sr_state->phase != next_phase; +} + /* Helper function: return a commit using the RSA fingerprint of the * authority or NULL if no such commit is known. */ static sr_commit_t * @@ -756,7 +853,6 @@ state_query_get_commit(const char *rsa_fpr) tor_assert(rsa_fpr); return digestmap_get(sr_state->commits, rsa_fpr); } - /* Helper function: This handles the GET state action using an * <b>obj_type</b> and <b>data</b> needed for the action. */ static void * @@ -941,6 +1037,20 @@ sr_state_set_current_srv(const sr_srv_t *srv) NULL); }

+/* Clean all the SRVs in our state. */ +void +sr_state_clean_srvs(void) +{ + sr_srv_t *previous_srv = sr_state_get_previous_srv(); + sr_srv_t *current_srv = sr_state_get_current_srv(); + + tor_free(previous_srv); + sr_state_set_previous_srv(NULL); + + tor_free(current_srv); + sr_state_set_current_srv(NULL); +} + /* Return a pointer to the commits map from our state. CANNOT be NULL. */ digestmap_t * sr_state_get_commits(void) @@ -952,6 +1062,68 @@ sr_state_get_commits(void) return commits; }

+/* Update the current SR state as needed for the upcoming voting round at + * <b>valid_after</b>. */ +void +sr_state_update(time_t valid_after) +{ + sr_phase_t next_phase; + + tor_assert(sr_state); + + /* Don't call this function twice in the same voting period. */ + if (valid_after <= sr_state->valid_after) { + log_info(LD_DIR, "SR: Asked to update state twice. Ignoring."); + return; + } + + /* Get phase of upcoming round. */ + next_phase = get_sr_protocol_phase(valid_after); + + /* If we are transitioning to a new protocol phase, prepare the stage. */ + if (is_phase_transition(next_phase)) { + if (next_phase == SR_PHASE_COMMIT) { + /* Going into commit phase means we are starting a new protocol run. */ + new_protocol_run(valid_after); + } + /* Set the new phase for this round */ + sr_state->phase = next_phase; + } else if (sr_state->phase == SR_PHASE_COMMIT && + digestmap_size(sr_state->commits) == 0) { + /* We are _NOT_ in a transition phase so if we are in the commit phase + * and have no commit, generate one. Chances are that we are booting up + * so let's have a commit in our state for the next voting period. */ + sr_commit_t *our_commit = + sr_generate_our_commit(valid_after, get_my_v3_authority_cert()); + if (our_commit) { + /* Add our commitment to our state. In case we are unable to create one + * (highly unlikely), we won't vote for this protocol run since our + * commitment won't be in our state. */ + sr_state_add_commit(our_commit); + } + } + + sr_state_set_valid_after(valid_after); + + /* Count the current round */ + if (sr_state->phase == SR_PHASE_COMMIT) { + /* invariant check: we've not entered reveal phase yet */ + tor_assert(sr_state->n_reveal_rounds == 0); + sr_state->n_commit_rounds++; + } else { + sr_state->n_reveal_rounds++; + } + + { /* Debugging. */ + char tbuf[ISO_TIME_LEN + 1]; + format_iso_time(tbuf, valid_after); + log_info(LD_DIR, "SR: State prepared for new voting period (%s). " + "Current phase is %s (%d/%d).", + tbuf, get_phase_str(sr_state->phase), + sr_state->n_commit_rounds, sr_state->n_reveal_rounds); + } +} + /* Return commit object from the given authority digest <b>identity</b>. * Return NULL if not found. */ sr_commit_t * @@ -1079,6 +1251,12 @@ sr_state_init(int save_to_disk, int read_from_disk) tor_assert(0); } } + /* We have a state in memory, let's make sure it's updated for the current + * and next voting round. */ + { + time_t valid_after = get_next_valid_after_time(now); + sr_state_update(valid_after); + } return 0;

error: diff --git a/src/or/shared_random_state.h b/src/or/shared_random_state.h index a9a80ee..d9d9751 100644 --- a/src/or/shared_random_state.h +++ b/src/or/shared_random_state.h @@ -95,6 +95,8 @@ typedef struct sr_disk_state_t {

/* Public methods: */

+void sr_state_update(time_t valid_after); + /* Private methods (only used by shared-random.c): */

void sr_state_set_valid_after(time_t valid_after); @@ -108,6 +110,8 @@ digestmap_t *sr_state_get_commits(void); sr_commit_t *sr_state_get_commit(const char *rsa_fpr); void sr_state_add_commit(sr_commit_t *commit); void sr_state_delete_commits(void); +void sr_state_copy_reveal_info(sr_commit_t *saved_commit, + const sr_commit_t *commit); unsigned int sr_state_srv_is_fresh(void); void sr_state_set_fresh_srv(void); void sr_state_unset_fresh_srv(void); @@ -118,8 +122,15 @@ void sr_state_free(void); #ifdef SHARED_RANDOM_STATE_PRIVATE

STATIC int disk_state_load_from_disk_impl(const char *fname); + STATIC sr_phase_t get_sr_protocol_phase(time_t valid_after); + STATIC time_t get_state_valid_until_time(time_t now); +STATIC const char *get_phase_str(sr_phase_t phase); +STATIC void reset_state_for_new_protocol_run(time_t valid_after); +STATIC void new_protocol_run(time_t valid_after); +STATIC void state_rotate_srv(void); +STATIC int is_phase_transition(sr_phase_t next_phase);

#endif /* SHARED_RANDOM_STATE_PRIVATE */