Hello. As part of my undergraduate thesis I wrote up the protocol suggested here. I figured someone might find it useful so I've attached a PDF version of it to this email. Feel free to use it for any purpose.
On Sat, Jan 11, 2014 at 3:08 AM, Nicholas Hopper hopper@cs.umn.edu wrote:
A Threshold Signature-based Shared RNG
- Overview
This proposal is for a design of a shared RNG to address ticket #8244 - "The HSDirs for a hidden service should not be predictable indefinitely into the future," /without/ requiring byzantine agreement protocols at each RNG period. The basic idea of this proposal is to have directory authorities use a deterministic threshold signature scheme to sign Hash(time-period) in each consensus document. This is done simply by having each authority contribute a publicly-verifiable share of the signature during the voting process. As long as at least ceiling(n/2) authorities are honest, the signature can be re-constructed by each client. Since the signature is hard to compute if you don't control at least ceiling(n/2) authorities, its inclusion in the input to a hash function (e.g. for use in constructing the HS hash ring) will make the output of the hash function pseudorandom. (In the strong cryptographic sense that unless you can break the signature scheme, you can't distinguish the hash from a truly random string of the same length)
- Notation and such
This protocol can work over a group G, using a subgroup generated by an element B of prime order p. We'll use Curve25519 [Curve25519] for concreteness, but any group where the Computational Diffie-Hellman problem is difficult would do.
We'll denote multiplication of scalars (e.g. mod p) by *, e.g. a*b; we'll denote multiplication of a group element P by scalar a by a.P.
We will make use of Shamir threshold secret sharing, described, e.g. in Handbook of Applied Cryptography [HAC], over the integers mod p. For a subset S = {P_1,...,P_t} of size t, we'll denote the lagrange multipliers for S by m_1,...m_t (eg. if each P_i has share s_i of secret x, then m_1*s_1 + m_2*s_2 + ... + m_t*s_t = x.)
We assume that each authority S_i has a publicly known verification key VK_i and signing key sk_i for a digital signature scheme (Sign, Verify). We model network communications as point-to-point with bounded delay and assume at most t-1 authorities are compromised. (Without these assumptions, the consensus voting protocol is also broken)
We'll need a hash function H that can output elements of the subgroup generated by B with unknown discrete logarithms. For Curve25519, it should work to compute H(x) by computing SHA256(x), and mapping this 256-bit string to the curve as in the Curve25519 paper. A security proof would model this H as a random oracle.
We'll need a distributed threshold key generation algorithm which works as follows: Input: Parties S_1,...,S_n Output: to all players: group public key P = x.B. player public key shares s_1.B, ..., s_n.B to each player P_i: secret key s_i) such that the secret keys s_i are (n,t) secret shares of the (unknown) secret key x. We discuss choices to implement this protocol in section [DKG]
We will also require a noninteractive zero-knowledge "signature of knowledge" that can be bound to a message m, to prove that two points P, Q have a common discrete logarithm to bases B and R respectively. We denote this proof by SK { s : s.B = P && s.R = Q } (m) and discuss its implementation in section [SKDH].
- Overall Protocol description [CONSENSUS-RANDOM]
The protocol requires that periodically the authorities run the distributed key generation procedure to produce the threshold public key P = s.B, and public key shares P_1 = s_1.B, ... , P_n = s_n.B. This can be done infrequently, since its only purpose is to limit key exposure.
For the time period starting at time T, the authorities generate the shared random value as follows:
Step 1. [Period Base]
Each authority (and anyone else interested) generates the "time period base point" R in G, by computing
R = H("tor-hs-rand-base-point " || period valid-after time)Step 2. [Signature Share]
Each authority S_i uses its secret share s_i and signing key sk_i to generate its signature share SHARE_i as follows:
SHARE_i = R || Q_i || PROOF_i || Sign_i(R || Q_i || PROOF_i) Q_i = s_i.R PROOF_i = SK { s_i : s_i.B == P_i && s_i.R == Q_i }(S_i || T)Each SHARE_i is appended by S_i to the network consensus document for time period T in a separate section.
Step 3. [Validation]
Tor clients locally validate SHARE_i from server S_i for time period T as follows: i. Verifythe signature using verification key vk_i. ii. Check that R = H("tor-hs-rand-base-point " || T). iii. Verify PROOF_i for points (P_i, Q_i) with bases (B,R) . SHARE_i is considered valid if and only if all three checks succeed.
Step 4. [Aggregation]
If at least t = ceiling(n/2) valid shares appear in the consensus, Tor clients locally compute the randomizer string RAND for time period T as follows:
i. Let (S[j], Q[j]) for j = 1,...,t denote the identities (S_i) and signature shares (Q_i) associated with t valid SHARE_i values.
ii. Compute the Lagrange multipliers m[j] for x points S[1]...S[t]
iii. Compute RAND = m[1].Q[1] + m[2].Q[2] + ... + m[t].Q[t]
Notice that RAND = m[1]*s[1].R + ... + m[t]*s[t].R = x.R
If there are not enough valid shares, the protocol fails; this indicates that a majority of the directory authorities are faulty or compromised. If we wanted a fail-open solution, possibilities include hashing the list of valid SHARE values, or taking the hash of the previous consensus RAND value. [XXX - other options or opinions?]
- Signature of knowledge scheme [SKDH]
Given values (R,S), bases (P,Q), and exponent s such that R=s.P, S = s.Q, we use the "Fiat-Shamir Heuristic" with the proof of equality of discrete logarithms due to Chaum-Pedersen [CP92, Sec. 3.2] to generate
SK { s : s.P == R && s.Q == S } (m)
As follows:
i. Choose random integer a in [0,p-1] ii. Compute: U = a.P V = a.Q c = Hash(U || V || m) z = a + s*c (mod p) iii. Output (U,V,z)
The proof is verified by computing cc = Hash(U || V || m) and checking that z.P == U + cc.R z.Q == V + cc.S
- Distributed Key Generation [DKG]
We'll need a protocol satisfying the following specs: Input: Parties S_1,...,S_n Output: to all players: group public key P = x.B. player public key shares s_1.B, ..., s_n.B to each player P_i: secret key s_i
such that the secret keys s_i are (n,t) secret shares of the (unknown) secret key x.
There are several options for such a protocol, depending on what we want to assume about the network over which the authorities will run the protocol (Presumably, the Internet):
If we assume "weak synchrony" (messages are eventually delivered without unbounded delay), the protocol of Kate and Goldberg [KG09] can tolerate floor((n-1)/3) corruptions and still run to completion.
If we assume bounded delay but allow "rushing" adversaries and adaptive corruptions, the protocol of Garay et al [GKKZ11] can be used to realize the broadcast channel required for Pedersen's protocol [Ped91] while tolerating up to t-1 = floor(n/2) corruptions.
If we assume bounded delay and static corruptions, the protocol of Dolev and Strong [DS83] can be used to realize the broadcast channel required for Pedersen's protocol and tolerate up to t-1 corruptions.
I'm not an expert on byzantine agreement protocols, so it is possible that there exist other, more easy to implement/manage options as well.
- References
[CP92] David Chaum, Torben Pryds Pedersen. "Wallet Databases with Observers", CRYPTO 92, pp 89-105. http://link.springer.com/chapter/10.1007/3-540-48071-4_7
[CURVE25519] Daniel J. Bernstein. "Curve25519: new Diffie-Hellman speed records", PKC 2006, pp 207-228. http://cr.yp.to/papers.html#curve25519
[DS83] D. Dolev and H. Strong. "Authenticated algorithms for Byzantine agreement", SIAM J. Computing 12(4):656-666, 1983. http://www.cse.huji.ac.il/~dolev/pubs/authenticated.pdf
[GKKZ11] Juan Garay, Jonathan Katz, Ranjit Kumaresan, Hong-Sheng Zhou. "Adaptively Secure Broadcast, Revisited", PODC 11, pp 179-186. http://chess.cs.umd.edu/~jkatz/papers/asb-final.pdf
[HAC] Alfred Manezes, Paul van Oorschot, Scott Vanstone. "Handbook of Applied Cryptography", CRC Press, 1996. http://cacr.uwaterloo.ca/hac/
[KG09] Aniket Kate, Ian Goldberg. "Distributed Key Generation for the Internet", 29th International Conference on Distributed Computing Systems, June 2009. https://cs.uwaterloo.ca/~iang/pubs/DKG.pdf
[Ped91] Torben Pryds Pedersen. "Non-interactive and information-theoretic secure verifiable secret sharing," CRYPTO91. http://www.cs.huji.ac.il/~ns/Papers/pederson91.pdf
--
Nicholas Hopper Associate Professor, Computer Science & Engineering, University of Minnesota Visiting Research Director, The Tor Project
tor-dev mailing list tor-dev@lists.torproject.org https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev