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

[Nick Mathewson]

On Wed, Sep 9, 2015 at 4:21 PM, George Kadianakis <desnacked at riseup.net> 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,
>
> 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.

It seemed comparatively simple to implement to me.  After all, relays
must already store one commitment per authority.  With
conflict-checking proposal, they must store up to two commitments per
authority.  I don't see what the hard part is.

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

So, this should get detected during the consensus phase, since there
will be a conflicting vote-digest for the authority in question. The
attack will be detectable at that point, even without the
conflict-detection in my proposal.

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

In my proposal, the next commitment round, the attack will be
detected, when the voters declare which commitments they believe in.
(Even without conflict detection!)

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

This would cause the consensus to fail detectably in the vote-digest
fields, as above. Whichever group was the majority, if any, would rule
the shared-randomness.  So the attacker could get one bit of control,
detectably, which is already the case with any commit/reveal thing.

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

Good idea.

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

It's not quite what I did in my small proposal, and I think the
difference matters. Here's why.

In my proposal, a commitment is:
     a timestamp,
     H(Secret),
     and a signature of both of those fields.

In your proposal, a commitment is a signature of H(Timestamp || Secret).

But with that proposal, there's no way to tell if there's a conflict
unless you see the commitment, because the timestamp part isn't
visible or verifiable.



yrs,
-- 
Nick