January 2015 - tor-commits - lists.torproject.org

[torspec/master] Add proposal 239
by nickm＠torproject.org 06 Jan '15

06 Jan '15

commit 8f3e6ce19054546a387bfce94f5c614de2d6c69f Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Jan 6 13:33:12 2015 -0500 Add proposal 239 --- proposals/000-index.txt | 2 + proposals/239-consensus-hash-chaining.txt | 99 +++++++++++++++++++++++++++++ 2 files changed, 101 insertions(+) diff --git a/proposals/000-index.txt b/proposals/000-index.txt index 8a13bf8..9af0405 100644 --- a/proposals/000-index.txt +++ b/proposals/000-index.txt @@ -159,6 +159,7 @@ Proposals by number: 236 The move to a single guard node [OPEN] 237 All relays are directory servers [OPEN] 238 Better hidden service stats from Tor relays [DRAFT] +239 Consensus Hash Chaining [DRAFT] Proposals by status: @@ -182,6 +183,7 @@ Proposals by status: 231 Migrating authority RSA1024 identity keys [for 0.2.?] 235 Stop assigning (and eventually supporting) the Named flag [for 0.2.5] 238 Better hidden service stats from Tor relays + 239 Consensus Hash Chaining NEEDS-REVISION: 131 Help users to verify they are using Tor 190 Bridge Client Authorization Based on a Shared Secret diff --git a/proposals/239-consensus-hash-chaining.txt b/proposals/239-consensus-hash-chaining.txt new file mode 100644 index 0000000..6cb16f1 --- /dev/null +++ b/proposals/239-consensus-hash-chaining.txt @@ -0,0 +1,99 @@ +Filename: 239-consensus-hash-chaining.txt +Title: Consensus Hash Chaining +Author: Nick Mathewson, Andrea Shepard +Created: 06-Jan-2015 +Status: Draft + +1. Introduction and overview + + To avoid some categories of attacks against directory authorities + and their keys, it would be handy to have an explicit hash chain in + consensuses. + +2. Directory authority operation + + We add the following field to votes and consensuses: + + previous-consensus ISOTIME [SP HashName "=" Base16]* NL + + where HashName is any keyword. + + This field may occur any number of times. + + The date in a previous-consensus line in a vote is the valid-after + date of the consensus the line refers to. The hash should be + computed over the signed portion of the consensus document. A + directory authority should include a previous-consensus line for a + consensus using all hashes it supports for all consensuses it knows + which are still valid, together with the two most recently expired + ones. + + When this proposal is implemented, a new consensus method should be + allocated for adding previous-consensus lines to the consensus. + + A previous-consensus line is included in the consensus if and only + if a line with that date was listed by more than half of the + authorities whose votes are under consideration. A hash is included + in that line if the hash was listed by more than half of the + authorities whose votes are under consideration. Hashes are sorted + lexically with a line by hashname; dates are sorted in temporal + order. + + If, when computing a consensus, the authorities find that any + previous-consensus line is *incompatible* with another, they must + issue a loud warning. Two lines are incompatible if they have the + same ISOTIME, but different values for the the same HashName. + + The hash "sha256" is mandatory. + +3. Client and cache operation + + All parties receiving consensus documents should validate + previous-consensus lines, and complain loudly if a hash fails to + match. + + When a party receives a consensus document, it SHOULD check all + previous-consensus lines against any previous consensuses it has + retained, and if a hash fails to match it SHOULD warn loudly in the + log mentioning the specific hashes and valid-after times in + question, and store both the new consensus containing the + mismatching hashes and the old consensus being checked for later + analysis. An option SHOULD be provided to disable operation as a + client or as a hidden service if this occurs. + + All relying parties SHOULD by default retain all valid consensuses + they download plus two; but see "Security considerations" below. + + If a hash is not mismatched, the relying party may nonetheless be + unable to validate the chain: either because there is a gap in the + chain itself, or because the relying party does not have any of the + consensuses that the latest consensus mentions. If this happens, + the relying party should log a warning stating the specific cause, + the hashes and valid-after time of both the consensus containing the + unverifiable previous-consensus line and the hashes and valid-after + time of the line for each such line, and retain a copy of the + consensus document in question. A relying party MAY provide an + option to disable operation as a client or hidden service in this + event, but due to the risk that breaks in the chain may occur + accidentally, such an option SHOULD be disabled by default if + provided. + + If a relying party starts up and finds only very old consensuses + such that no previous-consensus lines can be verified, it should log + a notice of the gap along the lines of "consensus (date, hash) is + quite new. Can't chain back to old consensus (date, hash)". If it + has no old consensuses at all, it should log an info-level message + of the form "we got consensus (date, hash). We haven't got any + older consensuses, so we won't do any hash chain verification" + +4. Security Considerations: + + * Retaining consensus documents on clients might leak information + about when the client was active if a disk is later stolen or the + client compromised. This should be documented somewhere and an + option to disable (but thereby also disable verifying + previous-consensus hashes) should be provided. + + * Clients MAY offer the option to retain previous consensuses in + memory only to allow for validation without the potential disk + leak.

1 0

[tor/master] Make test_cmdline_args.py work on Windows
by nickm＠torproject.org 06 Jan '15

06 Jan '15

commit f4221a809a71077cacda67fbeaee7cad064db602 Author: Nick Mathewson <nickm(a)torproject.org> Date: Tue Jan 6 13:26:52 2015 -0500 Make test_cmdline_args.py work on Windows Patch from Gisle Vanem on tor-dev ml --- changes/fix-test-cmdline-args | 4 ++++ src/test/test_cmdline_args.py | 6 +++--- 2 files changed, 7 insertions(+), 3 deletions(-) diff --git a/changes/fix-test-cmdline-args b/changes/fix-test-cmdline-args new file mode 100644 index 0000000..6902d19 --- /dev/null +++ b/changes/fix-test-cmdline-args @@ -0,0 +1,4 @@ + o Testing: + - Make the test_cmdline_args.py script work correctly on Windows. + Patch from Gisle Vanem. + \ No newline at end of file diff --git a/src/test/test_cmdline_args.py b/src/test/test_cmdline_args.py index 55d1cdb..c8e68e8 100755 --- a/src/test/test_cmdline_args.py +++ b/src/test/test_cmdline_args.py @@ -57,14 +57,14 @@ def run_tor(args, failure=False): raise UnexpectedFailure() elif not result and failure: raise UnexpectedSuccess() - return b2s(output) + return b2s(output.replace('\r\n','\n')) def spaceify_fp(fp): for i in range(0, len(fp), 4): yield fp[i:i+4] def lines(s): - out = s.split("\n") + out = s.splitlines() if out and out[-1] == '': del out[-1] return out @@ -151,7 +151,7 @@ class CmdlineTests(unittest.TestCase): if os.stat(TOR).st_mtime < os.stat(main_c).st_mtime: self.skipTest(TOR+" not up to date") out = run_tor(["--digests"]) - main_line = [ l for l in lines(out) if l.endswith("/main.c") ] + main_line = [ l for l in lines(out) if l.endswith("/main.c") or l.endswith(" main.c") ] digest, name = main_line[0].split() f = open(main_c, 'rb') actual = hashlib.sha1(f.read()).hexdigest()

1 0

[torspec/master] Fix an error in the description of KDF-RFC5869
by nickm＠torproject.org 06 Jan '15

06 Jan '15

commit 8a452ace6bb9a1aaaf160ac961f11aa5acaafb41 Author: Tom van der Woerdt <info(a)tvdw.eu> Date: Thu Jan 1 00:42:27 2015 +0100 Fix an error in the description of KDF-RFC5869 --- tor-spec.txt | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/tor-spec.txt b/tor-spec.txt index 923ea63..43bb181 100644 --- a/tor-spec.txt +++ b/tor-spec.txt @@ -1006,7 +1006,7 @@ see tor-design.pdf. Where H(x,t) is HMAC_SHA256 with value x and key t and K_1 = H(m_expand | INT8(1) , KEY_SEED ) - and K_(i+1) = H(K_i | m_expand | INT8(i) , KEY_SEED ) + and K_(i+1) = H(K_i | m_expand | INT8(i+1) , KEY_SEED ) and m_expand is an arbitrarily chosen value, and INT8(i) is a octet with the value "i".

1 0

[torspec/master] MSBs are actually the other way around
by nickm＠torproject.org 06 Jan '15

06 Jan '15

commit c2beaa8cb141b870b712380af96f9d87c9cb4d54 Author: Tom van der Woerdt <info(a)tvdw.eu> Date: Thu Jan 1 17:00:35 2015 +0100 MSBs are actually the other way around --- tor-spec.txt | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/tor-spec.txt b/tor-spec.txt index cf54271..923ea63 100644 --- a/tor-spec.txt +++ b/tor-spec.txt @@ -754,8 +754,8 @@ see tor-design.pdf. keys are compared numerically by modulus.) In link protocol version 4 or higher, whichever node initiated the - connection sets its MSB to 0, and whichever node didn't initiate the - connection sets its MSB to 1. + connection sets its MSB to 1, and whichever node didn't initiate the + connection sets its MSB to 0. (An OP with no public key MAY choose any CircID it wishes, since an OP never needs to process a CREATE cell.)

1 0

[torspec/master] Add proposals/238-hs-relay-stats.txt.
by nickm＠torproject.org 06 Jan '15

06 Jan '15

commit 909b63b6f7512582d05d1a089fb62a426845818c Author: George Kadianakis <desnacked(a)riseup.net> Date: Tue Nov 18 16:57:09 2014 +0000 Add proposals/238-hs-relay-stats.txt. --- proposals/238-hs-relay-stats.txt | 92 ++++++++++++++++++++++++++++++++++++++ 1 file changed, 92 insertions(+) diff --git a/proposals/238-hs-relay-stats.txt b/proposals/238-hs-relay-stats.txt new file mode 100644 index 0000000..a081989 --- /dev/null +++ b/proposals/238-hs-relay-stats.txt @@ -0,0 +1,92 @@ +Filename: 238-hs-relay-stats + +Title: Better hidden service stats from Tor relays +Author: George Kadianakis, David Goulet, Karsten Loesing +Created: 2014-11-17 +Status: Incomplete + +0. Motivation + + Hidden Services is one of the least understood parts of the Tor + network. We don't really know how many hidden services there are + and how much they are used. + + This proposal suggests that Tor relays include some hidden service + related stats to their extra info descriptors. No stats are + collected from Tor hidden services or clients. + + While uncertainty might be a good thing in a hidden network, + learning more information about the usage of hidden services can be + helpful. + + For example, learning how many cells are sent for hidden service + purposes tells us whether hidden service traffic is 2% of the Tor + network traffic or 90% of the Tor network traffic. This info can + also help us during load balancing, for example if we change the + path building of hidden services to mitigate guard discovery + attacks [XXX]. + # XXX Is "HS purposes" only RP traffic? Or also IP traffic? + + Also, learning the number of hidden services, can help us + understand how widespread hidden services are. It will also help us + understand approximately how much load is put in the network by + hidden service logistics, like introduction point circuits etc. + +1. Design + + Tor relays will add some fields related to hidden service + statistics in their extra-info descriptors. + + Tor relays collect these statistics by keeping track of their + hidden service directory or rendezvous point activities, slightly + obfuscating the numbers and posting them to the directory + authorities. Extra-info descriptors are posted to directory + authorities every 24 hours. + +2. Implementation + +2.1. Hidden service traffic statistics + + Tor HSDirs will add the following field to their extra-info + descriptor: + + "hs-traffic" ... XXX + +2.2. HSDir hidden service counting + + Tor HSDirs will add the following field to their extra-info + descriptor: + + "dirreq-v3-hsdir" key=val,... NL + [At most once.] + + Statistics about HS directory activities. + The current list of statistics is as follows: + + "hs-num": The approximate number of HSes that the HSDir is + hosting descriptors for at the time the extra-info + descriptor was created. + + + To derive this, HSDirs are expected to walk over their descriptor + caches and count the number of HSes contained. The number is then + obfuscated slightly by a small noise factor that introduces 10% + inaccuracy. + + More specifically: + + hs-num = <number of HSes> * <random real \in [0.9, 1.1]> + + + + time_t cutoff = now - REND_CACHE_MAX_AGE - REND_CACHE_MAX_SKEW; + +3. Discussion + +3.1. Count only RP cells? Or also IP cells? + +3.2. Why obfuscation on HSDirs stats? And how much? + + + +[XXX]: guard discovery: https://lists.torproject.org/pipermail/tor-dev/2014-September/007474.html

1 0

[torspec/master] Add feedback based on Aaron's reply.
by nickm＠torproject.org 06 Jan '15

06 Jan '15

commit 47691019b8bbb33e7fd0fd40b5c21dba40e23315 Author: Karsten Loesing <karsten.loesing(a)gmx.net> Date: Thu Nov 20 09:18:46 2014 +0100 Add feedback based on Aaron's reply. --- proposals/238-hs-relay-stats.txt | 88 +++++++++++++++++++++++++++----------- 1 file changed, 64 insertions(+), 24 deletions(-) diff --git a/proposals/238-hs-relay-stats.txt b/proposals/238-hs-relay-stats.txt index 135048b..b5a0bfc 100644 --- a/proposals/238-hs-relay-stats.txt +++ b/proposals/238-hs-relay-stats.txt @@ -1,7 +1,7 @@ Filename: 238-hs-relay-stats Title: Better hidden service stats from Tor relays -Author: George Kadianakis, David Goulet, Karsten Loesing +Author: George Kadianakis, David Goulet, Karsten Loesing, Aaron Johnson Created: 2014-11-17 Status: Incomplete @@ -104,7 +104,26 @@ Status: Incomplete "read-history" lines to compute similar fractions of traffic used for hidden services. The goal would be to avoid enabling "cell-*" statistics by default. In order for this to work we'll have to - multiply reported cell numbers with the default cell size of 512 bytes. + multiply reported cell numbers with the default cell size of 512 bytes + (we cannot infer the actual number of bytes, because cells are + end-to-end encrypted between client and service). + + A possible alternative to multiplying the number of cells with a random + factor is to introduce additive noise. Let's suppose that we would + like to obscure any individual connection that contains C cells or + fewer (obscuring extremely and unusually large connections seems + hopeless but unnecessary). That is, we don't want the (distribution + of) the cell count from any relay to change by much whether or not C + cells are removed. The standard differential privacy approach would be + to *add* noise from the Laplace distribution Lab(\epsilon/C), where + \epsilon controls how much the statistics *distribution* can + multiplicatively differ. This is not to say that we need to add noise + exactly from that distribution (maybe we weaken the guarantee slightly + to get better accuracy), but the same idea applies. This would apply + the same to both large and small relays. We *want* to learn roughly + how much hidden-service traffic each relay has - we just want to + obscure the exact number within some tolerance. (Would we want to + include \epsilon/C in the "hidserv-rend-relayed-cells" line?) 2.2. HSDir hidden service counting @@ -143,8 +162,11 @@ Status: Incomplete Here are some numbers: there are about 3000 directories, and each descriptor is stored on three directories. So, each directory is responsible for roughly 1/1000 of descriptor identifiers. There are - two replicas for each descriptor, and descriptor identifiers change - once per day. Hence, each descriptor is stored to four places in + two replicas for each descriptor (that is, each descriptor is stored + under two descriptor identifiers), and descriptor identifiers change + once per day (which means that, during a 24-hour period, there are two + opportunities for each directory to see a descriptor). Hence, each + descriptor is stored to four places in identifier space throughout a 24-hour period. The probability of any given directory to see a given hidden-service identity is 1-(1-1/1000)^4 = 0.00399 = 1/250. This approximation constitutes an @@ -154,36 +176,54 @@ Status: Incomplete A possible inaccuracy in the estimation algorithm comes from the fact that a relay may not be acting as hidden-service directory during the - full statistics interval. We suggest adding the following line to - handle this case better. + full statistics interval. We'll have to look at consensuses to + determine when the relay first received the "HSDir" flag, and only + consider the part of the statistics interval following the valid-after + time of that consensus. - Tor relays also add the following line to their extra-info descriptor, - preceding any "hidserv-dir-*" lines: + Finally, the intentionally added randomness leads to either under- or + overcounting hidden services by up to 10%. - "hidserv-dir-start" YYYY-MM-DD HH:00:00 NL - [At most once.] +3. Security - YYYY-MM-DD HH:00:00 defines the first hour when this - hidden-service directory accepted either a publish or fetch - request for a hidden-service descriptor. + The main security considerations that need discussion are what an + adversary could do with reported statistics that they couldn't do + without them. In the following, we're going through things the + adversary could learn, how plausible that is, and how much we care. + (All these things refer to hidden-service traffic, not to + hidden-service counting. We should think about the latter, too.) - Finally, the intentionally added randomness leads to either under- or - overcounting hidden services by up to 10%. +3.1. Identify rendezvous point of high-volume and long-lived connection + + The adversary could identify the rendezvous point of a very large and + very long-lived HS connection by observing a relay with unexpectedly + large relay cell count. -3. Discussion +3.2. Identify hard-coded rendezvous points -3.1. Count only RP cells? Or also IP cells? + The adversary could observe if there are RPs that consistently report + large cell counts. These might be HS clients with hardcoded RPs, and + that would allow the adversary to identify this behavior and + potentially link that with a known HS client of known behavior (e.g. + a botnet client). Then the adversary could figure out which RPs to + target. + +3.3. Identify number of users of a hidden service + + The adversary may be able to identify the number of users + of an HS if he knows the amount of traffic on a connection to that HS + (which he potentially can determine himself) and knows when that + service goes up or down. He can look at the change in the total + reported RP traffic to determine about how many fewer HS users there + are when that HS is down. + +4. Discussion + +4.1. Count only RP cells? Or also IP cells? As discussed on IRC, counting only RP cells should be fine for now. Everything else is protocol overhead, which includes HSDir traffic, IPo traffic, RPo traffic before the first RELAY cell, etc. We can always be smarter later. -KL -3.2. Why obfuscation on HSDirs stats? And how much? - As discussed on IRC, maybe we should obfuscate small numbers more than - large numbers by adding a random number in [-20, 20]. Or we could - require a reporting threshold, if we can figure out how that cannot be - gamed by the adversary by making the required number of requests - themselves. Let's ask Aaron Johnson. -KL - [XXX]: guard discovery: https://lists.torproject.org/pipermail/tor-dev/2014-September/007474.html

1 0

[torspec/master] Revise George's hidden-service statistics proposal.
by nickm＠torproject.org 06 Jan '15

06 Jan '15

commit 89282aba291d12a1a539606ebf02af3047bd61fa Author: Karsten Loesing <karsten.loesing(a)gmx.net> Date: Wed Nov 19 10:32:56 2014 +0100 Revise George's hidden-service statistics proposal. --- proposals/238-hs-relay-stats.txt | 151 +++++++++++++++++++++++++++++++------- 1 file changed, 124 insertions(+), 27 deletions(-) diff --git a/proposals/238-hs-relay-stats.txt b/proposals/238-hs-relay-stats.txt index a081989..135048b 100644 --- a/proposals/238-hs-relay-stats.txt +++ b/proposals/238-hs-relay-stats.txt @@ -45,48 +45,145 @@ Status: Incomplete 2. Implementation -2.1. Hidden service traffic statistics - - Tor HSDirs will add the following field to their extra-info - descriptor: - - "hs-traffic" ... XXX - -2.2. HSDir hidden service counting +2.0. Hidden service statistics interval - Tor HSDirs will add the following field to their extra-info - descriptor: + We want relays to report hidden-service statistics over a long-enough + time period to not put users at risk. Similar to other statistics, we + suggest a 24-hour statistics interval. All related statistics are + collected at the end of that interval and included in the next + extra-info descriptors published by the relay. - "dirreq-v3-hsdir" key=val,... NL - [At most once.] + Tor relays will add the following line to their extra-info descriptor: - Statistics about HS directory activities. - The current list of statistics is as follows: + "hidserv-stats-end" YYYY-MM-DD HH:MM:SS (NSEC s) NL + [At most once.] - "hs-num": The approximate number of HSes that the HSDir is - hosting descriptors for at the time the extra-info - descriptor was created. + YYYY-MM-DD HH:MM:SS defines the end of the included measurement + interval of length NSEC seconds (86400 seconds by default). + A "hidserv-stats-end" line, as well as any other "hidserv-*" line, + is first added after the relay has been running for at least 24 + hours. - To derive this, HSDirs are expected to walk over their descriptor - caches and count the number of HSes contained. The number is then - obfuscated slightly by a small noise factor that introduces 10% - inaccuracy. - - More specifically: - - hs-num = <number of HSes> * <random real \in [0.9, 1.1]> +2.1. Hidden service traffic statistics + We want to learn how much of the total Tor network traffic is caused by + hidden service usage. There are three phases in the rendezvous + protocol where traffic is generated: (1) when hidden services make + themselves available in the network, (2) when clients open connections + to hidden services, and (3) when clients exchange application data with + hidden services. We expect (3) to consume most bytes here, so we're + focusing on this only. More precisely, we measure hidden service + traffic by counting RELAY cells seen on a rendezvous point after + receiving a RENDEZVOUS1 cell. These RELAY cells include commands to + open or close application streams, and they include application data. + + Tor relays will add the following line to their extra-info descriptor: + + "hidserv-rend-relayed-cells" SP num NL + [At most once.] + + Approximate number of RELAY cells seen in either direction on a + circuit after receiving and successfully processing a RENDEZVOUS1 + cell. The actual number observed by the directory is multiplied + with a random number in [0.9, 1.1] before being reported. + + The keyword indicates that this line is part of hidden-service + statistics ("hidserv") and contains aggregate data from the relay + acting as rendezvous point ("rend"). + + We plan to extrapolate reported values to network totals by dividing + values by the probability of clients picking relays as rendezvous + point. This approach should become more precise on faster relays and + the more relays report these statistics. + + We also plan to compare reported values with "cell-*" statistics to + learn what fraction of traffic can be attributed to hidden services. + + Ideally, we'd be able to compare values to "write-history" and + "read-history" lines to compute similar fractions of traffic used for + hidden services. The goal would be to avoid enabling "cell-*" + statistics by default. In order for this to work we'll have to + multiply reported cell numbers with the default cell size of 512 bytes. +2.2. HSDir hidden service counting - time_t cutoff = now - REND_CACHE_MAX_AGE - REND_CACHE_MAX_SKEW; + We also want to learn how many hidden services exist in the network. + The best place to learn this is at hidden service directories where + hidden services publish their descriptors. + + Tor relays will add the following line to their extra-info descriptor: + + "hidserv-dir-published-ids" SP num NL + [At most once.] + + Approximate number of unique hidden-service identities seen in + descriptors published to and accepted by this hidden-service + directory. The actual number observed by the directory is + multiplied with a random number in [0.9, 1.1] before being + reported. + + This statistic requires keeping a separate data structure with unique + identities seen during the current statistics interval. We could, in + theory, have relays iterate over their descriptor caches when producing + the daily hidden-service statistics blurb. But it's unclear how + caching would affect results from such an approach, because descriptors + published at the start of the current statistics interval could already + have been removed, and descriptors published in the last statistics + interval could still be present. Keeping a separate data structure, + possibly even a probabilistic one, seems like the more accurate + approach. + + We plan to extrapolate this value to network totals by calculating what + fraction of hidden-service identities this relay was supposed to see. + This extrapolation will be very rough, because each hidden-service + directory is only responsible for a tiny share of hidden-service + descriptors, and there is no way to increase that share significantly. + + Here are some numbers: there are about 3000 directories, and each + descriptor is stored on three directories. So, each directory is + responsible for roughly 1/1000 of descriptor identifiers. There are + two replicas for each descriptor, and descriptor identifiers change + once per day. Hence, each descriptor is stored to four places in + identifier space throughout a 24-hour period. The probability of any + given directory to see a given hidden-service identity is + 1-(1-1/1000)^4 = 0.00399 = 1/250. This approximation constitutes an + upper threshold, because it assumes that services are running all day. + An extrapolation based on this formula will lead to undercounting the + total number of hidden services. + + A possible inaccuracy in the estimation algorithm comes from the fact + that a relay may not be acting as hidden-service directory during the + full statistics interval. We suggest adding the following line to + handle this case better. + + Tor relays also add the following line to their extra-info descriptor, + preceding any "hidserv-dir-*" lines: + + "hidserv-dir-start" YYYY-MM-DD HH:00:00 NL + [At most once.] + + YYYY-MM-DD HH:00:00 defines the first hour when this + hidden-service directory accepted either a publish or fetch + request for a hidden-service descriptor. + + Finally, the intentionally added randomness leads to either under- or + overcounting hidden services by up to 10%. 3. Discussion 3.1. Count only RP cells? Or also IP cells? + As discussed on IRC, counting only RP cells should be fine for now. + Everything else is protocol overhead, which includes HSDir traffic, + IPo traffic, RPo traffic before the first RELAY cell, etc. We can + always be smarter later. -KL 3.2. Why obfuscation on HSDirs stats? And how much? - + As discussed on IRC, maybe we should obfuscate small numbers more than + large numbers by adding a random number in [-20, 20]. Or we could + require a reporting threshold, if we can figure out how that cannot be + gamed by the adversary by making the required number of requests + themselves. Let's ask Aaron Johnson. -KL [XXX]: guard discovery: https://lists.torproject.org/pipermail/tor-dev/2014-September/007474.html

1 0

[torspec/master] Add more feedback from talking to Aaron.
by nickm＠torproject.org 06 Jan '15

06 Jan '15

commit 639969c32dd056524eb15a1e2e270d24f02b6a1b Author: Karsten Loesing <karsten.loesing(a)gmx.net> Date: Thu Nov 20 13:46:01 2014 +0100 Add more feedback from talking to Aaron. --- proposals/238-hs-relay-stats.txt | 12 ++++++++---- 1 file changed, 8 insertions(+), 4 deletions(-) diff --git a/proposals/238-hs-relay-stats.txt b/proposals/238-hs-relay-stats.txt index b5a0bfc..2f24434 100644 --- a/proposals/238-hs-relay-stats.txt +++ b/proposals/238-hs-relay-stats.txt @@ -115,15 +115,17 @@ Status: Incomplete hopeless but unnecessary). That is, we don't want the (distribution of) the cell count from any relay to change by much whether or not C cells are removed. The standard differential privacy approach would be - to *add* noise from the Laplace distribution Lab(\epsilon/C), where + to *add* noise from the Laplace distribution Lap(\epsilon/C), where \epsilon controls how much the statistics *distribution* can multiplicatively differ. This is not to say that we need to add noise exactly from that distribution (maybe we weaken the guarantee slightly to get better accuracy), but the same idea applies. This would apply the same to both large and small relays. We *want* to learn roughly how much hidden-service traffic each relay has - we just want to - obscure the exact number within some tolerance. (Would we want to - include \epsilon/C in the "hidserv-rend-relayed-cells" line?) + obscure the exact number within some tolerance. We'll probably want to + include the algorithm and parameters used for adding noise in the + "hidserv-rend-relayed-cells" line, as in, "lap=x" with x being + \epsilon/C. 2.2. HSDir hidden service counting @@ -182,7 +184,9 @@ Status: Incomplete time of that consensus. Finally, the intentionally added randomness leads to either under- or - overcounting hidden services by up to 10%. + overcounting hidden services by up to 10%. A probably better + alternative for adding noise is to use the Laplace approach suggested + above. 3. Security

1 0

[torspec/master] Tidy up the proposal.
by nickm＠torproject.org 06 Jan '15

06 Jan '15

commit 8579a06da38c3e5821c5145c9037892861aa75da Author: George Kadianakis <desnacked(a)riseup.net> Date: Tue Nov 25 17:33:19 2014 +0000 Tidy up the proposal. --- proposals/238-hs-relay-stats.txt | 196 +++++++++++++++++++------------------- 1 file changed, 97 insertions(+), 99 deletions(-) diff --git a/proposals/238-hs-relay-stats.txt b/proposals/238-hs-relay-stats.txt index 2f24434..bcadd52 100644 --- a/proposals/238-hs-relay-stats.txt +++ b/proposals/238-hs-relay-stats.txt @@ -1,9 +1,8 @@ -Filename: 238-hs-relay-stats - +Filename: 238-hs-relay-stats.txt Title: Better hidden service stats from Tor relays Author: George Kadianakis, David Goulet, Karsten Loesing, Aaron Johnson Created: 2014-11-17 -Status: Incomplete +Status: Draft 0. Motivation @@ -24,13 +23,13 @@ Status: Incomplete network traffic or 90% of the Tor network traffic. This info can also help us during load balancing, for example if we change the path building of hidden services to mitigate guard discovery - attacks [XXX]. - # XXX Is "HS purposes" only RP traffic? Or also IP traffic? + attacks [0]. - Also, learning the number of hidden services, can help us - understand how widespread hidden services are. It will also help us - understand approximately how much load is put in the network by - hidden service logistics, like introduction point circuits etc. + Also, learning the number of hidden services, can give us an + understanding of how widespread hidden services are. It will also + help us understand approximately how much load is put in the + network by hidden service logistics, like introduction point + circuits etc. 1. Design @@ -45,7 +44,7 @@ Status: Incomplete 2. Implementation -2.0. Hidden service statistics interval +2.1. Hidden service statistics interval We want relays to report hidden-service statistics over a long-enough time period to not put users at risk. Similar to other statistics, we @@ -65,7 +64,7 @@ Status: Incomplete is first added after the relay has been running for at least 24 hours. -2.1. Hidden service traffic statistics +2.2. Hidden service traffic statistics We want to learn how much of the total Tor network traffic is caused by hidden service usage. There are three phases in the rendezvous @@ -83,51 +82,17 @@ Status: Incomplete "hidserv-rend-relayed-cells" SP num NL [At most once.] - Approximate number of RELAY cells seen in either direction on a - circuit after receiving and successfully processing a RENDEZVOUS1 - cell. The actual number observed by the directory is multiplied - with a random number in [0.9, 1.1] before being reported. + Approximate number of RELAY cells seen in either direction on + a circuit after receiving and successfully processing a + RENDEZVOUS1 cell. The actual number observed by the directory + is multiplied with a random number in [0.9, 1.1] and then gets + floored before being reported. The keyword indicates that this line is part of hidden-service statistics ("hidserv") and contains aggregate data from the relay acting as rendezvous point ("rend"). - We plan to extrapolate reported values to network totals by dividing - values by the probability of clients picking relays as rendezvous - point. This approach should become more precise on faster relays and - the more relays report these statistics. - - We also plan to compare reported values with "cell-*" statistics to - learn what fraction of traffic can be attributed to hidden services. - - Ideally, we'd be able to compare values to "write-history" and - "read-history" lines to compute similar fractions of traffic used for - hidden services. The goal would be to avoid enabling "cell-*" - statistics by default. In order for this to work we'll have to - multiply reported cell numbers with the default cell size of 512 bytes - (we cannot infer the actual number of bytes, because cells are - end-to-end encrypted between client and service). - - A possible alternative to multiplying the number of cells with a random - factor is to introduce additive noise. Let's suppose that we would - like to obscure any individual connection that contains C cells or - fewer (obscuring extremely and unusually large connections seems - hopeless but unnecessary). That is, we don't want the (distribution - of) the cell count from any relay to change by much whether or not C - cells are removed. The standard differential privacy approach would be - to *add* noise from the Laplace distribution Lap(\epsilon/C), where - \epsilon controls how much the statistics *distribution* can - multiplicatively differ. This is not to say that we need to add noise - exactly from that distribution (maybe we weaken the guarantee slightly - to get better accuracy), but the same idea applies. This would apply - the same to both large and small relays. We *want* to learn roughly - how much hidden-service traffic each relay has - we just want to - obscure the exact number within some tolerance. We'll probably want to - include the algorithm and parameters used for adding noise in the - "hidserv-rend-relayed-cells" line, as in, "lap=x" with x being - \epsilon/C. - -2.2. HSDir hidden service counting +2.3. HSDir hidden service counting We also want to learn how many hidden services exist in the network. The best place to learn this is at hidden service directories where @@ -141,8 +106,8 @@ Status: Incomplete Approximate number of unique hidden-service identities seen in descriptors published to and accepted by this hidden-service directory. The actual number observed by the directory is - multiplied with a random number in [0.9, 1.1] before being - reported. + multiplied with a random number in [0.9, 1.1] and then gets + floored before being reported. This statistic requires keeping a separate data structure with unique identities seen during the current statistics interval. We could, in @@ -155,6 +120,65 @@ Status: Incomplete possibly even a probabilistic one, seems like the more accurate approach. +3. Security + + The main security considerations that need discussion are what an + adversary could do with reported statistics that they couldn't do + without them. In the following, we're going through things the + adversary could learn, how plausible that is, and how much we care. + (All these things refer to hidden-service traffic, not to + hidden-service counting. We should think about the latter, too.) + +3.1. Identify rendezvous point of high-volume and long-lived connection + + The adversary could identify the rendezvous point of a very large and + very long-lived HS connection by observing a relay with unexpectedly + large relay cell count. + +3.2. Identify number of users of a hidden service + + The adversary may be able to identify the number of users + of an HS if he knows the amount of traffic on a connection to that HS + (which he potentially can determine himself) and knows when that + service goes up or down. He can look at the change in the total + reported RP traffic to determine about how many fewer HS users there + are when that HS is down. + +4. Discussion + +4.1. Why count only RP cells? Why not also count IP cells? + + As discussed on IRC, counting only RP cells should be fine for now. + Everything else is protocol overhead, which includes HSDir traffic, + introduction point traffic, or rendezvous point traffic before the + first RELAY cell, etc. + + Furthermore, introduction points correspond to specific HSes, so + publishing IP cell stats could reveal the popularity of specific + HSes. + +4.2. How to use these stats? + + 4.2.1. How to use RP Cell statistics + + We plan to extrapolate reported values to network totals by dividing + values by the probability of clients picking relays as rendezvous + point. This approach should become more precise on faster relays and + the more relays report these statistics. + + We also plan to compare reported values with "cell-*" statistics to + learn what fraction of traffic can be attributed to hidden services. + + Ideally, we'd be able to compare values to "write-history" and + "read-history" lines to compute similar fractions of traffic used for + hidden services. The goal would be to avoid enabling "cell-*" + statistics by default. In order for this to work we'll have to + multiply reported cell numbers with the default cell size of 512 bytes + (we cannot infer the actual number of bytes, because cells are + end-to-end encrypted between client and service). + + 4.2.2. How to use HSDir HS statistics + We plan to extrapolate this value to network totals by calculating what fraction of hidden-service identities this relay was supposed to see. This extrapolation will be very rough, because each hidden-service @@ -183,51 +207,25 @@ Status: Incomplete consider the part of the statistics interval following the valid-after time of that consensus. - Finally, the intentionally added randomness leads to either under- or - overcounting hidden services by up to 10%. A probably better - alternative for adding noise is to use the Laplace approach suggested - above. - -3. Security - - The main security considerations that need discussion are what an - adversary could do with reported statistics that they couldn't do - without them. In the following, we're going through things the - adversary could learn, how plausible that is, and how much we care. - (All these things refer to hidden-service traffic, not to - hidden-service counting. We should think about the latter, too.) - -3.1. Identify rendezvous point of high-volume and long-lived connection - - The adversary could identify the rendezvous point of a very large and - very long-lived HS connection by observing a relay with unexpectedly - large relay cell count. - -3.2. Identify hard-coded rendezvous points - - The adversary could observe if there are RPs that consistently report - large cell counts. These might be HS clients with hardcoded RPs, and - that would allow the adversary to identify this behavior and - potentially link that with a known HS client of known behavior (e.g. - a botnet client). Then the adversary could figure out which RPs to - target. - -3.3. Identify number of users of a hidden service - - The adversary may be able to identify the number of users - of an HS if he knows the amount of traffic on a connection to that HS - (which he potentially can determine himself) and knows when that - service goes up or down. He can look at the change in the total - reported RP traffic to determine about how many fewer HS users there - are when that HS is down. - -4. Discussion - -4.1. Count only RP cells? Or also IP cells? - As discussed on IRC, counting only RP cells should be fine for now. - Everything else is protocol overhead, which includes HSDir traffic, - IPo traffic, RPo traffic before the first RELAY cell, etc. We can - always be smarter later. -KL +4.3. Multiplicative or additive noise? + A possible alternative to multiplying the number of cells with a random + factor is to introduce additive noise. Let's suppose that we would + like to obscure any individual connection that contains C cells or + fewer (obscuring extremely and unusually large connections seems + hopeless but unnecessary). That is, we don't want the (distribution + of) the cell count from any relay to change by much whether or not C + cells are removed. The standard differential privacy approach would be + to *add* noise from the Laplace distribution Lap(\epsilon/C), where + \epsilon controls how much the statistics *distribution* can + multiplicatively differ. This is not to say that we need to add noise + exactly from that distribution (maybe we weaken the guarantee slightly + to get better accuracy), but the same idea applies. This would apply + the same to both large and small relays. We *want* to learn roughly + how much hidden-service traffic each relay has - we just want to + obscure the exact number within some tolerance. We'll probably want to + include the algorithm and parameters used for adding noise in the + "hidserv-rend-relayed-cells" line, as in, "lap=x" with x being + \epsilon/C. -[XXX]: guard discovery: https://lists.torproject.org/pipermail/tor-dev/2014-September/007474.html +[0]: guard discovery: https://lists.torproject.org/pipermail/tor-dev/2014-September/007474.html

1 0

[torspec/master] More up-to-date graphs for our Laplace distributions.
by nickm＠torproject.org 06 Jan '15

06 Jan '15

commit caff5209d4ae8795770b73fffe82b9e40ed34c53 Author: George Kadianakis <desnacked(a)riseup.net> Date: Sun Dec 14 19:49:11 2014 +0200 More up-to-date graphs for our Laplace distributions. --- proposals/238-hs-relay-stats.txt | 8 ++++---- 1 file changed, 4 insertions(+), 4 deletions(-) diff --git a/proposals/238-hs-relay-stats.txt b/proposals/238-hs-relay-stats.txt index d46e35d..e113785 100644 --- a/proposals/238-hs-relay-stats.txt +++ b/proposals/238-hs-relay-stats.txt @@ -286,8 +286,8 @@ Status: Draft [DATA-BINNING]: https://en.wikipedia.org/wiki/Data_binning -[CELL-LAPLACE-GRAPH]: https://raw.githubusercontent.com/corcra/pioton/master/vis/laplacePDF_mu0_b… - https://raw.githubusercontent.com/corcra/pioton/master/vis/laplaceCDF_mu0_b… +[CELL-LAPLACE-GRAPH]: https://raw.githubusercontent.com/corcra/pioton/master/vis/laplacePDF_mu0.0… + https://raw.githubusercontent.com/corcra/pioton/master/vis/laplaceCDF_mu0.0… -[ONIONS-LAPLACE-GRAPH]: https://raw.githubusercontent.com/corcra/pioton/master/vis/laplacePDF_mu0_b… - https://raw.githubusercontent.com/corcra/pioton/master/vis/laplaceCDF_mu0_b… +[ONIONS-LAPLACE-GRAPH]: https://raw.githubusercontent.com/corcra/pioton/master/vis/laplacePDF_mu0.0… + https://raw.githubusercontent.com/corcra/pioton/master/vis/laplaceCDF_mu0.0…

1 0