[tor-dev] Update of prop#250: Random Number Generation During Tor Voting
David Goulet
dgoulet at ev0ke.net
Wed Oct 28 18:26:36 UTC 2015
Hello Tor-Dev!
We've almost completed the implementation [1] for prop#250 so we've
reviewed part of the proposal to correct part of it to reflect reality
(because you know a proposal is just wishful thinking until you
implement it :).
Attached is the new version that we've been working on. We would like
feedback from the community before at least calling it "ACCEPTED" and
updated in tor-spec.git [2].
Here is a small summary of the big changes and also we need feedback on
something that we are not fully in agreement.
First, period have been changed from 12:00 -> 12:00 (24 hour) to 00:00
-> 24:00 so the protocol run is not over two days. Seemed more logical
and less confusing :).
Second, we've removed the need of having majority for a commit to be
considered for the shared random computation. Yes this sounds intense!!
so it needs your attention. We think that majority concept was only
protecting us against was a partition attack during commit phase but it
turns out that having a conflict detection mechanism (see COMMITCONFLICT
section) already protect us of most of them during the commit phase
except maybe one that is described in Section 5.3.1. With this proposal
change, an authority only keeps commits that are authoritative that is a
commit coming directly from an authority.
We've added section 5.3 on Partition Attack. Choosing commit by majority
was protecting us against a partition attack in the commit phase but not
all so with or without it, we still need an external monitoring party
that makes sure attack are not ongoing (or bugs). DocTor is the obvious
candidate so we'll work on a partition attacks detection since all of
them are noisy and detectable.
A sub-section (4.1.7) has also been added which address the need of a
shared random key that signs the commit values so they can be verified
by other authorities [3].
Finally, we would like your opinion also on if we should keep the
conflict mechanism or not?. Since those partition attacks are basically
dumb, do not achive much result for an attacker and it's at a high cost
of comprimising a directory authority, should we keep them? Keep in mind
that it adds a layer of complexity in the code especially with shared
random keys which rotates every 30 days and are only available in the
vote of an authority. It gets difficult to validate a conflict of an
authority if we haven't seen yet a vote from that authority. There are
ways to fix that code wise but is this worth it considering that every
partition attack will be detected anyway by DocTor? One argument to keep
it is resilience of the protocol. With conflict line, if one dirauth
does stupid things, it will get ignored for the rest of the protocol run
so we can still compute a fresh random value in the end. Again, does it
worth it?
Don't hesitate to ask about sections that are not clear or could be
incorrect or you do not understand fully. Also, a ACK is a valid reply
:).
Thanks to all! David
[1] https://trac.torproject.org/projects/tor/ticket/16943
[2] https://gitweb.torproject.org/torspec.git/tree/proposals/250-commit-reveal-consensus.txt
[3] https://trac.torproject.org/projects/tor/ticket/17349
-------------- next part --------------
Filename: 250-commit-reveal-consensus.txt
Title: Random Number Generation During Tor Voting
Authors: David Goulet, George Kadianakis
Created: 2015-08-03
Status: Draft
Table Of Contents:
1. Introduction
1.1. Motivation
1.2. Previous work
2. Overview
2.1. Ten thousand feet view
2.2. Commit & Reveal
2.3. Consensus [CONS]
2.4. Persistent State of the Protocol [STATE]
2.5. Protocol Illustration
3. Protocol
3.1 Commitment Phase [COMMITMENTPHASE]
3.1.1. Voting During Commitment Phase
3.1.2. Persistent State During Commitment Phase [STATECOMMIT]
3.2 Reveal Phase
3.2.1. Voting During Reveal Phase
3.2.2. Persistent State During Reveal Phase [STATEREVEAL]
3.3. Shared Random Value Calculation At 00:00UTC
3.3.1. Shared Randomness Calculation [SRCALC]
3.4. Bootstrapping Procedure
3.5. Rebooting Directory Authorities [REBOOT]
3.6. Shared Randomness Disaster Recovery [SRDISASTER]
4. Specification [SPEC]
4.1 Voting
4.1.1. Computing commitments and reveals [COMMITREVEAL]
4.1.2. Validating commitments and reveals [VALIDATEVALUES]
4.1.4. Encoding commit/reveal values in votes [COMMITVOTE]
4.1.5. Shared Random Value [SRVOTE]
4.1.6. Conflict [COMMITCONFLICT]
4.1.7. Including the ed25519 shared randomness key in votes [SRKEY]
4.2. Persistent State
4.2.1 Format [STATEFORMAT]
4.3. Shared Random Value in Consensus [SRCONSENSUS]
5. Security Analysis
5.1. Security of commit-and-reveal and future directions
5.2. Predicting the shared random value during reveal phase
5.3. Partition Attack
5.3.1 During commit phase
5.3.2 During reveal phase
6. Discussion
6.1. Why the added complexity from proposal 225?
6.2. Why do you do a commit-and-reveal protocol in 24 rounds?
6.3. Why can't we recover if we fail to do a consensus at 00:00UTC?
1. Introduction
1.1. Motivation
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 midnight by the directory authorities during the regular voting
process. The distributed random generator scheme is based on the
commit-and-reveal technique.
The proposal also specifies how the final shared random value is embedded
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 00:00UTC. The final fresh random value is embedded in the
consensus document at that time.
Our protocol has two phases and uses the hourly voting procedure of Tor.
Each phase lasts 12 hours, which means that 12 voting rounds happen in
between. In short, the protocol works as follows:
Commit phase:
Starting at 00:00UTC and for a period of 12 hours, authorities every
hour send their commitments in their votes. They also include any
received commitments from other authorities, if available.
Reveal phase:
At 12:00UTC, the reveal phase starts and lasts till the end of the
protocol at 00:00UTC. In this stage, authorities must reveal the value
they committed to in the previous phase. The commitment and revealed
values from other authorities, when available, are also added to the
vote.
Shared Randomness Calculation:
At 00:00UTC, the shared random value is computed from the agreed
revealed values and added to the consensus.
This concludes the commit-and-reveal procedure at 00:00UTC everyday.
2.2. Commit & Reveal
Our commit-and-reveal protocol aims to produce a fresh shared random value
everyday at 00: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 run. 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 00:00UTC to 12:00UTC.
During this phase, an authority commits a value in its vote and
saves it to the permanent state as well.
Authorities also save any received authoritative commits by other
authorities in their permanent state. We call a commit by Alice
"authoritative" if was signed by Alice's shared randomness key and
also included in Alice's vote.
3.1.1. Voting During Commitment Phase
During the commit phase, each authority includes in its votes:
- The commitment value for this protocol run.
- Any commitments received from other authorities.
- The two previous shared random values produced by the protocol (if any).
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 authoritative commitments (one per auth).
- 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 it
is an authoritative commit.
An authority that just received a commitment from another authority's vote
MUST wait till the next voting round to include that commitment value in its
own votes.
3.2 Reveal Phase
The reveal phase lasts from 12:00UTC to 00: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 value 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.
3.3. Shared Random Value Calculation At 00:00UTC
Finally, at 00:00UTC every day, authorities compute a fresh shared random
value and this value must be added to the consensus so clients can use it.
Authorities calculate the shared random value using the reveal values in
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 00:00UTC start including this new shared random value in
their votes, replacing the one from two protocol runs ago. Authorities also
start including this new shared random value in the 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_SRV)
where the ID_a value is the base64 encoded SR key [SRKEY] of the 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_SRV" is the previous
shared random value if any.
To maintain consistent ordering, ID_a | R_a pairs are ordered based on the
base64 encoded SR key 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 00: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. Shared Randomness Disaster Recovery [SRDISASTER]
If the consensus at 00: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_SRV, "shared-random-disaster")
where "previous_SRV" 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 00: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 RN is the 256-bit random value RN, and TIMESTAMP is a 64-bit Unix
timestamp that points to the current protocol run (so it's between 00:00
and 24:00 of that day).
The value COMMIT is computed as follows:
SIGNATURE = ed25519-sign( privkey=PRIVKEY, msg=H(REVEAL) || TIMESTAMP )
COMMIT = base64-encode( H(REVEAL) || TIMESTAMP || SIGNATURE )
where the signature is performed using a special shared randomness ed25519
key [SRKEY]. TIMESTAMP MUST be 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(REVEAL) || TIMESTAMP_C )
where PUBKEY is the public key of the shared randomness ed25519 key
[SRKEY] and 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.4. Encoding commit/reveal values in votes [COMMITVOTE]
An authority puts in its vote the commitments and reveals it has produced and
seen from the other authorities. To do so, it includes the following in its
votes:
"shared-rand-commitment" SP identity SP algname SP COMMIT [SP REVEAL] NL
where "identity" is the base64 encoded commitment's authority SR key
[SRKEY] and COMMIT is the received encoded commitment [COMMITREVEAL].
Authorities can also optionally include the encoded reveal value REVEAL.
There MUST be only one line per authority else the vote is considered
invalid. Finally, the "algname" is the hash algorithm that should be used
to compute COMMIT and REVEAL which is "sha256" for version 1.
4.1.5. Shared Random Value [SRVOTE]
Authorities include a shared random value in their votes using the following
encoding for the previous and current value respectively:
"shared-rand-previous-value" SP 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 base64 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.1.7. Including the ed25519 shared randomness key in votes [SRKEY]
We don't want to use the master or signing key of the dirauth to sign the
commitments because those keys can also be kept offline for greater security.
Hence each dirauth will generate a special ed25519 key specifically for
shared randomness purposes. Its lifetime should be medium-term similar to the
lifetime of the signing key.
The shared randomness key needs to be included in the votes of each
authority, as well as the certificates required to bind it with the RSA
master key. We basically need the following chain:
[RSA master key -> ed25519 master key -> ed25519 signing key -> ed25519 shared randomness key]
To do so, we include the following two fields in vote documents as part
of the dir-source block:
"signing-ed25519" NL "-----BEGIN ED25519 CERT-----" NL certificate
"-----END ED25519 CERT-----" NL
[At most once]
The certificate is a base64-encoded Ed25519 certificate (see
cert-spec.txt) terminating =s removed.
The certificate has CERT_TYPE of [04] and it certifies the ed25519
master signing key under the ed25519 master key. The certificate also
includes the ed25519 master key in it certifying it under the RSA master
key (since it's included in a vote which is signed by the RSA key).
"shared-random-ed25519" NL "-----BEGIN ED25519 CERT-----" NL certificate
"-----END ED25519 CERT-----" NL
[At most once]
The certificate is a base64-encoded Ed25519 certificate (see
cert-spec.txt) terminating =s removed.
The certificate has CERT_TYPE of [04] and it certifies the ed25519
shared randomness key under the ed25519 singing key.
This last certificate completes the chain and allows dirauths to extract the
ed25519 shared randomness key.
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. The next sub-section suggest a
format for this state which is the same as the current state file format.
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:
"Version" SP version NL
[At start, exactly once.]
A document format version. For this specification, version is "1".
"ValidUntil" 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).
"ProtocolPhase" SP phase NL
[Exactly once]
The current protocol phase when this document is generated. The
accepted values are: "commit" and "reveal". This is mostly used for
human to be able to know that phase the state was last in.
The following details the commitment and reveal section. They are encoded
the same as in the vote. This makes it easier for implementation purposes.
"Commitment" SP identity SP algname SP commit [SP reveal] NL
[Exactly once per authority]
The values are the same as detailed in section [COMMITVOTE].
This line is also used by an authority to store its own value.
"Conflict" SP identity SP commit1 SP commit2 NL
[At most once per authority if any]
The values are the same as detailed in section [COMMITCONFLICT].
Finally is the shared random value section.
"SharedRandPreviousValue" 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].
"SharedRandCurrentValue" 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. 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.
5.3 Partition attack
This design is not immune to certain partition attacks. We believe they
don't offer much gain to an attacker as they are very easy to detect and
difficult to pull off since an attacker would need to compromised a
directory authority at the very least. Nevertheless, this section describes
all possible partition attack and how to detect them.
5.3.1 During commit phase
A malicious directory authority could send only its commit to one single
authority which results in that authority having an extra commit value for
the shared random calculation that the others don't have. Since the
consensus needs majority, this won't affect the final SRV value. However,
the attacker, using this attack, could remove a single directory authority
from the consensus decision at 24:00 when the SRV is computed.
If an attacker sends two different (or more) commit values either to
different authority in the same period or during the whole comit phase, a
conflict will be detected [COMMITCONFLICT]. Because of this conflict
mechanism, it's not possible to partition the authorities since ultimately
this authority will be ignored. All votes are broadcasted to others and
conflict line are carried through out the full protocol run (commit and
reveal phase).
All of the above is fairly easy to detect. Commitment values in the vote
coming from an authority should NEVER be different between authorities. If
so, this means an attack is ongoing or very bad bug (highly unlikely).
5.3.2 During reveal phase
Let's consider Alice, a malicious directory authority. Alice could wait
until the last reveal round, and reveal its value to half of the
authorities. That would partition the authorities into two sets: the ones
who think that the shared random value should contain this new reveal, and
the rest who don't know about it. This would result in a tie and two
different shared random value.
A similar attack is possible. For example, two rounds before the end of the
reveal phase, Alice could advertise her reveal value to only half of the
dirauths. This way, in the last reveal phase round, half of the dirauths
will include that reveal value in their votes and the others will not. In
the end of the reveal phase, half of the dirauths will calculate a
different shared randomness value than the others.
We claim that this attack is not particularly fruitful: Alice ends up
having two shared random values to chose from which is a fundamental
problem of commit-and-reveal protocols as well (since the last person can
always abort or reveal). The attacker can also sabotage the consensus, but
there are other ways this can be done with the current voting system.
Furthermore, we claim that such an attack is very noisy and detectable.
First of all, it requires the authority to sabotage two consensuses which
will cause quite some noise. Furthermore, the authority needs to send
different votes to different auths which is detectable. Like the commit
phase attack, the detection here is to make sure that the commiment values
in a vote coming from an authority are always the same for each authority.
6. Discussion
6.1. Why the added complexity from proposal 225?
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 00:00UTC?
Section [SRDISASTER] specifies that if the 00:00UTC consensus fails to be
created, we simply hash the random value of the previous day and use it as
the new shared random value. This changes the daily value but fails to make
it fresh, which is not optimal.
Theoretically, we could recover by calculating the shared randomness of the
day at 01:00UTC instead. However, adding such fallback logic would
complicate the protocol even further, so we have not yet considered it.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 603 bytes
Desc: Digital signature
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20151028/5df393b2/attachment-0001.sig>
More information about the tor-dev
mailing list