tor-commits

tor-commits@lists.torproject.org

June 2015

22 participants
1871 discussions

[tech-reports/master] Import hidden-service-stats report from pad.
by karsten＠torproject.org 17 Jun '15

17 Jun '15

commit 8d61d733dad03a3bace814cfe5972759f9716757 Author: Karsten Loesing <karsten.loesing(a)gmx.net> Date: Wed Nov 26 10:38:47 2014 +0100 Import hidden-service-stats report from pad. --- 2015/hidden-service-stats/.gitignore | 3 + 2015/hidden-service-stats/hidden-service-stats.tex | 1016 ++++++++++++++++++++ 2015/hidden-service-stats/tortechrep.cls | 1 + 3 files changed, 1020 insertions(+) diff --git a/2015/hidden-service-stats/.gitignore b/2015/hidden-service-stats/.gitignore new file mode 100644 index 0000000..2c5e321 --- /dev/null +++ b/2015/hidden-service-stats/.gitignore @@ -0,0 +1,3 @@ +.DS_Store +hidden-service-stats.pdf + diff --git a/2015/hidden-service-stats/hidden-service-stats.tex b/2015/hidden-service-stats/hidden-service-stats.tex new file mode 100644 index 0000000..ef8f46c --- /dev/null +++ b/2015/hidden-service-stats/hidden-service-stats.tex @@ -0,0 +1,1016 @@ +\documentclass{tortechrep} +\usepackage{url} +\usepackage{hyperref} +\usepackage{longtable} + +\begin{document} + +\title{Hidden-service statistics reported by relays} + +\author{David Goulet, George Kadianakis, Karsten Loesing} + +\contact{\href{mailto:dgoulet@torproject.org}{dgoulet@torproject.org},% +\href{mailto:asn@torproject.org}{asn@torproject.org},% +\href{mailto:karsten@torproject.org}{karsten@torproject.org}} + +\reportid{DRAFT} +\date{January XX, 2015} + +\maketitle + +% Text conventions +% - Each sentence ends with a newline, even inside a paragraph. +% - Lines are at most 74 characters wide. +% - Abbreviations are best avoided. +% - Code, cell names, etc. are put inside \verb+...+. + +\begin{abstract} +This document discusses new hidden-service related statistics to be +gathered by relays and reported to the directory authorities in their +extra-info descriptors. +\end{abstract} + +\section{Motivation} + +We have little insight into hidden-service usage in the Tor network. +The statistics discussed in this document shall help us get a basic +understanding of hidden-service usage, improve their performance, find +bugs, etc. + +\section{Design} + +The statistics discussed here can all be gathered by relays taking one of +three possible roles in the rendezvous protocol: as 1) introduction point, +2) rendezvous point, or 3) hidden-service directory. +All statistics will be reported by relays to the directory authorities in +their extra-info descriptors, possibly every 24 hours. + +General considerations for gathering hidden-service statistics: + +\begin{itemize} +\item Should we report number and type of failures in the protocol, if +these statistics are not sufficient to actually debug a problem? +Could be a starting point to look at actual logs from relays. +But is this what statistics are for? +\item Should we not report statistics if a relay acted as dir/IPo/RPo for +less than a certain threshold of clients/services? +Can we make sure that an adversary doesn't generate traffic on their own +to push a relay above that threshold and report a tiny number of real +users? +\end{itemize} + +There are no plans for gathering hidden-service statistics on hidden +servers or clients, mostly because there is no data-collecting +infrastructure in place and because privacy implications are even less +clear in the case of single clients or servers reporting statistics than +in the case of relays serving dozens or hundreds of hidden services and +their clients. + +Note: there is an evaluation in the next section that can lead to +positive/negative/neutral recommendations for actually proposing and +implementing statistics. + +\subsection{Statistics from relays acting as introduction points} + +The following statistics are related to relays acting as introduction +points. +These cover (1) services establishing introduction points +(\verb+ESTABLISH_INTRO+ cell) and (2) clients sending introductions to +introduction points (\verb+INTRODUCE1+ cell).% and 3) the server +%responding to the introduction point (the server does not respond to the +%introduction point). + +\subsubsection{Statistics on hidden services establishing introduction +points} + +\paragraph{Number of attempts to establish an introduction point (1.1.1.)} + +\subparagraph{Details} + +A relay counts how many \verb+ESTABLISH_INTRO+ cells it receives during +the statistics interval. + +\subparagraph{Benefits} + +We could validate that we have a ``uniform'' random distribution among +chosen introduction points in the network. +If not, there might be a problem. + +\subparagraph{Risks} +Considering we have a good randomness meaning every relay has the same +chance to be picked, there are no obvious risks to share this. +If not, we don't see a real risk for an attacker to know that a specific +relay got chosen X times instead of the measured average Y. + +\paragraph{Time from establishing a circuit to becoming an introduction +point (1.1.2.)} + +% (the following distinction cannot be made, AFAIK. here's what happens: +% we receive a CREATE (?) cell from another relay that establishes the +% circuit to us, and then we receive an ESTABLISH_INTRO cell. if the time +% difference between those two events is small, we can guess that the +% client built a new circuit for using us as introduction point, or that +% she extended an existing circuit by one hop to do so. if the time +% difference is more than, say, a second, we can guess that the client +% created this circuit a while ago and only recently decided to +% cannibalize it and use it as introduction circuit. statistics would +% tell us what fraction of circuits is newly built and what was +% cannibalized; well, allow guesses about the two cases.) + +\subparagraph{Details} + +A relay measures the time difference between a circuit extension from the +previous relay in the circuit to receiving an \verb+ESTABLISH_INTRO+ cell. +A very small time difference implies that the circuit was built/extended +specifically for use as introduction point, whereas a larger time +difference hints to the hidden service re-using a pre-built circuit for +the introduction point. + +% [dgoulet]: "if the time difference between those two events is small, we +% can guess that the client built a new circuit for using us as +% introduction point, or that she extended an existing circuit by one hop +% to do so" -- I think it should be that if the time difference is small, +% one can assume a cannibalized circuit else a new circuit. +% [karsten]: it might be that we're thinking of different things when we +% say cannibalizing a circuit. here are three possible cases, from the +% perspective of a client/service: +% - create, extend, extend, ............. wait ................., +% establish introduction point -> large time difference observed by +% last relay +% - create, extend, extend, ............. wait ........., extend, +% establish introduction point -> small time difference observed by +% last relay +% - create, extend, extend, establish introduction point +% -> small time difference observed by last relay +% which of these do you call cannibalized? (I'm not sure what the code +% says here.) +% [dgoulet]: To be honest not sure which one is right but what I can see +% from the code is that a client circuit can be cannibalized for the +% introducing part which is extended with an extra hop. Now the way I see +% it is that there is probably a noticable time difference between using +% an already created circuit for which we simply extend one hop versus +% establishing a new one of 4 hops. + + +% Newly established circuit. +% Benefits: Performance reason, this can be useful to know the real cost +% (on average) of becoming an IP. Can lead to understanding bottle necks +% across the network or maybe identify relay that are misbehaving. +% Risks: That can be tricky. Having a specific time frame on a circuit +% establishment can maybe lead to some traffic correlation. +% Cannibalized circuit. +% Benefits: Performance reason, we can see if cannibalizing a circuit is +% actually a gain from a new one. This value also could tell us what's the +% fraction of circuit that are cannibalized and the net performance gain +% of that which could lead to maybe better heuristic on choosing/creating +% circuit to be cannibalized. +% Risks: Also tricky. That info could tell us clearly if the IP circuit is +% on a new or already established circuit which changes the traffic +% timing. Not sure how useful it is to an attacker though. + +\subparagraph{Benefits} + +We would learn what fraction of introduction points can be established on +short notice using pre-built circuits vs. first having to build or extend +circuits. +This is something we would measure on hidden services, but given that we +don't have statistics from those, measuring this on introduction points +seems like a fine workaround. + +% Both of these stats should probably report an average and a variance +% instead of a <timestamp> + <circ. creation time>, that would be a +% disaster. (yes, please, no data about single events; that wouldn't fit +% into descriptors anyway, and it would reveal far too much detail.) +% I really wonder if an attacker could use this average to partition part +% of the network to predict where the circuit can be located? + +\subparagraph{Risks} + +No obvious risks. % only talking about aggregate statistics here, not +% single observations. + +\paragraph{Number of failed attempts to establish an introduction point +(1.1.3.)} + +\subparagraph{Details} + +A relay can not decline to be an introduction point. +However, an \verb+ESTABLISH_INTRO+ cell might be malformed (wrong public +key, bad signature, etc...). +The relay would count the number of declined \verb+ESTABLISH_INTRO+ cells +and report them along with the total number of received +\verb+ESTABLISH_INTRO+ cells. +Or it would report successes and failures, rather than totals and +failures. + +\subparagraph{Benefits} + +Wrong \verb+ESTABLISH_INTRO+ cells shows either a very bad bug in the code +or a deliberate action (data mangling, unknown attack, DoS, ...). + +% [dgoulet]: After an IRC discussion with arma and asn, I remember that +% this one could be "cool to have" but without more information that we +% can't collect for privacy reasons, this stat would not help at all in +% the end game. The question remains if we should simply keep it or not +% even if right now we don't see a added value? +% [karsten:] right, this is a fine question, not only limited to this +% statistic. I added a new paragraph to the section start for "general +% considerations for gathering hidden-service statistics". + +\subparagraph{Risks} + +No obvious risks. + +\paragraph{Lifetime of introduction circuits (1.1.4.)} + +\subparagraph{Details} + +How long did an introduction circuit last? +Relays would report statistics like mean/median time, variance/IQR, and/or +percentiles here. + +\subparagraph{Benefits} + +The longer introduction circuits last, the better, from a performance POV. +If many circuits break after a short time period, that indicates that +services should attempt to make better path-selection decisions for +building introduction circuits. + +\paragraph{Reasons for terminating established introduction points +(1.1.5.)} + +\subparagraph{Details} + +Relays report frequencies of circuit terminations requested by services +vs. different types of failures. + +\subparagraph{Benefits} + +If there are more than a small percentage of failures, decide how to make +things more robust. + +\subparagraph{Risks} + +No obvious risks. + +\paragraph{Number of introduction circuits built with TAP vs. nTor +(1.1.6.)} + +\subparagraph{Details} + +Older clients (0.2.3.x) would build/extend circuits using TAP, newer +clients would use nTor for that. +Relays can report the number of introduction circuits that were built +using either of the two methods. +More precisely, relays would remember for each circuit how it was built, +and as soon as they receive an \verb+ESTABLISH_INTRO+ cell, they increment +one of two counters. +See ticket 13466 for details. + +\subparagraph{Benefits} + +We would learn what fraction of hidden services run older tor versions +(0.2.3.x or older). + +\subsubsection{Statistics on clients connecting to introduction points} + +\paragraph{Total number of introductions received from clients (1.2.1.)} + +\subparagraph{Details} + +Relays report how many \verb+INTRODUCE1+ cells they received from clients. + +\subparagraph{Benefits} + +This indicates that there is in fact a client trying to reach a hidden +service thus the amount of cells could give us a rough estimate of how +many clients are actually connecting and using hidden services. + +\subparagraph{Risks} + +Unclear. +On the one hand, this is basically the same risk as the amount of time a +relay is picked as an introduction point. +On the other hand, an adversary could fetch a hidden-service descriptor, +learn that a particular relay was an introduction point for that service, +and then see the relay receive many \verb+INTRODUCE1+ cells. +Basically, this statistic could be used to learn how many connection +requests a very popular hidden service gets. + +% [dgoulet]: I think, after discussing it with Nick, that this might be OK +% if the relay reports this stat for a lot of HS meaning the relay has at +% least been an IP for multiple HS thus this stat can't be correlate to +% one specific HS. Now, the period here can be difficult to get right. +% RendPostPeriod is at 1 hour but is the HS actually changes the IP set +% every upload period? If yes, that means that over let say 24 hours, that +% INTRODUCE1 cell could potentially more than one HS which seems to me ok. +% Might be still dicy if wrongly implemented. +% [karsten]: this is also a fine question, not limited to this statistic; +% which is why I moved it to the section start, too. but I'm unclear what +% this has to do with RendPostPeriod. servers don't create a new set of +% introduction points every hour, AFAIK. +% [dgoulet]: No they don't, I confirmed in the code. + +\paragraph{Number of introductions received by established introduction +point (1.2.2.)} + +\subparagraph{Details} + +Relays can serve as introduction point for an arbitrary number of hidden +services. +Relays could report statistics (like percentiles) on received +\verb+INTRODUCE1+ cell by introduction circuit. + +\subparagraph{Benefits} + +This statistic would tell us something about usage diversity of hidden +services. +A special case would be the number or fraction of established introduction +points that never sees a single \verb+INTRODUCE1+ cell. +It's unclear what we'd do with this information, though. + +\paragraph{Number of discarded client introductions by reason (1.2.3.)} + +\subparagraph{Details} + +How many \verb+INTRODUCE1+ cells have been discarded because of unknown +service/malformed (?)/whatever-can-go-wrong, by introduction point? + +\subparagraph{Benefits} + +Anything exceeding a small portion of discarded \verb+INTRODUCE1+ cells +shows either a very bad bug in the code or a deliberate action (data +mangling, unknown attack, DoS, ...). + +% [dgoulet]: That is again a "cool to have" stat but not sure how it would +% help us investiguate. It can I guess trigger an alarm but apart from +% that... +% [karsten]: right, see section start. + +\subparagraph{Risks} + +No obvious risks. +More precisely, if absolute numbers are reported, the risk is the same as +the risk of reporting the number of received \verb+INTRODUCE1+ cells; if +only fractions are reported, it's not that bad. + +\subparagraph{Recommendation} + +\paragraph{Time between establishing introduction point and receiving the +first client introduction (1.2.4.)} + +\subparagraph{Details} + +Relays report the time between \verb+ESTABLISH_INTRO+ and first +\verb+INTRODUCE1+ cell. + +\subparagraph{Benefits} + +This statistic tells us how long it takes for the hidden service to +include a relay in its descriptor and publish that descriptor, and for the +first client to fetch that descriptor and use that relay for its +introduction. +This may not be very useful, but is listed here for completeness. +% [dgoulet]: That would basically leak the RendPostPeriod (if IP changes +% at each upload) of the HS. Not sure how an attacker could use that to +% his/her advantage but to consider. +% [karsten]: again, I think you're wrong about introduction points +% changing at each upload. +% [dgoulet]: Yup, IP do *NOT* change at each upload. + +\subparagraph{Risks} + +No obvious risks. + +\paragraph{Number of client introductions coming in via circuits built +with TAP vs. nTor (1.2.5.)} + +\subparagraph{Details} + +Relays remember whether an incoming circuit was built using TAP or nTor. +Whenever they receive an INTRODUCE1 cell they increment a counter for +either TAP or nTor. +See ticket 13466 for details. + +\subparagraph{Benefits} + +We would learn what fraction of hidden-service clients run older tor +versions (0.2.3.x or older). + +%3) Stats about the server responding to the introduction point. +% (this does not happen in the protocol) +% +% - How many INTRODUCE2 replayed cell we've observed? +% This can actually be an active attack or a client sending multiple +% INTRODUCE1 cell via different introduction points. +% - Benefits: Could give us an idea of how many client are misbehaving +% (actually need to confirm if the tor client can send multiple +% INTRODUCE1 for the same service). +% - Risks: No obvious risks. +% +% Note that the amount of valid INTRODUCE2 cell seen should correspond +% to the amount of RP circuit launched (might be a cannibalized one). +% So, having that stat could be useful +% to again simply correlate that stat with the RP amout stat. Finding +% out that there is a discrepancy could help us narrow down performance +% issue. +% +% (removed the following, because receiving INTRODUCE1 triggers an event +% that ends with responding with INTRODUCE_ACK.) +% - How many INTRODUCE_ACK were sent to the client? +% - Benefits: Can be coupled with the how many INTRODUCE1 we've seen and +% look for discrepancy. The difference of intro1 and intro_ack could not +% be explained though without a reason why the HS dropped it or if the +% HS did receive the intro1 at all. So, this stat can be fun to have but +% not really useful for performance tuning I would say. +% - Risks: No obvious risks. + +\subsection{Statistics from relays acting as rendezvous points} + +The following statistics are all related to relays acting as rendezvous +points. +These statistics cover the whole process from (1) clients establishing +rendezvous points, (2) servers connecting to a client's rendezvous point, +and (3) clients creating streams to the server, exchanging data, and +tearing down the circuit. +These phases of the rendezvous protocol are also used to organize the +statistics below. +All statistics focus on the number or timing of cells exchanged in the +rendezvous protocol and underlying OR protocol. + +\subsubsection{Statistics on clients establishing rendezvous points} + +\paragraph{Number of established rendezvous points (2.1.1.)} + +\subparagraph{Details} + +Relays report how many \verb+ESTABLISH_RENDEZVOUS+ cells they received. + +\subparagraph{Benefits} + +The number of received \verb+ESTABLISH_RENDEZVOUS+ cells indicates how +many connection attempts there are by clients to services that are +running. +This number is different from the number of descriptor fetches which +happen when clients don't know yet whether a service is running, which +will be omitted if clients still have a descriptor cached from a previous +connection, and which we may not even gather because of privacy concerns. +We can easily weight the number of \verb+ESTABLISH_RENDEZVOUS+ cells with +the probability of choosing a relay as rendezvous point to estimate the +total number of such cells in the network. + +\subparagraph{Risk} + +There is no obvious risk from sharing this number if aggregated over a +large enough time period. + +\paragraph{Time from circuit creation to establishing rendezvous point +(2.1.2.)} + +\subparagraph{Details} + +Relays report statistics on the time between circuit creation to receiving +a \verb+ESTABLISH_RENDEZVOUS+ cell. + +\subparagraph{Benefits} + +The time from receiving a circuit creation request to seeing the +\verb+ESTABLISH_RENDEZVOUS+ cell can help us optimize the rendezvous +protocol for performance. +The current implementation either builds a new circuit or extends an +existing circuit by one hop before sending the \verb+ESTABLISH_RENDEZVOUS+ +cell. +So, the measured time will be close to zero. +But if we ever decide to re-use existing circuits for rendezvous without +extending them by another hop, this metric will give us an idea on the +adoption of that change. +Admitted, this benefit is not huge. + +\subparagraph{Risk} + +There is no obvious risk related to this statistic. + +% [dgoulet]: Reporting a mean/average and with maybe a treshold before we +% publish like "we need 100 rdv cell before reporting this stat" ? +% [karsten]: agreed that this may seem useful in general. but what if the +% adversary sends 100 cells themselves to help us get past the threshold +% and report a tiny number of actual user cells? but I added an item to +% the section start where we can discuss whether this is a good safeguard +% in general. +% Right well that's a time statistic and not an amount so if an attacker +% would establish 100 RP I guess he/she indeed poisoning the stat?... + +\subparagraph{Recommendation} + +\paragraph{Number of rendezvous point establishment requests coming in via +circuits built with TAP vs. nTor (2.1.3.)} + +\subparagraph{Details} + +Relays remember whether an incoming circuit was built using TAP or nTor. +Whenever they receive an \verb+ESTABLISH_RENDEZVOUS+ cell they increment a +counter for either TAP or nTor. +See ticket 13466 for details. + +\subparagraph{Benefits} + +We would learn what fraction of hidden-service clients run older tor +versions (0.2.3.x or older). + +% How much RP traffic was transfererd through RP circuits? (see below re: +% RELAY cells) + +% Average traffic transfered through RP circuits? (see below re: RELAY +% cells) + +\subsubsection{Statistics on servers connecting to a client's rendezvous +point} + +\paragraph{Number of server rendezvous (2.2.1.)} + +\subparagraph{Details} + +Relays report the total number of \verb+RENDEZVOUS1+ cells they receive. + +\subparagraph{Benefits} + +The number of received \verb+RENDEZVOUS1+ cells tells us how many +connection requests are actually accepted by servers. +This number may be lower than the number of \verb+ESTABLISH_RENDEZVOUS+ +cells, because of failures in connection establishment, authentication +failures, or other reasons. + +\subparagraph{Risks} + +There is no obvious risk from this metric, because it's unrelated to any +given client or server. + +% [dgoulet]: Wondering if there is a real benefit here? I guess if we see +% 100 RENDEZVOUS1 and onlye *one* ESTABLISH_RENDEZVOUS, that might signal +% an issue... ? +% [karsten]: the idea is that things can go wrong between establishing a +% rendezvous point and the server sending a rendezvous. knowing what +% fraction of established rendezvous are actually used tells us something. +% and I think you mean 1 RENDEZVOUS1 and 100 ESTABLISH_RENDEZVOUS in your +% example. because 100 RENDEZVOUS1 for a single ESTABLISH_RENDEZVOUS +% would for sure look funny. +% [dgoulet]: well either way, it's an issue :)... If the HS sends a big +% amount of RENDEZVOUS1 to Alice's RP for which Alice only created one RP +% (one ESTABLISH_RENDEZVOUS), that's quite an issue (loop that went wrong +% :). + +\paragraph{Time from establishing a rendezvous point to receiving the +server rendezvous (2.2.2.)} + +\subparagraph{Details} + +Relays report the time from receiving an \verb+ESTABLISH_RENDEZVOUS+ cell +to receiving the corresponding \verb+RENDEZVOUS1+ cell. + +\subparagraph{Benefits} + +The time between receiving an \verb+ESTABLISH_RENDEZVOUS+ cell from the +client and the corresponding \verb+RENDEZVOUS1+ cell from the server tells +us a lot about performance of the rendezvous protocol. +The rendezvous point is the only place in the protocol that witnesses +events near the beginning and near the end of the connection establishment +process. +If we ever want to improve the substeps inbetween, this metric is the only +way to measure effectiveness of improvements in the deployed network. + +\subparagraph{Risks} + +Again, there are at least no obvious risks from gathering this statistic. + +\paragraph{Number of server rendezvous with unknown rendezvous cookie +(2.2.3.)} + +\subparagraph{Details} + +Relays report the number of \verb+RENDEZVOUS1+ cell with unknown +rendezvous cookie. + +\subparagraph{Benefits} + +The number of \verb+RENDEZVOUS1+ cell that cannot be matched with a +previously established rendezvous circuit can be interesting for analyzing +problems in the protocol. +We might even distinguish between rendezvous cookies that were previously +known to the relay and those that seem entirely unrelated. +The benefit gained from this statistic is not huge though. + +\subparagraph{Risk} + +No obvious risks. + +\paragraph{Number of server rendezvous coming in via circuits built with +TAP vs. nTor (2.2.4.)} + +\subparagraph{Details} + +Relays remember whether an incoming circuit was built using TAP or nTor. +Whenever they receive a \verb+RENDEZVOUS1+ cell they increment a counter +for either TAP or nTor. +See ticket 13466 for details. + +\subparagraph{Benefits} + +We would learn what fraction of hidden services run older tor versions +(0.2.3.x or older). + +\subsubsection{Statistics on clients creating streams to the server, +exchanging data, and tearing down the circuit} + +\paragraph{Time from server rendezvous to first client data (2.3.1.)} + +\subparagraph{Details} + +Relays report the time from receiving a \verb+RENDEZVOUS1+ cell to seeing +the first \verb+RELAY+ cell sent from the client. + +\subparagraph{Benefits} +The time from receiving a \verb+RENDEZVOUS1+ cell from the server (and +relaying it as \verb+RENDEZVOUS2+ cell to the client) and receiving the +first \verb+RELAY+ cell from the client is another performance indicator +of the protocol. + +\subparagraph{Risks} + +There are no obvious risks from learning the time between these two +substeps in the rendezvous protocol. + +\paragraph{Amount of data sent over connected rendezvous circuits in +either direction (2.3.2.)} + +\subparagraph{Details} + +Relays report the number of \verb+RELAY+ cells sent in either direction. + +\subparagraph{Benefits} + +The number of \verb+RELAY+ cells sent by either client or server can give +us a detailed view on hidden service usage. +In contrast to common Tor usage, there is no point in the rendezvous +protocol where we could count transferred bytes. +The number of cells is the best approximation that we have. +In addition to the total number of cells, the number of cells by direction +can indicate how common classical client-server protocols are compared to +peer-to-peer models. +As a special case, we'd want to know what fraction of circuits has zero +\verb+RELAY+ cells, which would indicate a connection problem late in the +process. + +\subparagraph{Risks} + +In contrast to the cells discussed above, \verb+RELAY+ cells contain +actual user content. +The pattern of \verb+RELAY+ cells could also be used to fingerprint a +given server or even client. +While total number of cells by direction aggregated over a certain time +period should be okay to measure, any statistics going further than that +need closer analysis. + +\paragraph{Time from first client data to tearing down circuit (2.3.3.)} + +\subparagraph{Details} + +Relays report the time from seeing the first \verb+RELAY+ cell sent by the +client to tearing down circuit by either client or server. + +\subparagraph{Benefits} + +The time between receiving the first \verb+RELAY+ cell to tearing down the +circuit indicates typical session length of hidden service connections. +We'd be able to say whether typical hidden-service connections are rather +short-lived or long-lived. +This information may help us make educated guesses on the type of +applications run over hidden services. +It may also help us improve the selection criteria for rendezvous points. + +\subparagraph{Risks} + +Session length is quite sensitive data that could be correlated with +circuit lifetimes at other places in the network. +Fortunately, the rendezvous point is neither specific to any given client +or service, which makes this information slightly less sensitive. +Still, this metric needs further analysis. + +% How many rendezvous requests finally succeded? +% Opposite: What percentage of the time did the rendezvous fail to happen? +% (rendezvous can fail at different steps. one way to count failures is +% to compare number of ESTABLISH_RENDEZVOUS, RENDEZVOUS1, and subsequent +% RELAY cells.) +% How much time did it take to splice the RP circuit? (#13194) (you mean +% time from RENDEZVOUS1 to first RELAY cell?) + +\subsection{Statistics from relays acting as hidden-service directories} + +% HSDirs threat model notes +Hidden Service directories periodically receive HS descriptors from hidden +services. +They cache them, and then serve them to any clients that ask for them. + +Hidden service directories are placed in a hash ring, and each hidden +service picks a slice of hidden service directories from that hash ring. +Given the address of a hidden service, it's easy to learn which +directories are responsible for it. +This makes hidden-service directory statistics dangerous since they can +potentially be matched to specific hidden services. + +Furthermore, each hidden service has 6 directories, and each directory +serves a different set of services. +This means that attackers have 6 different data points per hidden service +every hour that can be used to reduce measurement noise. + +The following statistics are grouped by (1) hidden services publishing +descriptors and (2) clients fetching descriptors from hidden-service +directories. + +\subsubsection{Statistics on hidden services publishing descriptors to +hidden-service directories} + +\paragraph{Number of cached descriptors (3.1.1.)} + +\subparagraph{Details} + +Relays keep a local count of cached hidden-service descriptors. +Every time they add or remove a descriptor to their cache, relays update +their counter and record the time of change. +At the end of the statistics period they calculate statistics like +minimum, maximum, average number of hosted descriptors during the +statistics interval. +(There may be more efficient ways to implement these statistics that avoid +keeping a full history with timestamps, which are not discussed here.) + +\subparagraph{Benefits} + +This is an interesting statistic that would allow us to understand how +used hidden services are, and also detect sudden changes in the number of +services (botnets, chat protocols, etc.). +Also, learning the number of hidden services per directory will help us +find bugs in the hash ring code and also understand how loaded directories +are. +FWIW, when \verb+rend-spec-ng.txt+ gets implemented, it will be harder for +hidden service directories to learn the number of served services since +the descriptor will be encrypted. +However, directories will still be able to approximate the number of +services by checking the amount of descriptors received per publishing +period. +If this ever becomes a problem we can imagine publishing fake descriptors +to confuse the directories. + +\subparagraph{Risks} + +Publishing this stat would allow someone who is indexing hidden services +to be able to say ``I have seen 76~\% of all HSes''. +We would really like to avoid having such an enumeration-facilitating +property. +We could be persuaded that with some heavy stats obfuscation (heavier than +the bridge stats obfuscation), this statistic might be plausible. +By statistics obfuscation, we mean obfuscating the numbers so that the +attacker can only say ``I'm somewhere between 60~\% to 75~\% of all +HSes.''. +This is a bit related to differential privacy as we understand it, but +much more basic. + +\paragraph{Number of descriptor updates per service (3.1.2.)} + +\subparagraph{Details} + +Relays count how many descriptor updates they see per service. +Assuming that stats are published daily (which is not necessary), this is +going to be a number between 1 and 24 (since RendPostPeriod is currently +one hour) and services pick a new directory after 24 hours (see +\verb+rendcommon.c:get_time_period()+). + +\subparagraph{Risks} + +Depending on how many HSes are behind each HSDir, this statistic might or +might not reveal uptime information about specific services. +Still it doesn't seem like something we want to risk. +Also, if the result is greater than 24, it means that an HS with modded +RendPostPeriod was publishing to that HSDir (and that the HSDir doesn't +have many clients). +Do we want to reveal that? +OTOH, it seems to me that if the directory is serving many services, this +statistic doesn't really provide any insight. + +\paragraph{Size of hidden service descriptors (3.1.3.)} + +\subparagraph{Details} + +Relays report the total/average size of received hidden service +descriptors. + +\subparagraph{Benefits} + +These statistics are not very helpful if reported by directories that +serve many services. +Any bugs or irregularities of one service will be smoothed out by all the +other services. +Basically, the only thing we would learn is approximately how much disk +space descriptors take, and maybe the average number of contained +introduction points (if we also know the number of services). +This statistic seems not very useful. + +\paragraph{Number of introduction points contained in descriptors +(3.1.4.)} + +\subparagraph{Details} + +Relays report average number of introduction points contained in +hidden-service descriptors, possibly also percentiles. + +\subparagraph{Benefits} + +It would be interesting to know whether services deviate from the default +number of introduction points. +Though it's unclear what we're going to do with this information. +This statistic will also be killed by rend-spec-ng. + +\paragraph{Number of descriptors with encrypted introduction points +(3.1.5.)} + +\subparagraph{Details} + +Relays can look at published hidden-service descriptor and count +descriptors with plain-text vs. encrypted introduction point sections. + +\subparagraph{Benefits} + +We would learn what fraction of services uses authentication features. +This statistic won't be available after implementing rend-spec-ng. + +\paragraph{Number of descriptors published over circuits built with TAP +vs. nTor (3.1.6.)} + +\subparagraph{Details} + +Relays remember whether an incoming circuit was built using TAP or nTor. +Whenever they receive a descriptor publication request they increment a +counter for either TAP or nTor. +See ticket 13466 for details. + +\subparagraph{Benefits} + +We would learn what fraction of hidden services run older tor versions +(0.2.3.x or older). + +\paragraph{Number of descriptors published to the wrong directory +(3.1.7.)} + +\subparagraph{Details} + +A relay reports the number of published descriptors that it is not +responsible for. + +\subsubsection{Statistics on clients fetching descriptors from +hidden-service directories} + +\paragraph{Number of descriptor fetch requests (3.2.1.)} + +\subparagraph{Details} + +A relay reports the total number of descriptor fetch requests, regardless +of the requested hidden service identity. + +\subparagraph{Risks} + +An adversary can use this statistic to evaluate the popularity of an HS. +An adversary can also use this stat to detect big changes in the numbers +of visitors of popular HSes. +Of course, there will be noise in the statitics since multiple services +correspond to each directory, but the adversary could reduce the noise +after observing the same service rotating to different directories, and +also by examining the statistics of all 6 directories that correspond to +the service. +This doesn't seem like a problem that is solvable with simple obfuscation +of stats, and I suggest we don't do this statistic at all. + +\paragraph{Number of descriptor fetch requests by hidden service identity +(3.2.2.)} + +\subparagraph{Details} + +Relays report the distribution of descriptor fetch requests to hidden +service identities. + +\paragraph{Number of descriptor fetch requests for non-existent descriptor +(3.2.3.)} + +\subparagraph{Details} + +Relays count the number of fetch requests for hidden service identities +they don't have in their cache. +We need to enumerate the reasons why a client would ask for the wrong +descriptor. +(but how do we find out...?) +For example: a) clock sync issues, b) different network view between, c) +``the hidden service hasn't published recently'', d) ``the hidden service +is offline for months''. + +\subparagraph{Benefits} + +This seems like a statistic that could potentially find bugs in Tor. + +\subparagraph{Risks} + +This statistic could reveal things that we don't really understand and +might reveal information about specific services. + +\paragraph{Number of descriptors fetched over circuits built with TAP vs. +nTor (3.2.4.)} + +\subparagraph{Details} + +Relays remember whether an incoming circuit was built using TAP or nTor. +Whenever they receive a descriptor fetch request they increment a counter +for either TAP or nTor. +See ticket 13466 for details. + +\subparagraph{Benefits} + +We would learn what fraction of hidden-service clients run older tor +versions (0.2.3.x or older). + +%- How many HSes is the HSDir hosting descriptors for? (harder to do with +%rend-spec-ng) (assuming that each HS desc is for one HS, this is already +%covered above.) +%- How many updates for the same HS desc did the HSDir see? (already covered +%above, it seems.) + +\section{Evaluation} + +Adding new statistics to something as sensitive as hidden services has two +sides: one side is the benefit from gathering data that can be used to +improve them, but the other side is potential harm to users. +The following table assigns points to both benefits and risks. +Each statistic can earn between 0 and 2 benefit points and between 0 and 2 +(negative) risk points. +The sum of both points provides us with a priority list from statistics +that make a lot of sense and don't pose much risk to statistics that are +mostly useless and at the same time very risky. + +\begin{longtable}{p{1cm}p{1cm}p{1cm}p{12cm}} +B & R & S \\ +$+$ & $0$ & $+$ & Number of attempts to establish an introduction point +(1.1.1.) \\ +$0$ & $0$ & $0$ & Time from establishing a circuit to becoming an +introduction point (1.1.2.) \\ +$+$ & $0$ & $+$ & Number of failed attempts to establish an introduction +point (1.1.3.) \\ +$+$ & $0$ & $+$ & Lifetime of introduction circuits (1.1.4.) \\ +$+$ & $0$ & $+$ & Reasons for terminating established introduction points +(1.1.5.) \\ +$+$ & $0$ & $+$ & Number of introduction circuits built with TAP vs. nTor +(1.1.6.) \\ +$+$ & $-$ & $0$ & Total number of introductions received from clients +(1.2.1.) \\ +$+$ & $-$ & $0$ & Number of introductions received by established +introduction point (1.2.2.) \\ +$+$ & $-$ & $0$ & Number of discarded client introductions by reason +(1.2.3.) \\ +$0$ & $0$ & $0$ & Time between establishing introduction point and receiving +the first client introduction (1.2.4.) \\ +$+$ & $0$ & $+$ & Number of client introductions coming in via circuits +built with TAP vs. nTor (1.2.5.) \\ +$+$ & $0$ & $+$ & Number of established rendezvous points (2.1.1.) \\ +$0$ & $0$ & $0$ & Time from circuit creation to establishing rendezvous +point (2.1.2.) \\ +$+$ & $0$ & $+$ & Number of rendezvous point establishment requests coming +in via circuits built with TAP vs. nTor (2.1.3.) \\ +$++$ & $0$ & $++$ & Number of server rendezvous (2.2.1.) \\ +$++$ & $0$ & $++$ & Time from establishing a rendezvous point to receiving the +server rendezvous (2.2.2.) \\ +$+$ & $0$ & $+$ & Number of server rendezvous with unknown rendezvous cookie +(2.2.3.) \\ +$+$ & $0$ & $+$ & Number of server rendezvous coming in via circuits built +with TAP vs. nTor (2.2.4.) \\ +$++$ & $0$ & $++$ & Time from server rendezvous to first client data (2.3.1.) +\\ +$++$ & $-$ & $+$ & Amount of data sent over connected rendezvous circuits in +either direction (2.3.2.) \\ +$+$ & $-$ & $0$ & Time from first client data to tearing down circuit +(2.3.3.) \\ +$++$ & $-$ & $+$ & Number of cached descriptors (3.1.1.) \\ +$+$ & $-$ & $0$ & Number of descriptor updates per service (3.1.2.) \\ +$0$ & $0$ & $0$ & Size of hidden service descriptors (3.1.3.) \\ +$+$ & $0$ & $+$ & Number of introduction points contained in descriptors +(3.1.4.) \\ +$+$ & $0$ & $+$ & Number of descriptors with encrypted introduction points +(3.1.5.) \\ +$+$ & $0$ & $+$ & Number of descriptors published over circuits built with +TAP vs. nTor (3.1.6.) \\ + & & & Number of descriptors published to the wrong directory +(3.1.7.) \\ +$+$ & $--$ & $-$ & Number of descriptor fetch requests (3.2.1.) \\ $+$ & +$--$ & $-$ & Number of descriptor fetch requests by hidden service identity +(3.2.2.) \\ +$+$ & $0$ & $+$ & Number of descriptor fetch requests for non-existent +descriptor (3.2.3.) \\ +$+$ & $0$ & $+$ & Number of descriptors fetched over circuits built with TAP +vs. nTor (3.2.4.) \\ +\end{longtable} + +\end{document} + diff --git a/2015/hidden-service-stats/tortechrep.cls b/2015/hidden-service-stats/tortechrep.cls new file mode 120000 index 0000000..4c24db2 --- /dev/null +++ b/2015/hidden-service-stats/tortechrep.cls @@ -0,0 +1 @@ +../../tortechrep.cls \ No newline at end of file

1 0

[tech-reports/master] Reply to dgoulet's comments.
by karsten＠torproject.org 17 Jun '15

17 Jun '15

commit 4baae27cec328db369acdfb0180a6943ba9dbf95 Author: Karsten Loesing <karsten.loesing(a)gmx.net> Date: Sat Nov 29 09:38:06 2014 +0100 Reply to dgoulet's comments. --- 2015/hidden-service-stats/hidden-service-stats.tex | 14 +++++++++++--- 1 file changed, 11 insertions(+), 3 deletions(-) diff --git a/2015/hidden-service-stats/hidden-service-stats.tex b/2015/hidden-service-stats/hidden-service-stats.tex index ef8f46c..75ce789 100644 --- a/2015/hidden-service-stats/hidden-service-stats.tex +++ b/2015/hidden-service-stats/hidden-service-stats.tex @@ -150,7 +150,11 @@ the introduction point. % it is that there is probably a noticable time difference between using % an already created circuit for which we simply extend one hop versus % establishing a new one of 4 hops. - +% [karsten]: That's right, but we have no data from the client, but only +% from the relay that happens to be the last hop in the circuit. That +% relay only sees that the circuit gets extended to it, but it has no +% information how long the client had the circuit lying around before +% extending it. % Newly established circuit. % Benefits: Performance reason, this can be useful to know the real cost @@ -497,8 +501,12 @@ There is no obvious risk related to this statistic. % and report a tiny number of actual user cells? but I added an item to % the section start where we can discuss whether this is a good safeguard % in general. -% Right well that's a time statistic and not an amount so if an attacker -% would establish 100 RP I guess he/she indeed poisoning the stat?... +% [dgoulet]: Right well that's a time statistic and not an amount so if an +% attacker would establish 100 RP I guess he/she indeed poisoning the +% stat?... +% [karsten]: Maybe. In theory, the stat is not poisoned for the attacker +% if she knows what values she's contributed to it. But I agree that this +% is not the best example. \subparagraph{Recommendation}

1 0

[tech-reports/master] adding subsection on aggregation techniques
by karsten＠torproject.org 17 Jun '15

17 Jun '15

commit 941b9516a472ae112a29540878424ae179ef7f86 Author: A. Johnson <aaron.m.johnson(a)nrl.navy.mil> Date: Wed Dec 31 15:57:25 2014 -0500 adding subsection on aggregation techniques --- 2015/hidden-service-stats/hidden-service-stats.bib | 35 +++ 2015/hidden-service-stats/hidden-service-stats.tex | 295 +++++++++++++++++--- 2 files changed, 298 insertions(+), 32 deletions(-) diff --git a/2015/hidden-service-stats/hidden-service-stats.bib b/2015/hidden-service-stats/hidden-service-stats.bib index 52daad5..2fbb81a 100644 --- a/2015/hidden-service-stats/hidden-service-stats.bib +++ b/2015/hidden-service-stats/hidden-service-stats.bib @@ -4,4 +4,39 @@ booktitle = {Proceedings of the Third Conference on Theory of Cryptography}, series = {TCC'06}, year = {2006} +} + +@inproceedings{nissim-stoc2007, + author = {Nissim, Kobbi and Raskhodnikova, Sofya and Smith, Adam}, + title = {Smooth Sensitivity and Sampling in Private Data Analysis}, + booktitle = {Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing}, + series = {STOC '07}, + year = {2007} +} + +@article{pgen:homer, + author = {N.~Homer et al.}, + title = {Resolving Individuals Contributing Trace Amounts of {DNA} to + Highly Complex Mixtures Using High-Density {SNP} + Genotyping Microarrays}, + year = {2008}, + journal = {PLoS Genet}, + volume = {4}, + year = {2008} +} + +@inproceedings{elahi-ccs2014, + author = {Elahi, Tariq and Danezis, George and Goldberg, Ian}, + title = {PrivEx: Private Collection of Traffic Statistics for Anonymous Communication Networks}, + booktitle = {Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security}, + series = {CCS '14}, + year = {2014} +} + +@inproceedings{dwork-stoc2009, + author = {Dwork, Cynthia and Lei, Jing}, + title = {Differential Privacy and Robust Statistics}, + booktitle = {Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing}, + series = {STOC '09}, + year = {2009} } \ No newline at end of file diff --git a/2015/hidden-service-stats/hidden-service-stats.tex b/2015/hidden-service-stats/hidden-service-stats.tex index 1400268..9aeb64c 100644 --- a/2015/hidden-service-stats/hidden-service-stats.tex +++ b/2015/hidden-service-stats/hidden-service-stats.tex @@ -473,6 +473,7 @@ No obvious risks. % only talking about aggregate statistics here, not % is not the best example. \subsubsection{Number of circuits built with TAP vs. nTor} +\label{subsubsec:num_circ_tap} \textbf{Details:} % @@ -510,6 +511,7 @@ Performance-related statistics and failure statistics are covered in a later section. \subsubsection{Number of established introduction points} +\label{subsubsec:num_establish_ip} \textbf{Details:} % @@ -646,7 +648,7 @@ Though it's unclear what we're going to do with this information. This statistic will also be killed by rend-spec-ng. \subsubsection{Number of descriptors with encrypted introduction points -(3.1.5.)} +(3.1.5.)} \label{subsubsec:num_desc_encrypted_ips} \textbf{Details:} % @@ -665,6 +667,7 @@ performance-related statistics and failure statistics are covered at a later time. \subsubsection{Number of descriptor fetch requests (3.2.1.)} +\label{subsubsec:num_desc_fetches} \textbf{Details:} % @@ -693,6 +696,7 @@ Relays report the distribution of descriptor fetch requests to hidden service identities. \subsubsection{Number of established rendezvous points (2.1.1.)} +\label{subsubsec:num_rps} \textbf{Details:} % @@ -717,6 +721,7 @@ There is no obvious risk from sharing this number if aggregated over a large enough time period. \subsubsection{Number of introductions received from clients (1.2.1.)} +\label{subsubsec:num_intros_from_clients} \textbf{Details:} % @@ -772,6 +777,7 @@ points that never sees a single \verb+INTRODUCE1+ cell. It's unclear what we'd do with this information, though. \subsubsection{Number of server rendezvous (2.2.1.)} +\label{subsubsec:num_server_rendezvous} \textbf{Details:} % @@ -871,7 +877,7 @@ Still, this metric needs further analysis. % time from RENDEZVOUS1 to first RELAY cell?) \subsubsection{Number of closed rendezvous circuits without a single data -cells} +cell} \label{subsubsec:num_rend_circ_no_data} \textbf{Details:} % @@ -957,7 +963,7 @@ Could be a starting point to look at actual logs from relays. But is this what statistics are for? \subsubsection{Number of failed attempts to establish an introduction -point (1.1.3.)} +point (1.1.3.)} \label{subsubsec:num_failed_ips} \textbf{Details:} % @@ -989,7 +995,7 @@ or a deliberate action (data mangling, unknown attack, DoS, ...). No obvious risks. \subsubsection{Reasons for terminating established introduction points -(1.1.5.)} +(1.1.5.)} \label{subsubsec:reasons_end_ips} \textbf{Details:} % @@ -1006,7 +1012,7 @@ things more robust. No obvious risks. \subsubsection{Number of descriptors published to the wrong directory -(3.1.7.)} +(3.1.7.)} \label{subsubsec:num_descriptors_wrong_hsdir} \textbf{Details:} % @@ -1039,7 +1045,7 @@ might reveal information about specific services. \subsubsection{Number of discarded client introductions by reason -(1.2.3.)} +(1.2.3.)} \label{subsubsec:num_discarded_client_intros} \textbf{Details:} % @@ -1065,7 +1071,7 @@ the risk of reporting the number of received \verb+INTRODUCE1+ cells; if only fractions are reported, it's not that bad. % \subsubsection{Number of server rendezvous with unknown rendezvous cookie -(2.2.3.)} +(2.2.3.)} \label{subsubsec:num_server_rend_unknown_cookie} \textbf{Details:} % @@ -1105,13 +1111,13 @@ such as anonymizing reports from individual relays We will be adding noise in a way that provides differential privacy~\cite{dwork-tcc2006} for -``single'' actions. What constitutes a single action will depend on the +``single actions''. What constitutes a single action will depend on the specific statistic. For example, when publishing the number of unique descriptors seen at each HSDir, a single action could be publishing a descriptor to six relays. To obtain differential privacy, we will add noise using the -Laplace distribution, which has a distribution function of -$\textrm{Lap}(b) = e^{-|x|/b}/(2b)$. We will choose $b$ such that +Laplace distribution, which has a distribution function +$\textsf{Lap}(b)$ of $e^{-|x|/b}/(2b)$. We will choose $b$ such that altering a single action will change the probability of the total output by a factor of at most $e^{\epsilon}$. Thus more privacy is provided the smaller that $\epsilon$ is. @@ -1131,9 +1137,127 @@ periodically) traffic (possibly leaked by the service itself, e.g. a web forum) \end{compactitem} -\subsection{Counts} +\subsection{Counts} \label{subsec:counts} +Reporting a basic count is useful in its own right, and it also provides a +simple setting in which to develop privacy-preserving methodology that +we can use for more complicated statistics. Counts can be used to +summarize many types of hidden-service activity, such as the number of +hidden services, the number of hidden-service clients, and the amount of +hidden-service traffic. Table~\ref{table:count_stats} lists the statistics +for which it could be useful to release counts. +\begin{table} +\center +\caption{Count statistics} +\label{table:count_stats} +\begin{tabular}{|l|l|} +\hline +\textbf{Description} & \textbf{Section}\\ +\hline +Number of circuits built with TAP vs. nTor & +\ref{subsubsec:num_circ_tap}\\ +\hline +Number of established introduction points & +\ref{subsubsec:num_establish_ip}\\ +\hline +Number of descriptor publish request & +\ref{subsubsec:num_descriptor_publish}\\ +\hline +Number of descriptors with encrypted introduction points & +\ref{subsubsec:num_desc_encrypted_ips}\\ +\hline +Number of descriptor fetch requests & +\ref{subsubsec:num_desc_fetches}\\ +\hline +Number of established rendezvous points & +\ref{subsubsec:num_rps}\\ +\hline +Number of introductions received from clients & +\ref{subsubsec:num_intros_from_clients}\\ +\hline +Number of server rendezvous & +\ref{subsubsec:num_server_rendezvous}\\ +\hline +Number of closed rendezvous circuits without a single data cell & +\ref{subsubsec:num_rend_circ_no_data}\\ +\hline +Number of failed attempts to establish an introduction point & +\ref{subsubsec:num_failed_ips}\\ +\hline +Reasons for terminating established introduction points & +\ref{subsubsec:reasons_end_ips}\\ +\hline +Number of descriptors published to the wrong directory & +\ref{subsubsec:num_descriptors_wrong_hsdir}\\ +\hline +Number of discarded client introductions by reason & +\ref{subsubsec:num_discarded_client_intros}\\ +\hline +Number of server rendezvous with unknown rendezvous cookie & +\ref{subsubsec:num_server_rend_unknown_cookie}\\ +\hline +\end{tabular} +\end{table} + +To release a single count, we will use ideas from differential privacy +to provide strong protection for a single hidden-service action, such as +making a small number of descriptor lookups or sending all but an +abnormally-large amount of traffic. However, we wish to +continually publish statistics over time, and as a result differential +privacy, using a per-user or per-service privacy notion that applies over +time, does not provide an adequate solution. The reasons are +(\emph{i}) mechanisms using global sensitivity~\cite{dwork-tcc2006} that +would apply over time require amounts of noise that grow with the +reporting period (potentially years in our case), and (\emph{ii}) +improving the accuracy using local mechanisms~\cite{nissim-stoc2007} is +not feasible because the Tor protocol by design hides which activities +correspond to the same user or service. + +There are several challenges to privately publishing statistics over time. +One is that, although the effect of a single action may be made difficult +to determine in any given statistic, the collective set of statistics may +reveal some level of activity by the same user or service. This problem +of a single sensitive fact influencing many published statistics +was effectively exploited by Homer et al.~\cite{pgen:homer} to identify +if an individual was a member of a diseased study group based only on +per-gene statistics (where here data per-gene replace data +per-time-period). Another challenge is that it may be +possible to remove the noise added to the published values if ``fresh'' +noise (i.e. noise generated using new randomness) is added to each +statistic. For example, if a count stays the same for a while, and +the adversary knows that (or can guess it with some confidence), then +the adversary can get a good estimate of the count by taking the +mean of the sequence of published noisy counts. Simply reusing the +same noise isn't adequate, however, because in that case the statistics +would reveal with certainty all changes in the statistic and thus +all activity since the fresh noise was chosen. + +To handle this problem, we will use simple rounding or ``binning''. This +will hide changes to a count that keep it in the same bin. Of course, +this won't hide the effects of an action if the count happens to be near +the rounding threshold, and also the adversary can in most cases himself +perform actions that alter the count to attempt to determine the location +of the count within the bin. However, we will mitigate both of these +issues by making the bin output itself noisy. + +We suggest the following to privately publish a count $c$: +\begin{compactenum} +\item Choose a bin granularity $\delta$, which should be larger than +the amount by which a single action can change the count. +\item Round $c$ to the nearest multiple of $\delta$, that is, let +$\hat{c} = \delta[c/\delta]$, where $[]$ indicates the nearest integer +function. +\item Choose a value $\nu$ from the $\textsf{Lap}(\delta/\epsilon)$ +distribution. $\epsilon$ is the privacy +parameter discussed at the beginning of Sec.~\ref{sec:obfuscation}. +$\delta$ appears in the Laplace +parameter because a single action could cause the bin center to change +by at most $\delta$. +\item Let the noisy count be $\tilde{c} = \hat{c} + \nu$. Publish +$\tilde{c}$. +\end{compactenum} -\subsection{Distributions} + +\subsection{Distributions} \label{subsec:distributions} For many statistics, it would be very helpful to understand the distribution of values. For example, such information about descriptor fetches could reveal if most hidden services are never used or if @@ -1141,6 +1265,7 @@ there are a few hidden services that constitute most HS activity. Table~\ref{table:dist_stats} lists the statistics for which it could be useful to release information about a distribution. \begin{table} +\center \caption{Statistics with interesting distributions} \label{table:dist_stats} \begin{tabular}{|l|l|} @@ -1202,40 +1327,146 @@ skew, and kurtosis). \end{compactitem} To protect individual privacy when releasing these kinds of data, we would again like to protect activity over time and also provide -particularly-strong protection for a ``single'' activity. This is quite +particularly-strong protection for a single activity. This is quite straightforward to do for publishing histograms, simply by applying the techniques that we developed for counts to each count in the histogram. Thus we suggest using histograms in this way to report distribution data, as follows: \begin{compactenum} -\item Choose a finite number of \emph{buckets} that cover the possible +\item Choose a finite number $k$ of \emph{buckets} that cover the possible values of the statistic (we use the term ``buckets'' to distinguish these from bins that will limit the granularity of each bucket). Each extra bucket will result in a certain additional amount of noise being added, but including more values in a bucket (i.e. increasing its width) -reduces its accuracy. Therefore, these should be balanced while also -choosing buckets that capture the most useful distinctions +reduces its accuracy. Therefore, the number of width of the buckets should +be balanced while also +choosing buckets to capture the most useful distinctions for the statistic under consideration (e.g. deciding between relative and absolute accuracy). -\item For each bucket, the count of values in that bucket should be -rounded to a chosen granularity $\delta$ (e.g. to the nearest multiple of -10). For simplicity, it is recommended that bins are not split over -multiple buckets (e.g. there should not be buckets for values 0 and 1 if -bin granularity is at least 2). A rounded value is used because over time -the effects of fresh noise can be factored out (e.g. by taking the mean -of a sequence of published values if the statistic stays the same over -that time). -\item Fresh Laplace noise with distribution -$\textrm{Lap}(2\delta/\epsilon)$ should be added to the center of the bin -of each bucket, where $\epsilon$ is the privacy parameter discussed at the -beginning of Sec.~\ref{sec:obfuscation}. $\delta$ appears in $b$ because -a single input to the histogram could cause the bucket center to change -by at most $\delta$ (e.g. if the rounding threshold is just crossed). -The value $2$ appears in $b$ because modifying a single entry in the +\item For the $i$th bucket, the count $c_i$ of values in that bucket +should be rounded to a chosen granularity $\delta$: +$\hat{c_i} = \delta[c_i/\delta]$. +$\delta$ should be larger than the amount by which a +single activity could change the bucket count, where again the notion of a +single activity depends on the context. Also, for simplicity, it is +recommended that bins +are not split over multiple buckets (e.g. there should not be buckets for +values 0 and 1 if $\delta = 2$). The bins here serve the same purpose +of protecting privacy over time that they did when publishing counts. +\item Fresh Laplace noise $\nu_i$ with distribution +$\textsf{Lap}(2\delta/\epsilon)$ should be added to the center of the +bin of the $i$th bucket. Let the resulting value be +$\tilde{c_i} = \hat{c_i} + \nu_i$. The value $2$ appears in the Laplace +parameter because modifying a single entry in the histogram can change two values: the value of the bucket it was changed from and the value of the bucket it was changed to. -\item The noisy bin center of each bucket is published. +\item Publish each noisy bucket count, $\tilde{c_i}$, $1\le i\le k$. +\end{compactenum} + +\subsection{Statistics aggregation} +Up to this point it has been suggested that individual Tor relays collect +and publish these statistics. However, there are many drawbacks to +collecting all statistics in this manner. The main advantage is that it is +straightforward to implement. Here we describe some of the problems and +outline potential solutions. + +One problem with publishing statistics in a way that +is attributable to specific Tor relays is that in some cases it is +inherently insecure. For example, if each relay reported the number of +client introduction requests it received +(Sec.~\ref{subsubsec:num_intros_from_clients}), then an adversary that +knows the \texttt{.onion} address of an HS (and thus can obtain its +introduction points) could infer how many client connections the HS +received, especially if there were few other HSes sharing its IPs. The +general issue is that for certain types of HS activities different HSes +or clients will make use of different relays in a way that may be +known by the adversary. Table~\ref{table:stats_needing_aggregation} lists +those statistics for which this is an issue. +\begin{table} +\center +\caption{Per-relay statistics at high risk to leak private information} +\label{table:stats_needing_aggregation} +\begin{tabular}{|l|l|} +\hline +\textbf{Description} & \textbf{Section}\\ +\hline +Number of descriptor fetch requests & +\ref{subsubsec:num_desc_fetches}\\ +\hline +Number of introductions received from clients & +\ref{subsubsec:num_intros_from_clients}\\ +\hline +Reasons for terminating established introduction points & +\ref{subsubsec:reasons_end_ips}\\ +\hline +Number of discarded client introductions by reason & +\ref{subsubsec:num_discarded_client_intros}\\ +\hline +Time from establishing introduction point to tearing down circuit & +\ref{subsubsec:time_intro_to_teardown}\\ +\hline +Number of descriptor updates per service & +\ref{subsubsec:num_decriptor_updates}\\ +\hline +Time between last and first published descriptor with same identifier & +\ref{subsubsec:time_first_last_descriptor_update}\\ +\hline +Number of descriptor fetch requests by service identity & +\ref{subsubsec:num_descriptor_fetches_per_hs}\\ +\hline +Number of introductions received by established introduction point & +\ref{subsubsec:num_intros_per_circ}\\ +\hline +Time from establishing introduction point to receiving first client +introduction & \ref{subsubsec:time_ip_est_to_introduce1}\\ +\hline +\end{tabular} +\end{table} + +Another problem is that with per-relay statistics much more total noise +needs to be added than is necessary if only network-wide totals are +ultimately desired. Note that the rounding and noise applied to each +relay's statistics (Secs. \ref{subsec:distributions} \& +\ref{subsec:counts}) +would provide equivalent protection if applied to the same statistics for +the entire network. This would reduce the amount of added noise and +rounding inaccuracy by a factor of $m$, where $m$ is the number of relays. + +There are many possible ways to improve both the security and accuracy +of Tor statistics via aggregation using well-studied cryptographic +techniques, including +\begin{compactitem} +\item Have the relays run a secure multiparty computation (SMC) protocol +that produces the desired statistics with any privacy-preserving +modifications included (e.g. added noise). +\item Take the approach of PrivEx~\cite{elahi-ccs2014} and use a separate +set of ``tally servers'' that secret-share statistics and use homomorphic +encryption to aggregate counts. +\item Anonymize statistics reports, either via Tor itself or via a shuffle +run over a separate set of servers. For statistics that could be +attributable to a small set of relays by their values alone (e.g. a large +number of rendezvous data cells is likely to come from a small set of +large relays), break up the values into minimum amounts. +\end{compactitem} + +Adoption of these approaches faces a couple of main challenges. Those +issues and our suggestions for handling them are +\begin{compactenum} +\item Implementation difficulty: Making use of sophisticated +cryptographic tools, such as non-standard cryptosystems or novel +SMC protocols, often requires building secure implementations of +them. This can require significant time and skill. It also +creates future maintenance obligations. When choosing from the above +solutions, we will have to consider what reliable software already exists +for their various cryptographic components. +\item Manipulation of statistics: Adversarial relays may report incorrect +statistics in order to affect the aggregate statistic. For example, a +simple aggregate such as a sum could be trivially destroyed by a malicious +relay reporting a much larger value than its true input. One way to handle +this problem is to use ``robust'' statistics~\cite{dwork-stoc2009}, which +are not excessively influenced by outliers. For example, we could use a +median instead of a mean as the basis for a sum. \end{compactenum}

1 0

[tech-reports/master] adding section on obfuscation techniques
by karsten＠torproject.org 17 Jun '15

17 Jun '15

commit f586165e9f9e0f5e1c2b62c85c1ac776248837b6 Author: A. Johnson <aaron.m.johnson(a)nrl.navy.mil> Date: Tue Dec 23 10:00:21 2014 -0600 adding section on obfuscation techniques --- 2015/hidden-service-stats/hidden-service-stats.tex | 60 +++++++++++++++++++- 1 file changed, 59 insertions(+), 1 deletion(-) diff --git a/2015/hidden-service-stats/hidden-service-stats.tex b/2015/hidden-service-stats/hidden-service-stats.tex index 7760e83..d4b586e 100644 --- a/2015/hidden-service-stats/hidden-service-stats.tex +++ b/2015/hidden-service-stats/hidden-service-stats.tex @@ -353,7 +353,8 @@ for the future that says \emph{why} they are a bad idea. We start with statistics that are not specific to the three roles of relays in the hidden-service protocol, but that apply to all of them. -\subsubsection{Time from circuit extension to circuit purpose change} +\subsubsection{Time from circuit extension to circuit purpose change} +\label{subsubsec:time_circ_ext_to_purpose_change} % (the following distinction cannot be made, AFAIK. here's what happens: % we receive a CREATE (?) cell from another relay that establishes the @@ -489,6 +490,7 @@ We would learn what fraction of clients and what fraction of services run older tor versions (0.2.3.x or older). \subsubsection{Time from circuit purpose change to tearing down circuit} +\label{subsubsec:time_circ_purpose_change_to_teardown} \textbf{Details:} % @@ -527,6 +529,7 @@ relay got chosen X times instead of the measured average Y. \subsubsection{Time from establishing introduction point to tearing down circuit (1.1.4.)} +\label{subsubsec:time_intro_to_teardown} \textbf{Details:} % @@ -545,6 +548,7 @@ available for a short time only, and what fraction is available most of the time. \subsubsection{Number of descriptor publish request (3.1.1.)} +\label{subsubsec:num_descriptor_publish} \textbf{Details:} % @@ -589,6 +593,7 @@ This is a bit related to differential privacy as we understand it, but much more basic. \subsubsection{Number of descriptor updates per service (3.1.2.)} +\label{subsubsec:num_decriptor_updates} \textbf{Details:} % @@ -1076,6 +1081,59 @@ The benefit gained from this statistic is not huge though. % No obvious risks. +\section{Obfuscation methodology} +The published statistics shouldn't reveal private information to an +adversary when combined with plausible background knowledge. We will use +techniques to provide uncertainty about any specific hidden service, +client, or connection, while maintaining good accuracy in the aggregate +statistics. These techniques include +\begin{itemize} +\item Releasing aggregate statistics over time, such as total counts or +averages in a given period +\item Adding noise (i.e. random inaccuracy) +\item Limiting accuracy to a certain granularity via rounding (aka +``binning'') +\item Adding time-delay to the release of statistics such that the output +doesn't reveal information about ongoing activity +\item Using cryptographic techniques to hide the source of information, +such as anonymizing reports from individual relays +\end{itemize} + + +\subsection{Adversary knowledge} +We can expect that the adversary may know things such as +\begin{itemize} +\item The addresses of a large number of publicly-available services +(e.g. by crawling the Web) +\item A minimum amount of traffic received by a given hidden service +(e.g. due to sending that traffic himself) +\item The introduction points of a service (by obtaining the descriptor) +\item The availability of the service (by attempting to connect +periodically) +\item Roughly the number of client connections and amount of client +traffic (possibly leaked by the service itself, e.g. a web forum) +\end{itemize} + +\subsection{Counts} + +\subsection{Distributions} +For many statistics, it would be very helpful to understand the +distribution of values. For example, such information about descriptor +fetches could reveal if most hidden services are never used or if +there are a few hidden services that constitute most HS activity. +Releasing information about the distribution of statistics could be useful +for the following statistics: +\begin{itemize} +\item Time from circuit extension to circuit purpose change +(Sec.~\ref{subsubsec:time_circ_ext_to_purpose_change}) +\item Time from circuit purpose change to tearing down circuit +(Sec.~\ref{subsubsec:time_circ_purpose_change_to_teardown} +\item Time from establishing introduction point to tearing down +circuit (Sec.~\ref{subsubsec:time_intro_to_teardown}) +\item Number of descriptor updates per service +(Sec.~\ref{subsubsec:num_decriptor_updates}) +\end{itemize} + \section{Recommendation} \label{sec:recommendation}

1 0

[tech-reports/master] Rewrite major parts of the hid-serv-stats report.
by karsten＠torproject.org 17 Jun '15

17 Jun '15

commit ba71cbb86d48b54b3dd10104bdfa12c8b0c17a66 Author: Karsten Loesing <karsten.loesing(a)gmx.net> Date: Sat Nov 29 09:54:35 2014 +0100 Rewrite major parts of the hid-serv-stats report. --- 2015/hidden-service-stats/.gitignore | 1 + 2015/hidden-service-stats/hidden-service-stats.tex | 1531 ++++++++++---------- 2015/hidden-service-stats/protocol.odg | Bin 0 -> 17986 bytes 2015/hidden-service-stats/protocol.pdf | Bin 0 -> 20270 bytes 4 files changed, 801 insertions(+), 731 deletions(-) diff --git a/2015/hidden-service-stats/.gitignore b/2015/hidden-service-stats/.gitignore index 2c5e321..863d44c 100644 --- a/2015/hidden-service-stats/.gitignore +++ b/2015/hidden-service-stats/.gitignore @@ -1,3 +1,4 @@ .DS_Store hidden-service-stats.pdf +*.toc diff --git a/2015/hidden-service-stats/hidden-service-stats.tex b/2015/hidden-service-stats/hidden-service-stats.tex index 75ce789..7760e83 100644 --- a/2015/hidden-service-stats/hidden-service-stats.tex +++ b/2015/hidden-service-stats/hidden-service-stats.tex @@ -1,5 +1,6 @@ \documentclass{tortechrep} \usepackage{url} +\usepackage{graphicx} \usepackage{hyperref} \usepackage{longtable} @@ -24,86 +25,335 @@ % - Abbreviations are best avoided. % - Code, cell names, etc. are put inside \verb+...+. +\tableofcontents + \begin{abstract} -This document discusses new hidden-service related statistics to be -gathered by relays and reported to the directory authorities in their -extra-info descriptors. +We have little insight into hidden-service usage in the public Tor +network. +In this report we discuss possible statistics to understand hidden +services better which can be used to make performance improvements, find +bugs, and possibly even detect attacks. +We also evaluate whether, and how, statistics could be abused by an +adversary. +The main contribution of this report is a comprehensive list of +hidden-service related statistics with recommendations for or against +gathering them in the public Tor network. \end{abstract} -\section{Motivation} - -We have little insight into hidden-service usage in the Tor network. -The statistics discussed in this document shall help us get a basic -understanding of hidden-service usage, improve their performance, find -bugs, etc. - -\section{Design} - -The statistics discussed here can all be gathered by relays taking one of -three possible roles in the rendezvous protocol: as 1) introduction point, -2) rendezvous point, or 3) hidden-service directory. -All statistics will be reported by relays to the directory authorities in -their extra-info descriptors, possibly every 24 hours. - -General considerations for gathering hidden-service statistics: - -\begin{itemize} -\item Should we report number and type of failures in the protocol, if -these statistics are not sufficient to actually debug a problem? -Could be a starting point to look at actual logs from relays. -But is this what statistics are for? -\item Should we not report statistics if a relay acted as dir/IPo/RPo for -less than a certain threshold of clients/services? -Can we make sure that an adversary doesn't generate traffic on their own -to push a relay above that threshold and report a tiny number of real -users? -\end{itemize} - -There are no plans for gathering hidden-service statistics on hidden -servers or clients, mostly because there is no data-collecting -infrastructure in place and because privacy implications are even less -clear in the case of single clients or servers reporting statistics than -in the case of relays serving dozens or hundreds of hidden services and -their clients. - -Note: there is an evaluation in the next section that can lead to -positive/negative/neutral recommendations for actually proposing and -implementing statistics. - -\subsection{Statistics from relays acting as introduction points} - -The following statistics are related to relays acting as introduction -points. -These cover (1) services establishing introduction points -(\verb+ESTABLISH_INTRO+ cell) and (2) clients sending introductions to -introduction points (\verb+INTRODUCE1+ cell).% and 3) the server -%responding to the introduction point (the server does not respond to the -%introduction point). - -\subsubsection{Statistics on hidden services establishing introduction -points} - -\paragraph{Number of attempts to establish an introduction point (1.1.1.)} +\section{Introduction} + +Tor hidden services are a means to provide web services over Tor while +hiding their physical location. +Unfortunately (or some would say fortunately), we have little insight into +hidden-service usage in the public Tor network. +A basic understanding of hidden-service usage would help us direct efforts +on hidden-service development. +These efforts include making performance improvements, finding bugs, and +possibly even detecting attacks. + +In this report we compile a list of hidden-service related statistics and +evaluate whether and how they could be used to make hidden services +better. +% There are no plans for gathering hidden-service statistics on hidden +% servers or clients, mostly because there is no data-collecting +% infrastructure in place and because privacy implications are even less +% clear in the case of single clients or servers reporting statistics than +% in the case of relays serving dozens or hundreds of hidden services and +% their clients. +At the same time we evaluate whether and how these statistics could be +abused by an adversary by providing them with data from relays they don't +control. +The primary purpose of hidden services to hide their location and the +location of their users must not be put at risk. +Other security properties like their ability to hide their existance, at +least to some extent, should not be sacrificed for potential improvements. +As a result we present a list of hidden-service related statistics with +recommendations for or against deploying them in the public Tor network. + +This report is structured as follows: +the next section gives an overview of the hidden-service protocol with +special focus on measurement points for hidden-service statistics. +Section~\ref{sec:criteria} defines evaluation criteria for statistics to +decide whether they should be considered helpful and/or harmful. +Section~\ref{sec:list} contains a list of hidden-service related +statistics, partly with early results obtained from a private Tor network, +and an evaluation of their helpfulness and harmfulness. +Section~\ref{sec:recommendation} concludes this report by recommending +which statistics should be implemented and deployed in the public Tor +network. + +\section{Hidden-service protocol and measurement points} +\label{sec:protocol} + +The hidden-service protocol consists of multiple substeps to make a +service available in the network and for clients connecting to a service. +The statistics discussed in this document all rely on relays gathering +aggregate statistics of their role in the hidden-service protocol. +These roles are: a) directory, b) introduction point, and c) rendezvous +point. +Figure~\ref{fig:protocol} gives an overview of protocol steps. + +\begin{figure} +\centering +\includegraphics[width=0.8\textwidth]{protocol.pdf} +\caption{Hidden-service protocol steps as observed by relays.} +\label{fig:protocol} +\end{figure} + +The protocol substeps for making a service available in the network are as +follows: + +\begin{enumerate} +\item The service \emph{establishes an introduction point} on one or more +relays. +A relay first receives a circuit extension request from another relay to +become the next relay in a circuit. +At this time the relay does not recognize that it will become an +introduction point. +Then the relay receives a request to establish an introduction point on +behalf of the service that built the circuit. +However, the introduction point does not know which service it's serving, +because the service creates a fresh identity key for each introduction +point. +The circuit, now called introduction circuit, will be kept open until the +service closes it. +From that time on the relay accepts client introductions for the service +coming in via other circuits. +\item The service \emph{publishes a descriptor} to a total number of six +directories, which are common relays with high-enough uptime of 24 hours +or more. +Each of those relays first receives a circuit extension request, followed +by a request to publish the descriptor. +The relay can read most parts of the descriptor which includes service +identity and selected introduction points. +The circuit that was built by the service is closed immediately after +transmitting the descriptor. +\end{enumerate} + +The protocol substeps for a client connecting to a service are as +follows: + +\begin{enumerate} +\setcounter{enumi}{2} +\item The client \emph{fetches a descriptors} from a directory. +The relay that acts as directory first receives a circuit extension +request, followed by a request to fetch the descriptor. +Once the descriptor is returned, or a response saying that it does not +exist, the circuit is closed immediately. +\item The client \emph{establishes a rendezvous point} on a relay. +The relay observes a circuit extension request, followed by the request to +become the client's rendezvous point for connecting to a service. +The relay does not learn which service the client attempts to connect to, +but it only learns a random identifier. +The circuit, now called rendezvous circuit, is kept open until either +client or service close it. +\item The client \emph{sends an introduction} to one of the service's +introduction points. +The introduction point first observes a circuit extension request, +followed by the introduction message, which it forwards to the service via +its introduction circuit. +The client's circuit is torn down immediately after receiving the +introduction and responding with an acknowledgement. +\item The service \emph{sends a rendezvous message} to the client's +rendezvous point. +The rendezvous point sees a circuit extension request, followed by the +rendezvous message, which it forwards to the client via its rendezvous +circuit. +Both service-side and client-side circuits are kept open until either side +decides to close it. +\item Both \emph{client and service send and receive data} along their +part of the rendezvous circuit. +The rendezvous point sees cells coming in from either side and forwards +them to the other side. +All cells are padded and end-to-end encrypted between client and service, +so that the rendezvous point only sees encrypted cells of the same size. +\end{enumerate} + +All these protocol steps constitute potential measurement points for +hidden-service related statistics. + +\section{Evaluation criteria for statistics} +\label{sec:criteria} + +Each of the hidden-service related statistics needs to fulfill two +criteria: first, it needs to serve a concrete purpose for making hidden +services better; and second, it must not provide an adversary with data +that would help them locate clients or services. + +\subsection{Possible benefits from gathering statistics} + +The purpose of the statistics discussed in this report is to learn more +about hidden services and as a result make them better. +We can imagine a couple possible benefits from gathering these statistics +that we outline in the following. +For all possible benefits we assess whether we need statistics from the +public Tor network, or if we could as well obtain statistics in a private +testing network. + +\paragraph{Learn about usage} + +We are interested in learning more about hidden service usage to direct +our development efforts. +All past design decisions around hidden services were either based on +assumptions how hidden services might be used, or on own observations. +If we had statistics about provided services and their usage, we might +adapt the design to its actual usage. +Related to this, having statistics on hidden service usage as compared to +normal Tor usage might help in getting sponsors and developers interested +in making hidden services better. + +\paragraph{Improve performance} + +We want to measure performance of hidden services as a whole and of their +protocol substeps to identify any bottlenecks. +We hope that we can perform most of these measurements in private networks +where we don't put any users at risk. +But if we want to build a model that resembles reality, we'll need at +least some real data as input, or we're back at making assumptions which +may not reflect reality. + +\paragraph{Identify bugs} + +Statistics can help us detect bugs that cannot be found in private Tor +networks. +Obviously, we'd want to fix as many bugs as possible in a private network +setting. +But there will always be cases that we'd miss in a test network, possibly +caused by different software versions or non-standard usage that we didn't +think of. +Having some real data indicating problems in the hidden-service protocol +would serve as good starting point to go bug hunting. + +\paragraph{Discover attacks} + +We might be able to use hidden-service related statistics to uncover +ongoing attacks in the network. +If a reported statistic is off by more than a certain expected threshold +or against the past trend, that might indicate that an attack is mounted +on the network. +This is obviously something we can only find out in the public Tor network +and not in private testing networks. + +\subsection{Possible risks of gathering statistics} -\subparagraph{Details} - -A relay counts how many \verb+ESTABLISH_INTRO+ cells it receives during -the statistics interval. +% HSDirs threat model notes +% +% Hidden Service directories periodically receive HS descriptors from +% hidden services. They cache them, and then serve them to any clients +% that ask for them. +% +% Hidden service directories are placed in a hash ring, and each hidden +% service picks a slice of hidden service directories from that hash ring. +% Given the address of a hidden service, it's easy to learn which +% directories are responsible for it. This makes hidden-service directory +% statistics dangerous since they can potentially be matched to specific +% hidden services. +% +% Furthermore, each hidden service has 6 directories, and each directory +% serves a different set of services. This means that attackers have 6 +% different data points per hidden service every hour that can be used to +% reduce measurement noise. + +The benefits of statistics have been discussed above, so it's clear that +statistics can be used for good. +But they can also be used for bad. +The risk of gathering statistics is that an adversary could misuse them +for their attacks on clients and/or services. +All statistics are designed to be publicly available, so an adversary, +who might already control one or more relays, could use statistics to +learn something about relays she does not (yet) control. +In the following we outline aspects of hidden-service usage that we don't +want to reveal by statistics. + +\paragraph{Infer availability or popularity of a specific service} + +We want to learn interesting facts about all services together, but we +want to avoid that statistics can be used to single out any specific +service and derive its availability or popularity. +This includes services identified by their service address as well as +popular services that may be identified by the number of connecting +clients or handled traffic volume. +As a matter of fact, it's not difficult for an adversary to link services +to relays working as directories or introduction points: the six +directories storing descriptors for that service can be determined easily, +and the introduction points of a service are listed in its descriptors. +The adversary can compare statistics reported by all directories or +introduction points of a service to reduce measurement noise. +Only the rendezvous point changes for each client connection, so that +statistics reported by rendezvous point cannot easily be linked to a +specific service. + +\paragraph{Infer activity of a specific client} + +Related to the above, we want to learn about activity of all clients, but +we want to avoid that statistics can be used to single out a specific +client and learn about its activity. +This includes power users that access lots of services or transfer large +data volumes as well as clients which are services themselves, like +tor2web. + +\paragraph{Assess precise number of available services} + +We want to learn roughly how many services are available in the network, +but we want to avoid that these estimates make it easier for an adversary +to enumerate available services. +While hiding the existence of a service is not the primary purpose of +hidden services, it's a security feature we don't want to give up easily. + +\subsection{Other aspects of gathering statistics} + +There are certain aspects of any given statistic that should be +considered in order to decide for or against gathering them. +We list a few of those aspects below. + +\paragraph{Robustness against liars} + +The statistics discussed in this document would all be reported by relays +and not confirmed by third parties. +We must consider cases where a relay operators modifies their source code +to manipulate reported statistics to their advantage. +A statistic should be robust against single liars, as long as there is a +sufficient number of honest relays, possibly run by trusted operators. +We also should not depend on statistics reported by single relays, if +possible. +Though it would be interesting to have statistics indicating adoption of +protocol changes. + +\paragraph{Robustness against protocol changes} + +We are planning to improve the hidden-service protocol in the medium term +by making major protocol changes.% +\footnote{\url{https://gitweb.torproject.org/torspec.git/blob/HEAD:/proposals/224-rend-spec-ng.txt}} +We should not implement a statistic if we know it will soon become +obsolete because of those protocol changes. + +\section{List of hidden-service related statistics} +\label{sec:list} + +\textbf{The descriptions in this section have not been updated yet. Let's +wait with cleaning them up until we have a final list of statistics and a +final section structure. Otherwise we'd be rewriting this section over +and over and over.} + +In this section we attempt to compile a comprehensive list of +hidden-service related statistics. +We start with general circuit related statistics, statistics on +successfully advertised services and successful service usage, +performance-related statistics, and finally discuss statistics on protocol +failures. -\subparagraph{Benefits} +Not all of the following statistics provide an actual benefit towards +making hidden services better, and some statistics are outright dangerous +and should never be deployed in the public Tor network. +However, they are all worth being listed here, if only to have a reference +for the future that says \emph{why} they are a bad idea. -We could validate that we have a ``uniform'' random distribution among -chosen introduction points in the network. -If not, there might be a problem. +\subsection{General hidden-service circuit related statistics} -\subparagraph{Risks} -Considering we have a good randomness meaning every relay has the same -chance to be picked, there are no obvious risks to share this. -If not, we don't see a real risk for an attacker to know that a specific -relay got chosen X times instead of the measured average Y. +We start with statistics that are not specific to the three roles of +relays in the hidden-service protocol, but that apply to all of them. -\paragraph{Time from establishing a circuit to becoming an introduction -point (1.1.2.)} +\subsubsection{Time from circuit extension to circuit purpose change} % (the following distinction cannot be made, AFAIK. here's what happens: % we receive a CREATE (?) cell from another relay that establishes the @@ -116,16 +366,16 @@ point (1.1.2.)} % cannibalize it and use it as introduction circuit. statistics would % tell us what fraction of circuits is newly built and what was % cannibalized; well, allow guesses about the two cases.) - -\subparagraph{Details} - +% +\textbf{Details:} +% A relay measures the time difference between a circuit extension from the previous relay in the circuit to receiving an \verb+ESTABLISH_INTRO+ cell. A very small time difference implies that the circuit was built/extended specifically for use as introduction point, whereas a larger time difference hints to the hidden service re-using a pre-built circuit for the introduction point. - +% % [dgoulet]: "if the time difference between those two events is small, we % can guess that the client built a new circuit for using us as % introduction point, or that she extended an existing circuit by one hop @@ -155,7 +405,8 @@ the introduction point. % relay only sees that the circuit gets extended to it, but it has no % information how long the client had the circuit lying around before % extending it. - +% +% % Newly established circuit. % Benefits: Performance reason, this can be useful to know the real cost % (on average) of becoming an IP. Can lead to understanding bottle necks @@ -171,127 +422,307 @@ the introduction point. % Risks: Also tricky. That info could tell us clearly if the IP circuit is % on a new or already established circuit which changes the traffic % timing. Not sure how useful it is to an attacker though. - -\subparagraph{Benefits} - +% +\textbf{Benefits:} +% We would learn what fraction of introduction points can be established on short notice using pre-built circuits vs. first having to build or extend circuits. This is something we would measure on hidden services, but given that we don't have statistics from those, measuring this on introduction points seems like a fine workaround. - +% % Both of these stats should probably report an average and a variance % instead of a <timestamp> + <circ. creation time>, that would be a % disaster. (yes, please, no data about single events; that wouldn't fit % into descriptors anyway, and it would reveal far too much detail.) % I really wonder if an attacker could use this average to partition part % of the network to predict where the circuit can be located? - -\subparagraph{Risks} - +% +The time from receiving a circuit creation request to seeing the +\verb+ESTABLISH_RENDEZVOUS+ cell can help us optimize the rendezvous +protocol for performance. +The current implementation either builds a new circuit or extends an +existing circuit by one hop before sending the \verb+ESTABLISH_RENDEZVOUS+ +cell. +So, the measured time will be close to zero. +But if we ever decide to re-use existing circuits for rendezvous without +extending them by another hop, this metric will give us an idea on the +adoption of that change. +Admitted, this benefit is not huge. +% +\textbf{Risks:} +% No obvious risks. % only talking about aggregate statistics here, not % single observations. -\paragraph{Number of failed attempts to establish an introduction point -(1.1.3.)} +% [dgoulet]: Reporting a mean/average and with maybe a treshold before we +% publish like "we need 100 rdv cell before reporting this stat" ? +% [karsten]: agreed that this may seem useful in general. but what if the +% adversary sends 100 cells themselves to help us get past the threshold +% and report a tiny number of actual user cells? but I added an item to +% the section start where we can discuss whether this is a good safeguard +% in general. +% [dgoulet]: Right well that's a time statistic and not an amount so if an +% attacker would establish 100 RP I guess he/she indeed poisoning the +% stat?... +% [karsten]: Maybe. In theory, the stat is not poisoned for the attacker +% if she knows what values she's contributed to it. But I agree that this +% is not the best example. -\subparagraph{Details} +\subsubsection{Number of circuits built with TAP vs. nTor} -A relay can not decline to be an introduction point. -However, an \verb+ESTABLISH_INTRO+ cell might be malformed (wrong public -key, bad signature, etc...). -The relay would count the number of declined \verb+ESTABLISH_INTRO+ cells -and report them along with the total number of received -\verb+ESTABLISH_INTRO+ cells. -Or it would report successes and failures, rather than totals and -failures. +\textbf{Details:} +% +Older clients (0.2.3.x) would build/extend circuits using TAP, newer +clients would use nTor for that. +Relays can report the number of introduction circuits that were built +using either of the two methods. +More precisely, relays would remember for each circuit how it was built, +and as soon as they receive an \verb+ESTABLISH_INTRO+ cell, they increment +one of two counters. +See ticket 13466 for details. +% +\textbf{Benefits:} +% +We would learn what fraction of clients and what fraction of services run +older tor versions (0.2.3.x or older). -\subparagraph{Benefits} +\subsubsection{Time from circuit purpose change to tearing down circuit} -Wrong \verb+ESTABLISH_INTRO+ cells shows either a very bad bug in the code -or a deliberate action (data mangling, unknown attack, DoS, ...). +\textbf{Details:} +% +Relays report how long it takes from changing the purpose of circuit to a +hidden-service specific purpose to tearing down the circuit. +This statistic only makes sense for circuits which are only built for +sending a single message, which includes services publishing descriptors, +clients fetching descriptors, and clients sending introductions. +In theory, we would expect the circuits to be torn down immediately, but +in practice circuits might be kept open longer. -% [dgoulet]: After an IRC discussion with arma and asn, I remember that -% this one could be "cool to have" but without more information that we -% can't collect for privacy reasons, this stat would not help at all in -% the end game. The question remains if we should simply keep it or not -% even if right now we don't see a added value? -% [karsten:] right, this is a fine question, not only limited to this -% statistic. I added a new paragraph to the section start for "general -% considerations for gathering hidden-service statistics". +\subsection{Statistics on service advertisement} -\subparagraph{Risks} +The following statistics are all about (successful) service advertisement. +Performance-related statistics and failure statistics are covered in a +later section. -No obvious risks. +\subsubsection{Number of established introduction points} -\paragraph{Lifetime of introduction circuits (1.1.4.)} +\textbf{Details:} +% +A relay counts how many \verb+ESTABLISH_INTRO+ cells it receives and acts +upon during the statistics interval. +% +\textbf{Benefits:} +% +We could validate that we have a ``uniform'' random distribution among +chosen introduction points in the network. +If not, there might be a problem. +% +\textbf{Risks:} +Considering we have a good randomness meaning every relay has the same +chance to be picked, there are no obvious risks to share this. +If not, we don't see a real risk for an attacker to know that a specific +relay got chosen X times instead of the measured average Y. -\subparagraph{Details} +\subsubsection{Time from establishing introduction point to tearing down +circuit (1.1.4.)} +\textbf{Details:} +% How long did an introduction circuit last? Relays would report statistics like mean/median time, variance/IQR, and/or percentiles here. - -\subparagraph{Benefits} - +% +\textbf{Benefits:} +% The longer introduction circuits last, the better, from a performance POV. If many circuits break after a short time period, that indicates that services should attempt to make better path-selection decisions for building introduction circuits. +This statistic can also be used to analyze what fraction of services is +available for a short time only, and what fraction is available most of +the time. -\paragraph{Reasons for terminating established introduction points -(1.1.5.)} +\subsubsection{Number of descriptor publish request (3.1.1.)} + +\textbf{Details:} +% +Relays keep a local count of cached hidden-service descriptors. +Every time they add or remove a descriptor to their cache, relays update +their counter and record the time of change. +At the end of the statistics period they calculate statistics like +minimum, maximum, average number of hosted descriptors during the +statistics interval. +(There may be more efficient ways to implement these statistics that avoid +keeping a full history with timestamps, which are not discussed here.) +% +\textbf{Benefits:} +% +This is an interesting statistic that would allow us to understand how +used hidden services are, and also detect sudden changes in the number of +services (botnets, chat protocols, etc.). +Also, learning the number of hidden services per directory will help us +find bugs in the hash ring code and also understand how loaded directories +are. +FWIW, when \verb+rend-spec-ng.txt+ gets implemented, it will be harder for +hidden service directories to learn the number of served services since +the descriptor will be encrypted. +However, directories will still be able to approximate the number of +services by checking the amount of descriptors received per publishing +period. +If this ever becomes a problem we can imagine publishing fake descriptors +to confuse the directories. +% +\textbf{Risks:} +% +Publishing this stat would allow someone who is indexing hidden services +to be able to say ``I have seen 76~\% of all HSes''. +We would really like to avoid having such an enumeration-facilitating +property. +We could be persuaded that with some heavy stats obfuscation (heavier than +the bridge stats obfuscation), this statistic might be plausible. +By statistics obfuscation, we mean obfuscating the numbers so that the +attacker can only say ``I'm somewhere between 60~\% to 75~\% of all +HSes.''. +This is a bit related to differential privacy as we understand it, but +much more basic. -\subparagraph{Details} +\subsubsection{Number of descriptor updates per service (3.1.2.)} -Relays report frequencies of circuit terminations requested by services -vs. different types of failures. +\textbf{Details:} +% +Relays count how many descriptor updates they see per service. +Assuming that stats are published daily (which is not necessary), this is +going to be a number between 1 and 24 (since RendPostPeriod is currently +one hour) and services pick a new directory after 24 hours (see +\verb+rendcommon.c:get_time_period()+). +% +\textbf{Risks:} +% +Depending on how many HSes are behind each HSDir, this statistic might or +might not reveal uptime information about specific services. +Still it doesn't seem like something we want to risk. +Also, if the result is greater than 24, it means that an HS with modded +RendPostPeriod was publishing to that HSDir (and that the HSDir doesn't +have many clients). +Do we want to reveal that? +OTOH, it seems to me that if the directory is serving many services, this +statistic doesn't really provide any insight. -\subparagraph{Benefits} +\subsubsection{Time between last and first published descriptor with same +identifier} -If there are more than a small percentage of failures, decide how to make -things more robust. +\textbf{Details:} +% +Relays report statistics on the time difference between the last and the +first descriptor published under the same identifier. +This statistics indicates service uptime, because a service with high +uptime would periodically re-publish its descriptor whenever its +introduction points change. +There is an upper bound on this statistic at 24 hours, because that's when +descriptor identifiers change. + +\subsubsection{Number of introduction points contained in descriptors +(3.1.4.)} -\subparagraph{Risks} +\textbf{Details:} +% +Relays report average number of introduction points contained in +hidden-service descriptors, possibly also percentiles. +% +\textbf{Benefits:} +% +It would be interesting to know whether services deviate from the default +number of introduction points. +Though it's unclear what we're going to do with this information. +This statistic will also be killed by rend-spec-ng. -No obvious risks. +\subsubsection{Number of descriptors with encrypted introduction points +(3.1.5.)} -\paragraph{Number of introduction circuits built with TAP vs. nTor -(1.1.6.)} +\textbf{Details:} +% +Relays can look at published hidden-service descriptor and count +descriptors with plain-text vs. encrypted introduction point sections. +% +\textbf{Benefits:} +% +We would learn what fraction of services uses authentication features. +This statistic won't be available after implementing rend-spec-ng. -\subparagraph{Details} +\subsection{Statistics on service usage} -Older clients (0.2.3.x) would build/extend circuits using TAP, newer -clients would use nTor for that. -Relays can report the number of introduction circuits that were built -using either of the two methods. -More precisely, relays would remember for each circuit how it was built, -and as soon as they receive an \verb+ESTABLISH_INTRO+ cell, they increment -one of two counters. -See ticket 13466 for details. +The following statistics are about service usage, where +performance-related statistics and failure statistics are covered at a +later time. -\subparagraph{Benefits} +\subsubsection{Number of descriptor fetch requests (3.2.1.)} -We would learn what fraction of hidden services run older tor versions -(0.2.3.x or older). +\textbf{Details:} +% +A relay reports the total number of descriptor fetch requests, regardless +of the requested hidden service identity. +% +\textbf{Risks:} +% +An adversary can use this statistic to evaluate the popularity of an HS. +An adversary can also use this stat to detect big changes in the numbers +of visitors of popular HSes. +Of course, there will be noise in the statitics since multiple services +correspond to each directory, but the adversary could reduce the noise +after observing the same service rotating to different directories, and +also by examining the statistics of all 6 directories that correspond to +the service. +This doesn't seem like a problem that is solvable with simple obfuscation +of stats, and I suggest we don't do this statistic at all. -\subsubsection{Statistics on clients connecting to introduction points} +\subsubsection{Number of descriptor fetch requests by service identity +(3.2.2.)} -\paragraph{Total number of introductions received from clients (1.2.1.)} +\textbf{Details:} +% +Relays report the distribution of descriptor fetch requests to hidden +service identities. -\subparagraph{Details} +\subsubsection{Number of established rendezvous points (2.1.1.)} -Relays report how many \verb+INTRODUCE1+ cells they received from clients. +\textbf{Details:} +% +Relays report how many \verb+ESTABLISH_RENDEZVOUS+ cells they received. +% +\textbf{Benefits:} +% +The number of received \verb+ESTABLISH_RENDEZVOUS+ cells indicates how +many connection attempts there are by clients to services that are +running. +This number is different from the number of descriptor fetches which +happen when clients don't know yet whether a service is running, which +will be omitted if clients still have a descriptor cached from a previous +connection, and which we may not even gather because of privacy concerns. +We can easily weight the number of \verb+ESTABLISH_RENDEZVOUS+ cells with +the probability of choosing a relay as rendezvous point to estimate the +total number of such cells in the network. +% +\textbf{Risk:} +% +There is no obvious risk from sharing this number if aggregated over a +large enough time period. -\subparagraph{Benefits} +\subsubsection{Number of introductions received from clients (1.2.1.)} +\textbf{Details:} +% +Relays report how many \verb+INTRODUCE1+ cells they received from clients. +% +\textbf{Benefits:} +% This indicates that there is in fact a client trying to reach a hidden service thus the amount of cells could give us a rough estimate of how many clients are actually connecting and using hidden services. - -\subparagraph{Risks} - +% +\textbf{Risks:} +% Unclear. On the one hand, this is basically the same risk as the amount of time a relay is picked as an introduction point. @@ -315,241 +746,40 @@ requests a very popular hidden service gets. % introduction points every hour, AFAIK. % [dgoulet]: No they don't, I confirmed in the code. -\paragraph{Number of introductions received by established introduction -point (1.2.2.)} - -\subparagraph{Details} +\subsubsection{Number of introductions received by established +introduction point (1.2.2.)} +\textbf{Details:} +% Relays can serve as introduction point for an arbitrary number of hidden services. Relays could report statistics (like percentiles) on received \verb+INTRODUCE1+ cell by introduction circuit. - -\subparagraph{Benefits} - +% +\textbf{Benefits:} +% This statistic would tell us something about usage diversity of hidden services. A special case would be the number or fraction of established introduction points that never sees a single \verb+INTRODUCE1+ cell. It's unclear what we'd do with this information, though. -\paragraph{Number of discarded client introductions by reason (1.2.3.)} - -\subparagraph{Details} - -How many \verb+INTRODUCE1+ cells have been discarded because of unknown -service/malformed (?)/whatever-can-go-wrong, by introduction point? - -\subparagraph{Benefits} - -Anything exceeding a small portion of discarded \verb+INTRODUCE1+ cells -shows either a very bad bug in the code or a deliberate action (data -mangling, unknown attack, DoS, ...). - -% [dgoulet]: That is again a "cool to have" stat but not sure how it would -% help us investiguate. It can I guess trigger an alarm but apart from -% that... -% [karsten]: right, see section start. - -\subparagraph{Risks} - -No obvious risks. -More precisely, if absolute numbers are reported, the risk is the same as -the risk of reporting the number of received \verb+INTRODUCE1+ cells; if -only fractions are reported, it's not that bad. - -\subparagraph{Recommendation} - -\paragraph{Time between establishing introduction point and receiving the -first client introduction (1.2.4.)} - -\subparagraph{Details} - -Relays report the time between \verb+ESTABLISH_INTRO+ and first -\verb+INTRODUCE1+ cell. - -\subparagraph{Benefits} - -This statistic tells us how long it takes for the hidden service to -include a relay in its descriptor and publish that descriptor, and for the -first client to fetch that descriptor and use that relay for its -introduction. -This may not be very useful, but is listed here for completeness. -% [dgoulet]: That would basically leak the RendPostPeriod (if IP changes -% at each upload) of the HS. Not sure how an attacker could use that to -% his/her advantage but to consider. -% [karsten]: again, I think you're wrong about introduction points -% changing at each upload. -% [dgoulet]: Yup, IP do *NOT* change at each upload. - -\subparagraph{Risks} - -No obvious risks. - -\paragraph{Number of client introductions coming in via circuits built -with TAP vs. nTor (1.2.5.)} - -\subparagraph{Details} - -Relays remember whether an incoming circuit was built using TAP or nTor. -Whenever they receive an INTRODUCE1 cell they increment a counter for -either TAP or nTor. -See ticket 13466 for details. - -\subparagraph{Benefits} - -We would learn what fraction of hidden-service clients run older tor -versions (0.2.3.x or older). - -%3) Stats about the server responding to the introduction point. -% (this does not happen in the protocol) -% -% - How many INTRODUCE2 replayed cell we've observed? -% This can actually be an active attack or a client sending multiple -% INTRODUCE1 cell via different introduction points. -% - Benefits: Could give us an idea of how many client are misbehaving -% (actually need to confirm if the tor client can send multiple -% INTRODUCE1 for the same service). -% - Risks: No obvious risks. -% -% Note that the amount of valid INTRODUCE2 cell seen should correspond -% to the amount of RP circuit launched (might be a cannibalized one). -% So, having that stat could be useful -% to again simply correlate that stat with the RP amout stat. Finding -% out that there is a discrepancy could help us narrow down performance -% issue. -% -% (removed the following, because receiving INTRODUCE1 triggers an event -% that ends with responding with INTRODUCE_ACK.) -% - How many INTRODUCE_ACK were sent to the client? -% - Benefits: Can be coupled with the how many INTRODUCE1 we've seen and -% look for discrepancy. The difference of intro1 and intro_ack could not -% be explained though without a reason why the HS dropped it or if the -% HS did receive the intro1 at all. So, this stat can be fun to have but -% not really useful for performance tuning I would say. -% - Risks: No obvious risks. - -\subsection{Statistics from relays acting as rendezvous points} - -The following statistics are all related to relays acting as rendezvous -points. -These statistics cover the whole process from (1) clients establishing -rendezvous points, (2) servers connecting to a client's rendezvous point, -and (3) clients creating streams to the server, exchanging data, and -tearing down the circuit. -These phases of the rendezvous protocol are also used to organize the -statistics below. -All statistics focus on the number or timing of cells exchanged in the -rendezvous protocol and underlying OR protocol. - -\subsubsection{Statistics on clients establishing rendezvous points} - -\paragraph{Number of established rendezvous points (2.1.1.)} - -\subparagraph{Details} - -Relays report how many \verb+ESTABLISH_RENDEZVOUS+ cells they received. - -\subparagraph{Benefits} - -The number of received \verb+ESTABLISH_RENDEZVOUS+ cells indicates how -many connection attempts there are by clients to services that are -running. -This number is different from the number of descriptor fetches which -happen when clients don't know yet whether a service is running, which -will be omitted if clients still have a descriptor cached from a previous -connection, and which we may not even gather because of privacy concerns. -We can easily weight the number of \verb+ESTABLISH_RENDEZVOUS+ cells with -the probability of choosing a relay as rendezvous point to estimate the -total number of such cells in the network. - -\subparagraph{Risk} - -There is no obvious risk from sharing this number if aggregated over a -large enough time period. - -\paragraph{Time from circuit creation to establishing rendezvous point -(2.1.2.)} - -\subparagraph{Details} - -Relays report statistics on the time between circuit creation to receiving -a \verb+ESTABLISH_RENDEZVOUS+ cell. - -\subparagraph{Benefits} - -The time from receiving a circuit creation request to seeing the -\verb+ESTABLISH_RENDEZVOUS+ cell can help us optimize the rendezvous -protocol for performance. -The current implementation either builds a new circuit or extends an -existing circuit by one hop before sending the \verb+ESTABLISH_RENDEZVOUS+ -cell. -So, the measured time will be close to zero. -But if we ever decide to re-use existing circuits for rendezvous without -extending them by another hop, this metric will give us an idea on the -adoption of that change. -Admitted, this benefit is not huge. - -\subparagraph{Risk} - -There is no obvious risk related to this statistic. - -% [dgoulet]: Reporting a mean/average and with maybe a treshold before we -% publish like "we need 100 rdv cell before reporting this stat" ? -% [karsten]: agreed that this may seem useful in general. but what if the -% adversary sends 100 cells themselves to help us get past the threshold -% and report a tiny number of actual user cells? but I added an item to -% the section start where we can discuss whether this is a good safeguard -% in general. -% [dgoulet]: Right well that's a time statistic and not an amount so if an -% attacker would establish 100 RP I guess he/she indeed poisoning the -% stat?... -% [karsten]: Maybe. In theory, the stat is not poisoned for the attacker -% if she knows what values she's contributed to it. But I agree that this -% is not the best example. - -\subparagraph{Recommendation} - -\paragraph{Number of rendezvous point establishment requests coming in via -circuits built with TAP vs. nTor (2.1.3.)} - -\subparagraph{Details} - -Relays remember whether an incoming circuit was built using TAP or nTor. -Whenever they receive an \verb+ESTABLISH_RENDEZVOUS+ cell they increment a -counter for either TAP or nTor. -See ticket 13466 for details. - -\subparagraph{Benefits} - -We would learn what fraction of hidden-service clients run older tor -versions (0.2.3.x or older). - -% How much RP traffic was transfererd through RP circuits? (see below re: -% RELAY cells) - -% Average traffic transfered through RP circuits? (see below re: RELAY -% cells) - -\subsubsection{Statistics on servers connecting to a client's rendezvous -point} - -\paragraph{Number of server rendezvous (2.2.1.)} - -\subparagraph{Details} +\subsubsection{Number of server rendezvous (2.2.1.)} +\textbf{Details:} +% Relays report the total number of \verb+RENDEZVOUS1+ cells they receive. - -\subparagraph{Benefits} - +% +\textbf{Benefits:} +% The number of received \verb+RENDEZVOUS1+ cells tells us how many connection requests are actually accepted by servers. This number may be lower than the number of \verb+ESTABLISH_RENDEZVOUS+ cells, because of failures in connection establishment, authentication failures, or other reasons. - -\subparagraph{Risks} - +% +\textbf{Risks:} +% There is no obvious risk from this metric, because it's unrelated to any given client or server. @@ -567,95 +797,16 @@ given client or server. % (one ESTABLISH_RENDEZVOUS), that's quite an issue (loop that went wrong % :). -\paragraph{Time from establishing a rendezvous point to receiving the -server rendezvous (2.2.2.)} - -\subparagraph{Details} - -Relays report the time from receiving an \verb+ESTABLISH_RENDEZVOUS+ cell -to receiving the corresponding \verb+RENDEZVOUS1+ cell. - -\subparagraph{Benefits} - -The time between receiving an \verb+ESTABLISH_RENDEZVOUS+ cell from the -client and the corresponding \verb+RENDEZVOUS1+ cell from the server tells -us a lot about performance of the rendezvous protocol. -The rendezvous point is the only place in the protocol that witnesses -events near the beginning and near the end of the connection establishment -process. -If we ever want to improve the substeps inbetween, this metric is the only -way to measure effectiveness of improvements in the deployed network. - -\subparagraph{Risks} - -Again, there are at least no obvious risks from gathering this statistic. - -\paragraph{Number of server rendezvous with unknown rendezvous cookie -(2.2.3.)} - -\subparagraph{Details} - -Relays report the number of \verb+RENDEZVOUS1+ cell with unknown -rendezvous cookie. - -\subparagraph{Benefits} - -The number of \verb+RENDEZVOUS1+ cell that cannot be matched with a -previously established rendezvous circuit can be interesting for analyzing -problems in the protocol. -We might even distinguish between rendezvous cookies that were previously -known to the relay and those that seem entirely unrelated. -The benefit gained from this statistic is not huge though. - -\subparagraph{Risk} - -No obvious risks. - -\paragraph{Number of server rendezvous coming in via circuits built with -TAP vs. nTor (2.2.4.)} - -\subparagraph{Details} - -Relays remember whether an incoming circuit was built using TAP or nTor. -Whenever they receive a \verb+RENDEZVOUS1+ cell they increment a counter -for either TAP or nTor. -See ticket 13466 for details. - -\subparagraph{Benefits} - -We would learn what fraction of hidden services run older tor versions -(0.2.3.x or older). - -\subsubsection{Statistics on clients creating streams to the server, -exchanging data, and tearing down the circuit} - -\paragraph{Time from server rendezvous to first client data (2.3.1.)} - -\subparagraph{Details} - -Relays report the time from receiving a \verb+RENDEZVOUS1+ cell to seeing -the first \verb+RELAY+ cell sent from the client. - -\subparagraph{Benefits} -The time from receiving a \verb+RENDEZVOUS1+ cell from the server (and -relaying it as \verb+RENDEZVOUS2+ cell to the client) and receiving the -first \verb+RELAY+ cell from the client is another performance indicator -of the protocol. -\subparagraph{Risks} - -There are no obvious risks from learning the time between these two -substeps in the rendezvous protocol. - -\paragraph{Amount of data sent over connected rendezvous circuits in -either direction (2.3.2.)} - -\subparagraph{Details} +\subsubsection{Number of cells sent over rendezvous circuits in either +direction (2.3.2.)} +\textbf{Details:} +% Relays report the number of \verb+RELAY+ cells sent in either direction. - -\subparagraph{Benefits} - +% +\textbf{Benefits:} +% The number of \verb+RELAY+ cells sent by either client or server can give us a detailed view on hidden service usage. In contrast to common Tor usage, there is no point in the rendezvous @@ -667,9 +818,9 @@ peer-to-peer models. As a special case, we'd want to know what fraction of circuits has zero \verb+RELAY+ cells, which would indicate a connection problem late in the process. - -\subparagraph{Risks} - +% +\textbf{Risks:} +% In contrast to the cells discussed above, \verb+RELAY+ cells contain actual user content. The pattern of \verb+RELAY+ cells could also be used to fingerprint a @@ -678,15 +829,16 @@ While total number of cells by direction aggregated over a certain time period should be okay to measure, any statistics going further than that need closer analysis. -\paragraph{Time from first client data to tearing down circuit (2.3.3.)} - -\subparagraph{Details} +\subsubsection{Time from first client data to tearing down circuit +(2.3.3.)} +\textbf{Details:} +% Relays report the time from seeing the first \verb+RELAY+ cell sent by the client to tearing down circuit by either client or server. - -\subparagraph{Benefits} - +% +\textbf{Benefits:} +% The time between receiving the first \verb+RELAY+ cell to tearing down the circuit indicates typical session length of hidden service connections. We'd be able to say whether typical hidden-service connections are rather @@ -694,9 +846,9 @@ short-lived or long-lived. This information may help us make educated guesses on the type of applications run over hidden services. It may also help us improve the selection criteria for rendezvous points. - -\subparagraph{Risks} - +% +\textbf{Risks:} +% Session length is quite sensitive data that could be correlated with circuit lifetimes at other places in the network. Fortunately, the rendezvous point is neither specific to any given client @@ -711,203 +863,152 @@ Still, this metric needs further analysis. % How much time did it take to splice the RP circuit? (#13194) (you mean % time from RENDEZVOUS1 to first RELAY cell?) -\subsection{Statistics from relays acting as hidden-service directories} - -% HSDirs threat model notes -Hidden Service directories periodically receive HS descriptors from hidden -services. -They cache them, and then serve them to any clients that ask for them. - -Hidden service directories are placed in a hash ring, and each hidden -service picks a slice of hidden service directories from that hash ring. -Given the address of a hidden service, it's easy to learn which -directories are responsible for it. -This makes hidden-service directory statistics dangerous since they can -potentially be matched to specific hidden services. - -Furthermore, each hidden service has 6 directories, and each directory -serves a different set of services. -This means that attackers have 6 different data points per hidden service -every hour that can be used to reduce measurement noise. - -The following statistics are grouped by (1) hidden services publishing -descriptors and (2) clients fetching descriptors from hidden-service -directories. - -\subsubsection{Statistics on hidden services publishing descriptors to -hidden-service directories} - -\paragraph{Number of cached descriptors (3.1.1.)} - -\subparagraph{Details} - -Relays keep a local count of cached hidden-service descriptors. -Every time they add or remove a descriptor to their cache, relays update -their counter and record the time of change. -At the end of the statistics period they calculate statistics like -minimum, maximum, average number of hosted descriptors during the -statistics interval. -(There may be more efficient ways to implement these statistics that avoid -keeping a full history with timestamps, which are not discussed here.) - -\subparagraph{Benefits} +\subsubsection{Number of closed rendezvous circuits without a single data +cells} -This is an interesting statistic that would allow us to understand how -used hidden services are, and also detect sudden changes in the number of -services (botnets, chat protocols, etc.). -Also, learning the number of hidden services per directory will help us -find bugs in the hash ring code and also understand how loaded directories -are. -FWIW, when \verb+rend-spec-ng.txt+ gets implemented, it will be harder for -hidden service directories to learn the number of served services since -the descriptor will be encrypted. -However, directories will still be able to approximate the number of -services by checking the amount of descriptors received per publishing -period. -If this ever becomes a problem we can imagine publishing fake descriptors -to confuse the directories. - -\subparagraph{Risks} - -Publishing this stat would allow someone who is indexing hidden services -to be able to say ``I have seen 76~\% of all HSes''. -We would really like to avoid having such an enumeration-facilitating -property. -We could be persuaded that with some heavy stats obfuscation (heavier than -the bridge stats obfuscation), this statistic might be plausible. -By statistics obfuscation, we mean obfuscating the numbers so that the -attacker can only say ``I'm somewhere between 60~\% to 75~\% of all -HSes.''. -This is a bit related to differential privacy as we understand it, but -much more basic. - -\paragraph{Number of descriptor updates per service (3.1.2.)} - -\subparagraph{Details} - -Relays count how many descriptor updates they see per service. -Assuming that stats are published daily (which is not necessary), this is -going to be a number between 1 and 24 (since RendPostPeriod is currently -one hour) and services pick a new directory after 24 hours (see -\verb+rendcommon.c:get_time_period()+). - -\subparagraph{Risks} - -Depending on how many HSes are behind each HSDir, this statistic might or -might not reveal uptime information about specific services. -Still it doesn't seem like something we want to risk. -Also, if the result is greater than 24, it means that an HS with modded -RendPostPeriod was publishing to that HSDir (and that the HSDir doesn't -have many clients). -Do we want to reveal that? -OTOH, it seems to me that if the directory is serving many services, this -statistic doesn't really provide any insight. - -\paragraph{Size of hidden service descriptors (3.1.3.)} - -\subparagraph{Details} - -Relays report the total/average size of received hidden service -descriptors. - -\subparagraph{Benefits} - -These statistics are not very helpful if reported by directories that -serve many services. -Any bugs or irregularities of one service will be smoothed out by all the -other services. -Basically, the only thing we would learn is approximately how much disk -space descriptors take, and maybe the average number of contained -introduction points (if we also know the number of services). -This statistic seems not very useful. - -\paragraph{Number of introduction points contained in descriptors -(3.1.4.)} - -\subparagraph{Details} +\textbf{Details:} +% +Relays report the number of rendezvous circuits that have been closed +before client or service sent a single data cell. -Relays report average number of introduction points contained in -hidden-service descriptors, possibly also percentiles. +\subsection{Performance-related statistics} -\subparagraph{Benefits} +\subsubsection{Time from establishing introduction point to receiving +first client introduction (1.2.4.)} -It would be interesting to know whether services deviate from the default -number of introduction points. -Though it's unclear what we're going to do with this information. -This statistic will also be killed by rend-spec-ng. +\textbf{Details:} +% +Relays report the time between \verb+ESTABLISH_INTRO+ and first +\verb+INTRODUCE1+ cell. +% +\textbf{Benefits:} +% +This statistic tells us how long it takes for the hidden service to +include a relay in its descriptor and publish that descriptor, and for the +first client to fetch that descriptor and use that relay for its +introduction. +This may not be very useful, but is listed here for completeness. +% [dgoulet]: That would basically leak the RendPostPeriod (if IP changes +% at each upload) of the HS. Not sure how an attacker could use that to +% his/her advantage but to consider. +% [karsten]: again, I think you're wrong about introduction points +% changing at each upload. +% [dgoulet]: Yup, IP do *NOT* change at each upload. +% +\textbf{Risks:} +% +No obvious risks. -\paragraph{Number of descriptors with encrypted introduction points -(3.1.5.)} +\subsubsection{Time from establishing a rendezvous point to receiving the +server rendezvous (2.2.2.)} -\subparagraph{Details} +\textbf{Details:} +% +Relays report the time from receiving an \verb+ESTABLISH_RENDEZVOUS+ cell +to receiving the corresponding \verb+RENDEZVOUS1+ cell. +% +\textbf{Benefits:} +% +The time between receiving an \verb+ESTABLISH_RENDEZVOUS+ cell from the +client and the corresponding \verb+RENDEZVOUS1+ cell from the server tells +us a lot about performance of the rendezvous protocol. +The rendezvous point is the only place in the protocol that witnesses +events near the beginning and near the end of the connection establishment +process. +If we ever want to improve the substeps inbetween, this metric is the only +way to measure effectiveness of improvements in the deployed network. +% +\textbf{Risks:} +% +Again, there are at least no obvious risks from gathering this statistic. -Relays can look at published hidden-service descriptor and count -descriptors with plain-text vs. encrypted introduction point sections. +\subsubsection{Time from server rendezvous to first client data (2.3.1.)} -\subparagraph{Benefits} +\textbf{Details:} +% +Relays report the time from receiving a \verb+RENDEZVOUS1+ cell to seeing +the first \verb+RELAY+ cell sent from the client. +% +\textbf{Benefits:} +The time from receiving a \verb+RENDEZVOUS1+ cell from the server (and +relaying it as \verb+RENDEZVOUS2+ cell to the client) and receiving the +first \verb+RELAY+ cell from the client is another performance indicator +of the protocol. +% +\textbf{Risks:} +% +There are no obvious risks from learning the time between these two +substeps in the rendezvous protocol. -We would learn what fraction of services uses authentication features. -This statistic won't be available after implementing rend-spec-ng. +\subsection{Failure statistics} -\paragraph{Number of descriptors published over circuits built with TAP -vs. nTor (3.1.6.)} +Should we report number and type of failures in the protocol, if these +statistics are not sufficient to actually debug a problem? +Could be a starting point to look at actual logs from relays. +But is this what statistics are for? -\subparagraph{Details} +\subsubsection{Number of failed attempts to establish an introduction +point (1.1.3.)} -Relays remember whether an incoming circuit was built using TAP or nTor. -Whenever they receive a descriptor publication request they increment a -counter for either TAP or nTor. -See ticket 13466 for details. +\textbf{Details:} +% +A relay can not decline to be an introduction point. +However, an \verb+ESTABLISH_INTRO+ cell might be malformed (wrong public +key, bad signature, etc...). +The relay would count the number of declined \verb+ESTABLISH_INTRO+ cells +and report them along with the total number of received +\verb+ESTABLISH_INTRO+ cells. +Or it would report successes and failures, rather than totals and +failures. +% +\textbf{Benefits:} +% +Wrong \verb+ESTABLISH_INTRO+ cells shows either a very bad bug in the code +or a deliberate action (data mangling, unknown attack, DoS, ...). +% +% [dgoulet]: After an IRC discussion with arma and asn, I remember that +% this one could be "cool to have" but without more information that we +% can't collect for privacy reasons, this stat would not help at all in +% the end game. The question remains if we should simply keep it or not +% even if right now we don't see a added value? +% [karsten:] right, this is a fine question, not only limited to this +% statistic. I added a new paragraph to the section start for "general +% considerations for gathering hidden-service statistics". +% +\textbf{Risks:} +% +No obvious risks. -\subparagraph{Benefits} +\subsubsection{Reasons for terminating established introduction points +(1.1.5.)} -We would learn what fraction of hidden services run older tor versions -(0.2.3.x or older). +\textbf{Details:} +% +Relays report frequencies of circuit terminations requested by services +vs. different types of failures. +% +\textbf{Benefits:} +% +If there are more than a small percentage of failures, decide how to make +things more robust. +% +\textbf{Risks:} +% +No obvious risks. -\paragraph{Number of descriptors published to the wrong directory +\subsubsection{Number of descriptors published to the wrong directory (3.1.7.)} -\subparagraph{Details} - +\textbf{Details:} +% A relay reports the number of published descriptors that it is not responsible for. -\subsubsection{Statistics on clients fetching descriptors from -hidden-service directories} - -\paragraph{Number of descriptor fetch requests (3.2.1.)} - -\subparagraph{Details} - -A relay reports the total number of descriptor fetch requests, regardless -of the requested hidden service identity. - -\subparagraph{Risks} - -An adversary can use this statistic to evaluate the popularity of an HS. -An adversary can also use this stat to detect big changes in the numbers -of visitors of popular HSes. -Of course, there will be noise in the statitics since multiple services -correspond to each directory, but the adversary could reduce the noise -after observing the same service rotating to different directories, and -also by examining the statistics of all 6 directories that correspond to -the service. -This doesn't seem like a problem that is solvable with simple obfuscation -of stats, and I suggest we don't do this statistic at all. - -\paragraph{Number of descriptor fetch requests by hidden service identity -(3.2.2.)} - -\subparagraph{Details} - -Relays report the distribution of descriptor fetch requests to hidden -service identities. - -\paragraph{Number of descriptor fetch requests for non-existent descriptor -(3.2.3.)} - -\subparagraph{Details} +\subsubsection{Number of descriptor fetch requests for non-existent +descriptor (3.2.3.)} +\textbf{Details:} +% Relays count the number of fetch requests for hidden service identities they don't have in their cache. We need to enumerate the reasons why a client would ask for the wrong @@ -916,109 +1017,77 @@ descriptor. For example: a) clock sync issues, b) different network view between, c) ``the hidden service hasn't published recently'', d) ``the hidden service is offline for months''. +% +\textbf{Benefits:} +% +This seems like a statistic that could potentially find bugs in Tor. +% +\textbf{Risks:} +% +This statistic could reveal things that we don't really understand and +might reveal information about specific services. -\subparagraph{Benefits} -This seems like a statistic that could potentially find bugs in Tor. -\subparagraph{Risks} +\subsubsection{Number of discarded client introductions by reason +(1.2.3.)} -This statistic could reveal things that we don't really understand and -might reveal information about specific services. +\textbf{Details:} +% +How many \verb+INTRODUCE1+ cells have been discarded because of unknown +service/malformed (?)/whatever-can-go-wrong, by introduction point? +% +\textbf{Benefits:} +% +Anything exceeding a small portion of discarded \verb+INTRODUCE1+ cells +shows either a very bad bug in the code or a deliberate action (data +mangling, unknown attack, DoS, ...). +% +% [dgoulet]: That is again a "cool to have" stat but not sure how it would +% help us investiguate. It can I guess trigger an alarm but apart from +% that... +% [karsten]: right, see section start. +% +\textbf{Risks:} +% +No obvious risks. +More precisely, if absolute numbers are reported, the risk is the same as +the risk of reporting the number of received \verb+INTRODUCE1+ cells; if +only fractions are reported, it's not that bad. +% +\subsubsection{Number of server rendezvous with unknown rendezvous cookie +(2.2.3.)} -\paragraph{Number of descriptors fetched over circuits built with TAP vs. -nTor (3.2.4.)} +\textbf{Details:} +% +Relays report the number of \verb+RENDEZVOUS1+ cell with unknown +rendezvous cookie. +% +\textbf{Benefits:} +% +The number of \verb+RENDEZVOUS1+ cell that cannot be matched with a +previously established rendezvous circuit can be interesting for analyzing +problems in the protocol. +We might even distinguish between rendezvous cookies that were previously +known to the relay and those that seem entirely unrelated. +The benefit gained from this statistic is not huge though. +% +\textbf{Risk:} +% +No obvious risks. -\subparagraph{Details} +\section{Recommendation} +\label{sec:recommendation} -Relays remember whether an incoming circuit was built using TAP or nTor. -Whenever they receive a descriptor fetch request they increment a counter -for either TAP or nTor. -See ticket 13466 for details. +\section*{Next steps in writing this report} -\subparagraph{Benefits} - -We would learn what fraction of hidden-service clients run older tor -versions (0.2.3.x or older). - -%- How many HSes is the HSDir hosting descriptors for? (harder to do with -%rend-spec-ng) (assuming that each HS desc is for one HS, this is already -%covered above.) -%- How many updates for the same HS desc did the HSDir see? (already covered -%above, it seems.) - -\section{Evaluation} - -Adding new statistics to something as sensitive as hidden services has two -sides: one side is the benefit from gathering data that can be used to -improve them, but the other side is potential harm to users. -The following table assigns points to both benefits and risks. -Each statistic can earn between 0 and 2 benefit points and between 0 and 2 -(negative) risk points. -The sum of both points provides us with a priority list from statistics -that make a lot of sense and don't pose much risk to statistics that are -mostly useless and at the same time very risky. - -\begin{longtable}{p{1cm}p{1cm}p{1cm}p{12cm}} -B & R & S \\ -$+$ & $0$ & $+$ & Number of attempts to establish an introduction point -(1.1.1.) \\ -$0$ & $0$ & $0$ & Time from establishing a circuit to becoming an -introduction point (1.1.2.) \\ -$+$ & $0$ & $+$ & Number of failed attempts to establish an introduction -point (1.1.3.) \\ -$+$ & $0$ & $+$ & Lifetime of introduction circuits (1.1.4.) \\ -$+$ & $0$ & $+$ & Reasons for terminating established introduction points -(1.1.5.) \\ -$+$ & $0$ & $+$ & Number of introduction circuits built with TAP vs. nTor -(1.1.6.) \\ -$+$ & $-$ & $0$ & Total number of introductions received from clients -(1.2.1.) \\ -$+$ & $-$ & $0$ & Number of introductions received by established -introduction point (1.2.2.) \\ -$+$ & $-$ & $0$ & Number of discarded client introductions by reason -(1.2.3.) \\ -$0$ & $0$ & $0$ & Time between establishing introduction point and receiving -the first client introduction (1.2.4.) \\ -$+$ & $0$ & $+$ & Number of client introductions coming in via circuits -built with TAP vs. nTor (1.2.5.) \\ -$+$ & $0$ & $+$ & Number of established rendezvous points (2.1.1.) \\ -$0$ & $0$ & $0$ & Time from circuit creation to establishing rendezvous -point (2.1.2.) \\ -$+$ & $0$ & $+$ & Number of rendezvous point establishment requests coming -in via circuits built with TAP vs. nTor (2.1.3.) \\ -$++$ & $0$ & $++$ & Number of server rendezvous (2.2.1.) \\ -$++$ & $0$ & $++$ & Time from establishing a rendezvous point to receiving the -server rendezvous (2.2.2.) \\ -$+$ & $0$ & $+$ & Number of server rendezvous with unknown rendezvous cookie -(2.2.3.) \\ -$+$ & $0$ & $+$ & Number of server rendezvous coming in via circuits built -with TAP vs. nTor (2.2.4.) \\ -$++$ & $0$ & $++$ & Time from server rendezvous to first client data (2.3.1.) -\\ -$++$ & $-$ & $+$ & Amount of data sent over connected rendezvous circuits in -either direction (2.3.2.) \\ -$+$ & $-$ & $0$ & Time from first client data to tearing down circuit -(2.3.3.) \\ -$++$ & $-$ & $+$ & Number of cached descriptors (3.1.1.) \\ -$+$ & $-$ & $0$ & Number of descriptor updates per service (3.1.2.) \\ -$0$ & $0$ & $0$ & Size of hidden service descriptors (3.1.3.) \\ -$+$ & $0$ & $+$ & Number of introduction points contained in descriptors -(3.1.4.) \\ -$+$ & $0$ & $+$ & Number of descriptors with encrypted introduction points -(3.1.5.) \\ -$+$ & $0$ & $+$ & Number of descriptors published over circuits built with -TAP vs. nTor (3.1.6.) \\ - & & & Number of descriptors published to the wrong directory -(3.1.7.) \\ -$+$ & $--$ & $-$ & Number of descriptor fetch requests (3.2.1.) \\ $+$ & -$--$ & $-$ & Number of descriptor fetch requests by hidden service identity -(3.2.2.) \\ -$+$ & $0$ & $+$ & Number of descriptor fetch requests for non-existent -descriptor (3.2.3.) \\ -$+$ & $0$ & $+$ & Number of descriptors fetched over circuits built with TAP -vs. nTor (3.2.4.) \\ -\end{longtable} +\begin{itemize} +\item Add results from private testing network to list of statistics. +\item Figure out which of the failure statistics actually make sense, by +looking at the code. +\item Decide how to evaluate helpfulness and harmfulness of statistics, in +an objective way, ideally using the stated evaluation criteria. +\end{itemize} \end{document} diff --git a/2015/hidden-service-stats/protocol.odg b/2015/hidden-service-stats/protocol.odg new file mode 100644 index 0000000..729c8eb Binary files /dev/null and b/2015/hidden-service-stats/protocol.odg differ diff --git a/2015/hidden-service-stats/protocol.pdf b/2015/hidden-service-stats/protocol.pdf new file mode 100644 index 0000000..352b4ef Binary files /dev/null and b/2015/hidden-service-stats/protocol.pdf differ

1 0

[tech-reports/master] Add a bit more content to the tech report.
by karsten＠torproject.org 17 Jun '15

17 Jun '15

commit 3f30d1c88cf13794f49f374dfdd6284847ed7779 Author: George Kadianakis <desnacked(a)riseup.net> Date: Fri Jan 9 13:24:44 2015 +0200 Add a bit more content to the tech report. - Another reason to worry about statistics. - A risk section --- 2015/hidden-service-stats/hidden-service-stats.tex | 39 +++++++++++++++----- 1 file changed, 29 insertions(+), 10 deletions(-) diff --git a/2015/hidden-service-stats/hidden-service-stats.tex b/2015/hidden-service-stats/hidden-service-stats.tex index 20e9dc9..d3ad6c4 100644 --- a/2015/hidden-service-stats/hidden-service-stats.tex +++ b/2015/hidden-service-stats/hidden-service-stats.tex @@ -302,6 +302,15 @@ to enumerate available services. While hiding the existence of a service is not the primary purpose of hidden services, it's a security feature we don't want to give up easily. +\paragraph{Unknown future attacks} + +Special care needs to be taken when designing and collecting +statistics because in anonymity the attacker landscape changes +continuously and attacks that are currently ineffective might become +powerful in the future. Alternatively, in the future attackers might +be able to acquire auxiliary data that can combine with statistics in +such ways that allow attacks that would not have been possible before. + \subsection{Other aspects of gathering statistics} There are certain aspects of any given statistic that should be @@ -491,6 +500,12 @@ See ticket 13466 for details. % We would learn what fraction of clients and what fraction of services run older tor versions (0.2.3.x or older). +\\ +\textbf{Risks:} +% +As tor-0.2.3.x gets less common and only a few hidden services still +use it, an adversary would be able to track their introduction points +by checking which relays still report TAP clients on their statistics. \subsubsection{Time from circuit purpose change to tearing down circuit} \label{subsubsec:time_circ_purpose_change_to_teardown} @@ -551,7 +566,7 @@ This statistic can also be used to analyze what fraction of services is available for a short time only, and what fraction is available most of the time. -\subsubsection{Number of descriptor publish request (3.1.1.)} +\subsubsection{Number of hidden service descriptors seen by directory (3.1.1.)} \label{subsubsec:num_descriptor_publish} \textbf{Details:} @@ -573,14 +588,6 @@ services (botnets, chat protocols, etc.). Also, learning the number of hidden services per directory will help us find bugs in the hash ring code and also understand how loaded directories are. -FWIW, when \verb+rend-spec-ng.txt+ gets implemented, it will be harder for -hidden service directories to learn the number of served services since -the descriptor will be encrypted. -However, directories will still be able to approximate the number of -services by checking the amount of descriptors received per publishing -period. -If this ever becomes a problem we can imagine publishing fake descriptors -to confuse the directories. \\ \textbf{Risks:} % @@ -602,6 +609,17 @@ are published during certain times of day and certain days of the week, which could correlate with daylight hours and/or working days in certain parts of the world. This information could also be correlated with network outages over time to narrow down the location of hidden services. +\\ +\textbf{Notes:} +% +When \verb+rend-spec-ng.txt+ gets implemented, it will be harder for +hidden service directories to learn the number of served services +since the descriptor will be encrypted. +However, directories will still be able to approximate the number of +services by checking the amount of descriptors received per publishing +period. +If this ever becomes a problem we can imagine publishing fake +descriptors \subsubsection{Number of descriptor updates per service (3.1.2.)} \label{subsubsec:num_decriptor_updates} @@ -1555,4 +1573,5 @@ an objective way, ideally using the stated evaluation criteria. \end{itemize} \bibliography{hidden-service-stats} -\end{document} \ No newline at end of file +\end{document} +

1 0

[tech-reports/master] describing how to publish data about distributions
by karsten＠torproject.org 17 Jun '15

17 Jun '15

commit 351b64d35dec5df7691db4596f995cf63e433fc3 Author: A. Johnson <aaron.m.johnson(a)nrl.navy.mil> Date: Sat Dec 27 18:44:13 2014 -0500 describing how to publish data about distributions --- 2015/hidden-service-stats/Makefile | 18 +++ 2015/hidden-service-stats/hidden-service-stats.bib | 7 + 2015/hidden-service-stats/hidden-service-stats.tex | 157 ++++++++++++++++---- 3 files changed, 156 insertions(+), 26 deletions(-) diff --git a/2015/hidden-service-stats/Makefile b/2015/hidden-service-stats/Makefile new file mode 100644 index 0000000..83a4dfd --- /dev/null +++ b/2015/hidden-service-stats/Makefile @@ -0,0 +1,18 @@ +.PHONY : main + +MAIN=hidden-service-stats +LATEX=pdflatex + +all: paper tidy + +paper: $(MAIN).tex + $(LATEX) $(MAIN) + bibtex $(MAIN) + $(LATEX) $(MAIN) + $(LATEX) $(MAIN) + +tidy: + rm -f *.dvi *.aux *.log *.nav *.snm *.toc *.out *.vrb *.bbl *.blg + +clean: + rm -f *.dvi *.aux *.log *.nav *.snm *.toc *.out *.vrb *.bbl *.blg $(MAIN).ps $(MAIN).pdf diff --git a/2015/hidden-service-stats/hidden-service-stats.bib b/2015/hidden-service-stats/hidden-service-stats.bib new file mode 100644 index 0000000..52daad5 --- /dev/null +++ b/2015/hidden-service-stats/hidden-service-stats.bib @@ -0,0 +1,7 @@ +@inproceedings{dwork-tcc2006, + author = {Dwork, Cynthia and McSherry, Frank and Nissim, Kobbi and Smith, Adam}, + title = {Calibrating Noise to Sensitivity in Private Data Analysis}, + booktitle = {Proceedings of the Third Conference on Theory of Cryptography}, + series = {TCC'06}, + year = {2006} +} \ No newline at end of file diff --git a/2015/hidden-service-stats/hidden-service-stats.tex b/2015/hidden-service-stats/hidden-service-stats.tex index d4b586e..1400268 100644 --- a/2015/hidden-service-stats/hidden-service-stats.tex +++ b/2015/hidden-service-stats/hidden-service-stats.tex @@ -3,6 +3,7 @@ \usepackage{graphicx} \usepackage{hyperref} \usepackage{longtable} +\usepackage{paralist} \begin{document} @@ -617,6 +618,7 @@ statistic doesn't really provide any insight. \subsubsection{Time between last and first published descriptor with same identifier} +\label{subsubsec:time_first_last_descriptor_update} \textbf{Details:} % @@ -629,7 +631,7 @@ There is an upper bound on this statistic at 24 hours, because that's when descriptor identifiers change. \subsubsection{Number of introduction points contained in descriptors -(3.1.4.)} +(3.1.4.)} \label{subsubsec:num_ips_in_descriptors} \textbf{Details:} % @@ -683,7 +685,7 @@ This doesn't seem like a problem that is solvable with simple obfuscation of stats, and I suggest we don't do this statistic at all. \subsubsection{Number of descriptor fetch requests by service identity -(3.2.2.)} +(3.2.2.)} \label{subsubsec:num_descriptor_fetches_per_hs} \textbf{Details:} % @@ -752,7 +754,7 @@ requests a very popular hidden service gets. % [dgoulet]: No they don't, I confirmed in the code. \subsubsection{Number of introductions received by established -introduction point (1.2.2.)} +introduction point (1.2.2.)} \label{subsubsec:num_intros_per_circ} \textbf{Details:} % @@ -804,7 +806,7 @@ given client or server. \subsubsection{Number of cells sent over rendezvous circuits in either -direction (2.3.2.)} +direction (2.3.2.)} \label{subsubsection:num_cells_rend_circ} \textbf{Details:} % @@ -835,7 +837,7 @@ period should be okay to measure, any statistics going further than that need closer analysis. \subsubsection{Time from first client data to tearing down circuit -(2.3.3.)} +(2.3.3.)} \label{subsubsec:time_client_data_to_teardown} \textbf{Details:} % @@ -880,6 +882,7 @@ before client or service sent a single data cell. \subsubsection{Time from establishing introduction point to receiving first client introduction (1.2.4.)} +\label{subsubsec:time_ip_est_to_introduce1} \textbf{Details:} % @@ -905,7 +908,7 @@ This may not be very useful, but is listed here for completeness. No obvious risks. \subsubsection{Time from establishing a rendezvous point to receiving the -server rendezvous (2.2.2.)} +server rendezvous (2.2.2.)} \label{subsubsec:time_rp_to_rend1} \textbf{Details:} % @@ -928,6 +931,7 @@ way to measure effectiveness of improvements in the deployed network. Again, there are at least no obvious risks from gathering this statistic. \subsubsection{Time from server rendezvous to first client data (2.3.1.)} +\label{subsubsec:time_rend1_to_data} \textbf{Details:} % @@ -1010,7 +1014,7 @@ A relay reports the number of published descriptors that it is not responsible for. \subsubsection{Number of descriptor fetch requests for non-existent -descriptor (3.2.3.)} +descriptor (3.2.3.)} \label{subsubsec:num_fetch_nonexistent} \textbf{Details:} % @@ -1081,13 +1085,13 @@ The benefit gained from this statistic is not huge though. % No obvious risks. -\section{Obfuscation methodology} +\section{Obfuscation methodology} \label{sec:obfuscation} The published statistics shouldn't reveal private information to an adversary when combined with plausible background knowledge. We will use techniques to provide uncertainty about any specific hidden service, client, or connection, while maintaining good accuracy in the aggregate statistics. These techniques include -\begin{itemize} +\begin{compactitem} \item Releasing aggregate statistics over time, such as total counts or averages in a given period \item Adding noise (i.e. random inaccuracy) @@ -1097,12 +1101,25 @@ averages in a given period doesn't reveal information about ongoing activity \item Using cryptographic techniques to hide the source of information, such as anonymizing reports from individual relays -\end{itemize} +\end{compactitem} + +We will be adding noise in a way that provides differential +privacy~\cite{dwork-tcc2006} for +``single'' actions. What constitutes a single action will depend on the +specific statistic. For example, when publishing the number of unique +descriptors seen at each HSDir, a single action could be publishing a +descriptor to +six relays. To obtain differential privacy, we will add noise using the +Laplace distribution, which has a distribution function of +$\textrm{Lap}(b) = e^{-|x|/b}/(2b)$. We will choose $b$ such that +altering a single action will change the probability of the total output +by a factor of at most $e^{\epsilon}$. Thus more privacy is provided the +smaller that $\epsilon$ is. \subsection{Adversary knowledge} We can expect that the adversary may know things such as -\begin{itemize} +\begin{compactitem} \item The addresses of a large number of publicly-available services (e.g. by crawling the Web) \item A minimum amount of traffic received by a given hidden service @@ -1112,7 +1129,7 @@ We can expect that the adversary may know things such as periodically) \item Roughly the number of client connections and amount of client traffic (possibly leaked by the service itself, e.g. a web forum) -\end{itemize} +\end{compactitem} \subsection{Counts} @@ -1121,18 +1138,106 @@ For many statistics, it would be very helpful to understand the distribution of values. For example, such information about descriptor fetches could reveal if most hidden services are never used or if there are a few hidden services that constitute most HS activity. -Releasing information about the distribution of statistics could be useful -for the following statistics: -\begin{itemize} -\item Time from circuit extension to circuit purpose change -(Sec.~\ref{subsubsec:time_circ_ext_to_purpose_change}) -\item Time from circuit purpose change to tearing down circuit -(Sec.~\ref{subsubsec:time_circ_purpose_change_to_teardown} -\item Time from establishing introduction point to tearing down -circuit (Sec.~\ref{subsubsec:time_intro_to_teardown}) -\item Number of descriptor updates per service -(Sec.~\ref{subsubsec:num_decriptor_updates}) -\end{itemize} +Table~\ref{table:dist_stats} lists the statistics for which it could +be useful to release information about a distribution. +\begin{table} +\caption{Statistics with interesting distributions} +\label{table:dist_stats} +\begin{tabular}{|l|l|} +\hline +\textbf{Description} & \textbf{Section}\\ +\hline +Time from circuit extension to circuit purpose change & +\ref{subsubsec:time_circ_ext_to_purpose_change}\\ +\hline +Time from circuit purpose change to tearing down circuit & +\ref{subsubsec:time_circ_purpose_change_to_teardown}\\ +\hline +Time from establishing introduction point to tearing down circuit & +\ref{subsubsec:time_intro_to_teardown}\\ +\hline +Number of descriptor updates per service & +\ref{subsubsec:num_decriptor_updates}\\ +\hline +Time between last and first published descriptor with same identifier & +\ref{subsubsec:time_first_last_descriptor_update}\\ +\hline +Number of introduction points contained in descriptors & +\ref{subsubsec:num_ips_in_descriptors}\\ +\hline +Number of descriptor fetch requests by service identity & +\ref{subsubsec:num_descriptor_fetches_per_hs}\\ +\hline +Number of introductions received by established introduction point & +\ref{subsubsec:num_intros_per_circ}\\ +\hline +Number of cells sent over rendezvous circuits in either direction & +\ref{subsubsection:num_cells_rend_circ}\\ +\hline +Time from first client data to tearing down circuit & +\ref{subsubsec:time_client_data_to_teardown}\\ +\hline +Time from establishing introduction point to receiving first client +introduction & \ref{subsubsec:time_ip_est_to_introduce1}\\ +\hline +Time from establishing a rendezvous point to receiving the +server rendezvous & \ref{subsubsec:time_rp_to_rend1}\\ +\hline Time from server rendezvous to first client data & +\ref{subsubsec:time_rend1_to_data}\\ +\hline +Number of descriptor fetch requests for non-existent descriptor & +\ref{subsubsec:num_fetch_nonexistent}\\ +\hline +\end{tabular} +\end{table} + +Following are several potential ways to publish information about a +distribution: +\begin{compactitem} +\item Publish a histogram of possible values (e.g. the number of values in +$[0,1]$, $[1,10]$, $[10, 100]$, and $[100, \infty)$). +\item Publish a subset of percentile values (e.g. quartiles). +\item Publish standard summary statistics, (e.g. mean, variance, +skew, and kurtosis). +\end{compactitem} +To protect individual privacy when releasing these kinds of data, +we would again like to protect activity over time and also provide +particularly-strong protection for a ``single'' activity. This is quite +straightforward to do for publishing +histograms, simply by applying the techniques that we developed for counts +to each +count in the histogram. Thus we suggest using histograms in this way to +report distribution data, as follows: +\begin{compactenum} +\item Choose a finite number of \emph{buckets} that cover the possible +values of the statistic (we use the term ``buckets'' to distinguish +these from bins that will limit the granularity of each bucket). Each +extra bucket will result in a certain additional amount of noise being +added, but including more values in a bucket (i.e. increasing its width) +reduces its accuracy. Therefore, these should be balanced while also +choosing buckets that capture the most useful distinctions +for the statistic under consideration (e.g. deciding between relative and +absolute accuracy). +\item For each bucket, the count of values in that bucket should be +rounded to a chosen granularity $\delta$ (e.g. to the nearest multiple of +10). For simplicity, it is recommended that bins are not split over +multiple buckets (e.g. there should not be buckets for values 0 and 1 if +bin granularity is at least 2). A rounded value is used because over time +the effects of fresh noise can be factored out (e.g. by taking the mean +of a sequence of published values if the statistic stays the same over +that time). +\item Fresh Laplace noise with distribution +$\textrm{Lap}(2\delta/\epsilon)$ should be added to the center of the bin +of each bucket, where $\epsilon$ is the privacy parameter discussed at the +beginning of Sec.~\ref{sec:obfuscation}. $\delta$ appears in $b$ because +a single input to the histogram could cause the bucket center to change +by at most $\delta$ (e.g. if the rounding threshold is just crossed). +The value $2$ appears in $b$ because modifying a single entry in the +histogram can change two values: the value of the bucket it was changed +from and the value of the bucket it was changed to. +\item The noisy bin center of each bucket is published. +\end{compactenum} + \section{Recommendation} \label{sec:recommendation} @@ -1147,5 +1252,5 @@ looking at the code. an objective way, ideally using the stated evaluation criteria. \end{itemize} -\end{document} - +\bibliography{hidden-service-stats} +\end{document} \ No newline at end of file

1 0

[tech-reports/master] adding benefits and risks to stats in 4.2 and 4.3, other minor edits
by karsten＠torproject.org 17 Jun '15

17 Jun '15

commit 56ddf59a769c803b4d08e78da37b7ae7b3e2a146 Author: A. Johnson <aaron.m.johnson(a)nrl.navy.mil> Date: Thu Jan 1 14:20:12 2015 -0500 adding benefits and risks to stats in 4.2 and 4.3, other minor edits --- 2015/hidden-service-stats/hidden-service-stats.tex | 219 +++++++++++++------- 1 file changed, 145 insertions(+), 74 deletions(-) diff --git a/2015/hidden-service-stats/hidden-service-stats.tex b/2015/hidden-service-stats/hidden-service-stats.tex index 9aeb64c..20e9dc9 100644 --- a/2015/hidden-service-stats/hidden-service-stats.tex +++ b/2015/hidden-service-stats/hidden-service-stats.tex @@ -291,7 +291,8 @@ we want to avoid that statistics can be used to single out a specific client and learn about its activity. This includes power users that access lots of services or transfer large data volumes as well as clients which are services themselves, like -tor2web. +tor2web. It also includes the fact that a given user under direct +observation is using hidden services at all. \paragraph{Assess precise number of available services} @@ -424,7 +425,7 @@ the introduction point. % Risks: Also tricky. That info could tell us clearly if the IP circuit is % on a new or already established circuit which changes the traffic % timing. Not sure how useful it is to an attacker though. -% +\\ \textbf{Benefits:} % We would learn what fraction of introduction points can be established on @@ -452,7 +453,7 @@ But if we ever decide to re-use existing circuits for rendezvous without extending them by another hop, this metric will give us an idea on the adoption of that change. Admitted, this benefit is not huge. -% +\\ \textbf{Risks:} % No obvious risks. % only talking about aggregate statistics here, not @@ -485,7 +486,7 @@ More precisely, relays would remember for each circuit how it was built, and as soon as they receive an \verb+ESTABLISH_INTRO+ cell, they increment one of two counters. See ticket 13466 for details. -% +\\ \textbf{Benefits:} % We would learn what fraction of clients and what fraction of services run @@ -517,18 +518,18 @@ later section. % A relay counts how many \verb+ESTABLISH_INTRO+ cells it receives and acts upon during the statistics interval. -% +\\ \textbf{Benefits:} % We could validate that we have a ``uniform'' random distribution among chosen introduction points in the network. -If not, there might be a problem. -% +If not, there might be a problem. This could also be used to count the +number of introduction points actually being used by hidden services, +which could reveal errors or non-standard usage. +\\ \textbf{Risks:} -Considering we have a good randomness meaning every relay has the same -chance to be picked, there are no obvious risks to share this. -If not, we don't see a real risk for an attacker to know that a specific -relay got chosen X times instead of the measured average Y. +This could reveal the introduction points of hidden services with +encrypted descriptors. \subsubsection{Time from establishing introduction point to tearing down circuit (1.1.4.)} @@ -539,7 +540,7 @@ circuit (1.1.4.)} How long did an introduction circuit last? Relays would report statistics like mean/median time, variance/IQR, and/or percentiles here. -% +\\ \textbf{Benefits:} % The longer introduction circuits last, the better, from a performance POV. @@ -563,7 +564,7 @@ minimum, maximum, average number of hosted descriptors during the statistics interval. (There may be more efficient ways to implement these statistics that avoid keeping a full history with timestamps, which are not discussed here.) -% +\\ \textbf{Benefits:} % This is an interesting statistic that would allow us to understand how @@ -580,7 +581,7 @@ services by checking the amount of descriptors received per publishing period. If this ever becomes a problem we can imagine publishing fake descriptors to confuse the directories. -% +\\ \textbf{Risks:} % Publishing this stat would allow someone who is indexing hidden services @@ -595,6 +596,13 @@ HSes.''. This is a bit related to differential privacy as we understand it, but much more basic. +Another risk is that changes in the number of HSes could reveal patterns +in the services over time. For example, it could reveal some services that +are published during certain times of day and certain days of the week, +which could correlate with daylight hours and/or working days in certain +parts of the world. This information could also be correlated with +network outages over time to narrow down the location of hidden services. + \subsubsection{Number of descriptor updates per service (3.1.2.)} \label{subsubsec:num_decriptor_updates} @@ -605,7 +613,13 @@ Assuming that stats are published daily (which is not necessary), this is going to be a number between 1 and 24 (since RendPostPeriod is currently one hour) and services pick a new directory after 24 hours (see \verb+rendcommon.c:get_time_period()+). -% +\\ +\textbf{Benefits:} +This could reveal overall HS descriptor stability, which reflects +the frequency of events causing descriptor updates, such as changing +IPs or changing authentication keys. Also, this could reveal client errors +or DoS attacks on HSDirs. +\\ \textbf{Risks:} % Depending on how many HSes are behind each HSDir, this statistic might or @@ -616,7 +630,11 @@ RendPostPeriod was publishing to that HSDir (and that the HSDir doesn't have many clients). Do we want to reveal that? OTOH, it seems to me that if the directory is serving many services, this -statistic doesn't really provide any insight. +statistic doesn't really provide any insight. In addition, this could +be used to reveal the introduction points used by a hidden service +(assuming its address is known, but its descriptors are encrypted) by +DOSing suspected IPs and observing in the responsible HSDirs report +a higher number of descriptor updates. \subsubsection{Time between last and first published descriptor with same identifier} @@ -639,7 +657,7 @@ descriptor identifiers change. % Relays report average number of introduction points contained in hidden-service descriptors, possibly also percentiles. -% +\\ \textbf{Benefits:} % It would be interesting to know whether services deviate from the default @@ -654,7 +672,7 @@ This statistic will also be killed by rend-spec-ng. % Relays can look at published hidden-service descriptor and count descriptors with plain-text vs. encrypted introduction point sections. -% +\\ \textbf{Benefits:} % We would learn what fraction of services uses authentication features. @@ -673,19 +691,24 @@ later time. % A relay reports the total number of descriptor fetch requests, regardless of the requested hidden service identity. -% +\\ +\textbf{Benefits:} +This statistics would be an indication of the amount of client HS +activity. It would complement the statistics counting rendezvous data +cells by indicating the number of ``initial'' connections rather +than the amount of data, which should be a better estimate of the +number of unique user-service pairs. +\\ \textbf{Risks:} % -An adversary can use this statistic to evaluate the popularity of an HS. -An adversary can also use this stat to detect big changes in the numbers -of visitors of popular HSes. -Of course, there will be noise in the statitics since multiple services -correspond to each directory, but the adversary could reduce the noise -after observing the same service rotating to different directories, and -also by examining the statistics of all 6 directories that correspond to -the service. -This doesn't seem like a problem that is solvable with simple obfuscation -of stats, and I suggest we don't do this statistic at all. +An adversary could use this statistic to evaluate the popularity of a +known HS because the HSes set of HSDirs would likely be unique and also +known. The adversary could remove from the reported counts the fetches +for other HSes sharing the individual HSDirs by identifying by how much +the counts of a given HSDir tend to change during the periods for which +the target HS is assigned to them. +This is a major problem that doesn't seem resolvable without some kind +of anonymization or private aggregation of the per-relay stats. \subsubsection{Number of descriptor fetch requests by service identity (3.2.2.)} \label{subsubsec:num_descriptor_fetches_per_hs} @@ -694,6 +717,22 @@ of stats, and I suggest we don't do this statistic at all. % Relays report the distribution of descriptor fetch requests to hidden service identities. +% +\textbf{Benefits:} +This statistic would have the same benefits +as~\ref{subsubsec:num_desc_fetches}, as well as being informative +about HS usage. For example, it could reveal if there are many +moderately-popular HSes or just a few very popular ones. +\\ +\textbf{Risks:} +This statistic would have the same risk +as~\ref{subsubsec:num_desc_fetches}, as well as potentially +making it even easier to reveal per-HS popularity. For example, +if the statistic reported the maximum number of fetches over all +HSes, and it was already clear which HS was the most popular, +then this statistic could give that adversary an exact measure +of popularity. +% \subsubsection{Number of established rendezvous points (2.1.1.)} \label{subsubsec:num_rps} @@ -701,7 +740,7 @@ service identities. \textbf{Details:} % Relays report how many \verb+ESTABLISH_RENDEZVOUS+ cells they received. -% +\\ \textbf{Benefits:} % The number of received \verb+ESTABLISH_RENDEZVOUS+ cells indicates how @@ -714,7 +753,7 @@ connection, and which we may not even gather because of privacy concerns. We can easily weight the number of \verb+ESTABLISH_RENDEZVOUS+ cells with the probability of choosing a relay as rendezvous point to estimate the total number of such cells in the network. -% +\\ \textbf{Risk:} % There is no obvious risk from sharing this number if aggregated over a @@ -724,25 +763,25 @@ large enough time period. \label{subsubsec:num_intros_from_clients} \textbf{Details:} -% Relays report how many \verb+INTRODUCE1+ cells they received from clients. -% +\\ \textbf{Benefits:} -% This indicates that there is in fact a client trying to reach a hidden service thus the amount of cells could give us a rough estimate of how many clients are actually connecting and using hidden services. -% +\\ \textbf{Risks:} -% -Unclear. -On the one hand, this is basically the same risk as the amount of time a -relay is picked as an introduction point. -On the other hand, an adversary could fetch a hidden-service descriptor, -learn that a particular relay was an introduction point for that service, -and then see the relay receive many \verb+INTRODUCE1+ cells. -Basically, this statistic could be used to learn how many connection -requests a very popular hidden service gets. +An adversary could use this statistic to learn the number of attempted +connections to a known HS. To do this, the adversary would fetch a +descriptor for the HS, learn the introduction poins for the HS, +and then observe how many \verb+INTRODUCE1+ cells were received by +those relays. To remove connections due to other HSes sharing the same +IP, the adversary could observe the counts over the (almost certainly +unique) set of IPs and identify how these counts differ from other +relays not used by the target HS and from the same relays in periods +for which they don't serve as IPs for the target HS. +This statistic may require anonymization or private aggregation techniques +to avoid this problem. % [dgoulet]: I think, after discussing it with Nick, that this might be OK % if the relay reports this stat for a lot of HS meaning the relay has at @@ -767,7 +806,7 @@ Relays can serve as introduction point for an arbitrary number of hidden services. Relays could report statistics (like percentiles) on received \verb+INTRODUCE1+ cell by introduction circuit. -% +\\ \textbf{Benefits:} % This statistic would tell us something about usage diversity of hidden @@ -775,6 +814,12 @@ services. A special case would be the number or fraction of established introduction points that never sees a single \verb+INTRODUCE1+ cell. It's unclear what we'd do with this information, though. +\\ +\textbf{Risks:} +This shares the same risks as \ref{subsubsec:num_intros_from_clients} but +potentially makes it even easier to differentiate introductions due to +different HSes with the same IP. +% \subsubsection{Number of server rendezvous (2.2.1.)} \label{subsubsec:num_server_rendezvous} @@ -782,7 +827,7 @@ It's unclear what we'd do with this information, though. \textbf{Details:} % Relays report the total number of \verb+RENDEZVOUS1+ cells they receive. -% +\\ \textbf{Benefits:} % The number of received \verb+RENDEZVOUS1+ cells tells us how many @@ -790,7 +835,7 @@ connection requests are actually accepted by servers. This number may be lower than the number of \verb+ESTABLISH_RENDEZVOUS+ cells, because of failures in connection establishment, authentication failures, or other reasons. -% +\\ \textbf{Risks:} % There is no obvious risk from this metric, because it's unrelated to any @@ -817,7 +862,7 @@ direction (2.3.2.)} \label{subsubsection:num_cells_rend_circ} \textbf{Details:} % Relays report the number of \verb+RELAY+ cells sent in either direction. -% +\\ \textbf{Benefits:} % The number of \verb+RELAY+ cells sent by either client or server can give @@ -831,13 +876,20 @@ peer-to-peer models. As a special case, we'd want to know what fraction of circuits has zero \verb+RELAY+ cells, which would indicate a connection problem late in the process. -% +\\ \textbf{Risks:} % In contrast to the cells discussed above, \verb+RELAY+ cells contain actual user content. The pattern of \verb+RELAY+ cells could also be used to fingerprint a -given server or even client. +given server or even client. Even more simply, this statistic could +reveal the mere existence of an HS connection, especially a large one, +which the adversary might otherwise not be aware of. This could combine +badly with background knowledge such as the following: the adversary +observes at the user's ISP a certain large amount of traffic from a user +that he suspects might be hidden-service traffic. If he observes an +increase in this statistic by about the same amount, he can infer that +the user was indeed using hidden services. While total number of cells by direction aggregated over a certain time period should be okay to measure, any statistics going further than that need closer analysis. @@ -849,7 +901,7 @@ need closer analysis. % Relays report the time from seeing the first \verb+RELAY+ cell sent by the client to tearing down circuit by either client or server. -% +\\ \textbf{Benefits:} % The time between receiving the first \verb+RELAY+ cell to tearing down the @@ -859,14 +911,19 @@ short-lived or long-lived. This information may help us make educated guesses on the type of applications run over hidden services. It may also help us improve the selection criteria for rendezvous points. -% +\\ \textbf{Risks:} % Session length is quite sensitive data that could be correlated with circuit lifetimes at other places in the network. Fortunately, the rendezvous point is neither specific to any given client or service, which makes this information slightly less sensitive. -Still, this metric needs further analysis. +However, if, for example, the adversary knows that a user maintained some +network activity for a specific amount of time and then observes a relay +report in this statistic that someone used a rendezvous connection +for that long, then he could infer that the target user was using hidden +services. This gets worse if the adversary makes observations over time +and can observe the changes in the resulting statistics. % How many rendezvous requests finally succeded? % Opposite: What percentage of the time did the rendezvous fail to happen? @@ -883,6 +940,22 @@ cell} \label{subsubsec:num_rend_circ_no_data} % Relays report the number of rendezvous circuits that have been closed before client or service sent a single data cell. +\\ +\textbf{Benefits:} +This could indicate erroneous, malicious, and non-standard behavior by +HS clients. Learing about any such behaviour would be interesting and +useful to improve hidden-service performance and usability. +\\ +\textbf{Risks:} +An adversary at the user's ISP could test to see if a user is attempting +to connect to a hidden service by allowing the connection to proceed until +just before data gets sent, and then killing it by modifying the packet +contents to be garbage. Then he could observe if later any relay reports +a larger-than-expected value for this statistic. This would be more +effective if the user response is immediately to attempt to create new +connections, which would only make the increase in this statistics more +noticeable. + \subsection{Performance-related statistics} @@ -894,7 +967,7 @@ first client introduction (1.2.4.)} % Relays report the time between \verb+ESTABLISH_INTRO+ and first \verb+INTRODUCE1+ cell. -% +\\ \textbf{Benefits:} % This statistic tells us how long it takes for the hidden service to @@ -908,7 +981,7 @@ This may not be very useful, but is listed here for completeness. % [karsten]: again, I think you're wrong about introduction points % changing at each upload. % [dgoulet]: Yup, IP do *NOT* change at each upload. -% +\\ \textbf{Risks:} % No obvious risks. @@ -920,7 +993,7 @@ server rendezvous (2.2.2.)} \label{subsubsec:time_rp_to_rend1} % Relays report the time from receiving an \verb+ESTABLISH_RENDEZVOUS+ cell to receiving the corresponding \verb+RENDEZVOUS1+ cell. -% +\\ \textbf{Benefits:} % The time between receiving an \verb+ESTABLISH_RENDEZVOUS+ cell from the @@ -931,7 +1004,7 @@ events near the beginning and near the end of the connection establishment process. If we ever want to improve the substeps inbetween, this metric is the only way to measure effectiveness of improvements in the deployed network. -% +\\ \textbf{Risks:} % Again, there are at least no obvious risks from gathering this statistic. @@ -943,13 +1016,13 @@ Again, there are at least no obvious risks from gathering this statistic. % Relays report the time from receiving a \verb+RENDEZVOUS1+ cell to seeing the first \verb+RELAY+ cell sent from the client. -% +\\ \textbf{Benefits:} The time from receiving a \verb+RENDEZVOUS1+ cell from the server (and relaying it as \verb+RENDEZVOUS2+ cell to the client) and receiving the first \verb+RELAY+ cell from the client is another performance indicator of the protocol. -% +\\ \textbf{Risks:} % There are no obvious risks from learning the time between these two @@ -975,7 +1048,7 @@ and report them along with the total number of received \verb+ESTABLISH_INTRO+ cells. Or it would report successes and failures, rather than totals and failures. -% +\\ \textbf{Benefits:} % Wrong \verb+ESTABLISH_INTRO+ cells shows either a very bad bug in the code @@ -989,7 +1062,7 @@ or a deliberate action (data mangling, unknown attack, DoS, ...). % [karsten:] right, this is a fine question, not only limited to this % statistic. I added a new paragraph to the section start for "general % considerations for gathering hidden-service statistics". -% +\\ \textbf{Risks:} % No obvious risks. @@ -1001,12 +1074,12 @@ No obvious risks. % Relays report frequencies of circuit terminations requested by services vs. different types of failures. -% +\\ \textbf{Benefits:} % If there are more than a small percentage of failures, decide how to make things more robust. -% +\\ \textbf{Risks:} % No obvious risks. @@ -1032,11 +1105,11 @@ descriptor. For example: a) clock sync issues, b) different network view between, c) ``the hidden service hasn't published recently'', d) ``the hidden service is offline for months''. -% +\\ \textbf{Benefits:} % This seems like a statistic that could potentially find bugs in Tor. -% +\\ \textbf{Risks:} % This statistic could reveal things that we don't really understand and @@ -1051,7 +1124,7 @@ might reveal information about specific services. % How many \verb+INTRODUCE1+ cells have been discarded because of unknown service/malformed (?)/whatever-can-go-wrong, by introduction point? -% +\\ \textbf{Benefits:} % Anything exceeding a small portion of discarded \verb+INTRODUCE1+ cells @@ -1062,7 +1135,7 @@ mangling, unknown attack, DoS, ...). % help us investiguate. It can I guess trigger an alarm but apart from % that... % [karsten]: right, see section start. -% +\\ \textbf{Risks:} % No obvious risks. @@ -1077,7 +1150,7 @@ only fractions are reported, it's not that bad. % Relays report the number of \verb+RENDEZVOUS1+ cell with unknown rendezvous cookie. -% +\\ \textbf{Benefits:} % The number of \verb+RENDEZVOUS1+ cell that cannot be matched with a @@ -1086,7 +1159,7 @@ problems in the protocol. We might even distinguish between rendezvous cookies that were previously known to the relay and those that seem entirely unrelated. The benefit gained from this statistic is not huge though. -% +\\ \textbf{Risk:} % No obvious risks. @@ -1349,11 +1422,9 @@ should be rounded to a chosen granularity $\delta$: $\hat{c_i} = \delta[c_i/\delta]$. $\delta$ should be larger than the amount by which a single activity could change the bucket count, where again the notion of a -single activity depends on the context. Also, for simplicity, it is -recommended that bins -are not split over multiple buckets (e.g. there should not be buckets for -values 0 and 1 if $\delta = 2$). The bins here serve the same purpose -of protecting privacy over time that they did when publishing counts. +single activity depends on the context. The bins here serve the same +purpose of protecting privacy over time that they did when publishing +counts. \item Fresh Laplace noise $\nu_i$ with distribution $\textsf{Lap}(2\delta/\epsilon)$ should be added to the center of the bin of the $i$th bucket. Let the resulting value be

1 0

[tech-reports/master] fixing interval specification
by karsten＠torproject.org 17 Jun '15

17 Jun '15

commit ad1068fc220851397ea93de92962a4a9193ebd1f Author: A. Johnson <aaron.m.johnson(a)nrl.navy.mil> Date: Mon Apr 27 16:34:29 2015 -0400 fixing interval specification --- 2015/hidden-service-stats/hidden-service-stats.tex | 10 +++++----- 1 file changed, 5 insertions(+), 5 deletions(-) diff --git a/2015/hidden-service-stats/hidden-service-stats.tex b/2015/hidden-service-stats/hidden-service-stats.tex index 9d57b1f..e1444e2 100644 --- a/2015/hidden-service-stats/hidden-service-stats.tex +++ b/2015/hidden-service-stats/hidden-service-stats.tex @@ -6,10 +6,10 @@ \usepackage{paralist} \usepackage{comment} -\usepackage{styles/pdfdraftcopy} -\draftcolor{gray20} -\draftstring{DRAFT} -\draftfontsize{150pt} +%\usepackage{styles/pdfdraftcopy} +%\draftcolor{gray20} +%\draftstring{DRAFT} +%\draftfontsize{150pt} \begin{document} @@ -1576,7 +1576,7 @@ Following are several potential ways to publish information about a distribution: \begin{compactitem} \item Publish a histogram of possible values (e.g. the number of values in -$[0,1]$, $[1,10]$, $[10, 100]$, and $[100, \infty)$). +$[0,1)$, $[1,10)$, $[10, 100)$, and $[100, \infty)$). \item Publish a subset of percentile values (e.g. quartiles). \item Publish standard summary statistics, (e.g. mean, variance, skew, and kurtosis).

1 0

[tech-reports/master] Remove our own hardcoded section numbers from subsubsections.
by karsten＠torproject.org 17 Jun '15

17 Jun '15

commit a80cfa08c5252ac44b331dd6823893d373639306 Author: George Kadianakis <desnacked(a)riseup.net> Date: Fri Jan 9 13:28:18 2015 +0200 Remove our own hardcoded section numbers from subsubsections. If we need them in the future, check this git history. --- 2015/hidden-service-stats/hidden-service-stats.tex | 49 +++++++++----------- 1 file changed, 21 insertions(+), 28 deletions(-) diff --git a/2015/hidden-service-stats/hidden-service-stats.tex b/2015/hidden-service-stats/hidden-service-stats.tex index d3ad6c4..d2650ea 100644 --- a/2015/hidden-service-stats/hidden-service-stats.tex +++ b/2015/hidden-service-stats/hidden-service-stats.tex @@ -547,7 +547,7 @@ This could reveal the introduction points of hidden services with encrypted descriptors. \subsubsection{Time from establishing introduction point to tearing down -circuit (1.1.4.)} +circuit} \label{subsubsec:time_intro_to_teardown} \textbf{Details:} @@ -566,7 +566,7 @@ This statistic can also be used to analyze what fraction of services is available for a short time only, and what fraction is available most of the time. -\subsubsection{Number of hidden service descriptors seen by directory (3.1.1.)} +\subsubsection{Number of hidden service descriptors seen by directory} \label{subsubsec:num_descriptor_publish} \textbf{Details:} @@ -621,7 +621,7 @@ period. If this ever becomes a problem we can imagine publishing fake descriptors -\subsubsection{Number of descriptor updates per service (3.1.2.)} +\subsubsection{Number of descriptor updates per service} \label{subsubsec:num_decriptor_updates} \textbf{Details:} @@ -668,8 +668,7 @@ introduction points change. There is an upper bound on this statistic at 24 hours, because that's when descriptor identifiers change. -\subsubsection{Number of introduction points contained in descriptors -(3.1.4.)} \label{subsubsec:num_ips_in_descriptors} +\subsubsection{Number of introduction points contained in descriptors} \label{subsubsec:num_ips_in_descriptors} \textbf{Details:} % @@ -702,7 +701,7 @@ The following statistics are about service usage, where performance-related statistics and failure statistics are covered at a later time. -\subsubsection{Number of descriptor fetch requests (3.2.1.)} +\subsubsection{Number of descriptor fetch requests} \label{subsubsec:num_desc_fetches} \textbf{Details:} @@ -728,8 +727,7 @@ the target HS is assigned to them. This is a major problem that doesn't seem resolvable without some kind of anonymization or private aggregation of the per-relay stats. -\subsubsection{Number of descriptor fetch requests by service identity -(3.2.2.)} \label{subsubsec:num_descriptor_fetches_per_hs} +\subsubsection{Number of descriptor fetch requests by service identity} \label{subsubsec:num_descriptor_fetches_per_hs} \textbf{Details:} % @@ -752,7 +750,7 @@ then this statistic could give that adversary an exact measure of popularity. % -\subsubsection{Number of established rendezvous points (2.1.1.)} +\subsubsection{Number of established rendezvous points} \label{subsubsec:num_rps} \textbf{Details:} @@ -777,7 +775,7 @@ total number of such cells in the network. There is no obvious risk from sharing this number if aggregated over a large enough time period. -\subsubsection{Number of introductions received from clients (1.2.1.)} +\subsubsection{Number of introductions received from clients} \label{subsubsec:num_intros_from_clients} \textbf{Details:} @@ -816,7 +814,7 @@ to avoid this problem. % [dgoulet]: No they don't, I confirmed in the code. \subsubsection{Number of introductions received by established -introduction point (1.2.2.)} \label{subsubsec:num_intros_per_circ} +introduction point} \label{subsubsec:num_intros_per_circ} \textbf{Details:} % @@ -839,7 +837,7 @@ potentially makes it even easier to differentiate introductions due to different HSes with the same IP. % -\subsubsection{Number of server rendezvous (2.2.1.)} +\subsubsection{Number of server rendezvous} \label{subsubsec:num_server_rendezvous} \textbf{Details:} @@ -875,7 +873,7 @@ given client or server. \subsubsection{Number of cells sent over rendezvous circuits in either -direction (2.3.2.)} \label{subsubsection:num_cells_rend_circ} +direction} \label{subsubsection:num_cells_rend_circ} \textbf{Details:} % @@ -912,8 +910,7 @@ While total number of cells by direction aggregated over a certain time period should be okay to measure, any statistics going further than that need closer analysis. -\subsubsection{Time from first client data to tearing down circuit -(2.3.3.)} \label{subsubsec:time_client_data_to_teardown} +\subsubsection{Time from first client data to tearing down circuit} \label{subsubsec:time_client_data_to_teardown} \textbf{Details:} % @@ -978,7 +975,7 @@ noticeable. \subsection{Performance-related statistics} \subsubsection{Time from establishing introduction point to receiving -first client introduction (1.2.4.)} +first client introduction} \label{subsubsec:time_ip_est_to_introduce1} \textbf{Details:} @@ -1005,7 +1002,7 @@ This may not be very useful, but is listed here for completeness. No obvious risks. \subsubsection{Time from establishing a rendezvous point to receiving the -server rendezvous (2.2.2.)} \label{subsubsec:time_rp_to_rend1} +server rendezvous} \label{subsubsec:time_rp_to_rend1} \textbf{Details:} % @@ -1027,7 +1024,7 @@ way to measure effectiveness of improvements in the deployed network. % Again, there are at least no obvious risks from gathering this statistic. -\subsubsection{Time from server rendezvous to first client data (2.3.1.)} +\subsubsection{Time from server rendezvous to first client data} \label{subsubsec:time_rend1_to_data} \textbf{Details:} @@ -1054,7 +1051,7 @@ Could be a starting point to look at actual logs from relays. But is this what statistics are for? \subsubsection{Number of failed attempts to establish an introduction -point (1.1.3.)} \label{subsubsec:num_failed_ips} +point} \label{subsubsec:num_failed_ips} \textbf{Details:} % @@ -1085,8 +1082,7 @@ or a deliberate action (data mangling, unknown attack, DoS, ...). % No obvious risks. -\subsubsection{Reasons for terminating established introduction points -(1.1.5.)} \label{subsubsec:reasons_end_ips} +\subsubsection{Reasons for terminating established introduction points} \label{subsubsec:reasons_end_ips} \textbf{Details:} % @@ -1102,8 +1098,7 @@ things more robust. % No obvious risks. -\subsubsection{Number of descriptors published to the wrong directory -(3.1.7.)} \label{subsubsec:num_descriptors_wrong_hsdir} +\subsubsection{Number of descriptors published to the wrong directory} \label{subsubsec:num_descriptors_wrong_hsdir} \textbf{Details:} % @@ -1111,7 +1106,7 @@ A relay reports the number of published descriptors that it is not responsible for. \subsubsection{Number of descriptor fetch requests for non-existent -descriptor (3.2.3.)} \label{subsubsec:num_fetch_nonexistent} +descriptor} \label{subsubsec:num_fetch_nonexistent} \textbf{Details:} % @@ -1135,8 +1130,7 @@ might reveal information about specific services. -\subsubsection{Number of discarded client introductions by reason -(1.2.3.)} \label{subsubsec:num_discarded_client_intros} +\subsubsection{Number of discarded client introductions by reason} \label{subsubsec:num_discarded_client_intros} \textbf{Details:} % @@ -1161,8 +1155,7 @@ More precisely, if absolute numbers are reported, the risk is the same as the risk of reporting the number of received \verb+INTRODUCE1+ cells; if only fractions are reported, it's not that bad. % -\subsubsection{Number of server rendezvous with unknown rendezvous cookie -(2.2.3.)} \label{subsubsec:num_server_rend_unknown_cookie} +\subsubsection{Number of server rendezvous with unknown rendezvous cookie} \label{subsubsec:num_server_rend_unknown_cookie} \textbf{Details:} %

1 0

Jump to page: