1 /* Copyright (c) 2016, The Tor Project, Inc. */
2 /* See LICENSE for licensing information */
5 * \file shared_random.c
7 * \brief Functions and data structure needed to accomplish the shared
8 * random protocol as defined in proposal #250.
11 #define SHARED_RANDOM_PRIVATE
14 #include "shared_random.h"
16 #include "confparse.h"
17 #include "networkstatus.h"
18 #include "routerkeys.h"
20 #include "routerlist.h"
21 #include "shared_random_state.h"
23 /* Allocate a new commit object and initializing it with <b>identity</b>
24 * that MUST be provided. The digest algorithm is set to the default one
25 * that is supported. The rest is uninitialized. This never returns NULL. */
27 commit_new(const char *rsa_identity_fpr
)
31 tor_assert(rsa_identity_fpr
);
33 commit
= tor_malloc_zero(sizeof(*commit
));
34 commit
->alg
= SR_DIGEST_ALG
;
35 strlcpy(commit
->rsa_identity_fpr
, rsa_identity_fpr
,
36 sizeof(commit
->rsa_identity_fpr
));
40 /* Issue a log message describing <b>commit</b>. */
42 commit_log(const sr_commit_t
*commit
)
46 log_debug(LD_DIR
, "SR: Commit from %s", commit
->rsa_identity_fpr
);
48 if (commit
->commit_ts
>= 0) {
49 log_debug(LD_DIR
, "SR: Commit: [TS: %ld] [Encoded: %s]",
50 commit
->commit_ts
, commit
->encoded_commit
);
53 if (commit
->reveal_ts
>= 0) {
54 log_debug(LD_DIR
, "SR: Reveal: [TS: %ld] [Encoded: %s]",
55 commit
->reveal_ts
, safe_str(commit
->encoded_reveal
));
57 log_debug(LD_DIR
, "SR: Reveal: UNKNOWN");
61 /* Return true iff the commit contains an encoded reveal value. */
63 commit_has_reveal_value(const sr_commit_t
*commit
)
65 return !tor_mem_is_zero(commit
->encoded_reveal
,
66 sizeof(commit
->encoded_reveal
));
69 /* Parse the encoded commit. The format is:
70 * base64-encode( TIMESTAMP || H(REVEAL) )
72 * If successfully decoded and parsed, commit is updated and 0 is returned.
73 * On error, return -1. */
75 commit_decode(const char *encoded
, sr_commit_t
*commit
)
79 /* XXX: Needs two extra bytes for the base64 decode calculation matches
80 * the binary length once decoded. #17868. */
81 char b64_decoded
[SR_COMMIT_LEN
+ 2];
86 if (strlen(encoded
) > SR_COMMIT_BASE64_LEN
) {
87 /* This means that if we base64 decode successfully the reveiced commit,
88 * we'll end up with a bigger decoded commit thus unusable. */
92 /* Decode our encoded commit. Let's be careful here since _encoded_ is
93 * coming from the network in a dirauth vote so we expect nothing more
94 * than the base64 encoded length of a commit. */
95 decoded_len
= base64_decode(b64_decoded
, sizeof(b64_decoded
),
96 encoded
, strlen(encoded
));
97 if (decoded_len
< 0) {
98 log_warn(LD_BUG
, "SR: Commit from authority %s can't be decoded.",
99 commit
->rsa_identity_fpr
);
103 if (decoded_len
!= SR_COMMIT_LEN
) {
104 log_warn(LD_BUG
, "SR: Commit from authority %s decoded length doesn't "
105 "match the expected length (%d vs %d).",
106 commit
->rsa_identity_fpr
, decoded_len
, SR_COMMIT_LEN
);
110 /* First is the timestamp (8 bytes). */
111 commit
->commit_ts
= (time_t) tor_ntohll(get_uint64(b64_decoded
));
112 offset
+= sizeof(uint64_t);
113 /* Next is hashed reveal. */
114 memcpy(commit
->hashed_reveal
, b64_decoded
+ offset
,
115 sizeof(commit
->hashed_reveal
));
116 /* Copy the base64 blob to the commit. Useful for voting. */
117 strlcpy(commit
->encoded_commit
, encoded
, sizeof(commit
->encoded_commit
));
125 /* Parse the b64 blob at <b>encoded</b> containing reveal information and
126 * store the information in-place in <b>commit</b>. Return 0 on success else
127 * a negative value. */
129 reveal_decode(const char *encoded
, sr_commit_t
*commit
)
132 /* XXX: Needs two extra bytes for the base64 decode calculation matches
133 * the binary length once decoded. #17868. */
134 char b64_decoded
[SR_REVEAL_LEN
+ 2];
139 if (strlen(encoded
) > SR_REVEAL_BASE64_LEN
) {
140 /* This means that if we base64 decode successfully the received reveal
141 * value, we'll end up with a bigger decoded value thus unusable. */
145 /* Decode our encoded reveal. Let's be careful here since _encoded_ is
146 * coming from the network in a dirauth vote so we expect nothing more
147 * than the base64 encoded length of our reveal. */
148 decoded_len
= base64_decode(b64_decoded
, sizeof(b64_decoded
),
149 encoded
, strlen(encoded
));
150 if (decoded_len
< 0) {
151 log_warn(LD_BUG
, "SR: Reveal from authority %s can't be decoded.",
152 commit
->rsa_identity_fpr
);
156 if (decoded_len
!= SR_REVEAL_LEN
) {
157 log_warn(LD_BUG
, "SR: Reveal from authority %s decoded length is "
158 "doesn't match the expected length (%d vs %d)",
159 commit
->rsa_identity_fpr
, decoded_len
, SR_REVEAL_LEN
);
163 commit
->reveal_ts
= (time_t) tor_ntohll(get_uint64(b64_decoded
));
164 /* Copy the last part, the random value. */
165 memcpy(commit
->random_number
, b64_decoded
+ 8,
166 sizeof(commit
->random_number
));
167 /* Also copy the whole message to use during verification */
168 strlcpy(commit
->encoded_reveal
, encoded
, sizeof(commit
->encoded_reveal
));
177 /* Encode a reveal element using a given commit object to dst which is a
178 * buffer large enough to put the base64-encoded reveal construction. The
179 * format is as follow:
180 * REVEAL = base64-encode( TIMESTAMP || H(RN) )
181 * Return base64 encoded length on success else a negative value.
184 reveal_encode(const sr_commit_t
*commit
, char *dst
, size_t len
)
188 char buf
[SR_REVEAL_LEN
] = {0};
193 set_uint64(buf
, tor_htonll(commit
->reveal_ts
));
194 offset
+= sizeof(uint64_t);
195 memcpy(buf
+ offset
, commit
->random_number
,
196 sizeof(commit
->random_number
));
198 /* Let's clean the buffer and then b64 encode it. */
200 ret
= base64_encode(dst
, len
, buf
, sizeof(buf
), 0);
201 /* Wipe this buffer because it contains our random value. */
202 memwipe(buf
, 0, sizeof(buf
));
206 /* Encode the given commit object to dst which is a buffer large enough to
207 * put the base64-encoded commit. The format is as follow:
208 * COMMIT = base64-encode( TIMESTAMP || H(H(RN)) )
209 * Return base64 encoded length on success else a negative value.
212 commit_encode(const sr_commit_t
*commit
, char *dst
, size_t len
)
215 char buf
[SR_COMMIT_LEN
] = {0};
220 /* First is the timestamp (8 bytes). */
221 set_uint64(buf
, tor_htonll((uint64_t) commit
->commit_ts
));
222 offset
+= sizeof(uint64_t);
223 /* and then the hashed reveal. */
224 memcpy(buf
+ offset
, commit
->hashed_reveal
,
225 sizeof(commit
->hashed_reveal
));
227 /* Clean the buffer and then b64 encode it. */
229 return base64_encode(dst
, len
, buf
, sizeof(buf
), 0);
232 /* Cleanup both our global state and disk state. */
239 /* Using <b>commit</b>, return a newly allocated string containing the commit
240 * information that should be used during SRV calculation. It's the caller
241 * responsibility to free the memory. Return NULL if this is not a commit to be
242 * used for SRV calculation. */
244 get_srv_element_from_commit(const sr_commit_t
*commit
)
249 if (!commit_has_reveal_value(commit
)) {
253 tor_asprintf(&element
, "%s%s", commit
->rsa_identity_fpr
,
254 commit
->encoded_reveal
);
258 /* Return a srv object that is built with the construction:
259 * SRV = SHA3-256("shared-random" | INT_8(reveal_num) |
260 * INT_8(version) | HASHED_REVEALS | previous_SRV)
261 * This function cannot fail. */
263 generate_srv(const char *hashed_reveals
, uint8_t reveal_num
,
264 const sr_srv_t
*previous_srv
)
266 char msg
[DIGEST256_LEN
+ SR_SRV_MSG_LEN
] = {0};
270 tor_assert(hashed_reveals
);
272 /* Add the invariant token. */
273 memcpy(msg
, SR_SRV_TOKEN
, SR_SRV_TOKEN_LEN
);
274 offset
+= SR_SRV_TOKEN_LEN
;
275 set_uint8(msg
+ offset
, reveal_num
);
277 set_uint8(msg
+ offset
, SR_PROTO_VERSION
);
279 memcpy(msg
+ offset
, hashed_reveals
, DIGEST256_LEN
);
280 offset
+= DIGEST256_LEN
;
281 if (previous_srv
!= NULL
) {
282 memcpy(msg
+ offset
, previous_srv
->value
, sizeof(previous_srv
->value
));
285 /* Ok we have our message and key for the HMAC computation, allocate our
286 * srv object and do the last step. */
287 srv
= tor_malloc_zero(sizeof(*srv
));
288 crypto_digest256((char *) srv
->value
, msg
, sizeof(msg
), SR_DIGEST_ALG
);
289 srv
->num_reveals
= reveal_num
;
293 char srv_hash_encoded
[SR_SRV_VALUE_BASE64_LEN
+ 1];
294 sr_srv_encode(srv_hash_encoded
, srv
);
295 log_debug(LD_DIR
, "SR: Generated SRV: %s", srv_hash_encoded
);
300 /* Compare reveal values and return the result. This should exclusively be
301 * used by smartlist_sort(). */
303 compare_reveal_(const void **_a
, const void **_b
)
305 const sr_commit_t
*a
= *_a
, *b
= *_b
;
306 return fast_memcmp(a
->hashed_reveal
, b
->hashed_reveal
,
307 sizeof(a
->hashed_reveal
));
310 /* Encode the given shared random value and put it in dst. Destination
311 * buffer must be at least SR_SRV_VALUE_BASE64_LEN plus the NULL byte. */
313 sr_srv_encode(char *dst
, const sr_srv_t
*srv
)
316 /* Extra byte for the NULL terminated char. */
317 char buf
[SR_SRV_VALUE_BASE64_LEN
+ 1];
322 ret
= base64_encode(buf
, sizeof(buf
), (const char *) srv
->value
,
323 sizeof(srv
->value
), 0);
324 /* Always expect the full length without the NULL byte. */
325 tor_assert(ret
== (sizeof(buf
) - 1));
326 strlcpy(dst
, buf
, sizeof(buf
));
329 /* Free a commit object. */
331 sr_commit_free(sr_commit_t
*commit
)
333 if (commit
== NULL
) {
336 /* Make sure we do not leave OUR random number in memory. */
337 memwipe(commit
->random_number
, 0, sizeof(commit
->random_number
));
341 /* Generate the commitment/reveal value for the protocol run starting at
342 * <b>timestamp</b>. <b>my_rsa_cert</b> is our authority RSA certificate. */
344 sr_generate_our_commit(time_t timestamp
, const authority_cert_t
*my_rsa_cert
)
346 sr_commit_t
*commit
= NULL
;
347 char fingerprint
[FINGERPRINT_LEN
+1];
349 tor_assert(my_rsa_cert
);
351 /* Get our RSA identity fingerprint */
352 if (crypto_pk_get_fingerprint(my_rsa_cert
->identity_key
,
353 fingerprint
, 0) < 0) {
357 /* New commit with our identity key. */
358 commit
= commit_new(fingerprint
);
360 /* Generate the reveal random value */
361 crypto_strongest_rand(commit
->random_number
,
362 sizeof(commit
->random_number
));
363 commit
->commit_ts
= commit
->reveal_ts
= timestamp
;
365 /* Now get the base64 blob that corresponds to our reveal */
366 if (reveal_encode(commit
, commit
->encoded_reveal
,
367 sizeof(commit
->encoded_reveal
)) < 0) {
368 log_err(LD_DIR
, "SR: Unable to encode our reveal value!");
372 /* Now let's create the commitment */
373 tor_assert(commit
->alg
== SR_DIGEST_ALG
);
374 /* The invariant length is used here since the encoded reveal variable
375 * has an extra byte added for the NULL terminated byte. */
376 if (crypto_digest256(commit
->hashed_reveal
, commit
->encoded_reveal
,
377 SR_REVEAL_BASE64_LEN
, commit
->alg
)) {
381 /* Now get the base64 blob that corresponds to our commit. */
382 if (commit_encode(commit
, commit
->encoded_commit
,
383 sizeof(commit
->encoded_commit
)) < 0) {
384 log_err(LD_DIR
, "SR: Unable to encode our commit value!");
388 log_debug(LD_DIR
, "SR: Generated our commitment:");
393 sr_commit_free(commit
);
397 /* Compute the shared random value based on the active commits in our state. */
401 size_t reveal_num
= 0;
402 char *reveals
= NULL
;
403 smartlist_t
*chunks
, *commits
;
404 digestmap_t
*state_commits
;
406 /* Computing a shared random value in the commit phase is very wrong. This
407 * should only happen at the very end of the reveal phase when a new
408 * protocol run is about to start. */
409 tor_assert(sr_state_get_phase() == SR_PHASE_REVEAL
);
410 state_commits
= sr_state_get_commits();
412 commits
= smartlist_new();
413 chunks
= smartlist_new();
415 /* We must make a list of commit ordered by authority fingerprint in
416 * ascending order as specified by proposal 250. */
417 DIGESTMAP_FOREACH(state_commits
, key
, sr_commit_t
*, c
) {
418 smartlist_add(commits
, c
);
419 } DIGESTMAP_FOREACH_END
;
420 smartlist_sort(commits
, compare_reveal_
);
422 /* Now for each commit for that sorted list in ascending order, we'll
423 * build the element for each authority that needs to go into the srv
425 SMARTLIST_FOREACH_BEGIN(commits
, const sr_commit_t
*, c
) {
426 char *element
= get_srv_element_from_commit(c
);
428 smartlist_add(chunks
, element
);
431 } SMARTLIST_FOREACH_END(c
);
432 smartlist_free(commits
);
435 /* Join all reveal values into one giant string that we'll hash so we
436 * can generated our shared random value. */
437 sr_srv_t
*current_srv
;
438 char hashed_reveals
[DIGEST256_LEN
];
439 reveals
= smartlist_join_strings(chunks
, "", 0, NULL
);
440 SMARTLIST_FOREACH(chunks
, char *, s
, tor_free(s
));
441 smartlist_free(chunks
);
442 if (crypto_digest256(hashed_reveals
, reveals
, strlen(reveals
),
446 tor_assert(reveal_num
< UINT8_MAX
);
447 current_srv
= generate_srv(hashed_reveals
, (uint8_t) reveal_num
,
448 sr_state_get_previous_srv());
449 sr_state_set_current_srv(current_srv
);
450 /* We have a fresh SRV, flag our state. */
451 sr_state_set_fresh_srv();
458 /* Parse a list of arguments from a SRV value either from a vote, consensus
459 * or from our disk state and return a newly allocated srv object. NULL is
462 * The arguments' order:
466 sr_parse_srv(const smartlist_t
*args
)
469 int num_reveals
, ok
, ret
;
470 sr_srv_t
*srv
= NULL
;
474 if (smartlist_len(args
) < 2) {
478 /* First argument is the number of reveal values */
479 num_reveals
= (int)tor_parse_long(smartlist_get(args
, 0),
480 10, 0, INT32_MAX
, &ok
, NULL
);
484 /* Second and last argument is the shared random value it self. */
485 value
= smartlist_get(args
, 1);
486 if (strlen(value
) != SR_SRV_VALUE_BASE64_LEN
) {
490 srv
= tor_malloc_zero(sizeof(*srv
));
491 srv
->num_reveals
= num_reveals
;
492 /* We substract one byte from the srclen because the function ignores the
493 * '=' character in the given buffer. This is broken but it's a documented
494 * behavior of the implementation. */
495 ret
= base64_decode((char *) srv
->value
, sizeof(srv
->value
), value
,
496 SR_SRV_VALUE_BASE64_LEN
- 1);
497 if (ret
!= sizeof(srv
->value
)) {
506 /* Parse a commit from a vote or from our disk state and return a newly
507 * allocated commit object. NULL is returned on error.
509 * The commit's data is in <b>args</b> and the order matters very much:
510 * algname, RSA fingerprint, commit value[, reveal value]
513 sr_parse_commit(const smartlist_t
*args
)
516 digest_algorithm_t alg
;
517 const char *rsa_identity_fpr
;
518 sr_commit_t
*commit
= NULL
;
520 if (smartlist_len(args
) < 3) {
524 /* First argument is the algorithm. */
525 value
= smartlist_get(args
, 0);
526 alg
= crypto_digest_algorithm_parse_name(value
);
527 if (alg
!= SR_DIGEST_ALG
) {
528 log_warn(LD_BUG
, "SR: Commit algorithm %s is not recognized.",
533 /* Second argument is the RSA fingerprint of the auth */
534 rsa_identity_fpr
= smartlist_get(args
, 1);
535 if (base16_decode(digest
, DIGEST_LEN
, rsa_identity_fpr
,
536 HEX_DIGEST_LEN
) < 0) {
537 log_warn(LD_DIR
, "SR: RSA fingerprint '%s' not decodable",
541 /* Let's make sure, for extra safety, that this fingerprint is known to
542 * us. Even though this comes from a vote, doesn't hurt to be
544 if (trusteddirserver_get_by_v3_auth_digest(digest
) == NULL
) {
545 log_warn(LD_DIR
, "SR: Fingerprint %s is not from a recognized "
546 "authority. Discarding commit.",
551 /* Allocate commit since we have a valid identity now. */
552 commit
= commit_new(rsa_identity_fpr
);
554 /* Third argument is the commitment value base64-encoded. */
555 value
= smartlist_get(args
, 2);
556 if (commit_decode(value
, commit
) < 0) {
560 /* (Optional) Fourth argument is the revealed value. */
561 if (smartlist_len(args
) > 3) {
562 value
= smartlist_get(args
, 3);
563 if (reveal_decode(value
, commit
) < 0) {
571 sr_commit_free(commit
);
575 /* Initialize shared random subsystem. This MUST be called early in the boot
576 * process of tor. Return 0 on success else -1 on error. */
578 sr_init(int save_to_disk
)
580 return sr_state_init(save_to_disk
, 1);
583 /* Save our state to disk and cleanup everything. */
585 sr_save_and_cleanup(void)