A Threshold Signature-based Shared RNG
0. 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)
1. 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].
2. 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?]
3. 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
4. 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.
5. 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
On Fri, Jan 10, 2014 at 10:38:06AM -0600, Nicholas Hopper wrote:
Careful here. Curve25519 doesn't represent points at all; it only represents x-coordinates. Also, most of those x-coordinates aren't of points in the subgroup generated by B (assuming you use the standard B). Can you be more specific about "as in the Curve25519 paper"? What's given on p.4 doesn't necessarily land you in the subgroup.
And this is where the above may bite you. But perhaps multiplying the above result by 8 may be good enough to solve the problem?
"for t points"? In a full spec, this step would also need to be spelled out, of course.
You haven't defined "Hash". I'd also be happier if P,Q,R,S were thrown in there as well.
Yes: Nick (who would probably be the one writing the code anyway) generates the shares encrypted to keys generated by the authority operators, sends them to the authority operators, and forgets the intermediate results. ;-) (Only partially kidding.)
Then again, if *that* code is written, then just having each authority operator run an instance of that code in the role of Nick, and having everyone add their results, works fine if everyone is online. It's also easy to check that the protocol succeeeded, by interpolating the resulting public keys. An actively malicious adversary during this phase would cause the protocol to fail, but I think it would be good to know that we have an actively malicious authority. ;-)
- Ian
On Fri, Jan 10, 2014 at 1:07 PM, Ian Goldberg iang@cs.uwaterloo.ca wrote:
You're right, I misread the section on p.4; if we use Curve25519 the result of the hash needs to be scalar multiplied by 8 to wind up in the subgroup.
Hash(x) could be implemented by computing y = SHA256("tor-hs-rand-sok-hash" | x) and taking the first 128 bits of y as the output.
As far as including P,Q,R,S in the hash: sure, sounds good.
Ha! Yes, byzantine agreement is much easier with a trusted party. :)
Let's call this the "optimistic approach", and it would certainly be an option, although one issue is that when it fails we can say that someone is malicious but not which authority(s). Although one possibility is to have the ability to fall back to a full byzantine-tolerant protocol in that event.
On Mon, Jan 20, 2014 at 7:32 AM, Ian Goldberg iang@cs.uwaterloo.ca wrote:
This runs into problems when parties claim *not* to have received messages from others. (e.g. imagine that floor(n/2) authorities are corrupted and claim that an uncorrupted party did not send them any input)
Hello. So here are my thoughts.
As far as the threat model goes my personal opinion is that it's fairly safe to assume that the bad guys are static and don't change during the protocol. As far as delay goes I'm not sure.
For failure behaviour I think having a single possible fall back value that can't be influenced by any participants at all seems like the safest bet. For instance if there aren't enough valid shares then just set RAND = R. I'm not sure using the previous consensus's RAND value is a good idea or not, it depends on how readily available it is from non-directory sources; we probably don't want to trust the directories to tell us the backup RAND value if they weren't able to successfully calculate a primary RAND value.
Could you please confirm these for me?: 1. In your notation x.y = y^{x} mod p. 2. We know P_i and that dlog_B(P_i) == s_i from the DKG protocol. This simplifies verification a bit since we don't need to prove that dlog_B(P_i) is a valid (private) keyshare, we already know it is. 3. The threshold for RAND calculation is the same as the DKG's threshold, not a fraction of whoever's online when the RAND calculation starts.
Lastly what purpose does the Sign_i(...) part serve? If s_i is _only_ known by S_i, and the zero knowledge proof PROOF_i proves that dlog_R(Q_i) == s_i, then the signature seems a little redundant since only S_i could have created Q_i. Maybe I've missed something here.
On Sat, Jan 18, 2014 at 11:05 AM, Kang td66bshwu@gmail.com wrote:
For instance if there aren't enough valid shares then just set RAND = R.
I like this suggestion; thanks.
Sort of - the proposal is to do the arithmetic over an elliptic curve, not in the integers mod a prime. And p is the (prime) order of the point B. But if we wanted to use a multiplicative group and had a prime q = 2p+1, then we would have x.y == y^{x} mod q.
Well, yes. But we can check the outcome of the DKG protocol to make sure that the P_i are valid shares of P.
Yes, the threshold is an integer fixed at the time of keyshare generation.
It's probably true that if the SoK is computed over the entire message then there's no need for a separate signature. The Sign_i part is just there for overengineering principles.
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:
-
Ian Goldberg -
Kang -
Nicholas Hopper