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

George Kadianakis desnacked at riseup.net
Fri Nov 6 13:09:37 UTC 2015

s7r <s7r at sky-ip.org> writes:

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

Thanks for the comments.

FWIW, here is the latest version of the spec:

The main change here is that we removed the conflict detection feature. The
rationale is the same as for removing the majority voting: it doesn't fix the
root cause of partition attacks and it adds complexity to the code.

> 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 )
> where the signature is performed using a special shared randomness
> ed25519 key [SRKEY].

To be honest now that we removed the conflict detection code, the SR keys are
almost useless, since there is already origin proof for authoritative
commits/reveals by listing them on the signed vote.

I'm kinda contemplating removing the SR keys altogether, since that would remove
another good 500+ lines of code. It would also simplify considerably our
commit/reveal generation and verification procedures. It would also speed up the
code review procedure.

I'm kind of sad for us killing all that nice code, but hey we can keep it in a
branch and use it when we actually need to.

Let me know what you think here. Maybe i'm crazy.

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

Hm, I didn't understand entirely what's the problem here?

BTW, in the code the timestamp is placed in both commit/reveal at the same time,
not after the ed25519 signature creation.

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

Yes indeed. Please see:

This will need to change if we decide to remove SR keys.

> 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 think I like your idea for having the SR key share the lifetime of the signing
key. We should do this if we decide to keep SR keys.

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

More information about the tor-dev mailing list