[tor-dev] Update of prop#250: Random Number Generation During Tor Voting

[s7r]

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

Hello,

Epic work. I agree that the code enforcing commit majority was not
making a difference in the partition attack. I also agree that the
partition attack is (almost) useless, expensive and very noisy. An
attacker can get the same result if, instead of a partition attack
where he has two shared random values to choose from, he simply does
not participate at all in the protocol run and there's no shared
random value for that day (assuming it's an odd total number and his
vote could be decisive). At least this won't be that noisy and get him
blown out of the consensus.

The SRDISASTER shared random value can be deterministically calculated
(based on previous consensus agreed SR value). This means 12 hours
earlier instead of the two different SR values that could result from
a successful partition attack (the attacker will have to know the
reveal values from the other authorities, then try to partition them,
etc.).

I am adding some parts of the proposal with comments, with some quotes
from the text in the proposal. Comments start with *:



4.1.1. Computing commitments and reveals [COMMITREVEAL]
"The value REVEAL is computed as follows:

      REVEAL = base64-encode( TIMESTAMP || RN )"

* Maybe it is useful to also sign the REVEAL value with the SR key for
broadcasting, besides keeping the unsigned one for computing COMMIT
which obviously needs a separate signature. It provides some security
against little effort. Useful for directory authorities who miss the
commitment phase and only participate in the reveal phase. Something
like this (switched TIMESTAMP's place at the end):

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

where the signature is performed using a special shared randomness
ed25519 key [SRKEY].

* Note for both REVEAL_BROADCAST and COMMIT values:
Is it mandatory to have TIMESTAMP in both SIGNATURE and final
REVEAL_BROADCAST or COMMIT values? If not, maybe we can avoid the
latter and rely only on the signed TIMESTAMP within SIGNATURE. Is
there any chance the TIMESTAMP value won't be an exact match? All
TIMESTAMP values must match exactly (in case the ed25519 signature
will take a fraction of a second or so, since we are talking about
unix timestamps).



4.1.2. Validating commitments and reveals [VALIDATEVALUES]
"TIMESTAMP_R must be equal to TIMESTAMP_C else REVEAL is an invalid
value for COMMIT."

* To be more explicit when defining validation, we should include that
after checking the signatures and timestamps, it must also check if
H(REVEAL) extracted from COMMIT value is indeed the hash sum
(sha256sum in present case) of RN extracted from the REVEAL value.

* If we will sign the REVEAL values with the SR key also, include the
additional validation steps required also.



4.1.7. Including the ed25519 shared randomness key in votes [SRKEY]

* This is a good idea, I don't have a strong argument against
maintaining a separate SharedRandomKeyLifetime and adding more logic
to load_ed_keys() for the SR key, but I do have a suggestion which
could simplify it and use the already existent logic and failure
recovery rules, the existent SigningKeyLifetime and the existent
need_new_signing_key and want_new_signing_key. Simple is good, plus
there is no additional security for keeping different expiration dates
for the medium term signing key and SR key. SR key is hierarchically
below medium term signing key one way or another. If this is a bad
idea and messes up other parts of the design, apologies - let me know
and I'll try to think of a different logic for SharedRandomkeyLifetime.

I have detailed it here:
https://trac.torproject.org/projects/tor/ticket/17349#comment:12

Also adding the comments here:
These checks should apply in AFTER finishing the existent checks for
ed25519 keys as they are fully compatible on them and actually rely on
them. The additional rules below should only apply if Tor is running
as a directory authority, and should be ignored on normal relays.

1. On fresh start or HUP signal, after doing all the existent checks
for ed25519 identity keys, only if we are an authority: also check if
ed25519_shared_random_secret_key and ed25519_shared_random_cert files
exist in $datadirectory/keys.

2. If these files are missing (or just one of them is missing, doesn't
matter):
generate a new ed25519_shared_random_secret_key and an
ed25519_shared_random_cert chained to ed25519_signing_secret_key. When
generating the ed25519_shared_random_cert, also check the expiration
timestamp of ed25519_signing_cert and copy/paste it. Since Tor will
first do the checks for ed25519_signing_secret_key and
ed25519_signing_cert, and only after this, in order, the checks for
ed25519_shared_random*, this step cannot go wrong.

3. If ed25519_shared_random_secret_key and ed25519_shared_random_cert
both exist in $datadirectory/keys:
3.1 First, check if expiration timestamp of ed25519_shared_random_cert
== expiration timestamp of ed25519_signing_cert. If not, it means the
ed25519_signing_secret_key has changed, so delete
ed25519_shared_random_secret_key and ed25519_shared_random_cert
entirely and fail back to step 2.

3.2 Second, if the expiration timestamps in both certificates match,
check if ed25519_shared_random_cert is valid and properly chains
ed25519_shared_random_secret_key to ed25519_signing_secret_key. If
they somehow do not match, delete ed25519_shared_random_secret_key and
ed25519_shared_random_cert entirely and fail back to step 2.

4. Proceed if all these went well as normally. Unlike
ed25519_signing_secret_key - when the ed25519_master_id_secret_key is
kept offline or encrypted, there is no excuse for not being able to
automatically generate an ed25519_shared_random_secret_key and
ed25519_shared_random_cert if we follow all the steps in the logic
order, so the above checks should be sufficient and leave us with 0
risk to end up with a Tor process running on a directory authority
with no (or invalid) SR key.



5.3 Partition attack
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."

* The last reveal round? Clarification needed (maybe I mixed
terminology here -- round = one vote at :00). Do we allow directory
authorities to participate only in the last reveal round? This sounds
like something very unlikely to happen normally, so I think we
shouldn't allow this. What if we require at least 2 or 3 rounds of the
reveal phase before we accept a dirauth in the SR protocol? If a
dirauth is missing for 23 hours in a day, I think it should not be a
part of the SR protocol in that day. At least one round before the
pre-last round (last round is the one when consensus is computed and
there's no time to identify and validate potential conflicts).

This won't make the partition attack any harder, the directory
authorities will detect if more than 1 reveal value is sent by Alice
and ignore her, but this won't help if Alice will send one reveal
value to some directory authorities and NO reveal value to others.

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

* Right, maybe we could do something like this here: Since all COMMIT
and REVEAL values are signed by their issuer AND the voter (they are
included in all votes) other authorities could follow a simple rule like
:

if (~50% from total number of directory authorities participating in
the SR protocol -1) vote the same REVEAL value for directory authority
"Alice" (with Alice's proper signature) and Alice doesn't vote the
same REVEAL value for her in the final vote, enforce the reveal value
broadcasted to the (~50% from total no of authorities participating
- -1) and use it to calculate the SR value as like Alice included it in
her vote also. This way Alice can't have two consensuses with
different SR values:
- - If she sends more than 1 REVEAL value to other directory
authorities, it will be detected as conflict and she will be ignored
when computing the SR value (if we require more rounds from REVEAL
phase to accept a dirauth in the protocol).
- - If she sends just 1 REVEAL value to exactly half of other directory
authorities, SR value will be calculated with that reveal value sent
by her (alice + other 50% = proper majority = ONE valid consensus)
regardless she doesn't vote it for herself in her final vote.

Simple view of the problem: hey Alice you voted something so much (to
50% of the dirauths) but you don't want to admit it? It's ok, we know
how to validate crypto signatures so we voted for you in your final
vote, thanks.

I don't know how complicated this would make the code (if it's simple,
it may be worth it). I am not entirely sure if this is worth our time
since it's agreed that this attack is noisy, expensive and with very
little return to the attacker.


On 10/28/2015 8:26 PM, David Goulet wrote:
> 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-re
veal-consensus.txt
>
>
> 
[3] https://trac.torproject.org/projects/tor/ticket/17349
> 
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2.0.22 (MingW32)

iQEcBAEBCAAGBQJWOsBKAAoJEIN/pSyBJlsR+1kH/1L9fqrHmGegoZEBJYmq2rNq
ogAd38x+94kx7u04ekmApmCrabA6fWvnJPP2+QjEnCWDjzmnt1rDq6exQsIFYQEo
riuxszQPHiXMOGy1/aCNLb5qHtjkvOkQQz7bkU2JPdq1btEJpUGj4uSSi7zFr3m9
WOE//mwLH4WHxsNJB3RyHYucYQ2ffvJ2tcgDSfyIjQIKFE1xdwPv9BgYVTk2Emta
CmdnKckT50j1aYxvnqLpfQUUBm7+3rZ3a379ZyZ4/6YR1sicFPElx/rtOuDeR6e9
0kulDArd5c3IkFoRl4wgxdLHnHbBLkeU8fqQ4IAoQVzvCYvDclMga88znO1x1X0=
=QZCy
-----END PGP SIGNATURE-----