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