On 4 Aug 2015, at 00:32 , Ian Goldberg iang@cs.uwaterloo.ca wrote:

Nice work! A couple of minor comments:

On Mon, Aug 03, 2015 at 05:03:38PM +0300, George Kadianakis wrote:

...

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.

Careful there. "50% + 1" of 9 is 5.5, so you'd need 6. I assume you *want* to only require 5, so you should rephrase "50% + 1" (it appears a couple of times in the document).

In common usage, "50% + 1" means floor(50% + 1). But I agree this should be clarified.

...

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:

 V = H(ID_a | R_a | ID_b | R_b | ...)

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 sha256 for protocol version 1.

How do you determine what order to include the IDs and Rs in the above hash? Also, since the number of votes is not necessarily constant, I'm slightly worried about length-extension issues unless you stick an encoding of the number of votes at the beginning of the input to the hash. (And while you're at it, start with a string identifying the protocol and version as well.)

Let's follow the pattern used by other hashes in the torspec and rendspec, which is to include an uppercase string of full English words, separated by spaces, at the start of (almost all?) hashes.

...

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/

Yes, you should definitely include *something* to break the symmetry among days.

Unless there's a good reason not to include the values, using both the date and the previous random value should prevent replay-like attacks.

Regards

Tim

Tim Wilson-Brown (teor)

teor2345 at gmail dot com pgp ABFED1AC https://gist.github.com/teor2345/d033b8ce0a99adbc89c5

teor at blah dot im OTR D5BE4EC2 255D7585 F3874930 DB130265 7C9EBBC7

On 4 Aug 2015, at 22:00 , George Kadianakis desnacked@riseup.net wrote:

Hello,

and thanks for the comments.

I uploaded a new version of the proposal that addresses some of your feedback.

You can find it here: https://gitweb.torproject.org/user/asn/torspec.git/log/?h=rng-draft-v4-asn

Thanks for making these changes.

...

...

4.1.3. Shared Random value

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

where "value" is the actual shared random value. It's computed as specified in the section [SRCALC].

Is "value" encoded using base64-encode as well?

Hm, we should define this.

BTW, do we prefer base64 or base32? I would vote for base32 for readability.

Also, the few extra bytes can't be that much overhead.

I prefer base32 for readability. (Do we specify the base32 variant somewhere else? In the torspec?)

In a text-based format, with signatures and everything, the length of the commit and reveal values isn't particularly significant. In base64, a 256 bit value is 43 characters long, and in base32, it's 52 characters long. The difference is 9 characters, or 17%.

The microdescriptor consensus size is most significant, as it will be transferred many times. (The SR document will only be transferred between the authorities, so its size is much less of an issue.)

The size of the additions to the microdescriptor consensus is:

"shared-rand-previous-value" SP value NL "shared-rand-current-value" SP value NL

26 + 1 + v + 1 + 25 + 1 + v + 1 = 55 + 2v

Which is: 141 characters in base64. 159 characters in base32. A difference of 18 characters, or 11%.

A recent microdescriptor consensus was 1.25MB. 18 characters is far less than the size of a single microdescriptor consensus entry, and about a thousandth of a percent of the entire consensus size. So the difference is irrelevant, AFAICT.

...

...

3.7. Shared Randomness Disaster Recovery [SRDISASTER]

If the consensus at 12:00UTC fails to be created, then there will be no new shared random value for the day.

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.

Clients should keep on using this shared random values.

(If the timestamp is updated, clients wouldn't even know that the protocol had failed, even if they downloaded the shared randomness document, unless they specifically checked for failure.)

We could instead run an instance of the hash with an empty set of reveals like so:

V = H("TOR SHARED RANDOMNESS PROTOCOL VERSION 1" | DATE | PREVIOUS_SHARED_RANDOMNESS_VALUE)

This would gracefully degrade the protocol, and provide a predictable but different value each day, based on the previous value and the date, very much like the current HSDir hash ring.

But does this gain us anything? (The HSDirs would at least move each day, albeit predictably. We might want this property.)

I think the result here will be the same.

However, I agree that making it hard to detect failure is a bad idea. We should think of how to make this more obvious.

We could add a shared random status line to the consensus (and SR doc) giving the status of the latest completed shared random round - success, failure, bootstrap 0, or bootstrap 1.

The expected state transitions would be:

(start) -> bootstrap 0 -> bootstrap 1 -> success -> success … (failure in any state) -> failure -> success -> success …

This would allow clients to determine how reliable the shared randomness is at any point in time.

Tim (teor)

Tim Wilson-Brown (teor)

teor2345 at gmail dot com pgp ABFED1AC https://gist.github.com/teor2345/d033b8ce0a99adbc89c5

teor at blah dot im OTR D5BE4EC2 255D7585 F3874930 DB130265 7C9EBBC7

Another implementation note on directory caching of the SR doc:

I just noticed the following code in update_consensus_networkstatus_downloads():

for (i=0; i < N_CONSENSUS_FLAVORS; ++i) { /* XXXX need some way to download unknown flavors if we are caching. */

This means that any new consensus flavour will only be cached by new versions of Tor, and they will automatically cache it.

I don't think this is an issue for the SR doc - did we really want / need it cached at directory mirrors? (If not, we could modify this code to skip the SR doc.)

(If the SR doc is cached at directory mirrors, this will make different relay versions distinguishable, but I don't think we worry too much about that, as relays report their versions.)

Tim

Tim Wilson-Brown (teor)

teor2345 at gmail dot com pgp ABFED1AC https://gist.github.com/teor2345/d033b8ce0a99adbc89c5

teor at blah dot im OTR D5BE4EC2 255D7585 F3874930 DB130265 7C9EBBC7

On 12 Aug 2015, at 04:35 , George Kadianakis desnacked@riseup.net wrote:

teor teor2345@gmail.com writes:

...

Another implementation note on directory caching of the SR doc:

I just noticed the following code in update_consensus_networkstatus_downloads():

for (i=0; i < N_CONSENSUS_FLAVORS; ++i) { /* XXXX need some way to download unknown flavors if we are caching. */

This means that any new consensus flavour will only be cached by new versions of Tor, and they will automatically cache it.

I don't think this is an issue for the SR doc - did we really want / need it cached at directory mirrors? (If not, we could modify this code to skip the SR doc.)

Hm, the way we've been thinking about this, the SR doc is only useful to dirauths.

I don't think that directory mirrors or clients will ever need to download it. So I think we will indeed need to mod that code to skip the SR doc if we are not dirauths.

Of course, SR docs should be puclicly available so that CollecTor and ConsensusHealth can fetch them and analyze them.

In which case, I think we can place them in the same category as the extra-info documents, and mirror them only where we would normally mirror everything.

That way, CollecTor, ConsensusHealth, and even Onionoo and similar, need not place too much load directly on the dir auths, and can download from anywhere that hosts the extra-info docs.

Tim

Tim Wilson-Brown (teor)

teor2345 at gmail dot com pgp ABFED1AC https://gist.github.com/teor2345/d033b8ce0a99adbc89c5

teor at blah dot im OTR D5BE4EC2 255D7585 F3874930 DB130265 7C9EBBC7

On 4 Aug 2015, at 22:00 , George Kadianakis desnacked@riseup.net wrote:

...

...

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]

One scenario in which this matters is when the difference between N and N-1 is enough to make the majority vote on the shared random value either succeed or fail. This could split the authorities into two groups with different views of the protocol. …

But, from the security analysis:

...

"the protocol is insecure to the extent that an adversary who controls b of the authorities gets to choose among 2^b outcomes for the result of the protocol"

So the dynamic numbering appears to be (at most) as insecure as the rest of the protocol, as it allows a single attacker to cause half the authorities to believe failure, in certain circumstances.

...

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.

What if (too many) extra authorities arrive later in the commit phase? Does this break the majority 50% + 1 property?

Why not make it the minimum? average? maximum? of the first and second-last rounds?

This would make the value harder to manipulate in the last round, while taking into account authorities which dropped out during the phase. (Authorities which dropped out or arrived in the last round wouldn't make a difference to the set of commitments, as they come from the second-last round.) It's still somewhat dynamic, though, so this could be over-complicating things for very little benefit.

Hmm, need to think more about this.

As we discussed on #tor-dev, an attacker wants to break the consensus into two disjoint sets with two different shared random values. Causing consensus failure is also undesirable.

I've split the analysis into a number of sections, each of which elaborates on the previous section.

A. Agreement on Number of Participants

In a standard run of the protocol, where we assume every participant agrees that the number of participants is N:

A majority in the protocol with N participants is N/2 + 1 (Rounding integer divisions down, as C does.)

A.A. Commitment Phase - Agreement on Number of Participants

If A_1 is the attacker, it can give different commitments, or no commitment, to disjoint sets of authorities. There are the following cases here: 1. If no disjoint set of authorities is a majority, then A_1's commitment (or lack thereof) is not carried into the reveal phase, and it can not influence the shared random value. 2. If one disjoint set of authorities is a majority, and A_1 does not send that set a commitment, then A_1's lack of commitment is carried into the reveal phase, and it can not influence the shared random value. 3. If one disjoint set of authorities is a majority, and A_1 does send that set a commitment, then A_1's commitment to a single value is carried into the reveal phase. (It is explicit in the majority requirement of the protocol that there can only be one disjoint set of authorities with a majority.)

A.B. Reveal Phase - Agreement on Number of Participants

If, as in case 3, A_1's commitment to a single value is carried into the reveal phase, it can choose to reveal or not to reveal to each authority. There are the following cases here: 1. If A_1 doesn't reveal to a majority, then A_1's reveal is not included in the shared random value. 2. If A_1 reveals to a majority, then A_1's reveal is included in the shared random value.

A.C. Security Result - Agreement on Number of Participants

So, as described in the security analysis:

"the protocol is insecure to the extent that an adversary who controls b of the authorities gets to choose among 2^b outcomes for the result of the protocol"

A_1 gets to choose between the shared randomness value with or without its committed/revealed value, either at the commitment or reveal stage, confirming the security analysis.

B. Disagreement on Number of Participants - Single Attacker

Now, I'll redo this analysis for a run of the protocol where the attacker, A_1, can cause the participants to disagree on whether the number of participants is N or N - 1:

A majority in the protocol with N participants is N/2 + 1 A majority in the protocol with N - 1 participants is (N - 1)/2 + 1

B.A. Odd Number of Authorities - Disagreement on Number of Participants - Single Attacker

(I list the odd case first, because it is simpler.)

If N is odd, then N/2 + 1 = (N - 1)/2 + 1, and the analysis reduces to the analysis above.

B.B. Odd Number of Authorities - Disagreement on Number of Participants - Single Attacker

If N is even, then N/2 + 1 and (N - 1)/2 + 1 differ by 1, and A_1 can cause a disjoint set of authorities to require 1 less authority for a majority, by withholding a commit/reveal from those authorities. (Assuming that N can be changed at any stage.)

However, since N is even, the number of authorities remaining once a majority has received a value from A_1 is N - (N/2 + 1) = N/2 - 1. This is strictly less than (N - 1)/2 + 1, therefore, A_1 can't create two disjoint sets of authorities, both of which believe they have a majority. Therefore, the analysis reduces to the analysis above.

B.C. Actual Numbers of Authorities - Disagreement on Number of Participants - Single Attacker

I'll instantiate the analysis above using actual numbers of authorities. As the protocol requires 5 authorities, I'll give examples for 5, 6, and 7 authorities.

B.C.A. 5 Authorities - Disagreement on Number of Participants - Single Attacker

If the attacker, A_1, can cause the participants to disagree on whether the number of participants is 5 or 4: 1. A_1 can cause any of the outcomes where all authorities agree that the number of participants is 5. 2. A_1 can cause one or more authorities to believe that the number of participants is 4, and therefore fail the protocol. But A_1 could do this by itself anyway by refusing entirely to participate.

B.C.B. 6 Authorities - Disagreement on Number of Participants - Single Attacker

If the attacker, A_1, can cause the participants to disagree on whether the number of participants is 6 or 5: 1. A_1 can cause any of the outcomes where all authorities agree that the number of participants is 6. 2. A_1 can cause any of the outcomes where all authorities agree that the number of participants is 5. (Since 6 is even, then 6/2 + 1 = 4 and (6 - 1)/2 + 1 = 3. A_1 can cause disjoint sets of authorities to require 3 or 4 authorities for a majority. But, since there are only 6 authorities, and 3 + 4 is 7, A_1 can't create two disjoint majorities.)

B.C.C. 7 Authorities - Disagreement on Number of Participants - Single Attacker

If the attacker, A_1, can cause the participants to disagree on whether the number of participants is 7 or 6: 1. A_1 can cause any of the outcomes where all authorities agree that the number of participants is 7. 2. A_1 can cause any of the outcomes where all authorities agree that the number of participants is 6. (Since 7 is odd, then 7/2 + 1 = 4 and (7 - 1)/2 + 1 = 4. Therefore, A_1 can't actually cause the authorities to disagree on the number of authorities required for a majority.)

This would seem to suggest that keeping an odd number of authorities has (slightly) better security properties.

C. Disagreement on Number of Participants - Multiple Attackers

...

...

Furthermore, X colluding attackers could create this scenario when the difference between N and N-X is enough to produce the above scenario.

Does this imply a minimum number of non-colluding authorities for this protocol to be secure from X colluding authorities? If so, can we make that minimum explicit? Do we need to check for this minimum in the implementation before voting on the document? (We'd need to choose a number of colluding authorities we'd want to protect against.)

If there are multiple, colluding, attacking authorities, I speculate that:

If the attackers, A_1, A_2, … , A_X can cause the participants to disagree on whether the number of participants is N or N - X (where X is limited to (N - 1)/2, otherwise the whole consensus could be corrupted anyway):

A majority in the protocol with N participants is N/2 + 1 A majority in the protocol with N - 1 participants is (N - 1)/2 + 1 A majority in the protocol with N - 2 participants is (N - 2)/2 + 1 … A majority in the protocol with N - X participants is (N - X)/2 + 1

C.A. Even Number of Authorities - Disagreement on Number of Participants - Multiple Attackers

(I list the even case first, because it is simpler.)

If N is even, then the required majorities are in decreasing order:

N/2 + 1 (N - 1)/2 + 1

Therefore, 2 colluding authorities can make 2 disjoint sets of (N - 1)/2 + 1 authorities believe that they each have a majority.

C.A.A. 10 Authorities - Disagreement on Number of Participants - Multiple Attackers

In the case of 10 authorities, this is: 1 of the colluding authorities avoids sending a value to 5 authorities, making them believe there are 9 participating authorities, and that they have a majority of 5. The other colluding authority avoids sending a value to the other 5 authorities, making them believe there are 9 participating authorities, and that they also have a majority of 5. (This requires the colluding authorities to {pretend to} be fooled by each other.)

I think 10 is the minimum for the "even" variant of the attack, as 8 only results in dual majorities of 4, and 5 authorities are required to sign the random value in this version of the protocol. If we supply a fallback value in the absence of 5 signatures, then 8 is the minimum, as one disjoint majority would sign an actual shared random value, and the other would use the fallback.

C.B. Odd Number of Authorities - Disagreement on Number of Participants - Multiple Attackers

If N is odd, then the required majorities are in decreasing order:

N/2 + 1 = (N - 1)/2 + 1 (N - 2)/2 + 1

Therefore, 2 colluding authorities can make 2 disjoint sets of N/2 + 1 and (N - 2)/2 + 1 authorities believe that they each have a majority.

C.B.A. 9 Authorities - Disagreement on Number of Participants - Multiple Attackers

In the case of 11 authorities, this is: The 2 colluding authorities send values to 6 authorities, making them believe there are 11 participating authorities, and that they have a majority of 6. The 2 colluding authorities avoid sending a value to the other 5 authorities, making them believe there are 9 participating authorities, and that they have a majority of 5. (This requires the colluding authorities to {pretend to} participate in the 6-authority consensus.)

I think 11 is the minimum for the "odd" variant of the attack, as 9 only results in dual majorities of 5 and 4, and 5 authorities are required to sign the random value in this version of the protocol. If we supply a fallback value in the absence of 5 signatures, then 9 is the minimum, as one disjoint majority would sign an actual shared random value, and the other would use the fallback.

D. Conclusion - Multiple Attacking Authorities Considered Harmful

I am quite concerned that 2 colluding authorities can split the shared random value into two disjoint majorities.

This appears to be a serious security issue, as the required number of attacking authorities (2) doesn't depend on the number of authorities in the consensus. (Well, apart from the fact that some minimum number of authorities (10?) is required, but that is the part of the result I have least confidence in.)

However, this scenario is somewhat mitigated by the [REBOOT] part of the specification, particularly if each phase is 12 hours long, and commitments and reveals are performed ASAP. (I hadn't anticipated that early reveals were part of the security of the protocol. Since security is a higher priority than being able to predict the value as late as possible, I withdraw the changes I suggested where some authorities reveal later.)

But I'd feel much more comfortable if we could somehow reach agreement on the identities of the participating authorities as part of the protocol. Knowing how many authorities there are just isn't enough, as there can be agreement on the number of participants, but disagreement on their identities.

Can someone confirm my analysis? Can we modify the protocol to make sure that multiple colluding authorities can't split the shared random value?

Regards

Tim (teor)

Tim Wilson-Brown (teor)

teor2345 at gmail dot com pgp ABFED1AC https://gist.github.com/teor2345/d033b8ce0a99adbc89c5

teor at blah dot im OTR D5BE4EC2 255D7585 F3874930 DB130265 7C9EBBC7

I'm not a big fan of automated systems that ban authorities as it may get false positives and it may be gamed and/or attacked.

An alternative solution is to make the voting a two-step system: first you publish the sha256 hash of your vote, then a few minutes later you publish the actual vote. If they didn't match, disregard the vote.

It may be a bit more work to implement, but should prove valuable in the long run as it mitigates most cases of authorities trying to manipulate the consensus.

Tom

On 07 Sep 2015, at 09:05, s7r s7r@sky-ip.org wrote:

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256

Hi,

Sending the comments from #tor-dev here as well.

This is related to the attack where exactly half of the directory authorities commit to some values, and the last directory authority can send different values to both camps, and have the ultimate decision about the SR value. This isn't the worst thing a compromised / malicious authority could do, but this would be simple to detect and take action against, so it doesn't hurt to have it. If we see this happening in the wild, it will also warn us to take a closer look at that authority.

I think we should implement a ban score system, in which we ignore the shared randomness votes from authorities for which we see different commitment values within a close time frame:

A_1 vote: A_1 -> 7 A_2 -> 15 A_3 -> 21

A2_vote: A_1 -> 7 A_2 -> 15 A_3 -> 21

A_3 vote: A_1 -> 11 A_2 -> 15 A_3 -> 21

In this case we give a ban score of 1 to A_1. We put a timestamp on the ban-score and remember that A_1 stepped wrong for a longer period of time, maybe 30 days. If the ban score of a directory authority reaches value 2, we ignore that authority and agree on a SR value without it. Maybe we don't even need value 2 here, this shouldn't be possible to happen accidentally (need to properly document what is the behavior when an authority goes offline, OS/hardware failure, power cutoff, gets disconnected from the internet, etc. [TODO]).

For such a system to work without opening the door to other attacks, each authority needs to include in its vote the commitment values received from other authorities including their cryptographic signature (related to the identity of the authority sending the commitment value), so all other authorities can verify that a certain authority sent / signed 2 different commitment values in a short time frame, and A_3 did not lie that it received commitment value 11 from A_1, while A_2 and A_1 claim the received commitment value from A_1 is 7. Without this, any authority can increase the ban score of other authority on purpose, while the targeted authority is in fact "not guilty".

We also need a tiebreaker besides the time stamp for when we have an even number of directory authorities and exactly half of them commit to something, the other half to something else. In this case we could implement the same simple system as we currently have for relay descriptors: shortest digest value wins.

...

On 8/3/2015 5:03 PM, George Kadianakis wrote: Hello there,

we are glad to release a first draft of our proposal on distributed random generation using the Tor voting process. It specifies how Tor dirauths can generate a fresh random value every day using a commit-and-reveal protocol. The protocol piggybacks on top of the regular Tor voting procedure which happens every hour.

Our proposal spends lots of effort resolving the various edge cases and engineering issues that come up when you are trying to fit such a protocol into the Tor voting system. It also introduces a new consensus flavor document which is used to host shared randomness information, so that the regular consensus does not get affected if this feature is flawed.

We are especially interested in feedback from people who are familiar with the Tor voting protocol and can tell us whether we have messed something up, or whether there are attacks that we did not consider.

We hope the document (and the illustration) is helpful for understanding the protocol. Let us know if you have any questions, or suggestions for improving the proposal.

We believe this proposal is fundamental for the security of hidden services and for developing proposal 224, hence we invite everyone to provide feedback and improvements.

Thanks!

-----BEGIN PGP SIGNATURE----- Version: GnuPG v2.0.22 (MingW32)

iQEcBAEBCAAGBQJV7Tc8AAoJEIN/pSyBJlsRsPcH/2eVMUWpMwQBsjhbY4Qru2Q/ IWOFTQY/C3A26Su/viZASzyzV7IoLPTTokbajOOUMVe04zqD7Kl2wvXwPLZ8/LHx 06wkr4tURTM0DXwvOzhnYJPXURlxDuZwLpUjOXe7YSpHNoRkJBh+rOd+i4CBmo1E imFa1HDgkMG3zn/GErbzhEZiGUTyh9wsdGdMl4LGcqNjc+6B9Uxccq5wG6lMoSuC bj9bNFpBROzspPGrRyx/zTfpQW18AHU3G/A+A4zgOW8m53W/krZyl2MxOiLVXTWD eIvHyV9uo3FKx2Jd4eLVtbVw4/bpKq25/Au+fSlTB0smxDaKb4z77JFyoLYOiL4= =EsTQ -----END PGP SIGNATURE----- _______________________________________________ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev

On 7 Sep 2015, at 23:36, David Goulet dgoulet@ev0ke.net wrote: ... Please review it, mostly format of the state (before the SR document) has changed. As well as a new "conflict" line is added to the vote. …

If an authority sees two distinct commitments from an other authority in the same period, the authority is broken or evil: you include both, thereby proving there is a conflict:

"shared-rand-conflict" SP identity SP commit1 SP commit2 NL

where "identity" is the hex-encoded commitment's authority fingerprint. "commit1" is the previous commit that the authority had in its state and "commit2" is the new received commit of the same period. Both commit values are constructed as specified in section [COMMITENCODING].

What if there are more than two conflicting commitments? Should they all be included? Is there a denial of service opportunity here, where an authority just keeps generating commitments to fill up the state files?

When there’s a conflict, should we order the multiple different commitments in numeric order, rather than time order? Time order involves the question of which commitment was received first, which isn’t necessarily consistent between authorities. (Does it need to be? If there’s no SR doc, I guess not.)

Tim (teor)

Tim Wilson-Brown (teor)

teor2345 at gmail dot com PGP: 968F094B (ABFED1AC & A39A9058 expire 15 Sep 2015)

teor at blah dot im OTR CAD08081 9755866D 89E2A06F E3558B7F B5A9D14F (From 1 Sep 2015)

On Tue, Sep 8, 2015 at 7:10 AM, David Goulet dgoulet@ev0ke.net wrote:

On 08 Sep (01:04:36), Tim Wilson-Brown - teor wrote:

...

...

On 7 Sep 2015, at 23:36, David Goulet dgoulet@ev0ke.net wrote: ... Please review it, mostly format of the state (before the SR document) has changed. As well as a new "conflict" line is added to the vote. …

...

If an authority sees two distinct commitments from an other authority in the same period, the authority is broken or evil: you include both, thereby proving there is a conflict:

"shared-rand-conflict" SP identity SP commit1 SP commit2 NL

where "identity" is the hex-encoded commitment's authority fingerprint. "commit1" is the previous commit that the authority had in its state and "commit2" is the new received commit of the same period. Both commit values are constructed as specified in section [COMMITENCODING].

What if there are more than two conflicting commitments? Should they all be included? Is there a denial of service opportunity here, where an authority just keeps generating commitments to fill up the state files?

Hrm... that is a good point!

We could put in a maximum number of conflicts let's say 5 and add a timestamp to it (meh...). Or when voting, we only add the latest per "identity". I think the important part is just that "oh at this period, we have a proof of conclict, wtf".

It's sufficient to log two conflicting commitments per authority for the same period in order to prove that a conflict exists. There's no reason to keep more.

But tbh, I'm less and less confident about this because for example an authority voting then rebooting immediately and then voting again will trigger a conflict even though this is totally acceptable I think (assuming the initial commit value was not saved in the state on disk).

I say, "Save before publishing, and make sure you don't do two commitments for one period." Assuming this kind of accident happens very rarely, I don't think we need a way to allow it to succeed anyway.

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256

Hi,

I think we can mitigate this by implementing a p2p-like distribution system for the commitment values between the directory authorities. When an authority sends to all other authorities its commitment / reveal value, it also sends the commitment / reveal values of the other authorities it knows about (including their cryptographic signatures).

If we see more than 1 commitment value from the same authority (by verifying the signature of course) we just trigger a warning somehow in consensus health and build a consensus without the commitment of that authority. We just mark it as blank, or behave like that authority didn't send a commitment value at all, to any authority or group of authorities. At this moment the worst an evil authority could do is throw away its right to vote for the shared randomness.

This way we cannot fail to create a consensus document at 12:00 UTC and we also cannot have 2 simultaneously valid consensus documents with different shared randomness value.

On 9/9/2015 11:21 PM, George Kadianakis wrote:

Hello,

I have mixed feelings about this shared-rand-conflict mechanism. It indeed seems to solve a problem, but not the nasty one. And it's not trivial to implement.

[ Let's say we have 9 dirauths. One of them is evil. Majority needs 5 dirauths in this case. For a consensus to be considered valid, it needs 5 dirauth signatures. ]

I think the attacker we are worrying about here is the one that during the Commitment Phase attempts to partition the dirauths in two sets (4 auths in group A, and 4 auths in group B). To achieve that the attacker sends a vote with commitment c_1 to group A, and a different vote with commitment c_2 to group B.

Then in the next commitment round the attacker does the same, and now the two groups both think they have majority (group A has 4 auths and the attacker, group B the same). So they both update their internal state accordingly.

The attacker can keep on doing the same, and when the Commitment Phase is over he will have persuaded both groups that they have the right commitment, if he keeps on lying during the Reveal Phase as well (by sending the right reveal value to the two groups) he could eventually succeed in making two different consensuses with two different shared random values.

Or an alternative ending scenario would be that the attacker chooses to not publish any consensus signatures during the last round of the protocol, and then neither of the groups achieves enough signatures to make a valid consensus. And consensus at 12:00UTC fails, and no shared random for today.

---

So OK these are two reasonable attacks that shared-rand-conflict can address. The attacks are very noisy and detectable but they work. Why am I saying that shared-rand-conflcit does not mitigate everything?

It's because IIUC the attacker could also do the same attacks by following the protocol normally and then doing the partitioning attack during the last rounds of the _Reveal Phase_. In this case, the attacker partitions the dirauths into two groups by sending a reveal value to group A, and omitting it to group B. For this to work you don't need to advertise different commitments.

Again this way the result is that the attacker can get two consensuses with a different shared random value in each. One consensus will have a shared random value including the attacker's reveal value, and the other will have a shared random value without it. Alternatively, the attacker can sabotage the consensus creation by not publishing consensus signatures.

I feel that this attack during the Reveal Phase is harder to detect and more deniable.

So what can we do?

---

An alternative protection we could do about these attacks is to take this to the consensus-health layer. We need to make a few detection scripts that will notify us if any of these attacks happen. We don't need shared-rand-conflict for this.

Here are some detections that need to happen:

1. To detect attacks during the Commitment Phase, consensus-health

should warn if it sees two votes having different commitment values from one auth.

2. To detect attacks during the Reveal Phase, consensus-health

should warn if it sees two votes where one includes a reveal value, and the other one doesn't. This is a sign of a partioning attack, or some severe misconfiguration/bug.

3. Of course, consensus-health should go nuts if we don't manage to

create a 12:00UTC consensus. Don't forget that an attacker that wants to hijack the HSDir hash ring, needs to sabotage the consensus like 5 days in a row to get the HSDir flag, so this should raise some alarms.

It would also be useful if consensus-health fetched all the votes *seen* by an authority, and not just the one it publishes. This way we can find attacks where the attacker sends different votes to different honest auths. We can fetch the alien votes seen by an authority using the URL tor/status-vote/next/<fp>.z .

---

Finally, regardless of whether we do shared-rand-conflict or not, I think I like the idea of using signatures for commitments. This way, a commitment is a standalone proof that it comes from a specific authority and a specific timestamp, without requiring the whole vote signature. This is required to do shared-rand-conflict and might be useful in any case in the future.

I made a patch that implements this for prop250 at:

https://gitweb.torproject.org/user/asn/torspec.git/commit/?h=prop250-nosrdoc...

s7r told me that he likes the signature approach, and that's also what Nick did in his small proposal. Please let me know if you think this is overengineering! :)

---

Looking forward to your thoughts!

These two things seem to be the main open attacks against prop250. They don't seem particularly threatening because they are all detectable, but we should make sure we are not forgetting anything.

See you around!

On 09 Sep (23:21:03), George Kadianakis wrote:

Nick Mathewson nickm@alum.mit.edu writes:

...

On Tue, Sep 8, 2015 at 7:10 AM, David Goulet dgoulet@ev0ke.net wrote:

...

On 08 Sep (01:04:36), Tim Wilson-Brown - teor wrote:

...

...

On 7 Sep 2015, at 23:36, David Goulet dgoulet@ev0ke.net wrote: ... Please review it, mostly format of the state (before the SR document) has changed. As well as a new "conflict" line is added to the vote. …

...

If an authority sees two distinct commitments from an other authority in the same period, the authority is broken or evil: you include both, thereby proving there is a conflict:

"shared-rand-conflict" SP identity SP commit1 SP commit2 NL

where "identity" is the hex-encoded commitment's authority fingerprint. "commit1" is the previous commit that the authority had in its state and "commit2" is the new received commit of the same period. Both commit values are constructed as specified in section [COMMITENCODING].

What if there are more than two conflicting commitments? Should they all be included? Is there a denial of service opportunity here, where an authority just keeps generating commitments to fill up the state files?

Hrm... that is a good point!

We could put in a maximum number of conflicts let's say 5 and add a timestamp to it (meh...). Or when voting, we only add the latest per "identity". I think the important part is just that "oh at this period, we have a proof of conclict, wtf".

It's sufficient to log two conflicting commitments per authority for the same period in order to prove that a conflict exists. There's no reason to keep more.

...

But tbh, I'm less and less confident about this because for example an authority voting then rebooting immediately and then voting again will trigger a conflict even though this is totally acceptable I think (assuming the initial commit value was not saved in the state on disk).

I say, "Save before publishing, and make sure you don't do two commitments for one period." Assuming this kind of accident happens very rarely, I don't think we need a way to allow it to succeed anyway.

Hello,

Hi!

Thanks for this George, very thorough anlysis. Took me a while to formulate a response and lots of text came out but please read it carefully and point me wrong if needed :).

I have mixed feelings about this shared-rand-conflict mechanism. It indeed seems to solve a problem, but not the nasty one. And it's not trivial to implement.

[ Let's say we have 9 dirauths. One of them is evil. Majority needs 5 dirauths in this case. For a consensus to be considered valid, it needs 5 dirauth signatures. ]

I think the attacker we are worrying about here is the one that during the Commitment Phase attempts to partition the dirauths in two sets (4 auths in group A, and 4 auths in group B). To achieve that the attacker sends a vote with commitment c_1 to group A, and a different vote with commitment c_2 to group B.

Then in the next commitment round the attacker does the same, and now the two groups both think they have majority (group A has 4 auths and the attacker, group B the same). So they both update their internal state accordingly.

Hrm, I think you don't need to change the commitment value to make the partition attack. The attacker simply sends c_1 and c_2 once and since it's majority (group + attacker) both group will keep the value they got. Now, the attacker just needs to send both reveals to the right group and job done, two consensuses with two SR values, no?

If yes, that means that the conflict line doesn't mitigate that at all.

Maybe the majority here needs to NOT include yourself when you decide which value to use or not? For example, if we have 9 dirauths, you want 5 dirauths to agree with you *NOT* counting yourself.

9 - yourself == 8 majority --> floor(8 / 2) + 1 == 5

As a quick example on why it seems to mitigate the attack:

Group A + attacker == 5 dirauths with value c_1 Group B + attacker == 5 dirauths with value c_2

If you are in group A, you'll see 4 dirauths voting c_2 (group B) and 4 dirauths voting for c_1 (group A + attacker - yourself). No majority, reject value from attacker.

The attacker can keep on doing the same, and when the Commitment Phase is over he will have persuaded both groups that they have the right commitment, if he keeps on lying during the Reveal Phase as well (by sending the right reveal value to the two groups) he could eventually succeed in making two different consensuses with two different shared random values.

Or an alternative ending scenario would be that the attacker chooses to not publish any consensus signatures during the last round of the protocol, and then neither of the groups achieves enough signatures to make a valid consensus. And consensus at 12:00UTC fails, and no shared random for today.

---

So OK these are two reasonable attacks that shared-rand-conflict can address. The attacks are very noisy and detectable but they work. Why am I saying that shared-rand-conflcit does not mitigate everything?

The thing I like about shared-rand-conflict is that it's low effort for high reward. As an authority, you see two commits in the commitment phase, you flag it and broadcast the issue in your vote. We do not need any majority for it, as an other authority if you see a conflict line, you simply ignore that authority until the next protocol run. (HARD requirement on commits being sig. but we should do that anyway. :)

Second great thing about it, for consensus-health, it is trivial to alert us. "Oh, a conflict line in a vote, email/sms/fax/phone armadev". It would be either a very very bad bug, malicious auth (unlikely) or a dirauth in bad shape because its state on disk is borked or it's rebooting with kill -9. In any case, super useful info for us.

It's because IIUC the attacker could also do the same attacks by following the protocol normally and then doing the partitioning attack during the last rounds of the _Reveal Phase_. In this case, the attacker partitions the dirauths into two groups by sending a reveal value to group A, and omitting it to group B. For this to work you don't need to advertise different commitments.

This is in part mitigated by the fact that an authority doesn't use the received commit/reveal values until the next period of the protocol. So sending your reveal values at the last round of the reveal phase (hour minus 1), basically it will not be used by any authorities since it is the first time an authority sees it and you only want to use a value if someone else has seen that *you* have received that value.

(We've just added this constraint in the latest edits of the proposal but I realized that it should be detailed much more if we want to keep it.)

Now doing that at hour minus 2, group A receives the value for the first time, keep it in their state and at hour minus 1, it will be added to their vote and used from that point on. So group B will receive those ultimately and will be able to confirm the reveal value of the attacker that they didn't receive and use it (this seems valid because we are using a commitment value that has been decided by the majority so as long as the reveal matches, it's OK to use it).

Note that I might be mistaken here since I have a huge headache while writing this but seems that this constraint of "using only a value if the others have seen that you have it" is an important one.

Again this way the result is that the attacker can get two consensuses with a different shared random value in each. One consensus will have a shared random value including the attacker's reveal value, and the other will have a shared random value without it. Alternatively, the attacker can sabotage the consensus creation by not publishing consensus signatures.

I feel that this attack during the Reveal Phase is harder to detect and more deniable.

So what can we do?

---

An alternative protection we could do about these attacks is to take this to the consensus-health layer. We need to make a few detection scripts that will notify us if any of these attacks happen. We don't need shared-rand-conflict for this.

Here are some detections that need to happen:

1. To detect attacks during the Commitment Phase, consensus-health should warn if it sees two votes having different commitment values from one auth.

2. To detect attacks during the Reveal Phase, consensus-health should warn if it sees two votes where one includes a reveal value, and the other one doesn't. This is a sign of a partioning attack, or some severe misconfiguration/bug.

3. Of course, consensus-health should go nuts if we don't manage to create a 12:00UTC consensus. Don't forget that an attacker that wants to hijack the HSDir hash ring, needs to sabotage the consensus like 5 days in a row to get the HSDir flag, so this should raise some alarms.

It would also be useful if consensus-health fetched all the votes *seen* by an authority, and not just the one it publishes. This way we can find attacks where the attacker sends different votes to different honest auths. We can fetch the alien votes seen by an authority using the URL tor/status-vote/next/<fp>.z .

+9000.

Having consensus-health monitoring the protocol runs is crucial imo.

---

Finally, regardless of whether we do shared-rand-conflict or not, I think I like the idea of using signatures for commitments. This way, a commitment is a standalone proof that it comes from a specific authority and a specific timestamp, without requiring the whole vote signature. This is required to do shared-rand-conflict and might be useful in any case in the future.

I made a patch that implements this for prop250 at:

https://gitweb.torproject.org/user/asn/torspec.git/commit/?h=prop250-nosrdoc-sigs&id=80ed03b4ac40db62582b4af2e3c5c7702c453055

s7r told me that he likes the signature approach, and that's also what Nick did in his small proposal. Please let me know if you think this is overengineering! :)

Again, +1. Little effort for extra safety. Quite happy with your edit above.

Cheers! David

---

Looking forward to your thoughts!

These two things seem to be the main open attacks against prop250. They don't seem particularly threatening because they are all detectable, but we should make sure we are not forgetting anything.

See you around! _______________________________________________ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev

-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA256

I disagree. can you describe how exactly? What exactly can be gamed, if we use the protection described by me? It will provide the same security as directory authorities already have for voting about relays. It's true that ultimately anything can be gamed, but if it's not trivial to do or likely to happen this is an option we rather have than not have.

...

Quote: I'm not a big fan of automated systems that ban authorities as it may get false positives and it may be gamed and/or attacked.

An alternative solution is to make the voting a two-step system: first you publish the sha256 hash of your vote, then a few minutes later you publish the actual vote. If they didn't match, disregard the vote.

It may be a bit more work to implement, but should prove valuable in the long run as it mitigates most cases of authorities trying to manipulate the consensus.

Tom

George Kadianakis desnacked@riseup.net writes:

...

Hello there,

Hello,

I'm inlining the latest version of proposal250.

It includes various improvements, like completely removing the need for an SR doc (which will make implementation much much easier), and switching to signature-based commitments which are attributable and easier to audit. Also the voting rules have been fleshed out to counter some partioning attacks.

You can also find it in git form here: https://gitweb.torproject.org/user/asn/torspec.git/log/?h=prop250-asn

(lots of text sorry but this is important).

Ok I had an epiphany while eating my lunch. The partition attack is actually not mitigated with this requirement: "don't use a value until you broadcast it if seen for first time".

For the purpose of the example, we have two groups, A and B composed of each 4 authorities and X is the malicious authority (the 9th one). We are in the reveal phase of the protocol at hour - 2 (10:00UTC).

At hour - 2, X broadcast its reveal value r_x to group A.

Group A sees r_x for the first time so keep it in memory and wait until the next voting period at hour - 1 to broadcast the value before using it.

At hour - 1, group A broadcast r_x and thus can start using it.

At hour - 1, group B receives r_x from group A, saves it to memory and wait to broadcast it until the next voting period (so they can use it).

At hour - 0 (12:00UTC), group B has r_x in memory and *COULD* use it if it could broadcast it _but_ at this time, all authorities should compute the shared random value and start a new protocol run. So r_x is NOT put into the vote of group B thus theoritically, they can NOT use that value for the SR.

-> Partition attack completed. Group A sees r_x with majority but not group B.

Ok ok... now how can we mitigate that. I think we should change the "seen for the first time" requirement to "seen for the first time and only once in a voting period".

In the example above, I think group B could have use r_x right away because they basically got 4 votes (all from group A) with r_x in there. It means that for the value r_x, it has been seen four times (yes in the same period but that's not important). It's pretty different then "Oh I've seen r_x but from only one vote in this period" which can be an attempt to trick me as an authority so I must inform the others of what I just got.

In a nutshell, if a value arrives in multiple vote for the same period, it's OK to use it right away but if only seen once for the first time in a single period, the requirement is to wait-until-broadcast. (Same goes for commit and reveal). It comes back bit into the indirect/direct vote discussion on when we are allow to use the value.

Requirement becomes: "Don't use a value until you broadcast it to the others iff it has been seen for the first time and only once for a single period."

If I have not completely fuck it up, I think it's a very light addition to the requirement for which we have great benefit :).

Cheers! David

Enjoy!

---

Filename: 250-commit-reveal-consensus.txt Title: Random Number Generation During Tor Voting Authors: David Goulet, George Kadianakis Created: 2015-08-03 Status: Draft

1. Introduction

1.1. Motivation

For the next generation hidden services project, we need the Tor network to produce a fresh random value every day in such a way that it cannot be predicted in advance or influenced by an attacker.

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 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

Proposal 225 specifies a commit-and-reveal protocol that can be run as an external script and have the results be fed to the directory authorities. However, directory authority operators feel unsafe running a third-party script that opens TCP ports and accepts connections from the Internet. Hence, this proposal aims to embed the commit-and-reveal idea in the Tor voting process which should makes it smoother to deploy and maintain.

Another idea proposed specifically for Tor is Nick Hopper's "A threshold signature-based proposal for a shared RNG" which was never turned into an actual Tor proposal.

2. Overview

This proposal alters the Tor consensus protocol such that a random number is generated every noon 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 in consensus documents so that clients who need it can get it.

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 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 between. In short, the protocol works as follows:

 Commit phase:

   Starting at 12: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.

 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
   they committed to in the previous phase. The commitment and revealed
   values from other authorities, when available, are also added to the
   vote.

 Shared Randomness Calculation:

   At 12: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.

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. The authority cryptographically signs a hash of the random value and calls the output its "commitment" value. The original random value is called the "reveal" value.

The idea is that given a reveal value you can cryptographically confirm that it corresponds to a given commitment value. 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. Consensus [CONS]

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 the authority state as well.

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.

For this, a new consensus method will be needed to indicate which authorities support this new protocol.

2.4. Persistent State of the Protocol [STATE]

A directory authority needs to keep a persistent state on disk of the on going protocol phases. This allows an authority to join the protocol in the case of a reboot.

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 also be present in the state at all times if they are available.

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, the resulting state (SR) and 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 describe the protocol participants' logic and the messages they send. The encoding of the messages is specified in the next section ([SPEC]).

Now we go through the phases of the protocol:

3.1 Commitment Phase [COMMITMENTPHASE]

The commit phase lasts from 12:00UTC to 00:00UTC.

During this phase, an authority commits a value in its vote and saves it to its state as well. Authorities decide which commits are active at any given time through majority voting.

3.1.1. Voting During Commitment Phase

During the commit phase, each authority includes in its votes:

• A commitment value for this consensus period.
• Any commitments received from other authorities.
• The two previous shared random values produced by the protocol (if any).

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 (see [COMMITCONFLICT]).

3.1.2. Persistent State During Commitment Phase [STATECOMMIT]

During the commitment phase, an authority state contains:

• The active commitments (one per auth) agreed by the majority of authorities
• The two previous shared random values produced by the protocol (if any).

All received commitments MUST first be verified according to [VALIDATEVALUES].

A commitment MUST only be transcribed to permanent state 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.

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.

An authority transcribes a foreign commitment value to permanent state, only after that commitment value has been broadcasted personally by that authority. For example, if A_1 receives c_2 from A_2 for the first time, it MUST not write c_2 to permanent state until it's put in A_1's vote and sent out to the other authorities.

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 not possible that a majority opinion about commitments will be created at 12:00UTC. Instead authorities are expected to form a majority opinion and transcribe commitments to their state 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.

3.2 Reveal Phase

The reveal phase lasts from 00:00UTC to 12:00UTC.

Now that the commitments have been agreed on, it's time for authorities to reveal their random values.

3.2.1. Voting During Reveal Phase

During the reveal phase, each authority includes in its votes:

• Its reveal value that was previously committed in the commit phase.
• 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 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, it should be flagged as a conflict (see [COMMITCONFLICT]) and the authority should be ignored until the next protocol run.

Authorities during the first reveal round MUST verify that received votes contain the same commitments as the ones in their state (built during the last commitment round).

3.2.2. Persistent State During Reveal Phase [STATEREVEAL]

During the reveal phase, the state contains:

• The commitments agreed on during the commitment phase.
• The corresponding reveal values
• The two previous shared random values produced by this system (if any).

Reveal values don't require majority voting to be valid. Instead they MUST be verified and matched to a commitment value as specified in [VALIDATEVALUES].

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.

An authority transcribes a foreign reveal value to permanent state, only after that reveal value has been broadcasted personally by that authority.

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 consensus so clients can use it.

Authorities calculate the shared random value using the reveal values in 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 their votes, replacing the one from two protocol runs ago. Authorities also 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 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_SR)

where the ID_a value is the identity fingerprint of directory authority 'a' and R_a is the corresponding reveal value of that authority for the current period.

Also, "reveal_num" is the number of revealed values in this construction, "version" is the protocol version number and "previous_SR" is the previous shared random value if any.

To maintain consistent ordering, ID_a | R_a pairs are ordered based on the identity fingerprint of the authority in ascending order.

For protocol version 1, H is SHA256 and HMAC is HMAC-SHA256.

3.4. Bootstrapping Procedure

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 produced, which takes 48 hours.

3.5. Rebooting Directory Authorities [REBOOT]

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 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 their persistent state until the end of the protocol.

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.

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:

In each voting session we define the number of active participants to be the number of directory authorities that included their *own* commit/reveal values in their votes.

As specified in sections [STATECOMMIT] and [STATEREVEAL], a commit/reveal value should be transcribed to the an authority state iff 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.

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.

3.7. Shared Randomness Disaster Recovery [SRDISASTER]

If the consensus at 12:00UTC fails to be created, then there will be no fresh shared random value for the day.

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:

  SRV = HMAC(previous_SR, "shared-random-disaster")

where "previous_SR" is the previous shared random value.

Clients should keep on using this shared random values.

4. Specification [SPEC]

4.1 Voting

This section describes how commitments, reveals and SR values are encoded in votes. We describe how to encode both the authority's own commits/reveals and also the commits/reveals received from the other authorities. Commits and reveals share the same line, but reveals are optional.

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 12:00UTC).

The procedure is as follows: 1. Authority generates a fresh 256-bit random value RN. 2. Authority uses RN to derive REVEAL (see below). 3. Authority uses REVEAL to derive COMMIT (see below).

The value REVEAL is computed as follows:

 REVEAL = base64-encode( TIMESTAMP || RN )

 where TIMESTAMP is a big-endian unsigned 64 bit integer being the number
 of seconds since the Unix epoch. RN is the 256-bit random value RN.

The value COMMIT is computed as follows:

 SIGNATURE = ed25519-sign( privkey=PRIVKEY, msg=H(REVEAL) || TIMESTAMP )
 COMMIT = base64-encode( TIMESTAMP || H(REVEAL) || SIGNATURE )

 where PRIVKEY is the identity key of the authority that is used to sign
 the vote documents. TIMESTAMP is the same as the one used for REVEAL.
 H is the hashing algorithm "sha256".

4.1.2. Validating commitments and reveals [VALIDATEVALUES]

When authorities receive a COMMIT value, they need to verify the signature and ensure that the TIMESTAMP field corresponds ot the current protocol run. The same timestamp check should be done on REVEAL values. If an outdated COMMIT or REVEAL value is found, it should be ignored.

Given a COMMIT value, if you later receive its REVEAL value it should be possible to verify that they indeed correspond. This can be done as follows:

 TIMESTAMP_R || RN = base64-decode(REVEAL)
 TIMESTAMP_C || COMMIT_SIG = base64-decode(COMMIT)

 return ed25519-verify( pubkey=PUBKEY, sig=COMMIT_SIG,
                        msg=H(RN) || TIMESTAMP )

 where PUBKEY is the identity public key of the authority revealing its
 value. H is the hashing algorithm "sha256".

 TIMESTAMP_R must be equal to TIMESTAMP_C else REVEAL is an invalid value
 for COMMIT.

Authorities should ignore reveal values during the Reveal Phase that don't correspond to commit values published during the Commitment Phase.

4.1.3. Encoding the authority's own commit/reveal value

The commitment value COMMIT (as computed in [COMMITREVEAL]) should be included on votes as follows:

 "shared-rand-commitment" SP algname SP COMMIT [SP REVEAL] NL

During the Reveal Phase, an authority can also optionally publish its reveal value REVEAL. The "algname" is the hash algorithm that should be used to compute COMMIT and REVEAL if any. It should be "sha256" for version 1.

4.1.4. Encoding commit/reveal values received by other authorities [COMMITOTHER]

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:

 "shared-rand-received-commitment" SP identity SP algname SP
                                      COMMIT [SP REVEAL] NL

where "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 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 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].

"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.1.6. Conflict [COMMITCONFLICT]

If an authority sees two distinct commitments from an other authority, that authority is broken or evil: you include both commits, thereby proving there is a conflict:

 "shared-rand-conflict" SP identity SP commit1 SP commit2 NL

where "identity" is the hex-encoded commitment's authority fingerprint. "commit1" is the previous commit that the authority had in its state and "commit2" is the new received commit of the same period. Both commit values are constructed as specified in section [COMMITREVEAL].

A conflict can occur if: - An authority sends two different values during the commitment phase. - An authority sends a new commit value during the reveal phase. - A commit value seen by other authorities that doesn't match the value in the authority's persistent state.

It is possible for an authority to vote multiple times in the same voting period so only the latest commitment conflict should be added to the vote. The point of this line is to notify that a conflict happened and not list them all.

When a conflict line is seen in a vote, an authority should verify the commit values (see [VALIDATEVALUES]) that they are in fact coming from the authority identified by "identity" and if so, ignore that authority until the next protocol run. If the conflict line is invalid, ignore it.

4.2. Persistent State

As a way to keep ground truth state in this protocol, an authority MUST keep a persistent state of the protocol.

4.2.1 Format [STATEFORMAT]

It contains a preamble, a commitment and reveal section and a list of shared random values.

The preamble (or header) contains the following items. They MUST occur in the order given here:

"shared-random-version" SP version NL

   [At start, exactly once.]

   A document format version. For this specification, version is "1".

"valid-until" SP YYYY-MM-DD SP HH:MM:SS NL

   [Exactly once]

   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).

"protocol-phase" SP phase NL

   [Exactly once]

   The current protocol phase when this document is generated. The
   accepted values are: "commitment" and "reveal".

The following details the commitment and reveal section.

"shared-rand-commitment" SP algname SP identity SP
                         YYYY-MM-DD SP HH:MM:SS SP
                         commitment-value [SP revealed-value] 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].

   This line is also used by an authority to store its own value.

Finally is the shared random value section.

"shared-rand-previous-value" SP status SP value NL

   [At most once]

   This is the previous shared random value agreed on at the previous
   period. The fields are the same as in section [SRVOTE].

"shared-rand-current-value" SP status SP value NL

   [At most once]

   This is the latest shared random value. The fields are the same as in
   section [SRVOTE].

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].

5. Security Analysis

5.1. Security of commit-and-reveal and future directions

The security of commit-and-reveal protocols is well understood, and has certain flaws. Basically, the protocol is insecure to the extent that an adversary who controls b of the authorities gets to choose among 2^b outcomes for the result of the protocol. However, an attacker who is not a dirauth should not be able to influence the outcome at all.

We believe that this system offers sufficient security especially compared to the current situation. More secure solutions require much more advanced 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 shared random value.

However, we believe that an agreement phase is not necessary in our protocol since reveal values are choosen 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

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 attacker can predict the final shared random value about 12 hours before it's generated.

This does not pose a problem for the HSDir hash ring, since we impose an 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.

6. Discussion

6.1. Why the added complexity from proposal 225?

The complexity difference between this proposal and prop225 is in part because prop225 doesn't specify how the shared random value gets to the clients. This proposal spends lots of effort specifying how the two shared random values can always be readily accessible to clients.

6.2. Why do you do a commit-and-reveal protocol in 24 rounds?

The reader might be wondering why we span the protocol over the course of a whole day (24 hours), when only 3 rounds would be sufficient to generate a shared random value.

We decided to do it this way, because we piggyback on the Tor voting protocol which also happens every hour.

We could instead only do the shared randomness protocol from 21:00 to 00:00 every day. Or to do it multiple times a day.

However, we decided that since the shared random value needs to be in every consensus anyway, carrying the commitments/reveals as well will not be a 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?

Section [SRDISASTER] specifies that if the 12: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 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 values used are:

                                +-------------+
                                | 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 be broadcasted by A_1, A_2 and A_3 during the reveal phase thus making the rest of the authorities see it at some point. Remember that for a reveal to be used by an authority, no majority is needed, it just need to be verified and used if the commit value was choosen by the majority.

Hence, the final values that must be used are:

                                +-------------+
                                | A_1 -> 444  |
                                | A_2 -> 110  |
                                | A_3 -> 420  |
                                | BLANK       |
                                | A_5 -> 555  |
                                | A_6 -> 123  |
                                +-------------+

---

tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev