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

[Nicholas Hopper]

On Fri, Nov 22, 2013 at 9:55 AM, George Kadianakis <desnacked at riseup.net> wrote:
> (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.

(re-posting this reply to tor-dev at George's request)

Your analysis looks correct to me.  But what's wrong with using
threshold crypto or secret sharing?  Since you're already assuming
some sort of bounded delay synchronization, I think we can eliminate
any advantage in influencing the randomness with one extra round,
using e.g. threshold Elgamal:

0. (Periodically, like once per month): authorities derive a shared
Elgamal key pair (x, X = xB) for the group G.  (with prime order p)

1. each authority publishes a randomly chosen encrypted group element
P_i:  (r_iB, r_iX+P_i) along with a proof of knowledge of r_i.  (an
easy proof to implement)

2. After COMMIT_TIMEOUT: each authority takes all published
ciphertexts (with valid proofs), and publishes a list of ciphertexts
it received.

3. After AGREE_TIMEOUT: each authority takes all published, valid
ciphertexts that appear in over half of the previous set of documents,
and adds them componentwise to get an encryption of the sum of the
group elements (sB, sX+Q).  Each authority publishes this ciphertext
plus its decryption share of this ciphertext with a proof of correct
decryption.  (this is also a pretty straightforward proof to
implement)

[ here s is the sum of the scalars r_i, Q is the sum of the group elements P_i ]

4. After REVEAL_TIMEOUT: each authority combines the valid decryption
shares to get a random group element Q, and publishes a signed
document containing the decryption shares and Q.


-- 
------------------------------------------------------------------------
Nicholas Hopper
Associate Professor, Computer Science & Engineering, University of Minnesota
Visiting Research Director, The Tor Project
------------------------------------------------------------------------