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

[George Kadianakis]

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,

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.

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?

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.

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 .

---

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! :) 

---

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!