[tor-dev] On the security of a commit-and-reveal solution for #8244

[George Kadianakis]

(This message has been sitting in my drafts for a week or so, because
I fear that it might make no sense. Today I cleaned it up and decided
to post it.)

Hello Nick and Elly,

we were recently discussing various commit-and-reveal schemes to
accomplish the unpredictability of HSDir positions in the hash ring.

This is a thread to better coordinate on this subject. The
corresponding trac ticket number is 8244.

I left our IRC discussion with two conclusions in mind:

a) The simple approach of a commit-and-reveal protocol can not be
   entirely secure since an adversary could choose not to reveal his
   value (abort) which would allow him to influence the final result.

b) Proper protocols that achieve this goal are ugly, both in elegance
   and in the number of rounds. This is basically the Byzantine
   agreement problem which has ugly solutions and funny impossibility
   results.

We started thinking of how disastrous a commit-and-reveal scheme could
be for our specific use case, and we decided that it's worth thinkihng
more about before moving to other heavyweight protocols.

Today, I thought a bit about it.

The goal of such a scheme would be to have all authorities
collectively generate and agree on a nonce. Adversaries who control a
subset of the authorities should not be able to influence the result
(except if they control a majority of the authorities; in which case
Tor is screwed anyway).

So we consider adversaries that can control multiple
authorities. Adversarial authorities can either be Byzantine (can lie,
malfunction, etc.)  or abort unpredictably (because of random
failures).

To make this more concrete, let's also consider a simple
commit-and-reveal scheme for our use case.

Every ONCE_IN_A_WHILE:
1. Each authority publishes a signed document with a commitment value.

2. Authorities collect commitment documents from the other authorities.

3. After COMMIT_TIMEOUT minutes each authority publishes a signed
   document that reveals the cleartext value of their previous
   commitment.

4. Authorities collect cleartext values from other authorities and
   check that they match the received commitments.

5. After REVEAL_TIMEOUT minutes each authority publishes a signed
   document containing:
   * a list of the received commitments and cleartext values that the
      authority used in its nonce calculation
   * the resulting nonce

6. Authorites collect the nonce documents from the other authorities,
   and check that all authorities had the same commitment/cleartext
   list and calculated the same nonce.

The final nonce derivation function should be unpredictable given at
least one honest contribution to the derivation function. For example,
if the inputs to the derivation function are big enough (e.g. each
authority publishes 32 random bytes), stuffing them into a hash
function should do the trick.

Also, assuming big enough COMMIT_TIMEOUT and REVEAL_TIMEOUT values,
honest authorities should not have trouble casting their vote in
time. Maybe we can even allow multi-hour timeout intervals, since we
are not in a particular hurry if ONCE_IN_A_WHILE is every 24 hours or
more.

For the rest of this analysis, the response of authorities towards
node failure is to ignore it: keep calm and and carry on. That is, if
a node doesn't send a message during COMMIT_TIMEOUT or REVEAL_TIMEOUT,
other nodes simply ignore the node for the rest of the protocol. There
might be other responses here (like restarting the protocol), but this
one is the simplest to reason about and probably the most secure. I
argue that the response of restarting the protocol in case of node
failure might be much worse than simply proceeding, but it depends on
the number of restarts we allow (and especially what happens in the
last round of the protocol if the maximum number of restarts is
reached).

Now, let's consider some adversarial tactics:
* (trivial case) If adversaries perform the protocol normally, the
  resulting nonce should be unpredictable assuming that there is at
  least one other honest authority.

* (stupid case) An adversary can abort during the COMMIT_TIMEOUT phase
  but she doesn't gain much. The calculation contains without her
  contributions.

* (interesting case) An adversary can abort during the REVEAL_TIMEOUT
  phase. At this stage, she has seen the cleartext values of the
  honest authorities and can pre-calculate the final nonce value using
  her own cleartext values. If the adversary doesn't like the
  resulting final nonce, she can abort a subset of her authorities, so
  that she gets different final nonces (since the nonce calculation
  would continue without considering the aborting
  authorities). Specifically, if an adversary controls 'a'
  authorities, she can choose between 2^a possible final nonce values,
  by aborting different subsets of her authorities.

  The next question is how this attack influences the probability of
  an attacker that wants to inject his own HSDirs as the responsible
  HSDirs of a Hidden Service. I should note that the final nonce is
  still unpredictable (the adversary can just choose between multiple
  unpredictable final nonces), so the best strategy of an attacker is
  to add HSDirs in the hash ring (probably in strategically chosen
  positions) and choose whichever of the possible 2^a nonce values (if
  any) makes his HSDirs responsible for the target HS.

  We can analyze this situation by modeling it as a game and
  calculating the probability of the adversary winning. I tried to do
  this in the appendix of this post.

  If my logic is not flawed (could as well be) and my assumptions are
  not ridiculous, an attacker has probability '1 - (1 - k/r)^d' of
  getting his HSDir as the first responsible HSDir of a Hidden
  Service. In the above formula, k is the number of adversarial HSDirs
  in the hash ring, r is the total number of HSDirs, and d is d=2^a
  that is the number of possible final nonce values he can choose from
  by aborting some of his authorities. On the other hand, the
  probability of an attacker succeding without the commit-and-reveal
  scheme is simply k/r.

All in all, it seems that the commit-and-reveal protocol is not too
bad (if the adversary controls one or two authorities), but it's not
very good either. It's worth bearing in mind that footnote [0] might
change the probabilities for the worse.

It's also important that we look deeper into #8243.

If I get persuaded that my assumptions, models and math are correct, I
might make some graphs to demonstrate how the attacker probability
changes for different values of k, r and d.

---


APPENDIX:

Badness of commit-and-reveal scheme:

(Here be dragons, bad math and plenty of mental masturbation. Proceed
with caution.)

The problem with the commit-and-reveal scheme is that an adversary who
is not happy with the position of the Hidden Service in the hash ring,
has the option of choosing any subset of her a adversarial authorities
to abort the commit-and-reveal protocol during the REVEAL_TIMEOUT
phase, which lets her choose between 2^a positions for the Hidden
Service.

To evaluate how bad this is, we can model our problem as a game and
calculate the probability of the adversary winning.

In the game, we model the HSDir positions in the hash ring as random
integers from 0 to N. [0]

Similarly, we model the position of a Hidden Service in the hash ring
as another random integer from 0 to N.

We say that an adversary wins, if any of her HSDirs are the closest
(in a clockwise fashion) to the position of the Hidden Service.

Defining the game formally:

Game_1:
"""
Step 1: Each player p_i picks a number x_i uniformly in [0, N]
{This corresponds to HSDir positions in the hash ring} 

Step 2: A random value phi is chosen uniformly in [0, N]
{This corresponds to the position of the Hidden Service in the hash ring}

Step 3: Winner is the player whose x_i is the closest to phi. We
        define the distance of a player i as d_i = x_i - phi (mod N).
{This emulates the algorithm that Hidden Services use to pick their
responsible HSDirs}
"""

(For computing ease, we will assume that x_i and phi values are
distinct from each other. This should be true in real life too,
otherwise some key collision happened.)

Looking at the above game, and based on our assumptions, it is easy to
see that d_i values are actually random values in [0, N]. This can be
seen informally, since the players during step 1 don't know the value
of phi. It can also be seen formally by calculating P[d_i == 0],
P[d_i == 1], ..., P[d_i == N]: all of those probabilities should be 1/N.  

This means that we can reduce the above game to a new game that is
easier to analyze:

Game_2:
"""
Step 1: Each player p_i picks a number d_i uniformly in [0, N].
{This corresponds to each player getting assigned a distance value d_i}

Step 2: Winner is the player with the smallest d_i value.
{The winner is the player with the smallest distance from the Hidden Service.}   
"""

Now let's analyze Game_2:

Informally again, since the game is fair and symmetric, all players
have the same probability of winning. That is,
P[p_1 wins] == P[p_2 wins] == ... == P[p_r wins]            (1)
where r is the total number of players.
{in our equivalent real life problem, r is the number of HSDirs }

Furthermore, since one player has to win, we have:
P[p_1 wins] + P[p_2 wins] + ... + P[p_r wins] == 1          (2)

Combining (1) and (2) we get that P[p_i wins] == 1/r  (for 0 < i < r)
which means that all players have probability 1/r of winning. This is
intuitive and what we expected.

Now let's calculate the probability of an adversary winning the game,
assuming that he controls multiple players.
{or that he controls multiple HSDirs in our equivalent real life problem}

It's easy to see that the probablity of k players winning is k/r.
This means that:
P[adversary that controls k out of r players wins] = k/r    (3)
with k <= r.

Now that we have these probabilities in place, we can calculate how
bad the commit-and-reveal scheme is for us. It's important to notice,
that an adversary who controls a authorities can choose between d = 2^a
values of phi in Game_1, but she doesn't get a chance to redistribute
her x_i values accordingly (since relays require a certain uptime till
they get the HSDir flag).

Informally again, I argue that choosing between d values of phi in
Game_1, is the same as restarting Game_2 d times (so that all players
get completely different d_i values). Hence, I believe that the
probability of an adversary winning if he has d choices of phi, is the
same as the adversary winning in at least one instance of Game_2 if
Game_2 is restarted d times. That is,

P[winning in at least one instance of Game_2 if you play d times]
== P[*not* loosing all d instances of Game_2]
== 1 - (P[loosing all d instances of Game_2]
== 1 - (P[loosing on Game_2])^d 
== 1 - (1 - P[winning on Game_2])^d, and using (3) we get:
== 1 - (1 - k/r)^d                                          (4)
where we assume that the adversary controls k out of r players of Game_2.

Now that we have (4), let's plug some real life Tor network data into
it to see what kind of probabilities we get:

If we assume that we have r=2000 HSDirs in total [1], and an adversary
controls k=100 HSDirs, the probability of him winning Game_2 is:
P[adversary wins] = k/r == 100/2000 == 0.05

Now, let's also assume that we are using the commit-and-reveal scheme
and the adversary controls 1 authority, hence d = 2^a == 2. Now we have:
P[adversary wins] = 1 - (1 - k/r)^d == 1 - (1 - 100/2000)^2 == 0.0975

If he controls 2 authorities, we have d == 4, and:
P[adversary wins] = 1 - (1 - k/r)^d == 1 - (1 - 100/2000)^4 == 0.1854

If he controls 3 authorities, we have d == 8, and:
P[adversary wins] = 1 - (1 - k/r)^d == 1 - (1 - 100/2000)^8 == 0.3697

And the numbers go on... [2]

It's worth noting here that this attacker only cares to get the first
position after the HS. An attacker who wants to do so probably plans
to squat *all* responsible HSDirs of a HS, and he can achieve it by
placing multiple clusters of HSDirs in different parts of the hash
ring. This is a different strategy from the attacker who only cares
about having a single responsible HSDir for an HS; the probabilities
for such an attacker would be better than the ones above.

[0]: This is a very *important* assumption, since adversarial HSDirs
     can pretty much pick their position in the hash ring by brute
     forcing their keys till they find one that puts them in a good
     position. A good position would be a place where there is a big
     gap between the adversarial HSDir and the previous honest
     HSDirs. We will not consider this adversarial strategy since it
     makes the math harder.

[1]: $ grep -i HSDir cached-microdesc-consensus  | wc -l
     2015

[2]: http://www.wolframalpha.com/input/?i=1+-+%281+-+k%2Fr%29%5Ed%2C+for+k%3D100+r%3D2000+d%3D2%5En