[tor-dev] Draft Proposal: Random Number Generation During Tor Voting

Tue Aug 4 15:14:01 UTC 2015

> On 4 Aug 2015, at 22:00 , George Kadianakis <desnacked at 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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 832 bytes
Desc: Message signed with OpenPGP using GPGMail
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20150805/f20714ff/attachment.sig>