On 09 Sep (23:21:03), George Kadianakis wrote:
Nick Mathewson nickm@alum.mit.edu writes:
On Tue, Sep 8, 2015 at 7:10 AM, David Goulet dgoulet@ev0ke.net wrote:
On 08 Sep (01:04:36), Tim Wilson-Brown - teor wrote:
On 7 Sep 2015, at 23:36, David Goulet dgoulet@ev0ke.net wrote: ... Please review it, mostly format of the state (before the SR document) has changed. As well as a new "conflict" line is added to the vote. …
If an authority sees two distinct commitments from an other authority in the same period, the authority is broken or evil: you include both, thereby proving there is a conflict:
"shared-rand-conflict" SP identity SP commit1 SP commit2 NL
where "identity" is the hex-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 [COMMITENCODING].
What if there are more than two conflicting commitments? Should they all be included? Is there a denial of service opportunity here, where an authority just keeps generating commitments to fill up the state files?
Hrm... that is a good point!
We could put in a maximum number of conflicts let's say 5 and add a timestamp to it (meh...). Or when voting, we only add the latest per "identity". I think the important part is just that "oh at this period, we have a proof of conclict, wtf".
It's sufficient to log two conflicting commitments per authority for the same period in order to prove that a conflict exists. There's no reason to keep more.
But tbh, I'm less and less confident about this because for example an authority voting then rebooting immediately and then voting again will trigger a conflict even though this is totally acceptable I think (assuming the initial commit value was not saved in the state on disk).
I say, "Save before publishing, and make sure you don't do two commitments for one period." Assuming this kind of accident happens very rarely, I don't think we need a way to allow it to succeed anyway.
Hello,
Hi!
Thanks for this George, very thorough anlysis. Took me a while to formulate a response and lots of text came out but please read it carefully and point me wrong if needed :).
I have mixed feelings about this shared-rand-conflict mechanism. It indeed seems to solve a problem, but not the nasty one. And it's not trivial to implement.
[ Let's say we have 9 dirauths. One of them is evil. Majority needs 5 dirauths in this case. For a consensus to be considered valid, it needs 5 dirauth signatures. ]
I think the attacker we are worrying about here is the one that during the Commitment Phase attempts to partition the dirauths in two sets (4 auths in group A, and 4 auths in group B). To achieve that the attacker sends a vote with commitment c_1 to group A, and a different vote with commitment c_2 to group B.
Then in the next commitment round the attacker does the same, and now the two groups both think they have majority (group A has 4 auths and the attacker, group B the same). So they both update their internal state accordingly.
Hrm, I think you don't need to change the commitment value to make the partition attack. The attacker simply sends c_1 and c_2 once and since it's majority (group + attacker) both group will keep the value they got. Now, the attacker just needs to send both reveals to the right group and job done, two consensuses with two SR values, no?
If yes, that means that the conflict line doesn't mitigate that at all.
Maybe the majority here needs to NOT include yourself when you decide which value to use or not? For example, if we have 9 dirauths, you want 5 dirauths to agree with you *NOT* counting yourself.
9 - yourself == 8 majority --> floor(8 / 2) + 1 == 5
As a quick example on why it seems to mitigate the attack:
Group A + attacker == 5 dirauths with value c_1 Group B + attacker == 5 dirauths with value c_2
If you are in group A, you'll see 4 dirauths voting c_2 (group B) and 4 dirauths voting for c_1 (group A + attacker - yourself). No majority, reject value from attacker.
The attacker can keep on doing the same, and when the Commitment Phase is over he will have persuaded both groups that they have the right commitment, if he keeps on lying during the Reveal Phase as well (by sending the right reveal value to the two groups) he could eventually succeed in making two different consensuses with two different shared random values.
Or an alternative ending scenario would be that the attacker chooses to not publish any consensus signatures during the last round of the protocol, and then neither of the groups achieves enough signatures to make a valid consensus. And consensus at 12:00UTC fails, and no shared random for today.
So OK these are two reasonable attacks that shared-rand-conflict can address. The attacks are very noisy and detectable but they work. Why am I saying that shared-rand-conflcit does not mitigate everything?
The thing I like about shared-rand-conflict is that it's low effort for high reward. As an authority, you see two commits in the commitment phase, you flag it and broadcast the issue in your vote. We do not need any majority for it, as an other authority if you see a conflict line, you simply ignore that authority until the next protocol run. (HARD requirement on commits being sig. but we should do that anyway. :)
Second great thing about it, for consensus-health, it is trivial to alert us. "Oh, a conflict line in a vote, email/sms/fax/phone armadev". It would be either a very very bad bug, malicious auth (unlikely) or a dirauth in bad shape because its state on disk is borked or it's rebooting with kill -9. In any case, super useful info for us.
It's because IIUC the attacker could also do the same attacks by following the protocol normally and then doing the partitioning attack during the last rounds of the _Reveal Phase_. In this case, the attacker partitions the dirauths into two groups by sending a reveal value to group A, and omitting it to group B. For this to work you don't need to advertise different commitments.
This is in part mitigated by the fact that an authority doesn't use the received commit/reveal values until the next period of the protocol. So sending your reveal values at the last round of the reveal phase (hour minus 1), basically it will not be used by any authorities since it is the first time an authority sees it and you only want to use a value if someone else has seen that *you* have received that value.
(We've just added this constraint in the latest edits of the proposal but I realized that it should be detailed much more if we want to keep it.)
Now doing that at hour minus 2, group A receives the value for the first time, keep it in their state and at hour minus 1, it will be added to their vote and used from that point on. So group B will receive those ultimately and will be able to confirm the reveal value of the attacker that they didn't receive and use it (this seems valid because we are using a commitment value that has been decided by the majority so as long as the reveal matches, it's OK to use it).
Note that I might be mistaken here since I have a huge headache while writing this but seems that this constraint of "using only a value if the others have seen that you have it" is an important one.
Again this way the result is that the attacker can get two consensuses with a different shared random value in each. One consensus will have a shared random value including the attacker's reveal value, and the other will have a shared random value without it. Alternatively, the attacker can sabotage the consensus creation by not publishing consensus signatures.
I feel that this attack during the Reveal Phase is harder to detect and more deniable.
So what can we do?
An alternative protection we could do about these attacks is to take this to the consensus-health layer. We need to make a few detection scripts that will notify us if any of these attacks happen. We don't need shared-rand-conflict for this.
Here are some detections that need to happen:
To detect attacks during the Commitment Phase, consensus-health should warn if it sees two votes having different commitment values from one auth.
To detect attacks during the Reveal Phase, consensus-health should warn if it sees two votes where one includes a reveal value, and the other one doesn't. This is a sign of a partioning attack, or some severe misconfiguration/bug.
Of course, consensus-health should go nuts if we don't manage to create a 12:00UTC consensus. Don't forget that an attacker that wants to hijack the HSDir hash ring, needs to sabotage the consensus like 5 days in a row to get the HSDir flag, so this should raise some alarms.
It would also be useful if consensus-health fetched all the votes *seen* by an authority, and not just the one it publishes. This way we can find attacks where the attacker sends different votes to different honest auths. We can fetch the alien votes seen by an authority using the URL tor/status-vote/next/<fp>.z .
+9000.
Having consensus-health monitoring the protocol runs is crucial imo.
Finally, regardless of whether we do shared-rand-conflict or not, I think I like the idea of using signatures for commitments. This way, a commitment is a standalone proof that it comes from a specific authority and a specific timestamp, without requiring the whole vote signature. This is required to do shared-rand-conflict and might be useful in any case in the future.
I made a patch that implements this for prop250 at:
https://gitweb.torproject.org/user/asn/torspec.git/commit/?h=prop250-nosrdoc-sigs&id=80ed03b4ac40db62582b4af2e3c5c7702c453055s7r told me that he likes the signature approach, and that's also what Nick did in his small proposal. Please let me know if you think this is overengineering! :)
Again, +1. Little effort for extra safety. Quite happy with your edit above.
Cheers! David
Looking forward to your thoughts!
These two things seem to be the main open attacks against prop250. They don't seem particularly threatening because they are all detectable, but we should make sure we are not forgetting anything.
See you around! _______________________________________________ tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev