(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+...
Hello.
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
On Fri, Nov 22, 2013 at 9:55 AM, George Kadianakis desnacked@riseup.net wrote:
(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.
On Thu, Dec 12, 2013 at 11:11 PM, Nicholas Hopper hopper@cs.umn.edu wrote:
Kang pointed out to me in private email that *this* protocol doesn't avoid the need for some sort of consensus about what was sent by other authorities at each time period. This can be solved but it gets messy. I started a separate thread that describes a solution that doesn't have this issue.
------------------------------------------------------------------------ Nicholas Hopper Associate Professor, Computer Science & Engineering, University of Minnesota Visiting Research Director, The Tor Project ------------------------------------------------------------------------
-
George Kadianakis -
Kang -
Nicholas Hopper