April 2016 - tor-dev - lists.torproject.org

What happens to my hidden service?
by Liste 29 Dec '25

29 Dec '25

Hidden service is unavailable, but tor is running. Tor's log: Dec 12 18:10:27.000 [notice] Your Guard SECxFreeBSD64 ($D7DB8E82604F806766FC3F80213CF719A0481D0B) is failing more circuits than usual. Most likely this means the Tor network is overloaded. Success counts are 199/285. Use counts are 101/101. 253 circuits completed, 0 were unusable, 54 collapsed, and 15 timed out. For reference, your timeout cutoff is 60 seconds. is failing a very large amount of circuits. Most likely this means the Tor network is overloaded, but it could also mean an attack against you or potentially the guard itself. Dec 12 18:15:53.000 [warn] Giving up launching first hop of circuit to rendezvous point [scrubbed] for service xxxxxxxxxxxxxxx. Dec 11 13:08:59.000 [notice] We'd like to launch a circuit to handle a connection, but we already have 32 general-purpose client circuits pending. Waiting until some finish. [268 similar message(s) suppressed in last 600 seconds] Dec 11 13:43:12.000 [warn] onion_skin_client_handshake failed. Dec 11 13:43:12.000 [warn] circuit_finish_handshake failed. Dec 11 13:43:12.000 [warn] connection_edge_process_relay_cell (at origin) failed. Dec 11 00:34:57.000 [warn] Giving up launching first hop of circuit to rendezvous point [scrubbed] for service .... Dec 10 10:09:01.000 [warn] rend_service_introduce(): Bug: Internal error: Got an INTRODUCE2 cell on an intro circ (for service "...") with no corresponding rend_intro_point_t. Dec 10 10:09:03.000 [warn] rend_service_introduce(): Bug: Internal error: Got an INTRODUCE2 cell on an intro circ (for service "...") with no corresponding rend_intro_point_t. Dec 10 10:09:04.000 [warn] rend_service_introduce(): Bug: Internal error: Got an INTRODUCE2 cell on an intro circ (for service "...") with no corresponding rend_intro_point_t. Dec 10 12:42:19.000 [warn] rend_service_introduce(): Bug: Internal error: Got an INTRODUCE2 cell on an intro circ (for service "...") with no corresponding rend_intro_point_t.

3 2

Proposal 247 (Hidden Service Vanguards) Overhaul
by Mike Perry 09 Jun '17

09 Jun '17

I spent some time trying to clean up proposal 247 based on everyone's comments, as well as based on my own thoughts. Please have a look if you commented on the original proposal, and complain if I've not taken your thoughts into account. (Aaron: In particular, I made several tradeoffs in favor of performance and DoS resistance that may be at odds with some of your suggestions, but I think the end result is still OK after looking into the Sybil rates and thinking about the adversary model in more detail. You may disagree). I've attached my updated version of the proposal inline in this mail, but the canonical updated proposal is in my remote at: https://gitweb.torproject.org/user/mikeperry/torspec.git/tree/proposals/247… Here's a summary of the changes (which are also listed in Git): * Try to make a coherent threat model and specify its assumptions * Fold in my comments about using disjoint sets ("buckets") for the third level guard. * Make the parameter discussion subsection its own section, and include tables with far more detail for the Sybil success rates. * Put the rotation period in a separate subsection from the number of guards * Switch to using min(X,X) and max(X,X) for the distribution for the second and third layer guard lifespans, respectively. Add a subsection describing this distribution (3.2.3) * Changed the default parameters based on these tables, and based on my own intuition about Tor's performance properties. * Move the load balancing, torrc, and other performance considerations to their own section (Section 5). * Move "3.2. Distinguishing new HS circuits from normal HS circuits" to section 4.1. * Fold in some of "3.3. Circuit nodes can now be linked to specific hidden services" into 4.1. Some of it I just removed, though, because I did not find it credible. * Added Roger's concerns about guard linkability to Section 4.2. * Added a denial of service subsection to Section 4.3. ================================ Filename: 247-hs-guard-discovery.txt Title: Defending Against Guard Discovery Attacks using Vanguards Author: George Kadianakis Created: 2015-07-10 Status: Draft 0. Motivation A guard discovery attack allow attackers to determine the guard node of a Tor client. The hidden service rendezvous protocol provides an attack vector for a guard discovery attack since anyone can force an HS to construct a 3-hop circuit to a relay (#9001). Following the guard discovery attack with a compromise and/or coercion of the guard node can lead to the deanonymization of a hidden service. 1. Overview This document tries to make the above guard discovery + compromise attack harder to launch. It introduces an optional configuration option which makes the hidden service also pin the second and third hops of its circuits for a longer duration. With this new path selection, we force the adversary to perform a Sybil attack and two compromise attacks before succeeding. This is an improvement over the current state where the Sybil attack is trivial to pull off, and only a single compromise attack is required. With this new path selection, an attacker is forced to do a one or more node compromise attacks before learning the guard node of a hidden service. This increases the uncertainty of the attacker, since compromise attacks are costly and potentially detectable, so an attacker will have to think twice before beginning a chain of node compromise attacks that he might not be able to complete. 1.1. Visuals Here is how a hidden service rendezvous circuit currently looks like: -> middle_1 -> middle_A -> middle_2 -> middle_B -> middle_3 -> middle_C -> middle_4 -> middle_D HS -> guard -> middle_5 -> middle_E -> Rendezvous Point -> middle_6 -> middle_F -> middle_7 -> middle_G -> middle_8 -> middle_H -> ... -> ... -> middle_n -> middle_n this proposal pins the two middles nodes to a much more restricted set, as follows: -> guard_3A_A -> guard_2_A -> guard_3A_B -> guard_3A_C -> Rendezvous Point HS -> guard_1 -> guard_3B_D -> guard_2_B -> guard_3B_E -> guard_3B_F -> Rendezvous Point Note that the third level guards are partitioned into buckets such that they are only used with one specific second-level guard. In this way, we ensure that even if an adversary is able to execute a Sybil attack against the third layer, they only get to learn one of the second-layer Guards, and not all of them. This prevents the adversary from gaining the ability to take their pick of the weakest of the second-level guards for further attack. 2. Design This feature requires the HiddenServiceGuardDiscovery torrc option to be enabled. When a hidden service picks its guard nodes, it also picks two additional sets of middle nodes `second_guard_set` and `third_guard_set` of size NUM_SECOND_GUARDS and NUM_THIRD_GUARDS respectively for each hidden service. These sets are unique to each hidden service created by a single Tor client, and must be kept separate and distinct. When a hidden service needs to establish a circuit to an HSDir, introduction point or a rendezvous point, it uses nodes from `second_guard_set` as the second hop of the circuit and nodes from that second hop's corresponding `third_guard_set` as third hops of the circuit. A hidden service rotates nodes from the 'second_guard_set' at a random time between MIN_SECOND_GUARD_LIFETIME hours and MAX_SECOND_GUARD_LIFETIME hours. A hidden service rotates nodes from the 'third_guard_set' at a random time between MIN_THIRD_GUARD_LIFETIME and MAX_THIRD_GUARD_LIFETIME hours. These extra guard nodes should be picked with the same path selection procedure that is used for regular middle nodes (though see Section 5.1 for performance reasons to restrict this slightly). Each node's rotation time is tracked independently, to avoid disclosing the rotation times of the primary and second-level guards. XXX how should proposal 241 ("Resisting guard-turnover attacks") be applied here? 2.1. Security parameters We set NUM_SECOND_GUARDS to 4 nodes and NUM_THIRD_GUARDS to 16 nodes (ie four sets of four). XXX: 3 and 12 might be another option here, in which case our rotation period for the second guard position can be reduced to 15 days. We set MIN_SECOND_GUARD_LIFETIME to 1 day, and MAX_SECOND_GUARD_LIFETIME to 33 days, for an average rotation rate of ~11 days, using the min(X,X) distribution specified in Section 3.2.2. We set MIN_THIRD_GUARD_LIFETIME to 1 hour, and MAX_THIRD_GUARD_LIFETIME to 18 hours, for an average rotation rate of ~12 hours, using the max(X,X) distribution specified in Section 3.2.2. XXX make all the above consensus parameters? Yes. Very yes, especially if we decide to change the primary guard lifespan. See Section 3 for more analysis on these constants. 3. Rationale and Security Parameter Selection 3.1. Threat model, Assumptions, and Goals Consider an adversary with the following powers: - Can launch a Sybil guard discovery attack against any node of a rendezvous circuit. The slower the rotation period of the node, the longer the attack takes. Similarly, the higher the percentage of the network is compromised, the faster the attack runs. - Can compromise any node on the network, but this compromise takes time and potentially even coercive action, and also carries risk of discovery. We also make the following assumptions about the types of attacks: 1. A Sybil attack is noisy. It will require either large amounts of traffic, multiple test circuits, or both. 2. A Sybil attack against the second or first layer Guards will be more noisy than a Sybil attack against the third layer guard, since the second and first layer Sybil attack requires a timing side channel in order to determine success, where as the Sybil success is almost immediately obvious to third layer guard, since it will now be returned as a rend point for circuits for the hidden service in question. 3. As soon as the adversary is confident they have won the Sybil attack, an even more aggressive circuit building attack will allow them to determine the next node very fast (an hour or less). 4. The adversary is strongly disincentivized from compromising nodes that may prove useless, as node compromise is even more risky for the adversary than a Sybil attack in terms of being noticed. Given this threat model, our security parameters were selected so that the first two layers of guards should be hard to attack using a Sybil guard discovery attack and hence require a node compromise attack. Ideally, we want the node compromise attacks to carry a non-negligible probability of being useless to the adversary by the time they complete. On the other hand, the outermost layer of guards should rotate fast enough to _require_ a Sybil attack. 3.2. Parameter Tuning 3.2.1. Sybil rotation counts for a given number of Guards The probability of Sybil success for Guard discovery can be modeled as the probability of choosing 1 or more malicious middle nodes for a sensitive circuit over some period of time. P(At least 1 bad middle) = 1 - P(All Good Middles) = 1 - P(One Good middle)^(num_middles) = 1 - (1 - c/n)^(num_middles) c/n is the adversary compromise percentage In the case of Vanguards, num_middles is the number of Guards you rotate through in a given time period. This is a function of the number of vanguards in that position (v), as well as the number of rotations (r). P(At least one bad middle) = 1 - (1 - c/n)^(v*r) Here's detailed tables in terms of the number of rotations required for a given Sybil success rate for certain number of guards. 1.0% Network Compromise: Sybil Success One Two Three Four Five Six Eight Nine Ten Twelve Sixteen 10% 11 6 4 3 3 2 2 2 2 1 1 15% 17 9 6 5 4 3 3 2 2 2 2 25% 29 15 10 8 6 5 4 4 3 3 2 50% 69 35 23 18 14 12 9 8 7 6 5 60% 92 46 31 23 19 16 12 11 10 8 6 75% 138 69 46 35 28 23 18 16 14 12 9 85% 189 95 63 48 38 32 24 21 19 16 12 90% 230 115 77 58 46 39 29 26 23 20 15 95% 299 150 100 75 60 50 38 34 30 25 19 99% 459 230 153 115 92 77 58 51 46 39 29 5.0% Network Compromise: Sybil Success One Two Three Four Five Six Eight Nine Ten Twelve Sixteen 10% 3 2 1 1 1 1 1 1 1 1 1 15% 4 2 2 1 1 1 1 1 1 1 1 25% 6 3 2 2 2 1 1 1 1 1 1 50% 14 7 5 4 3 3 2 2 2 2 1 60% 18 9 6 5 4 3 3 2 2 2 2 75% 28 14 10 7 6 5 4 4 3 3 2 85% 37 19 13 10 8 7 5 5 4 4 3 90% 45 23 15 12 9 8 6 5 5 4 3 95% 59 30 20 15 12 10 8 7 6 5 4 99% 90 45 30 23 18 15 12 10 9 8 6 10.0% Network Compromise: Sybil Success One Two Three Four Five Six Eight Nine Ten Twelve Sixteen 10% 2 1 1 1 1 1 1 1 1 1 1 15% 2 1 1 1 1 1 1 1 1 1 1 25% 3 2 1 1 1 1 1 1 1 1 1 50% 7 4 3 2 2 2 1 1 1 1 1 60% 9 5 3 3 2 2 2 1 1 1 1 75% 14 7 5 4 3 3 2 2 2 2 1 85% 19 10 7 5 4 4 3 3 2 2 2 90% 22 11 8 6 5 4 3 3 3 2 2 95% 29 15 10 8 6 5 4 4 3 3 2 99% 44 22 15 11 9 8 6 5 5 4 3 The rotation counts in these tables were generated with: def count_rotations(c, v, success): r = 0 while 1-math.pow((1-c), v*r) < success: r += 1 return r 3.2.2. Rotation Period As specified in Section 3.1, the primary driving force for the third layer selection was to ensure that these nodes rotate fast enough that it is not worth trying to compromise them, because it is unlikely for compromise to succeed and yield useful information before the nodes stop being used. For this reason we chose 1 to 18 hours, with a weighted distribution (Section 3.2.3) causing the expected average to be 12 hours. From the table in Section 3.2.1, it can be seen that this means that the Sybil attack will complete with near-certainty (99%) in 29*12 hours (14.5 days) for the 1% adversary, 3 days for the 5% adversary, and 1.5 days for the 10% adversary. Since rotation of each node happens independently, the distribution of when the adversary expects to win this Sybil attack in order to discover the next node up is uniform. This means that on average, the adversary should expect that half of the rotation period of the next node is already over by the time that they win the Sybil. With this fact, we choose our range and distribution for the second layer rotation to be short enough to cause the adversary to risk compromising nodes that are useless, yet long enough to require a Sybil attack to be noticeable in terms of client activity. For this reason, we choose a minimum second-layer guard lifetime of 1 day, since this gives the adversary a minimum expected value of 12 hours for during which they can compromise a guard before it might be rotated. If the total expected rotation rate is 11 days, then the adversary can expect overall to have 5.5 days remaining after completing their Sybil attack before a second-layer guard rotates away. 3.2.3. Rotation distribution In order to skew the distribution of the third layer guard towards higher values, we use max(X,X) for the distribution, where X is a random variable that takes on values from the uniform distribution. In order to skew the distribution of the second layer guard towards low values (to increase the risk of compromising useless nodes) we skew the distribution towards lower values, using min(X,X). Here's a table of expectation (arithmetic means) for relevant ranges of X (sampled from 0..N). The current choice for second-layer guards is noted with **, and the current choice for third-layer guards is noted with ***. Range Min(X,X) Max(X,X) 10 2.85 6.15 11 3.18 6.82 12 3.51 7.49 13 3.85 8.15 14 4.18 8.82 15 4.51 9.49 16 4.84 10.16 17 5.18 10.82*** 18 5.51 11.49 19 5.84 12.16 20 6.18 12.82 21 6.51 13.49 22 6.84 14.16 23 7.17 14.83 24 7.51 15.49 25 7.84 16.16 26 8.17 16.83 27 8.51 17.49 28 8.84 18.16 29 9.17 18.83 30 9.51 19.49 31 9.84 20.16 32 10.17** 20.83 33 10.51 21.49 34 10.84 22.16 35 11.17 22.83 36 11.50 23.50 37 11.84 24.16 38 12.17 24.83 39 12.50 25.50 4. Security concerns and mitigations 4.1. Mitigating fingerprinting of new HS circuits By pinning the middle nodes of rendezvous circuits, we make it easier for all hops of the circuit to detect that they are part of a special hidden service circuit with varying degrees of certainty. The Guard node is able to recognize a Vanguard client with a high degree of certainty because it will observe a client IP creating the overwhelming majority of its circuits to just a few middle nodes in any given 10-18 day time period. The middle nodes will be able to tell with a variable certainty that depends on both its traffic volume and upon the popularity of the service, because they will see a large number of circuits that tend to pick the same Guard and Exit. The final nodes will be able to tell with a similar level certainty that depends on their capacity and the service popularity, because they will see a lot of rend handshakes that all tend to have the same second hop. The most serious of these is the Guard fingerprinting issue. When proposal xxx-padding-negotiation is implemented, services that enable this feature should use those padding primitives to create fake circuits to random middle nodes that are not their guards, in an attempt to look more like a client. Additionally, if Tor Browser implements "virtual circuits" based on SOCKS username+password isolation in order to enforce the re-use of paths when SOCKS username+passwords are re-used, then the number of middle nodes in use during a typical user's browsing session will be proportional to the number of sites they are viewing at any one time. This is likely to be much lower than one new middle node every ten minutes, and for some users, may be close to the number of Vanguards we're considering. This same reasoning is also an argument for increasing the number of second-level guards beyond just two, as it will spread the hidden service's traffic over a wider set of middle nodes, making it both easier to cover, and behave closer to a client using SOCKS virtual circuit isolation. 4.2. Hidden service linkability Multiple hidden services on the same Tor instance should use separate second and third level guard sets, otherwise an adversary is trivially able to determine that the two hidden services are co-located by inspecting their current chosen rend point nodes. Unfortunately, if the adversary is still able to determine that two or more hidden services are run on the same Tor instance through some other means, then they are able to take advantage of this fact to execute a Sybil attack more effectively, since there will now be an extra set of guard nodes for each hidden service in use. For this reason, if Vanguards are enabled, and more than one hidden service is configured, the user should be advised to ensure that they do not accidentally leak that the two hidden services are from the same Tor instance. 4.3. Denial of service Since it will be fairly trivial for the adversary to enumerate the current set of rend nodes for a hidden service, denial of service becomes a serious risk for Vanguard users. For this reason, it is important to support a large number of third-level guards, to increase the amount of resources required to bring a hidden service offline by DoSing just a few Tor nodes. 5. Performance considerations The switch to a restricted set of nodes will very likely cause significant performance issues, especially for high-traffic hidden services. If any of the nodes they select happen to be temporarily overloaded, performance will suffer dramatically until the next rotation period. 5.1. Load Balancing Since the second and third level "guards" are chosen from the set of all nodes eligible for use in the "middle" hop (as per hidden services today), this proposal should not significantly affect the long-term load on various classes of the Tor network, and should not require any changes to either the node weight equations, or the bandwidth authorities. Unfortunately, transient load is another matter, as mentioned previously. It is very likely that this scheme will increase instances of transient overload at nodes selected by high-traffic hidden services. One option to reduce the impact of this transient overload is to restrict the set of middle nodes that we chose from to some percentage of the fastest middle-capable relays in the network. This may have some impact on load balancing, but since the total volume of hidden service traffic is low, it may be unlikely to matter. 5.2. Circuit build timeout The adaptive circuit build timeout mechanism in Tor is what corrects for instances of transient node overload right now. The timeout will naturally tend to select the current fastest and least-loaded paths even through this set of restricted routes, but it may fail to behave correctly if there are a very small set of nodes in each guard set, as it is based upon assumptions about the current path selection algorithm, and it may need to be tuned specifically for Vanguards, especially if the set of possible routes is small. 5.3. OnionBalance At first glance, it seems that this scheme makes multi-homed hidden services such as OnionBalance[1] even more important for high-traffic hidden services. Unfortunately, if it is equally damaging to the user for any of their multi-homed hidden service locations to be discovered, then OnionBalance is strictly equivalent to simply increasing the number of second-level guard nodes in use, because an active adversary can perform simultaneous Sybil attacks against all of the rend points offered by the multi-homed OnionBalance introduction points. 5.4. Default vs optional behavior We suggest this torrc option to be optional because it changes path selection in a way that may seriously impact hidden service performance, especially for high traffic services that happen to pick slow guard nodes. However, by having this setting be disabled by default, we make hidden services who use it stand out a lot. For this reason, we should in fact enable this feature globally, but only after we verify its viability for high-traffic hidden services, and ensure that it is free of second-order load balancing effects. Even after that point, until Single Onion Services are implemented, there will likely still be classes of very high traffic hidden services for whom some degree of location anonymity is desired, but for which performance is much more important than the benefit of Vanguards, so there should always remain a way to turn this option off. 6. Future directions Here are some more ideas for improvements that should be done sooner or later: - Maybe we should make the size and rotation period of secondary/third guard sets to be configurable by the user. - To make it harder for an adversary, a hidden service MAY extend the path length of its circuits by an additional static hop. This forces the adversary to use another coercion attack to walk the chain up to the hidden service. 7. Acknowledgments Thanks to Aaron Johnson, John Brooks, Mike Perry and everyone else who helped with this idea. 1. https://onionbalance.readthedocs.org/en/latest/design.html#overview -- Mike Perry

7 14

Re: [tor-dev] Onioncat and Prop224
by str4d 09 Oct '16

09 Oct '16

On 27/04/16 22:31, grarpamp wrote: > On 4/25/16, Tim Wilson-Brown - teor <teor2345(a)gmail.com> wrote: >> >>> On 22 Apr 2016, at 17:03, grarpamp <grarpamp(a)gmail.com> wrote: >>> >>> FYI: The onioncat folks are interested in collaborating >>> with tor folks regarding prop224. >>> >>> https://gitweb.torproject.org/torspec.git/tree/proposals/224-rend-spec-ng.t… >> >> I'm interested in what kind of collaboration onioncat would like to do on >> prop224, next-generation hidden services. >> It would be great to work this out in the next few weeks, as we're coding >> parts of the proposal right now. > > Yep :) And I know Bernhard was hoping to get in touch with Roger > on this before long. > > Basically, prop224 HS being wider than 80 bits will break onioncat's > current HS onion <---> IPv6 addressing mechanism. > > They're looking at various backward compatibility options, as well > as possibly making side use of the HSDir DHT, or even integrating > more directly with the tor client. > Just FYI, I recently migrated all of I2P's spec proposals to the website, and came across a seven-year-old proposal that Bernhard wrote about improving I2P support in GarliCat: https://geti2p.net/spec/proposals/105-garlicat-name-translation I don't know how well it has aged, but given that Tor is now facing the same issues that I2P has, perhaps it can be of some use if resurrected from the dead :) > >> But the tor-onions mailing list is to discuss the technical details running >> onion services. > > Readers of tor-onions / newbies may have been unfamiliar with > onioncat. It's a way to get non-TCP between TorHS onions, thus in > the thread "Hidden datagram service". > > I think there are a nontrivial number of users interested in, and > using, non-strictly-TCP transport over an IPv6 tunnel interface. > For example, look at users of CJDNS... > > For which we should try to continue a way, in v2, to do that over > anonymous overlay network Tor / I2P. > There is already some work on doing this in I2P: https://github.com/majestrate/i2p-tools/tree/master/i2tun https://github.com/majestrate/i2p-tools/tree/master/pyi2tun I2P also natively supports non-TCP protocols if that helps (only datagrams implemented thus far). str4d

9 20

onion moshing
by David Stainton 25 Sep '16

25 Sep '16

I was inspired by onioncat to write a twisted python implementation. Onionvpn doesn't have as many features as onioncat. I've successfully tested that onionvpn and onioncat can talk to each other and play nice. Both onionvpn and onioncat implement a virtual public network. Anyone can send packets to you if they know your onion address or ipv6 address... however injection attacks are unlikely since the attacker cannot know the contents of your traffic without compromising the tor process managing the onion service. I've also tested with mosh; that is, you can use mosh which only works with ipv4 over an ipv4-to-ipv6 tunnel over onionvpn/onioncat. Like this: mosh-client -> udp/ipv4 -> ipv6 -> tun device -> tcp-to-tor -> onion service decodes ipv6 to tun device -> ipv6 -> udp/ipv4 -> mosh-server https://github.com/david415/onionvpn If an onionvpn/onioncat operator were to NAT the onion ipv6 traffic to the Internet then that host essentially becomes a special IPv6 exit node for the tor network. The same can be done for IPv4. Obviously operating such an exit node might be risky due to the potential for abuse... however don't you just love the idea of being about to use low-level network scanners over tor? I wonder if Open Observatory of Network Interference would be interested in this. david

4 3

Revisiting prop224 time periods and HS descriptor upload/downloads
by George Kadianakis 24 Jun '16

24 Jun '16

Hello, during March we discussed the cell formats of prop224: https://lists.torproject.org/pipermail/tor-dev/2016-March/010534.html The prop224 topic for this month has to do with the way descriptors get uploaded and downloaded, how this is scheduled using time periods and how the shared randomness subsystem interacts with all that. Here are some discussion topics. Lots of text on the first two, less text on the rest: - My main goal was to understand the prop224 sections [TIME-PERIODS] and [TIME-OVERLAP]. Those sections specify a system where hidden services decide in a probabilistic manner _when_ to publish their descriptor so that not all hidden services publish their descriptors at the same moment and cause a thundering herd that stampedes the network. For this to work, time is split into time periods of k hours each. A few hours before each time period, there is an overlap period where hidden services start publishing their _next_ descriptors to HSDirs, so that when the upcoming time period starts, all the HSDirs have already received the descriptors and are ready to serve them. Consider the overlap period at the end of time period #N. During that overlap period, hidden services publish their descriptors for future time period #N+1. In this case, hidden services also need to know the shared random value that will be active during time period #N+1, since it needs to be used to find the responsible HSDirs. This means, that the shared random value for time period #N+1 needs to be published _before_ the overlap period starts. This is not the case in current proposal 224, since time is split into time periods of 25 hours, which means that each day the start time shifts by one hour forward. Since the start/end times of the time periods keep on shifting, there will be cases where the right shared random value will not be accessible when the overlap period starts. So what to do? To fix this, I suggest we change the time period length to a day (24 hours). I also suggest we start time periods every day at 12:00 and finish after 24 hours same time, so that it works well with the current shared randomness schedule (where the new shared random value gets published at 00:00 every day). [It might actually be wiser to actually reverse those schedules: create the SRV at 12:00 and start the time period at 00:00] In any case, this is how this might look like: +------------------------------------------------------------------+ | | | 00:00 12:00 00:00 12:00 00:00 12:00 | | SRV#1 TP#1 SRV#2 TP#2 SRV#3 TP#3 | | | | $ |-----------$-----======|-----------$-----======| | | overlap12 overlap23 | | | +------------------------------------------------------------------+ Legend: [TP#1 = Time Period #1] [SRV#1 = Shared Random Value #1] So, this basically gives a space of 12 hours between the SRV generation and the start of the next time period. We can then easily fit an overlap period of 6 hours before the next time periods starts. In the above diagram, the "equal sign" segments are the overlap periods. 'overlap12' is the overlap period from TP#1 to TP#2. Do you think that's reasonable? And do you see any problems with changing the time period length from 25 hours to 24 hours? - So now that we have ironed out the time period stuff slightly, let's discuss the behavior that hidden services, clients and HSDirs should inherit. This email is quite long already so I'm going to go with examples, instead of formal specification. However, this stuff needs to go formally in the proposal IMO, so any help in formalizing it would be great. + Hidden Service behavior: Example 1: Our hidden service boots up at 14:00 of TP#1. In this case, we are nowhere close to the overlap period, so the hidden service should just publish its TP#1 descriptor to the HSDir hash ring using SRV#1 (which at that point should be in consensuses as "shared-rand-current-value"). The hidden service might also want to calculate its overlap OFFSET (as specified in [TIME-OVERLAP]) and schedule a time callback for publishing its TP#2 descriptors. Example 2: Our hidden service boots up at 03:00 of TP#1. That's outside of the overlap period again, but this time the hidden service needs to use the SRV from "shared-rand-previous-value" because the SRV was rotated at midnight. Example 3: Our hidden service boots up at 09:00 of TP#1. That's inside the overlap period, so the hidden service should calculate its overlap OFFSET and compare it with the current time. If it has not passed, then we are in the exact same case as Example 2. If the overlap OFFSET _has_ passed, then the hidden service needs to act as Example 2, and _also_ publish its TP#2 descriptors to a second set of HSDirs using SRV#2. I think these are all the cases for the hidden service, but I would like to formalize this in a way that can be written in the spec. Particularly, I'm not sure how to formalize which SRV to pick at a given time point. + Client behavior My current intuition with regards to client behavior is that they should always fetch descriptors from the HSDirs of the _current_ time period. They should not concern themselves with the overlap stuff _at all_. The overlap system is there so that by the time the new time period starts, all the HSDirs have received the descriptors and are ready to help the clients. Clients should never notice the overlap stuff happening. For this reason I think we can remove this paragraph from the spec: When a client is looking for a service, it must calculate its key both for the current and for the subsequent period, to decide whether the next period's key is valid yet. What do you think? + HSDir behavior Currently the spec says the following: Hidden service directories should accept descriptors at least [TODO: how much?] minutes before they would become valid, and retain them for at least [TODO: how much?] minutes after the end of the period. After discussion with David, we thought of chopping off the first part of that paragraph and not imposing any such weak restrictions for accepting descriptors (see #18332). We still have not decided about the second part of that paragraph, that is how long descriptors should be retained after the end of the period. We currently think clock skew is the only thing that can bring clients to the wrong HSDir after the end of the period. Maybe an hour is OK? David suggested 12 hours. The current Tor is doing 48 hours... Any ideas? And this half-assedly sums up the behaviors of clients/HSes and HSDirs with regards to descriptor uploads and downloads. What is missing, and do you agree that parts of this should be in the proposal? - We should revert the torspec commit: "prop224: avoid replicas with the same blinded key" https://gitweb.torproject.org/torspec.git/commit/?id=8df8c0584392240aa8fecb… It adds a whole lot of complexity to prop224 with no clear security benefit against realistic adversaries. Furthermore, the time period and descriptor download/upload logic of Tor gets very complicated with it. I discussed this with teor and special and found it reasonable. - The randomized revision-counter logic should also be simplified or even removed: https://gitweb.torproject.org/torspec.git/commit/?id=01119bf1291a40aa309dfb… I haven't looked much into this yet. If someone has thoughts please let me know. - We should use fresh salt every time we rebuild the descriptor, but not for every replica: https://gitweb.torproject.org/torspec.git/commit/?id=01e865d592ffcbb67a0e66… - teor says we should revert the double hashing here, and just use tor's random API: https://gitweb.torproject.org/torspec.git/commit/?id=93f47f4f4e7614d4b3debf… peace

5 25

GSoC: Tails Server
by segfault 14 Jun '16

14 Jun '16

Hi everyone, I'm a Tails contributor since a few months and I'm excited that I will work on the Tails Server [1] project during this year's Google Summer of Code. This project aims at providing a user-friendly interface to start onion services in Tails. My mentors are anonym (of Tails) and asn. I will start with this project four weeks early, which means I start next Monday (April 25th) and finish at the end of July. Most of the discussion on this project will happen on the appropiate Tails communication channels, i.e. the mailing lists tails-dev(a)boum.org and tails-ux(a)boum.org and the tails-dev channels on irc.oftc.net and conference.riseup.net. Regarding Tor specific questions, I will write to this list or ask in the tor channels on irc.oftc.net. I'm segfault1 on OFTC. I will send bi-weekly status reports to this list and tails-dev(a)boum.org. Cheers! segfault [1] https://tails.boum.org/blueprint/tails_server/

4 4

adding smartcard support to Tor
by Razvan Dragomirescu 03 Jun '16

03 Jun '16

Hello, I am not sure if this has been discussed before or how hard it would be to implement, but I'm looking for a way to integrate a smartcard with Tor - essentially, I want to be able to host hidden service keys on the card. I'm trying to bind the hidden service to a hardware component (the smartcard) so that it can be securely hosted in a hostile environment as well as impossible to clone/move without physical access to the smartcard. I have Tor running on the USBArmory by InversePath ( http://inversepath.com/usbarmory.html ) and have a microSD form factor card made by Swissbit ( www.swissbit.com/products/security-products/overwiev/security-products-over… ) up and running on it. I am a JavaCard developer myself and I have developed embedded Linux firmwares before but I have never touched the Tor source. Is there anyone that is willing to take on a side project doing this? Would it be just a matter of configuring OpenSSL to use the card (I haven't tried that yet)? Thank you, Razvan -- Razvan Dragomirescu Chief Technology Officer Cayenne Graphics SRL

8 34

Request for feedback/victims: cfc-0.0.2
by Yawning Angel 16 May '16

16 May '16

Hello, Thanks for the feedback so far. [ PEOPLE THAT HAVE BIG SCARY ADVERSARIES IN THEIR THREAT MODEL STILL SHOULD NOT USE THIS. ] New version with changes some that add functionality, some code of quality stuff, hence a version bump to 0.0.2, especially since it'll probably be a bit before I can focus on tackling the TODO items. Source: https://git.schwanenlied.me/yawning/cfc XPI: https://people.torproject.org/~yawning/volatile/cfc-20160327/ Major changes: * Properly deregister the HTTP event listeners on addon unload. * Toned down the snark when I rewrite the CloudFlare captcha page, since I wasn't very nice. * Additional quality of life/privacy improvements courtesy of Will Scott, both optional and enabled by default. * (QoL) Skip useless landing pages (github.com/twitter.com will be auto-redirected to the "search" pages). * (Privacy) Kill twitter's outbound link tracking (t.co URLs) by rewriting the DOM to go to the actual URL when possible. Since DOM changes made from content scripts are isolated from page scripts, this shouldn't substantially alter behavior. * (Code quality) Use a pref listener to handle preference changes. TODO: * Try to figure out a way to mitigate the ability for archive.is to track you. The IFRAME based approach might work here, needs more investigation. * Handle custom CloudFlare captcha pages (In general my philosophy is to minimize false positives, over avoiding false negatives). Looking at the regexes in dcf's post, disabling the title check may be all that's needed. * Handle CloudFlare 503 pages. * Get samples of other common blanket CDN based Tor blocking/major sites that block Tor, and implement bypass methods similar to how CloudFlare is handled. * Look into adding a "contact site owner" button as suggested by Jeff Burdges et al (Difficult?). * Support a user specified "always use archive.is for these sites" list. * UI improvements. * More Quality of Life/Privacy improvements (Come for the Street Signs, stay for the user scripts). * I will eventually get annoyed enough at being linked to mobile wikipedia that I will rewrite URLs to strip out the ".m.". * Test this on Fennec. * Maybe throw this up on addons.mozilla.org. Regards, -- Yawning Angel

6 10

exitmap modules that make *lots* of connections
by Zack Weinberg 13 May '16

13 May '16

I'm working on an exitmap module that wants to feed order of 5000 short-lived streams through each exit relay. I think this is running foul of some sort of upper limit (in STEM, or in Tor itself, not sure) on the number of streams a circuit can be used for, or how long, or something. What I see in the logs (note: I've modified eventhandler.py for more detailed debug logs) looks like 2016-04-22 16:07:53,306 [DEBUG]: Circuit status change: CIRC 6 LAUNCHED PURPOSE=GENERAL TIME_CREATED=2016-04-22T20:07:53.305851 2016-04-22 16:07:53,325 [DEBUG]: Circuit status change: CIRC 6 EXTENDED [fp] PURPOSE=GENERAL TIME_CREATED=2016-04-22T20:07:53.305851 2016-04-22 16:07:54,114 [DEBUG]: Circuit status change: CIRC 6 EXTENDED [fp],[fp] PURPOSE=GENERAL TIME_CREATED=2016-04-22T20:07:53.305851 2016-04-22 16:07:54,115 [DEBUG]: Circuit status change: CIRC 6 BUILT [fp],[fp] PURPOSE=GENERAL TIME_CREATED=2016-04-22T20:07:53.305851 2016-04-22 16:07:54,136 [DEBUG]: Port 47488 preparing to attach to circuit 6 2016-04-22 16:07:54,136 [DEBUG]: Port 47488 circuit 6 waiting for stream. 2016-04-22 16:07:54,155 [DEBUG]: Attempting to attach stream 65 to circuit 6. 2016-04-22 16:07:54,387 [DEBUG]: Port 47492 preparing to attach to circuit 6 2016-04-22 16:07:54,387 [DEBUG]: Port 47492 circuit 6 waiting for stream. 2016-04-22 16:07:54,388 [DEBUG]: Attempting to attach stream 67 to circuit 6. 2016-04-22 16:07:54,809 [DEBUG]: Port 47496 preparing to attach to circuit 6 2016-04-22 16:07:54,810 [DEBUG]: Port 47496 circuit 6 waiting for stream. 2016-04-22 16:07:54,810 [DEBUG]: Attempting to attach stream 69 to circuit 6. 2016-04-22 16:07:55,060 [DEBUG]: Port 47502 preparing to attach to circuit 6 2016-04-22 16:07:55,060 [DEBUG]: Port 47502 circuit 6 waiting for stream. 2016-04-22 16:07:55,061 [DEBUG]: Attempting to attach stream 72 to circuit 6. 2016-04-22 16:07:55,468 [DEBUG]: Port 47506 preparing to attach to circuit 6 2016-04-22 16:07:55,468 [DEBUG]: Port 47506 circuit 6 waiting for stream. 2016-04-22 16:07:55,469 [DEBUG]: Attempting to attach stream 74 to circuit 6. 2016-04-22 16:07:55,720 [DEBUG]: Port 47508 preparing to attach to circuit 6 2016-04-22 16:07:55,720 [DEBUG]: Port 47508 circuit 6 waiting for stream. 2016-04-22 16:07:55,990 [DEBUG]: Port 47512 preparing to attach to circuit 6 2016-04-22 16:07:55,990 [DEBUG]: Port 47512 circuit 6 waiting for stream. 2016-04-22 16:07:55,990 [DEBUG]: Attempting to attach stream 77 to circuit 6. 2016-04-22 16:07:56,241 [DEBUG]: Port 47518 preparing to attach to circuit 6 2016-04-22 16:07:56,241 [DEBUG]: Port 47518 circuit 6 waiting for stream. 2016-04-22 16:07:56,242 [DEBUG]: Attempting to attach stream 80 to circuit 6. 2016-04-22 16:07:56,492 [DEBUG]: Port 47528 preparing to attach to circuit 6 2016-04-22 16:07:56,492 [DEBUG]: Port 47528 circuit 6 waiting for stream. 2016-04-22 16:07:56,495 [DEBUG]: Attempting to attach stream 85 to circuit 6. 2016-04-22 16:07:56,836 [DEBUG]: Port 47536 preparing to attach to circuit 6 2016-04-22 16:07:56,836 [DEBUG]: Port 47536 circuit 6 waiting for stream. 2016-04-22 16:07:56,836 [DEBUG]: Attempting to attach stream 89 to circuit 6. 2016-04-22 16:07:57,100 [DEBUG]: Port 47540 preparing to attach to circuit 6 2016-04-22 16:07:57,100 [DEBUG]: Attempting to attach stream 91 to circuit 6. 2016-04-22 16:07:57,351 [DEBUG]: Port 47544 preparing to attach to circuit 6 2016-04-22 16:07:57,351 [DEBUG]: Port 47544 circuit 6 waiting for stream. 2016-04-22 16:07:57,352 [DEBUG]: Attempting to attach stream 93 to circuit 6. 2016-04-22 16:07:57,769 [DEBUG]: Port 47550 preparing to attach to circuit 6 2016-04-22 16:07:57,769 [DEBUG]: Port 47550 circuit 6 waiting for stream. 2016-04-22 16:07:57,769 [DEBUG]: Attempting to attach stream 96 to circuit 6. 2016-04-22 16:07:58,118 [DEBUG]: Port 47554 preparing to attach to circuit 6 2016-04-22 16:07:58,118 [DEBUG]: Port 47554 circuit 6 waiting for stream. 2016-04-22 16:07:58,118 [DEBUG]: Attempting to attach stream 98 to circuit 6. 2016-04-22 16:08:04,697 [DEBUG]: Circuit status change: CIRC 6 CLOSED [fp],[fp] PURPOSE=PATH_BIAS_TESTING TIME_CREATED=2016-04-22T20:07:53.305851 REASON=FINISHED 2016-04-22 16:08:05,878 [DEBUG]: Port 47690 preparing to attach to circuit 6 2016-04-22 16:08:05,878 [DEBUG]: Port 47690 circuit 6 waiting for stream. 2016-04-22 16:08:05,879 [DEBUG]: Attempting to attach stream 166 to circuit 6. 2016-04-22 16:08:05,879 [WARNING]: Failed to attach stream because: Unknown circuit "6" You can see that circuit 6 is no longer available, but the module is still trying to use it. It looks like it lasted for almost exactly ten seconds, which smells like a time limit, but I can't find any relevant configuration parameters in the documentation. Rather than trying to make a circuit survive as long as necessary, which might not even be possible, it'd probably be better if exitmap could notice that it's lost a circuit that's still in use and create a new one. However, I'm not sure how to do that in the current architecture. The existing code has "one circuit per module invocation = one circuit per exit node" as a pretty deeply embedded design constraint. Anyone have any ideas? Full logfile available on request, but it's huge. zw

2 2

Proposal: Tor with collective signatures
by Nicolas Gailly 03 May '16

03 May '16

Hi all, Since the first post, I've received some comments off-list and consequently added more sections to the proposal. Particularly, it adds a detailed description of the messages that needs to be passed down between the witnesses, paragraphs to answer some questions, and a link to the official paper. I hope it gets clearer and answer most of your questions :) Please, feel free to ask questions on/off list, I'd be happy to discuss about it anytime ;) (irc: nikkolasg) Thanks, Nicolas version 0.2: - 3.2.1 Setup : explicitly using Fallback directory mirrors as witnesses - 3.2.2 Operation: what does a witness that refuse to sign do - 3.2.3 added incremental deployment section - 3.3 : added evolution of the CoSi set of witnesses section - 3.1 added signature description - 5 Specifications: 5.1: Protocol 5.2: Format ------------------------------------------------------------------------------------------ Filename: tor_cosi.txt Title: Tor Cosi Author: Nicolas GAILLY, DeDiS lab, EPFL Created: 09.03.2016 Status: draft Version: 0.2 0. Introduction This document describes how to provide and use a decentralized witness cosigning mechanism in order to gain proactive transparency and public accountability for the Tor consensus documents. Directory Authorities (DA) send their document to this set of witnesses and embed the signature within the document. Tor relays and clients can choose to refuse a consensus document if it has not been accepted and signed by a threshold of witnesses. 1. Overview A weakness of the current DA system is that if any 5 of the 9 DAs’ keys are stolen or coerced they could be used to sign fake directories that the attacker might use secretly in another part of the world to compromise Tor clients in the attacker’s domain. We propose to address this class of attacks by incorporating decentralized witness cosigning (CoSi) into the directory signing process, which ensures that any consensus document must be not only signed by appropriate DAs, but also publicly witnessed, signed and logged by a larger group of servers acting as witnesses, before clients will accept the directory. A Tor relay or client expects to receive an additional "CoSi" signature alongside the consensus document. They verify if the signature is correct and whether a sufficient number of witnesses attested that the consensus document is valid or not. The Tor project would fix such a threshold in the default configuration but any user or relay is free to adjust this value to its own need. In order to verify the signature, they need to have the individuals public keys of all the witnesses beforehand. This "CoSi certificate" can be embedded in the software in the same way certificate pinning does. 2. Motivation Tor's DAs are comprised of 9 servers (and one extra for the bridges): four of them are in the US and 5 of them are in the EU. Attacking these central and vital points of the Tor network is clearly within the reach of state level adversaries if they were to collaborate. Recent stories about surveillance show that such a collaboration is already happening. For example, let's imagine a plausible situation where a state-level attacker secretly coerces and/or steals the private keys of 5 of the 9 DAs, takes them back to the Republic of Tyrannia where they control the ISPs and the country’s Internet connectivity to the rest of the world. The government embeds those keys in their “Great Firewall” type devices, and uses them to secretly MITM attack targeted Tor users within Tyrannia by giving them correctly-signed but completely false views of the Tor directory in which all of the available relays are run by the Tyrannian authorities. Since this attack does not attack the consensus documents that the legitimate DAs are regularly broadcasting to the rest of the world, neither the Tor project nor anyone else outside of Tyrannia will have the opportunity to see or become aware of the fake consensus documents, and not many people even inside Tyrannia might have the opportunity to detect the attack if it is carefully targeted against the small number of suspected activists and journalists the government does not like. The main goal of CoSi applied in Tor should be to ensure consensus document transparency: that is, ensure the property that any consensus document that any Tor client anywhere will accept has been observed and logged by a significant number of parties throughout the world, so that any misuse of a quorum of 5 DA keys anywhere will be quickly detectable (soon, if not necessarily during the signing process itself). 3. Design The first part will talk more about the architecture of a "CoSi" system and the second part will go into more detail about how such a system can be integrated in Tor. For more details, please refer to the official paper [0]. 3.1 Simplified Architecture The designated leader arranges all the witnesses in a tree. The public keys of each participants are aggregated to form an aggregate public key. The tree is only there for performance reasons and can be reconfigured at any point in time without affecting security (the latest experiments showed that we could run up to 8000 nodes with a 2 second delay for generating a signature). Once the tree is constructed, its "certificate" represents the aggregate public key and all its individual public keys of each witnesses. At the end of a signature round, the client will be able to verify the CoSi signature (which uses Schnorr signatures) using the aggregate public key. A CoSi signature have two components: - Schnorr signature - Exceptions: bitmap of length equal to the size of the witness group used by absent witnesses or refusing-to-sign witnesses (see 3.2.2 Operations). Besides contributing to the signing, each witness can and should perform any readily feasible syntactic and semantic correctness checks on the leader’s proposed statements before signing off on them. They can / should probably publish logs of the statements they witness or simply make available a public mirror of everything that its tree roster has been asked to sign. 3.2 CoSi in Tor 3.2.1 Setup CoSi relies on a list of decentralized cosigning witnesses, an optional role to be supported by a future version of the standard Tor relay software. The set of witness servers will initially be defined as the D.A. and a subset of the Fallback Directory Mirrors [2], namely the set of relays that are (a) deemed stable enough by the same criteria as used for selecting Fallback Directory Mirrors, (b) are running a recent enough version of the Tor relay software to support the CoSi witness server role, and (c) have not opted out of playing this CoSi witness role. That way the deployment cost is drastically reduced as software will already have the keys to verify a CoSi signature. Another criteria for the tree construction includes the latency between witnesses. One can collect information about the communication latencies between the witnesses and construct a shortest-path spanning tree using this data in order to reduce the global latency of the system. 3.2.2 Operations Once the tree is setup and each one knows about it (have the certificate), then the signature process happens for each consensus document. The CoSi protocol produces a collective signature in response to the initiation of the protocol by a leader. This signature is then included in the consensus document so clients don't have to request it from another party. If a witness does not want to sign, it toggles the bit at its index in the bitmap. Its index is determined as the index in the list of witnesses from the CoSi certificate. The client will then see a "1" bit in the bitmap, and will subtract the corresponding public key of the witness from the aggregate public key. That way, the client is still able to verify the signature and it knows about which witnesses refused to sign off. The mechanism is similar for witnesses that went offline. The parent of an offline witness will set the bit in the bitmap of the failed witness. One issue for discussion is who should initiate CoSi protocol rounds and at what times. For example, each of the 9 DAs (or whatever subset is online) could independently initiate CoSi rounds on each directory consensus event, producing up to nine separate, redundant collective signatures on each directory consensus. Alternatively, the common case might be for one of the 9 DAs to be the CoSi initiator at a given time, with a round-robin leader-change mechanism ensuring that another leader takes over if the prior one becomes unavailable. A related issue for discussion is whether it could be problematic if there are two or more distinct collective signatures for a given directory consensus, and whether it is a problem if distinct subsets of 5 DAs might (perhaps accidentally) produce multiple slightly different, though valid and legitimately-signed, consensus documents at about the same time. In other words, does Tor directory consensus “need” strong consistency with a single serialized timeline, as Byzantine consensus protocols are intended to provide - or is weak consistency with occasional cases of multiple concurrent consensus documents and/or collective signatures acceptable? 3.2.3 Integration First of all, integrating CoSi would *not* immediately affect the fundamental structure or function of the current DAs: there could still be 9 of them, of which any 5 can authorize the release of a new consensus document, as they do now. Secondly, CoSi would not necessarily change anything about how the 9 DAs decide on how to compute these directory consensus documents; e.g., it would not prevent the DAs from working together to block the inclusion of (or assignment of bandwidth-weight to) relays that might be perceived by the DAs as doing bad things. Finally, full backward compatibility with old Tor clients and relay software may be maintained by treating the new CoSi-generated collective signature as just an additional signature that gets attached to and distributed with consensus documents. It may be treated as a special “10th virtual DA” that does not help authorize decisions but just publicly witnesses the output of the regular 9 DAs. Old client and relay software can simply ignore that new collective signature, whereas new software might look for it and over time gradually increase the threshold number of witnesses it expects to see. For incremental deployment purposes, it's reasonable to think that those Fallback Directory mirrors servers probably would not deply CoSi support all at the same time. Moreover, this set of witnesses might be a subset of the Fallback Directoy mirrors and some of them would not want to be cosigners. The hard-coded list of mirrors into the Tor client might need to be annotated with a “cosigner flag" for each such mirror, allowing some bootstrap relays to be cosigners and others not. The witness group is then simply the subset of fallback directory mirrors with the cosigner flag set. 3.3 Evolution of the CoSi set of witnesses One obvious solution for the evolution of the CoSi set of winesses lies into the version-ing mechanism of Tor. A particular Tor client version would be associated with a particular cosigning group which consists of the D.A. and the Fallback Directory Mirrors whose keys are embedded into the source code of this Tor version with this "cosigner flag" set. A client will have the latest CoSi set keys when and only when its Tor client would be upgraded - just like the list of directory authorities. 3.4 Optional: Break-the-glass Emergency Directory Adjustments In case of emergency, the delay caused by having to coordinate among 5 DAs in order to make anything happen (i.e. excluding a set of malicious nodes) can be problematic. This section proposes a mechanism in which the CoSi witnesses can accept and witness not just “full consensus” documents (signed by 5 DAs), but can also accept “emergency adjustments”, which are highly-constrained deltas (diffs) to an existing full consensus document signed by a smaller threshold of DAs, e.g., 2 or even just 1. For example, the CoSi witness cosigning rules might require that an emergency directory-adjustment must: - be a diff against a “fresh”, recent full consensus document (perhaps *the* most recent one), - can make no modifications to the full consensus other than some pre-defined operations such as decreasing bandwidth weights assigned to relays, - cannot affect the directory-wide total bandwidth weight by more than X% (e.g., 1% or .1%). These suggestions are just a few imaginable rules to get the idea across; the “right” rules would of course need much more discussion. This way, if one or two DAs discovers or even strongly suspects an attack of some kind, they can take emergency countermeasures against the attack and be able to roll them out to clients quickly without having to get a full 5 DAs out of bed - but because the delta-consensus is still witness-cosigned automatically by (perhaps) all the DAs and a number of additional trusted relays, we get the strong accountability provision that the use of such a “break-the-glass” emergency provision will immediately become known to the other DAs as soon as they do get out of bed. Such a break-the-glass emergency adjustment mechanism could be designed, if desired, so that ordinary clients and relays cannot immediately tell the difference between a directory consensus produced via the normal threshold of 5 DAs and one that was produced as a delta via the emergency adjustment mechanism. Only the witness cosigners would necessarily need to know which collectively-signed directories were authorized via the full consensus procedure or via a break-the-glass adjustment. So if it’s important to keep it secret from the general public the precise reason for a particular directory update, that can be accommodated. Only the more-trusted group of witness cosigners (and obviously all the DAs themselves) would necessarily know the precise origin and administrative justification of a given directory update. With even fancier crypto, even the witnesses would not necessarily need to know, but that’s beyond the scope of this proposal and its desirability may be questionable at any rate. 4. Security implications 4.1 Cons Since the structure is a tree, if any node fails, there must be some failover mechanisms to restore connectivity between the children of the failed node and the rest of the tree. Since the DA reach consensus every hour [1], with the help of the gossiping network, the availability problem is not an issue. 4.2 Benefits Technically, it is quite easy to implement witness cosigning if the group of witnesses is small. If we want the group of witnesses to be large, however – and we do, to ensure that compromising transparency would require not just a few but hundreds or even thousands of witnesses to be colluding maliciously – then gathering hundreds or thousands of individual signatures could become painful and inefficient. Worse, every client would need to check all these signatures individually. The key technical contribution of our research is a distributed protocol that makes large, decentralized witness cosigning groups practical. This decentralized approach enables the security of the whole system to scale with the number of witnesses. Not only does this system dramatically increase the cost of successfully deploying an attack on the DA (the attacker would have to corrupt a large majority of the witnesses), it also decreases the incentive to launch such an attack because the threshold of witnesses that are required to sign the document for the signature to be accepted can be locally set on each client. 4.3 Differences between CoSi and Certificate Transparency Prior transparency mechanisms have two weaknesses. First they do not significantly increase the number of secret keys an attacker must control to compromise any client device, and client devices cannot even retroactively detect such compromise unless they can actively communicate with multiple well-known Internet servers. For example, even with Certificate Transparency, an attacker can forge an Extended Validation (EV) certificate for Chrome after compromising or coercing only three parties: one Certificate Authority (CA) and two log servers. Since many CAs and log servers are in US jurisdiction, such an attack is clearly within reach of the US government. If such an attack does occur, Certificate Transparency cannot detect it unless the victim device has a chance to communicate or gossip the fake certificate with other parties on the Internet – after it has already accepted and started using the fake digital certificate. In the case of Tor Transparency, the attack is harder because the attacker would have to compromise the three parties plus a majority of Directory Authorities but facing a state-level adversary the threat is still plausible. One way to increase the difficulty of the attack is to make sure the logs servers are scattered in different places of the world. Second, the attacker can still evade transparency by controlling the client’s Internet access paths. For example, a compromised Internet service provider (ISP) or corporate Internet gateway can defeat retroactive transparency mechanisms by persistently blocking a victim device’s access to transparency servers elsewhere on the Internet. Even if the user’s device is mobile, a state intelligence service such as China’s “Great Firewall” could defeat retroactive transparency mechanisms by persistently blocking connections from a targeted victim’s devices to external transparency servers, in the same way that China already blocks connections to many websites and Tor relays. Using CoSi requires the clients to have the list of public keys of all the witnesses embedded in the software, like certificate pinning. In order to reduce the size of this CoSi certificate, we embed the aggregated public key of all the witnesses and a hash representing the root of a Merkle tree containing the public key of all the witnesses. Using the certificate this way provides an universally-verifiable commitment to all the witnesses’ public keys, without the certificate actually containing them all. 5. Specifications 5.1 Protocol We will describe quickly the protocol here; for a more detailed explanation, please refers to the academic paper [0]. The setup is as described in 3.2.1. The protocol in itself consists of four phases: - Announcement: The leader broadcast down the consensus document to its children, which in turn also broadcast to their children,etc. - Commitment: When the leaves of the CoSi tree get the consensus document, generate its random value v(i) and the corresponding commitment V(i) and sends V(i) up to its parent. If a leaf refuses to sign this consensus document, it does not create any commitment. Each intermediate node aggregate all the commitments of their children, add their own commitment (or nothing if it refuses to sign) and send the result up in the tree. The root gets the aggregated commitment V of all signing witnesses. - Challenge: The root then compute the challenge c = H( m || V ), with m being the consensus document and H being a collision resistant hash function that returns a scalar, and distribute the challenge down the tree like in the Announcement phase. - Response: Starting from the leaves, each witnesses compute its response r(i) = v(i) - c * x(i), where x(i) is the long term private key of the witness. If the witness refuses to sign, it simply set the n-th bit of the bitmap to "1", where n is the index of the witness in the "CoSi certificate" (the list of all individual public keys). Each intermediate nodes in the tree aggregate the responses and the bitmap of all its children, aggregate with its own response/bitmap and send that up in the tree. At the end of the protocol, the root gets the aggregated response r. The signature is the tuple (c,r) and must be included in the consensus document. If no exceptions occurred (i.e. the bitmap contains all "0"s), the signature can be verified using the aggregate public key of all witnesses using standard Schnorr verification algorithm [3]. If an exception occurs, the client needs to lookup the indexes where the bitmap contains "1"s. The client then lookup the corresponding public keys (from the list of public keys of witnesses) and subtract each of them from the aggregate public key. The client can then use this reduced public key to verify the signature as usual. 5.2 Format + The "CoSi certificate" is a list of all witnesse's ed25519 public keys and the aggregate public key of all individual public keys. Please note that while the current implementation only uses ed25519, it is completely possible to use any other elliptic curve implementations. + A CoSi signature contains: - the challenge c, an ed25519 scalar - the response r, an ed25519 scalar - the bitmap of exceptions, whose length is equal to the number of witnesses. + The messages sent during the four following phases are as follow: - Announcement: consensus document - Commitment: an ed25519 curve point - Challenge: an ed25519 scalar - Response: an ed25519 scalar and the exception bitmap 6. Compatibility 7. Implementation Implementation in Go is open source at: https://github.com/dedis/cothority 8. Performance 9. Acknowledgements This proposals has received some valuable feedback from Bryan Ford, Linus Gasser, Ismail Khoffi, Philipp Jovanovic, and Ludovic Barman. A. References [0] http://arxiv.org/pdf/1503.08768v3.pdf [1] https://collector.torproject.org [2] https://trac.torproject.org/projects/tor/wiki/doc/FallbackDirectoryMirrors [3] https://en.wikipedia.org/wiki/Schnorr_signature

3 6