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

[Kang]

Hello.

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

If you're willing to live with that then it should be possible to make
a ``perfect'' protocol.
I'll attach some notes regarding one potential solution to the end of
this email. Perhaps you can see some flaws in this that I can't.

Another idea that has occured to me is that you could make the
probability of natural failure tiny, and hence make it significantly
easier to identify troublemakers.
For instance you could extend the protocol to have each participant
select k random onion-routers to be their ``backups''.
They could give their contribution (properly encrypted, ofcourse) to
each of these backups, then tell the other participants who these
backups are.
If a participant vanishes during the reveal stages of the protocol you
can retrieve their value from their backups instead.
This means that for an adversary to back out it needs to shut down
both itself and all its backups.
If a single directory authority goes down for a short amount of time
it's not particularly unusual; on the other hand if a directory
authority and all k of its personally selected backups are unreachable
that's _very_ unusual, and can't really be attributed to network
unreliability alone.

Regards

-----

#METHOD USING SECRET SHARING
##Apologies if the formatting gets mangled or it's a little rough in some parts
This is a method of calculating a shared random value that should be
secure against cheating as long as the majority (> 50%) of players are
honest. That is, it can support a maximum of floor((n-1)/2)
collaborating adversaries, where n is the total number of participants
in the protocol. It's a mix of bit commitment and secret sharing.

The protocol should involve O(n^2) messages, but since it's designed
to be used on only a small number of directory authorities (about 10)
and only run once or so per day this isn't a huge issue. That's
probably about the same number of messages involved a vanilla bit
commitment scheme since it follows the same two phase design.

The method has two phases. In the first phase each participant
generates a value, then splits it into n-1 shares using a (t,
n-1)-secret-sharing method. They distribute those shares to the other
players along with a commitment. The commitment is to protect against
attacks where an adversary can select the result; it converts such
attacks into a secondary backing out attack. Once all participants
have received n-1 shares (one share from each other player) the next
phase begins. During this phase they simply distribute all their known
shares until all players are able to reconstruct all secrets; at which
point they can calculate the shared random as some function of those.

If I haven't made any mistakes this method should prevent any kind of
backing out or influencing the result provided that more than 50% of
the participants are honest [logic behind this later]. It's not the
most efficient algorithm, nor is it [probably] the most secure, but it
is fairly simple and if 50% or more of the directory authorities are
adversaries then there's likely far larger threats to worry about.
Additionally a perfect algorithm that uses this basic form (generate
contributions and distribute them to the others) may be impossible
(deterministic multi-party fair exchange protocols that don't involve
a trusted third party have been proven impossible).

The share combination function could simply be XOR. Provided at least
one of the contributions is random the XOR of all contributions
together should also be random.

-----BASIC ALGORITHM & NOTATION
t = secret sharing threshold = number of shares required to
reconstruct a secret.
n = number of participants.
d = number of collaborating adversary participants.

1. Commit phase.
  1.1. Each participant generates or selects a random value to be
their contribution (the exact method isn't important here).
  1.2. Each participant uses a secret sharing scheme to split their
value into n-1 shares.
  1.3. Each participant distributes these shares, one to each other participant.
    1.3.1. When this is complete each participant will have n-1
shares; 1 share from each other participant.
    1.3.2. When a participant has received all n-1 they send a
PHASE_COMPLETE message to the others to signify they're ready to begin
the revelation phase (these messages should also contain all n-1
received commitments).
    1.3.3. When a participant has received all n-1 shares, and
additionally has received all n-1 PHASE_COMPLETE messages they begin
the revelation phase.
    TODO: failure process [timeout? Process should NOT continue
without the missing shares, it should restart from the beginning.
Continuing could allow adversaries to have honest participants
excluded by claiming they never sent their shares out. [Fix by sending
bundle of all shares, each share encrypted with a different
participant's key -> they receive all shares but can only decrypt
one]]
2. Revelation phase.
  2.1. Each participant sends their whole list of n-1 received shares
to the other participants.
    2.1.1. When this is complete each participant will have
(n-1)*(n-1) shares [not including its own shares, which it of course
knows].
  2.2. Using those shares Each participant reconstructs the n-1
secrets belonging to the other participants.
  2.3. Each participant calculates the shared random value as some
function of all n secrets [n-1 secrets created by the other
participants, plus the secret they created themselves].

-----[BACKING OUT ATTACK (during reveal phase)]-----
Possible when n-d < t. [num honest < threshold]
Not possible when n-d >= t. [num honest >= threshold]

If t = n-1, and d = 2 participant is bad. Then:
1. Commit phase goes normally.
  1.1. Each participant generates a secret, splits it into n-1 shares,
then distributes one to each other participant.
  1.2. Each individual participant now has n-1 shares, 1 share from each secret.
  1.3. The d collaborating adversarial participants pool their shares
to get (n-1)*d + d*(n-d), all the shares of each adversarial secret
and d shares from each honest secret [not enough to reconstruct them].
2. Reveal phase:
  2.1. Honest participants send all their known shares to all the
other participants.
  2.2. Adversarial participants just wait and listen.
  2.3. Honest participants now have (n-d)*(n-1) shares each, n-d
shares from each secret.
    2.3.1. (n-d) < t, that is (n-2) < (n-1), so honest participants
don't have enough shares to reveal the secrets.
  2.4. Adversarial participants now have n*(n-1) shares, n-1 shares
from each secret [that is, they have all the shares from all secrets].
    2.4.1. This is enough for the adversarial participants to
reconstruct all secrets.
      2.4.1.1. If the adversaries like the result they give their
shares to the honest participants to finalise it.
      2.4.1.2. If the adversaries don't like the result they withhold
their shares, meaning that the secret is unrecoverable to the honest
participants and therefore they have no choice but to calculate a
different value.

-----[BACKING OUT ATTACK (during commit phase)]-----
Possible when t <= d. [threshold smaller than or equal to the number
of adversaries]
Not possible when t > d. [threshold larger than number of adversaries]

Say t <= d. Then:
1. Commit phase.
  1.1. Each _honest_ participant generates a secret, splits it into
n-1 shares, then distributes one to each other participant.
  1.2. Adversarial participants just wait to receive shares.
  1.3. Once each adversary has received a share from each honest
participant they pool their knowledge to get a list of d*(n-d) shares,
d shares from each honest participant's secret.
  1.4. Since t <= d the adversaries know enough shares to reconstruct
each honest participant's secret and therefore calculate the final
result before the others.
    1.5.1. If the adversaries like the result they give their shares
to the honest participants to finalise it.
    1.5.2. If the adversaries don't like the result they withhold
their shares, meaning that the secret is unrecoverable to the honest
participants and therefore they have no choice but to calculate a
different value.

-----HOW TO PREVENT BOTH ATTACKS?
Remember that d is the maximum number of adversaries we can defend
against, and t is the secret sharing threshold.
So at what values for t and d are both backing-out attacks prevented?

n-d >= t AND t > d
convert to:
n > 2d AND d < t <= n - d

n > 2d so
n/2 > d [we can only prevent both types of attack if less than half of
the participants are adversaries] or
floor(n/2) > d, since we're dealing with integers here

so
d = floor((n-1)/2) = the maximum possible number of adversaries we can
handle while defending against both backing out attacks.
Putting this value for d in the equation for t then gives:
    floor((n-1)/2) < t <= n - floor((n-1)/2)

Example:
n = 10
d = 4
4 < t <= 6
    t in [5, 6]

n = 11
d = 5
5 < t <= 6
    t in [6]

n = 12
d = 5
5 < t <= 7
    t in [6, 7]

n = 13
d = 6
6 < t <= 7
    t in [7]

...

We'll choose the smaller value for t when more than one is possible.
 t = d + 1