[tor-dev] Partitioning Attacks on Prop250 (Re: Draft Proposal: Random Number Generation During Tor Voting)

[David Goulet]

On 09 Sep (23:21:03), George Kadianakis wrote:
> Nick Mathewson <nickm at alum.mit.edu> writes:
> 
> > On Tue, Sep 8, 2015 at 7:10 AM, David Goulet <dgoulet at ev0ke.net> wrote:
> >> On 08 Sep (01:04:36), Tim Wilson-Brown - teor wrote:
> >>>
> >>> > On 7 Sep 2015, at 23:36, David Goulet <dgoulet at 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:
> 
> 1) To detect attacks during the Commitment Phase, consensus-health should warn
>    if it sees two votes having different commitment values from one auth.
> 
> 2) 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.  
> 
> 3) 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=80ed03b4ac40db62582b4af2e3c5c7702c453055
> 
> s7r 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 at lists.torproject.org
> https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 603 bytes
Desc: Digital signature
URL: <http://lists.torproject.org/pipermail/tor-dev/attachments/20150910/6f8991f6/attachment-0001.sig>