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

[s7r]

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