commit 11bfee42b4e860524ba6c8941089ae5dfed5932a Author: George Kadianakis <desnacked@riseup.net> Date: Thu Nov 12 15:46:38 2015 +0200 Fold in changes to the shared randomness proposal (prop250). - Remove majority requirement for commitments. - Remove conflict detection. - Remove the need for SR keys. - Don't use signatures in commits. - Simplify persistent state logic. - Change the protocol starting time from 12:00UTC to 00:00UTC. --- proposals/250-commit-reveal-consensus.txt | 759 +++++++++++++---------------- 1 file changed, 334 insertions(+), 425 deletions(-) diff --git a/proposals/250-commit-reveal-consensus.txt b/proposals/250-commit-reveal-consensus.txt index 0415bd8..526372d 100644 --- a/proposals/250-commit-reveal-consensus.txt +++ b/proposals/250-commit-reveal-consensus.txt @@ -5,6 +5,50 @@ Created: 2015-08-03 Status: Draft Supersedes: 225 + + Table Of Contents: + + 1. Introduction + 1.1. Motivation + 1.2. Previous work + 2. Overview + 2.1. Ten thousand feet view + 2.2. Commit & Reveal + 2.3. Consensus [CONS] + 2.4. Persistent State of the Protocol [STATE] + 3. Protocol + 3.1 Commitment Phase [COMMITMENTPHASE] + 3.1.1. Voting During Commitment Phase + 3.1.2. Persistent State During Commitment Phase [STATECOMMIT] + 3.2 Reveal Phase + 3.2.1. Voting During Reveal Phase + 3.2.2. Persistent State During Reveal Phase [STATEREVEAL] + 3.3. Shared Random Value Calculation At 00:00UTC + 3.3.1. Shared Randomness Calculation [SRCALC] + 3.4. Bootstrapping Procedure + 3.5. Rebooting Directory Authorities [REBOOT] + 3.6. Shared Randomness Disaster Recovery [SRDISASTER] + 4. Specification [SPEC] + 4.1 Voting + 4.1.1. Computing commitments and reveals [COMMITREVEAL] + 4.1.2. Validating commitments and reveals [VALIDATEVALUES] + 4.1.4. Encoding commit/reveal values in votes [COMMITVOTE] + 4.1.5. Shared Random Value [SRVOTE] + 4.1.6. Including the ed25519 identity key in votes [SRKEY] + 4.2. Persistent state format [STATEFORMAT] + 4.3. Shared Random Value in Consensus [SRCONSENSUS] + 5. Security Analysis + 5.1. Security of commit-and-reveal and future directions + 5.2. Predicting the shared random value during reveal phase + 5.3. Partition Attack + 5.3.1 During commit phase + 5.3.2 During reveal phase + 6. Discussion + 6.1. Why the added complexity from proposal 225? + 6.2. Why do you do a commit-and-reveal protocol in 24 rounds? + 6.3. Why can't we recover if we fail to do a consensus at 00:00UTC? + + 1. Introduction 1.1. Motivation @@ -16,9 +60,10 @@ Supersedes: 225 Currently we need this random value to make the HSDir hash ring unpredictable (#8244), which should resolve a wide class of hidden service DoS attacks and should make it harder for people to gauge the popularity - and activity of target hidden services. Furthermore, this random value can - be used by other Tor-related protocols (or even non-Tor-related) like - OnioNS to introduce unpredictability to the protocol. + and activity of target hidden services. Furthermore this random value can + be used by other systems in need of fresh global randomness like + Tor-related protocols (e.g. OnioNS) or even non-Tor-related (e.g. warrant + canaries). 1.2. Previous work @@ -35,9 +80,9 @@ Supersedes: 225 2. Overview - This proposal alters the Tor consensus protocol such that a random number - is generated by the directory authorities during the regular voting - process. The distributed random generator scheme is based on a + This proposal alters the Tor consensus protocol such that a random number is + generated every midnight by the directory authorities during the regular voting + process. The distributed random generator scheme is based on the commit-and-reveal technique. The proposal also specifies how the final shared random value is embedded @@ -46,14 +91,8 @@ Supersedes: 225 2.1. Ten thousand feet view Our commit-and-reveal protocol aims to produce a fresh shared random value - everyday at 12:00UTC. The final fresh random value is embedded in the - microdescriptor consensus document at that time. - - Our protocol uses a *new* consensus flavor document called "shared - randomness document" (SR doc). We use a new consensus document as a way to - keep ground truth state and also as a way to apply the majority (see - section [MAJORITY]) rule on commit and reveal values. It also allows - rebooting authorities to rejoin the protocol in some cases. + everyday at 00:00UTC. The final fresh random value is embedded in the + consensus document at that time. Our protocol has two phases and uses the hourly voting procedure of Tor. Each phase lasts 12 hours, which means that 12 voting rounds happen in @@ -61,102 +100,77 @@ Supersedes: 225 Commit phase: - Starting at 12:00UTC and for a period of 12 hours, authorities every + Starting at 00:00UTC and for a period of 12 hours, authorities every hour send their commitments in their votes. They also include any - received commitments from other authorities, if available. From those - votes, a shared random document consensus is computed containing the - commitments decided by the majority. + received commitments from other authorities, if available. Reveal phase: - At 00:00UTC, the reveal phase starts and lasts till the end of the - protocol at 12:00UTC. In this stage, authorities must reveal the value + At 12:00UTC, the reveal phase starts and lasts till the end of the + protocol at 00:00UTC. In this stage, authorities must reveal the value they committed to in the previous phase. The commitment and revealed values from other authorities, when available, are also added to the - vote. Then a shared random document consensus is computed containing - the commitments and the revealed values agreed on. + vote. Shared Randomness Calculation: - At 12:00UTC, the shared random value is computed from the agreed - revealed values located in the shared random document and finally - added to the microdescriptor consensus. + At 00:00UTC, the shared random value is computed from the agreed + revealed values and added to the consensus. - This concludes the commit-and-reveal procedure at 12:00UTC everyday. + This concludes the commit-and-reveal procedure at 00:00UTC everyday. 2.2. Commit & Reveal Our commit-and-reveal protocol aims to produce a fresh shared random value - everyday at 12:00UTC. In the beginning of that time period, each authority - generates a new random value and keeps it for the whole day. + everyday at 00:00UTC. + + In the beginning of that time period, each authority generates a new random + value and keeps it for a whole day. The authority cryptographically hashes + the random value and calls the output its "commitment" value. The original + random value is called the "reveal" value. - The authority cryptographically hashes the random value and calls the - output its "commitment" value. The original random value is called the - "reveal value". Given a reveal value you can verify that it corresponds to - a given commitment value. However given a commitment value you cannot - derive the underlying reveal value. + The idea is that given a reveal value you can cryptographically confirm that + it corresponds to a given commitment value (by hashing it). However given a + commitment value you should not be able to derive the underlying reveal + value. The construction of these values is specified in section [COMMITREVEAL]. -2.3. Microdescriptor Consensus [MDCONS] +2.3. Consensus [CONS] - Every hour, the microdescriptor consensus documents need to include the - shared random value of the day, as well as the shared random value of the - previous day. That's because either of these values might be needed at a - given time for a Tor client to access a hidden service according to section + The produced shared random value needs to be readily available to + clients. For this reason we include it in the consensus documents. + + Furthermore, every hour the consensus documents need to include the shared + random value of the day, as well as the shared random value of the previous + day. That's because either of these values might be needed at a given time + for a Tor client to access a hidden service according to section [TIME-OVERLAP] of proposal 224. These means that these two values also need - to be included in votes and in SR documents as well. + to be included in votes and in the authority state as well. - Microdescriptor consensuses include: + Hence, the consensuses include: (a) The shared random value of the current time period. This is derived from the reveal values sent by the authorities during the voting session. - (b) The shared random value of the previous time period. This is the - same shared random value that was included in the votes. + (b) The shared random value of the previous time period. + + For this, a new consensus method will be needed to indicate which authorities + support this new protocol. -2.4. Shared Random Document [SRDOC] +2.4. Persistent State of the Protocol [STATE] - The Shared Random document is a consensus flavor that contains the current - state of our commit & reveal protocol. Since it uses the consensus - mechanism of Tor, we use it as a way to enforce majority voting on the - commitments and reveals without messing with the actual network status - consensus. See section [REBOOT] for detail on how this document is handled - when an authority reboots. + A directory authority needs to keep a persistent state on disk of the on + going protocol run. This allows an authority to join the protocol in the + case of a reboot. - During the commitment phase, the SR doc is populated with the commitments - of all authorities. Then during the reveal phase, it's also used to store - the reveal values as well. + During the commitment phase, it is populated with the commitments of all + authorities. Then during the reveal phase, the reveal values are also + stored in the state. As discussed previously, the shared random values from the current and - previous time period must be present in the document at all times if they + previous time period must also be present in the state at all times if they are available. - A shared random document requires 50% + 1 authority signatures to be - considered valid. As this proposal is being written, there are 9 - authorities thus we would need 5. - -2.5. Protocol Illustration - - We have prepared an illustration to help you understand the protocol. You can - find it here: - https://people.torproject.org/~asn/hs_notes/shared_rand.jpg - - For every hour, it shows the authority votes and the resulting SR doc and - microdescriptor consensus. The chain 'A_1 -> c_1 -> r_1' denotes that the - authority committed to the value c_1 which corresponds to the reveal value - r_1. - - The illustration depicts the first 25 hours of running the protocol. It - starts with the very first commit round, then moves on to the second commit - round, and then skips directly to the last commit round. Then the reveal - phase starts, where we again show the first, second and last rounds. - - After the reveal phase is done, we generate the shared randomness (SR_1) - and we start the new commit phase. The illustration finishes with the - second round of this new commit phase. - - We advice you to revisit this after you have read the whole document. - 3. Protocol In this section we give a detailed specification of the protocol. We @@ -167,66 +181,44 @@ Supersedes: 225 3.1 Commitment Phase [COMMITMENTPHASE] - The commit phase lasts from 12:00UTC to 00:00UTC. + The commit phase lasts from 00:00UTC to 12:00UTC. + + During this phase, an authority commits a value in its vote and + saves it to the permanent state as well. - The goal is that at the end of this phase, the shared random document MUST - contain a single commitment value from each authority (or none, if that - authority did not participate in this phase). + Authorities also save any received authoritative commits by other authorities + in their permanent state. We call a commit by Alice "authoritative" if it was + included in Alice's vote. 3.1.1. Voting During Commitment Phase During the commit phase, each authority includes in its votes: - - A commitment value for this consensus period. + - The commitment value for this protocol run. - Any commitments received from other authorities. - The two previous shared random values produced by the protocol (if any). - After all votes have been received or pulled in, the authorities - collectively generate the shared random document containing the - commitments. + The commit phase lasts for 12 hours, so authorities have multiple chances to + commit their values. An authority MUST NOT commit a second value during a + subsequent round of the commit phase. -3.1.2. Shared Random Document During Commitment Phase [SRDOCCOMMIT] + if an authority publishes a second commitment value in the same + commit phase, only the first commitment should be taken in account + by other authorities. Any subsequent commitments MUST be ignored. - During the commitment phase, the shared random document contains: +3.1.2. Persistent State During Commitment Phase [STATECOMMIT] - - The commitments received by the majority of authorities - - The two previous shared random values produced by the protocol (if any). + During the commitment phase, authorities save in their persistent state the + authoritative commits they have received from each authority. Only one commit + per authority must be considered trusted and active at a given time. - A commitment should only be transcribed to the shared random document if - and only if the majority of the voting authorities agreed that a particular - commitment was sent by a particular authority. Appendix section - [COMMITEXAMPLE] contains an example of this procedure. - - The commit phase lasts for 12 hours, so authorities have multiple chances - to commit their values. An authority can commit a second value during a - subsequent round of the commit phase, but only the last value should be - transcribed to the shared random document and only if it has been seen by - the majority. - - Also, an authority should not be able to register a commitment value for a - different authority. Hence, an authority X should only vote and place in - the SR doc commitments by authority Y, iff authority Y included that - commitment in its vote. - -3.1.3. First & Last Round Of Commitment Phase [FIRSTLASTROUND] - - It's worth mentioning that during the very first round of the commitment - phase at 12:00UTC, each authority votes its own commitment and is unaware - of the commitments of the other authorities. For this reason, it's unlikely - that a majority opinion of commitments will be created at 12:00UTC. Instead - authorities are expected to form a majority opinion and transcribe - commitments to the SR doc during the voting period of 13:00UTC or at least - until the reveal phase. - - Similarly, an authority will not be able to commit to a new value during - the last round of the commitment phase. That's because there won't be - enough time for the other authorities to form a majority opinion about this - value before the reveal phase. Hence, Tor authorities SHOULD NOT commit new - values during the last round of the commitment phase at 23:00UTC. + An authority that just received a commitment from another authority's vote + MUST wait till the next voting round to include that commitment value in its + own votes. 3.2 Reveal Phase - The reveal phase lasts from 00:00UTC to 12:00UTC. + The reveal phase lasts from 12:00UTC to 00:00UTC. Now that the commitments have been agreed on, it's time for authorities to reveal their random values. @@ -239,79 +231,75 @@ Supersedes: 225 - All the commitments and reveals received from other authorities. - The two previous shared random values produced by the protocol (if any). - The set of commitments have been established during the commitment phase - and must remain the same. If an authority tries to change its commitment - during the reveal phase or introduce a new commitment, the entire vote MUST - be ignored for the purposes of this system. To do so, authorities during - the first reveal round MUST check that received votes contain the same - commitments as the last SR document of the commitment phase. In subsequent - reveal rounds, authorities check the previous hour SR document for - commitment validation. - - After all votes have been received, authorities generate the shared random - document along with the consensus. + The set of commitments have been decided during the commitment + phase and must remain the same. If an authority tries to change its + commitment during the reveal phase or introduce a new commitment, + the new commitment MUST be ignored. -3.2.2. Shared Random Document During Reveal Phase [SRDOCREVEAL] +3.2.2. Persistent State During Reveal Phase [STATEREVEAL] - During the reveal phase, the shared random document contains: + During the reveal phase, authorities keep the authoritative commits from the + commit phase in their persistent state. They also save any received reveals + that correspond to authoritative commits and are valid (as specified in + [VALIDATEVALUES]). - - The commitments agreed on during the commitment phase. - - The corresponding reveal values from the majority of authorities. - - The two previous shared random values produced by this system (if any). + An authority that just received a reveal value from another authority's vote, + MUST wait till the next voting round before including that reveal value in + its votes. - Similar to the commitment phase, authorities transcribe reveal values to - the shared random document if and only if the majority of the voting - authorities have voted on that particular reveal value. An example of this - can be seen in section [REVEALEXAMPLE]. +3.3. Shared Random Value Calculation At 00:00UTC - Section [FIRSTLASTROUND] also applies for the reveal phase. This means that - Tor authorities SHOULD NOT reveal new values during the last round of the - reveal phase at 11:00UTC. - -3.3. Shared Random Value Calculation At 12:00UTC - - Finally, at 12:00UTC every day, authorities compute a fresh shared random - value and this value must be added to the microdescriptor consensus so - clients can use it. + Finally, at 00:00UTC every day, authorities compute a fresh shared random + value and this value must be added to the consensus so clients can use it. Authorities calculate the shared random value using the reveal values in - the latest shared random document as specified in subsection [SRCALC]. + their state as specified in subsection [SRCALC]. If the shared random value contains reveal contributions by less than 3 directory authorities, it MUST NOT be created. Instead, the old shared random value should be used as specified in section [SRDISASTER]. - Authorities at 12:00UTC start including this new shared random value in + Authorities at 00:00UTC start including this new shared random value in their votes, replacing the one from two protocol runs ago. Authorities also - start including this new shared random value in the SR document and in the - microdescriptor consensus as well. + start including this new shared random value in the consensus as well. Apart from that, authorities proceed voting normally as they would in the first round of the commitment phase (section [COMMITMENTPHASE]). 3.3.1. Shared Randomness Calculation [SRCALC] - An authority that wants to derive the shared random value V, should use the - appropriate reveal values for that time period and calculate V as follows: + An authority that wants to derive the shared random value SRV, should use + the appropriate reveal values for that time period and calculate SRV as + follows. + + HASHED_REVEALS = H(ID_a | R_a | ID_b | R_b | ..) + + SRV = HMAC(HASHED_REVEALS, + "shared-random" | INT_8(reveal_num) | INT_8(version) | + previous_SRV) + + where the ID_a value is the identity key fingerprint of authority 'a' and R_a + is the corresponding reveal value of that authority for the current period. - V = H(ID_a | R_a | ID_b | R_b | ...) + Also, "reveal_num" is the number of revealed values in this construction, + "version" is the protocol version number and "previous_SRV" is the previous + shared random value if any. - where the ID_k value is the identity fingerprint of directory authority k - and R_k is its corresponding reveal value of that authority for the current - period. H is the sha256 for protocol version 1. + To maintain consistent ordering, ID_a | R_a pairs are ordered based on the + base64 encoded SR key of the authority in ascending order. - XXX Should the hashing here include more elements? Like the previous random - value for chaining? Or the current date? See how the NIST beacon does it - in case we can steal some additional RNG security properties: - http://hackaday.com/2014/12/19/nist-randomness-beacon/ + For protocol version 1, H is SHA256 and HMAC is HMAC-SHA256. + + XXX We need to make sure that all dirauths know the previous_SRV here. + Otherwise, they might partition accidentally when calculating the SRV. 3.4. Bootstrapping Procedure - As described in [MDCONS], two shared random values are required for the - HSDir overlay periods to work properly as specified in proposal 224. Hence + As described in [CONS], two shared random values are required for the HSDir + overlay periods to work properly as specified in proposal 224. Hence clients MUST NOT use the randomness of this system till it has bootstrapped completely; that is, until two shared random values are included in a - consensus. This should happen after three 12:00UTC consensuses have been + consensus. This should happen after three 00:00UTC consensuses have been produced, which takes 48 hours. 3.5. Rebooting Directory Authorities [REBOOT] @@ -319,63 +307,33 @@ Supersedes: 225 The shared randomness protocol must be able to support directory authorities who leave or join in the middle of the protocol execution. - An authority that commits in the Commitment Phase and then leaves SHOULD - store its reveal value on disk so that it continues participating in the + An authority that commits in the Commitment Phase and then leaves MUST have + stored its reveal value on disk so that it continues participating in the protocol if it returns before or during the Reveal Phase. The reveal value MUST be stored timestamped to avoid sending it on wrong protocol runs. - For this reason, other authorities should carry the commitment values of - absent authorities in the shared randomness document until the end of the - protocol. The shared randomness document can be used to verify that the - commitment values are carried properly. - - An authority that misses the Commitment Phase cannot commit anymore, so - it's unable to participate in the protocol for that run. Same thing for an - authority that misses the Reveal phase. Authorities who do not participate - in the protocol SHOULD still carry commits and reveals of others in their - vote. + An authority that misses the Commitment Phase cannot commit anymore, so it's + unable to participate in the protocol for that run. Same goes for an + authority that misses the Reveal phase. Authorities who do not participate in + the protocol SHOULD still carry commits and reveals of others in their vote. -3.6. How we define majority [MAJORITY] - - The shared randomness protocol must be able to support directory - authorities who participate in the consensus protocol but not in the shared - randomness protocol. It must also be able to tolerate authorities who drop - or join in the middle of the protocol. + Finally, authorities MUST implement their persistent state in such a way that they + will never commit two different values in the same protocol run, even if they + have to reboot in the middle (assuming that their persistent state file is + kept). A suggested way to structure the persistent state is found at [STATEFORMAT]. - The security of this proposal strongly relies on forming majority opinion - so it's important for the number of participants to always be well defined: +3.6. Shared Randomness Disaster Recovery [SRDISASTER] - In the voting session right before creating the SR doc, we define the - number of active participants to be the number of directory authorities - that included commit/reveal values in their votes. - - As specified in sections [SRDOCCOMMIT] and [SRDOCREVEAL], a commit/reveal - value should be transcribed to the SR doc if and only if the majority voted - for it. So for example, if there are 6 active participants, a commit value - will only be transcribed if 4 or more participants agreed on it. - - Furthermore, as specified in section [SRDOC], the shared random document is - considered valid only if it is signed by 50% + 1 authorities. - - XXX The number of active participants is dynamic as authorities leave and - join the protocol. Since the number of active participants is dynamic , - an attacker could trick some authorities believing there are N - participants and some others believing there are N-1 participants, by - sending different votes to different auths. Should we worry? [asn] - - A way to avoid a dynamic number of participants could be to set the - number of participants to be the number of auths who committed during the - very first commitment phase round. + If the consensus at 00:00UTC fails to be created, then there will be no fresh + shared random value for the day. -3.7. Shared Randomness Disaster Recovery [SRDISASTER] + In this case, and assuming there is a previous shared random value, directory + authorities should use the following construction as the shared random value + of the day: - If the consensus at 12:00UTC fails to be created, then there will be no new - shared random value for the day. + SRV = HMAC(previous_SRV, "shared-random-disaster") - Directory authorities should keep including the previous shared random - values in the consensus till the next 12:00UTC commit-and-reveal session. - The time period needs to be updated to reflect the current time period even - if the random value stays the same. + where "previous_SRV" is the previous shared random value. Clients should keep on using this shared random values. @@ -389,155 +347,156 @@ Supersedes: 225 authorities. Commits and reveals share the same line, but reveals are optional. -4.1.1 Encoding the authority's own commit/reveal value +4.1.1. Computing commitments and reveals [COMMITREVEAL] + + A directory authority that wants to participate in this protocol needs to + create a new pair of commitment/reveal values for every protocol + run. Authorities SHOULD generate a fresh pair of such values right before the + first commitment phase of the day (at 00:00UTC). + + The value REVEAL is computed as follows: - An authority that wants to commit (or reveal) a value during a vote, should - generate a random 256-bit value REVEAL, and include its commitment COMMIT - in its 12:00UTC vote as follows: + REVEAL = base32-encode( TIMESTAMP || RN ) - "shared-rand-commitment" SP algname SP COMMIT [SP REVEAL] NL + where RN is a 256-bit random value. - During the Reveal Phase, an authority can also optionally reveal the value - REVEAL. The "algname" is the hash algorithm that should be used to compute - COMMIT and REVEAL if any. It should be "sha256" for this version. + The value COMMIT is computed as follows: - The commitment value COMMIT is constructed as follows: + COMMIT = base32-encode( H(RN) || TIMESTAMP ) - C = base64-encode( SHA256(REVEAL) ) + where H is the hashing algorithm "sha256", and RN is the random value from + REVEAL. -4.1.2 Encoding commit/reveal values received by other authorities [COMMITOTHER] +4.1.2. Validating commitments and reveals [VALIDATEVALUES] - An authority puts in its vote the commitments and reveals it has seen from - the other authorities. To do so, it includes the following in its votes: + Authorities need to verify that the TIMESTAMP field of commitments and + reveals corresponds to the current protocol run. If an outdated COMMIT or + REVEAL value is found, it should be ignored. Corresponding COMMIT and REVEAL + values MUST have the same timestamp value. - "shared-rand-received-commitment" SP identity SP algname SP COMMIT [SP REVEAL] NL + Given a COMMIT message and a REVEAL message it should be possible to verify + that they indeed correspond. To do so, the client extracts the random value + RN from the REVEAL message, hashes it, and compares it with the H(RN) from + the COMMIT message. We say that the COMMIT and REVEAL messages correspond, if + the comparison was successful. - when "identity" is the hex-encoded commitment's authority fingerprint and - COMMIT is the received commitment value. Authorities can also optionally - include the reveal value REVEAL. There MUST be only one line per authority - else the vote is considered invalid. Finally, the "algname" is the hash - algorithm that should be used to compute COMMIT and REVEAL if any. + Authorities should ignore reveal values during the Reveal Phase that don't + correspond to commit values published during the Commitment Phase. -4.1.3. Shared Random value +4.1.4. Encoding commit/reveal values in votes [COMMITVOTE] + + An authority puts in its vote the commitments and reveals it has produced and + seen from the other authorities. To do so, it includes the following in its + votes: + + "shared-rand-commitment" SP identity SP algname SP COMMIT [SP REVEAL] NL + + where "identity" is the authority's identity key fingerprint and COMMIT is + the received encoded commitment [COMMITREVEAL]. Authorities can also + optionally include the encoded reveal value REVEAL. There MUST be only one + line per authority else the vote is considered invalid. Finally, the + "algname" is the hash algorithm that should be used to compute COMMIT and + REVEAL which is "sha256" for version 1. + +4.1.5. Shared Random Value [SRVOTE] Authorities include a shared random value in their votes using the following encoding for the previous and current value respectively: - "shared-rand-previous-value" SP value NL - "shared-rand-current-value" SP value NL + "shared-rand-previous-value" SP status SP value NL + "shared-rand-current-value" SP status SP value NL + + where "value" is the actual shared random value. It's normally computed as + specified in the section [SRCALC]. - where "value" is the actual shared random value. It's computed as specified - in the section [SRCALC]. + "status" denotes how fresh the value is. If that value was produced as + specified in section [SRCALC] then status is "fresh". If the value was + produced from a failed protocol run (as specified in [SRDISASTER]) then + status is "non-fresh". To maintain consistent ordering, the shared random values of the previous period should be listed before the values of the current period. -4.2. Shared Random Document +4.1.6. Including the ed25519 shared randomness key in votes [SRKEY] - As a way to keep ground truth state in this protocol, we introduce a new - consensus flavor document. We call it the "Shared Random Document". This - document is only used by directory authorities. + We don't want to use the legacy RSA keys as part of the shared randomness + protocol since they are going to be deprecated soon. - This new consensus flavor should be signed with the sha256 signature format - as documented in proposal 162. + For this reason we want each dirauth to include its ed25519 identity key in + its votes. To do so we include the following block in vote documents as part + of the dir-source block: -4.2.1 Format [SRFORMAT] + "signing-ed25519" NL "-----BEGIN ED25519 CERT-----" NL certificate + "-----END ED25519 CERT-----" NL - This document has a very strict format because authorities need to generate - the exact same document. - - It contains a preamble, a commitment and reveal section, a list of shared - random values and finally a footer. - - The preamble (or header) contains the following items. They MUST occur in - the order given here: + [At most once] - "shared-random-version" SP version SP flavor NL + The certificate is a base64-encoded Ed25519 certificate (see + cert-spec.txt) terminating =s removed. - [At start, exactly once.] + The certificate has CERT_TYPE of [04] and it certifies the ed25519 + master signing key under the ed25519 master key. The certificate also + includes the ed25519 master key in it certifying it under the RSA master + key (since it's included in a vote which is signed by the RSA key). - A document format version. For this specification, version is "1". The - flavor is always "shared-random". +4.2. Persistent state format [STATEFORMAT] - "created" SP YYYY-MM-DD SP HH:MM:SS NL + As a way to keep ground truth state in this protocol, an authority MUST + keep a persistent state of the protocol. The next sub-section suggest a + format for this state which is the same as the current state file format. - [Exactly once] + It contains a preamble, a commitment and reveal section and a list of + shared random values. - The creation time of this document. + The preamble (or header) contains the following items. They MUST occur in + the order given here: - "valid-until" SP YYYY-MM-DD SP HH:MM:SS NL + "Version" SP version NL - [Exactly once] + [At start, exactly once.] - After this time, this document is invalid and shouldn't be used nor - trusted. The validity time period is 3 hours. + A document format version. For this specification, version is "1". - "protocol-phase" SP phase NL + "ValidUntil" SP YYYY-MM-DD SP HH:MM:SS NL [Exactly once] - The current protocol phase when this document is generated. The accepted - values are: "commitment" and "reveal". + After this time, this state is expired and shouldn't be used nor + trusted. The validity time period is till the end of the current + protocol run (the upcoming noon). - The following details the commitment and reveal section. + The following details the commitment and reveal section. They are encoded + the same as in the vote. This makes it easier for implementation purposes. - "shared-rand-commitment" SP algname SP identity SP commitment-value - [SP revealed-value] NL + "Commitment" SP identity SP algname SP commit [SP reveal] NL [Exactly once per authority] - This is the commitment or/and reveal value agreed upon by the majority - from one authority. The algname is always "sha256" in version 1. The - "identity" is the authority hex-encoded digest of the authority - identity key of the signing authority from which the values are from. - Finally, "{commitment|revealed}-value" is the value as specified in - section [SPEC]. + The values are the same as detailed in section [COMMITVOTE]. + + This line is also used by an authority to store its own value. - Next is the shared random value section. + Finally is the shared random value section. - "shared-rand-previous-value" SP value NL + "SharedRandPreviousValue" SP status SP value NL [At most once] This is the previous shared random value agreed on at the previous - period. The "value" is defined in section [SRCALC]. + period. The fields are the same as in section [SRVOTE]. - "shared-rand-current-value" SP value NL + "SharedRandCurrentValue" SP status SP value NL [At most once] - This is the latest shared random value. The "value" is defined in - section [SRCALC]. + This is the latest shared random value. The fields are the same as in + section [SRVOTE]. - Finally, the footer of the document: - - "shared-random-footer" NL - - [Exactly once] - - It contains one subsection, the authority signatures. - - "authority-signature" SP algname SP identity SP signing-key-digest - NL Signature NL - - [Exactly once per authority] - - The "identity" is the hex-encoded digest of the authority - identity key and the "signing-key-digest" is the hex-encoded - digest of the current authority signing key of the signing - authority. - - The "algname" item is the algorithm used to compute the hash of - the document before signing it. As proposal 162 proposed, - "sha256" should be used. The authority-signature entry MUST be - ignored if "algname" is unrecognized. - - See dir-spec.txt for a specification for the Signature item. 4.3. Shared Random Value in Consensus [SRCONSENSUS] Authorities insert the two shared random values in the consensus following - the same encoding format as in [SRFORMAT]. + the same encoding format as in [SRVOTE]. 5. Security Analysis @@ -554,35 +513,7 @@ Supersedes: 225 crypto and more complex protocols so this seems like an acceptable solution for now. -5.2. Is there a need for a final agreement phase? - - Commit-and-reveal protocols usually also end with an agreement phase, - during which participants agree on which reveal values should be used to - make the shared random value. - - An agreement phase is needed, because if the protocol ended with the reveal - phase, an evil authority could wait until the last reveal round, and reveal - its value to half of the authorities. That would partition the authorities - into two sets: the ones who think that the shared random value should - contain this new reveal, and the rest who don't know about it. This would - result in a tie and two different SR docs. - - However, we believe that an agreement phase is not necessary in our - protocol since reveal values are transcribed in the SR document if only if - the majority agrees. Hence, a tie is not enough to confuse the authorities - since it's not majority and the offending value would just be discarded. - - That said, an attack that could still work here would be if an authority - can make half of the authorities believe that the value should be - discarded, and make the other half of the authorities believe that the - value should be included. That could be achieved if the attacker could - force honest authorities to send different votes to different authorities. - We believe this should not be the case currently, but we should look more - into this. - - XXX Needs feedback by a person who knows the voting protocol well!!! - -5.3. Predicting the shared random value during reveal phase +5.2. Predicting the shared random value during reveal phase The reveal phase lasts 12 hours, and most authorities will send their reveal value on the first round of the reveal phase. This means that an @@ -590,12 +521,68 @@ Supersedes: 225 it's generated. This does not pose a problem for the HSDir hash ring, since we impose an - uptime restriction on HSDir nodes, so 12 hours predictability is not an - issue. + higher uptime restriction on HSDir nodes, so 12 hours predictability is not + an issue. Any other protocols using the shared random value from this system should be aware of this property. +5.3 Partition attack + + This design is not immune to certain partition attacks. We believe they + don't offer much gain to an attacker as they are very easy to detect and + difficult to pull off since an attacker would need to compromise a directory + authority at the very least. Also, because of the byzantine general problem, + it's very hard (even impossible in some cases) to protect against all such + attacks. Nevertheless, this section describes all possible partition attack + and how to detect them. + +5.3.1 During commit phase + + A malicious directory authority could send only its commit to one single + authority which results in that authority having an extra commit value for + the shared random calculation that the others don't have. Since the + consensus needs majority, this won't affect the final SRV value. However, + the attacker, using this attack, could remove a single directory authority + from the consensus decision at 24:00 when the SRV is computed. + + An attacker could also partition the authorities by sending two + different commitment values to different authorities during the + commit phase. + + All of the above is fairly easy to detect. Commitment values in the vote + coming from an authority should NEVER be different between authorities. If + so, this means an attack is ongoing or very bad bug (highly unlikely). + +5.3.2 During reveal phase + + Let's consider Alice, a malicious directory authority. Alice could wait + until the last reveal round, and reveal its value to half of the + authorities. That would partition the authorities into two sets: the ones + who think that the shared random value should contain this new reveal, and + the rest who don't know about it. This would result in a tie and two + different shared random value. + + A similar attack is possible. For example, two rounds before the end of the + reveal phase, Alice could advertise her reveal value to only half of the + dirauths. This way, in the last reveal phase round, half of the dirauths + will include that reveal value in their votes and the others will not. In + the end of the reveal phase, half of the dirauths will calculate a + different shared randomness value than the others. + + We claim that this attack is not particularly fruitful: Alice ends up + having two shared random values to chose from which is a fundamental + problem of commit-and-reveal protocols as well (since the last person can + always abort or reveal). The attacker can also sabotage the consensus, but + there are other ways this can be done with the current voting system. + + Furthermore, we claim that such an attack is very noisy and detectable. + First of all, it requires the authority to sabotage two consensuses which + will cause quite some noise. Furthermore, the authority needs to send + different votes to different auths which is detectable. Like the commit + phase attack, the detection here is to make sure that the commiment values + in a vote coming from an authority are always the same for each authority. + 6. Discussion 6.1. Why the added complexity from proposal 225? @@ -622,91 +609,13 @@ Supersedes: 225 big problem. Also, this way we give more chances for a failing dirauth to recover and rejoin the protocol. -6.3. Why can't we recover if we fail to do a consensus at 12:00UTC? +6.3. Why can't we recover if we fail to do a consensus at 00:00UTC? - Section [SRDISASTER] specifies that if the 12:00UTC consensus or SR doc - fails to be created, we fall back to the random value of the previous day - meaning authorities will carry the last valid SR values from the previous - microdescriptor consensus to the new one. + Section [SRDISASTER] specifies that if the 00:00UTC consensus fails to be + created, we simply hash the random value of the previous day and use it as + the new shared random value. This changes the daily value but fails to make + it fresh, which is not optimal. Theoretically, we could recover by calculating the shared randomness of the - day at 13:00UTC instead. However, adding such fallback logic would + day at 01:00UTC instead. However, adding such fallback logic would complicate the protocol even further, so we have not yet considered it. - -7. Appendix - -7.1. Example commitment majority [COMMITEXAMPLE] - - Here is an example of voting during the commitment phase. The table below - represents the votes of 6 individual authorities A_i (one vote per column). - - Since it's the commitment phase, votes include the authorities commitments - and all commitments received. For example, below all authorities believe - that A_1 has registered the value 7 as its commitment. - - +------------+------------+-------------+-------------+-------------+-----------+ - | A_1 vote | A_2 vote | A_3 vote | A_4 vote | A_5 vote | A_6 vote | - +------------+------------+-------------+-------------+-------------+-----------+ - | A_1 -> 7 | A_1 -> 7 | A_1 -> 7 | A_1 -> 7 | A_1 -> 7 | A_1 -> 7 | - | A_2 -> 66 | A_2 -> 66 | A_2 -> 42 | A_2 -> 42 | A_2 -> 42 | A_2 -> 42 | - | A_3 -> 16 | A_3 -> 16 | A_3 -> 16 | A_3 -> 16 | A_3 -> 16 | A_3 -> 16 | - | A_4 -> 22 | A_4 -> 22 | A_4 -> 22 | BLANK | A_4 -> 22 | BLANK | - | A_5 -> 9 | A_5 -> 9 | A_5 -> 9 | A_5 -> 9 | A_5 -> 9 | A_5 -> 9 | - | A_6 -> 33 | A_6 -> 33 | A_6 -> 33 | A_6 -> 33 | A_6 -> 33 | BLANK | - +------------+------------+-------------+-------------+-------------+-----------+ - - In this case, following the majority rule, the final SR doc will contain: - - +-------------+ - | SR Document | - +-------------+ - | A_1 -> 7 | - | A_2 -> 42 | - | A_3 -> 16 | - | A_4 -> 22 | - | A_5 -> 9 | - | A_6 -> 33 | - +-------------+ - -7.2. Example reveal phase [REVEALEXAMPLE] - - Here is an example of voting during the reveal phase. - - The table below represents 6 votes by 6 different authorities A_i (one vote - per column). Since it's the reveal phase, votes include all reveals - received (commitments have been hidden for simplicity). For example, below - all authorities believe that A_1 has revealed the value 444. - - Let's say that a malicious dirauth is trying to partition the group into - two sets, by sending different votes to different auths. The attacker has - splitted the group into two sets, the auths who think that A_6 has revealed - the value 123, and the rest who have not seen a reveal from A_6. - - +------------+------------+-------------+-------------+-------------+------------+ - | A_1 vote | A_2 vote | A_3 vote | A_4 vote | A_5 vote | A_6 vote | - +------------+------------+-------------+-------------+-------------+------------+ - | A_1 -> 444 | A_1 -> 444 | A_1 -> 444 | A_1 -> 444 | A_1 -> 444 | A_1 -> 444 | - | A_2 -> 110 | A_2 -> 110 | A_2 -> 110 | A_2 -> 110 | A_2 -> 110 | A_2 -> 110 | - | A_3 -> 420 | A_3 -> 420 | A_3 -> 420 | A_3 -> 420 | A_3 -> 420 | A_3 -> 420 | - | BLANK | BLANK | A_4 -> 980 | BLANK | A_4 -> 980 | BLANK | - | A_5 -> 666 | A_5 -> 555 | A_5 -> 555 | A_5 -> 555 | A_5 -> 555 | A_5 -> 555 | - | A_6 -> 123 | A_6 -> 123 | A_6 -> 123 | BLANK | BLANK | BLANK | - +------------+------------+-------------+-------------+-------------+------------+ - - Following the rules of the reveal phase, the reveal of A_4 should be - ignored since it was not voted by > 3 authorities. The reveal from A_6 - should also be ignored since it was only seen by half of the auths (3/6) - which is not majority (it would require at least 4/6 votes). - - Hence, the final shared random document should contain: - - +-------------+ - | SR Document | - +-------------+ - | A_1 -> 444 | - | A_2 -> 110 | - | A_3 -> 420 | - | BLANK | - | A_5 -> 555 | - | BLANK | - +-------------+