January 2014 - tor-dev - lists.torproject.org

Re: [tor-dev] Projects to combat/defeat data correlation
by Ximin Luo 17 Jan '14

17 Jan '14

> I imagine the anonymity set would be much smaller for these combined > transports... fewer people using them. In my understanding, the anonymity set doesn't apply to use of PTs since this is only at the entry side. The exit side does not know[1] what PT the originator is using, so is unable to use that information to de-anonymise. [1] at least, in theory should not know, perhaps someone can check there are no side-channels? would be pretty scary if exit could work out that originator is using PTs.

3 2

Re: [tor-dev] Proposal 225: Strawman proposal: commit-and-reveal shared rng
by George Kadianakis 16 Jan '14

16 Jan '14

I'm forwarding a private email by Florian Dold which is related to this discussion. I talked with Florian during CCC and we talked some more over email. Reposting with his permission. Thanks! From: Florian Dold <dold(a)in.tum.de> Date: Sat, 4 Jan 2014 20:45:15 +0100 To: George Kadianakis <desnacked(a)riseup.net> > > Hi! > > I'm afraid there is not much usable information in the slides, it's > just a quick overview of what I'm currently implementing for GNUnet > ... > > However, I do have some comments / ideas for the distributed nonce > generation in Tor. From what I read, most of your current efforts > focus on protocols for distributed *key* generation, which might be > overkill, as your scenario needs less structure --- only a random > value, not a key pair must be generated. > > There's been a lot of theoretical discussion about that in literature > about exactly that, usually under the name "Collective Coin Flipping" > or "Leader Election" (which also must generate a random number), and I > think these ideas are more appropriate for your problem than those > from DKG. > > Let me sketch how their protocols (see [1], [2] and many many more) > work. For simplicity, let's only generate single bit: > > 1. Each player P_i broadcasts a boolean b_i. > 2. The resulting random bit is f(b_1,...,b_n) > > Now, when f = XOR, this corresponds exactly to the protocol we > discussed, which is not secure against adaptive adversaries. However, > when choosing f as the majority function > > f(b_1,...,b_n) = 1 if sum(b_1,...,b_n) > ceil(n/2), 0 otherwise > > it won't be as easy for a single player (or even a small coalition) to > influence the resulting bit (as there's a chance that their choices > don't even influence the final result). > > There are constructions for the function 'f' in literature that are > even more influence-resilient than the majority function. > > > But of course, this is only part of the issue: Problems arise when > players don't broadcast their values correctly. This essentially > boils down to the byzantine consensus problem, and there are various > approaches to this. One of the simplest implementations of this are > based on gradecast [3], a multicast protocol that also gives a > "confidence level" for the correctness of the broadcast. There are > many optimizations of gradecast, including some probablistic > constructions for settings with a large number of players. > > The last paragraph, however, also might apply to distributed key > generation that do *not* use the Fouque-protocol with its complex > zero-knowledge proofs of fair encryption to avoid private channels. > > > Does this help? While still somewhat complex, the collective coin > flipping protocols are probably still less complex than establishing a > distributed key and then doing threshold elgamal, as proposed by > Nicholas Hopper. > > Happy Hacking! > Florian > > [1] http://www.cs.huji.ac.il/~nati/PAPERS/coll_coin_fl.pdf > [2] www.cs.yale.edu/homes/aspnes/papers/stoc97-proceedings.pdf > [3] http://arxiv.org/abs/1007.1049 > > On Sat, Jan 4, 2014 at 6:38 PM, George Kadianakis <desnacked(a)riseup.net> wrote: > > Hey there, > > > > I'm the guy that talked with you about Distributed Key Agreements in CCC. > > We talked about its applications in Tor (we need Distributed Nonce > > Agreement) and attacks on the naive commit-and-reveal method. > > > > I was wondering if your slides or talk is uploaded somewhere on the > > Internet. I found > > https://gnunet.org/content/video-30c3-talk-gnu-name-system but it doesn't > > seem to be the one I was looking for. > > > > Thank you! > > > > [BTW, the relevant Tor ticket is: > > https://trac.torproject.org/projects/tor/ticket/8244 > > and the threshold elgamal idea is here: > > https://lists.torproject.org/pipermail/tor-dev/2013-December/005944.html ] > > > >

2 1

Re: [tor-dev] Projects to combat/defeat data correlation
by Malard Joel 16 Jan '14

16 Jan '14

Sounds like a challenging problem, good luck. In the case of the Harvard exam, the administration may have used some meta data that may not be under your control, listing out all student taking an exam that day, asking teachers for a shortlist of their class jerks and clowns, checking for repeat offenders, finding which ones had downloaded TOR software, asking frat buddies and classmates. Someone willing to send a bomb threat just to avoid an exam may be more likely to brag after the fact, etc. Cheers, Joel ------------------------------ On Wed, Jan 15, 2014 7:16 PM PST Jim Rucker wrote: >There was a story in the news recently of a Harvard student who used Tor to >send a bomb threat to Harvard in order to cancel classes so he wouldn't >have to take a test. He was apprehended within a day, which puts into >question the anonymity of Tor. > >From my understanding (please correct me if I'm wrong) Tor has a weakness >in that if someone can monitor data going into the relays and going out of >the exit nodes then they can defeat the anonymity of tor by correlating the >size and number of packets being sent to relays and comparing those that >the packets leaving the exit nodes. > >Are there any projects in Tor being worked in to combat data correlation? >For instance, relays the send/recv constant data rates continuously - >capping data rates and padding partial or non-packets with random data to >maintain the data rates

1 0

Re: [tor-dev] Anyone wanting to write some Weather-tight code?
by Abhiram Chintangal 16 Jan '14

16 Jan '14

Hello Norbert and Karsten, I have added a couple of attachments to the projects wiki-page. The first one, is a UML diagram of the data-models being used in the current weather. It should gives us a good idea about the current implementation. The second attachment is the Design Document from the current Tor Weather application. It should give a decent idea about the important modules in the application and more importantly its work-flow. Thanks!

1 0

Anyone wanting to write some Weather-tight code?
by Oliver Baumann 15 Jan '14

15 Jan '14

Hi guys, just like Norbert, I have wanted to become an active contributor for some time and this fledgling project seems like a nice chance. If you're in need of a frontend-guy with some Python background, I'll happily add myself to the wiki and chip in wherever I can! All the best, Oliver -- PGP: 0x520AADF9 --

2 1

Re: [tor-dev] Anyone wanting to write some Weather-tight code?
by abhiram 15 Jan '14

15 Jan '14

Hello Karsten, It looks like a nice little project to work on. I reguarly check my relay-status via Atlas, at the moment using the Onionoo service makes sense to me too. For now the onionoo-glue-code, seems like a good place to start. Do you have any other suggestions or ideas? thanks! On Thu, Jan 9, 2014 at 2:11 PM, Karsten Loesing <karsten(a)torproject.org>wrote: > Hello coders, > > is anyone here looking for a fun new project to hack on? Here's > something you could do to help grow the Tor network: > > We're planning to decommission the currently unmaintained Tor Weather > which provides an email notification service to any users who want to > monitor the status of a Tor node. And we'd like to replace it with a > clean rewrite of this service. > > https://weather.torproject.org/ > > (You're asking why we're not simply trying to find a new maintainer? > That's also an option, but a clean rewrite that uses the Onionoo service > would be much smaller and easier to maintain in the future. Read on to > find out more.) > > Here's what the rewritten Weather should do: > > - Maintain a list of subscriptions, consisting of an email address, a > password, a relay identity fingerprint, how soon the user wants to be > notified of problems, when it was last notified, etc. > > - Allow users to create, read, update, and delete subscriptions via a > web interface. All these operations should have the usual security > features like email address verification, password login, etc. > > - Allow users to search for relays to subscribe for by relay IP address, > relay identity fingerprint, or relay nickname. This search can be done > with help of Onionoo's search feature, or by simply adding a link to > Atlas (https://atlas.torproject.org/) or Globe > (https://globe.torproject.org/) > > - Once per hour, download a list from Onionoo that contains relays that > have been running in the last week. Check if there are any relays that > have been offline for long enough to notify a subscribed user. Send out > emails. > > - Once per day, download bandwidth histories of relays from Onionoo and > check whether a relay has been running long enough and fast enough that > the operator should be offered a t-shirt. Send out emails, regardless > of subscriptions, and ask if operators would want one. > > As you can see, most of the work can be done with help of Onionoo. The > parts that need to be written are a web and an email interface, a small > database for subscriptions, and some glue code to talk to Onionoo. > > (And if you still favor the variant where somebody maintains the current > Weather, be aware that it needs to parse Tor descriptors and keep its > own relay database to do searches, to check how long relays are offline, > and to decide which relay operators should get a t-shirt.) > > Here's some more information on the Onionoo service: > > https://onionoo.torproject.org/ > > Happy to provide more information! > > All the best, > Karsten > _______________________________________________ > tor-dev mailing list > tor-dev(a)lists.torproject.org > https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev > -- Abhiram Chintangal Graduate Student Florida State University Computer Science Department (850) 980-4954

6 14

Some uncommon use cases for PT library transport selection
by David Fifield 13 Jan '14

13 Jan '14

I've been thinking about a couple of tricky use cases for pluggable transport libraries, and whether we should do anything to try to support them. The first use case is the flashproxy/websocket use case. flashproxy-client recognizes the two transport names "flashproxy" and "websocket" as synonyms. That is, tor can ask for either one and they will work equivalently. But what should happen when tor asks for "*"; i.e., the activation of all supported transports? We want to start only one SOCKS listener, for the preferred name "flashproxy", not a separate listener for every synonym. The way that you would indicate you support two transport names would be done like this in pyptlib and goptlib respectively: ptclient.init(["flashproxy", "websocket"]) ptInfo, err := pt.ClientSetup([]string{"flashproxy", "websocket"}) but neither of those work for this use case, because if tor asks for "*", you get two listeners. Maybe we don't care about this use case, because as I understand it, tor will never ask for "*" anyway. The second use case is the fog* use case. As a server, we may not want to declare all the transports we support in advance. Rather, we may prefer to look at the names of the transports tor has asked for, and decide for each one whether we support it. The idea here is that since we can arbitrarily chain a set of transports, we can't just enumerate all possible chains and declare those as the transport we support. Both pylib and goptlib require you to list all the transports you want to support on initialization. We would like for tor to be able to ask for a transport name like "obfs3|cbr|obfs3|websocket", and we check to see whether we are able to construct such a chain. The current idea is to only support a small number of predefined chains in a configuration file, so that we can in fact declare them all in advance. https://trac.torproject.org/projects/tor/ticket/9744 David Fifield * fog is the transport combinator formerly known as Metallica; see https://trac.torproject.org/projects/tor/ticket/9743.

1 1

Anyone wanting to write some Weather-tight code?
by Karsten Loesing 12 Jan '14

12 Jan '14

Hello coders, is anyone here looking for a fun new project to hack on? Here's something you could do to help grow the Tor network: We're planning to decommission the currently unmaintained Tor Weather which provides an email notification service to any users who want to monitor the status of a Tor node. And we'd like to replace it with a clean rewrite of this service. https://weather.torproject.org/ (You're asking why we're not simply trying to find a new maintainer? That's also an option, but a clean rewrite that uses the Onionoo service would be much smaller and easier to maintain in the future. Read on to find out more.) Here's what the rewritten Weather should do: - Maintain a list of subscriptions, consisting of an email address, a password, a relay identity fingerprint, how soon the user wants to be notified of problems, when it was last notified, etc. - Allow users to create, read, update, and delete subscriptions via a web interface. All these operations should have the usual security features like email address verification, password login, etc. - Allow users to search for relays to subscribe for by relay IP address, relay identity fingerprint, or relay nickname. This search can be done with help of Onionoo's search feature, or by simply adding a link to Atlas (https://atlas.torproject.org/) or Globe (https://globe.torproject.org/) - Once per hour, download a list from Onionoo that contains relays that have been running in the last week. Check if there are any relays that have been offline for long enough to notify a subscribed user. Send out emails. - Once per day, download bandwidth histories of relays from Onionoo and check whether a relay has been running long enough and fast enough that the operator should be offered a t-shirt. Send out emails, regardless of subscriptions, and ask if operators would want one. As you can see, most of the work can be done with help of Onionoo. The parts that need to be written are a web and an email interface, a small database for subscriptions, and some glue code to talk to Onionoo. (And if you still favor the variant where somebody maintains the current Weather, be aware that it needs to parse Tor descriptors and keep its own relay database to do searches, to check how long relays are offline, and to decide which relay operators should get a t-shirt.) Here's some more information on the Onionoo service: https://onionoo.torproject.org/ Happy to provide more information! All the best, Karsten

3 4

Fwd: ECC curves that are safe safecurves.cr.yp.to
by grarpamp 10 Jan '14

10 Jan '14

---------- Forwarded message ---------- From: gwen hastings <gwen(a)cypherpunks.to> Date: Fri, Jan 10, 2014 at 9:54 AM Subject: ECC curves that are safe safecurves.cr.yp.to To: "cypherpunks(a)cpunks.org" <cypherpunks(a)cpunks.org> DJ Bernstein and Tanja Lange did a study on which ECC curves are safe to implement and use, found at http://safecurves.cr.yp.to/ YMMV as per the snowden releases but for now curve p25514 appears to be safe AND accessible in at least 2 cli type implementations. To be avoided at present is SECCURE-0.4 and below(no safe curves as per the bernstein document) GH -- Tentacle #99 ecc public key curve p25519(pcp 0.15) 1l0$WoM5C8z=yeZG7?$]f^Uu8.g>4rf#t^6mfW9(rr910 Governments are instituted among men, deriving their just powers from the consent of the governed, that whenever any form of government becomes destructive of these ends, it is the right of the people to alter or abolish it, and to institute new government, laying its foundation on such principles, and organizing its powers in such form, as to them shall seem most likely to effect their safety and happiness.’ https://github.com/TLINDEN/pcp.git to get pcp(curve25519 cli)

1 0

On the security of a commit-and-reveal solution for #8244
by George Kadianakis 10 Jan '14

10 Jan '14

(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…

3 3