tor-commits June 2015

tor-commits@lists.torproject.org

22 participants
1870 discussions

[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

[tech-reports/master] fixing HS protocol step numbering
by karsten＠torproject.org 17 Jun '15

17 Jun '15

commit 2c25f916e2457a4b08b167e0ea24a05214345170 Author: A. Johnson <aaron.m.johnson(a)nrl.navy.mil> Date: Wed Apr 22 14:33:17 2015 -0400 fixing HS protocol step numbering --- 2015/hidden-service-stats/hidden-service-stats.bib | 143 ++- 2015/hidden-service-stats/hidden-service-stats.tex | 972 +++++++++++--------- 2015/hidden-service-stats/protocol.odg | Bin 17986 -> 14037 bytes 3 files changed, 690 insertions(+), 425 deletions(-) diff --git a/2015/hidden-service-stats/hidden-service-stats.bib b/2015/hidden-service-stats/hidden-service-stats.bib index 2fbb81a..c55e917 100644 --- a/2015/hidden-service-stats/hidden-service-stats.bib +++ b/2015/hidden-service-stats/hidden-service-stats.bib @@ -39,4 +39,145 @@ booktitle = {Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing}, series = {STOC '09}, year = {2009} -} \ No newline at end of file +} + +@misc{torprop-rend-spec-ng, + author = {Nick Mathewson}, + title = {Next-Generation Hidden Services in {Tor}}, + howpublished = {\url{https://gitweb.torproject.org/torspec.git/plain/proposals/224-rend-spec-ng.txt}}, + note = {Accessed: 2015-04-18} +} + +@inproceedings{tor-design, + title = {{Tor}: The Second-Generation Onion Router}, + author = {Roger Dingledine and Nick Mathewson and Paul Syverson}, + booktitle = {Proceedings of the 13th USENIX Security Symposium}, + year = {2004} +} + +@misc{rend-spec, + key = {Tor Rendezvous Specification}, + title = {Tor Rendezvous Specification}, + howpublished = {\url{https://gitweb.torproject.org/torspec.git/plain/rend-spec.txt}}, + note = {Accessed: 2015-04-18} +} + +@misc{tormetrics, + key = {{Tor Metrics Portal}}, + title = {{Tor Metrics Portal}}, + howpublished = {\url{http://metrics.torproject.org/}}, + note = {Accessed: 2015-04-18} +} + +@misc{dir-spec, + key = {Tor directory protocol}, + title = {Tor directory protocol}, + howpublished = {\url{https://gitweb.torproject.org/torspec.git/plain/dir-spec.txt}}, + note = {Accessed: 2015-04-18} +} + +@techreport{extrapolation-tor-techreport, + author = {George Kadianakis and Karsten Loesing}, + title = {Extrapolating network totals from hidden-service statistics}, + number = {2015-01-001}, + institution = {The Tor Project}, + year = {2015} +} + +@misc{torprop-hsstats, + authors = {George Kadianakis, David Goulet, Karsten Loesing, Aaron Johnson}, + title = {Better hidden service stats from {Tor} relays}, + howpublished = {\url{https://gitweb.torproject.org/torspec.git/plain/proposals/238-hs-relay-stats.txt}}, + note = {Accessed: 2015-04-18} +} + +@inproceedings{botnetfc14, + title = {Challenges in protecting Tor hidden services from botnet abuse}, + author = {Nicholas Hopper}, + booktitle = {Proceedings of Financial Cryptography and Data Security (FC'14)}, + year = {2014}, + month = {March}, + www_tags = {selected}, + www_pdf_url = {http://fc14.ifca.ai/papers/fc14_submission_152.pdf}, + www_section = {Anonymous communication}, +} + +@inproceedings{oakland2013-trawling, + title = {Trawling for {Tor} Hidden Services: Detection, Measurement, Deanonymization}, + author = {Alex Biryukov and Ivan Pustogarov and Ralf-Philipp Weinmann}, + booktitle = {Proceedings of the 2013 IEEE Symposium on Security and Privacy}, + year = {2013} +} + +@misc{tor2web, + key = {Tor2web: browse the anonymous internet}, + title = {Tor2web: browse the anonymous internet}, + howpublished = {\url{https://www.tor2web.org/}}, + note = {Accessed: 2015-04-18} +} + +@inproceedings{torflow-hotpets10, + title = {TorFlow: Tor network analysis}, + author = {Mike Perry}, + booktitle = {3rd Hot Topics in Privacy Enhancing Technologies (HotPETs 2010)}, + year = {2010} +} + +@misc{torprop-hsdir-stable, + author = {George Kadianakis}, + title = {{Give out HSDir flag only to relays with Stable flag}}, + howpublished = {\url{https://gitweb.torproject.org/torspec.git/plain/proposals/243-hsdir-flag-need-stable.txt}}, + note = {Accessed: 2015-04-19} +} + +@misc{torprop-tor2web, + author = {Virgil Griffith and Fabio Pietrosanti and Giovanni Pellerano}, + title = {Making Tor2Web mode faster}, + howpublished = {\url{https://gitweb.torproject.org/torspec.git/plain/proposals/233-quicken-tor2web-mode.txt}}, + note = {Accessed: 2015-04-19} +} + +@inproceedings{privda-acsac2014, + author = {Eigner, Fabienne and Kate, Aniket and Maffei, Matteo and Pampaloni, Francesca and Pryvalov, Ivan}, + title = {Differentially Private Data Aggregation with Optimal Utility}, + booktitle = {Proceedings of the 30th Annual Computer Security Applications Conference}, + series = {ACSAC '14}, + year = {2014} +} + +@inproceedings{shadow-ndss12, + title = {{Shadow: Running Tor in a Box for Accurate and Efficient Experimentation}}, + author = {Rob Jansen and Nicholas Hopper}, + booktitle = {Proceedings of the Network and Distributed System Security Symposium - + {NDSS}'12}, + year = {2012} +} + +@mastersthesis{sukhbir-thesis, + author = {Sukhbir Singh}, + title = {Large-Scale Emulation of Anonymous Communication Networks}, + school = {University of Waterloo}, + year = {2014} +} + +@inproceedings{Dwork06differentialprivacy, + author = {Cynthia Dwork}, + title = {Differential privacy}, + booktitle = {in ICALP}, + year = {2006} +} + +@misc{tor-spec, + author = {Roger Dingledine and Nick Mathewson}, + title = {Tor Protocol Specification}, + howpublished = {\url{https://gitweb.torproject.org/torspec.git/plain/tor-spec.txt}}, + note = {Accessed: 2015-04-21} +} + +@inproceedings{ganta-kdd2008, + author = {Ganta, Srivatsava Ranjit and Kasiviswanathan, Shiva Prasad and Smith, Adam}, + title = {Composition Attacks and Auxiliary Information in Data Privacy}, + booktitle = {Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining}, + series = {KDD '08}, + year = {2008} +} \ 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 d2650ea..9d57b1f 100644 --- a/2015/hidden-service-stats/hidden-service-stats.tex +++ b/2015/hidden-service-stats/hidden-service-stats.tex @@ -4,19 +4,25 @@ \usepackage{hyperref} \usepackage{longtable} \usepackage{paralist} +\usepackage{comment} + +\usepackage{styles/pdfdraftcopy} +\draftcolor{gray20} +\draftstring{DRAFT} +\draftfontsize{150pt} \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}} +\author{David Goulet\\The Tor Project\\ \href{mailto:dgoulet@torproject.org}{dgoulet@torproject.org} \and +Aaron Johnson\\U.S. Naval Research Laboratory\\ \href{mailto:aaron.m.johnson@nrl.navy.mil}{aaron.m.johnson@nrl.navy.mil} \and +George Kadianakis\\The Tor Project\\ \href{mailto:asn@torproject.org}{asn@torproject.org} \and +Karsten Loesing\\The Tor Project\\ \href{mailto:karsten@torproject.org}{karsten@torproject.org}} +%\footnotemark[\ref{tpi}] -\reportid{DRAFT} -\date{January XX, 2015} +%\reportid{DRAFT} +\date{} \maketitle @@ -26,325 +32,360 @@ % - Abbreviations are best avoided. % - Code, cell names, etc. are put inside \verb+...+. -\tableofcontents +%\tableofcontents \begin{abstract} -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. +In order to understand how hidden services are being used in Tor, relays +can collect and report statistics about the hidden-service activity they +observe. However, such statistics might harm the privacy of individual Tor +users. We describe how relays can be used to collect statistics about +hidden services, how they might be useful, and how they can be published +in a way that protects individual privacy. \end{abstract} \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. +Tor hidden services~\cite{tor-design,rend-spec} are a means to provide a +network service while hiding the location of the server. To provide this +anonymity to the server, client connections are set up using a different +process than is used by connections to known servers. This process comes +with a performance cost. Also, servers must be configured explicitly to +be accessed as a hidden service. As a result, the way that Tor hidden +services are being used may be quite different from the way that Tor is +used to anonymize traffic to normal, non-hidden Internet services. + +Therefore, in addition to the general statistics that Tor collects +about its network~\cite{tormetrics}, it is interesting and useful to +collect statistics specific to hidden services. For example, +hidden-service statistics could show how popular they are, how well they +perform, and if they are under attack. Publishing such data could help +Tor to manage and improve its network, Tor advocates to argue more +effectively in support of Tor, and researchers to understand how Tor is +being used. + +Tor relays are frequently in a position to learn some information about +hidden services and their usage. Relays have long collected and reported +information for many \emph{general} statistics of interest (i.e. +those that are not specific to hidden services), such as the amount of +total traffic that they have relayed. They do this by including these data +in ``extra-info documents''~\cite{dir-spec}, which +are uploaded to the Directory Authorities. These local observations can be +combined to give a global view of Tor's hidden service activity. + +However, Tor's privacy protections depend on relays not sharing all their +local observations. Therefore, we must carefully consider how to publish +data in a way that doesn't hurt Tor's privacy goals. Tor has adopted +some privacy protections for the general statistics it gathers. These +protections include +reporting data aggregated over a period of time and rounding some +measurements to a desired level of accuracy. There is a set of privacy +objectives and risks that are specific to hidden services, however, and so +these techniques may not apply directly. +For example, hidden services have a primary privacy goal of hiding the +server's location and a secondary goal of allowing the existence of the +service itself to be hidden. + +% more detail / a paragraph about obfuscation techniques? +Thus, to address the particular challenge of studying Tor hidden services, +this report describes how relays can safely collect useful statistics +about them. It includes the following contributions: +\begin{itemize} +\item A description of the types of observations that relays can make +about hidden services +\item A description of the privacy objectives specific to hidden services +\item A description of obfuscation techniques that can be used to safely +release hidden-service statistics +\end{itemize} \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. +The hidden-service protocol consists of multiple steps for a service to +become available through the network and for a client to connect to a +service~\cite{rend-spec}. Each step gives some relays the opportunity to +gather statistics about their role in the hidden-service +protocol. Hidden service clients and servers also are in a position to +gather statistics, but in this report we focus on collection by relays. +The major roles of relays in the hidden-service protocol are: a) Hidden +Service Directory (HSDir), b) Introduction Point (IP), and c) Rendezvous +Point (RP). 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.} +\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: +The protocol steps for making a service available through the network are +as follows: \begin{enumerate} -\item The service \emph{establishes an introduction point} on one or more +\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 +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. +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 +Hidden Service Directories, which are the set of relays with high-enough +uptime as indicated by the ``HSDir'' flags in the network consensus. +Each of those relays 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 relay can read most parts of the descriptor, including the service +identity (this may change as part of a proposed protocol +update~\cite{torprop-rend-spec-ng}) 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 +The protocol steps 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. +\item The client \emph{fetches a descriptor} from a Hidden Service +Directory. The relay that acts as an HSDir receives a circuit extension +request followed by a request to fetch the descriptor. +Once the descriptor is returned, or a response is returned saying that the +descriptor 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 a 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. +only a random identifier. The circuit, now called rendezvous circuit, is kept open until either -client or service close it. +the client or service closes 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, +Introduction Points. +The Introduction Point 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 +The client's circuit is torn down by the relay 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 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 +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. +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. +All of these protocol steps constitute potential measurement points for +hidden-service related statistics. For example, some Tor relays have +been reporting the following statistics about hidden services, which +were proposed by Kadianakis et al.~\cite{torprop-hsstats} and the +results analyzed by Kadianakis and +Loesing~\cite{extrapolation-tor-techreport}: +\begin{compactenum} +\item \textsf{NumRPCells}: The number of hidden-service data +cells seen at a Rendezvous Point, reported every 24 hours +\item \textsf{NumHSDirIDs}: The number of unique hidden +identifiers seen at an HSDir, reported every 24 hours +\end{compactenum} \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. +A proposal to collect some hidden-service statistics must be evaluated +according to several criteria. The main criteria are the benefits to Tor, +the effect on privacy, the reliability of the statistics, the efficiency +of the collection process, and alternatives to live collection. \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. +There are several compelling reasons to collect information about hidden +service statistics. We describe some of them to illustrate the possible +benefits. \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. +Understanding how hidden services are being used can help both to direct +development efforts and to justify them. Usage statistics could provide +insight into how many hidden services exist, how available they are, how +many clients they have, how much Tor traffic is hidden-service traffic, +and what types +of applications use hidden services. These data could help Tor developers +decide how much effort to spend improving hidden services and what types +of changes would most benefit users. They can also be of use to +researchers that analyze Tor and design improvements. +Hidden-service statistics would also provide evidence +that can be used in efforts to improve their media coverage, +to persuade potential funders, and to inform government policy. \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. +Data about hidden services can help Tor developers improve performance. +Such data might include speed and failure rates for the steps of the +hidden-service protocol, resource utilization at the relays, and +hidden-service availability. +This information could be used to improve load balancing across relays, +to optimize the values of various parameters in the hidden-service +protocol, and to add relay resources where they would be most effective. +They could be used to inform more ambitious redesigns of the +hidden-service protocols. They could also be used to build models of +client, network, and hidden-service behavior to use in network simulations +done in support of performance improvements. \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. +Statistics can help detect bugs in hidden services. This could be +especially useful to identify problems those that occur infrequently or +only under realistic conditions, such the network traffic load or the mix +of Tor software versions used. Information that could be particularly +useful for this purpose includes failures rates and the frequency of +unexpected events. \paragraph{Discover attacks} +Hidden-service statistics may uncover ongoing attacks in the network. +Denial-of-service attacks in particular might be detected from spikes in +usage and failure statistics. Statistics about the utilization of relay +resources such as CPU, memory, and bandwidth might also reveal variations +that are unexpected under normal use. In addition, data about the software +versions may reveal client Sybil attacks or botnet +abuse~\cite{botnetfc14}. + +\subsection{Hidden-service privacy goals} +Gathering statistics on Tor has implications for its privacy because the +data is determined from relays' observations of the private behavior of +Tor users. Tor statistics are published and thus may be used by an +adversary to determine the private activity of Tor users. + +Tor has several privacy goals. Primary, of course, is to provide +anonymity to the source of a connection and to hide the network location +of a hidden service. However, there are several +other related and secondary goals. Complementing user privacy, for +example, is the goal of unlinkability among separate Tor connections, +which prevents an adversary from creating a pseudonymous profile +of a user's network activity. We focus on the various privacy goals +specific to hidden services, which to our knowledge have not previously +been explicitly articulated. Our listing of privacy goals is not +exhaustive. Tor's default position for information about the use +of its network is that it should be protected, and exceptions should be +made only in specific, carefully-considered cases. The privacy goals we +highlight are those for which choosing to contradict them is very +unlikely. + +\paragraph{Information about a specific hidden service} +The following information about any specific hidden service should remain +private: +\begin{compactenum} +\item The network location of the hidden service +\item The exact number of hidden services (i.e. the existence of the +hidden service) +\item The number of clients that have used the hidden service +\item The number of connections to the hidden service +\item The amount of traffic to or from the hidden service +\item The availability of the hidden service +\end{compactenum} +Observe that including several of these amounts to a goal of allowing a +hidden service to remain undiscovered or undistinguished. This allows a +hidden service to maintain a low profile and not come under investigation +or scrutiny by an observant adversary. +Also note that these are not all currently well-protected by Tor. For +example, the existence and popularity of a hidden service can currently be +learned by an HSDir~\cite{oakland2013-trawling}, although there are plans +to close this information leak~\cite{torprop-rend-spec-ng}. + +\paragraph{Information about a specific hidden-service client} +Related to the above, it is a goal to hide information that is specific +to a given hidden-service client, including +\begin{compactenum} +\item The number of hidden-service connections of the client +\item The amount of the client's hidden-service traffic +\item When a client is active on hidden services +\end{compactenum} +These privacy goals also exist more generally for clients' Tor activity +that doesn't use hidden services. -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} - -% 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. 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} - -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. - -\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 -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 +\paragraph{Information about a specific hidden-service connection} +It is also a goal to hide information about any given hidden-service +connection, including +\begin{compactenum} +\item The client and the service of the connection +\item The exact number of hidden-service connections +\item When a connection occurred +\item How much traffic was transferred over some connection +\item If the connection shares a client or hidden service with another +given connection +\end{compactenum} +As with specific client information, it is a privacy goal more generally +to protect information about any specific client connection. + +\paragraph{Information about ongoing activity} +Statistics should not reveal information relevant to the \emph{ongoing} +activity of clients, hidden services, or connections. This should be +maintained even when the information is safe to release \emph{after} the +activity has ceased. For example, it should not be revealed that certain +relays are currently being used as Introduction Points by some hidden +service, although it may be reasonable to reveal that some relays have +been used as Introduction Points in the past. The risk of revealing +ongoing activity is that an active adversary can use that information +to begin targeted surveillance of that activity. + + +\subsection{Reliability} +An important criterion for a statistics-gathering procedure is its +reliability. To be reliable, data must be accurate, available, robust to +network changes, and resilient to malicious attacks. This criterion +becomes especially important when a statistic affects the operation +of Tor in real time. For example, the measurements gathered by +TorFlow~\cite{torflow-hotpets10} are used to determine relay weights +in the hourly consensuses. + +Robustness to future network changes is an important concern in the Tor +network, which frequently improves in response to user needs and +adversarial capabilities. For example, there are several current +proposals to change hidden services in +minor~\cite{torprop-hsdir-stable,torprop-tor2web} and +major~\cite{torprop-rend-spec-ng} ways. +Statistics collection shouldn't be broken or precluded by such 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. - +Malicious attacks are another particular concern for Tor, because it +operates in a highly-adversarial setting that is not typical of many other +networks and services. When relays collect and report hidden-service +statistics, the process is particularly vulnerable to manipulation +by malicious relays, which can provide completely arbitrary data. An +ideal procedure for gathering statistics would be robust to attempted +manipulation by a small fraction of the network. + +\subsection{Efficiency} +Statistics collection should not place an undue burden on Tor's existing +infrastructure. It should be designed to minimize bandwidth consumption, +CPU utilization, and memory requirements. Thus it may be necessary to +limit the frequency at which statistics are updated or the complexity of +a cryptographic aggregation +procedure~\cite{elahi-ccs2014,privda-acsac2014}. + +\subsection{Alternatives} +Some of the possible benefits of measuring the live Tor network may +also obtained by measuring private or +simulated~\cite{shadow-ndss12,sukhbir-thesis} networks. For example, +private networks can be used to find bugs by testing hidden services under +various conditions and looking for unexpected behavior. Using these +methods eliminates the privacy risk that accompanies measurement of the +live network, and so such methods should be preferred when possible. + +\begin{comment} \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.} +%\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. @@ -461,7 +502,7 @@ 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. +%Admitted, this benefit is not huge. \\ \textbf{Risks:} % @@ -592,16 +633,18 @@ are. \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''. +to be able to say ``I have seen 76~\% of all hidden services''. 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. +%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. +Obfuscation will be necessary to prevent this (see +Section~\ref{sec:obfuscation}). 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 @@ -612,7 +655,8 @@ 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 +When \verb+rend-spec-ng.txt+\cite{torprop-rend-spec-ng} 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 @@ -646,9 +690,10 @@ 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. In addition, this could +%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. +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 @@ -680,7 +725,7 @@ hidden-service descriptors, possibly also percentiles. 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. +This statistic will also be killed by rend-spec-ng~\cite{torprop-rend-spec-ng}. \subsubsection{Number of descriptors with encrypted introduction points (3.1.5.)} \label{subsubsec:num_desc_encrypted_ips} @@ -693,7 +738,8 @@ 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. +This statistic won't be available after implementing +rend-spec-ng~\cite{torprop-rend-spec-ng}. \subsection{Statistics on service usage} @@ -725,7 +771,8 @@ 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. +of anonymization or private aggregation of the per-relay stats (see +Section~\ref{sec:obfuscation}). \subsubsection{Number of descriptor fetch requests by service identity} \label{subsubsec:num_descriptor_fetches_per_hs} @@ -1017,7 +1064,7 @@ 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 +If we ever want to improve the steps inbetween, this metric is the only way to measure effectiveness of improvements in the deployed network. \\ \textbf{Risks:} @@ -1041,7 +1088,7 @@ of the protocol. \textbf{Risks:} % There are no obvious risks from learning the time between these two -substeps in the rendezvous protocol. +steps in the rendezvous protocol. \subsection{Failure statistics} @@ -1174,13 +1221,18 @@ The benefit gained from this statistic is not huge though. \textbf{Risk:} % No obvious risks. +\end{comment} \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 +There is a variety of available methods to produce general +statistics about a dataset without revealing specific sensitive details. +We briefly discuss how this might be done in the context of hidden +services, and then we provide two algorithms for revealing count and +distributional statistics that can be applied to a variety of specific +hidden-service statistics. + +Some useful techniques for privately publishing statistics on hidden +services are \begin{compactitem} \item Releasing aggregate statistics over time, such as total counts or averages in a given period @@ -1192,42 +1244,128 @@ 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{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 -$\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. - - -\subsection{Adversary knowledge} +However, in general, publishing any information that is broadly +informative might break privacy, because that information may be just what +the adversary needs to know in order to learn a sensitive +fact~\cite{Dwork06differentialprivacy}. Therefore, a discussion of privacy +on Tor should consider plausible background knowledge for an adversary. We can expect that the adversary may know things such as \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 (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 +\item The Introduction Points of a service (e.g. by obtaining the +descriptor) +\item The availability of a service (e.g. 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) +traffic for a service (e.g. a web forum that reveals user activity on the +site) \end{compactitem} +Given such information, it can be seen that certain statistics cannot be +published by individual relays with reasonable accuracy without violating +some privacy. For example, if each relay accurately reported the number of +client introduction requests it received, then an adversary that +knows the \texttt{.onion} address of a hidden service (and thus can obtain +its Introduction Points) could infer how many client connections the +hidden-service received, especially if there were few other hidden +services sharing its Introduction Points. The general problem is that, for +certain types of hidden-service activities, different hidden services or +clients will make use of different relays in a way that may be known by +the adversary. + +\begin{comment} +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} +\end{comment} + +We give two algorithms for privately publishing statistics that do not +have this problem, that is, that can be released by each relay. +Two examples of such statistics are those described by Kadianakis et +al.~\cite{torprop-hsstats} (also mentioned in Section~\ref{sec:protocol}): +\begin{compactenum} +\item \textsf{NumRPCells}: The number of hidden-service data +cells seen at a Rendezvous Point +\item \textsf{NumHSDirIDs}: The number of unique hidden +identifiers seen at an HSDir. +\end{compactenum} +The first algorithm provides a way to +publish statistics that are simple running counts, including both +\textsf{NumRPCells} and \textsf{NumHSDirIDs}. The second algorithm +provides a way to publish statistics about a distribution of values. + +Our algorithms will add 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, +Kadianakis et al.~\cite{torprop-hsstats} use the following for their +statistics: +\begin{compactenum} +\item For \textsf{NumRPCells}, a single action is +transferring a fixed amount of data (specifically, 2048 cells). Thus the +added noise obscures the activity of a single service, client, or +connection up to that amount of traffic. +\item For \textsf{NumHSDirIDs}, a single action is +publishing a fixed number of hidden services (specifically, 8). Thus the +added noise obscures the existence of any eight or fewer hidden services. +\end{compactenum} +To obtain differential privacy, our algorithms add noise using the +Laplace distribution, which has a probability distribution function +$\textsf{Lap}(b)$ of $f(x) = 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{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 +hidden-service traffic. +\begin{comment} +Table~\ref{table:count_stats} lists the statistics for which it could be useful to release counts. \begin{table} \center @@ -1281,14 +1419,14 @@ Number of server rendezvous with unknown rendezvous cookie & \hline \end{tabular} \end{table} +\end{comment} 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 +to provide strong protection for a single hidden-service action. 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 +privacy, using a per-user or per-service privacy notion that includes +actions 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}) @@ -1325,27 +1463,60 @@ 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)$ +\item Repeatedly maintain a running count $c$ over a time period of length +$t$. +\item Choose a bin granularity $\delta_1$, which should be large enough +to contain the change in a single statistic due to a \emph{repeated} +action, that is, an action repeated over many +reporting periods that we wish to hide any single instance of. +\item Round $c$ to the nearest multiple of $\delta_1$, that is, let +$\hat{c} = \delta_1[c/\delta_1]$, where $[]$ indicates the nearest integer +function. Rounding up (as in Kadianakis et al.~\cite{torprop-hsstats}) or +down can be performed instead for a similar effect on privacy, although +they introduce a bias that should be corrected +for~\cite{extrapolation-tor-techreport}. +\item Choose a value $\nu$ from the $\textsf{Lap}(\delta_2/\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}$. +parameter discussed in Sec.~\ref{sec:obfuscation}. +$\delta_2$ is the amount by which a single (non-persistent) action that +we wish to hide could change the bin center. +\item Let the noisy count be $\tilde{c} = \hat{c} + \nu$. +\item Wait until all activity contributing to count $c$ should have +completed, and then publish $\tilde{c}$. \end{compactenum} +\paragraph{Example 1:} Kadianakis et al.~\cite{torprop-hsstats} use this +algorithm to publish \textsf{NumRPCells} over periods of length +$t = 24$ hours. The waiting period after collection is implicit in the +length of time until the next extra-info descriptor is published by the +relay, which happens every 18 hours unless certain relay properties +change~\cite{dir-spec}. They use $\delta_1 = 1024$, $\delta_2 = 2048$, and +$\epsilon = 0.3$. This setting of $\delta_1$ hides any repeated transfer +of up to 1024 cells. Tor cells have up to 509 payload +bytes~\cite{tor-spec}, and so this is 509 KiB. This setting of $\delta_2$ +hides any group of up to 2048 transferred cells (1018 KiB) (e.g. a +connection in which a client downloads 1 MB). One way of interpreting the +privacy from $\epsilon=0.3$ is from a Bayesian +perspective~\cite{ganta-kdd2008}, where if a priori, for any given set of +other transfers, the adversary believed a given transfer of up to 2048 +cells did (or didn't) occur, then the statistics can only increase his +confidence by at most $1-e^{0.3}$ (i.e. $\sim35\%$). + +\paragraph{Example 2:} Kadianakis et al.~\cite{torprop-hsstats} use this +algorithm to publish \textsf{NumHSDirIDs} over periods of length +$t = 24$ hours, waiting to publish with the relay's next extra-info +descriptor. They use $\delta_1 = 8$, $\delta_2 = 8$, and +$\epsilon = 0.3$. These settings for $\delta_1$ and $\delta_2$ hide any +single or repeated publication of any given group of at most 8 onion +services (e.g. a set of 8 or fewer related onion addresses that are +aliases for the same onionsite). \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 -there are a few hidden services that constitute most HS activity. +distribution of values. For example, such information about the +number of cells on a single circuit could reveal if most +hidden-service traffic is produced by relatively few connections. +\begin{comment} Table~\ref{table:dist_stats} lists the statistics for which it could be useful to release information about a distribution. \begin{table} @@ -1399,6 +1570,7 @@ Number of descriptor fetch requests for non-existent descriptor & \hline \end{tabular} \end{table} +\end{comment} Following are several potential ways to publish information about a distribution: @@ -1413,8 +1585,8 @@ 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 +histograms simply by applying the techniques that we have 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} @@ -1423,108 +1595,62 @@ 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, the number of width of the buckets should -be balanced while also +reduces its accuracy. Therefore, the number and 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 Over repeated time periods of length $t$, maintain running counts +$c_i$, where $c_i$ is the count of observed values in the $i$th bucket. \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. The bins here serve the same -purpose of protecting privacy over time that they did when publishing -counts. +should be rounded to a chosen granularity $\delta_1$: +$\hat{c_i} = \delta_1[c_i/\delta_1]$. +$\delta_1$ should be at least the amount by which a single instance of +a repeated action that we want to hide could change the bucket count, +where again the notion +of a single action depends on the context. The $\delta_1$-sized bins here +serve the same purpose of protecting privacy over time that they did when +publishing a single count. \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 +$\textsf{Lap}(2\delta_2/\epsilon)$ should be added to the center of the +bin of the $i$th bucket, where $\delta_2$ is at least the amount by which +a single (non-repeated) action that we want to hide could change the bin +center. 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 Publish each noisy bucket count, $\tilde{c_i}$, $1\le i\le k$. +\item Wait until the activity contributing to the histogram should have +completed, and then 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 +\section{Future Work} +There are many possible ways to expand the hidden-service statistics that +we can safely gather and to improve their accuracy. One promising option +is to securely perform aggregation +such that no single party can learn more than the final aggregate value. +This would allow collecting statistics that cannot be reported by each +relay individually, as previously discussed. + +In addition, secure aggregation could reduce the amount of noise that +needs to be added. With per-relay reporting, rounding and noise is +applied to each relay's statistics when using the algorithms described +in Sections~\ref{subsec:counts} \& \ref{subsec:distributions}. However, +the same noise would provide equivalent protection if applied only once +to the statistics after network-wide aggregation. 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 some promising approaches to secure statistics aggregation +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 Have the relays provide inputs to a secure multiparty computation +(SMC) protocol that produces the desired statistics with any +privacy-preserving modifications included (e.g. added +noise)~\cite{privda-acsac2014}. +\item Use a customized aggregation protocol, such at that of Elahi et +al.~\cite{elahi-ccs2014} \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 @@ -1532,8 +1658,8 @@ 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 +Adoption of these approaches faces some challenges specific to their use +in Tor. Those issues and some suggestions for handling them are \begin{compactenum} \item Implementation difficulty: Making use of sophisticated cryptographic tools, such as non-standard cryptosystems or novel @@ -1551,20 +1677,18 @@ 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} - -\section{Recommendation} -\label{sec:recommendation} - -\section*{Next steps in writing this report} - -\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} +\section{Conclusion} +Statistics about the usage and performance of Tor hidden services could +serve many valuable purposes. However, doing so in a privacy-preserving +manner is challenging. We have described the kinds of hidden-service +statistics that Tor relays are in a position to collect and the main +criteria +on which collection procedures should be evaluated. In particular, we have +provided a list of privacy goals for Tor hidden services that goes beyond +simply hiding the server's location. Furthermore, we explored how +statistics might be published in a privacy-preserving way, and we gave two +specific algorithms for publishing broadly useful count and distribution +statistics. \bibliography{hidden-service-stats} -\end{document} - +\end{document} \ No newline at end of file diff --git a/2015/hidden-service-stats/protocol.odg b/2015/hidden-service-stats/protocol.odg index 729c8eb..7a26776 100644 Binary files a/2015/hidden-service-stats/protocol.odg and b/2015/hidden-service-stats/protocol.odg differ

1 0

Jump to page:

2025

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

tor-commits June 2015